Uzawa Algorithms for Fully Fuzzy Linear Systems

H. Zareamoghaddam; A.T. Chronopoulos; M. Nouri Kadijani; Z. Zareamoghaddam

doi:10.1080/18756891.2016.1237194

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Volume 9, Issue 5, September 2016, Pages 971 - 983

Uzawa Algorithms for Fully Fuzzy Linear Systems

Authors

H. Zareamoghaddam¹^,, A.T. Chronopoulos², M. Nouri Kadijani¹, Z. Zareamoghaddam¹

¹Department of Mathematics, Kashmar Branch, Islamic Azad University, Kashmar, Iran.

²Department of Computer Science, University of Texas at San Antonio, 1 UTSA Circle, San Antonio, TX 78249, USA.

Corresponding author’s (H. Zareamoghaddam’s) E-mail: zareamoghaddam@yahoo.com

Corresponding Author

H. Zareamoghaddam

Received 2 January 2015, Accepted 1 March 2016, Available Online 1 September 2016.

DOI: 10.1080/18756891.2016.1237194 How to use a DOI?
Keywords: FFLS; Uzawa; iterative methods; trapezoidal fuzzy numbers; fuzzy systems
Abstract: Recently, there have been many studies on solving different kinds of fuzzy equations. In this paper, the solution of a trapezoidal fully fuzzy linear system (FFLS) is studied. Uzawa approach, which is a popular iterative technique for saddle point problems, is considered for solving such FFLSs. In our Uzawa approach, it is possible to compute the solution of a fuzzy system using various relaxation iterative methods such as Richardson, Jacobi, Gauss-Seidel, SOR, SSOR as well as Krylov subspace methods such as GMRES, QMR and BiCGSTAB. Krylov subspace iterative methods are known to converge for a larger class of matrices than relaxation iterative methods and they exhibit higher convergence rates. Thus, they are more widely used in practical problems. Numerical experiments are to illustrate the performance of our suggested methods.
Copyright: © 2016. the authors. Co-published by Atlantis Press and Taylor & Francis
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

1. Introduction

Linear system of equations Ax = b, where A and b are respectively a crisp (i.e. exact) square matrix and vector, mostly comes from the discretization of some practical partial differential equations. The solution of linear systems is required in various areas such as Physics, Statistics, Engineering and Social Science. Then, several researchers have focused on solving such systems by numerous developed iterative methods over the years. In the past, researchers in numerical computing have developed relaxation iterative methods such as Richardson, Jacobi, Gauss-Seidel, SOR, SSOR. Some of these methods are applicable to only to diagonally dominant and others for symmetric positive definite matrices. They are proved to converge in infinite number of iterations (steps) and their convergence rate is rather slow for practical problems. Thus more attractive iterative methods are the iterative method based on conjugate gradient (CG). CG is applicable for symmetric positive definite matrices and it is proven to converge in a finite number of steps and in general at higher convergence rates than the relaxation iterative methods. Various extensions of CG that apply to non symmetric and non definite matrices exist and are widely known as Krylov subspace (iterative) methods. Well known Krylov subspace methods are GMRES, Orthodir, (s-step) Orthomin (which are extensions of conjugate gradient method) and QMR, CGS, BiCGSTAB (which are extensions of biconjugate gradient and biorthogonal Lanczos methods). These methods and the theory for their convergence is covered in Refs. 1–9 and references therein.

One difficulty for numerous linear systems is that, in many practical problems, some parameters of such systems may be vague or imprecise. Because of the importance of these systems, fuzzy mathematics is considered for computing the solution of linear system of equations with vague parameters. Many authors have studied different kinds of fuzzy linear systems and have extended several solver methods for the solutions of these problems because of the large amount of applications of such systems in various areas.

Friedman et al. Ref. 10 studied a general form of fuzzy linear system of equations (FLSE) with a crisp coefficient matrix and an arbitrary right hand side fuzzy vector. They used an embedding approach to replace a n×n FLSE by a 2n×2n crisp linear system and the solution of FLSE was extracted from the solution of the new parametric system. Many authors have had different investigations on the solution of such fuzzy problems such as the extended methods based on Friedman et al.’s approach, as well as several novel methods. To know more about these methods refer to Refs. 11–16 and references therein.

Furthermore, there is a secondary kind of fuzzy linear systems of the form

(1)A˜x˜=b˜,

where the components of both the coefficient matrix Ã, i.e. ã_i,j, 1 ⩽ i, j ⩽ n, and right hand side vector b˜, i.e. b˜i, 1 ≤ i ≤ n, are fuzzy numbers, which this system is usually called as fully fuzzy linear system (FFLS). FFLSs have been studied by several authors over the last years. Dehghan et al. focused their studies on FFLSs with LR fuzzy numbers and they proposed some iterative methods in Refs. 17–18 for FFLSs with LR fuzzy numbers. Vroman et al. in Ref. 19 suggested a new approach to compute the solution of FFLSs by Cramer’s rule and Allahviranloo et al. in Refs. 20–22 developed different approaches for the solution of these systems.

In this paper, we propose practical implementations, which solve the solution of a trapezoidal FFLSs based on Uzawa approach. At first, Uzawa algorithm was considered as a simple implementation which needs minimal memory requirement for solving linear saddle point system

(2)(ABTB−C)(xy)=(fg),

where A ∈ R^n×n was a symmetric and positive definite matrix, C ∈ R^m×m was a symmetric positive semi-definite, B ∈ R^m×n had full rank, x , f ∈ R_n and y , g ∈ R^m. Later on, many investigations, such as the works in Refs. 23–26, have developed different Uzawa approaches for solving different kinds of linear or nonlinear saddle point problems because this sort of problem frequently arises from the discretization of Stokes equations and elasticity problems or from the linearization of Navier-Stokes equations. Generally, the implementation of Uzawa algorithm is as follows.

Suppose (x₀; y₀) is an initial guess for the exact pair solution (x; y) of (2). Uzawa algorithms mainly construct a sequence of approximations x_k and y_k for x and y based on the following instruction:

For k = 0 until convergence do

1.
Solve linear system Ax_k+1 = f−B^T y_k,
2.
y_k+1 = y_k +τ (g−Bx_k −Cy_k).

End

Algorithm 1:

General Uzawa implementation

In this algorithm, the extrapolation scalar τ is a real number which is named as Uzawa parameter.

This papers aim is to compute the solution of a trapezoidal FFLS by the above Uzawa instruction based on several different appropriate iterative methods. The rest of this paper is organized as follows. In Section 2, some basic definitions and remarks on fuzzy numbers and FFLSs are reviewed. Uzawa algorithm is discussed more in Section 3. Next, some iterative methods for computing the solution of FFLSs based on Uzawa algorithm are proposed in Section 3. Our proposed algorithms are illustrated by solving some numerical examples in Sections 4 and 5.

2. Preliminaries

In this section, some basic definitions and notes on fuzzy numbers and FFLSs are reviewed Refs. 11, 12, 14, 17, 18 and 20.

Definition 1:

A fuzzy number is a fuzzy set ũ : R → [0, 1] which satisfies

1.
ũ is upper semi continuous,
2.
ũ = 0 outside some interval [c, d],
3.
There are real numbers a, b: c ⩽ a ⩽ b ⩽ d so that
1. (a)
  ũ(x) is a monotonic increasing function on [c, a].
2. (b)
  ũ(x) is a monotonic decreasing function on [b, d].
3. (c)
  ũ(x) = 1, a ⩽ x ⩽ b.

For simplicity the above fuzzy number ũ, which is called trapezoidal fuzzy number, is represented by ũ = (a, b, α, β) where 0 ⩽ α = a−c and 0 ⩽ β = d −b. The set of all such fuzzy numbers is denoted by E.

Definition 2:

The parametric form of an arbitrary fuzzy number ũ is also represented by an ordered pair of functions (u(r), ū (r)), 0 ⩽ r ⩽1, see Ref. 27, that satisfies :

1.
u is a bounded monotonically increasing left continuous function.
2.
ū is a bounded monotonically decreasing left continuous function.
3.
u(r) ⩽ ū (r), 0 ⩽ r ⩽ 1.

A crisp number c is simply represented by u(r) = ū(r) = c, 0 ⩽ r ⩽ 1.

Definition 3:

The membership function of trapezoidal fuzzy number ũ = (a, b, α, β) is

(3)u˜(x)={x−a+αα,a−α≤x≤a,1,a≤x≤b,b+β−xβ,b≤x≤b+β,0,otherwise.

and its parametric form is

(4)u_(r)=αr+a−α and u¯(r)=b+β−βr.

Furthermore, if a = b, then ũ = (a, α, β) is called a triangular fuzzy number.

Remark:

For an arbitrary trapezoidal fuzzy number ũ = (a, b, α, β), 0 ⩽ ũ if 0 ⩽ a − α.

Definition 4:

For two arbitrary fuzzy numbers ũ = (m, n, α, β) and ṽ = (p, q, γ, λ) (or in parametric form ũ(r) = (u(r), ū(r)) and v˜=(v_(r),v¯(r))) and a crisp number c, the following algebraic operations are defined

1.
ũ+ ṽ = (m+ p, n+q, α +γ, β +λ),
2.
−ũ = (−n, −m, β, α),
3.
ũ− ṽ = (m−q, n− p, α +λ, β + γ)
4.
The multiplication of two trapezoidal fuzzy numbers are defined by
u˜⊗v˜=(min{mp,nq},max{mp,nq},|mγ|+|pα|,|nλ|+|qβ|)
where |x| means the absolute value of x.
5.

cu˜={(cm,cn,cα,cβ),c≥0,(cm,cn,−cβ,−cα),c<0.

In parametric form, we have

i.
u˜(r)±v˜(r)=(u_(r)±v_(r),u¯(r)±v¯(r)),
ii.

cu˜={(cu_(r),cu¯(r),c≥0(cu¯(r),cu_(r)),c<0,
iii.

u˜⊗v˜=(uv_(r),u,v¯(r)) , where uv_(r)=min{u_(r)v_(r),u_(r)v¯(r),u¯(r)v_(r),u_(r)v¯(r)} and uv¯(r)=max{u_(r)v_(r),u_(r)v¯(r),u¯(r)v_(r),u_(r)v¯(r)}
iv.
ũ = ṽ iff u (r) = v (r), u¯(r)=v¯(r), 0 ⩽ r ⩽ 1.

Definition 5:

The matrix Ã = (ã_i,j) is called a fuzzy matrix, if each element of Ã be a fuzzy number. Similarly, a fuzzy vector is defined.

We can represent the trapezoidal fuzzy matrix Ã = (ã_i,j), i.e ã_i,j = (a_i,j, b_i,j, α_i,j, β_i,j); 1 ⩽ i, j ⩽ n, by Ã = (A, B, M, N) where A = (a_i,j), B = (b_i,j), M = (α_i,j) and N = (β_i,j).

Definition 6:

The following linear system of equations

(5)a˜1,1⊗x˜1+⋯+a˜1,n⊗x˜n=b˜1,a˜2,1⊗x˜1+⋯+a˜2,n⊗x˜n=b˜2,⋮a˜n,1⊗x˜1+⋯+a˜n,n⊗x˜n=b˜n.

where Ã = (ã_i,j) is a n×n fuzzy matrix and b˜i∈E, (1 ⩽ i ⩽ n) is called a fully fuzzy linear system. The system of equations (5) in matrix form is A˜⊗x˜=b˜ with the fuzzy vectors x˜=(x˜1,x˜2,…,x˜n)T∈En and b˜=(b˜1,b˜2,…,b˜n)T∈En.

In this paper, we look for the possible solution of a fully fuzzy linear system of equations A˜⊗x˜=b˜ where Ã = (A, B, M, N) and b˜=(b,g,h,k). So, we have

(6)A˜⊗x˜=b˜ ⇒(A,B,M,N)⊗(x,y,w,z)=(b,g,h,k)

From multiplication of two fuzzy numbers (following definition 4), the equation (6) is divided into the following four separate crisp linear systems of equations,

(7)Ax=b,

(8)By=g,

(9)Aw+Mx=h,

(10)Bz+Ny=k.

Let the crisp matrices A and Bare nonsingular, the generalized inverse techniques might be useful for some singular matrices, then

(11)x=A−1b,w=A−1(h−Mx)y=B−1g,z=B−1(k−Ny).

3. Uzawa algorithm

One of the simple and efficient algorithms for computing the solution of crisp saddle point problem (2) is the Uzawa implementation (algorithm 1) which finds some approximations x_k and y_k(k > 0) for the following system of equations

(12)Ax+BTy=f,

(13)Bx+Cy=g,

computed by the following iterative relations

(14)Axk+1=f−BTyk,

(15)yk+1=yk+τ(g−Bxk−Cyk).

where τ is a positive descent parameter.

Based on equation (14), the approximation x_k+1 (k ⩾ 0) is determined by solving linear system of equations with different right column f−B^T y_k for any iteration by some suitable methods. Next, y_k+1 (k ⩾ 0) is computed from equation (15) by an appropriate amount of τ. This scalar has directly a significant effect on the convergence speed of Uzawa algorithm because the algorithm may converge slowly or perhaps may not converge for inappropriate values of τ.

Let us assume that A is a nonsingular matrix. By applying block Gaussian elimination to (2) Ref. 24, the following equation is obtained

(16)(ABT0BA−1BT+C)(xy)=(fBA−1f−g)

From (16) it is easily concluded that the unknown vector x can be removed from the second block equation and y may be computed by solving the linear system

(17)(BA−1BT+C)y=BA−1f−g,

instead of computing y from (15). By applying Uzawa approach on this equation, the approximation y_k(k > 0) can be obtained from

(18)yk+1=yk+τ(BA−1f−g−(BA−1BT+C)yk),

which is a Richardson iterative method for the solution of (17).

Theorem 1.

Let suppose that G = I − τ(BA⁻¹B^T + C). The relation (18) is converges for any arbitrary vector y₀, if the spectral radius of G is less than unity, i.e. ρ (G) < 1.

Proof.

Let y is the exact solution of (17), then we have

(19)y=y+τ((BA−1f−g)−(BA−1BT+C)y).

Suppose y_k is the approximate solution of (18) for 0 ⩽ k. Subtracting (19) from (18) yields

(20)yk+1−yk=G(yk−y)=⋯=Gk+1(y0−y),

From ρ (G) < 1, it is quickly concluded that G^k+1 → 0. Then y_k+1 →y for any y₀.

Theorem 2.

Suppose λ_m and λ_M are the smallest and largest eigenvalues of BA⁻¹B^T +C, respectively. Then the spectral radius of G is ρ (G) = max{|1−τλ_m|, |1− τλ_M|}. For the proof refer to Ref. 1.

The spectral radius of matrix G, which is very important for convergence of (18), is named as ”convergence factor”. The following theorem gives us some more practical information about Uzawa algorithm and optimum Uzawa parameter.

Theorem 3.

(Ref. 23) Let us suppose that G = I −τ(BA⁻¹B^T +C) and (x;y) is the block solution of (2) and also (x_k ;y_k) are the approximations of (x;y) computed by the Uzawa algorithm, then the following results are obtained

i.
The sequences x − x_k and y − y_k satisfy
((x−xk)TA(x−xk))1/2≤λM‖y−yk‖ ,‖y−yk‖≤ρ(G)‖x−xk‖.
ii.
For τ<2λM, the Uzawa algorithm is convergent and
ρ(G)=max{|1−τλm|,|1−τλM|}.
iii.
For τ=2λM, the convergence factor (spectral reduce) is
ρ(G)=1−λmλM.
iv.
The optimal parameter is τopt=2λm+λM and the corresponding convergence factor is
ρopt(G)=λM−λmλM+λm.

The Uzawa algorithm needs some practical iterative method, which works by repeatedly improving an approximate solution until it is accurate enough.

4. Uzawa Iterative methods for FFLSs

Now, the trapezoidal FFLS A˜⊗x˜=b˜ is considered to be solved by the Uzawa approach based on some popular iterative methods like Richardson, Jacobi, Gauss-Seidel, SOR, SSOR, USSOR, as well as iterative methods of Krylov subspace type such as conjugate gradient for symmetric crisp linear systems and its variants for nonsymmetric crisp system of equations and several other popular iterative methods like GMRES Ref. 1. In past, Wang and Wu in Ref. 28 used Uzawa-SOR for solving fuzzy linear system of equations. Here, we proposed several Uzawa approaches for solving fully fuzzy linear system of equations.

As it has been discussed in section 2, the FFLS (1) is divided into four separate crisp systems of equations (7) to (10). Using the Uzawa algorithm, the crisp linear systems (7) and (9) are solved together and similarly the equations (8) and (10) are considered as a separate crisp problem. In a better statement, this FFLS is replaced by the following two problems

Pr1:Ax=band Aw+Mx=h.Pr2:By=g and Bz+Ny=k.

Suppose x₀ and w₀ are initial values for the solutions x and w of Pr 1 and y₀ and z₀ are the initial Guesses for Pr 2. The Uzawa algorithm for the solution of FFLS (1) is as follows:

For k = 0 until convergence do

1.
Compute x_k+1 from Ax_k+1 = b,
2.
Compute w_k+1 by

w_k+1 = w_k +τ (h−Aw_k −Mx_k),
3.
Compute y_k+1 from By_k+1 = g,
4.
Compute z_k+1 by

z_k+1 = z_k +τ′ (k−Bz_k −N y_k).

End

Algorithm 2:

Uzawa algorithm for FFLSs

For the better convergence speed, some appropriate parameters τ and τ′ have to be considered for algorithm 2. In section 3, we have discussed the convergence factor and optimum parameter of Uzawa algorithm. So, if A, B are symmetric positive definite matrices, it is concluded that

(21)τopt=2λm+λM and τopt'=2λm'+λM'

and steps 2 and 4 of algorithm 2 are convergent to the exact solutions w and z for any initial vectors w₀ and z₀, where λ_m and λ_M are respectively the smallest and the largest eigenvalues of A and λ′_m and λ′_M are similarly the smallest and the largest eigenvalues of B.

The following are some of the possible iterative methods for the solution of such FFLSs.

4.1. Uzawa-Richardson (UR) method

The structure of this iterative algorithm is as follows. At first, the Richardson iterative method needs to compute the solutions of two crisp linear systems (7) and (8), separately. From these primary linear systems we have

(22)x=(I−ηA)x+ηb,

(23)y=(I−η′B)y+η′g,

where η and η′ are the scalars which called as the extrapolation Richardson parameters.

Using the preceding equations and steps 2 and 4 of algorithm 2, sequentially, the approximate solution of a FFLS is computed. Then the algorithm of UR for the acceleration scalars η, η′, τ and τ′ is as follows.

For k = 0 until convergence do

1.
x_k+1 = (I−ηA) x_k +ηb,
2.
w_k+1 = w_k +τ (h−Aw_k −Mx_k),
3.
y_k+1 = (I−η′B) y_k +η′g,
4.
z_k+1 = z_k +τ′ (k−Bz_k −Ny_k).

End

Algorithm 3:

UR algorithm for FFLSs

If the square matrices A and B are symmetric and positive definite, the optimal extrapolation parameters η and η′ are

(24)ηopt=2λm+λM and ηopt'=2λm'+λM',

and the corresponding spectral radiuses are respectively as

(25)ρ(I−ηoptA)=λM−λmλM+λmandρ(I−η′optB)=λM'−λm'λM'+λm',

To apply some iterative methods like Jacobi, Gauss-Seidel (GS), SOR, SSOR, etc, the following decompositions for the coefficient matrices of A, B are needed

(26)A=D+L+U

(27)B=D′+L′+U′,

in which D and D′ are the diagonals of A, B, L and L′ are the strict lower parts and U and U′ are the strict upper sections of A and B, respectively.

4.2. Uzawa-Gauss-Seidel (UGS) method

Gauss-Seidel algorithm uses the decompositions (26) and (27) to transform the linear equations (7) and (8) into iterative methods of the forms

(28)xk+1=Hxk+f,

(29)yk+1=H′yk+f′.

To achieve this, Gauss-Seidel computes the components of approximations x_k+1 and y_k+1 by the following iterations

xk+1(i)=1ai,i(bi−∑j=1i−1ai,jxk+1(j)−∑j=i+1nai,jxk(j)),yk+1(i)=1bi,i(gi−∑j=1i−1bi,jyk+1(j)−∑j=i+1nbi,jyk(j)),i=1,…,n,

where A = (a_i,j), B = (b_i,j), b = (b_i) and g = (g_i), or in matrix form by

(30)xk+1=−(D+L)−1Uxk+(D+L)−1b,

(31)yk+1=−(D′+L′)−1U′yk+(D′+L′)−1g

Proposition 1:

These two last iterative relations are convergent for any arbitrary initial vectors if the spectral radius of (D+L)⁻¹U and (D′+L′)⁻¹U′ are less than unity (theorem 1).

Now, the UGS algorithm is similar to algorithm 3 except for the steps 1 and 3 in which UGS instead computes the approximate solutions x_k+1 and y_k+1 by (30) and (31).

4.3. Uzawa–SOR (USOR) method

SOR is an iterative algorithm which is a modified version of Gauss-Seidel. SOR is derived from Gauss-Seidel method by applying an extrapolation parameter ω, which named as ”convergence rate”, to accelerate the convergence speed of algorithm as much as possible. In USOR, we also have to replace the equations (7) and (8) by two iterative methods of the forms (28) and (29).

Due to the SOR condition, the components of x_k+1 and y_k+1 are computed from the following iterations

xk+1(i)=ωai,i(bi−∑j=1i−1ai,jxk+1(j)−∑j=i+1nai,jxk(j))+(1−ω)xk(j),yk+1(i)=ω′bi,i(gi−∑j=1i−1bi,jyk+1(j)−∑j=i+1nbi,jyk(j))+(1−ω′)yk(j)i=1,…,n,

where ω and ω′ are the convergence rates. In matrix form, we have

(32)xk+1=(D+ωL)−1((1−ω)D−ωU)xk+ω(D+ωL)−1b,

(33)yk+1=(D′+ω′L′)−1((1−ω′)D′−ω′U′)yk+ω′(D′+ω′L′)−1g.

Proposition 2:

The iterative formulas (32) and (33) are convergent for arbitrary initial vectors x₀ and y₀, if ρ (H) < 1 and ρ (H′) < 1, where H =(D + ωL)⁻¹ ((1 − ω)D − ωU) and H′ = (D′ + ω′L′)⁻¹ ((1 − ω′)D′ − ω′U′) (the proof follows from theorem 1).

Therefore, USOR algorithm differs from UR only in the style of computing the solutions of crisp linear systems (7) and (8). USOR computes these solutions by the above iterative formulas (32) and (33). There are some more similar implementations for Uzawa algorithm based on other iterative methods such as Jacobi, SSOR (Symmetric Successive Over Relaxation), USSOR (UnSymmetric successive Over Relaxation), etc (see Refs. 1–3), which may yield similar or better performances. For Uzawa-Jacobi algorithm, x_k+1 and y_k+1 are computed by

(34)xk+1=−D−1(L+U)xk+D−1b,

(35)yk+1=−D′−1(L′+U′)yk+D′−1g.

SSOR and USSOR are two modified versions of SOR algorithm which have no advantage over SOR as iterative methods except they are mainly more practical used in preconditionings for Krylov subspace iterative methods. If these two methods want to be considered for solving FFLSs by Uzawa approach, their instructions are as follows. For Uzawa-SSOR and Uzawa-USSOR, if A = Q−P and B = Q′ − P′ the iterative solutions are obtained from

(36)xk+1=Q−1Pxk+Q−1b,

(37)yk+1=Q′−1Pyk+Q′−1g,

where in Uzawa-SSOR

(38)Q=1ω(2−ω)(D+ωL)D−1(D+ωU)and

(39)Q′=1ω′(2−ω′)(D′+ω′L′)D′−1(D′+ω′U′)

while in Uzawa-USSOR

(40)Q=1ω1+ω2−ω1ω2(D+ω1L)D−1(D+ω2U),

and

(41)Q′=1ω′1+ω′2−ω′1ω′2(D′+ω′1L′)D′−1×(D′+ω′2U′).

In all these cases, the equations (7) and (8) are replaced by equations of the forms (28) and (29). Next, w_k+1 and z_k+1 of the two rest equations (9) and (10) are computed by algorithm 2.

The discussed above iterative methods, which are older algorithms, are named stationary iterative methods with simpler theory and implementations. Nonstationary methods (e.g. Krylov) are more recently developed methods, with harder analysis and implementations, can be highly more effective for crisp linear systems. The following is a discussion about Uzawa algorithm based on some nonstationary iterative methods for solving trapezoidal FFLSs.

4.4. Uzawa algorithms for large sparse FFLSs

Previous iterative methods are more suitable for FFLSs with small matrix dimensions because the convergence speed of these methods is usually slow and they may converge to the solution after too many iterations or may not even converge. Furthermore, the required arithmetic computations of those methods will increase dramatically by raising the dimension of the original problems. As a remedy, a class of popular iterative methods which is called ”Krylov subspace methods” is considered because many Krylov subspace approaches are popular for dealing with large sparse crisp linear system of equations. Among these methods, there are some techniques only for solving symmetric linear systems such as Conjugate Gradient (CG), MINRES, etc. as well as several popular iterative algorithms such as FOM, GMRES and several variants of CG algorithms like BiCG, CGS, QMR, BiCGSTAB and many unmentioned algorithms for the solution of unsymmetric linear system of equations (see Refs. 1–3). CG, which generates orthogonal residual sequences, is an effective method for a linear system of equations with symmetric positive definite coefficient matrix such that this method storages a limited number of vectors. BiCG generates two CG-like sequences of vectors simultaneously, one for original linear system with coefficient matrix A and one for an alternative system with coefficient matrix A^s . QMR is an updated version of BiCG which mostly avoid the possible breakdown that can occur in BiCG. BiCGSTAB is a variant of BiCG which uses different updates for A^T-sequences. BiCGSTAB has a smoother convergence than BiCG. GMRES is an effective method that requires heavy storage requirement. To avoid this drawback, restarted versions of GMRES are considered for crisp linear systems. Generally, most of the practical iterative methods are based on a projection process. For example, FOM and GMRES depend on an orthogonal projection while BiCG variants are based on biorthogonalization techniques.

Generally, each iterative algorithm has some advantages and disadvantages. It is normally difficult to find an iterative method which could quickly solve all kinds of crisp linear systems with low memory requirement, especially if the linear systems are illposed or singular. Numerous iterative techniques have been developed by several authors, for the solution of such problems, over the years. Also, many researchers have investigated the existing methods to improve their convergence speed. Readers whom are interested in knowing more about these iterative techniques for crisp linear systems are referred to Refs. 1 and 4.

Now, for solving large sparse FFLSs by Uzawa approach similar to the previous discussed methods, at first, two extracted crisp linear equations (7) and (8) have to be solved by a Krylov method. Next, the two reminded iterative solutions w_k+1 and z_k+1 are computed by the above mentioned Uzawa approaches of Algorithm 2.

Generally, many iterative methods have been developed and it is impossible to discuss about them all in this section. However, our Uzawa algorithm is flexible to employ any effective iterative method for solving two required crisp linear system of equations.

5. Numerical Experiments

The following numerical experiments are for readers to gain a better understanding of the algorithms discussed in previous section.

Example 1:

The following 3×3 FFLS

(42)A˜⊗ x˜=b˜

is considered to be solved by some discussed Uzawa based algorithms where the system of equations is as follows.

{(4.5,5,1,1)x˜1+(0.5,1,0.5,0.5)x˜2+(1,3,1,0.5)x˜3=(14,33,11.75,22.5),(1,1,0.5,1)x˜1+(5,8,2,3)x˜2+(2,4,1,0.5)x˜3=(28,67,25.5,49.5),(2,3,2,2)x˜1+(3,4,1,1.5)x˜2+(6,8,3,3)x˜3=(34,65,33,62.5).

From (6), it is quickly concluded that

A=(4.50.51152236), B=(513184348)M=(10.510.521213), N=(10.50.5130.521.53)

and the right hand side vectors are

b=(142834), g=(336765),h=(11.7525.533), k=(22.549.562.5),

One important factor for convergence of Uzawa algorithms for FFLSs is the selection of appropriate Uzawa parameters. Here, we illustrate the effect of choosing different Uzawa parameters on the convergence of (42) by selecting two different set of such parameters for the algorithms of UR, UGS and USOR as follows. The initial Guess for the unknown parameters is x₀ = y₀ = w₀ = z₀ = (0, 0, 0)^T.

a)
At first, we select τ = 0.1 and τ′ = 0.1. After 15 iterations Uzawa-Richardson (UR) computed the following approximations where η = 0.1 and η′ = 0.1.
x15=(1.99683.99363.0083), y15=(2.98965.99454.0100),w15=(0.50142.00821.4904), z15=(0.52391.51613.4756)
and UR gave us the following results for η =0.2 and η′ = 0.1
x15=(2.01004.02003.0308), y15=(2.98965.99454.0100),w15=(0.49521.99171.4911), z15=(0.52391.51613.4756)
The numerical approximations of UGS for the above Uzawa parameters are
x15=(2.08334.16672.5417), y15=(3.00006.00004.0000),w15=(0.52691.92831.7025), z15=(0.50331.50173.4968)
The 15^th approximations of FFLS (42) computed by USOR algorithm with SOR parameters ω = 1.3 and ω′ = 0.3 were
x15=(2.08334.16672.5417), y15=(3.00006.00004.0000),w15=(0.52681.92821.7026), z15=(0.50491.50263.4953)
b)
The second set of Uzawa parameters for computing the solution of (42) is as τ = 0.2, τ′ = 0.01. To compare the effect of such parameters on convergence of discussed methods, previous Uzawa approaches are again considered for (42) where τ = 0.2, τ′ = 0.01. Similarly, the numerical results of such methods in 15^th iteration are written.

UR algorithm gave us the following approximations where η = 0.1 and η′ = 0.1
x15=(1.99683.99363.0083), y15=(2.98965.99454.0100),w15=(0.50622.01521.5134) , z15=(0.89221.69032.5118),
and for η = 0.2 and η′ = 0.1, UR approximations were
x15=(2.01004.02003.0308), y15=(2.98965.99454.0100),w15=(0.37631.75671.1220), z15=(0.89221.69032.5118).
UGS computes the following approximations
x15=(2.08334.16672.5417), y15=(3.00006.00004.0000),w15=(0.53271.94031.7117), z15=(0.86091.62112.5624).
The 15^th approximations of algorithm 2 computed by USOR with extrapolation parameters ω = 1.3 and ω′ = 1.3 were
x15=(2.08334.16672.5417), y15=(3.00006.00004.0000),w15=(0.53311.94111.7130), z15=(0.86171.61382.5603).
and for ω =1.3 and ω′ =0.3 the estimated solutions were
x15=(2.08334.16672.5417), y15=(3.04075.98923.9847),w15=(0.53311.94111.7130), z15=(0.85601.72892.5899).
It is easy to compare the approximated solutions of different Uzawa algorithms and to observe the effect of various required parameters with each other. The exact fuzzy solution of FFLS of example 1 is
x˜=(x˜1x˜2x˜3)=(x,y,w,z)=((2, 3, 0.5, 0.5)(4, 6, 2.0, 1.5)(3, 4, 1.5, 3.5))
The following example is a 6×6 FFLS to be solved by Krylov subspace methods.

Example 2:

Consider the problem A˜⊗x˜=b˜ where the trapezoidal fuzzy matrix Ã = (A, B, M, N) is as follows

A=(52132114.812312260.5132135211121100.5213136),B=(7224321.5533312310123.533412522132111323449)M=(210.50.10.211410.50.310.10.3210.50.10.50.21310.2110.10.14110.50.30.212),N=(2110.10.511410.20.20.50.20.3310.50.20.30.31310.30.510.20.14110.50.10.213)

and right hand side fuzzy vector is

b˜=((33, 69, 25, 44)(36.4, 61, 35.2, 46.5)(28, 72, 25.8, 48.6)(37, 120, 36.7, 64.7)(41.5, 85, 36, 62.1)(39, 97, 34.6, 61.8)).

This example is solved by the Uzawa algorithm based on some Krylov subspace methods. For all Uzawa algorithms the parameters τ = 0.02 and τ′ = 0.01 are considered and the initial vector for all vectors are zero vector of order 6(i.e. x₀ = y₀ = w₀ = z₀ = (0, …, 0)^T).

At first, restarted version of GMRES is considered for two crisp linear systems. In this example, GMRES(3) computed the unknown vectors x and y from the related crisp linear systems and the two rest crisp vectors are estimated by Uzawa approaches with the above parameters. The numerical results of this Uzawa algorithm after 6 iterations were

x6=(1.00003.00001.00004.00003.00003.0000), y6=(2.00003.00003.00005.00005.00004.0000),w6=(0.87860.93910.98961.25060.92841.4013), z6=(0.91170.95241.03861.24331.23961.4235).

The Uzawa algorithm based on QMR computed the approximations in 6 iterations as

x6=(1.00003.00001.00004.00003.00003.0000), y6=(2.00003.00003.00005.00005.00004.0000),w6=(0.83490.94731.02301.37780.60321.4566), z6=(0.89440.95371.03841.23791.26661.4163).

To solve this example by the Uzawa algorithm based on BICGSTAB, the following results have been obtained

x6=(1.00003.00001.00004.00003.00003.0000), y6=(2.00003.00003.00005.00005.00004.0000),w6=(0.88860.95861.01261.31820.67171.4601), z6=(0.90810.95291.04011.24161.24021.4212).

The exact solution of this FFLS is

x˜=((1, 2, 0.5, 1)(3, 3, 1, 2)(1, 3, 1, 1)(4, 5, 2, 1)(3, 5, 1, 2)(3, 4, 2, 2))

6. Conclusion

In this work, the solution of a trapezoidal fully fuzzy linear system of equations has been studied. Before, Uzawa algorithm has been widely used for solving system of saddle point problems because of its efficiency and minimal storage requirement. We found out that the mentioned fully fuzzy linear system of equations can be solved by different Uzawa approaches based on relaxation iterative methods such as Richardson, Jacobi, Gauss-Seidel, SOR, SSOR and by krylov subspace methods such as GMRES and BiCGSTAB. We note that the rate of convergence of Krylov subspace methods is higher than that of the relaxation methods and that they apply to a larger class of matrices. Also, Krylov methods are preferred because they have low computational costs. Numerical experiments of previous sections confirm the usefulness of our suggested methods for fully fuzzy linear systems.

References

1.Y Saad, Iterative Methods for Sparse Linear Systems, SIAM, 2003.

2.O Axelsson, Iterative Solution Methods, Cambridge University Press, 1996.

3.HA Van Der Vorst, Iterative Krylov methods for large linear systems, Cambridge University Press, Cambridge, 2013.

4.R Barrett et al., Templates for the Solution of Linear Systems Building Blocks for Iterative Methods, SIAM, 1994.

5.AT Chronopoulos, A Class of Parallel Iterative Methods Implemented on Multiprocessors, University of Illinois, Urbana, Illinois, 1986, pp. 1-116. Technical Report UIUCDCS-R-86-1267, Department of Computer Science

6.AT Chronopoulos, s-Step Iterative Methods for (Non)Symmetric (In)Definite Linear Systems, SIAM Journal on Numerical Analysis, Vol. 28, No. 6, 1991, pp. 1776-1789.

7.A Chronopoulos and D Kincaid, On the Odir iterative method for non-symmetric indefinite linear systems, Numerical Linear Algebra with Applications, Vol. 8, No. 2, 2001, pp. 71-82.

8.AT Chronopoulos, On the squared unsymmetric Lanczos method, Journal of Computational and Applied Mathematics, Vol. 54, No. 1, 1994, pp. 65-78.

9.AT Chronopoulos and A Kucherov, Block s-step Krylov iterative methods, Numerical Linear Algebra with Applications, Vol. 17, No. 1, 2010, pp. 3-15.

10.M Friedman, M Ming, and A Kandel, Fuzzy linear systems, Fuzzy Sets Syst, Vol. 96, 1998, pp. 201-209.

11.S Abbasbandy, A Jafarian, and R Ezzati, Conjugate gradient method for fuzzy symmetric positive-definite system of linear equations, Appl. Math. Comput, Vol. 171, 2005, pp. 1184-1191.

12.T Allahviranloo et al., On the solution of fuzzy linear system, Appl. Math. Model, Vol. 37, 2013, pp. 1170-1176.

13.D Behera and S Chakraverty, Solution of Fuzzy System of Linear Equations with Polynomial Parametric Form, Appl. Appl. Math, Vol. 7, No. 2, 2012, pp. 648-657.

14.R Ezzati, Solving fuzzy linear systems, Soft Comput, Vol. 15, 2011, pp. 193-197.

15.N Gasilov et al., A geometric approach to solve fuzzy linear systems, CMES Comp. Model. Eng, Vol. 75, No. 3, 2011, pp. 189-203.

16.P Husek, Stability Margin for Linear Systems with Fuzzy Parametric Uncertainty, PRICAI, 2008, pp. 708-717.

17.M Dehghan, B Hashemi, and M Ghatee, Computational methods for solving fully fuzzy linear systems, Appl. Math. Comput, Vol. 179, No. 1, 2006, pp. 328-343.

18.M Dehghan, B Hashemi, and M Ghatee, Solution of the fully fuzzy linear systems using iterative techniques, Chaos Soliton Fract, Vol. 34, No. 2, 2007, pp. 316-336.

19.J Vroman, G Deschrijver, and EE Kerre, Solving systems of linear fuzzy equations by parametric functions, IEEE T. Fuzzy Syst, Vol. 15, 2007, pp. 370-384.

20.T Allahviranloo et al., General solutions of fully fuzzy linear systems, Abstr. Appl. Anal, 2013. ID: 593274DOI/

21.T Allahviranloo et al., On the new solutions for a fully fuzzy linear system, Soft Computing, 2013.

22.S Moloudzadeh et al., A new method for solving an arbitrary fully fuzzy linear system, Soft Comput, Vol. 17, No. 9, 2013, pp. 1725-1731.

23.C Bacuta, A Unified Approach for Uzawa Algorithms, SIAM J. Numer. Anal, Vol. 44, No. 6, 2006, pp. 2633-2649.

24.ZH Cao, Fast Uzawa algorithm for generalized saddle point problems, Appl. Numer. Math, Vol. 46, 2003, pp. 157-171.

25.J Lu, Convergence Analysis of the Modified Nonlinear Inexact Uzawa Algorithm for Saddle Point Problem, Int. J. Contemp. Math. Sciences, Vol. 22, No. 7, 2012, pp. 1067-1075.

26.J Zhang and J Shang, A class of Uzawa-SOR methods for saddle point problems, Appl. Math. Comput, Vol. 216, 2010, pp. 2163-2168.

27.R Goetschel and W Voxman, Elementary fuzzy calculus, Fuzzy Sets Syst, Vol. 18, 1986, pp. 31-43.

28.K Wang and Y Wu, Uzawa-SOR method for fuzzy linear system, International Journal of Information and Computer Science (IJICS), Vol. 1, No. 2, 2012, pp. 30-33.

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Journal: International Journal of Computational Intelligence Systems
Volume-Issue: 9 - 5
Pages: 971 - 983
Publication Date: 2016/09/01
ISSN (Online): 1875-6883
ISSN (Print): 1875-6891
DOI: 10.1080/18756891.2016.1237194 How to use a DOI?
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Cite this article

ris enw bib

TY  - JOUR
AU  - H. Zareamoghaddam
AU  - A.T. Chronopoulos
AU  - M. Nouri Kadijani
AU  - Z. Zareamoghaddam
PY  - 2016
DA  - 2016/09/01
TI  - Uzawa Algorithms for Fully Fuzzy Linear Systems
JO  - International Journal of Computational Intelligence Systems
SP  - 971
EP  - 983
VL  - 9
IS  - 5
SN  - 1875-6883
UR  - https://doi.org/10.1080/18756891.2016.1237194
DO  - 10.1080/18756891.2016.1237194
ID  - Zareamoghaddam2016
ER  -

download .riscopy to clipboard