# Refinement of Multiparameters Overrelaxation (RMPOR) Method

Authors: Gashaye Dessalew; Tesfaye Kebede; Gurju Awgichew; Assaye Walelign
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this paper, we present refinement of multiparameters overrelaxation (RMPOR) method which is used to solve the linear system of equations. We investigate its convergence properties for different matrices such as strictly diagonally dominant matrix, symmetric positive definite matrix, and M-matrix. The proposed method minimizes the number of iterations as compared with the multiparameter overrelaxation method. Its spectral radius is also minimum. To show the efficiency of the proposed method, we prove some theorems and take some numerical examples.


---

## Body

## 1. Introduction

Large and sparse linear systems of the form(1)Ax=b,can be solved using iterative methods. One of the techniques of obtaining iterative methods is splitting the coefficient matrix. A=M−N and A=D−∑i=1kEi−F are some of the splitting of the matrix A. Using either of splittings, we can derive iterative methods which can solve the system of linear equation (1).Recently, many researchers used the splittingA=D−∑i=1kEi−F, where D is diagonal matrix of A, ∑i=1kEi is strictly lower triangular matrix of D−A, and F is strictly upper triangular matrix of D−A, to get the new iterative methods. Song and Dai [1] introduced multiparameters overrelaxation (MPOR) method, whose special cases involve many classical iterative methods. The convergence conditions with A being a Hermitian matrix, an L-matrix, an M-matrix, an H-matrix, and a strictly diagonally dominant matrix are derived. Kuang and Ji [2] presented a two-parameter iterative method called TOR method, which is effective to give the numerical solution of partial differential equations. Wang extended the TOR method to the GTOR method and improved some results of Ju, Wang, and Zeng. In [3], O’Leary and White proposed multisplitting methods which are based on several splittings of the matrix A. More precisely, a multisplitting of A is defined as a collection of triples Mk,Nk,Ek,k=1,2,…,K, such that for all k, Mk, Nk, and Ek are n×n matrices, each Mk is nonsingular, A=Mk−Nk, and Ek is a diagonal matrix with nonnegative entries satisfying ∑i=1kEk=I. The corresponding multisplitting method to solve (1) is given by the iteration xm+1=∑i=1kEkym,k, m=0,1,2,…, where Mkym,k=Nkxm+b, k=1,2,…,K. Similarly, the convergence of the parallel multisplitting TOR method is studied for M-matrix in [4]. Chang studied the convergence of the parallel multisplitting TOR method for H-matrices, but Zhang et al. [5] found some gaps in the proof of theorem.There are other many techniques to get new iterative methods such as extrapolation, overrelaxation, and acceleration. Up to now, a lot of first-order stationary iterative methods are proposed. They include the well-known methods as Jacobi, JOR, Gauss–Seidel, SOR, AOR, GAOR, TOR, and so on [1].Partial differential equations (PDEs) can be solved using finite difference and finite element methods. These two methods have deficiencies in accuracy and code implementation but there is novel efficient matrix approach for solving the second-order linear matrix partial differential equations (MPDEs) under given initial conditions which are proposed by Tohidi and Khorsand Zak [6]. Similarly, Asgari et al. [7] introduced an extended block Golub–Kahan algorithm for large algebraic and differential matrix Riccati equations by providing new theoretical analysis of the method and the norm of the residual.The remainder of this paper is organized as follows. In Section2, we first review some preliminaries which are used in our basic idea. In Section 3, the main result of this paper is presented. Convergence analysis of the proposed scheme is provided, and numerical examples are considered in this section. In Section 4, we provide a brief conclusion from our main results.


## 2. Preliminaries

The solution of equation (1) can be obtained using the following methods:(i)
SOR:xn+1=D−ωE−11−ωD+ωFxn+ωD−ωE−1b(ii)
AOR:xn+1=D−γ^E−11−ω^D+ω^−γ^E+ω^Fxn+ω^D−γ^E−1b(iii)
TOR:xn+1=D−a1E1−a2E2−11−ωD+ω−a1E1+ω−a2E2+ωFxn+ωD−a1E1−a2E2−1bIn [2], the lower part of A is split into two parts: E1 and E2. Also, E1 and E2 are multiplied different factors, and this a new scheme was introduced.(iv)
MPOR:xn+1=D−∑i=1kaiEi−11−ωD+∑i=1kω−aiEi+ωFxn+ωD−∑i=1kaiEi−1bDefinition 1.
The splittingA=M−N is called(1)
Regular ifM−1≥O and N≥O(2)
Weak regular ifM−1≥O and M−1N≥OTheorem 1.
LetA=M−N be a regular splitting of a matrix A. Then, ρM−1N<1 if and only if A is nonsingular and A−1 is nonnegative.Theorem 2.
LetA=M−N be a weak regular splitting of the matrix A. Then, A is nonsingular with A−1≥O if and only if ρM−1N<1.Definition 2.
The spectrum of a matrixA∈ℂ is defined by σA=λ∈ℂ:detA−λI=0. That is, the spectrum of a matrix A is the set of all its eigenvalues.Definition 3.
The spectral radius of a matrixA is denoted by ρA and is defined by ρA=maxλ∈σAλ.Definition 4.
The (asymptotic) rate of convergence ofA is denoted by R∞A and is defined by R∞A=−lnρA.Lemma 1 (see [8]).
La1,…,ak;ω=1−ωI+ωI−∑i=1kaiLi−1∑i=1k1−aiLi+U, where Li=D−1Ei, i=1,2,…,k, and U=D−1F.Theorem 3 (see [8]).
Let0,…,0;0≤a1,…,ak;ω≤1,…,1;1 and ω≠0. Let BJ=∑i=1kLi+U. Then,(1)
1−ω≤ρLa1,…,ak;ω<1 if and only if ρBJ<1; in this case, we have ρLa1,…,ak;ω≤1−ω+ωρBJ. Furthermore, if ρBJ=0, then ρLa1,…,ak;ω=1−ω.(2)
ρLa1,…,ak;ω=1 if and only if ρBJ=1.(3)
ρLa1,…,ak;ω>1 if and only if ρBJ>1; in this case, we have ρLa1,…,ak;ω≤1−ω+ωρBJ.Theorem 4 (see [9]).
LetA=D−E−ET be an n×n Hermitian positive definite matrix, where D is the Hermitian and positive definite and E is strictly lower part of D−A. Then, the eigenvalues μi, where i=1,2,…,n, and the Jacobi matrix BJ=D−1E+ET=I−D−1A≡L0,1 are real and less than 1. Moreover, if μm=miniμi and μM=maxiμi and μm≤0≤μM, then for the values(2)ω∈0,2,ω+2−ωμm<γ<ω+2−ωμM,provided that detD−γE≠0, and the AOR method converges.Theorem 5 (see [2]).
LetA=D−E1−E2−F be an H-matrix, then the TOR method converges for 0≤a1<ω<2/1+ρBJ and 0≤a2<ω<2/1+ρBJ, where BJ=La1,a2,ω=L0,0,1.


## 3. Main Results

LetAx=b be given with A is any nonsingular square matrix. Then, split A as A=D−∑i=1kEi−F, where D is the diagonal matrix, Ei is any strictly lower triangular matrix of D−A for i=1,2,…,k, and F is strictly upper triangular matrix of D−A. Then, ωA=ωD−∑i=1kωEi−ωF.(3)ωAx=ωbD−∑i=1kaiEi−1−ωD+∑i=1kω−aiEi+ωFx=ωbD−∑i=1kaiEix=1−ωD+∑i=1kω−aiEi+ωFx+ωb=D−∑i=1kaiEi−ωAx+ωb=D−∑i=1kaiEix+ωb−Axx=x+ωD−∑i=1kaiEi−1b−Ax,(4)xn+1=x˜n+1+ωD−∑i=1kaiEi−1b−Ax˜n+1.After some steps, one can get the following:(5)xn+1=D−∑i=1kaiEi−11−ωD+∑i=1kω−aiEi+ωFx˜n+1+ωD−∑i=1kaiEi−1b.Equation (5) is called refiner for the multiparameter overrelaxation (MPOR) method. To get the RMPOR method, first we should substitute the MPOR method into equation (5) or equation (4) and then simplify and rearrange, and the results will be(6)xn+1=D−∑i=1kaiEi−11−ωD+∑i=1kω−aiEi+ωF2xn+ωI+D−∑i=1kaiEi−11−ωD+∑i=1kω−aiEi+ωFD−∑i=1kaiEi−1b.Equation (6) is the refinement of multiparameter overrelaxation (RMPOR) iterative method.Equation (6) can also be written as(7)xn+1=Lai,ω2xn+I+Lai,ωCai,ω,where Lai,ω=D−∑i=1kaiEi−11−ωD+∑i=1kω−aiEi+ωF and Cai,ω=ωD−∑i=1kaiEi−1b.For a specificω and ai, i=1,2,…,k, the RMPOR method reduces to(i)
Refinement of Jacobi (RJ) ifa1=a2=a3=⋯=ak=0 and ω=1(ii)
Refinement of Gauss–Seidel (RGS) ifa1=a2=⋯=ak=1 and ω=1(iii)
Refinement of successive overrelaxation (RSOR) ifa1=a2=⋯=ak=ω and any ω(iv)
Refinement of Jacobi overrelaxation (RJOR) ifa1=a2=⋯=ak=0 and any ω(v)
Refinement of accelerating overrelaxation (RAOR) ifa1=a2=a3=⋯=ak=γ and any ω(vi)
Refinement of two-parameter overrelaxation (RTOR) ifa1, a2, and ω, and the remaining parameters a3=a4=⋯=ak=0, and so on


### 3.1. Convergence of RMPOR Method

Theorem 6.
If A is the SDD matrix, then MPOR is convergent for0≤ai≤1 and 0<ω<1.Proof.
(8)Laiωx=λx1−ωD+∑i=1kω−aiEi+ωFx=λD−∑i=1kaiEix1−ωD+ω−a1E1+ω−a2E2+⋯+ω−akEk+ωFx=λD−a1E1−a2E2−⋯−akEkx1−ωD+ωE1+E2+⋯+Ek+λ−1a1E1+a2E2+⋯+akEk+ωFx=λDx1−ω−λDx+ωE+Fx=1−λa1E1+a2E2+⋯+akEkx1−ω−λaiixi−ω∑j=1,j≠inaijxj=1−λ∑i=1kaiai,jxi1−ω−λaiixi−ω∑j=1,j≠inaijxj≤1−λ∑j=1,j≠ikaiai,jxi1−ω−λ1−λ≤∑j=1,j≠ikaiai,jaii+ω1−λ∑j=1,j≠inaijaii<∑j=1,j≠ikaiai,jaii+ω1−λ1−ω−λ−ω1−λ<∑j=1,j≠ikaiai,jaii<1,for 0≤ai≤1. Thus,(9)1−ω−λ−ω1−λ<1.
According to Theorem3, ρLai,ω<1 since A is SDD for which ρB<1 or let D−1Ei=lkji, D−1F=ukj, lki=∑j=1k−1lkji, and uk=∑j=k+1nlkjukj. If A is strictly diagonally dominant, then we have BJ∞<1 and ∑i=1kailki<1, and we obtain(10)ρLai,ω≤max1−ω+∑i=1kω−ailki+ωuk1−∑i=1kailki.
Ifω≤1, inequality (10) reduces to(11)ρLai,ω≤max1−ω+∑i=1kω−ailki+ωuk1−∑i=1kailki≤max1−ω+ωBJ∞−∑i=1kailki1−∑i=1kailki<1.
Ifω>1, then inequality (10) reduces to(12)ρLai,ω≤maxω−1+∑i=1kai−ωlki+ωuk1−∑i=1kailki≤maxω−1+ωBJ∞−∑i=1kailki1−∑i=1kailki<1.
Hence, the MPOR method is convergent. ForLω,a having real eigenvalue, the method is also convergent for 1−ω<λ<1−1/2ω. Hence, the optimal value is 1−1/2ω.Theorem 7.
If A is symmetric and positive definite (SPD) andD−∑i=1kaiEi is nonsingular, then the MPOR method is convergent.Proof.
(13)Lai,ωx=λx1−ωD+∑i=1kω−aiEi+ωFx=λD−∑i=1kaiEixxT1−ωD+∑i=1kω−aiEi+ωFx=λxTD−∑i=1kaiEixxTD−ωD+ωE1+E2+⋯+Ek−a1E1+a2E2+⋯+akEk+ωFx=λxTD−∑i=1kaiEixxTD−∑i=1kaiEix−ωxTD−E−Fx=λxTD−∑i=1kaiEixωxTAx=1−λxTD−∑i=1kaiEix.
We now suffice to show that the spectral radius ofG satisfies ρG<1. Let λ be an eigenvalue of G, and let x be an eigenvector corresponding to λ.(14)G=D−∑i=1kaiEi−11−ωD+∑i=1kω−aiEi+ωF=D−∑i=1kaiEi−1D−∑i=1kaiEi−ωA,(15)=I−B−1A,where B=1/ωD−1/ω∑i=1kaiEi.
From the above, we have(16)B−1A=I−G,A−1B=I−G−1.
From equation (22), we obtain(17)G=I−B−1ABG=B−ABI+G=2B−AA−1BI+G=A−12B−AI−G−1I+Gx=μxI+Gx=μI−Gx.
If the eigenvalues ofG are λ,(18)1+λ=μ1−λ,μ=1+λ1−λ,λ=μ−1μ+1,λ2=λλ¯=μ2+1−Reμμ2+1+Reμ.
Thus, we haveλ<1 since Reμ>0. Therefore, the MPOR method is convergent.Theorem 8.
IfA is an M-matrix and 0≤ai≤ω<1, then the MPOR iterative method is convergent.Proof.
In the MPOR iterative method, we haveA=D−∑i=1kEi−F or A=M−N where M=1/ωD−∑i=1kaiEi and N=1−ω/ωD+∑i=1kω−ai/ωEi+F. From this, we have A≤M. Therefore, M is an M-matrix and as a result M−1≥O. On the other hand, for 0<ai<1, we have ρ∑i=1kaiD−1Ei<1, and therefore,(19)M−1N=D−∑i=1kaiEi−11−ωD+∑i=1kω−aiEi+ωF=I−∑i=1kaiD−1Ei−11−ωI+∑i=1kω−aiD−1Ei+ωD−1F=∑j=0∞∑ikaiD−1Eij1−ωI+∑i=1kω−aiD−1Ei+ωD−1F≥0.
For0≤ai≤ω<1.
Hence, we conclude that isA a weak regular splitting.
Thus, using Theorem2, we conclude that ρM−1N<1. This completes the proof.Theorem 9.
LetA be strictly diagonally dominant and BJ=D−1∑i=1kEi+F=∑i=1kLi+U=I−D−1A. Then, for(20)0≤ai≤ω<21+BJ∞,ω≠0,the RMPOR method converges.Proof.
Assume0≤ai≤ω and Lai,ω=D−∑i=1kaiEi−11−ωD+∑i=1kω−aiEi+ωF2. It is known that BJ∞<1 since A is SDD matrix.
Then,(21)Lai,ωx=λxD−∑i=1kaiEi−11−ωD+∑i=1kω−aiEi+ωFx=λ1/2x1−ωD+∑i=1kω−aiEi+ωFx=λ1/2D−∑i=1kaiEix1−ωI+∑i=1kω−aiLi+ωUx=λ1/2I−∑i=1kaiLixλ1/2∑i=1kaiLi+ω∑i=1kLi−∑i=1kaiLi+ωUx=λ1/2+ω−1xλ1/2∑i=1kaiLi−∑i=1kaiLi+ωBJx=λ1/2+ω−1x.
Taking norms on both sides, we get(22)λ1/2+ω−1x∞≤λ1/2−1∑i=1kaiLi∞+ωBJ∞x∞.
Thus,(23)λ1/2+ω−1≤λ1/2−1∑i=1kaiLi∞+ωBJ∞.
Using inequalities,(24)λ1/2−1−ω≤λ1/2−1∑i=1kaiLi∞+ωBJ∞,λ1/2−1∑i=1kaiLi∞≤ω1+BJ∞,0<λ1/2−11−∑i=1kaiLi∞<ω1+BJ∞<2.
From the fact that∑i=1kaiLi∞<1 and λ<1,λ1/2−1<1. Therefore,(25)ω<21+BJ∞.
Hence, we prove the theorem.Theorem 10.
IfA is symmetric and positive definite (SPD) and detD−∑i=1kaiLi≠0, then the refinement of multiparameter overrelaxation (RMPOR) method is convergent for any initial guess x0.Proof.
Let us begin with(26)Lai,ωx=λx,(27)1−ωD+∑i=1kω−aiEi+ωFx=λD−∑i=1kaiEix,(28)λ+ω−1Dx+1−λ∑i=1kaiEix=ω∑i=1kEi+Fx,(29)λ+ω−1Ix+1−λ∑i=1kaiLix=ω∑i=1kLi+Ux.
However, we know that the eigenvalues of the Jacobi matrixBJ is μ. Thus,(30)BJx=μx,D−1∑i=1kEi+Fx=μx,∑i=1kLi+Ux=μx,(31)ω∑i=1kLi+Ux=ωμx.
Using equations (29) and (31), we get(32)λ+ω−1Ix+1−λ∑i=1kaiLix=ωμx,(33)λ+ω−1−ωμx=λ−1∑i=1kaiLix.
From equation (33), we have the following two cases:(1)
Ifx∗∑i=1kaiEix>0, then λ+ω−1−ωμ/λ−1>0. Again, from this, we have two cases:(i)
λ−1>0 and λ+ω−1−ωμ>0. Thus, λ>1 and λ+ω−1−ωμ>0 which is impossible according to convergent property.(ii)
λ−1<0 and λ+ω−1−ωμ<0. In this case, we get λ<1 and ω<1−λ/1−μ.On the other hand,(2)
Ifx∗∑i=1kaiEix<0, then λ+ω−1−ωμ/λ−1<0. Again, from this we, have two cases:(i)
λ−1<0 and λ+ω−1−ωμ>0. In this case, we have λ<1 and ω<1−λ/1−μ.(ii)
λ−1>0 and λ+ω−1−ωμ<0 which is impossible.
Thus, we must choose the second possibility, which isx∗∑i=1kaiEix<0.
Therefore, we can conclude that(34)x∗D−∑i=1kaiEix>0.
Now, let us start to proof the theorem, using equation (27).(35)1−ωD+∑i=1kω−aiEi+ωFx=λD−∑i=1kaiEixλ+ω−1Dx+1−λ∑i=1kaiEix=ω∑i=1kEi+Fx1−λDx+λ−1∑i=1kaiEix=ωD−∑i=1kEi−Fx1−λD−∑i=1kaiEix=ωAx1−λωx∗D−∑i=1kaiEix=x∗Ax.
Using equation (34) and SPD property of the matrix A, we have x∗D−∑i=1kaiEi>0 and x∗Ax>0. Hence, 1−λ>0. Thus,(36)λ<1.
Therefore, the MPOR method is convergent.
Now, let us prove the convergence of the RMPOR iterative method.(37)Lai,ω2x=Λx,(38)Lai,ωx=Λ1/2x,where Λ is the eigenvalue of Lai,ω2. From equation (38), we have λ=Λ1/2 or λ2=Λ.
From this, we can generalize that the RMPOR method is convergent if A is SPD matrix.Theorem 11.
LetA be an M-matrix. If(39)0≤ai≤ω<21+ρBJ,and then ρLai,ω2<1. That is, the RMPOR iterative method is convergent.Proof.
For the case whenω≤1, the statement is proved. Now, we consider the case when ω>1. We assume ρLai,ω>1 and denote(40)Lai,ω=D−∑i=1kaiEi−11−ωD+∑i=1kω−aiEi+ωF2.
By direct comparision, it gets. Hence, there exists a nonzero vectorx≥0 such that(41)Lai,ωx=ρLai,ωx1+ρLai,ω1/2−ωx=∑i=1kω−ai+aiρLai,ω1/2Li+Ux≤maxω+ρLai,ω1/2−1aiBJx.
Thus,(42)1+ρLai,ω1/2−ω≤maxω+ρLai,ω1/2−1aiρBJ≤ωρLai,ω1/2ρBJ,and consequently,(43)ω≥1+ρLai,ω1/21+ρLai,ω1/2ρBJ≥21+ρBJ.
Obviously, it contradicts the hypothesis; therefore, we haveρLai,ω≤ρLai,ω<1.


### 3.2. Numerical Examples

Example 1.
Let us solve the system of linear equations of the form Ax =b using SOR, AOR, TOR, MPOR, and RMPOR iterative methods, where(44)A=8−10−100010100−18−10−101010100−1800−1010001−1008−101000100−10−18−101010100−10−180010100101008−10−100101010−18−10−100100010−1800−1100010−1008−100101010−10−18−100101000−10−18,b=9−921189132333−13−18719,E1=0000000000000000000000000000000000001000000000000100000000000010000000000−10−100000000−10−10−100000000−1000−10000000000−10100000000−10−10100000000−10001000,E2=000000000000100000000000010000000000000000000000000100000000000010000000000000000000000000100000000000010000−1000000000000−1000000010000−1000000010,E3=000000000000100000000000010000000000000000000000000100000000000010000000000000000000000000100000000000010000000000000000000000000100000000000010,E4=000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000−1000000000000−1000000000000−1000000000,with a1=0.5, a2=0.6, a3=0.4, and ω=0.9. E=E1+E2=E1+E3+E4. To use the MPOR and RMPOR method, we used the splitting E=E1+E3+E4, and to apply the TOR method, we used the splitting E=E1+E2. The exact solution is x¯=1;−1;2;2;1;2;3;4;−1;−2;1;2. The spectral radius of Lai,ω is ρLai,ω=0.5731 and ρLai,ω2=0.3284 which means that RMPOR is faster than the MPOR iterative method.
From Table1, the RMPOR method converges to the exact solution faster than the MPOR method. The spectral radius is also smaller than the MPOR method. Similarly, rate of convergence of the RMPOR is larger than that of MPOR method. Hence, the proposed is better than MPOR method.Table 1
Comparison of SOR, AOR, TOR, MPOR, and RMPOR methods for Example1.
MethodsNumber of iterationsSpectral radiusRate of convergenceSORω0=1.112880.23341.4550AORω^=1andγ^=1.1128100.25561.3641TOR160.56910.5637MPOR170.57310.5567RMPOR90.32841.1135Example 2 (see [10]).
Consider the system of linear equations:(45)6x1+2x2+2x3=5,2x1+8x2+2x3=6,2x1+2x2+10x3=7.
The coefficient matrix is both SDD and SPD matrix. To solve the system with tolerance 0.0001 by using SOR, AOR, TOR, MPOR, and RMPOR iterative methods would be shown as follows:Solution is as follows:(46)A=6222822210,b=567,E1=000−200000,E2=000000−2−20,E3=000000−200,E4=0000000−20,with a1=0.4, a2=0.5, a3=0.6, and ω=0.9. We also used the splitting of E as E=E1+E2 for the TOR method and E=E1+E3+E4 for MPOR and RMPOR iterative methods.From Table2, the number of iteration of RMPOR is smaller than that of the MPOR method. The spectral radius of the RMPOR method is smaller than the spectral radius of the MPOR method. Similarly, rate of convergence of RMPOR is larger than that of the MPOR method. Hence, the proposed method is better than the MPOR method.Table 2
Comparison of SOR, AOR, TOR, MPOR, and RMPOR methods for Example2.
MethodsNumber of iterationsSpectral radiusRate of convergenceSORω0=1.0160.12432.0851AORω^=1.01andγ^=0.950.13641.9922TOR80.31431.1574MPOR80.31381.1590RMPOR40.09852.3177


## 3.1. Convergence of RMPOR Method

Theorem 6.
If A is the SDD matrix, then MPOR is convergent for0≤ai≤1 and 0<ω<1.Proof.
(8)Laiωx=λx1−ωD+∑i=1kω−aiEi+ωFx=λD−∑i=1kaiEix1−ωD+ω−a1E1+ω−a2E2+⋯+ω−akEk+ωFx=λD−a1E1−a2E2−⋯−akEkx1−ωD+ωE1+E2+⋯+Ek+λ−1a1E1+a2E2+⋯+akEk+ωFx=λDx1−ω−λDx+ωE+Fx=1−λa1E1+a2E2+⋯+akEkx1−ω−λaiixi−ω∑j=1,j≠inaijxj=1−λ∑i=1kaiai,jxi1−ω−λaiixi−ω∑j=1,j≠inaijxj≤1−λ∑j=1,j≠ikaiai,jxi1−ω−λ1−λ≤∑j=1,j≠ikaiai,jaii+ω1−λ∑j=1,j≠inaijaii<∑j=1,j≠ikaiai,jaii+ω1−λ1−ω−λ−ω1−λ<∑j=1,j≠ikaiai,jaii<1,for 0≤ai≤1. Thus,(9)1−ω−λ−ω1−λ<1.
According to Theorem3, ρLai,ω<1 since A is SDD for which ρB<1 or let D−1Ei=lkji, D−1F=ukj, lki=∑j=1k−1lkji, and uk=∑j=k+1nlkjukj. If A is strictly diagonally dominant, then we have BJ∞<1 and ∑i=1kailki<1, and we obtain(10)ρLai,ω≤max1−ω+∑i=1kω−ailki+ωuk1−∑i=1kailki.
Ifω≤1, inequality (10) reduces to(11)ρLai,ω≤max1−ω+∑i=1kω−ailki+ωuk1−∑i=1kailki≤max1−ω+ωBJ∞−∑i=1kailki1−∑i=1kailki<1.
Ifω>1, then inequality (10) reduces to(12)ρLai,ω≤maxω−1+∑i=1kai−ωlki+ωuk1−∑i=1kailki≤maxω−1+ωBJ∞−∑i=1kailki1−∑i=1kailki<1.
Hence, the MPOR method is convergent. ForLω,a having real eigenvalue, the method is also convergent for 1−ω<λ<1−1/2ω. Hence, the optimal value is 1−1/2ω.Theorem 7.
If A is symmetric and positive definite (SPD) andD−∑i=1kaiEi is nonsingular, then the MPOR method is convergent.Proof.
(13)Lai,ωx=λx1−ωD+∑i=1kω−aiEi+ωFx=λD−∑i=1kaiEixxT1−ωD+∑i=1kω−aiEi+ωFx=λxTD−∑i=1kaiEixxTD−ωD+ωE1+E2+⋯+Ek−a1E1+a2E2+⋯+akEk+ωFx=λxTD−∑i=1kaiEixxTD−∑i=1kaiEix−ωxTD−E−Fx=λxTD−∑i=1kaiEixωxTAx=1−λxTD−∑i=1kaiEix.
We now suffice to show that the spectral radius ofG satisfies ρG<1. Let λ be an eigenvalue of G, and let x be an eigenvector corresponding to λ.(14)G=D−∑i=1kaiEi−11−ωD+∑i=1kω−aiEi+ωF=D−∑i=1kaiEi−1D−∑i=1kaiEi−ωA,(15)=I−B−1A,where B=1/ωD−1/ω∑i=1kaiEi.
From the above, we have(16)B−1A=I−G,A−1B=I−G−1.
From equation (22), we obtain(17)G=I−B−1ABG=B−ABI+G=2B−AA−1BI+G=A−12B−AI−G−1I+Gx=μxI+Gx=μI−Gx.
If the eigenvalues ofG are λ,(18)1+λ=μ1−λ,μ=1+λ1−λ,λ=μ−1μ+1,λ2=λλ¯=μ2+1−Reμμ2+1+Reμ.
Thus, we haveλ<1 since Reμ>0. Therefore, the MPOR method is convergent.Theorem 8.
IfA is an M-matrix and 0≤ai≤ω<1, then the MPOR iterative method is convergent.Proof.
In the MPOR iterative method, we haveA=D−∑i=1kEi−F or A=M−N where M=1/ωD−∑i=1kaiEi and N=1−ω/ωD+∑i=1kω−ai/ωEi+F. From this, we have A≤M. Therefore, M is an M-matrix and as a result M−1≥O. On the other hand, for 0<ai<1, we have ρ∑i=1kaiD−1Ei<1, and therefore,(19)M−1N=D−∑i=1kaiEi−11−ωD+∑i=1kω−aiEi+ωF=I−∑i=1kaiD−1Ei−11−ωI+∑i=1kω−aiD−1Ei+ωD−1F=∑j=0∞∑ikaiD−1Eij1−ωI+∑i=1kω−aiD−1Ei+ωD−1F≥0.
For0≤ai≤ω<1.
Hence, we conclude that isA a weak regular splitting.
Thus, using Theorem2, we conclude that ρM−1N<1. This completes the proof.Theorem 9.
LetA be strictly diagonally dominant and BJ=D−1∑i=1kEi+F=∑i=1kLi+U=I−D−1A. Then, for(20)0≤ai≤ω<21+BJ∞,ω≠0,the RMPOR method converges.Proof.
Assume0≤ai≤ω and Lai,ω=D−∑i=1kaiEi−11−ωD+∑i=1kω−aiEi+ωF2. It is known that BJ∞<1 since A is SDD matrix.
Then,(21)Lai,ωx=λxD−∑i=1kaiEi−11−ωD+∑i=1kω−aiEi+ωFx=λ1/2x1−ωD+∑i=1kω−aiEi+ωFx=λ1/2D−∑i=1kaiEix1−ωI+∑i=1kω−aiLi+ωUx=λ1/2I−∑i=1kaiLixλ1/2∑i=1kaiLi+ω∑i=1kLi−∑i=1kaiLi+ωUx=λ1/2+ω−1xλ1/2∑i=1kaiLi−∑i=1kaiLi+ωBJx=λ1/2+ω−1x.
Taking norms on both sides, we get(22)λ1/2+ω−1x∞≤λ1/2−1∑i=1kaiLi∞+ωBJ∞x∞.
Thus,(23)λ1/2+ω−1≤λ1/2−1∑i=1kaiLi∞+ωBJ∞.
Using inequalities,(24)λ1/2−1−ω≤λ1/2−1∑i=1kaiLi∞+ωBJ∞,λ1/2−1∑i=1kaiLi∞≤ω1+BJ∞,0<λ1/2−11−∑i=1kaiLi∞<ω1+BJ∞<2.
From the fact that∑i=1kaiLi∞<1 and λ<1,λ1/2−1<1. Therefore,(25)ω<21+BJ∞.
Hence, we prove the theorem.Theorem 10.
IfA is symmetric and positive definite (SPD) and detD−∑i=1kaiLi≠0, then the refinement of multiparameter overrelaxation (RMPOR) method is convergent for any initial guess x0.Proof.
Let us begin with(26)Lai,ωx=λx,(27)1−ωD+∑i=1kω−aiEi+ωFx=λD−∑i=1kaiEix,(28)λ+ω−1Dx+1−λ∑i=1kaiEix=ω∑i=1kEi+Fx,(29)λ+ω−1Ix+1−λ∑i=1kaiLix=ω∑i=1kLi+Ux.
However, we know that the eigenvalues of the Jacobi matrixBJ is μ. Thus,(30)BJx=μx,D−1∑i=1kEi+Fx=μx,∑i=1kLi+Ux=μx,(31)ω∑i=1kLi+Ux=ωμx.
Using equations (29) and (31), we get(32)λ+ω−1Ix+1−λ∑i=1kaiLix=ωμx,(33)λ+ω−1−ωμx=λ−1∑i=1kaiLix.
From equation (33), we have the following two cases:(1)
Ifx∗∑i=1kaiEix>0, then λ+ω−1−ωμ/λ−1>0. Again, from this, we have two cases:(i)
λ−1>0 and λ+ω−1−ωμ>0. Thus, λ>1 and λ+ω−1−ωμ>0 which is impossible according to convergent property.(ii)
λ−1<0 and λ+ω−1−ωμ<0. In this case, we get λ<1 and ω<1−λ/1−μ.On the other hand,(2)
Ifx∗∑i=1kaiEix<0, then λ+ω−1−ωμ/λ−1<0. Again, from this we, have two cases:(i)
λ−1<0 and λ+ω−1−ωμ>0. In this case, we have λ<1 and ω<1−λ/1−μ.(ii)
λ−1>0 and λ+ω−1−ωμ<0 which is impossible.
Thus, we must choose the second possibility, which isx∗∑i=1kaiEix<0.
Therefore, we can conclude that(34)x∗D−∑i=1kaiEix>0.
Now, let us start to proof the theorem, using equation (27).(35)1−ωD+∑i=1kω−aiEi+ωFx=λD−∑i=1kaiEixλ+ω−1Dx+1−λ∑i=1kaiEix=ω∑i=1kEi+Fx1−λDx+λ−1∑i=1kaiEix=ωD−∑i=1kEi−Fx1−λD−∑i=1kaiEix=ωAx1−λωx∗D−∑i=1kaiEix=x∗Ax.
Using equation (34) and SPD property of the matrix A, we have x∗D−∑i=1kaiEi>0 and x∗Ax>0. Hence, 1−λ>0. Thus,(36)λ<1.
Therefore, the MPOR method is convergent.
Now, let us prove the convergence of the RMPOR iterative method.(37)Lai,ω2x=Λx,(38)Lai,ωx=Λ1/2x,where Λ is the eigenvalue of Lai,ω2. From equation (38), we have λ=Λ1/2 or λ2=Λ.
From this, we can generalize that the RMPOR method is convergent if A is SPD matrix.Theorem 11.
LetA be an M-matrix. If(39)0≤ai≤ω<21+ρBJ,and then ρLai,ω2<1. That is, the RMPOR iterative method is convergent.Proof.
For the case whenω≤1, the statement is proved. Now, we consider the case when ω>1. We assume ρLai,ω>1 and denote(40)Lai,ω=D−∑i=1kaiEi−11−ωD+∑i=1kω−aiEi+ωF2.
By direct comparision, it gets. Hence, there exists a nonzero vectorx≥0 such that(41)Lai,ωx=ρLai,ωx1+ρLai,ω1/2−ωx=∑i=1kω−ai+aiρLai,ω1/2Li+Ux≤maxω+ρLai,ω1/2−1aiBJx.
Thus,(42)1+ρLai,ω1/2−ω≤maxω+ρLai,ω1/2−1aiρBJ≤ωρLai,ω1/2ρBJ,and consequently,(43)ω≥1+ρLai,ω1/21+ρLai,ω1/2ρBJ≥21+ρBJ.
Obviously, it contradicts the hypothesis; therefore, we haveρLai,ω≤ρLai,ω<1.


## 3.2. Numerical Examples

Example 1.
Let us solve the system of linear equations of the form Ax =b using SOR, AOR, TOR, MPOR, and RMPOR iterative methods, where(44)A=8−10−100010100−18−10−101010100−1800−1010001−1008−101000100−10−18−101010100−10−180010100101008−10−100101010−18−10−100100010−1800−1100010−1008−100101010−10−18−100101000−10−18,b=9−921189132333−13−18719,E1=0000000000000000000000000000000000001000000000000100000000000010000000000−10−100000000−10−10−100000000−1000−10000000000−10100000000−10−10100000000−10001000,E2=000000000000100000000000010000000000000000000000000100000000000010000000000000000000000000100000000000010000−1000000000000−1000000010000−1000000010,E3=000000000000100000000000010000000000000000000000000100000000000010000000000000000000000000100000000000010000000000000000000000000100000000000010,E4=000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000−1000000000000−1000000000000−1000000000,with a1=0.5, a2=0.6, a3=0.4, and ω=0.9. E=E1+E2=E1+E3+E4. To use the MPOR and RMPOR method, we used the splitting E=E1+E3+E4, and to apply the TOR method, we used the splitting E=E1+E2. The exact solution is x¯=1;−1;2;2;1;2;3;4;−1;−2;1;2. The spectral radius of Lai,ω is ρLai,ω=0.5731 and ρLai,ω2=0.3284 which means that RMPOR is faster than the MPOR iterative method.
From Table1, the RMPOR method converges to the exact solution faster than the MPOR method. The spectral radius is also smaller than the MPOR method. Similarly, rate of convergence of the RMPOR is larger than that of MPOR method. Hence, the proposed is better than MPOR method.Table 1
Comparison of SOR, AOR, TOR, MPOR, and RMPOR methods for Example1.
MethodsNumber of iterationsSpectral radiusRate of convergenceSORω0=1.112880.23341.4550AORω^=1andγ^=1.1128100.25561.3641TOR160.56910.5637MPOR170.57310.5567RMPOR90.32841.1135Example 2 (see [10]).
Consider the system of linear equations:(45)6x1+2x2+2x3=5,2x1+8x2+2x3=6,2x1+2x2+10x3=7.
The coefficient matrix is both SDD and SPD matrix. To solve the system with tolerance 0.0001 by using SOR, AOR, TOR, MPOR, and RMPOR iterative methods would be shown as follows:Solution is as follows:(46)A=6222822210,b=567,E1=000−200000,E2=000000−2−20,E3=000000−200,E4=0000000−20,with a1=0.4, a2=0.5, a3=0.6, and ω=0.9. We also used the splitting of E as E=E1+E2 for the TOR method and E=E1+E3+E4 for MPOR and RMPOR iterative methods.From Table2, the number of iteration of RMPOR is smaller than that of the MPOR method. The spectral radius of the RMPOR method is smaller than the spectral radius of the MPOR method. Similarly, rate of convergence of RMPOR is larger than that of the MPOR method. Hence, the proposed method is better than the MPOR method.Table 2
Comparison of SOR, AOR, TOR, MPOR, and RMPOR methods for Example2.
MethodsNumber of iterationsSpectral radiusRate of convergenceSORω0=1.0160.12432.0851AORω^=1.01andγ^=0.950.13641.9922TOR80.31431.1574MPOR80.31381.1590RMPOR40.09852.3177


## 4. Conclusion

Iterative methods are very essential to solve large and sparse linear system of equations which arise from the discretization of PDE and ODE problems. The iterative methods can be found by splitting the coefficient matrix. There are many techniques to split the matrixA. One of them is multiparameter splitting technique which is discussed in this paper. The method obtained by this technique is efficient to solve system of linear equations whose coefficient matrices are SDD, SPD, and M-matrices, and then the RMPOR iterative method is better than the MPOR iterative method.



---

*Source: 2804698-2021-08-23.xml*