# A Single Sweep AGE  Algorithm on a Variable Mesh Based on Off-Step Discretization for the Solution of Nonlinear  Burgers’ Equation

Authors: R. K. Mohanty; Jyoti Talwar
Journal: Journal of Computational Methods in Physics
 (2014)

---

## Abstract

We discuss a new single sweep alternating group explicit iteration method, along with a third-order numerical method based on off-step discretization on a variable mesh to solve the nonlinear ordinary differential equationy′′=f(x,y,y′) subject to given natural boundary conditions. Using the proposed method, we have solved Burgers’ equation both in singular and nonsingular cases, which is the main attraction of our work. The convergence of the proposed method is discussed in detail. We compared the results of the proposed iteration method with the results of the corresponding double sweep alternating group explicit iteration methods to demonstrate computationally the efficiency of the proposed method.


---

## Body

## 1. Introduction

Consider the general nonlinear ordinary differential equation(1)y′′=f(x,y,y′),a<x<b
subject to essential boundary conditions
(2)y(a)=A,y(b)=B,
where -∞<a<b<∞,A,B are finite constants.We assume that forx∈[a,b],-∞<y,z<∞(i)
f(x,y,z) is continuous,(ii)
∂f/∂y and ∂f/∂z exist and are continuous,(iii)
∂f/∂y>0 and |∂f/∂z|<W for some positive constant W.These conditions ensure that the boundary value problem (1) and (2) possesses a unique solution (see Keller [1]).With the advent of parallel computers, scientists are focusing on developing finite difference methods with the property of parallelism. Working on this, in the early 1980s, Evans [2, 3] introduced the Group Explicit methods for large linear system of equations. Further he discussed the Alternating Group Explicit (AGE) method to solve periodic parabolic equations in a coupled manner. Mohanty and Evans applied AGE method along with various high order methods [4, 5] for the solution of two-point boundary value problems. Later, Sukon and Evans [6] introduced a Two-parameter Alternating Group Explicit (TAGE) method for the two-point boundary value problem with a lower order accuracy scheme. In 2003 Mohanty et al. [7] discussed the application of TAGE method for nonlinear singular two point boundary value problems using a fourth-order difference scheme. In 1990, Evans introduced the Coupled Alternating Group Explicit method [8] and applied it to periodic parabolic equations. Many scientists are applying these parallel algorithms to solve ordinary and partial differential equations [9–11].Recently, Mohanty [12] has proposed a high order variable mesh method for nonlinear two-point boundary value problem. Mohanty and Khosla [13, 14] also devised a new third-order accurate arithmetic average variable mesh method for the solution of the boundary value problem (1) and (2), using three grid points, which is applicable to both singular and nonsingular problems. No special technique is required to handle singular problems. They also discussed the application of two-parameter double sweep alternating group explicit methods. Here, we discuss a new single sweep group explicit iteration method along with a third-order accurate variable mesh method based on two extra off-step grid points for the solution of the boundary value problem (1) and (2).


## 2. Off-Step Discretization

Consider the solution interval[a,b] with a nonuniform mesh such that a=x0<x1<⋯<xN<xN+1=b. Let hk=xk-xk-1, k=1(1)N+1, be the mesh size and let σk=hk+1/hk>0, k=1(1)N, be the mesh ratio. Grid points are given by xi=x0+∑k=1ihk, i=1(1)N+1. Let Yk=y(xk) be the exact solution of y at the grid point xk and approximated by yk. Let xk+1/2=xk+(σkhk/2) and xk-1/2=xk-(hk/2).The new third-order method is described as follows.Fory′′=f, we first obtain the off-step discretization
(3)Yk+1-(1+σk)Yk+σkYk-1=σkhk23[σkfk+1/2+(1+σk)2fk+fk-1/2]+Tk,
where fk+1/2=y′′(xk+1/2), fk-1/2=y′′(xk-1/2), and Tk=O(hk5).Now, let(4a)Y-k+1/2=12(Yk+1+Yk),(4b)Y-k-1/2=12(Yk-1+Yk),(4c)Y-k+1/2′=1σkhk(Yk+1-Yk),(4d)Y-k-1/2′=1hk(Yk-Yk-1),(4e)Y-k′=(Yk+1-(1-σk2)Yk-σk2Yk-1)(hkσk(σk+1)),(4f)f-k+1/2=f(xk+1/2,Y-k+1/2,Y-k+1/2′),(4g)f-k-1/2=f(xk-1/2,Y-k-1/2,Y-k-1/2′),(4h)Y^k=Yk-(1-σk+σk2)hk28(f-k+1/2+f-k-1/2),(4i)Y^k′=Y-k′-(1+σk+σk2)hk6(1+σk)(f-k+1/2-f-k-1/2),(4j)f^k=f(xk,Y^k,Y^k′).Then, at each interior grid pointxk,k=1(1)N, the proposed differential equation (1) is discretized by
(5)Yk+1-(1+σk)Yk+σkYk-1=σkhk23[σkf-k+1/2+(1+σk2)f^k+f-k-1/2]+T-k,σk≠1.
With the help of (3), from (5) it is easy to verify that T-k=O(hk5), provided σk≠1. However, for uniform mesh σk=1, the local truncation error associated with (5) becomes T-k=O(hk6) (see Chawla and Shivakumar [15]).Note that the proposed method (5) is applicable to both singular and nonsingular problems. We do not require any special technique to handle singular problems (see Mohanty [13]). Further note that, the boundary values are given by y0=Y0=A and yN+1=YN+1=B. If the differential equation (1) is linear we use the proposed single sweep AGE iterative method and in nonlinear case, we use the Newton-AGE iterative method to obtain the solution.


## 3. Application to Singular Problems

### 3.1. Linear Singular Problems

We now discuss the application of the proposed numerical method (5) to the linear differential equation with variable coefficients
(6)y′′=D(x)y′+g(x),0<x<1,
where g(x) represents a forcing function.ForD(x)=-α/x and for α=1 and 2, the equation above represents singular equation in cylindrical and spherical symmetry, respectively.Let us denote(7)Dk=D(xk),Dk±1/2=D(xk±1/2),gk=g(xk),gk±12=g(xk±12),σk=hk+1hk,Rk=(1+σk+σk2)12.Therefore applying the method (5) to the differential equation (6) and neglecting error term, we obtain a linear difference equation of the form
(8)akyk-1+2bkyk+ckyk+1=Jk,k=1(1)N,
where
(9)ak=-σk[1+hk3(1+DkRkhk)Dk-1/2+σkhk6Dk]2bk=[1+σk-hk3(σk-DkRkhk)Dk+1/2+σkhk3(1+DkRkhk)Dk-1/2-hk6(1-σk2)Dk]ck=[-1+hk3(σk-DkRkhk)Dk+1/2+hk6Dk]Jk=-σkhk23[(1+σk2)gk+(σk-DkRkhk)gk+1/2+(1+DkRkhk)gk-1/2(1+σk2)].The linear difference scheme (8) has a local truncation error of O(hk5) and is free from the terms 1/xk±1 and therefore can very easily be solved for k=1(1)N in the region x∈(0,1).


### 3.2. Nonlinear Singular Problems

Now we consider the application to nonlinear differential equation (1). Neglecting the error term, we may rewrite the nonlinear difference equation (5) as
(10)yk+1-(1+σk)yk+σkyk-1=σkhk23[σkf-k+1/2+(1+σk2)f^k+f-k-1/2].
Let
(11)ϕk≡-yk+1+(1+σk)yk-σkyk-1+σkhk23[σkf-k+1/2+(1+σk2)f^k+f-k-1/2]≡ϕk(yk-1,yk,yk+1),k=1(1)N,σk≠1.
We denote
(12)y=[y1y2⋮⋮yN]N×1,φ(y)=[ϕ1(y)ϕ2(y)⋮⋮ϕN(y)]N×1,ak(y)=∂ϕk∂yk-1,k=2(1)N2bk(y)=∂ϕk∂yk,k=1(1)Nck(y)=∂ϕk∂yk+1,k=1(1)N-1.
The Jacobian φ(y) may be represented as
(13)T≡∂φ(y)∂y=[2b1(y)c1(y)0a2(y)2b2(y)c2(y)⋱⋱⋱⋱⋱cN-1(y)0aN(y)2bN(y)]N×N.


## 3.1. Linear Singular Problems

We now discuss the application of the proposed numerical method (5) to the linear differential equation with variable coefficients
(6)y′′=D(x)y′+g(x),0<x<1,
where g(x) represents a forcing function.ForD(x)=-α/x and for α=1 and 2, the equation above represents singular equation in cylindrical and spherical symmetry, respectively.Let us denote(7)Dk=D(xk),Dk±1/2=D(xk±1/2),gk=g(xk),gk±12=g(xk±12),σk=hk+1hk,Rk=(1+σk+σk2)12.Therefore applying the method (5) to the differential equation (6) and neglecting error term, we obtain a linear difference equation of the form
(8)akyk-1+2bkyk+ckyk+1=Jk,k=1(1)N,
where
(9)ak=-σk[1+hk3(1+DkRkhk)Dk-1/2+σkhk6Dk]2bk=[1+σk-hk3(σk-DkRkhk)Dk+1/2+σkhk3(1+DkRkhk)Dk-1/2-hk6(1-σk2)Dk]ck=[-1+hk3(σk-DkRkhk)Dk+1/2+hk6Dk]Jk=-σkhk23[(1+σk2)gk+(σk-DkRkhk)gk+1/2+(1+DkRkhk)gk-1/2(1+σk2)].The linear difference scheme (8) has a local truncation error of O(hk5) and is free from the terms 1/xk±1 and therefore can very easily be solved for k=1(1)N in the region x∈(0,1).


## 3.2. Nonlinear Singular Problems

Now we consider the application to nonlinear differential equation (1). Neglecting the error term, we may rewrite the nonlinear difference equation (5) as
(10)yk+1-(1+σk)yk+σkyk-1=σkhk23[σkf-k+1/2+(1+σk2)f^k+f-k-1/2].
Let
(11)ϕk≡-yk+1+(1+σk)yk-σkyk-1+σkhk23[σkf-k+1/2+(1+σk2)f^k+f-k-1/2]≡ϕk(yk-1,yk,yk+1),k=1(1)N,σk≠1.
We denote
(12)y=[y1y2⋮⋮yN]N×1,φ(y)=[ϕ1(y)ϕ2(y)⋮⋮ϕN(y)]N×1,ak(y)=∂ϕk∂yk-1,k=2(1)N2bk(y)=∂ϕk∂yk,k=1(1)Nck(y)=∂ϕk∂yk+1,k=1(1)N-1.
The Jacobian φ(y) may be represented as
(13)T≡∂φ(y)∂y=[2b1(y)c1(y)0a2(y)2b2(y)c2(y)⋱⋱⋱⋱⋱cN-1(y)0aN(y)2bN(y)]N×N.


## 4. Single Sweep AGE Method

### 4.1. Description of the Method

In this section we discuss the single sweep AGE iteration method. Using the boundary conditionsy0=A, yN+1=B, the linear difference equation (8) may be written in the matrix form as
(14)Ay=RH,
where
(15)A=[2b1c10a22b2c2⋱aN-12bN-1cN-10aN2bN]N×N,y=[y1y2⋮⋮yN]N×1,RH=[J1-a1y0J2⋮⋮JN-cNyN+1]N×1=[RH1RH2⋮⋮RHN]N×1(say).To implement the single sweep AGE iterative method, we split the coefficient matrixA into two submatrices A=G1+G2, where G1 and G2 satisfy the following conditions.(i)
G1+ω1I and G2+ω2I are nonsingular for suitable choice of ω1>0 and ω2>0.(ii)
For any vectorsν1 and ν2 and ω1>0, ω2>0, it is “convenient” to solve the system explicitly; that is, z1=(G1+ω1I)-1ν1 and z2=(G2+ω2I)-1ν2 for vectors z1 and z2, respectively.We will be concerned here with the situation where G1 and G2 are small (2×2) block systems.Now we discuss the case whenN is even (with x0=0, xN+1=1).Let(16)G1=[b1c1a2b20b3c3a4b4⋱0bN-1cN-1aNbN]N×N,G2=[b10b2c2a3b3⋱bN-2cN-2aN-1bN-10bN]N×N.
So that the system (14) can be rewritten as
(17)(G1+G2)y=RH.
Then a two-parameter AGE method for solving the afore mentioned system may be written as
(18)(G1+ω1I)z(s)=RH-(G2-ω1I)y(s),s=0,1,2,…,(19)(G2+ω2I)y(s+1)=RH-(G1-ω2I)z(s),s=0,1,2,…,
where z(s) is an intermediate vector.Eliminatingz(s) and combining (18) and (19), we obtain the iterative method
(20)(G2+ω2I)y(s+1)=[I-(ω1+ω2)(G1+ω1I)-1](G2-ω1I)y(s)+(ω1+ω2)(G1+ω1I)-1RH,s=0,1,2,…,
or
(21)u(s+1)=Twy(s)+RHw,s=0,1,2,…,
where
(22)Tw=(G2+ω2I)-1×[(G1+ω1I)-1(G2-ω1I)-(ω1+ω2)(G1+ω1I)-1(G2-ω1I)],RHw=(ω1+ω2)(G2+ω2I)-1(G1+ω1I)-1RH.The new iterative method (20) or (21) is called the two-parameter single sweep AGE iterative method and the matrix Tw is called the iteration matrix.Now we discuss the single sweep AGE algorithm, whenN is even.For simplicity, we denote(23)pk=bk+ω1,qk=bk-ω1,rk=bk+ω2fork=1(1)N,for(pkpk+1-ckak+1)≠0,
and we define dk=1/(pkpk+1-ckak+1) for k=1(1)N-1.By carrying out the necessary algebra in (20), we obtain the following algorithm.Fork=1,
(24)y1(s+1)=(q1y1(s)-(ω1+ω2)d1×[-c1q2y2(s)-c1c2y3(s)+p2q1y1(s)+c1RH2-p2RH1-c1q2y2(s)]q1y1(s)-(ω1+ω2)d1)×(r1)-1,s=0,1,2,….
For k=2(2)N-2.Let(25)Δ=rkrk+1-ckak+1≠0,S1=qkyk(s)+ckyk+1(s)-(ω1+ω2)dk-1×[-ak-1akyk-2(s)-akqk-1yk-1(s)+pk-1qkyk(s)+pk-1ckyk+1(s)+akRHk-1-pk-1RHk],S2=ak+1yk(s)+qk+1yk+1(s)-(ω1+ω2)dk+1×[pk+2ak+1yk(s)+pk+2qk+1yk+1(s)-ck+1qk+2yk+2(s)-ck+1ck+2yk+3(s)-pk+2RHk+1+ck+1RHk+2yk(s)],
and then
(26)yk(s+1)=(S1rk+1-S2ck)Δ,s=0,1,2,…yk+1(s+1)=(S2rk-S1ak+1)Δ,s=0,1,2,….
Finally, for k=N,
(27)yN(s+1)=(qNyN(s)-(ω1+ω2)dN-1×[-aN-1aNyN-2(s)-aNqN-1yN-1(s)+pN-1qNyN(s)+aNRHN-1-pN-1RHNyN-2(s)])×(rN)-1,s=0,1,2,….
Similarly, we can write the single sweep AGE algorithm when N is odd.


### 4.2. Convergence Analysis

The single sweep AGE iteration method is given by(28)(G2+ω2I)y(s+1)=[I-(ω1+ω2)(G1+ω1I)-1](G2-ω1I)y(s)+(ω1+ω2)(G1+ω1I)-1RH,s=0,1,2,…,
or
(29)y(s+1)=Twy(s)+RHw,s=0,1,2,…,
where
(30)Tw=(G2+ω2I)-1×[(G1+ω1I)-1(G2-ω1I)-(ω1+ω2)(G1+ω1I)-1(G2-ω1I)],RHw=(ω1+ω2)(G2+ω2I)-1(G1+ω1I)-1RH.
The matrix Tw is called the iteration matrix.To prove the convergence of the method, we need to prove thatS(Tw)≤1, where S(Tw) denotes the spectral radius of Tw.Lemma 1.
Lethk be sufficiently small. Then, the eigenvalues of G1 and G2 are all real.Proof.
Consider(31)ak=-σk[1+hk3(1+DkRkhk)Dk-1/2+σkhk6Dk]=-σk-O(hk)<0,forsufficientlysmallhk,ck=[-1+hk3(σk-DkRkhk)Dk+1/2+hk6Dk]=-1+O(hk)<0,forsufficientlysmallhk.
Therefore, we have ak+1ck>0, for k=1(2)N-1.
Letλi,i=1(1)N, be the eigenvalues of G1. Then λi’s are the roots of the quadratic equation
(32)λi2-(bi+bi+1)λi+(bibi+1-ai+1ci)=0.
Simplifying, we get
(33)λi=12[(bi+bi+1)±(bi-bi+1)2+4ai+1ci].
The discriminants of the quadratic equations are
(34)(bi-bi+1)2+4ai+1ci>0,k=1(2)N-1.
Hence, the eigenvalues of G1 are real.
In a similar manner, we can show that the eigenvalues ofG2 are real.Now we give the sufficient condition for the convergence of the method.Theorem 2.
Letλi and μi,i=1(1)N, be the eigenvalues of G1 and G2, respectively. If
(35)ω1>max⁡⁡{0,-λ1,…,-λN},(36)ω2>max⁡⁡{0,-μ1,…,-μN},(37)ω2-2min⁡iλi<ω1<ω2+2min⁡iμi,
then the iterative method is convergent for the system (14).Proof.
Let(38)D=diag⁡(1,c1a2,c1c2a2a3,…,c1c2⋯cN-1a2a3⋯aN)≡diag⁡(d1,d2,d3,…,dN).
Since the off-diagonal entries ofA are negative, therefore ak+1ck>0, k=1,…,N-1. Therefore, the diagonal entries of D are positive.
The iteration matrix is given by(39)Tw=(G2+ω2I)-1×[(G1+ω1I)-1(G2-ω1I)-(ω1+ω2)(G1+ω1I)-1(G2-ω1I)]=(G2+ω2I)-1×[I-(ω1+ω2)(G1+ω1I)-1](G2-ω1I).
Define
(40)Tw*=(G2+ω2I)Tw(G2+ω2I)-1=[I-(ω1+ω2)(G1+ω1I)-1]×(G2-ω1I)(G2+ω2I)-1S(Tw)=S(Tw*)=S(D1/2Tw*D-1/2)D1/2Tw*D-1/2=[I-(ω1+ω2)(G-1+ω1I)-1]×(G-2-ω1I)(G-2+ω2I)-1,
where G-1=D1/2G1D-1/2 and G-2=D1/2G2D-1/2, and
(41)S(Tw)=S(Tw*)=S(D1/2Tw*D-1/2)≤∥D1/2Tw*D-1/2∥2≤∥[I-(ω1+ω2)(G-1+ω1I)-1]∥2×∥(G-2-ω1I)(G-2+ω2I)-1∥2.
It is easy to verify that G-1 and G-2 are symmetric. Therefore, the matrices (G-2-ω1I)(G-2+ω2I)-1 and [I-(ω1+ω2)(G-1+ω1I)-1] are also symmetric. Hence,
(42)∥(G-2-ω1I)(G-2+ω2I)-1∥2=max⁡μi∈σ(G-2)|(μi-ω1)(μi+ω2)|∥[I-(ω1+ω2)(G-1+ω1I)-1]∥2=∥[(G-1+ω1I)(G-1+ω1I)-1-(ω1+ω2)(G-1+ω1I)-1]∥2=∥[(G-1-ω2I)][(G-1+ω1I)-1]∥2.
Also, (G-1-ω2I)(G-1+ω1I)-1 is symmetric, and therefore
(43)∥[(G-1-ω2I)][(G-1+ω1I)-1]∥2=max⁡λi∈σ(G-1)|(λi-ω2)(λi+ω1)|.
Therefore, we have
(44)S(Tw)≤max⁡λi∈σ(G-1)|(λi-ω2)(λi+ω1)|max⁡μi∈σ(G-2)|(μi-ω1)(μi+ω2)|.
From (35) and (36), we have ω1,ω2>0 and λi+ω1>0 for k=1,…,N.
Hence,(45)λi-ω2λi+ω1<1,k=1(1)N.
Also, from (37), we have
(46)ω2<ω1+2min⁡iλi<ω1+2λi,i=1(1)N-1<λi-ω2λi+ω1,k=1(1)N.
Hence, we conclude that
(47)|λi-ω2λi+ω1|<1,k=1(1)N.
Thus,
(48)max⁡λi∈σ(G-1)|(λi-ω2)(λi+ω1)|<1.
Similarly, we can prove that
(49)max⁡μi∈σ(G-2)|(μi-ω1)(μi+ω2)|<1.
Using (44), (48), and (49), we get S(Tw)<1.Hence, the convergence of the method (20) follows.


### 4.3. Application of Single Sweep Newton-AGE Method

Now we discuss the single sweep Newton-AGE iterative method for the nonlinear difference equation (11). We follow the approaches given by Evans [8, 16].Let us define(50)y=[y1y2⋮yN]N×1,φ(y)=[ϕ1(y)ϕ2(y)⋮ϕN(y)]N×1,ak(y)=∂ϕk∂yk-1,k=2(1)N2bk(y)=∂ϕk∂yk,k=1(1)Nck(y)=∂ϕk∂yk+1,k=1(1)N-1.
Then the Jacobian of φ(y) can be written as the Nth-order tridiagonal matrix
(51)T=∂φ(y)∂y=[2b1(y)c1(y)0a2(y)2b2(y)c2(y)⋱⋱0aN(y)2bN(y)]N×N.
Now with any initial vector y(0), we define
(52)y(s+1)=y(s)+Δy(s),s=0,1,2,…,
where Δy(s) is the solution of the nonlinear system
(53)TΔy(s)=-φ(y(s)),s=0,1,2,….For the single sweep Newton-AGE method, we consider the case whenN is even. We split the matrix T as T=T1+T2, where
(54)T1=[b1c1a2b20b3c3a4b4⋱0bN-1cN-1aNbN]N×N,T2=[b10b2c2a3b3⋱bN-2cN-2aN-1bN-10bN]N×N
and then we write single sweep Newton-AGE method as
(55)(T2+ω2I)Δy(s+1)=[I-(ω1+ω2)(T1+ω1I)-1](T2-ω1I)Δy(s)-(ω1+ω2)(T1+ω1I)-1φ(y(s)),s=0,1,2,…,
where ω1>0,ω2>0 are relaxation parameters and (T1+ω1I) and (T2+ω2I) are nonsingular.Since(T1+ω1I) and (T2+ω2I) consist of (2×2) submatrices, they can be easily inverted as(56a)(T1+ω1I)-1=[(p2-c1-a2p1)Δ1⋱00⋱(pN-cN-1-aNpN-1)ΔN-1]N×N,(56b)(T2+ω2I)-1=[1r1(r3-c2-a3r2)Δ200⋱1rN]N×Nwith pk=bk+ω1,k=1(1)N, Δk=pkpk+1-ckak+1,k=1(2)N-1, rk=bk+ω2,k=1(1)N, and Δk=rkrk+1-ckak+1,k=2(2)N-2.The matrices(T2+ω2I)-1(T1+ω1I)-1(T2-ω1I) and (T2+ω2I)-1(T1+ω1I)-1 can be evaluated in a manner suitable for parallel computing. In order for this method to converge, it is sufficient that the initial vector y(0) be close to the solution.Similarly, we can write the single sweep Newton-AGE algorithm whenN is odd.


## 4.1. Description of the Method

In this section we discuss the single sweep AGE iteration method. Using the boundary conditionsy0=A, yN+1=B, the linear difference equation (8) may be written in the matrix form as
(14)Ay=RH,
where
(15)A=[2b1c10a22b2c2⋱aN-12bN-1cN-10aN2bN]N×N,y=[y1y2⋮⋮yN]N×1,RH=[J1-a1y0J2⋮⋮JN-cNyN+1]N×1=[RH1RH2⋮⋮RHN]N×1(say).To implement the single sweep AGE iterative method, we split the coefficient matrixA into two submatrices A=G1+G2, where G1 and G2 satisfy the following conditions.(i)
G1+ω1I and G2+ω2I are nonsingular for suitable choice of ω1>0 and ω2>0.(ii)
For any vectorsν1 and ν2 and ω1>0, ω2>0, it is “convenient” to solve the system explicitly; that is, z1=(G1+ω1I)-1ν1 and z2=(G2+ω2I)-1ν2 for vectors z1 and z2, respectively.We will be concerned here with the situation where G1 and G2 are small (2×2) block systems.Now we discuss the case whenN is even (with x0=0, xN+1=1).Let(16)G1=[b1c1a2b20b3c3a4b4⋱0bN-1cN-1aNbN]N×N,G2=[b10b2c2a3b3⋱bN-2cN-2aN-1bN-10bN]N×N.
So that the system (14) can be rewritten as
(17)(G1+G2)y=RH.
Then a two-parameter AGE method for solving the afore mentioned system may be written as
(18)(G1+ω1I)z(s)=RH-(G2-ω1I)y(s),s=0,1,2,…,(19)(G2+ω2I)y(s+1)=RH-(G1-ω2I)z(s),s=0,1,2,…,
where z(s) is an intermediate vector.Eliminatingz(s) and combining (18) and (19), we obtain the iterative method
(20)(G2+ω2I)y(s+1)=[I-(ω1+ω2)(G1+ω1I)-1](G2-ω1I)y(s)+(ω1+ω2)(G1+ω1I)-1RH,s=0,1,2,…,
or
(21)u(s+1)=Twy(s)+RHw,s=0,1,2,…,
where
(22)Tw=(G2+ω2I)-1×[(G1+ω1I)-1(G2-ω1I)-(ω1+ω2)(G1+ω1I)-1(G2-ω1I)],RHw=(ω1+ω2)(G2+ω2I)-1(G1+ω1I)-1RH.The new iterative method (20) or (21) is called the two-parameter single sweep AGE iterative method and the matrix Tw is called the iteration matrix.Now we discuss the single sweep AGE algorithm, whenN is even.For simplicity, we denote(23)pk=bk+ω1,qk=bk-ω1,rk=bk+ω2fork=1(1)N,for(pkpk+1-ckak+1)≠0,
and we define dk=1/(pkpk+1-ckak+1) for k=1(1)N-1.By carrying out the necessary algebra in (20), we obtain the following algorithm.Fork=1,
(24)y1(s+1)=(q1y1(s)-(ω1+ω2)d1×[-c1q2y2(s)-c1c2y3(s)+p2q1y1(s)+c1RH2-p2RH1-c1q2y2(s)]q1y1(s)-(ω1+ω2)d1)×(r1)-1,s=0,1,2,….
For k=2(2)N-2.Let(25)Δ=rkrk+1-ckak+1≠0,S1=qkyk(s)+ckyk+1(s)-(ω1+ω2)dk-1×[-ak-1akyk-2(s)-akqk-1yk-1(s)+pk-1qkyk(s)+pk-1ckyk+1(s)+akRHk-1-pk-1RHk],S2=ak+1yk(s)+qk+1yk+1(s)-(ω1+ω2)dk+1×[pk+2ak+1yk(s)+pk+2qk+1yk+1(s)-ck+1qk+2yk+2(s)-ck+1ck+2yk+3(s)-pk+2RHk+1+ck+1RHk+2yk(s)],
and then
(26)yk(s+1)=(S1rk+1-S2ck)Δ,s=0,1,2,…yk+1(s+1)=(S2rk-S1ak+1)Δ,s=0,1,2,….
Finally, for k=N,
(27)yN(s+1)=(qNyN(s)-(ω1+ω2)dN-1×[-aN-1aNyN-2(s)-aNqN-1yN-1(s)+pN-1qNyN(s)+aNRHN-1-pN-1RHNyN-2(s)])×(rN)-1,s=0,1,2,….
Similarly, we can write the single sweep AGE algorithm when N is odd.


## 4.2. Convergence Analysis

The single sweep AGE iteration method is given by(28)(G2+ω2I)y(s+1)=[I-(ω1+ω2)(G1+ω1I)-1](G2-ω1I)y(s)+(ω1+ω2)(G1+ω1I)-1RH,s=0,1,2,…,
or
(29)y(s+1)=Twy(s)+RHw,s=0,1,2,…,
where
(30)Tw=(G2+ω2I)-1×[(G1+ω1I)-1(G2-ω1I)-(ω1+ω2)(G1+ω1I)-1(G2-ω1I)],RHw=(ω1+ω2)(G2+ω2I)-1(G1+ω1I)-1RH.
The matrix Tw is called the iteration matrix.To prove the convergence of the method, we need to prove thatS(Tw)≤1, where S(Tw) denotes the spectral radius of Tw.Lemma 1.
Lethk be sufficiently small. Then, the eigenvalues of G1 and G2 are all real.Proof.
Consider(31)ak=-σk[1+hk3(1+DkRkhk)Dk-1/2+σkhk6Dk]=-σk-O(hk)<0,forsufficientlysmallhk,ck=[-1+hk3(σk-DkRkhk)Dk+1/2+hk6Dk]=-1+O(hk)<0,forsufficientlysmallhk.
Therefore, we have ak+1ck>0, for k=1(2)N-1.
Letλi,i=1(1)N, be the eigenvalues of G1. Then λi’s are the roots of the quadratic equation
(32)λi2-(bi+bi+1)λi+(bibi+1-ai+1ci)=0.
Simplifying, we get
(33)λi=12[(bi+bi+1)±(bi-bi+1)2+4ai+1ci].
The discriminants of the quadratic equations are
(34)(bi-bi+1)2+4ai+1ci>0,k=1(2)N-1.
Hence, the eigenvalues of G1 are real.
In a similar manner, we can show that the eigenvalues ofG2 are real.Now we give the sufficient condition for the convergence of the method.Theorem 2.
Letλi and μi,i=1(1)N, be the eigenvalues of G1 and G2, respectively. If
(35)ω1>max⁡⁡{0,-λ1,…,-λN},(36)ω2>max⁡⁡{0,-μ1,…,-μN},(37)ω2-2min⁡iλi<ω1<ω2+2min⁡iμi,
then the iterative method is convergent for the system (14).Proof.
Let(38)D=diag⁡(1,c1a2,c1c2a2a3,…,c1c2⋯cN-1a2a3⋯aN)≡diag⁡(d1,d2,d3,…,dN).
Since the off-diagonal entries ofA are negative, therefore ak+1ck>0, k=1,…,N-1. Therefore, the diagonal entries of D are positive.
The iteration matrix is given by(39)Tw=(G2+ω2I)-1×[(G1+ω1I)-1(G2-ω1I)-(ω1+ω2)(G1+ω1I)-1(G2-ω1I)]=(G2+ω2I)-1×[I-(ω1+ω2)(G1+ω1I)-1](G2-ω1I).
Define
(40)Tw*=(G2+ω2I)Tw(G2+ω2I)-1=[I-(ω1+ω2)(G1+ω1I)-1]×(G2-ω1I)(G2+ω2I)-1S(Tw)=S(Tw*)=S(D1/2Tw*D-1/2)D1/2Tw*D-1/2=[I-(ω1+ω2)(G-1+ω1I)-1]×(G-2-ω1I)(G-2+ω2I)-1,
where G-1=D1/2G1D-1/2 and G-2=D1/2G2D-1/2, and
(41)S(Tw)=S(Tw*)=S(D1/2Tw*D-1/2)≤∥D1/2Tw*D-1/2∥2≤∥[I-(ω1+ω2)(G-1+ω1I)-1]∥2×∥(G-2-ω1I)(G-2+ω2I)-1∥2.
It is easy to verify that G-1 and G-2 are symmetric. Therefore, the matrices (G-2-ω1I)(G-2+ω2I)-1 and [I-(ω1+ω2)(G-1+ω1I)-1] are also symmetric. Hence,
(42)∥(G-2-ω1I)(G-2+ω2I)-1∥2=max⁡μi∈σ(G-2)|(μi-ω1)(μi+ω2)|∥[I-(ω1+ω2)(G-1+ω1I)-1]∥2=∥[(G-1+ω1I)(G-1+ω1I)-1-(ω1+ω2)(G-1+ω1I)-1]∥2=∥[(G-1-ω2I)][(G-1+ω1I)-1]∥2.
Also, (G-1-ω2I)(G-1+ω1I)-1 is symmetric, and therefore
(43)∥[(G-1-ω2I)][(G-1+ω1I)-1]∥2=max⁡λi∈σ(G-1)|(λi-ω2)(λi+ω1)|.
Therefore, we have
(44)S(Tw)≤max⁡λi∈σ(G-1)|(λi-ω2)(λi+ω1)|max⁡μi∈σ(G-2)|(μi-ω1)(μi+ω2)|.
From (35) and (36), we have ω1,ω2>0 and λi+ω1>0 for k=1,…,N.
Hence,(45)λi-ω2λi+ω1<1,k=1(1)N.
Also, from (37), we have
(46)ω2<ω1+2min⁡iλi<ω1+2λi,i=1(1)N-1<λi-ω2λi+ω1,k=1(1)N.
Hence, we conclude that
(47)|λi-ω2λi+ω1|<1,k=1(1)N.
Thus,
(48)max⁡λi∈σ(G-1)|(λi-ω2)(λi+ω1)|<1.
Similarly, we can prove that
(49)max⁡μi∈σ(G-2)|(μi-ω1)(μi+ω2)|<1.
Using (44), (48), and (49), we get S(Tw)<1.Hence, the convergence of the method (20) follows.


## 4.3. Application of Single Sweep Newton-AGE Method

Now we discuss the single sweep Newton-AGE iterative method for the nonlinear difference equation (11). We follow the approaches given by Evans [8, 16].Let us define(50)y=[y1y2⋮yN]N×1,φ(y)=[ϕ1(y)ϕ2(y)⋮ϕN(y)]N×1,ak(y)=∂ϕk∂yk-1,k=2(1)N2bk(y)=∂ϕk∂yk,k=1(1)Nck(y)=∂ϕk∂yk+1,k=1(1)N-1.
Then the Jacobian of φ(y) can be written as the Nth-order tridiagonal matrix
(51)T=∂φ(y)∂y=[2b1(y)c1(y)0a2(y)2b2(y)c2(y)⋱⋱0aN(y)2bN(y)]N×N.
Now with any initial vector y(0), we define
(52)y(s+1)=y(s)+Δy(s),s=0,1,2,…,
where Δy(s) is the solution of the nonlinear system
(53)TΔy(s)=-φ(y(s)),s=0,1,2,….For the single sweep Newton-AGE method, we consider the case whenN is even. We split the matrix T as T=T1+T2, where
(54)T1=[b1c1a2b20b3c3a4b4⋱0bN-1cN-1aNbN]N×N,T2=[b10b2c2a3b3⋱bN-2cN-2aN-1bN-10bN]N×N
and then we write single sweep Newton-AGE method as
(55)(T2+ω2I)Δy(s+1)=[I-(ω1+ω2)(T1+ω1I)-1](T2-ω1I)Δy(s)-(ω1+ω2)(T1+ω1I)-1φ(y(s)),s=0,1,2,…,
where ω1>0,ω2>0 are relaxation parameters and (T1+ω1I) and (T2+ω2I) are nonsingular.Since(T1+ω1I) and (T2+ω2I) consist of (2×2) submatrices, they can be easily inverted as(56a)(T1+ω1I)-1=[(p2-c1-a2p1)Δ1⋱00⋱(pN-cN-1-aNpN-1)ΔN-1]N×N,(56b)(T2+ω2I)-1=[1r1(r3-c2-a3r2)Δ200⋱1rN]N×Nwith pk=bk+ω1,k=1(1)N, Δk=pkpk+1-ckak+1,k=1(2)N-1, rk=bk+ω2,k=1(1)N, and Δk=rkrk+1-ckak+1,k=2(2)N-2.The matrices(T2+ω2I)-1(T1+ω1I)-1(T2-ω1I) and (T2+ω2I)-1(T1+ω1I)-1 can be evaluated in a manner suitable for parallel computing. In order for this method to converge, it is sufficient that the initial vector y(0) be close to the solution.Similarly, we can write the single sweep Newton-AGE algorithm whenN is odd.


## 5. Results and Observations

We have applied the methods to the following three examples, whose exact solutions are known to us, and have compared the results with the corresponding double sweep AGE and Newton-AGE method [14]. For single sweep Newton-AGE method, we use the technique given by Evans [16]. The right hand side function and boundary conditions may be obtained using the exact solutions. Here, we have taken σk=σ=a constant, k=1(1)N+1. The value of the first mesh spacing on the left is given by
(57)h1=(b-a)(1-σ)(1-σN+1),σ≠1.Therefore, given the value ofN and σ, we can calculate h1 from the above relation and the remaining mesh points are determined by hk+1=σhk, k=1(1)N. The initial vector y(0)=0 is used in all iterative methods and the iterations were stopped when the absolute error tolerance |y(s+1)-y(s)|≤10-10 was achieved.Example 1 (linear singular problem).
Consider(58)y′′+αxy′=f(x),0<x<1.
The exact solution is y(x)=ex4. The root mean square errors (RMSE), the maximum absolute errors (MAE), and number of iterations both for single and double sweep AGE methods are tabulated in Table 1 for α=1, σ=0.7, α=2,σ=1.1, α=1, σ=1.0, and α=2, σ=1.0. The graph of Example 1 of exact solution versus numerical solution is plotted in Figure 1.Table 1
Example1.
N
TAGE
Single sweep AGE
MAE
RMS errors
ω
1
ω
2
Iter
ω
1
ω
2
Iter
α
=
1
,
σ
=
0.7
10
0.441
0.44
38
0.47
0.34
20
0.4062 (−03)
0.2435 (−03)
20
0.286
0.286
59
0.33
0.25
33
0.3604 (−03)
0.1558 (−03)
30
0.25
0.247
77
0.32
0.23
44
0.3592 (−03)
0.1269 (−03)
40
0.218
0.218
75
0.24
0.20
47
0.3592 (−03)
0.1099 (−03)
50
0.203
0.203
86
0.26
0.21
54
0.3592 (−03)
0.9829 (−04)
60
0.202
0.199
96
0.26
0.20
62
0.3592 (−03)
0.8973 (−04)
70
0.194
0.194
100
0.26
0.20
65
0.3592 (−03)
0.8307 (−04)
80
0.149
0.149
79
0.25
0.17
62
0.3592 (−03)
0.7771 (−04)
α
=
2
,
σ
=
1.1
10
0.529
0.524
39
0.51
0.40
23
0.2990 (−02)
0.2910 (−02)
20
0.298
0.297
78
0.34
0.26
44
0.9774 (−03)
0.9580 (−03)
30
0.213
0.213
113
0.29
0.20
63
0.6774 (−03)
0.6672 (−03)
40
0.169
0.168
146
0.16
0.15
81
0.5925 (−03)
0.5855 (−03)
50
0.142
0.141
178
0.14
0.13
101
0.5633 (−03)
0.5579 (−03)
60
0.124
0.124
180
0.14
0.12
113
0.5525 (−03)
0.5481 (−03)
70
0.112
0.112
201
0.14
0.12
118
0.5484 (−03)
0.5446 (−03)
80
0.103
0.103
221
0.13
0.10
128
0.5469 (−03)
0.5435 (−03)
α
=
1
,
σ
=
1.0
10
0.57
0.37
47
0.46
0.34
26
0.4258 (−03)
0.3739 (−03)
20
0.31
0.23
115
0.25
0.239
75
0.3371 (−04)
0.2934 (−04)
30
0.20
0.19
204
0.203
0.183
128
0.7197 (−05)
0.6256 (−05)
40
0.17
0.15
309
0.19
0.17
225
0.2367 (−05)
0.2058 (−05)
50
0.14
0.14
445
0.1749
0.173
362
0.9928 (−06)
0.8634 (−06)
60
0.13
0.13
623
0.179
0.164
503
0.4864 (−06)
0.4232 (−06)
70
0.125
0.124
842
0.177
0.163
681
0.2654 (−06)
0.2310 (−06)
80
0.124
0.123
1117
0.176
0.163
888
0.1567 (−06)
0.1365 (−06)
α
=
2
,
σ
=
1.0
10
0.59
0.42
40
0.45
0.39
24
0.5725 (−03)
0.5344 (−03)
20
0.32
0.25
86
0.34
0.25
45
0.4488 (−04)
0.4152 (−04)
30
0.20
0.19
131
0.21
0.18
73
0.9532 (−05)
0.8792 (−05)
40
0.16
0.14
180
0.16
0.14
99
0.3125 (−05)
0.2877 (−05)
50
0.12
0.12
228
0.11
0.10
126
0.1307 (−05)
0.1202 (−05)
60
0.1
0.1
274
0.10
0.09
151
0.6392 (−06)
0.5876 (−06)
70
0.08
0.08
332
0.09
0.08
176
0.3485 (−06)
0.1890 (−06)
80
0.07
0.07
382
0.08
0.07
202
0.2058 (−06)
0.1890 (−06)Figure 1
Graph of exact solution and the numerical solution for alpha = 2.0, sigma = 1.1, andN=80 for Example 1.Example 2 (Burgers’ equation).
Consider(59)vy′′=(y-12)y′,0<x<1.
The exact solution is given by y(x)=(1/2)[1-tanh(x/4v)], where v=Re-1. The RMSE, MAE, and the number of iterations for both single and double sweep AGE methods are tabulated in Table 2 for Re=50, σ=1.1, Re=10, σ=1.4, and Re=50, σ=1.0. The graph of Example 2 of exact solution versus numerical solution for N=60, Re=50, σ=1.0 is plotted in Figure 2.Table 2
Example2.
N
TAGE
Single sweep AGE
MAE
RMS errors
ω
1
ω
2
Iter
ω
1
ω
2
Iter
R
e
=
10
,
σ
=
1.4
10
0.0578
0.0585
6
0.0568
0.0568
6
0.1067(−03)
0.6084(−04)
20
0.0368
0.0374
7
0.0281
0.0285
7
0.8511(−04)
0.3726(−04)
30
0.0318
0.0321
8
0.0320
0.0315
7
0.8442(−04)
0.3028(−04)
40
0.0282
0.0286
9
0.0170
0.0170
8
0.8440(−04)
0.2622(−04)
50
0.0236
0.0239
10
0.0160
0.0166
8
0.8440(−04)
0.2345(−04)
60
0.0161
0.0162
10
0.0161
0.0166
8
0.8440(−04)
0.2141(−04)
R
e
=
50
,
σ
=
1.1
10
0.0152
0.0155
5
0.016
0.016
4
0.8156(−03)
0.3181(−03)
20
0.0093
0.0096
6
0.009
0.0089
5
0.3228(−04)
0.1508(−04)
30
0.0063
0.0068
7
0.006
0.0059
7
0.8624(−05)
0.4435(−05)
40
0.0044
0.0045
10
0.0032
0.0042
9
0.5159(−05)
0.2771(−05)
50
0.0036
0.0035
12
0.002
0.0031
12
0.4238(−05)
0.2232(−05)
60
0.0029
0.0029
10
0.0027
0.00278
15
0.3917(−05)
0.1968(−05)
R
e
=
50
,
σ
=
1.0
10
0.006
0.014
5
0.005
0.014
4
0.3335(−02)
0.1197(−02)
20
0.012
0.012
5
0.008
0.0089
4
0.3326(−03)
0.9523(−04)
30
0.008
0.008
6
0.008
0.008
4
0.7487(−04)
0.2147(−04)
40
0.0061
0.0061
7
0.0051
0.0053
5
0.2502(−04)
0.7150(−05)
50
0.0049
0.0049
8
0.0058
0.0049
5
0.1055(−04)
0.3012(−05)
60
0.0041
0.0041
9
0.0043
0.0041
5
0.5186(−05)
0.1478(−05)Figure 2
Graph of the exact solution and the numerical solution forR=50, sigma = 1.0, and N=60 for Example 2.Example 3 (Burgers’ equation in polar coordinates).
Consider(60)1Re(y′′+αxy′-αx2y)=yy′+f(x),0<x<1.
The exact solution is given by y(x)=x2cosh⁡(x). The RMSE, MAE, and the number of iterations for both single and double sweep AGE methods are tabulated in Table 3 for various values of α,Re, and σ. The graph of Example 3 of exact solution versus numerical solution for N=60, Re=50, α=2, σ=0.9 is plotted in Figure 3.Table 3
Example3.
N
TAGE
Single sweep AGE
MAE
RMS errors
ω
1
ω
2
Iter
ω
1
ω
2
Iter
α
=
1
,
R
e
=
10
,
σ
=
1.3
10
0.0368
0.0373
8
0.050
0.052
5
0.8036(−03)
0.2692(−03)
20
0.0329
0.0334
9
0.034
0.046
6
0.7645(−03)
0.1770(−03)
30
0.0297
0.0311
10
0.017
0.034
7
0.7605(−03)
0.1436(−03)
40
0.0283
0.0287
10
0.023
0.0242
8
0.7602(−03)
0.1243(−03)
50
0.0261
0.0269
10
0.025
0.027
8
0.7602(−03)
0.1112(−03)
60
0.0242
0.0251
10
0.0211
0.0218
9
0.7602(−03)
0.1015(−03)
α
=
2
,
R
e
=
10
,
σ
=
1.2
10
0.0554
0.0562
7
0.0555
0.0559
5
0.6954(−03)
0.2261(−03)
20
0.0457
0.0464
9
0.035
0.037
7
0.4545(−03)
0.1034(−04)
30
0.0403
0.0412
10
0.027
0.029
8
0.4245(−03)
0.7896(−04)
40
0.0381
0.0393
10
0.025
0.030
9
0.4198(−03)
0.6765(−04)
50
0.0359
0.0364
10
0.03
0.033
9
0.4191(−03)
0.6040(−04)
60
0.0326
0.0335
10
0.022
0.029
10
0.4190(−03)
0.5512(−04)
α
=
1
,
R
e
=
50
,
σ
=
0.9
10
0.0204
0.0211
8
0.016
0.020
7
0.8035(−03)
0.3961(−03)
20
0.0183
0.0189
8
0.011
0.014
6
0.5906(−03)
0.1492(−03)
30
0.0079
0.0084
9
0.007
0.0072
7
0.5252(−03)
0.1101(−03)
40
0.0056
0.0067
11
0.0051
0.0052
9
0.5044(−03)
0.9227(−04)
50
0.0036
0.0041
15
0.0043
0.0043
12
0.4973(−03)
0.8159(−04)
60
0.0034
0.0035
17
0.0032
0.0034
16
0.4949(−03)
0.7419(−04)
α
=
2
,
R
e
=
50
,
σ
=
0.9
10
0.0198
0.0211
8
0.016
0.017
7
0.4542(−03)
0.3755(−03)
20
0.0172
0.0181
8
0.011
0.018
6
0.6976(−04)
0.4929(−04)
30
0.0069
0.0072
9
0.007
0.008
7
0.4018(−04)
0.2422(−04)
40
0.0064
0.0064
10
0.0065
0.0057
8
0.3333(−04)
0.1789(−04)
50
0.0045
0.0043
13
0.0036
0.0041
12
0.3124(−04)
0.1525(−04)
60
0.0035
0.0034
17
0.0043
0.0033
15
0.3054(−04)
0.1372(−04)
α
=
1
,
R
e
=
50
,
σ
=
1.0
10
0.0174
0.0177
10
0.01
0.027
8
0.1217(−02)
0.5654(−03)
20
0.009
0.011
12
0.0113
0.0115
9
0.1044(−03)
0.4913(−04)
30
0.0063
0.0065
14
0.0072
0.0077
10
0.4547(−04)
0.1367(−04)
40
0.0063
0.0069
16
0.0054
0.0056
11
0.2617(−04)
0.6119(−05)
50
0.0042
0.0046
18
0.0044
0.0045
12
0.1697(−04)
0.3416(−05)
60
0.0034
0.0039
21
0.0032
0.0041
13
0.1188(−04)
0.2152(−05)
α
=
2
,
R
e
=
50
,
σ
=
1.0
10
0.017
0.025
9
0.015
0.026
7
0.1234(−02)
0.5767(−03)
20
0.0101
0.011
11
0.0118
0.0118
9
0.1058(−03)
0.4505(−04)
30
0.0071
0.0083
13
0.0075
0.0075
10
0.2644(−04)
0.1025(−04)
40
0.0054
0.0063
15
0.0049
0.0058
11
0.1502(−04)
0.3813(−05)
50
0.0043
0.0049
17
0.0038
0.0049
12
0.9686(−05)
0.1870(−05)
60
0.0035
0.004
20
0.0042
0.0044
11
0.6762(−05)
0.1084(−05)Figure 3
Graph of the exact solution and the numerical solution for alpha = 2.0,R=50, sigma = 0.9, and N=60 for Example 3.


## 6. Discussion and Conclusion

We have discussed a new single sweep AGE iterative method and three-point off-step method of accuracyO(hk3) on a variable mesh for the solution of nonlinear two point boundary value problems. To demonstrate the efficiency of the method, three examples including two nonlinear and singular cases are presented. The results obtained are compared with the corresponding double sweep AGE method and show superiority over the latter. The double sweep AGE method requires two sweeps to solve a problem, whereas the single sweep AGE method requires only one sweep to solve the problem. Experimentally, as compared to the double sweep method the corresponding single sweep method requires much less number of iterations as it uses less intermediate variables. The method can be extended to solve multidimensional problems and is suitable for use on parallel computers.



---

*Source: 853198-2014-01-16.xml*