# A Note on the Inner-Outer Iterative Method for Solving the Linear EquationAx = b

Authors: Li-Tao Zhang; Xian-Yu Zuo; Tong-Xiang Gu; Yan-Ping Wang; Yi-Fan Zhang; Jian-Lei Li; Sheng-Kun Li
Journal: Journal of Mathematics
 (2020)

---

## Abstract

Recently, Tian et al. [Computers and Mathematics with Applications, 75(2018): 2710-2722] came up with the inner-outer iterative method to solve the linear equationAx=b and studied the corresponding convergence of the method. In this paper, we improve the main results of the inner-outer method and get weaker convergence results. Moreover, the parameters can be adjusted suitably so that the convergence property of the method can be substantially improved.


---

## Body

## 1. Introduction

When it comes to solving the large sparse linear system(1)Ax=b,where A∈RN×N is a square nonsingular matrix and x,b∈RN, an iterative method is commonly used. Multisplitting for parallel solutions was initially introduced and adopted by O’Leary and White [1] for solving the linear equations and further studied by many other authors [2–35]. Among them, Prof. Bai [2–9] did a mountain of great work and constructed the parallel nonlinear AOR method about matrix multisplitting, the parallel chaotic multisplitting method, the two-stage multisplitting method under suitable constraints about two-stage multisplitting, some new hybrid algebraic multilevel preconditioning algorithms, nonstationary multisplitting iterative algorithms, and the nonstationary multisplitting two-stage iterative algorithms. Apart from these methods, Gu et al. [13, 14], Cao et al. [16–18], Wang et al. [15, 24, 26, 27, 29, 30], and Zhang et al. [28, 29, 31] also constructed relaxed nonstationary two-stage multisplitting algorithms, nested stationary iterative algorithms, relaxed parallel multisplitting AOR, USAOR, and SSOR algorithms on an H-matrix, two relaxed multisplitting algorithms for different weighting types when A is a monotone matrix or M-matrix, the parallel multisplitting TOR algorithm, and the global relaxed parallel multisplitting USAOR (GUSAOR) algorithm. Recently, Tian et al. [22] studied the inner-outer iterative method for the linear equation Ax=b and deduced the corresponding convergence of the inner-outer algorithm. In this paper, based the inner-outer iterative method, we conducted a further analysis and obtained some convergence results weaker than Tian et al.’s.In this paper, we present the inner-outer iterative method in Section2 and show the essentially procedural deduction as well as its corresponding main results in Section 3. Compared with those earlier studies, our findings of convergence results are more applicable. Furthermore, our new convergent domain of the parameter α is wider than that in [22]. Therefore, the convergence property of the method can be substantially improved due to the suitable adjustability of the parameters we adopted.


## 2. The Inner-Outer Iterative Method

In 2018, Tian et al. [22] presented an inner-outer iterative algorithm for the linear system Ax=b. Let A=M−N be a convergent splitting; then, the authors can obtain the following linear system equivalent to (1):(2)I−Rx=c,where R=M−1N and c=M−1b.Then, the inner-outer iterative method for (2) is expressed as follows:(3)I−αRxk+1=1−αRxk+c,k=0,1,2,…,with α>0. Here, we regard (3) as the outer iteration. Let g=1−αRxk+c, and define the inner linear system as(4)I−αRz=g.Then, applying the inner iteration, we can get(5)zs+1=αRzs+g,s=0,1,2,…,l−1,where we take z0=zk as the initial value and assign zl as new xk+1. Moreover, the parameters η and ϵ are the tolerances of the inner and outer iterations, respectively:(6)c−I−Rxk+12<ϵ,g−I−αRzs+12<η.Then, the inner-outer iterative algorithm is given in Algorithm1.Algorithm 1: KThe inner-outer iterative algorithm [22].
(i)
InputR,c,α,ϵ,ηOutput:xStep 1:x⟵cStep 2:z⟵RxStep 3: whilec−x+x2≥ϵStep 4:g⟵1−αz+cStep 5: repeatStep 6:x⟵g+αzStep 7:z⟵RxStep 8: untilg+αz−x2<ηStep 9: end whileStep 10:x⟵z+c


## 3. Main Results

In Algorithm1, the authors discussed the convergence of the inner-outer iterative algorithm and studied the convergence of the iterations (3) and (5), respectively.Lemma 1 (see [12]).
The iterative sequencexm+1=Rxm+c converges to the corresponding solution of Ax=b for all starting vectors x0 and for all b if and only if (iff) ρR<1.Theorem 1 (see [22]).
LetρR<1 and 0<α<1; then, the outer iteration (3) is convergent, where ρR denotes the spectral radius of matrix A.Theorem 2 (see [22]).
LetρR<1 and 0<α<1; then, the inner iteration (5) is convergent, where ρR denotes the spectral radius of matrix A.Remark 1.
Through careful analysis of the proving process of Theorems1 and 2, we found that the convergence parameter α may actually be weaker and weaker. In addition, parameter α can be adjusted suitably so that the convergence of this method could be improved obviously. Thus, we may get the following convergence results.
Through further analysis, the outer iteration (3) is associated with the matrix splitting:(7)I−R=M1−N1,M1=I−αR,N1=1−αR,and the corresponding outer iteration matrix is(8)R1=M1−1N1=1−αI−αR−1R.
The inner iteration for (4) has the following splitting:(9)M1=I−αR=M2−N2,M2=I,N2=αR,and the inner iteration matrix is(10)R2=αR.Theorem 3.
LetρR<1 and 0<α<1+ρ/2ρ; then, the outer iteration (3) is convergent, where ρ=ρR denotes the spectral radius of matrix A.Proof.
Letλi be an eigenvalue of R. Then, λi≤ρR<1 from the assumption. Assume that μi is an eigenvalue of R1 in (8); then,(11)μi=1−αλi1−αλi.Case 1.
When0<α≤1 and λi≤ρR<1:(12)μi=1−αλi1−αλi≤1−αρ1−αρ<1.Case 2.
When1<α<1+ρ/2ρ and λi≤ρR<1:(13)μi=1−αλi1−αλi=α−1λi1−αλi.
Since1<α<1+ρ/2ρ, we may obtain(14)2αρ<1+ρ⟹αρ<1+ρ2<1⟹1−αρ>0,2αρ<1+ρ⟹αρ−ρ<1−αρ⟹αρ−ρ1−αρ<1.
So, we can immediately get(15)μi=1−αλi1−αλi=α−1λi1−αλi≤α−1ρ1−αρ<1.
From Lemma1 and equations (12) and (15), the outer iteration (3) is convergent.Remark 2.
SinceρR<1, then(16)1+ρ2ρ>1.
So, our new convergent domain about parameterα in Theorem 3 is wider than that in Theorem 1 [22].Theorem 4.
LetρR<1 and 0<α<1/ρ; then, the inner iteration (5) is convergent, where ρ=ρR denotes the spectral radius of matrix A.Proof.
Letϕi be an eigenvalue of R2 in (10); then,(17)ϕi=αλi,where λi is an eigenvalue of R. Then, from (17), we can get(18)ϕi=αλi≤αρ<1.
From Lemma1 and equation (18), we complete the proof.Remark 3.
SinceρR<1, then(19)1ρ>1.
So, the new convergent domain about parameterα in Theorem 4 is wider than that in Theorem 2 [22].
Next, the authors gave the overall convergence for the inner-outer iterative algorithm without considering the parametersϵ and η, which shows that the inner-outer iterative algorithm converges linearly to the exact solution x∗ of linear system (2).Lemma 2 (see [12]).
For all operator norms,ρR≤r. For all R and for all ϵ>0, there is an operator norm R∗≤ρR+ϵ. The norm •∗ depends on both R and ϵ, where ρC denotes the spectral radius of matrix C.Lemma 3 (see [12]).
Assume• satisfies AB≤A⋅B. Then, X<1 implies that I−X is invertible, I−X−1=∑i=0∞Xi, and I−X−1≤1/1−X.Now, we rewrite the inner-outer iterative algorithm as a two-stage iteration framework [21, 22]:(20)xk,0=xk,x0=c,xk+1=xk,mk,xk,j+1=αRxk,j+1−αRxk+c,k=0,1,2,…,j=0,1,2,…,mk−1.Theorem 5 (see [22]).
LetA=M−N be a convergence splitting, 0<α<1, and mk be the number of inner iteration steps at the k-th outer iteration. Then, the iteration sequence xkk=0∞ generated by (20) converges to the exact solution x∗ of (2), faster than the iteration sequence derived from (2) for the same initial value x0.Through careful analysis, we found that the iteration sequencexkk=0∞ generated by (20) still converges to the exact solution x∗ of (2) when α>1. So, by similar proving process, we can get the following convergence theorem.Theorem 6.
AssumeA=M−N to be a convergence splitting, 0<α<2/1+ρ, and mk be the number of the inner iteration steps at the k-th outer iteration. Then, the iteration sequence xkk=0∞ generated by (20) converges to the exact solution x∗ of (2), faster than the iteration sequence derived from (2) for the same initial value x0.Proof.
From equation (20), we can obtain(21)xk,j+1=αRj+1+1−α∑s=0jαRsRxk+∑s=0jαRsc.
Then, we can get(22)xk+1=Hkxk+Ekc,k=0,1,2,…,where Hk=αRmk+1−α∑s=0mk−1αRsR and Ek=∑s=0mk−1αRs. Since x∗ is the exact solution of (1), then from (22), we have(23)x∗=Hkx∗+Ekc,k=0,1,2,…
Subtracting equation (23) from equation (22), we can get(24)xk+1−x∗=Hkxk−x∗=⋯=HkHk−1⋯H0x0−x∗,k=0,1,2,…,(25)Hk=αRmk+1−α∑s=0mk−1αRsR=αRmk−∑s=0mk−1αRsI−R−1−αR=αRmk+I−αRmk−∑s=0mk−1αRsI−R=I−∑s=0mk−1αRsI−R.
Letλi be an eigenvalue of R; then, from equation (25), we can obtain that(26)ϕik=1−1−λi1−αλimk1−αλi,is an eigenvalue of Hk.(27)ϕik=1−1−λi1−αλimk1−αλi=λi1−α+αmkλimk−1−αλimk1−αλi<1−α+αλimk−11−λiα1−αλi=1−α1−αλi,as mk⟶∞.Case 3.
When0<α≤1 and λi≤ρR<1: from equation (27), we have(28)ϕik<1−α1−αλi<1−α1−αλi<1.Case 4.
When1<α<2/1+ρ and λi≤ρR<1: since 1<α<2/1+ρ, we can obtain(29)1<α<21+ρ⟹α<21+ρ<1ρ⟹αρ<1,1<α<21+ρ⟹αρ+α<2⟹α−1<1−αρ⟹α−11−αρ<1.
So, from equation (27), we can immediately get(30)ϕik<1−α1−αλi<α−11−αρ<1.
Then, we can obtainρHk<1. Next, from the proving process of Theorem 5, we can get ρHk<ρR for k=0,1,2,⋯.Remark 4.
SinceρR<1, then(31)21+ρ>1.
Consequently, our new convergent domain of the parameterα in Theorem 6 is wider than the convergent domain in Theorem 5 [22].


## 4. Conclusions

In this paper, based on the convergence of the inner-outer iteration, we obtain more applicable convergence results. Furthermore, our new convergent domain of the parameterα is wider than that in [22]. Therefore, the convergence property of the method can be substantially improved due to the suitable adjustability of the parameters we adopted[34, 35].



---

*Source: 1832589-2020-07-06.xml*