# Broyden's Method for Solving Fuzzy Nonlinear Equations

Authors: Amirah Ramli; Mohd Lazim Abdullah; Mustafa Mamat
Journal: Advances in Fuzzy Systems
 (2010)

---

## Abstract

Instead of  using standard analytical techniques, like Buckley and Qu method, which are not suitable for solving a system of  fuzzy nonlinear equations where the coefficient is fuzzy number, Broyden's method is  proposed for solving fuzzy nonlinear equations. In this paper, an eight-step algorithm is used to solve fuzzy nonlinear equations. Two numerical examples are given to illustrate the proposed method.


---

## Body

## 1. Introduction

Over time, nonlinear equations have been played a major role in engineering, mathematics, medicines, and robotics.One of the applications in nonlinear problem is in weather which is inherently nonlinear in nature. Another interesting nonlinear problem is in phenomenon such as chaos arises from the difficulties of solving nonlinear equations. Consider the set ofn nonlinear equations
(1)fi(x1,x2,…,xn)=0,i=1,2,…,n.
The general form of the nonlinear equation for n=1 may be simply stated as finding a value of the variable x such that
(2)F(x)=0,
where F:ℜN→ℜN and was denoted  by fi  is any nonlinear function of x. The value of x is then called a solution or root of this equation and may be just one of many equations.Numerical approximation methods are usually needed in solving system of equations when the equation is nonlinear. Solving a system of nonlinear equations is a problem that is avoided when possible, usually by approximating the nonlinear systems by a system of linear equations. But when this is unsatisfactory, the problem must be solved directly [1].However, in most applications, the parameters of the system of nonlinear and measurement are not always represented by crisp number but also by fuzzy numbers. Hence, it is necessary to study numerical method for solving fuzzy nonlinear equations. The concept of fuzzy number arises from the fact that many quantifiable phenomena do not lend themselves to being characterized in terms of absolutely precise numbers [2]. For example, standard analytical techniques proposed by [3] could not be suitable to solve the fuzzy nonlinear equations such as(i)
ax4+bx3+cx2-dx=e,(ii)
fx+gcosx=h,(iii)
ix3-jsinx=k,wherea,b,c,d,e,f,g,h,i,j,k, and x are fuzzy numbers. Therefore, numerical methods for solving the above type equations are needed to be studied. In the study by [4–6], Newton’s method and Steepest Descent’s method were used to solve this type of equations.The disadvantages of Newton’s method arise from  the need to calculate and invert the Jacobian matrixJ(x) at each iteration. Even Newton’s method can converge very rapidly once a good initial value obtained, but it is not always easy to determine this kind of value and also this method is comparatively expensive to employ [1]. Although Steepest Descent’s method does not require a good initial value its weakness is that it has low speed of convergence.In this study, Broyden’s method is proposed to solve this kind of equation. Broyden’s method is superlinearly convergent. This method was chosen due to its being a powerful alternative to Newton’s method, and hence it reduces the amount of calculation at each iteration without significantly degrading the speed of convergence. It replaces the Jacobian matrixJ with a matrix Ak-1 whose inverse is directly determined at each iteration, and it reduces the arithmetic operation form O(n3) to O(n2) [1]. Specifically the objective of this paper is to apply Broyden’s method in solving fuzzy nonlinear equations.Section2 begins with some basic definition about fuzzy numbers and a brief overview of the fuzzy nonlinear equations. Section 3 describes definition of Broyden’s method. Section 4 defines Broyden’s method for solving nonlinear equations. Two numerical examples to illustrate the proposed method are given in Section 5. This paper ends with a short conclusion in Section 6.


## 2. Preliminaries

In this section, some important definitions of fuzzy numbers are reviewed.


### 2.1. Fuzzy Number

Fuzzy numbers are of great importance in fuzzy systems. The fuzzy numbers usually used in applications are the triangular (shaped) and the trapezoidal (shaped) fuzzy numbers [7].Definition 1 (see [8, 9]).
A fuzzy number is set likeu:ℜ→I=[0,1] which satisfies the following:(1)
u is upper semicontinuous,(2)
u(x)=0 is outside some interval [c,d],(3)
there are real numbersa,b such that c≤a≤b≤d:
(3.1)
u(x) is monotonic increasing on [c,a],(3.2)
u(x) is monotonic decreasing on [b,d],(3.3)
u(x)=1,a≤x≤b.The set of all these fuzzy numbers is denoted by E. An equivalent parametric is also given in [10].Definition 2 (see [8, 9]).
Fuzzy numberu in parametric form is a pair (u̲,u̅) of functions   u̲(α),u¯(α),0≤α≤1, which satisfies the following requirements: (1)
u̲(α) is a bounded monotonic increasing left continuous function,(2)
u¯(α) is a bounded monotonic decreasing left continuous function,(3)
u̲(α)≤u¯(α),0≤α≤1.Definition 3 (see [8, 9]).
Triangular fuzzy numberu=(a,c,b) is a popular fuzzy number with the membership function
(3)u(x)={(x-a)(c-a),a≤x≤c,(x-b)(c-b),c≤x≤b,
where c≠a,c≠b, and hence its parametric form is
(4)u̲(α)=a+(c-a)α,u¯(α)=b+(c-b)α.LetTF(ℜ) be the set of all trapezoidal fuzzy numbers. The addition and scalar multiplication of fuzzy numbers are defined by the extension principle and can be equivalently represented as follows [4–6].For arbitraryu=(u̲,u¯),v=(v̲,v¯), and k>0, the addition (u+v) and multiplication by real numberk>0 are defined as (5)(u+v̲)(α)=u̲(α)+v̲(α),(u+v¯)(α)=u¯(α)+v¯(α),(ku̲)(α)=ku̲(α),(ku¯)(α)=ku¯(α).The Definitions1, 2, and 3 are parameters of fuzzy nonlinear equations. In the next section, Broyden’s method and its properties are presented.


## 2.1. Fuzzy Number

Fuzzy numbers are of great importance in fuzzy systems. The fuzzy numbers usually used in applications are the triangular (shaped) and the trapezoidal (shaped) fuzzy numbers [7].Definition 1 (see [8, 9]).
A fuzzy number is set likeu:ℜ→I=[0,1] which satisfies the following:(1)
u is upper semicontinuous,(2)
u(x)=0 is outside some interval [c,d],(3)
there are real numbersa,b such that c≤a≤b≤d:
(3.1)
u(x) is monotonic increasing on [c,a],(3.2)
u(x) is monotonic decreasing on [b,d],(3.3)
u(x)=1,a≤x≤b.The set of all these fuzzy numbers is denoted by E. An equivalent parametric is also given in [10].Definition 2 (see [8, 9]).
Fuzzy numberu in parametric form is a pair (u̲,u̅) of functions   u̲(α),u¯(α),0≤α≤1, which satisfies the following requirements: (1)
u̲(α) is a bounded monotonic increasing left continuous function,(2)
u¯(α) is a bounded monotonic decreasing left continuous function,(3)
u̲(α)≤u¯(α),0≤α≤1.Definition 3 (see [8, 9]).
Triangular fuzzy numberu=(a,c,b) is a popular fuzzy number with the membership function
(3)u(x)={(x-a)(c-a),a≤x≤c,(x-b)(c-b),c≤x≤b,
where c≠a,c≠b, and hence its parametric form is
(4)u̲(α)=a+(c-a)α,u¯(α)=b+(c-b)α.LetTF(ℜ) be the set of all trapezoidal fuzzy numbers. The addition and scalar multiplication of fuzzy numbers are defined by the extension principle and can be equivalently represented as follows [4–6].For arbitraryu=(u̲,u¯),v=(v̲,v¯), and k>0, the addition (u+v) and multiplication by real numberk>0 are defined as (5)(u+v̲)(α)=u̲(α)+v̲(α),(u+v¯)(α)=u¯(α)+v¯(α),(ku̲)(α)=ku̲(α),(ku¯)(α)=ku¯(α).The Definitions1, 2, and 3 are parameters of fuzzy nonlinear equations. In the next section, Broyden’s method and its properties are presented.


## 3. Broyden’s Method

Broyden’s method is a method for solving the system of nonlinear equation and is designed to improve Newton’s method with respect to storage and approximation of the Jacobian. Broyden’s method is generalization of the secant method to multiple dimensions [1]. Once the initial value x0 is obtained, then the next approximation x1 is calculated as the same manner as Newton’s method. In order to obtain x2, the Secant method uses the finite difference approximation
(6)f′(xn)≈f(xn)-f(xn-1)xn-xn-1
as a replacement for f'(xn) in Newton’s method by considering x1-x0 as a vector, and corresponding quotient is undefined. In Broyden’s method, the Jacobian matrix J(x1) is replaced by matrix A1 as follows:
(7)A1(x1-x0)=F(x1)-F(x0).
Any nonzero vector in ℜn can be written as the sum of a multiple of x1-x0. How it acts on the orthogonal complement of x1-x0 is needed to be specified first in order to define the matrix A1 as follows:
(8)A1z=J(x0)z,whenever(x1-x0)tz=0.
Thus, any vector orthogonal to x1-x0 is unaffected by the updated form J(x0), which was used to compute x2. A1 is defined by (7) and (8) as
(9)A1=J(x0)+[F(x1)-F(x0)-J(x0)(x1-x0)](x1-x0)t∥x1-x0∥22.
To determine x2, the matrix J(x1) is replaced by A1 as follows:
(10)x2=x1-A1-1F(x1).
Once the xi is determined, then the new approximation xi+1 is obtained by executing the following
(11)Ai=Ai-1+yi-Ai-1si∥si∥22sit,xi+1=xi-Ai-1F(xi),
where  yi=F(xi)-F(xi-1) and si=xi-xi-1. Hence, the number of scalar functional evaluations is reduced from n2+n to n (those required for evaluating F(xi), but O(n3) calculations are still required to solve the associated n×n linear system:
(12)Aisi+1=-F(xi).
The reduction form the quadratic convergence of Newton’s method to superlinearly convergence can be improved by employing a matrix inversion formula of Sherman and Morrison [1].Theorem 1 (see [1]. Sherman-Morrison).
LetA be a nonsingular matrix and let  x and y be vectors, then A+xyt is nonsingular, provided that ytA-1x≠-1, and
(13)(A+xyt)-1=A-1-A-1xytA-11+ytA-1x.
In order to eliminate the computation matrix inversion with each iteration, the Sherman-Morrison states that A-1 can be computed directly from Ai-1-1 by using this formula
(14)Ai-1=Ai-1-1+(si-Ai-1-1yi)sitAi-1-1sitAi-1-1yi,
where si=xi-xi-1 and yi=F(xi)-F(xi-1).The following theorem defines that the Broyden’ method make the smallest possible changes in updating the Jacobian.Theorem 2 (see [11]).
Among all matricesA satisfying yi=Ai+1si, the matrix An+1 minimizes the difference ∥An+1-An∥.Proof.
By properties of the Euclidean norm and∥sst/sts∥=1 for any vectors s, we have
(15)∥An+1-An∥=∥(yn-Ansn)sntsts∥≤∥A-An∥∥snsntsntsn∥=∥A-An∥.
Therefore,
(16)An+1∈argmin∥A-An∥, whereA:yk=Ask.Theorem 3 (see [12]).
Suppose that the assumptions of Kantorovich’s Theorem hold. Then there exist positive constantsε and γ s.t. if the starting point  x0 and the starting approximate Jacobian A0 satisfy
(17)∥x0-x*∥≤γ,∥A0-J(x*)∥≤ε,
then the sequence generated by Broyden’s method {xn} will converge superlinearly to x*.As stated previously, Broyden’s method is a method for solving nonlinear equations. Next, tested Broyden’s method is tested on solving fuzzy nonlinear equations.


## 4. Broyden’s Method for Solving Fuzzy Nonlinear Equations

Now the objective is to obtain a solution for fuzzy nonlinear equationsF(x)=c. The parametric form is given as follows.
(18)F̲(x̲,x¯;α)=c̲(α),F¯(x̲,x¯;α)=c¯(α).∀r∈[0,1]
To solve the nonlinear system   F(x̲,x¯;α)=0, one initial approximation x0 is given, and then generate a sequence  {xn}  which converges to the solution x,  that is, F(x̲,x¯;α)=0. The method of Broyden’s Newton can be described as follows:Step 1.
Transform the fuzzy nonlinear equations into parametric form.Step 2.
Solve the above system forα=0 and α=1 in order to obtain the initial value, x0.Step 3.
Substitutex0 into parametric formStep 4.
Compute the initial Jacobian matrix(19)A0(α)=J(x̲0,x̅0;α).
Use it to compute the first approximation using Newton's method. Let xk(α)=(x̲k,x¯k;α), then
(20)x1(α)=x0(α)-A0(α)-1F(x0(α)).
For k≥1, suppose that  x1(α) has been obtained, then use the following steps to obtain  x2(α).Step 5.
Evaluate the function(21)F(x̲1,x¯1;α)=[F̲(x̲1,x¯1;α)F¯(x̲1,x¯1;α)].Step 6.
Update the approximate Jacobian usingsk(α)=xk(α)-xk-1(α)  and   yk(α)=F(xk(α))-F(xk-1(α)), for k=1,2,…,n.Step 7.
Use Sherman-Morrison formula to computeA1(α)-1 as follows:
(22)A1(α)-1=A0(α)-1+[s1(α)-A0(α)-1y1(α)]s1(α)tA0(α)-1s1(α)tA0(α)-1y1(α).Step 8.
Solve the linear systemA1(α)x2(α)=x1(α)-F(x1(α)) for x2(α).Step 9.
Repeat Steps from4 to 8 and continue with the next k until tolerance criteria ε≤10-5 are satisfied.


## 5. Numerical Application

Two examples are proposed to illustrate the Broyden’s method for solving fuzzy nonlinear equations.Consider the example from [4, 6].Example 1.
consider(23)(3,4,5)x2+(1,2,3)x=(1,2,3).
Assume that x is positive, without any loss of generality, then the parametric form of this equation is as follows [4, 6]:
(24)(3+α)x̲2(α)+(1+α)x̲(α)=(1+α),(5-α)x¯2(α)+(3-α)x¯(α)=(3-α)
or equality
(25)(3+α)x̲2(α)+(1+α)x̲(α)-(1+α)=0,(5-α)x¯2(α)+(3-α)x¯(α)-(3-α)=0.
The above system needs initial values as follows.For     α=0.(26)3x̲2(0)+x̲(0)=1,5x¯2(0)+3x¯(0)=3.
For    α=1:
(27)4x̲2(1)+2x̲(1)=2,4x¯2(1)+2x¯(1)=2.
Hence, x̲(0)=0.4343,x¯(0)=0.5307, and   x̲(1)=x¯(1)=0.5. Suppose that x is negative, where x̲(0)=-0.7676,x¯(0)=-1.1307, and x̲(1)=x¯(1)=-1.  For x̲(0)>x̅(0),  therefore, negative root does not exist.
For initial value, one can use the fuzzy number(28)x0=(x̲(0),x̲(1),x¯(0))=(0.4343,0.5,0.5307).
As can be observed, the above initial value is too close to the true solution. So this value can be taken as an actual solution. Therefore in this paper, another initial value is proposed in order to show the efficiency of the proposed method. Hence, the initial value is x0=(0.4,0.5,0.6). However, other initial values also can be used, but the suggested value is more reasonable to be used because Broyden’s method needs a good initial value near to the exact solution that will lead to the true solution. Initially, parametric form can be written as follows:
(29)(3+α)x̲2(α)+(1+α)x̲(α)-(1+α)=0,(5-α)x¯2(α)+(3-α)x¯(α)-(3-α)=0.
Then substitute x0 into parametric form. First iteration for Broyden’s method is similar to the iteration for Newton’s method. The Jacobian matrix for this fuzzy equation is
(30)J(x̲0,x̅0;α)=[2(3+α)x̲(α)+(1+α)002(5-α)x̅(α)+(3-α)].
Let x0=(0.4,0.5,0.6) and
(31)F(x̲0,x̅0;α)={F̲(x̲0,x̅0;α),F̅(x̲0,x̅0;α)={(3+α)x̲02(α)+(1+α)x̲0(α)-(1+α)=0,(5-α)x¯02(α)+(3-α)x̅0(α)-(3-α)=0.
Since A0(α)=J(x̲0,x̅0;α)(32)A0(α)-1=J(x̲0,x̅0;α)-1.
Let xi(α)=(x̲i,x̅i;α), then
(33)x1(α)=x0(α)-A0(α)-1F0(α).
In the next step, x1(α) is used to compute x2(α). In Broyden’s method, the Jacobian matrix is denoted by matrix Ai-1, and it can be computed directly from Ai-1-1 by using this formula
(34)A1(α)-1=A0(α)-1+[s1(α)-A0(α)-1y1(α)]s1(α)tA0(α)-1s1(α)tA0(α)-1y1(α),
where s1(α)=x1(α)-x0(α) and y1(α)=F(x0(α))-F(x0(α)) for  i=1,2,…,n. Repeat Steps from 4 to 8 until it satisfies the tolerance ε≤10-5. After three iterations, the solution was obtained with maximum error 10-5. Details of the solution from 0≤α≤1are given in Figure 1.
Figure1 shows that Broyden’s method can converge very rapidly to a solution once initial value is obtained which is sufficiently close to true solution. The solution is obtained after two iterations with the maximum error less than 10-5.
Now the second example is proposed.Figure 1
Solution of Broyden’s Method for Example1.Example 2.
consider(35)(4,6,8)x2+(2,3,4)x-(8,12,16)=(5,6,7).
Assume that x is positive, without any loss of generality, then the parametric form of this equation is as follows [4, 6]:
(36)(4+2α)x̲2(α)+(2+α)x̲(α)-(8+4α)=(5+α),(8-2α)x̅2(α)+(4-α)x̅(α)-(16-4α)=(7-α),
or equality
(37)(4+2α)x̲2(α)+(2+α)x̲(α)-(3+3α)=0,(8-2α)x¯2(α)+(4-α)x¯(α)-(9-3α)=0.
In order to obtain initial guess, we use above system.  For     α=0,
(38)4x̲2(0)+2x̲(0)-3=0,8x¯2(0)+4x¯(0)-9=0.
For    α=1:
(39)6x̲2(1)+3x̲(1)-6=0,6x¯2(1)+3x¯(1)-6=0.
Hence, x̲(0)=0.65139,x¯(0)=0.83972, and   x̲(1)=x¯(1)=0.78078. For initial guess, one can use the fuzzy number:
(40)x0=(x̲(0),x̲(1),x¯(0))=(0.65139,0.78078,0.83972).
Consequently, the initial guess is x0=(0.65139,0.78078,0.83972).
Similar to the arguments in Example1, the initial value above is too near to the true solution. Hence, other initial value is proposed as x0=(0.6,0.8,0.9), but other initial values may also be able to be tested as follows:
(41)(4+2α)x̲2(α)+(2+α)x̲(α)-(3+3α)=0,(8-2α)x¯2(α)+(4-α)x¯(α)-(9-3α)=0.
Then the above equations are solved by using Steps from 3 to 8 until the solution is obtained within the maximum error ε≤10-5. Details of the solution for 0≤r≤1are shown in Figure 2.
This figure illustrates how Broyden’s method converges very rapidly to a solution, once initial value is obtained which is sufficiently close to true solution. However, it is not easy to determine initial values that will lead to a solution. Poor initial values may not lead to the actual solution. The solution using Broyden’s method is obtained after three iterations with the maximum error less than10-5.Figure 2
Solution of Broyden’s Method for Example2.


## 6. Conclusion

In this paper, Broyden’s method has been applied for solving fuzzy nonlinear equations. Firstly, fuzzy nonlinear equations are written in parametric form and then are solved using Broyden’s method. The proposed eight steps algorithm yields the solution with maximum error less than10-5. Two numerical examples have proven the feasibility of Broyden’s method in solving fuzzy nonlinear equations.



---

*Source: 763270-2010-08-31.xml*