INTRODUCTION

Fuzzy linear systems (FLSs) occur in many fields, such as control problems, information, physics, statistics, engineering, economics, finance and even social sciences [1]. Thus, it is significant to develop models for solving FLSs theoretically and numerically [2, 3, 4].

A general model was suggested in [1] by Friedman et al. with embedding technique for solving a class of \(n\times n\) FLSs

$$Ax = y,$$
(1)

where

$$A=\left[ \begin{matrix}a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{matrix}\right]$$

is a crisp matrix, \(y=\left[ y_{1}, y_{2}, \cdots, y_{n} \right]^{\rm T}\) is a fuzzy vector, and \(x=\left[ x_{1}, x_{2}, \cdots, x_{n} \right]^{\rm T}\) is unknown, by which, Large numbers of numerical methods [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] was established to solve FLS (1).

Kaczmarz algorithm is a popular iterative projection method [23] as it is simple to implement and suitable for parallel computing. Many authors studied Kaczmarz methods for solving linear systems [23, 24, 25, 26]. In this paper, a Kaczmarz algorithm is proposed for fuzzy linear system (1).

The rest of the paper is organized as follows. Section 1 gives some basic definitions and results of FLS. In Section 2, the Kaczmarz method is presented with convergence theorem. Two numerical examples are discussed in Section 3 and the conclusion is in Section 4.

1. PRELIMINARIES

Generally, as defined in [1], a fuzzy number is a pair of \(( \underline{u}(r),\overline{u}(r))\), \(0\leqslant r\leqslant 1\), satisfying

  • \(\circ\) \(\underline{u}(r)\) is a bounded left continuous nondecreasing function over \([0,1]\),

  • \(\circ\) \(\overline{u}(r)\) is a bounded left continuous nonincreasing function over \([0,1]\),

  • \(\circ\) \(\underline{u}(r)\leqslant \overline{u}(r)\).

The arithmetic operations of arbitrary fuzzy numbers \(x = (\underline{x}(r),\overline{x}(r))\), \(y = (\underline{y}(r),\overline{y}(r))\), \(0\leqslant r\leqslant 1\), and real number k, are as follows,

(1) \(x=y\) if and only if \(\underline{x}(r)=\underline{y}(r)\) and \(\overline{x}(r)=\overline{y}(r)\),

(2) \(x+y=(\underline{x}(r)+\underline{y}(r),\overline{x}(r)+\overline{y} (r))\),

(3) \(kx=\left\{ \begin{array}{c} (k\underline{x}(r),k\overline{x}(r))\text{, }k\geqslant 0\text{,} \\ (k\overline{x}(r),k\underline{x}(r))\text{, }k<0\text{.} \end{array} \right.\)

Definition 1.

[1] A fuzzy number vector \(X=(x_{1},x_{2},\cdots ,x_{n})^{\text{T}}\) given by

$$x_{i}=(\underline{x}_{i}(r),\overline{x}_{i}(r))\text{, }1\leqslant i\leqslant n\text{, }\ 0\leqslant r\leqslant 1\text{,}$$

is called a solution of fuzzy linear system (1) if

$$\begin{array}{c} \underline{\sum\limits_{j=1}^{n}a_{ij}x_{j}}=\sum\limits_{j=1}^{n}\underline{ a_{ij}x_{j}}=\underline{y}_{i}\text{,}\vspace{.1cm} \\ \overline{\sum\limits_{j=1}^{n}a_{ij}x_{j}}=\sum\limits_{j=1}^{n}\overline{ a_{ij}x_{j}}=\overline{y}_{i}\text{.} \end{array}$$
(2)

By (2), M. Friedman et al.[1] extend FLS (1) to a \(2n\times 2n\) crisp linear system

$$SX=Y,$$
(3)

where \(S=(s_{kl})\) determined as

$$\left. \begin{array}{lllr} a_{ij}\geqslant 0 & \Rightarrow & s_{ij}=a_{ij}, & s_{n+i,\ n+j}=a_{ij}, \\ a_{ij}<0 & \Rightarrow & s_{i,\ n+j}=a_{ij}, & s_{n+i,\ j}=a_{ij}, \end{array}\right. \qquad1\leqslant i,j\leqslant n,$$

and any \(s_{kl}\) not in the above is zero (\(1\leqslant k\), \(l\leqslant 2n\)), and

$$X=\left[ \begin{array}{c} \underline{x}_{1} \\ \vdots \\ \underline{x}_{n} \\ \overline{x}_{1} \\ \vdots \\ \overline{x}_{n} \end{array}\right] \text{, }Y=\left[ \begin{array}{c} \underline{y}_{1} \\ \vdots \\ \underline{y}_{n} \\ \overline{y}_{1} \\ \vdots \\ \overline{y}_{n} \end{array}\right] \text{. }$$

Furthermore, the matrix S has the structure \(\left[ \begin{array}{cc} S_{1} & S_{2} \\ S_{2} & S_{1} \end{array} \right]\), \(A=S_{1}+S_{2}\), and (3) can be rewritten as

$$\begin{array}{l} S_{1}\underline{X}+S_{2}\overline{X}=\underline{Y}, \\ S_{2}\underline{X}+S_{1}\overline{X}=\overline{Y}, \end{array}$$
(4)

where

$$\underline{X}=\left[ \begin{array}{c} \underline{x}_{1} \\ \underline{x}_{2} \\ \vdots \\ \underline{x}_{n} \end{array}\right] \text{, }\overline{X}=\left[ \begin{array}{c} \overline{x}_{1} \\ \overline{x}_{2} \\ \vdots \\ \overline{x}_{n} \end{array}\right] \text{, }\underline{Y}=\left[ \begin{array}{c} \underline{y}_{1} \\ \underline{y}_{2} \\ \vdots \\ \underline{y}_{n} \end{array}\right] \text{, }\overline{Y}=\left[ \begin{array}{c} \overline{y}_{1} \\ \overline{y}_{2} \\ \vdots \\ \overline{y}_{n} \end{array}\right] \text{. }$$

The following theorem indicates when FLS (1) has a unique solution.

Theorem 1.

The matrix S is nonsingular if and only if the matrices \(A=S_{1}+S_{2}\) and \(S_{1}-S_{2}\) are both nonsingular. See [1].

In the next section, a Kaczmarz iterative scheme is presented for nonsingular FLS (1).

2. THE KACZMARZ METHOD

For nonsingular fuzzy linear system (3) or (4), a Kaczmarz method can be proposed as follows,

$$X_{k+1}=X_{k}+\dfrac{Y^{\left(i_k\right)}-S^{\left(i_k\right)}X_{k}}{\left\|S^{\left(i_k\right)}\right\|_2^2}\left(S^{\left(i_k\right)}\right)^{\rm T},$$

and can be implemented as the following algorithm.

KACZMARZ ALGORITHM. Given initial vectors \(\underline{X}_0, \overline{X}_0\in\mathbb{R}^{n}\), for \(k=0,1,2,\cdots\), the following iterative scheme is taken,

$$\begin{array}{l} \underline{X}_{k+1}=\underline{X}_{k}+\dfrac{(\underline{Y}-S_2\overline{X}_{k})^{\left(i_k\right)}-S_1^{\left(i_k\right)}\underline{X}_{k}}{\left\|S_1^{\left(i_k\right)}\right\|_2^2}\left(S_1^{\left(i_k\right)}\right)^{\rm T},\\ \overline{X}_{k+1}=\overline{X}_{k}+\dfrac{(\overline{Y}-S_2\underline{X}_{k+1})^{\left(i_k\right)}-S_1^{\left(i_k\right)}\overline{X}_k}{\left\|S_1^{\left(i_k\right)}\right\|_2^2}\left(S_1^{\left(i_k\right)}\right)^{\rm T}, \end{array}$$
(5)

where \(i_k=(k{\rm\ mod\ }n)+1\), and \({\left(\cdot\right)}^{\left(i_k\right)}\) denotes the ikth row of a matrix.

The convergence result for method (5) is as the following theorem.

Theorem 2.

Suppose that fuzzy linear system (3) or (4) is consistent. Then the iterative sequence \(\left\{ \begin{bmatrix} \underline{X}_k\\ \overline{X}_k \end{bmatrix}\right\}_{k=0}^{\infty}\), generated by the Kaczmarz method  (5) starting from an initial guess \(\begin{bmatrix} \underline{X}_0\\ \overline{X}_0 \end{bmatrix}\) with \(\underline{X}_0\) and \(\overline{X}_0\) in the column space of S2, converges to the unique solution \(\begin{bmatrix} \underline{X}_*\\ \overline{X}_* \end{bmatrix} = \begin{bmatrix} S_1 & S_2 \\ S_2 & S_1 \end{bmatrix}^{-1} \begin{bmatrix} \underline{Y}\\ \overline{Y} \end{bmatrix}\) of (3). Moreover, the solution error for the iteration sequence is

$$\begin{aligned} \left\|X_{k+1}-X_*\right\|_2^2&\leqslant\left(1-\frac{\lambda_{\min}(S^{\rm T}S)}{\left\|S\right\|_F^2}\right)\left\|X_k-X_*\right\|_2^2, \end{aligned}$$

where \(\lambda_{\rm min}\left(\cdot\right)\) is the smallest nonzero eigenvalue of a matrix, \(X_k= \begin{bmatrix} \underline{X}_k\\ \overline{X}_k \end{bmatrix}\) and \(X_*= \begin{bmatrix} \underline{X}_*\\ \overline{X}_* \end{bmatrix}\).

Proof. Take \(P^{\left(i_k\right)}=\left(\dfrac{S^{\left(i_k\right)}}{\left\|S^{\left(i_k\right)}\right\|_2}\right)^{\rm T}\left(\dfrac{S^{\left(i_k\right)}}{\left\|S^{\left(i_k\right)}\right\|_2}\right)\), thus

$$X_{k+1}-X_* =X_k-X_*+\frac{Y^{\left(i_k\right)}-S^{\left(i_k\right)}X_k}{\left\|S^{\left(i_k\right)}\right\|_2^2}\left(S^{\left(i_k\right)}\right)^{\rm T}$$
$$=\ X_k-X_*-\left(S^{\left(i_k\right)}\right)^{\rm T}\frac{S^{\left(i_k\right)}\left(X_k-X_*\right)}{\left\|S^{\left(i_k\right)}\right\|_2^2}=\left(I-P^{\left(i_k\right)}\right)\left(X_k-X_*\right),$$

then

$$\left\|X_{k+1}-X_*\right\|_2^2=\left(X_k-X_*\right)^{\rm T}\left(I-P^{\left(i_k\right)}\right)^2\left(X_k-X_*\right)$$
$$=\ \left(X_k-X_*\right)^{\rm T}\left(I-P^{\left(i_k\right)}\right)\left(X_k-X_*\right) =\left\|X_k-X_*\right\|_2^2-\left(X_k-X_*\right)^{\rm T}P^{\left(i_k\right)}\left(X_k-X_*\right),$$

and

$$\begin{gathered}\left(X_k-X_*\right)^{\rm T}P^{\left(i_k\right)}\left(X_k-X_*\right) =\frac{\left(X_k-X_*\right)^{\rm T}\left(S^{\left(i_k\right)}\right)^{\rm T}S^{\left(i_k\right)}\left(X_k-X_*\right)}{\left\|S^{\left(i_k\right)}\right\|_2^2}\\ =\ \frac{\left|S^{\left(i_k\right)}\left(X_k-X_*\right)\right|^2}{\left\|S^{\left(i_k\right)}\right\|_2^2}\geqslant\frac{\left\|S\left(X_k-X_*\right)\right\|_2^2}{\left\|S\right\|_F^2}. \end{gathered}$$

As x0 is in the column space of S, from [23], it holds that \(\left\|S\left(X_k-X_*\right)\right\|_2^2\geqslant\lambda_{\rm min}(S^{\rm T}S)\left\|\left(X_k-X_*\right)\right\|_2^2\). Therefore, the following is obtained

$$\begin{aligned} \left\|X_{k+1}-X_*\right\|_2^2&\leqslant\left(1-\frac{\lambda_{\rm min}(S^{\rm T}S)}{\left\|S\right\|_F^2}\right)\left\|X_k-X_*\right\|_2^2. \end{aligned}$$

The proof is completed. \(\square\)

3. NUMERICAL EXAMPLES

This section gives two illustrative examples to show the effectiveness of the Kaczmarz method. All implements using Matlab 7 run in a Windows 7 DELL laptop with Intel 2.80GHz CPU and 8.00GB RAM. In the numerical experiments, the initial guess is zero and the stopping criterion is

$$\left\Vert R_{k}\right\Vert _{2}<10^{-6},$$

where \(R_{k}\) is the residual vector after k iterations, i. e., \(R_{k}=Y-SX_{k}\).

In the actual calculations, \(SX=Y\) is solved by two numeric systems

$$S\left[ \begin{array}{c} x_{a1} \\ x_{a2} \\ \vdots \\ x_{a,2n} \end{array}\right] =\left[ \begin{array}{c} y_{a1} \\ y_{a2} \\ \vdots \\ y_{a,2n} \end{array}\right] \text{ and }S\left[ \begin{array}{c} x_{b1} \\ x_{b2} \\ \vdots \\ x_{b,2n} \end{array}\right] =\left[ \begin{array}{c} y_{b1} \\ y_{b2} \\ \vdots \\ y_{b,2n} \end{array}\right],$$

not by one symbolic system

$$S\left[ \begin{array}{c} x_{a1}+x_{b1}r \\ x_{a2}+x_{b2}r \\ \vdots \\ x_{a,2n}+x_{b,2n}r \end{array}\right] =\left[ \begin{array}{c} y_{a1}+y_{b1}r \\ y_{a2}+y_{b2}r \\ \vdots \\ y_{a,2n}+y_{b,2n}r \end{array}\right].$$

Example 1.

Consider \(n\times n\) fuzzy linear system \(Ax=y\) with

$$A=\left[ \begin{matrix}8 & -1 & -1 & -1 & & & & & \\ -\ 1 & 8 & -1 & -1 & \ddots & & & & \\ -\ 1 & -1 & 8 & -1 & \ddots & \ddots & & & \\ -\ 1 & -1 & -1 & 8 & \ddots & \ddots & \ddots & & \\ & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \\ & & \ddots & \ddots & \ddots & 8 & -1 & -1 & -1 \\ & & & \ddots & \ddots & -1 & 8 & -1 & -1 \\ & & & & \ddots & -1 & -1 & 8 & -1 \\ & & & & & -1 & -1 & -1 & 8 \end{matrix}\right]$$

and

$$y=\left[ \begin{array}{c} (2+r,2+r) \\ (2+r,2+r) \\ \vdots \\ (2+r,2+r) \end{array}\right] .$$

Example 2.

Consider \(n^2\times n^2\) fuzzy linear system \(Ax=y\) with

$$A=\left[ \begin{matrix}D & B^{\rm T} & & & \\ B & D & \ddots & & \\ & \ddots & \ddots & \ddots & \\ & & \ddots & D & B^{\rm T} \\ & & & B & D \end{matrix}\right],$$

where

$$B=\left[ \begin{matrix}0.5 & -0.25 & & & \\ -\ 0.25 & 0.5 & \ddots & & \\ & \ddots & \ddots & \ddots & \\ & & \ddots & 0.5 & -0.25 \\ & & & -0.25 & 0.5 \end{matrix}\right],\ D=\left[ \begin{matrix}5 & -1 & & & \\ -\ 1 & 5 & \ddots & & \\ & \ddots & \ddots & \ddots & \\ & & \ddots & 5 & -1 \\ & & & -1 & 5 \end{matrix}\right],$$

and

$$y=\left[ \begin{array}{c} (1+r,1+r) \\ (2+r,2+r) \\ \vdots \\ (n^2+r,n^2+r) \end{array}\right].$$

Tables 1 and 2 give the number of iterations (IT) and the residual of the stopping step (RES). As n increases, the method requires more iterations and converges very slowly, thus, improvement should be made to change the convergence.

Table 1 Iterations (IT) and Residual (RES) for Example 1
Full size table
Table 2 Iterations (IT) and Residual (RES) for Example 2
Full size table

4. CONCLUSION

A Kaczmarz method is proposed for solving \(n\times n\) fuzzy linear systems. The numerical results show that the method is effective. Further work would be improving the method with stochastic approximation and comparing with other methods. And more interesting work would be exploring the real applications in natural science.