# Convergence Results on Iteration Algorithms to Linear Systems

Authors: Zhuande Wang; Chuansheng Yang; Yubo Yuan
Journal: The Scientific World Journal
 (2014)

---

## Abstract

In order to solve the large scale linear systems, backward and Jacobi iteration algorithms are employed. The convergence is the most important issue. In this paper, a unified backward iterative matrix is proposed. It shows that some well-known iterative algorithms can be deduced with it. The most important result is that the convergence results have been proved. Firstly, the spectral radius of the Jacobi iterative matrix is positive and the one of backward iterative matrix is strongly positive (lager than a positive constant). Secondly, the mentioned two iterations have the same convergence results (convergence or divergence simultaneously). Finally, some numerical experiments show that the proposed algorithms are correct and have the merit of backward methods.


---

## Body

## 1. Introduction

The primal goal of this paper is to study the iterative methods of the linear systems:(1)Ax=b,
where A is a given n×n complex or real matrix.It is well known that linear systems arise in studies in many areas such as engineering and industrial science. For example, in the field of numerical solutions of differential-algebraic equations (DAE) and ordinary differential equations (ODE) [1–3] it is very important to solve (1). In digital image and signal processing, especially in compressed sensing, Stojnic [4] has mentioned that the systems (1) are the mathematical background of compressed sensing problems and studied sharp lower bounds on the values of allowable sparsity for any given number (proportional to the length of the unknown vector) of equations for the case of the so-called block-sparse unknown vectors. In the blind source separation of signal, Congedo et al. [5] have showed that it is very important to solve (1) and proposed a special method with joint singular value decomposition. In the field of biomedical engineering, Deo et al. [6] have mentioned that the cardiac electrical activity can be described by the bidomain equations and pointed out that the numerical solution of partial differential equations (PDEs) associated with bidomain problems often leads to (1). Moreover, they have proposed a novel preconditioner for the PCG method to solve (1) and a cheap iterative method such as successive overrelaxation (SOR) to further refine the solution for a desired accuracy. In 2008, Shou et al. [7] have showed that the reconstruction of epicardial potentials (EPs) from body surface potentials (BSPs) can be characterized as an ill-posed inverse problem and geometric errors in the ECG inverse problem will directly affect the calculation of transfer matrix A in (1). In the field of systems and control science, Ding and Chen [8] have pointed out that Sylvester equations in systems and control especially Lyapunov equations in continuous- and discrete-time stability analysis can be converted into equivalent equations as (1). In the field of machine learning many problems of classification and regression, such as single-hidden layer neural networks [9, 10], support vector machines, functional neural networks, and so on, can be summarized as (1). Therefore, the solution of (1) is very important in scientific computing.The methods to solve linear systems can be roughly divided into two categories: direct methods and iterative methods 1. Iterative methods are more suitable than direct methods for large linear systems [11, 12]. The current research on iterative algorithms has been more mature, but how to make it fit the new architecture model is complicated. In order to gain more good performance, acceleration has been applied and architecture has been considered [13].In this paper, we do some research with the iterative algorithm. To this end, the paper is organized as follows. In Section2, we introduce the backward MPSD (backward modified preconditioned simultaneous displacement) iterative method which is a unified form of some important backward iterations. In Section 3, we first introduce some important lemmas which will be used and then we obtained the convergence results between backward MPSD iteration and Jacobi iteration. We also proposed convergence results between some backward iterations and Jacobi iteration in the corollaries. In Section 4, some examples and numerical experiments have been done to make sure of the correctness of results. Especially, we point out that the backward iteration is better than the original one in many cases just like Example 4.


## 2. A Unified Framework of Iteration Matrix and Algorithm

The basic idea to solve (1) is matrix splitting. If we let
(2)A=D-CL-CU,L=D-1CL,U=D-1CU,
where D=diag⁡(A) is a diagonal matrix obtained from A and nonsingular and CL and CU are strictly lower and upper triangular matrices obtained from A, (1) becomes the equivalent one:
(3)(I-L-U)x=D-1b.
At this moment, D-1A=(I-L-U).The Jacobi iterative matrix is(4)B=L+U=I-D-1A.
The MPSD (modified preconditioned simultaneous displacement) iterative method is studied in [14–17].Ifτ>0 is a real constant, obviously (3) is equivalent to
(5)τ(I-L-U)x=τD-1b.At the same time, ifω1,ω2 are real constants, we can obtain the following equivalent from (5):
(6)(I-ω1U-ω2L+ω1ω2UL)x=(I-ω1U-ω2L+ω1ω2UL)x+(-τI+τL+τU)x+τD-1b.It is easy to verify that(7)(I-ω1U)(I-ω2L)x=[(1-τ)I+(τ-ω1)U+(τ-ω2)L+ω1ω2UL]x+τD-1b.With (7), we can construct the backward MPSD iterative method as follows:
(8)x(k+1)=S~τ,ω1,ω2x(k)+(I-ω2L)-1(I-ω1U)-1τD-1b,
where
(9)S~τ,ω1,ω2=(I-ω2L)-1(I-ω1U)-1×[(1-τ)I+(τ-ω1)U+(τ-ω2)L+ω1ω2UL],
which we named as backward MPSD iterative matrix.Also, we have the following algorithm.Backward MPSD AlgorithmStep  0 (Input). Matrix A, vector b, τ>0, ω1, ω2, algorithm stop cutoff ϵ.Step  1 (Initialization). Compute D=diag⁡(A), CL, CU, L=D-1CL,U=D-1CU,x(0)=0, and set i≔0.Step  2. Compute matrix S~τ,ω1,ω2 according to (9).Step  3. Compute x(i+1) with (8).Step  4. If ∥x(i+1)-x(i)∥22⩽ϵ, then stop and accept x(i) as the solution of (1); else i:=i+1; go to step 3.Remark 1.
With special values ofω1,ω2, and τ, we have the following.(1)
Whenω1=0, ω2=0, and τ=1, we obtain the Jacobi iterative method.(2)
Whenω1=0, ω2=0, and τ=ω, we obtain the backward JOR iterative method.(3)
Whenω1=1, ω2=0, and τ=1, we obtain the backward G-S iterative method.(4)
Whenω1=ω, ω2=0, and τ=ω, we obtain the backward SOR iterative method.(5)
Whenω1=ω, ω2=0, and τ=α, we obtain the backward AOR iterative method.(6)
Whenω1=ω, ω2=ω, and τ=ω(2-ω), we obtain the backward SSOR iterative method.(7)
Whenω1=ω, ω2=ω, and τ=ω, we obtain the backward EMA iterative method.(8)
Whenω1=ω, ω2=ω, and τ=α, we obtain the backward PSD iterative method.(9)
Whenω1=ω, ω2=ω, and τ=1, we obtain the backward PJ iterative method.The convergence relationship between the Gauss-Seidel iterative matrix and the Jacobi iterative matrix is studied in [12], and the generalized results are studied in [18]. Some eigenvalue relationships between other iterative matrices and Jacobi iterative matrix are studied with the p-cyclic case in [19–26]. Some backward iterations are studied in [27]. In the following we consider the convergence results between the backward MPSD iterative matrix and the Jacobi iterative matrix and obtain convergence relationships between some other backward iterative matrices and Jacobi matrix.


## 3. Convergence Results

In order to obtain the convergence results, we give some well-known results which will be used in the proof of Theorem7 as follows.Definition 2 (see [13]).
The splittingA=M-N with A and M nonsingular is called a regular splitting if M-1≥0 and N≥0. It is called a weak regular splitting if M-1≥0 and M-1N≥0.
It is obvious that a regular splitting is a weak regular splitting.Lemma 3 (see [13]).
The nonnegative matrixT∈Rn×n is convergent; that is, ρ(T)<1 if and only if (I-T)-1 exists and (I-T)-1=∑k=1∞‍Tk≥0.Lemma 4 (see [13]).
LetA=M-N be a weak regular splitting of A, H=M-1N. Then the following statements are equivalent.(1)
A-1≥0; that is, A is inverse-positive.(2)
A-1N≥0.(3)
ρ(H)=ρ(A-1N)/(1+ρ(A-1N)) so that ρ(H)<1.Lemma 5 (see [12]).
LetA≥0 be an irreducible n×n matrix. Then(1)
A has a positive real eigenvalue equal to its spectral radius;(2)
toρ(A), there corresponds an eigenvector x>0,(3)
ρ(A) increases when any entry of A increases,(4)
ρ(A) is a simple eigenvalue of A.Lemma 6 (see [12]).
LetA=(aij)≥0 be an irreducible n×n matrix. Then for any x>0, either
(10)min⁡1≤i≤n∑j=1naijxjxi<ρ(A)<max⁡1≤i≤n∑j=1naijxjxi
or
(11)∑j=1naijxjxi=ρ(A)∀i.By the lemmas above, we give the convergence theorem in the following.Theorem 7.
Let the coefficient matrixA of (1) be irreducible with aii≠0,∀i, B=U+L≥0 the Jacobi matrix, and S~τ,ω1,ω2 the backward MPSD iterative matrix. Then, for 0≤ωk<τ≤1, k=1,2, we have the following.(1)
ρ(B)>0, ρ(S~τ,ω1,ω2)>1-τ.(2)
One and only one of the following mutually exclusive relations is valid.
(i)
0<ρ(B)<1⇔1-τ<ρ(S~τ,ω1,ω2)<1.(ii)
ρ(B)=1⇔ρ(S~τ,ω1,ω2)=1.(iii)
ρ(B)>1⇔ρ(S~τ,ω1,ω2)>1.Thus, The Jacobi iterative method and the backward MPSD iterative method are either both convergent or both divergent.Proof.
Combiningρ(ω2L)=ρ(ω1U)=0 with Lemma 3, we have (I-ω2L)-1≥0,(I-ω1U)-1≥0, and
(12)S~τ,ω1,ω2=(I-ω2L)-1(I-ω1U)-1×[(1-τ)I+(τ-ω1)U+(τ-ω2)L+ω1ω2UL]=(I+ω2L+ω22L2+⋯)×(I+ω1U+ω12U2+⋯)×[(1-τ)I+(τ-ω1)U+(τ-ω2)L+ω1ω2UL]≥(1-τ)I+(τ-ω1)U+(τ-ω2)L.
Sinceaii≠0 and A is irreducible, I-L-U=D-1A and B=L+U are irreducible. By 0≤ωk<τ≤1,k=1,2, we have (1-τ)I+(τ-ω1)U+(τ-ω2)L≥0 and irreducible. Thus, by (12), S~τ,ω1,ω2≥0 and is irreducible. By Lemma 5, there exists λ=ρ(S~τ,ω1,ω2)>0 and corresponding vector x=(x1,x2,…,xn)T>0, such that S~τ,ω1,ω2x=λx; namely,
(13)[(1-τ)I+(τ-ω1)U+(τ-ω2)L+ω1ω2UL]x=λ(I-ω1U)(I-ω2L)x.
Let ηk=τ-ωk+λωk,k=1,2; by calculation,
(14)η1Ux+η2Lx+(1-λ)ω1ω2ULx=[λ-(1-τ)]x;
that is,
(15)η1Ux+η2Lx=(λ-1)ω1ω2ULx+[λ-(1-τ)]x.
(
1
) Since B≥0 is irreducible, by Lemma 5, ρ(B)>0. If ρ(S~τ,ω1,ω2)≥1, by 0≤ωk<τ≤1,k=1,2, ρ(S~τ,ω1,ω2)≥1>1-τ. If ρ(S~τ,ω1,ω2)<1, then λ-(1-τ)≥0 because the left side of (14) is nonnegative, Thus λ≥1-τ. By (14),
(16)η1Ux+η2Lx≤[λ-(1-τ)]x.
If λ=1-τ, by (16), we have η1Ux+η2Lx≤0; that is,
(17)η1∑j=i+1n‍bijxj+η2∑j=1i-1‍bijxj≤0,∀i.
Sinceηk>0,k=1,2,B=(bij)≥0 and x>0, we obtain that B=0. Thus, ρ(B)=0. This contradicts ρ(B)>0. So, ρ(S~τ,ω1,ω2)>1-τ.
(
2
) For mutually exclusive relations, consider the following.
(i) If0<ρ(B)<1, let
(18)M=(I-ω1U)(I-ω2L),N=[(1-τ)I+(τ-ω1)U+(τ-ω2)L+ω1ω2UL],
and then
(19)S~τ,ω1,ω2=M-1N.
SinceM-1=(I-ω2L)-1(I-ω1U)-1≥0 and N≥0, T=M-N is a regular splitting:
(20)T=M-N=τI-τ(U+L)=τ(I-(U+L))=τ(I-B).
ByB≥0,0<ρ(B)<1, and 0<τ≤1, we know that T-1=(1/τ)(I-B)-1≥0. By Lemma 4, ρ(S~τ,ω1,ω2)=ρ(M-1N)<1. Combine this with the result in (1), we have 1-τ<ρ(S~τ,ω1,ω2)<1.
If1-τ<λ=ρ(S~τ,ω1,ω2)<1, by (14), we have
(21)η1Ux+η2Lx≤[λ-(1-τ)]x.
Since ηk>0,k=1,2,bii=0,∀i,
(22)min⁡k=1,2ηk(∑j=1n‍bijxj)≤η1∑j=i+1n‍bijxj+η2∑j=1i-1‍bijxj≤[λ-(1-τ)]xi,∀i;
that is,
(23)∑j=1nbijxjxi≤λ-(1-τ)min⁡k=1,2ηk,∀i.
Byλ<1 and 1-ωk>0(k=1,2), there is
(24)λ(1-ωk)<1-ωk,λ-1<-ωk+λωk,0<λ-(1-τ)=λ-1+τ<ηk.
Thus,
(25)0<λ-(1-τ)ηk<1,k=1,2.
Combining (23) with (29), we have
(26)∑j=1nbijxjxi<1,∀i.
By Lemma 6, we obtain that 0<ρ(B)<1.
(ii) Ifλ=ρ(S~τ,ω1,ω2)=1, by (14), we have
(27)τ(U+L)x=[1-(1-τ)]x=τx;
namely, Bx=x. Since x>0, we have
(28)∑j=1nbijxjxi=1,∀i.
By Lemma 6, we obtain that ρ(B)=1.
(iii) Ifλ=ρ(S~τ,ω1,ω2)>1, by (15), we have
(29)η1Ux+η2Lx≥[λ-(1-τ)]x.
Since ηk>0,k=1,2,bii=0,∀i,
(30)max⁡k=1,2ηk(∑j=1n‍bijxj)≥η1∑j=i+1n‍bijxj+η2∑j=1i-1‍bijxj≥[λ-(1-τ)]xi,∀i;
that is,
(31)∑j=1nbijxjxi≥λ-(1-τ)max⁡k=1,2ηk,∀i.
Byλ>1 and 1-ωk>0(k=1,2), there is
(32)λ(1-ωk)>1-ωk,λ-1>-ωk+λωk,λ-(1-τ)=λ-1+τ>ηk>0.
Thus,
(33)λ-(1-τ)ηk>1,k=1,2.
Combining (31) with (33), we have
(34)∑j=1nbijxjxi>1,∀i.
By Lemma 6, we obtain that ρ(B)>1.
Ifρ(B)=1 and ρ(S~τ,ω1,ω2)≠1, by (1), we obtain that 1-τ<λ=ρ(S~τ,ω1,ω2)<1 or ρ(S~τ,ω1,ω2)>1. Thus, by (i) and (iii), we know that 0<ρ(B)<1 or ρ(B)>1. This contradicts ρ(B)=1. So, ρ(S~τ,ω1,ω2)=1.
Ifρ(B)>1 and ρ(S~τ,ω1,ω2)≤1, by (i) and (ii), we have ρ(B)≤1. This contradicts ρ(B)>1. So, ρ(S~τ,ω1,ω2)>1.With special values ofω1, ω2, and τ, we have the following corollaries.Corollary 8.
Let the coefficient matrixA of (1) be irreducible, B=U+L≥0 the Jacobi matrix, and S~ω,0,0 the backward JOR iterative matrix. Then, for 0≤ω≤1, we have the following.(1)
ρ(B)>0, ρ(S~ω,0,0)>1-ω.(2)
One and only one of the following mutually exclusive relations is valid.
(i)
0<ρ(B)<1⇔1-ω<ρ(S~ω,0,0)<1.(ii)
ρ(B)=1⇔ρ(S~ω,0,0)=1.(iii)
ρ(B)>1⇔ρ(S~ω,0,0)>1.Thus, The Jacobi iterative method and the backward JOR iterative method are either both convergent or both divergent.Corollary 9.
Let the coefficient matrixA of (1) be irreducible, B=U+L≥0 the Jacobi matrix, and S~1,1,0 the backward Gauss-Seidel iterative matrix. Then, we have the following.
(1)
ρ
(
B
)
>
0, ρ(S~1,1,0)>0.
(2)
One and only one of the following mutually exclusive relations is valid.
(i)
0
<
ρ
(
B
)
<
1
⇔
0
<
ρ
(
S
~
1,1
,
0
)
<
1.
(ii)
ρ
(
B
)
=
1
⇔
ρ
(
S
~
1,1
,
0
)
=
1.
(iii)
ρ
(
B
)
>
1
⇔
ρ
(
S
~
1,1
,
0
)
>
1.Thus, The Jacobi iterative method and the backward Gauss-Seidel iterative method are either both convergent or both divergent.Corollary 10.
Let the coefficient matrixA of (1) be irreducible, B=U+L≥0 the Jacobi matrix, and S~ω,ω,0 the backward SOR iterative matrix. Then, for 0≤ω≤1, we have the following.
(1)
ρ
(
B
)
>
0, ρ(S~ω,,ω,0)>1-ω.
(2)
One and only one of the following mutually exclusive relations is valid.
(i)
0
<
ρ
(
B
)
<
1
⇔
1
-
ω
<
ρ
(
S
~
ω
,
,
ω
,
0
)
<
1.
(ii)
ρ
(
B
)
=
1
⇔
ρ
(
S
~
ω
,
ω
,
0
)
=
1.
(iii)
ρ
(
B
)
>
1
⇔
ρ
(
S
~
ω
,
ω
,
0
)
>
1.Thus, The Jacobi iterative method and the backward SOR iterative method are either both convergent or both divergent.Corollary 11.
Let the coefficient matrixA of (1) be irreducible, B=U+L≥0 the Jacobi matrix, and S~α,ω,0 the backward AOR iterative matrix. Then, for 0≤ω<α≤1, we have the following.(1)
ρ(B)>0, ρ(S~α,ω,0)>1-α.(2)
One and only one of the following mutually exclusive relations is valid.
(i)
0<ρ(B)<1⇔1-α<ρ(S~α,ω,0)<1.(ii)
ρ(B)=1⇔ρ(S~α,ω,0)=1.(iii)
ρ(B)>1⇔ρ(S~α,ω,0)>1.Thus, The Jacobi iterative method and the backward AOR iterative method are either both convergent or both divergent.Corollary 12.
Let the coefficient matrixA of (1) be irreducible, B=U+L≥0 the Jacobi matrix, and S~ω(2-ω),ω,ω the backward SSOR iterative matrix. Then, for 0≤ω≤1, we have the following.
(1)
ρ
(
B
)
>
0, ρ(S~ω(2-ω),ω,ω)>(1-ω)2.
(2)
One and only one of the following mutually exclusive relations is valid.
(i)
0
<
ρ
(
B
)
<
1
⇔
(
1
-
ω
)
2
<
ρ
(
S
~
ω
(
2
-
ω
)
,
ω
,
ω
)
<
1.
(ii)
ρ
(
B
)
=
1
⇔
ρ
(
S
~
ω
(
2
-
ω
)
,
ω
,
ω
)
=
1.
(iii)
ρ
(
B
)
>
1
⇔
ρ
(
S
~
ω
(
2
-
ω
)
,
ω
,
ω
)
>
1.Thus, The Jacobi iterative method and the backward SSOR iterative method are either both convergent or both divergent.Corollary 13.
Let the coefficient matrixA of (1) be irreducible, B=U+L≥0 the Jacobi matrix, and S~ω,ω,ω the backward EMA iterative matrix. Then, for 0≤ω≤1, we have the following.(1)
ρ(B)>0, ρ(S~ω,ω,ω)>(1-ω)2.(2)
One and only one of the following mutually exclusive relations is valid.
(i)
0<ρ(B)<1⇔(1-ω)2<ρ(S~ω,ω,ω)<1.(ii)
ρ(B)=1⇔ρ(S~ω,ω,ω)=1.(iii)
ρ(B)>1⇔ρ(S~ω,ω,ω)>1.Thus, The Jacobi iterative method and the backward EMA iterative method are either both convergent or both divergent.Corollary 14.
Let the coefficient matrixA of (1) be irreducible, B=U+L≥0 the Jacobi matrix, and S~α,ω,ω the backward PSD iterative matrix. Then, for 0≤ω<α≤1, we have the following.(1)
ρ(B)>0, ρ(S~α,ω,ω)>1-α.(2)
One and only one of the following mutually exclusive relations is valid.
(i)
0<ρ(B)<1⇔1-α<ρ(S~α,ω,0)<1.(ii)
ρ(B)=1⇔ρ(S~α,ω,ω)=1.(iii)
ρ(B)>1⇔ρ(S~α,ω,ω)>1.Thus, The Jacobi iterative method and the backward PSD iterative method are either both convergent or both divergent.Corollary 15.
Let the coefficient matrixA of (1) be irreducible, B=U+L≥0 the Jacobi matrix, and S~1,ω,ω the backward PJ iterative matrix. Then, for 0≤ω≤1, we have the following.(1)
ρ(B)>0, ρ(S~1,ω,ω)>0.(2)
One and only one of the following mutually exclusive relations is valid.
(i)
0<ρ(B)<1⇔0<ρ(S~1,ω,ω)<1.(ii)
ρ(B)=1⇔ρ(S~1,ω,ω)=1.(iii)
ρ(B)>1⇔ρ(S~1,ω,ω)>1.Thus, The Jacobi iterative method and the backward PJ iterative method are either both convergent or both divergent.Remark 16.
The convergence results between the backward MPSD and Jacobi iterative matrix are proposed, and The convergence results between some special cases of backward MPSD (such as backward JOR, backward G-S, backward EMA, and backward PSD) and Jacobi iterative matrix are obtained. These results involve some special iterative methods which are proposed in the references.


## 4. Numerical Examples

In this section, we show five examples. The first three examples are used to show the convergence of the proposed iterative methods. Example4 is used to show the divergence of the proposed iterative methods. Example 5 shows that the backward iterative methods are better than the origin methods when the upper triangular part dominates the lower triangular part. In the following figures, horizontal axis denotes the numbers of iterations and vertical axis denotes the errors of iterations.Example 1.
Let the coefficient matrixA and the vector b of (1) be
(35)A=[10-14-1401-14-14-14-1410-14-1401],b=[1111].
The Jacobi iterative matrix is(36)B=[001414001414141400141400].
By caculation, we obtain0<ρ(B)=1/2<1.(1)
Letτ=α=1/2, ω1=ω2=ω=1/4. We obtain the backward PSD iterative matrix S~α,ω,ω=S~1/2,1/4,1/4, and
(37)1>ρ(S~α,ω,ω)=ρ(S~1/2,1/4,1/4)=9671349>12=1-α.(2)
Letτ=1, ω1=ω2=ω=1/2. We obtain the backward PJ iterative matrix S~1,ω,ω=S~1,1/2,1/2, and
(38)1>ρ(S~1,ω,ω)=ρ(S~1,1/2,1/2)=250693>0=1-τ.(3)
Letτ=ω=1/2, ω1=ω2=0. We obtain the backward JOR iterative matrix S~ω,0,0=S~1/2,0,0, and
(39)1>ρ(S~ω,0,0)=ρ(S~1/2,0,0)=34>12=1-ω.(4)
Letτ=ω1=ω2=ω=1/2. We obtain the backward EMA iterative matrix S~ω,ω,ω=S~1/2,1/2,1/2, and
(40)1>ρ(S~ω,ω,ω)=ρ(S~1/2,1/2,1/2)=9431386>14=(1-ω)2. With these iterative methods and the presented algorithm, the solution is x=(2,2,2,2)T.Example 2.
In order to obtain the numerical solution of the laplace equation(41)∂2u(x,y)∂x2+∂2u(x,y)∂y2=uxx(x,y)+uyy(x,y)=0,
under a uniform square mesh of five-point difference approximations, and the interior mesh points as shown in Figure 1 [28], we can obtain the linear system (1), where the matrix A and the vector b of (1) are(42)A=[1000000-140-14-140100000-14000001000-14-14-14-140000100-14-1400000001000-14-140000001000-14-1400-14-140010000-14-14-14-14000100000-140-14000100-140-140-14-1400010-140000-1400001],b=[11111111111].
The Jacobi iterative matrix is(43)B=[000000014014140000000140000000001414141400000001414000000000001414000000000014-14001414001000014141414000000000140140001001401401414000001400001400000].
By caculation, we obtain 0<ρ(B)=1159/1601<1.(1)
Letτ=α=1/2, ω1=ω2=ω=1/4. We obtain the backward PSD iterative matrix S~α,ω,ω=S~1/2,1/4,1/4, and
(44)1>ρ(S~α,ω,ω)=ρ(S~1/2,1/4,1/4)=10611271>12=1-α.(2)
Letτ=1, ω1=ω2=ω=1/2. We obtain the backward PJ iterative matrix S~1,ω,ω=S~1,1/2,1/2, and
(45)1>ρ(S~1,ω,ω)=ρ(S~1,1/2,1/2)=13192168>0=1-τ.(3)
Letτ=ω=1/2, ω1=ω2=0. We obtain the backward JOR iterative matrix S~ω,0,0=S~1/2,0,0, and
(46)1>ρ(S~ω,0,0)=ρ(S~1/2,0,0)=13801601>12=1-ω.(4)
Letτ=ω1=ω2=ω=1/2. We obtain the backward EMA iterative matrix S~ω,ω,ω=S~1/2,1/2,1/2, and
(47)1>ρ(S~ω,ω,ω)=ρ(S~1/2,1/2,1/2)=36024479>14=(1-ω)2.
From Figures2, 3, 4, and 5, the errors of Jacobi iteration are denoted by blue circles and that of MPSD iteration is denoted by red stars. By the figures above, We know that Jacobi iteration is better than backward PSD, JOR, and EMA iteration and is worse than PJ iteration under the values of ω1, ω2, and τ in this example.Figure 1
Uniform square mesh of five-point difference.Figure 2
The errors of PSD and Jacobi iteration.Figure 3
The errors of PJ and Jacobi iteration.Figure 4
The errors of JOR and Jacobi iteration.Figure 5
The errors of EMA and Jacobi iteration.Example 3.
Let the coefficient matrixA of (1) be
(48)A=[1qrsq⋯s1qr⋱qqs⋱⋱⋱sr⋱⋱1qrs⋱qs1q⋯srqs1],
where q=-p/n, r=-p/(n+1), and s=-p/(n+2) [28]. Here, we let n=100 and p=1. By caculation, we obtain 0<ρ(B)=199/203<1.(1)
Letτ=α=1/2, ω1=ω2=ω=1/4. We obtain the backward PSD iterative matrix S~α,ω,ω=S~1/2,1/4,1/4, and
(49)1>ρ(S~α,ω,ω)=ρ(S~1/2,1/4,1/4)=233236>12=1-α.(2)
Letτ=1, ω1=ω2=ω=1/2. We obtain the backward PJ iterative matrix S~1,ω,ω=S~1,1/2,1/2, and
(50)1>ρ(S~1,ω,ω)=ρ(S~1,1/2,1/2)=724749>0=1-τ.(3)
Letτ=ω=1/2, ω1=ω2=0. We obtain the backward JOR iterative matrix S~ω,0,0=S~1/2,0,0, and
(51)1>ρ(S~ω,0,0)=ρ(S~1/2,0,0)=199203>12=1-ω.(4)
Letτ=ω1=ω2=ω=1/2. We obtain the backward EMA iterative matrix S~ω,ω,ω=S~1/2,1/2,1/2, and
(52)1>ρ(S~ω,ω,ω)=ρ(S~1/2,1/2,1/2)=766779>14=(1-ω)2.Example 4.
Let the coefficient matrixA and the vector b of (1) be
(53)A=[1-2-2-11-1-2-21],b=[212].
The Jacobi iterative matrix is
(54)B=[022101220].
By caculation, we obtain ρ(B)=987/305>1.(1)
Letτ=α=1/2, ω1=ω2=ω=1/4. We obtain the backward PSD iterative matrix S~α,ω,ω=S~1/2,1/4,1/4, and
(55)ρ(S~α,ω,ω)=ρ(S~1/2,1/4,1/4)=36631052>1.(2)
Letτ=1, ω1=ω2=ω=1/2. We obtain the backward PJ iterative matrix S~1,ω,ω=S~1,1/2,1/2, and
(56)ρ(S~1,ω,ω)=ρ(S~1,1/2,1/2)=2543247>1.(3)
Letτ=ω=1/2, ω1=ω2=0. We obtain the backward JOR iterative matrix S~ω,0,0=S~1/2,0,0, and
(57)ρ(S~ω,0,0)=ρ(S~1/2,0,0)=646305>1.(4)
Letτ=ω1=ω2=ω=1/2. We obtain the backward EMA iterative matrix S~ω,ω,ω=S~1/2,1/2,1/2, and
(58)ρ(S~ω,ω,ω)=ρ(S~1/2,1/2,1/2)=1530271>1. It shows that the backward MPSD iteration is invalid for this example.Example 5.
Let the coefficient matrixA of (1) be(59)A=[10-2-2-2-2-2-2-2-2-2-110-2-2-2-2-2-2-2-2-1-111-2-2-2-2-2-2-2-1-1-112-2-2-2-2-2-2-1-1-1-113-2-2-2-2-2-1-1-1-1-114-2-2-2-2-1-1-1-1-1-115-2-2-2-1-1-1-1-1-1-116-2-2-1-1-1-1-1-1-1-117-2-1-1-1-1-1-1-1-1-118].
We can see the analogous matrixA in [29]. By caculation, we obtain ρ(B)=811/822<1.Letτ=1, ω1=1,ω2=0. We obtain the backward Gauss-Seidel iterative matrix S~1,ω1,ω2=S~1,1,0, and
(60)ρ(S~1,ω1,ω2)=ρ(S~1,1,0)=766789.
The Gauss-Seidel iterative matrix S1,ω1,ω2=S~1,1,0=(I-L)-1U, and
(61)ρ(S1,ω1,ω2)=ρ(S1,1,0)=721739.
Thus,
(62)ρ(S~1,1,0)<ρ(S1,1,0).From Figure6, the red stars denote the error of backward Guass-Seidel iteration and the blue circles denote that of Guass-Seidel. So, the backward iterative methods are better than the original methods under the assumption that the upper triangular part dominates the lower triangular part.Figure 6
The errors of backward Guass-Seidel and Guass-Seidel iteration.


## 5. Conclusions

The Jacobi iteration is the basic iteration for linear systems and easier to the analysis of the convergence than other iterations. In the paper, we proposed the backward MPSD iteration and obtained the convergence result between backward MPSD iteration (including iterations such as backward JOR, backward G-S, backward EMA, and backward PSD) and Jacobi iteration. We pointed out that the backward MPSD iteration and the Jacobi iteration are either both convergent or both divergent under the assumptions in Theorem7. So, we can ascertain the convergence or divergence of backward MPSD iteration by Jacobi iteration. In some case, the backward iteration is better than the original one.



---

*Source: 273873-2014-05-13.xml*