# Generalized Refinement of Gauss-Seidel Method for Consistently Ordered 2-Cyclic Matrices

Authors: Gashaye Dessalew; Tesfaye Kebede; Gurju Awgichew; Assaye Walelign
Journal: Abstract and Applied Analysis
 (2021)

---

## Abstract

This paper presents generalized refinement of Gauss-Seidel method of solving system of linear equations by considering consistently ordered 2-cyclic matrices. Consistently ordered 2-cyclic matrices are obtained while finite difference method is applied to solve differential equation. Suitable theorems are introduced to verify the convergence of this proposed method. To observe the effectiveness of this method, few numerical examples are given. The study points out that, using the generalized refinement of Gauss-Seidel method, we obtain a solution of a problem with a minimum number of iteration and obtain a greater rate of convergence than other previous methods.


---

## Body

## 1. Introduction

Consider the problem of large and sparse linear systems of the form(1)Ax=b,where A=aij is a nonsingular real matrix of order n, b is a given n-dimensional real vector, and x is an n-dimensional vector to be determined. By splitting A into A=D−L−U, where D is a diagonal matrix with aii≠0, −L is strictly lower, and −U is strictly an upper triangular part of A, different iterative methods were developed. In recent years, research results show that generalized, refinement, and extrapolation (acceleration or relaxation) are used for modifying the Gauss-Seidel method. Salkuyeh [1] introduced the generalized Gauss-Seidel (GGS) method and discussed the convergence of the method by considering strictly diagonally dominant (SDD) and M-matrices. The refinement of the Gauss-Seidel (RGS) method was studied by Vatti and Eneyew [2] and proved the convergence of the method by taking SDD matrices. Recently, Enyew et al. [3] developed a second refinement of the Gauss-Seidel method on SDD, symmetric positive definite (SPD), and M-matrices. All the above researchers tried to minimize the number of iterations and improved the rate of convergence. But still, different researchers have been conducting research in the area of iterative methods. In line with this, in this paper, we study the generalized refinement of Gauss-Seidel (GRGS) iterative method which is used to accelerate the convergence of the basic Gauss-Seidel method. Here, for the GRGS method, we mean thekth-RGS method, wherek=0,1,2,3,⋯.


## 2. Preliminaries

Some of the basic iterative methods are given below.The Jacobi (J) iterative method is(2)xn+1=D−1L+Uxn+D−1b.The Gauss-Seidel (GS) iterative method is(3)xn+1=D−L−1Uxn+D−L−1b,and the successive overrelaxation (SOR) iterative method is(4)xn+1=D−ωL−11−ωD+ωUxn+D−ωL−1ωb,where 0<ω<2. Equations (2), (3), and (4) can be denoted by xn+1=GJxn+kJ, xn+1=GGSxn+kGS, and xn+1=GSORxn+kSOR, where GJ=D−1L+U, kJ=D−1b, GGS=D−L−1U, kGS=D−L−1b, GSOR=D−ωL−11−ωD+ωU, and kSOR=D−ωL−1ωb, respectively.Definition 1.
The spectrum of a matrixA∈ℂis defined byσA=λ∈ℂ:detA−λI=0.That is, the spectrum of a matrixAis the set of all its eigenvalues.Definition 2.
The spectral radius of a matrixAis denoted byρAand is defined byρA=maxλ∈σA∣λ∣.Definition 3.
The (asymptotic) rate of convergence ofAis denoted byR∞Aand is defined byR∞A=−logρA.Definition 4 ([4]).
A matrixA∈ℂn,nis said to be consistently ordered two-cyclic ifσD−1αL+1/αUis independent ofα∈ℂ\0.Theorem 5 ([5]).
LetAbe consistently ordered and 2-cyclic with nonvanishing diagonal elements, and letGJ=I−diagA−1A=D−1L+U.Then,(a)
ifμ is any eigenvalue of GJ of multiplicity p, then −μ is also an eigenvalue of GJ of multiplicity p(b)
λ satisfies(5)λ+ω−12=ω2μ2λ,for some eigenvalue μ of GJ if and only if λ satisfies λ+ω−1=ωμλ1/2 for some eigenvalue μ of GJ.Theorem 6 ([6]).
LetAbe consistently ordered and 2-cyclic with nonzero diagonal elements. Then,(6)ρGGS=ρGJ2.Theorem 7 ([6]).
For consistently ordered 2-cyclic matrices, if the Jacobi method converges, so does the Gauss-Seidel method, and the Gauss-Seidel method converges twice as fast as the Jacobi method.
We used the following algorithms for nonstationary methods like conjugate gradient (CG), biconjugate gradient (BiCG), and minimal residual (MINRES) methods:(a)
Algorithm for the conjugate gradient (CG) method
Givenx0, find r0=b−Ax0 and set v1=r0. Fork=1,2,3,⋯, until convergence, do(7)tk=rk−1,rk−1vk,Avk,xk=xk−1+tkvk,rk=rk−1−tkAvk,sk=rk,rkrk−1,rk−1,vk+1=rk+skvk.(b)
Algorithm for the biconjugate gradient (BiCG) method
Choose initial guessx0. Then, find r0=b−Ax0 for r0,r0∗≠0 and set p0=r0 and p0∗=r0∗. For j=0,1,2,3,⋯, do(8)αj=rj,rj∗Apj,pj∗,xj+1=xj+αjpj,rj+1=rj−αjApj,rj+1∗=rj∗−αjApj∗,βj=rj+1,rj+1∗rj,rj∗,pj+1=rj+1+βjpj,pj+1∗=rj+1∗+βjpj∗.(c)
Minimal residual (MINRES) method
Choose initial guessx0, then find r0=b−Ax0 and α0=Ar0,r0/Ar0,Ar0. For k=0,1,2,3,⋯, do(9)xk+1=xk+αkrk,rk+1=b−Axk+1,αk+1=Ark+1,rk+1Ark+1,Ark+1.


## 3. Main Result

The refinement of Gauss-Seidel (RGS) and second refinement of Gauss-Seidel (SRGS) methods are a modification of the Gauss-Seidel method. Using a system of linear equations in the form (1), we can derive the refinement of Gauss-Seidel (RGS) method as the following procedures: D−L−Ux=b. By adding Ux to both sides, we get D−Lx=Ux+b.This could be written asD−Lx=D−L−Ax+b, where U=D−L−A.After arranging and multiplying both sides byD−L−1, we get x=x+D−L−1b−Ax. Thus,(10)xn+1=x~n+1+D−L−1b−Ax~n+1or(11)xn+1=D−L−1Ux~n+1+D−L−1b.Equations (10) or (11) are refiner of the Gauss-Seidel method. By taking either of the above equations (10) or (11), substitute Gauss-Seidel scheme (3) in the place of x~n+1 to get the refinement of Gauss-Seidel method. Thus, we can derive the generalized refinement of Gauss-Seidel method:(12)xn+1=D−L−1Uk+1xn+∑m=0kD−L−1UmD−L−1b.Equation (12) is called the generalized refinement of Gauss-Seidel (GRGS) method or the kth-refinement of Gauss-Seidel (kth-RGS) method. Equation (12) can be denoted by either xn+1=GGRGSxn+kGRGS or xn+1=GGSk+1xn+kGRGS, where kGRGS=∑m=0kD−L−1UmD−L−1b.Ifk=0, the scheme is reduced to the Gauss-Seidel method.Ifk=1, the method is reduced to the refinement of Gauss-Seidel method.Ifk=2, the scheme is reduced to the second refinement of Gauss-Seidel method and so on.


### 3.1. Algorithm for GRGS Method

(1)
DecomposeA as A=D−L−U, where D−L is nonsingular and U is nonzero matrices; initial approximation x0; tolerance TOL; maximum number of iterations N.(2)
Choosek=0,1,2,3,⋯Forn=0,1,2,⋯, until convergence.Doxn+1=D−L−1Uk+1xn+∑m=0kD−L−1UmD−L−1b.IfN=1 or 2, then stop.


### 3.2. Convergence of Generalized Refinement of Gauss-Seidel Method

Theorem 8.
IfAis consistently ordered 2-cyclic matrices, thenρGGRGS=ρGGSk+1=ρGJ2k+1.The Gauss-Seidel method converges if and only if the generalized refinement of Gauss-Seidel method converges, and the GRGS method converges(k+1)times as fast as Gauss-Seidel method and2k+1times as fast as the Jacobi method.Proof.
LetA be consistently ordered matrix with nonvanishing diagonal elements and 2-cyclic matrix. Then, by Theorem 6, we have ρGGS=ρGJ2. This implies that the Gauss-Seidel method converges twice as fast as the Jacobi method. Hence, based on Theorem 7, the Jacobi method is convergent if and only if the Gauss-Seidel method is convergent. Similarly, if GS converges, then RGS, SRGS, 3th-RGS, …, and GRGS methods converge.(13)ρGRGS=ρGGS2=ρGJ4.
Again,(14)ρGSRGS=ρGRGS3/2=ρGGS3=ρGJ6,ρG3rd−RGS=ρGSRGS4/3=ρGRGS2=ρGGS4=ρGJ8,ρG4th−RGS=ρG3rd−RGS5/4=ρGSRGS5/3=ρGRGS5/2=ρGGS5=ρGJ10,ρG5th−RGS=ρG4th−RGS6/5=ρG3rd−RGS3/2=ρGSRGS2=ρGRGS3=ρGGS6=ρGJ12,and so on. Thus, the spectral radius of the GRGS method is as follows:(15)ρGkth−RGS=ρGk−1th−RGSk+1/k=ρGk−2th−RGSk+1/k−1=ρGk−3th−RGSk+1/k−2=⋯=ρGSRGSk+1/3=ρGRGSk+1/2=ρGGSk+1=ρGJ2k+1.
Therefore, the GRGS method converges (k+1) times as fast as the Gauss-Seidel method and 2k+1 times as fast as the Jacobi method.
Here, one can deduce that the number of iterations of the GRGS method denoted bynGGRGS is(16)nGGRGS=nGkth−RGS≈kk+1nGk−1th−RGS≈k−1k+1nGk−2th−RGS≈⋯≈2k+1nGRGS≈1k+1nGGS≈12k+1nGJ.
Similarly, the rate of convergence of GRGS is denoted byR∞GGRGS such that(17)R∞GGRGS=R∞Gkth−RGS=k+1kR∞Gk−1th−RGS=k+1k−1R∞Gk−2th−RGS=⋯=k+13R∞GSRGS=k+12R∞GRGS=k+1R∞GGS=2k+1R∞GJ.☐Theorem 9.
The generalized refinement of Gauss-Seidel method converges faster than the Gauss-Seidel method and refinement of Gauss-Seidel method when the Gauss-Seidel method is convergent.Proof.
We can rewrite equation (3), RGS, SRGS, and (12), respectively, by xn+1=GGSxn+kGS, xn+1=GGS2xn+B, xn+1=GGS3xn+C, and xn+1=GGSk+1xn+E, where GGS=D−L−1U, kGS=D−L−1b, B=I+D−L−1UD−L−1b, C=I+D−L−1UD−L−1U2D−L−1b, and E=I+D−L−1U+D−L−1U2+⋯+D−L−1Uk, given that∥GGS∥<1. Let X be the exact solution of (1). That is, X=GGSX+kGS, X=GGS2X+B, X=GGS3X+C, and X=GGSk+1X+E. Let n=0,1,2,.. be nonnegative integers.☐If we consider the Gauss-Seidel method,(18)xn+1=GGSxn+kGS,(19)xn+1−X=GGSxn−X+kGS=GGSxn−GGSX−kGS+kGS,(20)∥xn+1−X∥=∥GGSxn−X∥,(21)∥xn+1−X∥≤∥GGS∥∥xn−X∥≤∥GGS2∥∥xn−2−X∥≤∥GGS3∥∥xn−2−X∥≤⋯≤∥GGSn∥∥x1−X∥,(22)∥xn+1−X∥≤∥GGSn∥∥x1−X∥≤∥GGS∥n∥x1−X∥,(23)∥xn+1−X∥≤∥GGS∥n∥x1−X∥.Consider the refinement of Gauss-Seidel method.(24)xn+1=GGS2xn+B(25)xn+1−X=GGS2xn−X+B=GGS2xn−GGS2X−B+B,(26)∥xn+1−X∥=∥GGS2xn−X∥,(27)∥xn+1−X∥≤∥GGS2∥∥xn−X∥≤∥GGS4∥∥xn−2−X∥≤∥GGS6∥∥xn−2−X∥≤⋯≤∥GGS2n∥∥x1−X∥,(28)∥xn+1−X∥≤∥GGS2n∥∥x1−X∥≤∥GGS∥2n∥x1−X∥,(29)∥xn+1−X∥≤∥GGS∥2n∥x1−X∥.Consider the second-refinement of Gauss-Seidel method.(30)xn+1=GGS3xn+C,(31)xn+1−X=GGS3xn−X+C=GGS3xn−GGS3X−C+C,(32)∥xn+1−X∥=∥GGS3xn−X∥,(33)∥xn+1−X∥≤∥GGS3∥∥xn−X∥≤∥GGS6∥∥xn−2−X∥≤∥GGS9∥∥xn−2−X∥≤⋯≤∥GGS3n∥∥x1−X∥,(34)∥xn+1−X∥≤∥GGS3n∥∥x1−X∥≤∥GGS∥3n∥x1−X∥,(35)∥xn+1−X∥≤∥GGS∥3n∥x1−X∥.Finally, let us consider the generalized refinement of Gauss-Seidel method.(36)xn+1=GGSk+1xn+E,(37)xn+1−X=GGSk+1xn−X+E=GGSk+1xn−GGSk+1X−E+E,(38)∥xn+1−X∥=∥GGSk+1xn−X∥,(39)∥xn+1−X∥≤∥GGSk+1∥∥xn−X∥≤∥GGS2k+1∥∥xn−2−X∥≤∥GGS3k+1∥∥xn−2−X∥≤⋯,(40)≤∥GGSnk+1∥∥x1−X∥,(41)∥xn+1−X∥≤∥GGSnk+1∥∥x1−X∥≤∥GGS∥nk+1∥x1−X∥,(42)∥xn+1−X∥≤∥GGS∥nk+1∥x1−X∥.According to the coefficients of above inequalities (23), (29), (35), and (42), we have ∥GGS∥nk+1≤∥GGS∥3n≤∥GGS∥2n≤∥GGS∥n since ∥GGS∥<1.Therefore, the generalized refinement of Gauss-Seidel method converges faster than the Gauss-Seidel method, refinement of Gauss-Seidel method, and second-refinement of Gauss-Seidel method.


### 3.3. Numerical Examples

Example 1.
Consider an M-matrix A (or 2-cyclic matrix A), which arises from discretization of the Poisson equations∂2T/∂x2+∂2T/∂y2=f, on the unit square as considered [6]. If the system has the form(43)4−10−100−14−10−100−1400−1−1004−100−10−14−100−10−14x1x2x3x4x5x6=100000,then solve it with tol=0.0001.Solution 1.
Forμ¯=ρGJ=0.6036, we obtain optimal values of ω=2/1+1−μ¯2=1.1128.From Table1, one can visualize that the GRGS method is much better than the SOR method. When we choose the 8th-RGS method we get the solution at the first iteration, which means finding a solution using a direct method. The 8th-RGS method is even better than nonstationary methods like CG, BiCG, and MINRES methods.Example 2.
Consider the steady-state heat distribution in a thin square metal plate with dimensions 0.5 m by 0.5 m usingn=m=4. Two adjacent boundaries are held at 0°C, and the heat on the other boundaries increases linearly from 0°C at one corner to 100°C where the sides meet.Solution.
Place the sides with the zero boundary conditions along thex- and y-axes. Then, the problem is expressed as ∂2U/∂x2x,y+∂2U/∂y2x,y=0, for (x,y) in the set R=x,y:0<x<0.5,0<y<0.5. The boundary conditions are u0,y=0,ux,0=0,ux,0.5=200x, and u0.5,y=200y. If n=m=4, the problem has the grid, and the difference equation is 4wi,j−wi+1,j−wi−1,j−wi,j−1−wi,j+1=0, for each i=1,2,3 and j=1,2,3, given in [7]. The exact solution is wx,y=400xy, such that u1=18.75, u2=37.5, u3=56.25, u4=12.5, u5=25, u6=37.5, u7=6.25, u8=12.5, and u9=18.75. The matrix has the form:(44)4−10−100000−14−10−100000−1400−1000−1004−10−1000−10−14−10−1000−10−1400−1000−1004−100000−10−14−100000−10−14w1w2w3w4w5w6w7w8w9=255015000500025.Table 1
Comparison of J, GS, SOR, and GRGS methods.
MethodsNumber of iterationsSpectral radiusRate of convergenceJ190.60360.2193GS90.36430.4385SOR50.11280.9477CG6BiCG6MINRES19RGS50.13270.8771SRGS30.04831.31613rd-RGS30.01761.75454th-RGS20.00642.19385th-RGS20.00232.63836th-RGS20.000853.070587th-RGS20.000313.50868th-RGS10.000113.9586Forμ¯=ρGJ=0.7071, we get optimal values of ω=2/1+1−μ¯2=1.1716.As illustrated in Table2, the 9th-RGS method is better than other listed methods. This is the second example to show that the GRGS method is much better than even the nonstationary method like CG, BiCG, and MINRES methods.Example 3.
Consider the Poisson equation(45)∂2U∂x2+∂2U∂y2=8x2y2on the square with sides x=0=y,x=1=y for x,y in the set with u=0 on the boundary with mesh h=k=1/4.Solution.
Using a finite difference formula, we get the following system:(46)−4101000001−4101000001−4001000100−4101000101−4101000101−4001000100−4100000101−4100000101−4u11u21u31u12u22u32u13u23u33=1/5124/5129/5124/51216/51236/5129/51236/51281/512.Table 2
Comparison of J, GS, SOR, and GRGS methods.
MethodsNumber of iterationsSpectral radiusRate of convergenceJ390.70710.1505GS200.50.3010SOR110.17160.7655CG5BiCG8MINRES33RGS100.0.250.6021SRGS70.1250.90313rd-RGS50.0.06251.20414th-RGS40.03131.50455th-RGS40.01561.80696th-RGS30.00782.10797th-RGS30.00392.40898th-RGS30.0022.6999th-RGS20.0013Forμ¯=ρGJ=0.7071, one can get the optimal values of ω=2/1+1−μ¯2=1.1716.Table3 shows that the 9th-RGS method has a minimum spectral radius and maximum rate of convergence compared to methods listed in the table. We deduce that the GRGS method is preferable than any other iterative methods even the nonstationary method. Therefore, this method is equivalent to the direct methods.Table 3
Comparison of J, GS, SOR, and GRGS methods.
MethodsNumber of iterationsSpectral radiusRate of convergenceJ180.70710.1505GS110.50.3010SOR80.17160.7655CG5BiCG5MINRES19RGS60.250.6021SRGS40.1250.90313rd-RGS30.06251.20414th-RGS20.03131.50455th-RGS20.01561.80696th-RGS20.00782.10797th-RGS20.00392.40898th-RGS20.0022.6999th-RGS20.0013


## 3.1. Algorithm for GRGS Method

(1)
DecomposeA as A=D−L−U, where D−L is nonsingular and U is nonzero matrices; initial approximation x0; tolerance TOL; maximum number of iterations N.(2)
Choosek=0,1,2,3,⋯Forn=0,1,2,⋯, until convergence.Doxn+1=D−L−1Uk+1xn+∑m=0kD−L−1UmD−L−1b.IfN=1 or 2, then stop.


## 3.2. Convergence of Generalized Refinement of Gauss-Seidel Method

Theorem 8.
IfAis consistently ordered 2-cyclic matrices, thenρGGRGS=ρGGSk+1=ρGJ2k+1.The Gauss-Seidel method converges if and only if the generalized refinement of Gauss-Seidel method converges, and the GRGS method converges(k+1)times as fast as Gauss-Seidel method and2k+1times as fast as the Jacobi method.Proof.
LetA be consistently ordered matrix with nonvanishing diagonal elements and 2-cyclic matrix. Then, by Theorem 6, we have ρGGS=ρGJ2. This implies that the Gauss-Seidel method converges twice as fast as the Jacobi method. Hence, based on Theorem 7, the Jacobi method is convergent if and only if the Gauss-Seidel method is convergent. Similarly, if GS converges, then RGS, SRGS, 3th-RGS, …, and GRGS methods converge.(13)ρGRGS=ρGGS2=ρGJ4.
Again,(14)ρGSRGS=ρGRGS3/2=ρGGS3=ρGJ6,ρG3rd−RGS=ρGSRGS4/3=ρGRGS2=ρGGS4=ρGJ8,ρG4th−RGS=ρG3rd−RGS5/4=ρGSRGS5/3=ρGRGS5/2=ρGGS5=ρGJ10,ρG5th−RGS=ρG4th−RGS6/5=ρG3rd−RGS3/2=ρGSRGS2=ρGRGS3=ρGGS6=ρGJ12,and so on. Thus, the spectral radius of the GRGS method is as follows:(15)ρGkth−RGS=ρGk−1th−RGSk+1/k=ρGk−2th−RGSk+1/k−1=ρGk−3th−RGSk+1/k−2=⋯=ρGSRGSk+1/3=ρGRGSk+1/2=ρGGSk+1=ρGJ2k+1.
Therefore, the GRGS method converges (k+1) times as fast as the Gauss-Seidel method and 2k+1 times as fast as the Jacobi method.
Here, one can deduce that the number of iterations of the GRGS method denoted bynGGRGS is(16)nGGRGS=nGkth−RGS≈kk+1nGk−1th−RGS≈k−1k+1nGk−2th−RGS≈⋯≈2k+1nGRGS≈1k+1nGGS≈12k+1nGJ.
Similarly, the rate of convergence of GRGS is denoted byR∞GGRGS such that(17)R∞GGRGS=R∞Gkth−RGS=k+1kR∞Gk−1th−RGS=k+1k−1R∞Gk−2th−RGS=⋯=k+13R∞GSRGS=k+12R∞GRGS=k+1R∞GGS=2k+1R∞GJ.☐Theorem 9.
The generalized refinement of Gauss-Seidel method converges faster than the Gauss-Seidel method and refinement of Gauss-Seidel method when the Gauss-Seidel method is convergent.Proof.
We can rewrite equation (3), RGS, SRGS, and (12), respectively, by xn+1=GGSxn+kGS, xn+1=GGS2xn+B, xn+1=GGS3xn+C, and xn+1=GGSk+1xn+E, where GGS=D−L−1U, kGS=D−L−1b, B=I+D−L−1UD−L−1b, C=I+D−L−1UD−L−1U2D−L−1b, and E=I+D−L−1U+D−L−1U2+⋯+D−L−1Uk, given that∥GGS∥<1. Let X be the exact solution of (1). That is, X=GGSX+kGS, X=GGS2X+B, X=GGS3X+C, and X=GGSk+1X+E. Let n=0,1,2,.. be nonnegative integers.☐If we consider the Gauss-Seidel method,(18)xn+1=GGSxn+kGS,(19)xn+1−X=GGSxn−X+kGS=GGSxn−GGSX−kGS+kGS,(20)∥xn+1−X∥=∥GGSxn−X∥,(21)∥xn+1−X∥≤∥GGS∥∥xn−X∥≤∥GGS2∥∥xn−2−X∥≤∥GGS3∥∥xn−2−X∥≤⋯≤∥GGSn∥∥x1−X∥,(22)∥xn+1−X∥≤∥GGSn∥∥x1−X∥≤∥GGS∥n∥x1−X∥,(23)∥xn+1−X∥≤∥GGS∥n∥x1−X∥.Consider the refinement of Gauss-Seidel method.(24)xn+1=GGS2xn+B(25)xn+1−X=GGS2xn−X+B=GGS2xn−GGS2X−B+B,(26)∥xn+1−X∥=∥GGS2xn−X∥,(27)∥xn+1−X∥≤∥GGS2∥∥xn−X∥≤∥GGS4∥∥xn−2−X∥≤∥GGS6∥∥xn−2−X∥≤⋯≤∥GGS2n∥∥x1−X∥,(28)∥xn+1−X∥≤∥GGS2n∥∥x1−X∥≤∥GGS∥2n∥x1−X∥,(29)∥xn+1−X∥≤∥GGS∥2n∥x1−X∥.Consider the second-refinement of Gauss-Seidel method.(30)xn+1=GGS3xn+C,(31)xn+1−X=GGS3xn−X+C=GGS3xn−GGS3X−C+C,(32)∥xn+1−X∥=∥GGS3xn−X∥,(33)∥xn+1−X∥≤∥GGS3∥∥xn−X∥≤∥GGS6∥∥xn−2−X∥≤∥GGS9∥∥xn−2−X∥≤⋯≤∥GGS3n∥∥x1−X∥,(34)∥xn+1−X∥≤∥GGS3n∥∥x1−X∥≤∥GGS∥3n∥x1−X∥,(35)∥xn+1−X∥≤∥GGS∥3n∥x1−X∥.Finally, let us consider the generalized refinement of Gauss-Seidel method.(36)xn+1=GGSk+1xn+E,(37)xn+1−X=GGSk+1xn−X+E=GGSk+1xn−GGSk+1X−E+E,(38)∥xn+1−X∥=∥GGSk+1xn−X∥,(39)∥xn+1−X∥≤∥GGSk+1∥∥xn−X∥≤∥GGS2k+1∥∥xn−2−X∥≤∥GGS3k+1∥∥xn−2−X∥≤⋯,(40)≤∥GGSnk+1∥∥x1−X∥,(41)∥xn+1−X∥≤∥GGSnk+1∥∥x1−X∥≤∥GGS∥nk+1∥x1−X∥,(42)∥xn+1−X∥≤∥GGS∥nk+1∥x1−X∥.According to the coefficients of above inequalities (23), (29), (35), and (42), we have ∥GGS∥nk+1≤∥GGS∥3n≤∥GGS∥2n≤∥GGS∥n since ∥GGS∥<1.Therefore, the generalized refinement of Gauss-Seidel method converges faster than the Gauss-Seidel method, refinement of Gauss-Seidel method, and second-refinement of Gauss-Seidel method.


## 3.3. Numerical Examples

Example 1.
Consider an M-matrix A (or 2-cyclic matrix A), which arises from discretization of the Poisson equations∂2T/∂x2+∂2T/∂y2=f, on the unit square as considered [6]. If the system has the form(43)4−10−100−14−10−100−1400−1−1004−100−10−14−100−10−14x1x2x3x4x5x6=100000,then solve it with tol=0.0001.Solution 1.
Forμ¯=ρGJ=0.6036, we obtain optimal values of ω=2/1+1−μ¯2=1.1128.From Table1, one can visualize that the GRGS method is much better than the SOR method. When we choose the 8th-RGS method we get the solution at the first iteration, which means finding a solution using a direct method. The 8th-RGS method is even better than nonstationary methods like CG, BiCG, and MINRES methods.Example 2.
Consider the steady-state heat distribution in a thin square metal plate with dimensions 0.5 m by 0.5 m usingn=m=4. Two adjacent boundaries are held at 0°C, and the heat on the other boundaries increases linearly from 0°C at one corner to 100°C where the sides meet.Solution.
Place the sides with the zero boundary conditions along thex- and y-axes. Then, the problem is expressed as ∂2U/∂x2x,y+∂2U/∂y2x,y=0, for (x,y) in the set R=x,y:0<x<0.5,0<y<0.5. The boundary conditions are u0,y=0,ux,0=0,ux,0.5=200x, and u0.5,y=200y. If n=m=4, the problem has the grid, and the difference equation is 4wi,j−wi+1,j−wi−1,j−wi,j−1−wi,j+1=0, for each i=1,2,3 and j=1,2,3, given in [7]. The exact solution is wx,y=400xy, such that u1=18.75, u2=37.5, u3=56.25, u4=12.5, u5=25, u6=37.5, u7=6.25, u8=12.5, and u9=18.75. The matrix has the form:(44)4−10−100000−14−10−100000−1400−1000−1004−10−1000−10−14−10−1000−10−1400−1000−1004−100000−10−14−100000−10−14w1w2w3w4w5w6w7w8w9=255015000500025.Table 1
Comparison of J, GS, SOR, and GRGS methods.
MethodsNumber of iterationsSpectral radiusRate of convergenceJ190.60360.2193GS90.36430.4385SOR50.11280.9477CG6BiCG6MINRES19RGS50.13270.8771SRGS30.04831.31613rd-RGS30.01761.75454th-RGS20.00642.19385th-RGS20.00232.63836th-RGS20.000853.070587th-RGS20.000313.50868th-RGS10.000113.9586Forμ¯=ρGJ=0.7071, we get optimal values of ω=2/1+1−μ¯2=1.1716.As illustrated in Table2, the 9th-RGS method is better than other listed methods. This is the second example to show that the GRGS method is much better than even the nonstationary method like CG, BiCG, and MINRES methods.Example 3.
Consider the Poisson equation(45)∂2U∂x2+∂2U∂y2=8x2y2on the square with sides x=0=y,x=1=y for x,y in the set with u=0 on the boundary with mesh h=k=1/4.Solution.
Using a finite difference formula, we get the following system:(46)−4101000001−4101000001−4001000100−4101000101−4101000101−4001000100−4100000101−4100000101−4u11u21u31u12u22u32u13u23u33=1/5124/5129/5124/51216/51236/5129/51236/51281/512.Table 2
Comparison of J, GS, SOR, and GRGS methods.
MethodsNumber of iterationsSpectral radiusRate of convergenceJ390.70710.1505GS200.50.3010SOR110.17160.7655CG5BiCG8MINRES33RGS100.0.250.6021SRGS70.1250.90313rd-RGS50.0.06251.20414th-RGS40.03131.50455th-RGS40.01561.80696th-RGS30.00782.10797th-RGS30.00392.40898th-RGS30.0022.6999th-RGS20.0013Forμ¯=ρGJ=0.7071, one can get the optimal values of ω=2/1+1−μ¯2=1.1716.Table3 shows that the 9th-RGS method has a minimum spectral radius and maximum rate of convergence compared to methods listed in the table. We deduce that the GRGS method is preferable than any other iterative methods even the nonstationary method. Therefore, this method is equivalent to the direct methods.Table 3
Comparison of J, GS, SOR, and GRGS methods.
MethodsNumber of iterationsSpectral radiusRate of convergenceJ180.70710.1505GS110.50.3010SOR80.17160.7655CG5BiCG5MINRES19RGS60.250.6021SRGS40.1250.90313rd-RGS30.06251.20414th-RGS20.03131.50455th-RGS20.01561.80696th-RGS20.00782.10797th-RGS20.00392.40898th-RGS20.0022.6999th-RGS20.0013


## 4. Conclusion

Large and sparse linear systems of equations which arise from the discretization of PDE and ODE problems are often solved by iterative methods. The iterative method contributed in this study is the GRGS method. The characteristics of the GRGS method compared to other iterative methods are summarized as follows:(i)
The number of iterations of the GRGS methodnGGRGS=nGkth−RGS≈k/k+1nGk−1th−RGS≈k−1/k+1nGk−2th−RGS≈k−2k−2/k+1k+1nGk−3th−RGS≈⋯≈3/k+1nGSRGS≈2/k+1k+1nGRGS≈1/k+1k+1nGGS≈1/2k+12k+1nGJ. The number of iterations of the kth-RGS method is approximately equal to 1/k+1 of the number of iterations of GS and 2/k+1 of the number of iterations of the RGS method and so on.(ii)
The spectral radius of GRGS methodρGGRGS=ρGkth−RGS=ρGk−1th−RGSk+1/k=ρGk−2th−RGSk+1/k−1=⋯=ρGSRGSk+1/3=ρGRGSk+1/2=ρGGSk+1=ρGJ2k+1. Thus, GRGS is faster than J, GS, RGS, and SRGS.(iii)
Rate of convergence of the GRGS methodR∞GGRGS=R∞Gkth−RGS=k+1/kR∞Gk−1th−RGS=k+1/k−1R∞Gk−2th−RGS=⋯=k+1/3R∞GSRGS=k+1/2R∞GRGS=k+1R∞GGS=2k+1R∞GJ. Therefore, the GRGS method has largest rate of convergence than J, GS, RGS, and SRGS.(iv)
The SOR iterative method has the smallest number of iteration as compared to J and GS methods but it has a large number of iterations as compared to the GRGS method. Even though the SOR method is the best method for consistently ordered matrices, our new modified method GRGS is much better than SOR method



---

*Source: 8343207-2021-06-01.xml*