Solving fuzzy linear systems

Abstract

In this paper, the main aim is to develop a method for solving an arbitrary general fuzzy linear system by using the embedding approach. Considering the existing and uniqueness of fuzzy solution to n × n linear fuzzy system is done. Numerical examples are presented to illustrate the proposed model.

1 Introduction

System of simultaneous linear equations is important for studying and solving a large proportion of the problems in many topics in applied mathematics. Usually, in many applications, at least some of the system’s parameters are represented by fuzzy rather than crisp numbers, and hence it is important to develop mathematical models and solving methods that would appropriately treat general fuzzy linear systems and solve them. A general model for solving an arbitrary n × n fuzzy linear system whose coefficients matrix is crisp and the right hand side column is an arbitrary fuzzy number vector were first proposed by Friedman et al. (1998) and they studied duality fuzzy linear systems in Friedman et al. (2000). They used the embedding method given in Cong-Xin and Ming (1991) and replaced the original fuzzy linear system by 2n × 2n crisp linear system. The numerical solution of fuzzy linear system is studied in Allahviranloo (2004a, b, 2005). Solving $m\times n\; (m\leq n)$ original fuzzy linear system by 2m × 2n crisp system is done in Asady et al. (2005). In Abbasbandy et al. (2007), the authors obtained the least square symmetric solution of m × n fuzzy general linear systems, in which m ≤ n. Recently, Ezzati (2008) solved $m\times n\;(m\leq n)$ dual fuzzy general linear systems by two m × n crisp linear systems.

In this work, we give a new method for solving a n × n fuzzy linear system whose coefficients matrix is crisp and the right-hand side column is an arbitrary fuzzy number vector by using the embedding method given in Cong-Xin and Ming (1991) and replace the original n × n fuzzy linear system by two n × n crisp linear systems. It is clear that in large systems, solving n × n linear system is better than solving 2n × 2n linear system. Since perturbation analysis is very important in numerical methods, the authors of Wang et al. (2009) presented the perturbation analysis for a class of fuzzy linear systems which could be solved by an embedding method. Now, according to the presented method in this paper, we can investigate perturbation analysis in two n × n crisp linear systems instead of 2n × 2n linear system as the authors of Wang et al. (2009) have done.

The paper is organized as follows. In Sect. 2, we introduce the notation, the definitions, and preliminary results that will be used throughout the paper. In this section, we review the proposed method in Friedman et al. (1998). In Sect. 3, the model for solving fuzzy linear system is proposed. The proposed model is illustrated by solving some examples in Sect. 4 and conclusions are drawn in Sect. 5.

2 Preliminaries

Definition 1

A fuzzy number is a fuzzy set like $\widetilde{u}: {\mathbb{R}}\rightarrow I=[0,1]$ which satisfies, Dubois and Prade (1980),

• 1. $\widetilde{u}$ is upper semi-continuous,

• 2. $\widetilde{u}(x)=0$ outside some interval [c, d],

• 3. There are real numbers a, b such that $c\leq a\leq b \leq d$ and

  • 3.1 $\widetilde{u}(x)$ is monotonic increasing on [c, a],

  • 3.2 $\widetilde{u}(x)$ is monotonic decreasing on [b, d],

  • 3.3 $\widetilde{u}(x)=1,\; a\leq x \leq b.$

The set of all these fuzzy numbers is denoted by E ¹. An equivalent parametric form is also given in Friedman et al. (1998, 2000) and Ma et al. (1999) as follows.

Definition 2

A fuzzy number $\widetilde{u}$ in parametric form is an ordered pair of functions $(\underline {u}(r), \overline{u}(r)),\;0 \leq r \leq 1$, which satisfy the following requirements:

• 1. $\underline {u}(r)$ is a bounded monotonic increasing left continuous function,

• 2. $\overline{u}(r)$ is a bounded monotonic decreasing left continuous function,

• 3. $\underline {u}(r)\leq \overline{u}(r),\; 0 \leq r \leq 1.$

Remark 1

A crisp number α is simply represented by $\underline {u}(r)=\overline{u}(r)=\alpha, 0 \leq r \leq 1.$

The triangular fuzzy numbers are very popular and denoted by $\widetilde{u}=(c, \alpha, \beta)$ and defined by

$$ \widetilde{u}(x)= \left\{\begin{array}{ll} {\frac{x-c+\alpha}{\alpha}}, & c-\alpha \leq x \leq c, \\ {\frac{c+\beta-x}{\beta}}, & c \leq x \leq c+\beta,\\ 0, & \hbox{otherwise},\\ \end{array}\right. $$

where α > 0 and β > 0. It is clear that

$$ \underline u(r)=r\alpha+c - \alpha,\quad \overline{u}(r)=c+\beta-\beta r. $$

The addition and scalar multiplication of fuzzy numbers are defined by the extension principle and can be equivalently represented as follows, see Friedman et al. (1998, 2000) and Ma et al. (1999).

For arbitrary $\widetilde{u}=(\underline{u}, \overline{u})$, $\widetilde{v}=(\underline{v},\overline{v})$ and real number k we define equality $\widetilde{u}=\widetilde{v}$, addition $(\widetilde{u}+\widetilde{v})$ and multiplication as follows:

• (i) $\widetilde{u}=\widetilde{v}$ if and only if $\underline{u}(r)=\underline{v}(r)$ and $\overline{u}(r)=\overline{v}(r).$

• (ii) $\widetilde{u}+\widetilde{v}=(\underline{u}(r)+ \underline{v}(r), \overline{u}(r)+\overline{v}(r)).$

• (iii) $k\widetilde{u}=\left\{\begin{array}{ll} (k\underline{u},k\overline{u}) & ,\; k\geq 0,\\ (k\overline{u},k\underline{u}) &, \; k< 0.\\ \end{array}\right.$

Definition 3

The n × n linear system of equations

$$ \begin{array}{l} a_{11}\widetilde{x}_{1}+a_{12}\widetilde{x}_{2}+\cdots+a_{1n} \widetilde{x}_{n}=\widetilde{y}_{1},\\ a_{21}\widetilde{x}_{1}+a_{22}\widetilde{x}_{2}+\cdots +a_{2n} \widetilde{x}_{n}=\widetilde{y}_{2}, \\ \vdots \\ a_{n1}\widetilde{x}_{1}+a_{n2}\widetilde{x}_{2}+\cdots +a_{nn}\widetilde{x}_{n}=\widetilde{y}_{n},\\ \end{array} $$

(1)

where the coefficients matrix $A=(a_{ij}), 1\leq i, j \leq n$ is a crisp n × n matrix and $\widetilde{y}_{i} \in E^{1},\; 1\leq i \leq n$ and the unknowns $\widetilde{x}_{j} \in E^{1},$ $1 \leq j \leq n$ is called a fuzzy linear system (FLS).

Definition 4

A fuzzy number vector $(\widetilde{x}_{1},\widetilde{x}_{2},\ldots,\widetilde{x}_{n})^{t}$ given by

$$ \widetilde{x}_{j}=(\underline{x}_{j}(r),\overline{x}_{j}(r)),\; 1\leq j \leq n,\; 0\leq r \leq 1, $$

is called a solution of (1) if

$$ \begin{array}{ll} {\begin{array}{l} \underline{\sum\limits_{j=1}^{n}a_{ij}\widetilde{x}_{j}}=\sum\limits_{j=1}^{n} \underline{a_{ij}\widetilde{x}_{j}}=\underline{y}_{i}, \\ \\ \overline{\sum\limits_{j=1}^{n}a_{ij}\widetilde{x}_{j}}= \sum\limits_{j=1}^{n}\overline{a_{ij}\widetilde{x}_{j}}=\overline{y}_{i}.\\ \end{array}} & \quad {i=1,2,\ldots,n.} \\ \end{array} $$

(2)

Finally, we conclude this section by a reviewing on the proposed method for solving fuzzy linear system in Friedman et al. (1998).

The authors of Friedman et al. (1998) wrote the linear system of Eq. 2 as follows:

$$ SX=Y, $$

where the element of S = (s _ij ), 1 ≤ i, j ≤ 2n, were as follows:

$$ \begin{aligned} a_{ij}&\geq 0\Rightarrow s_{ij}=a_{ij},\;s_{i,j+n}=a_{ij},\\ a_{ij}&< 0\Rightarrow s_{i,j+n}=-a_{ij},\;s_{i+n,j}=-a_{ij},\\ \end{aligned} $$

(3)

and any s _ij is not determined by Eq. 3 is zero, the unknowns and the right-hand side column were

$$ \begin{aligned} X&=(\underline {x}_1, \underline {x}_2,\ldots,\underline {x}_n, -\overline{x}_1, -\overline{x}_2,\ldots,-\overline{x}_n)^T,\\ Y&=(\underline {y}_1, \underline {y}_2,\ldots,\underline {y}_n, -\overline{y}_1, -\overline{y}_2,\ldots,-\overline{y}_n)^T,\\ \end{aligned} $$

(4)

respectively. The structure of S implies that $s_{ij}\geq 0,$ $1 \leq i,j \leq 2n$ and that

$$ S=\left(\begin{array}{ll} B & C\\ C & B\\ \end{array}\right) $$

where B contains the positive entries of A and C the absolute values of the entries of the negative entries of A and A = B − C.

Theorem 1

(Friedman et al. 1998) The matrix S is nonsingular if and only if the matrices A = B − C and B + C are both nonsingular.

Theorem 2

(Friedman et al. 1998) If S ⁻¹ exists it must have the same structure as S, i.e.

$$ S^{-1}=\left(\begin{array}{ll} D & E\\ E & D\\ \end{array}\right) $$

where $D={\frac{1}{2}}[(B+C)^{-1}+(B-C)^{-1}]$ and $E={\frac{1} {2}}[(B+C)^{-1}-(B-C)^{-1}]$. We know that if S is nonsingular then

$$ X=S^{-1}Y, $$

but this solution may still not be an appropriate fuzzy vector, see the following example.

Example 1

Consider the 3 × 3 fuzzy system

$$ \begin{aligned} &4\widetilde{x}_{1}+2\widetilde{x}_{2}-\widetilde{x}_{n}=(-27 + 7r,-7 - 13r), \\ &2\widetilde{x}_{1}+7\widetilde{x}_{2}+6\widetilde{x}_{n}=(1 + 15r,40 - 24r), \\ &-\widetilde{x}_{1}+6\widetilde{x}_{2}+10\widetilde{x}_{n}=(26 + 18r,47 - 3r). \\ \end{aligned} $$

This fuzzy system will not be a fuzzy solution if we use the method of Friedman et al. (1998).

3 The proposed model

In this section, we propose a new method for solving fuzzy linear system.

Theorem 3

Suppose the inverse of matrix A in Eq. 1 exists and $\widetilde{x}=(\widetilde{x}_1, \widetilde{x}_2,\ldots,\widetilde{x}_n)^T$ is a fuzzy solution of this equation. Then $\underline {x}+\overline{x}=(\underline {x}_1+\overline{x}_1,\underline {x}_2+\overline{x}_2,\ldots,\underline {x}_n+\overline{x}_n)^T$ is the solution of the following system

$$ A(\underline {x}+\overline{x})=\underline {y}+\overline{y} $$

where $\underline {y}+\overline{y}=(\underline {y}_1+\overline{y}_1,\underline {y}_2+\overline{y}_2,\ldots,\underline {y}_n+\overline{y}_n)^T$.

Proof

Suppose the parametric form of $\widetilde{x_{j}}$ be $\widetilde{x_{j}}=(\underline {x}_{j},\overline{x}_{j}),$ $1\leq j \leq n,$ and let $a_{ij}=a_{ij}^{\prime}-a_{ij}^{\prime\prime}$ such that $a_{ij}^{\prime}$ and $a_{ij}^{\prime\prime}$ are positive and $a_{ij}^{\prime}.a_{ij}^{\prime\prime}=0.$ If we consider Eq. 1 in the parametric form then for $i=1,2,\ldots,n,$ we have:

$$ (a_{i1}^{\prime}-a_{i1}^{\prime\prime})(\underline {x}_{1},\overline{x}_{1})+\cdots+(a_{in}^{\prime}-a_{in}^{\prime\prime}) (\underline {x}_{n},\overline{x}_{n})=(\underline {y}_{i},\overline{y}_{i}), $$

(5)

hence

$$ a_{i1}^{\prime}\underline {x}_{1}-a_{i1}^{\prime\prime}\overline{x}_{1}+ a_{i2}^{\prime}\underline {x}_{2}-a_{i2}^{\prime\prime}\overline{x}_{2} +\cdots+a_{in}^{\prime}\underline {x}_{n}-a_{in}^{\prime\prime}\overline{x}_{n} =\underline {y}_{i}, $$

(6)

and

$$ a_{i1}^{\prime} \overline{x}_{1}-a_{i1}^{\prime\prime}\underline {x}_{1}+ a_{i2}^{\prime} \overline{x}_{2}-a_{i2}^{\prime\prime}\underline {x}_{2} +\cdots+a_{in}^{\prime}\overline{x}_{n}-a_{in}^{\prime\prime}\underline {x}_{n} =\overline{y}_{i}. $$

(7)

By addition of Eqs. 5 and 7 we have:

$$ (a_{i1}^{\prime}-a_{i1}^{\prime\prime})(\underline {x}_{1}+\overline{x}_{1})+(a_{i2}^{\prime}-a_{i2}^{\prime\prime}) (\underline {x}_{2}+\overline{x}_{2})+\cdots+ (a_{in}^{\prime}-a_{in}^{\prime\prime})(\underline {x}_{n} +\overline{x}_{n})=(\underline {y}_{i}+\overline{y}_{i}), $$

(8)

and hence

$$ a_{i1}(\underline {x}_{1}+\overline{x}_{1}) +a_{i2}(\underline {x}_{2}+\overline{x}_{2})+\cdots +a_{in}(\underline {x}_{n}+\overline{x}_{n}) =(\underline {y}_{i}+\overline{y}_{i}). $$

Therefore, $X=(\underline {x}_{1}+\overline{x}_{1}, \underline {x}_{2}+\overline{x}_{2}, \ldots,\underline {x}_{n}+\overline{x}_{n})^T$ is the solution of $A(\underline {x}+\overline{x})=\underline {y}+\overline{y}$. □

For solving Eq. 1, we first solve the following system:

$$ \left\{\begin{array}{l} a_{11}(\underline {x}_{1}+\overline{x}_{1})+\cdots+a_{1n}(\underline {x}_{n} +\overline{x}_{n})=(\underline {y}_{1}+\overline{y}_{1}),\\ a_{21}(\underline {x}_{1}+\overline{x}_{1})+\cdots +a_{2n}(\underline {x}_{n}+\overline{x}_{n})=(\underline {y}_{2}+ \overline{y}_{2}), \\ \vdots \\ a_{n1}(\underline {x}_{1}+\overline{x}_{1})+\cdots + a_{nn}(\underline {x}_{n}+\overline{x}_{n})=(\underline {y}_{n}+\overline{y}_{n}),\\ \end{array}\right. $$

(9)

and suppose the solution of this system is as

$$ d =\left[\begin{array}{c} d_{1} \\ d_{2} \\ \vdots\\ d_{n}\\ \end{array}\right] =\underline{x}+\overline{x}=\left[\begin{array}{c} \underline{x}_{1}+\overline{x}_{1} \\ \underline{x}_{2}+\overline{x}_{2} \\ \vdots\\ \underline{x}_{n}+\overline{x}_{n}\\ \end{array}\right]. $$

Let matrices B and C have defined as Sect. 2. Now using matrix notation for Eq. 1, we get $A\widetilde{x}=\widetilde{y}$ or $(B-C)\widetilde{x}=\widetilde{y}$ and in parametric form $(B-C)(\underline{x}(r),\overline{x}(r))=(\underline{y}(r), \overline{y}(r))$. We can write this system as follows:

$$ \left\{\begin{array}{l} B\underline{x}(r)-C\overline{x}(r)=\underline {y}(r),\\ B\overline{x}(r)-C\underline {x}(r)=\overline{y}(r),\\ \end{array}\right. $$

By substituting of $\overline{x}(r)=d-\underline{x}(r)$ and $\underline{x}(r)=d-\overline{x}(r)$ in the first and second equation of above system, respectively, we have

$$ (B+C)\underline{x}(r)=\underline{y}(r)+Cd, $$

(10)

and

$$ (B+C)\overline{x}(r)=\overline{y}(r)+Cd. $$

(11)

If the inverse of matrix F = B + C exist then

$$ \underline{x}(r)=F^{-1}(\underline{y}(r)+Cd), $$

(12)

$$ \overline{x}(r)=F^{-1}(\overline{y}(r)+Cd). $$

(13)

Therefore, we can solve fuzzy linear system Eq. 1 by solving Eqs. 9–10. The solution vector is unique but may still not be an appropriate fuzzy vector, see example 1.

Theorem 4

Assume that n is any integer, n ≥ 2, and denote byd _n andD _n the number of multiplication operations that are required to calculate$X=(\underline{x}_1,\underline{x}_2,\ldots,\underline{x}_n, -\overline{x}_1,-\overline{x}_2,\ldots,-\overline{x}_n)^T=S^{-1}Y$ (the proposed method in Friedman et al. (1998)) and$X=(\underline{x}_1,\underline{x}_2,\ldots,\underline {x}_n,\overline{x}_1,\overline{x}_2,\ldots,\overline{x}_n)^T$from Eqs. 9–10, respectively. Then

$$ D_n \leq d_n $$

and

$$ d_n-D_n=n^2. $$

Proof According to Sect. 2, we have

$$ S^{-1}=\left(\begin{array}{ll} D & E\\ E & D\\ \end{array}\right) $$

where $D={\frac{1}{2}}[(B+C)^{-1}+(B-C)^{-1}]$ and $E={\frac{1} {2}}[(B+C)^{-1}-(B-C)^{-1}].$ Therefore, for determining S⁻¹, we need to compute (B + C)⁻¹ and (B − C)⁻¹. Now, assume that M is n × n matrix and denote by h _n (M) the number of multiplication operations that are required to calculate M⁻¹. It is clear that

$$ h_n(S)=h_n(B+C)+h_n(B-C)=2h_n(A) $$

and hence

$$ d_n=2h_n(A)+4n^2. $$

For computing $\underline {x}+ \overline{x}=(\underline {x}_1+ \overline{x}_1,\underline {x}_2+ \overline{x}_2,\ldots,\underline {x}_n+ \overline{x}_n)^T$ from Eq. 9 and $\underline {x}=(\underline {x}_1,\underline {x}_2,\ldots,\underline {x}_n)^T$ from Eq. 10, the number of multiplication operations are $h_n(A)+n^2$ and $h_n(B+C)+2n^2,$ respectively. Clearly $h_n(B+C)=h_n(A),$ so

$$ D_n=2h_n(A)+3n^2 $$

and hence

$$ d_n-D_n=n^2. $$

This proves Theorem. $\square$

As Friedman et al. (1998), we restrict the discussion to triangular fuzzy numbers. Having calculated $\underline {x}(r)=(\underline {x}_1(r),\underline {x}_2(r),\ldots,\underline {x}_n(r))^T$ and $\overline{x}(r)=(\overline{x}_1(r),\overline{x}_2(r),\ldots, \overline{x}_n(r))^T$ which solve Eqs. 9–10, we now define fuzzy solution to the original system given by Eq. 1.

Definition 5

Let $x=\{(\underline {x}_{j}(r),\overline{x}_{j}(r)),1\leq j \leq n\}$ denote the unique solution of Eqs. 9 and 10. The fuzzy number vector $\widetilde{U}=\{(\underline {u}_{j}(r),\overline{u}_{j}(r)), 1\leq j \leq n\}$ defined by

$$ \underline {u}_{j}(r)=\hbox{min}\{\underline {x}_{j}(r),\overline{x}_{j}(r), \underline {x}_{j}(1)\}, $$

$$ \overline{u}_{j}(r)=\hbox{max}\{\underline {x}_{j}(r),\overline{x}_{j}(r), \overline{x}_{j}(1)\} $$

is called the fuzzy solution of Eqs. 9–10.

If $\underline{u}_{j}(r)=\underline{x}_{j}(r)$ and $\overline{u}_{j}(r)=\overline{x}_{j}(r),$ $1 \leq j \leq n,$ then $\widetilde{U}$ is called a strong fuzzy solution. Otherwise, $\widetilde{U}$ is called a weak fuzzy solution.

4 Numerical examples

Example 2

(Friedman et al. 1998) Consider the 2 × 2 fuzzy linear system

$$ \begin{aligned} &\widetilde{x_{1}}-\widetilde{x_{2}}=(r,2-r),\\ &\widetilde{x_{1}}+3\widetilde{x_{2}}=(4+r,7-2r).\\ \end{aligned} $$

By using Eqs. 9 and 10 (or Eq. 12) we have:

$$ \left[\begin{array}{l} \underline{x}_1(r)+\overline {x}_1(r)\\ \underline{x}_2(r)+\overline{x}_2(r)\\ \end{array}\right] =\left[\begin{array}{l} \left({\frac{17-r}{4}}\right)\\ \left({\frac{9-r}{4}}\right)\\ \end{array}\right], $$

$$ \left[\begin{array}{l} \underline {x}_1(r)\\ \underline {x}_2(r)\\ \end{array}\right]=\left[\begin{array}{l} 1.375+ 0.625r\\ 0.875+0.125r\\ \end{array}\right], $$

and hence

$$ \left[\begin{array}{l} \overline{x}_1(r)\\ \overline{x}_2(r)\\ \end{array}\right]=\left[\begin{array}{l} 2.875- 0.875r\\ 1.375-0.375r\\ \end{array}\right]. $$

According to this fact that $\underline {x}_i \leq \overline{x}_i ,$ i = 1, 2, are monotonic decreasing functions then the fuzzy solution $\widetilde{x}_i=(\underline {x}_i, \overline{x}_i),$ i = 1, 2, is a strong fuzzy solution.

Example 3

(Friedman et al. 1998) Consider the 3 × 3 fuzzy linear system

$$ \left\{\begin{array}{l} \widetilde{x_{1}}+1\widetilde{x_{2}}-\widetilde{x_{3}}=(r,2-r),\\ \widetilde{x_{1}}-2\widetilde{x_{2}}+\widetilde{x_{3}}=(2+r,3),\\ 2\widetilde{x_{1}}+\widetilde{x_{2}}+3\widetilde{x_{3}}=(-2,-1-r).\\ \end{array}\right. $$

(14)

In this example

$$ \left[\begin{array}{l} \underline {x}_1(r)+\underline {x}_2(r)\\ \overline{x}_1(r)+\overline{x}_2(r)\\ \underline {x}_3(r)+\overline{x}_3(r)\\ \end{array}\right]=\left[\begin{array}{l} (2.38462+0.230769r)\\ (-2.23077-0.538462)\\ (-1.84615-0.307692r)\\ \end{array}\right], $$

$$ \left[\begin{array}{l} \underline {x}_1(r)\\ \underline {x}_2(r)\\ \underline {x}_3(r)\\ \end{array}\right]=\left[\begin{array}{l} -2.31+3.62r\\ -0.62-0.77r\\ 1.08-2.15r\\ \end{array}\right], $$

and by notice to Eq. 9 we have

$$ \left[\begin{array}{l} \overline{x}_1(r)\\ \overline{x}_2(r)\\ \overline{x}_3(r)\\ \end{array}\right] =\left[\begin{array}{l} 4.69-3.38r\\ -1.62+0.23r\\ -2.92+1.85r\\ \end{array}\right]. $$

It is clear that $\widetilde{x}_2$ and $\widetilde{x}_3$ are not fuzzy numbers and the fuzzy solution in this case is weak solution. This weak solution is as follows:

$$ \left[\begin{array}{l} \widetilde{u}_1\\ \widetilde{u}_2\\ \widetilde{u}_3\\ \end{array}\right] =\left[\begin{array}{l} (-2.31+3.62r,4.69-3.38r)\\ (-1.62+0.23r,-0.62-0.77r)\\ (-2.92+1.85r,1.08-2.15r)\\ \end{array}\right], $$

5 Conclusion

In this paper, we proposed a general model for solving fuzzy linear system. The original system is replaced by two n × n crisp linear systems.