# Convergence Analysis of an Iterative Method for Nonlinear Partial Differential Equations

Authors: Hung-Yu Ke; Ren-Chuen Chen; Chun-Hsien Li
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We will combine linear successive overrelaxation method with nonlinear
monotone iterative scheme to obtain a new iterative method for solving nonlinear equations. The
basic idea of this method joining traditional monotone iterative method (known as the method
of lower and upper solutions) which depends essentially on the monotone parameter is that by
introducing an acceleration parameter one can construct a sequence to accelerate the convergence.
The resulting increase in the speed of convergence is very dramatic. Moreover, the sequence can
accomplish monotonic convergence behavior in the iterative process when some suitable acceleration
parameters are chosen. Under some suitable assumptions in aspect of the nonlinear function and
the matrix norm generated from this method, we can prove the boundedness and convergence of
the resulting sequences. Application of the iterative scheme is given to a logistic model problem
in ecology, and numerical results for a test problem with known analytical solution are given to
demonstrate the accuracy and efficiency of the present method.


---

## Body

## 1. Introduction

In terms of solving linear equations, we usually use two different iterative methods, namely, the Jacobi and Gauss-Seidel methods [1–3]. The monotone iterative (MI) schemes which combine linear iterative techniques, respectively, are presented and analyzed in [4–8] for solving nonlinear equations. The method of monotone iterations is a classical tool for the study of the existence of solutions of semilinear PDEs of certain types [9–12]. It is also useful for numerical solutions of these types of problems approximated, for instance, by the finite difference [5, 6, 13–15], finite element [16], or boundary element [17, 18] method. It is a constructive method that depends essentially on only one parameter, called the monotone parameter herein, which determines the convergent behavior of the iterative process. Besides, the block Picard, block Jacobi, and block Gauss-Seidel MI methods are also developed and compared the rates of convergence with the point MI schemes [6]. The block MI methods accelerate the rate of convergence more than the point MI methods. In particular, Ortega and Rheinboldt [19, page 456] mention an analysis of the Newton-SOR methods to research some properties of convergence for relaxation factor 0<ω<1. The MI methods have been widely used in the treatment of certain nonlinear parabolic and elliptic differential equations. For instance, in the study of certain subsonic flows and molecular interactions, the equation Δu=u2 is of fundamental importance [18]. For parabolic problems with time delays we refer to [20]. In addition, we also utilize MI schemes to handle nonlinear problems on analysis of numerical results for semiconductor equations [21–23] and the Poisson Boltzmann equation [24].Consider the nonlinear boundary-value problem:(1)-[(D(1)ux)x+(D(2)uy)y]=f(x,y,u),inΩ,α∂u∂v+βu=g(x,y),on∂Ω,
in a two-dimensional domain Ω with boundary ∂Ω, where ∂u/∂v is the outward normal derivative of u on ∂Ω, D(l)≡D(l)(x,y), l=1,2, are positive functions on Ω¯≡Ω∪∂Ω, α≡α(x,y) and β≡β(x,y) are nonnegative functions on ∂Ω with α+β>0, and f and g are given functions in their respective domains. For the nonlinear function f, we give two assumptions:(i)
(H1)fisuniformlyboundedfor-∞<u<∞;(ii)
if|u|,|v|≤c, then there exists a function ℋ(c), such that for all x,y∈Ω we have
(H2)|f(x,y,u)-f(x,y,v)|≤ℋ(c)·|u-v|.Applying the finite difference method to (1), we obtain a system of nonlinear algebraic equations in a compact form:
(2)AU=F(U)+G*.
Suppose that A can be written in the splitting form A=𝒟-ℒ-𝒰, where 𝒟, -ℒ, and -𝒰 are the diagonal, lower-off-diagonal, and upper-off-diagonal matrices of A, respectively. We consider that linear SOR method can be combined with nonlinear MI scheme to obtain a nonlinear SOR monotone iterative method for solving nonlinear equations which gives rise to the terminology “SORMI”. The basic idea of this method joining MI method which depends essentially on the monotone parameter Γ is that by introducing an acceleration parameter one can construct a sequence to accelerate the convergence. The algorithm is similar to the SOR method. Roughly speaking, given an initial vector U(0), the SORMI method generates a sequence of iterates {U(m)}, m=0,1,…, by solving the equation:
(3)(𝒟+Γ-ωℒ)U(m+1)=[(1-ω)(𝒟+Γ)+ω𝒰]U(m)+ω[ΓU(m)+F(U(m))+G*],
where ω is a relaxation factor. Under some suitable assumptions in aspect of the nonlinear function and the matrix norm generated from this method, we can prove the boundedness and convergence of the resulting sequences. Moreover, the sequences can accomplish monotonic convergence in the iterative process when some suitable relaxation factors are chosen.The structure of the paper is as follows. In Section2, we briefly make a description for discretization process to obtain algebraic equations for model (1) and state some properties of the matrix. Section 3 deals with the monotone parameter and constructs the SORMI scheme. We show the boundedness and convergence of the SORMI sequence in Sections 4 and 5. Moreover, we offer another proof for the convergence of the SORMI sequence in the case 0<ω<1. In Section 6, we solve a one dimensional problem, and a logistic model in population growth problem and numerical results of the method are also given to verify the theoretical analysis. The final section is for some concluding remarks.


## 2. A Finite Difference Discretization

We discuss problem (1) in a rectangular domain Ω=(0,l1)×(0,l2). Let h=l1/n, k=l2/m, and let xi=ih, yj=jk for i=0,1,2,…,n, j=0,1,2,…,m. The set of points (xi,yj) in Ω and Ω¯≡Ω∪∂Ω are defined, respectively, by Υ and Υ¯. When no confusion arises we write a point (xi,yj) in Υ¯ by (i,j)∈Υ¯. Define
(4)ui,j=u(xi,yj),fi,j(ui,j)=f(xi,yj,u(xi,yj)),gi,j=g(xi,yj).
The finite difference method for differential and boundary operators in (1) leads to a discrete system in the form
(5)aijuij-bijui-1,j-bij′ui+1,j-cijui,j-1-cij′ui,j+1=hkfij(uij)+gij*,
for all (i,j)∈Υ¯, where the coefficients aij, bij, bij′, cij, and cij′ are associated with the diffusion coefficients Dij(l)≡D(l)(xi,yj), l=1,2, as well as the boundary coefficients αij≡α(xi,yj) and βij≡β(xi,yj), gij* is associated with the boundary functions gij, and
(6)for,m,iib0j=bnj′=ci0=cim′=0fori=0,1,…,n,j=0,1,…,m,gij*=0fori=1,2,…,n-1,j=1,2,…,m-1.
Typical choice of the coefficients in (5) for the interior mesh points is given by
(7)bij=(kh)D(1)(xi-h2,yj),bij′=(kh)D(1)(xi+h2,yj),cij=(hk)D(2)(xi,yj-k2),cij′=(hk)D(2)(xi,yj+k2),aij=bij+bij′+cij+cij′,((i,j)∈Υ)
(e.g., see [25]). For the boundary points (xi,yj), where i=0,n or j=0,m, the above coefficients are associated with the boundary coefficients αij and βij, and possess the property (for the case α>0),
(8)aij≥bij+bij′+cij+cij′fori=0,norj=0,m.
Furthermore, strict inequality in (8) holds for at least one (i,j) when the boundary condition is not of pure Neumann condition. In either case, these coefficients satisfy the condition
(9)bij≥0,bij′≥0,bij+bij′>0,cij≥0,cij′≥0,aij≥bij+bij′+cij+cij′,((i,j)∈Υ¯).
Condition (9) is our basic hypothesis for the boundedness and the convergence of the SORMI sequence. Now we rewrite system (5) in a compact form:
(10)AU=F(U)+G*.Definition 1.
A realn×n matrix A=(aij) with aij≤0 for all i≠j and aii>0 for all 1≤i≤n is an ℳ-matrix if A is nonsingular, and A-1≥0 [2].Obviously,A is a diagonally dominant with strict inequality for at least one (i,j). Since the domain Υ¯ is connected, the above property implies that A is nonsingular, and A-1≥0. Hence, A is an ℳ-matrix. This implies that for any nonnegative diagonal matrix D, (A+D)-1 exists and is nonnegative.Remark 2.
Nonnegative matrices play a crucial role in the theory of matrices. They are important in the study of convergence of iterative methods and arise in many applications including economics, queuing theory, and chemical engineering. LetA=(aij) and B=(bij) be two real n×r matrices. Then, A≥B(A>B) if aij≥bij(>bij) for all 1≤i≤n, 1≤j≤r. If O is the null matrix and A≥O(>O), we say that A is a nonnegative (positive) matrix. Since column vectors are n×1 matrices, we will use the terms nonnegative and positive vector throughout. A theorem which has important consequences on the analysis of iterative methods should be stated. Let B be a nonnegative matrix. Then ρ(B)<1 if and only if I-B is nonsingular and (I-B)-1 is nonnegative, where ρ(B) is the spectral radius of B.Remark 3.
In reality, the four conditions in the definition ofℳ-matrix are somewhat redundant, and equivalent conditions that are more rigorous will be (i) aij≤0 for all i≠j, (ii) A is nonsingular, and (iii) A-1≥0. The condition, aii>0 for all i, is implied by the other three. Moreover, let D be the diagonal of A, and B≡I-D-1A. We can also obtain ρ(B)<1. A comparison theorem is as follows.
LetA and B be two n×nℳ-matrices, with A≥B. Then we have B-1≥A-1.Remark 4.
Let us look in more detail at the algebraic system (10) [26, 27]. The connectedness assumption of Ω ensures that A is irreducible. Condition (9) implies that A is irreducibly diagonally dominant [28]. Let A=𝒟-ℬ, where 𝒟 is the diagonal matrix of A. It can be shown that 0<ρ(ℬ)<1, using Perron-Frobenius theorem and the theory of regular splittings. A theorem states the following.
IfA=(aij) is a real n×n matrix with aij≤0 for all i≠j, then the following are equivalent.(i)
A is nonsingular, and A-1>0.(ii)
The diagonal entries ofA are positive real numbers. ℬ is nonnegative, irreducible, and convergent.Thus, we know that A is a diagonally dominant ℳ-matrix.


## 3. The SORMI Method

We now arrive to construct the SORMI sequence.Definition 5.
A vectorU~≡(u~00,u~10,…,u~n0,…,u~0m,u~1m,…,u~nm)T with (n+1)×(m+1) components is called an upper solution of (10) if
(11)AU~≥F(U~)+G*,
and U^≡(u^00,u^10,…,u^n0,…,u^0m,u^1m,…,u^nm)T is called a lower solution of (10) if
(12)AU^≤F(U^)+G*.
We say that U~ and U^ are ordered if U~≥U^. Given any ordered upper and lower solutions U~, U^, we set
(13)〈U^,U~〉≡{U:U^≤U≤U~}.
Define
(14)γij≡max{-∂fij∂u(uij):u^ij≤uij≤u~ij},γij+≡max{0,γij},Γ≡hk·diag(γ-00,γ-10,…,γ-n0,γ-01,000000000000γ-11,…,γ-n1,…,γ-0m,γ-1m,…,γ-nm),
where γ-ij is any nonnegative scalar satisfying γ-ij≥γij+, and u~ij and u^ij are the components of U~ and U^, respectively. Then problem (10) is equivalent to
(15)(A+Γ)U=ΓU+F(U)+G*.
Suppose that A can be written in the splitting form A=𝒟-ℒ-𝒰, where 𝒟, -ℒ, and -𝒰 are the diagonal, lower-off-diagonal, and upper-off-diagonal matrices of A, respectively. The elements of 𝒟 are positive, and those of ℒ and 𝒰 are nonnegative. Given an initial iterate vector U(0), the SOR method for solving the linear system AU=b is
(16)(𝒟-ωℒ)UL(m+1)=[(1-ω)𝒟+ω𝒰]UL(m)+ωb,
where ω is a relaxation factor, and UL(0)=U(0). Moreover, the Gauss-Seidel MI method for solving the nonlinear system (15) is defined by
(17)(𝒟+Γ-ℒ)UGS(m+1)=(Γ+𝒰)UGS(m)+F(UGS(m))+G*.
Thus, we define the SORMI method for solving the nonlinear system (15) by
(18)(𝒟+Γ-ωℒ)Us(m+1)=[(1-ω)(𝒟+Γ)+ω𝒰]Us(m)+ω[ΓUs(m)+F(Us(m))+G*].


## 4. The Boundedness of the SORMI Sequences

Before the convergence analysis of the method, we want to ask whether the SORMI sequences are bounded. Now we consider the property.Lemma 6.
Given a pair of upper and lower solutionsU~, U^ of (10),  let U, V be two vectors with (n+1)×(m+1) components, and U~≥U≥V≥U^. Then
(19)ΓU+F(U)≥ΓV+F(V).Proof .
Letuij and vij be the components of U and V, respectively. By the mean value theorem,
(20)-[f(xi,yj,uij)-f(xi,yj,vij)uij-vij]=-∂fij∂u(wij),
where wij lies between vij and uij. From (14), we have γ-ij≥γij+. Hence
(21)-hk[f(xi,yj,uij)-f(xi,yj,vij)uij-vij]≤hkγij+≤hkγ-ij,hkγ-ij·uij+hkfij(uij)≥hkγ-ij·vij+hkfij(vij).
This completes the proof.In [2, page 83], the theorem is stated as follows.Theorem 7.
IfA≥O is an n×n matrix, then κ>ρ(A) if and only if κI-A is nonsingular, and (κI-A)-1≥O, where ρ(A) is a spectral radius of A.Hence, we quote the above theorem to obtain the following lemma.Lemma 8.
The matrix(𝒟+Γ-ωℒ) in (18) is nonsingular, and (𝒟+Γ-ωℒ)-1 is nonnegative for 0<ω<2.Proof.
From the splitting form ofA and (14), we have (𝒟+Γ-ωℒ)=(aij+hkγ-ij)I-ωℒ, i=0,1,2,…,n, j=0,1,2,…,m, where aij+hkγ-ij>0. Since 0<ω<2, ωℒ≥O, and ωℒ is a strictly lower triangle matrix. It follows that all eigenvalues of ωℒ are zeros, and thus ρ(ωℒ)=0. Hence, aij+hkγ-ij>ρ(ωℒ). By Theorem 7, (𝒟+Γ-ωℒ)-1=[(aij+hkγ-ij)I-ωℒ]-1≥O.Definition 9.
Let the vectorU=(u00,u10,…,un0,…,u0m,u1m,…,unm)T. We define |U|=(|u00|,|u10|,…,|un0|, …,|u0m|,|u1m|,…,|unm|)T.Definition 10.
LetU=(u1,u2,…,un)T∈ℜn. The vector 2-norm is usually defined by ∥U∥=(Σi=1nui2)1/2.Definition 11.
Let∥·∥ be a vector 2-norm. The induced matrix 2-norm of an n×n matrix A is defined by
(22)∥A∥=supU≠0∥AU∥∥U∥.
Let {Us(m)}m=0∞ be a sequence generated by the SORMI method with initial vector Us(0)∈〈U^,U~〉, where U~, U^ are upper and lower solutions of (10), respectively. We have the following.Lemma 12.
∥
U
∥
≤
∥
|
U
^
|
+
|
U
~
|
∥ for any U∈〈U^,U~〉. In fact, ∥U∥=∥|U|∥.Proof.
LetU=(u00,u10,…,un0,…,u0m,u1m,…,unm)T, U^=(u^00,u^10,…,u^n0,…,u^0m,u^1m,…,u^nm)T, U~=(u~00,u~10,…,u~n0,…,u~0m,u~1m,…,u~nm)T. Since U∈〈U^,U~〉, u^ij≤uij≤u~ij for all i=0,1,2,…,n, j=0,1,2,…,m. Hence,
(23)uij≤|uij|≤max{|u^ij|,|u~ij|}≤|u^ij|+|u~ij|,(∑i=0n∑j=0muij2)1/2≤[∑i=0n∑j=0m(|u^ij|+|u~ij|)2]1/2;
that is, ∥U∥≤∥|U^|+|U~|∥ for any U∈〈U^,U~〉.To prove that the SORMI sequences are bounded, we must define several values about matrix and vector norms.Notations and Assumptions. (a) Let M1=def∥U^∥+∥U~∥. By Lemma 12,
(24)∥Us(0)∥≤∥|U^|+|U~|∥≤∥U^∥+∥U~∥=M1.
(b) In (H1), we assume that fij(uij) is uniformly bounded for -∞<uij<∞, and gij* is known boundary value; that is, there exists δ>0 such that |hkfij(uij)+gij*|≤δ for -∞<uij<∞, where h and k are mesh sizes. By Definition 10, (5) and (10), we have
(25)∥F(U)+G*∥≤[(n+1)×(m+1)×δ2]1/2=δN.
(c) Define
(26)M2=∥E∥=∥(𝒟+Γ-ωℒ)-1∥,∥B∥=∥(𝒟+Γ-ωℒ)-1[(1-ω)𝒟+Γ+ω𝒰]∥,
and assume that
(H3)∥B∥<1.
(d) Consider two vectors:
(27)U1=defU^-ω(𝒟+Γ-ωℒ)-1(𝒟+Γ)(U~-U^),U2=defU~+ω(𝒟+Γ-ωℒ)-1(𝒟+Γ)(U~-U^).
Since 0<ω<2, (𝒟+Γ-ωℒ)-1≥O, 𝒟+Γ≥O, and U~≥U^, we know that [ω(𝒟+Γ-ωℒ)-1(𝒟+Γ)(U~-U^)] is a nonnegative vector. It follows that U1≤U^≤U~≤U2. Let
(28)〈U1,U2〉=def{U:U1≤U≤U2},M3=def∥|U1|+|U2|∥.
Then
(29)M3=∥|U1|+|U2|∥≤∥U1∥+∥U2∥=∥U^-ω(𝒟+Γ-ωℒ)-1(𝒟+Γ)(U~-U^)∥+∥U~+ω(𝒟+Γ-ωℒ)-1(𝒟+Γ)(U~-U^)∥≤∥U^∥+ω∥(𝒟+Γ-ωℒ)-1(𝒟+Γ)∥(∥U~∥+∥U~∥)+∥U~∥+ω∥(𝒟+Γ-ωℒ)-1(𝒟+Γ)∥(∥U~∥+∥U~∥)<∞.
(e) Define
(30)M4=max{M1,2δNM2}.Theorem 13.
LetU~, U^ be a pair of ordered upper and lower solutions of (10), respectively, and let {Us(m)}m=0∞ be a sequence generated by (18) with initial vector Us(0)∈〈U^,U~〉. Then, the iterative sequence {Us(m)}m=0∞ is bounded for 0<ω<2.Proof.
By (28) and (30), we can choose a constant M=max{M3,M4/(1-∥B∥)}.
Consider two cases of the sequence{Us(m)}.
Case  1. Let Us(m-1)∈〈U^,U~〉. Then
(31)(𝒟+Γ-ωℒ)Us(m)=[(1-ω)(𝒟+Γ)+ω𝒰]Us(m-1)+ω[ΓUs(m-1)+F(Us(m-1))+G*]≤𝒟Us(m-1)+ΓUs(m-1)-ω𝒟Us(m-1)-ωΓUs(m-1)+ω𝒰Us(m-1)+ω[ΓU~+F(U~)+G*]≤𝒟Us(m-1)+ΓUs(m-1)-ω𝒟Us(m-1)-ωΓUs(m-1)+ω𝒰Us(m-1)+ω[ΓU~+AU~]≤𝒟U~+ΓU~-ω𝒟U^-ωΓU^+ω𝒰U~+ωΓU~+ω𝒟U~-ωℒU~-ω𝒰U~=ω(𝒟+Γ)(U~-U^)+(𝒟+Γ-ωℒ)U~.
By (27) and (𝒟+Γ-ωℒ)-1≥0, we obtain
(32)Us(m)≤U~+ω(𝒟+Γ-ωℒ)-1(𝒟+Γ)(U~-U^)=U2.
Similarly,
(33)(D+Γ-ωℒ)Us(m)≥(𝒟+Γ-ωℒ)U^-ω(𝒟+Γ)(U~-U^),
and thus
(34)Us(m)≥U^-ω(𝒟+Γ-ωℒ)-1(𝒟+Γ)(U~-U^)=U1.
So U1≤Us(m)≤U2. By Lemma 12 and (28), we obtain
(35)∥Us(m)∥≤∥|U1|+|U2|∥=M3≤M.Case  2. Let Us(m-1)∉〈U^,U~〉. Then
(36)(𝒟+Γ-ωℒ)Us(m)=[(1-ω)(𝒟+Γ)+ω𝒰]Us(m-1)+ω[ΓUs(m-1)+F(Us(m-1))+G*]=[(1-ω)𝒟+Γ+ω𝒰]Us(m-1)+ω[F(Us(m-1))+G*].
By (26), we have
(37)Us(m)=(𝒟+Γ-ωℒ)-1[(1-ω)𝒟+Γ+ω𝒰]Us(m-1)+ω(𝒟+Γ-ωℒ)-1[F(Us(m-1))+G*]=BUs(m-1)+ωE[F(Us(m-1))+G*].
Consider the iterative process. An induction argument gives
(38)Us(1)=BUs(0)+ωE[F(Us(0))+G*],Us(2)=BUs(1)+ωE[F(Us(1))+G*]=B{BUs(0)+ωE[F(Us(0))+G*]}+ωE[F(Us(1))+G*]=B2Us(0)+ωBE[F(Us(0))+G*]+ωE[F(Us(1))+G*],⋮Us(m)=BmUs(0)+ωBm-1E[F(Us(0))+G*]+ωBm-2E[F(Us(1))+G*]+⋯+ωBE[F(Us(m-2))+G*]+ωE[F(Us(m-1))+G*].
Hence, from Definition 11, (H3), (24), (25), (26), (30), and 0<ω<2, we obtain
(39)∥Us(1)∥≤∥B∥·∥Us(0)∥+ω·∥E∥·∥F(Us(0))+G*∥≤M1∥B∥+2δNM2≤M4(∥B∥+1)≤M41-∥B∥≤M,∥Us(2)∥≤∥B∥2∥Us(0)∥+ω∥B∥·∥E∥·∥F(Us(0))+G*∥+ω∥E∥·∥F(Us(1))+G*∥≤M1∥B∥2+2δNM2∥B∥+2δNM2≤M4(∥B∥2+∥B∥+1)≤M41-∥B∥≤M,⋮∥Us(m)∥≤∥B∥m∥Us(0)∥+ω∥B∥m-1∥E∥·∥F(Us(0))+G*∥+ω∥B∥m-2∥E∥·∥F(Us(1))+G*∥+⋯+ω∥B∥·∥E∥·∥F(Us(m-2))+G*∥+ω∥E∥·∥F(Us(m-1))+G*∥≤M4(∥B∥m+⋯+∥B∥+1)≤M41-∥B∥≤M.
Thus, by Cases 1 and 2, there exists M>0, such that ∥Us(m)∥≤M for all m∈{0}∪𝒩, and the proof is completed.


## 5. The Convergence of the SORMI Sequences

In(H2), we assume that if |u|,|v|≤c, then there is a function ℋ(c), such that |f(x,y,u)-f(x,y,v)|≤ℋ(c)·|u-v|. From Theorem 13, we have shown the boundedness of the SORMI sequences; that is, there exists a constant M such that ∥Us(k)∥<M=max{M3,M4/(1-∥B∥)}. Let ck satisfy max0≤i≤m,0≤j≤n|uij(k)|≤ck. So 0≤ck<M for all k. Let c0=supk=1,2,…{ck}. c0 exists and 0≤c0<M. Hence, we can find the constant λ=defℋ(c0). So we have
(40)|f(xi,yj,uij)-f(xi,yj,vij)|≤λ|uij-vij|,|hkf(xi,yj,uij)-hkf(xi,yj,vij)|≤λhk|uij-vij|,|F(U)-F(V)|≤λhk|U-V|.
Then we obtain the inequality:
(41)∥F(U)-F(V)∥=∥|F(U)-F(V)|∥≤λhk∥|U-V|∥=λhk∥U-V∥.Theorem 14.
LetU~, U^ be a pair of ordered upper and lower solutions of (10), respectively, and let {Us(m)}m=0∞ be a sequence generated by the SORMI method with initial vector Us(0)∈〈U^,U~〉. Suppose that
(H4)η=def∥B∥+ωλhk∥E∥<1,0<ω<2,
where B and E are defined by (26). Then the sequence {Us(m)}m=0∞ is convergent for 0<ω<2.Proof.
By Theorem13, {Us(m)}m=0∞ is bounded for 0<ω<2. Hence, ∃M>0, such that ∥Us(m)∥≤M for all m∈{0}∪𝒩. Since η=∥B∥+ωλhk∥E∥<1, and 0<ω<2, then, for every ε>0, ∃N∈𝒩, such that ηn<ε/2M for all n≥N. Let k≥m≥N. By (37), we have
(42)Us(k)-Us(m)={BUs(k-1)+ωE[F(Us(k-1))+G*]}-{BUs(m-1)+ωE[F(Us(m-1))+G*]}=B(Us(k-1)-Us(m-1))+ωE[F(Us(k-1))-F(Us(m-1))].
Hence, from 0<ω<2 and (41), we obtain
(43)∥Us(k)-Us(m)∥=∥B(Us(k-1)-Us(m-1))2+ωE[F(Us(k-1))-F(Us(m-1))]∥≤∥B∥·∥Us(k-1)-Us(m-1)∥+ω∥E∥·∥F(Us(k-1))-F(Us(m-1))∥≤∥B∥·∥Us(k-1)-Us(m-1)∥+ωλhk∥E∥·∥Us(k-1)-Us(m-1)∥=(∥B∥+ωλhk∥E∥)·∥Us(k-1)-Us(m-1)∥=η∥Us(k-1)-Us(m-1)∥.
Inductively we have
(44)∥Us(k)-Us(m)∥≤ηm∥Us(k-m)-Us(0)∥.
Hence,
(45)∥Us(k)-Us(m)∥≤ηm∥Us(k-m)-Us(0)∥≤ηm(∥Us(k-m)∥+∥Us(0)∥)≤ηm×2M<ε2M×2M=ε.
We have proved that {Us(m)}m=0∞ is a Cauchy sequence for 0<ω<2. It implies that {Us(m)}m=0∞ is convergent for 0<ω<2.Furthermore, we provide another proof about the convergence of the SORMI sequences for0<ω<1 without the assumptions (H3) and (H4). Denote the sequence by {U¯s(m)}m=0∞ when U(0)=U~ and by {U_s(m)}m=0∞ when U(0)=U^, and refer to them as the maximal and minimal sequences, respectively. The following theorem gives some monotone property of these sequences.Theorem 15.
The maximal and minimal sequences{U¯s(m)}m=0∞ and {U_s(m)}m=0∞ given by (18) with U~=U¯s(0) and U^=U_s(0) possess the monotone property
(46)U^≤U_s(m)≤U_s(m+1)≤U¯s(m+1)≤U¯s(m)≤U~,m=1,2,….
Moreover for each m, U¯s(m) and U_s(m) are ordered upper and lower solutions.Proof.
We will use induction to complete the proof of monotone property. First, letW(0)=U¯s(0)-U¯s(1)=U~-U¯s(1). From (11), (18), and 0<ω<1,
(47)(𝒟+Γ-ωℒ)W(0)=(𝒟+Γ-ωℒ)U~-(𝒟+Γ-ωℒ)U¯s(1)=(𝒟+Γ-ωℒ)U~-{[ΓU¯s(0)+F(U¯s(0))+G*][ΓU¯s(0)+F(U¯s(0))+G*][(1-ω)(𝒟+Γ)+ω𝒰]U¯s(0)i+ω[ΓU¯s(0)+F(U¯s(0))+G*]}=ω(𝒟-ℒ-𝒰)U~-ω[F(U~)+G*]=ω{AU~-[F(U~)+G*]}≥0.
By Lemma 8, we obtain W(0)≥0. This leads to U¯s(1)≤U¯s(0). Similarly let V(0)=U_s(0)-U_s(1)=U^-U_s(1), and use (12) to obtain
(48)(𝒟+Γ-ωℒ)V(0)=ω{AU^-[F(U^)+G*]}≤0.
Since (𝒟+Γ-ωℒ)-1≥0, it implies that U_s(1)≥U_s(0). Secondly, let W(1)=U¯s(1)-U_s(1). By (18),
(49)(𝒟+Γ-ωℒ)W(1)=(𝒟+Γ-ωℒ)U¯s(1)-(𝒟+Γ-ωℒ)U_s(1)={[ΓU¯s(0)+F(U¯s(0))+G*][ΓU¯s(0)+F(U¯s(0))+G][(1-ω)(𝒟+Γ)+ω𝒰]U¯s(0)000+ω[ΓU¯s(0)+F(U¯s(0))+G*]}-{[ΓU_s(0)+F(U_s(0))+G*][(1-ω)(𝒟+Γ)+ω𝒰]U_s(0)+ω[ΓU_s(0)+F(U_s(0))+G*]}={(1-ω)(𝒟+Γ)+ω𝒰}×(U¯s(0)-U_s(0))+ω[Γ(U¯s(0)-U_s(0))+F(U¯s(0))-F(U_s(0))(U¯s(0)-U_s(0))].
We have from Lemma 6, U¯s(0)≥U_s(0), and the nonnegative property of [(1-ω)(𝒟+Γ)+ω𝒰] that (𝒟+Γ-ωℒ)W(1)≥0. It follows from Lemma 8 again that W(1)≥0. The above conclusions imply that
(50)U_s(0)≤U_s(1)≤U¯s(1)≤U¯s(0).
We finally assume that U_s(m-1)≤U_s(m)≤U¯s(m)≤U¯s(m-1) for some m>1. Let W(m)=U¯s(m)-U¯s(m+1), and by (18) we have
(51)(𝒟+Γ-ωℒ)W(m)={(1-ω)(𝒟+Γ)+ω𝒰}×(U¯s(m-1)-U¯s(m))+ω[Γ(U¯s(m-1)-U¯s(m))0000+F(U¯s(m-1))-F(U¯s(m))].
Since U¯s(m)≤U¯s(m-1), we have (𝒟+Γ-ωℒ)W(m)≥0. So W(m)≥0 which shows that U¯s(m+1)≤U¯s(m). Similarly, let V(m)=U_s(m)-U_s(m+1) and W(m+1)=U¯s(m+1)-U_s(m+1) simultaneously. We see that
(52)(𝒟+Γ-ωℒ)V(m)={(1-ω)(𝒟+Γ)+ω𝒰}×(U_s(m-1)-U_s(m))+ω[Γ(U_s(m-1)-U_s(m))2221+F(U_s(m-1))-F(U_s(m))]≤0,(𝒟+Γ-ωℒ)W(m+1)={(1-ω)(𝒟+Γ)+ω𝒰}×(U¯s(m)-U_s(m))+ω[Γ(U¯s(m)-U_s(m))2221+F(U¯s(m))-F(U_s(m))]≥0.
By (𝒟+Γ-ωℒ)-1≥0, we have V(m)≤0, and W(m+1)≥0. Hence, U_s(m)≤U_s(m+1), and U¯s(m+1)≥U_s(m+1). The proof of monotone property (46) is completed.
To show thatU¯s(m) is an upper solution for each m, we observe from (18) that
(53)(𝒟+Γ-ωℒ)U¯s(m)={[ΓU¯s(m-1)+F(U¯s(m-1))+G*][ΓU¯s(m-1)+F(U¯s(m-1))+G*][(1-ω)(𝒟+Γ)+ω𝒰]U¯s(m-1)0ii+ω[ΓU¯s(m-1)+F(U¯s(m-1))+G*]},ω𝒟U¯s(m)-ωℒU¯s(m)=ω𝒟U¯s(m)-𝒟U¯s(m)+𝒟U¯s(m-1)-ω𝒟U¯s(m-1)+ΓU¯s(m-1)-ΓU¯s(m)+ω𝒰U¯s(m-1)+ωF(U¯s(m-1))+ωG*,ω𝒟U¯s(m)-ωℒU¯s(m)=(1-ω)𝒟(U¯s(m-1)-U¯s(m))+ω𝒰U¯s(m-1)+Γ(U¯s(m-1)-U¯s(m))+ωF(U¯s(m-1))+ωG*.
By 0<ω<1 and (46), we obtain
(54)ω𝒟U¯s(m)-ωℒU¯s(m)≥ω𝒰U¯s(m)+ωΓ(U¯s(m-1)-U¯s(m))+ωF(U¯s(m-1))+ωG*,ω(𝒟-ℒ-𝒰)U¯s(m)≥ω[Γ(U¯s(m-1)-U¯s(m))+F(U¯s(m-1))+G*],AU¯s(m)≥Γ(U¯s(m-1)-U¯s(m))+F(U¯s(m-1))+G*.
By Lemma 6, we have
(55)AU¯s(m)≥F(U¯s(m))+G*.
This shows that U¯s(m) is an upper solution for each m. Similarly, we have
(56)AU_s(m)≤F(U_s(m))+G*;
that is, for each m, U_s(m) is a lower solution, and thus the proof is completed.Theorem 16.
LetU~, U^ be a pair of ordered upper and lower solutions of (10). Then the sequences {U¯s(m)}m=0∞, {U_s(m)}m=0∞ given by (18) with U¯s(0)=U~ and U_s(0)=U^ converge monotonically to solutions U¯s and U_s of (10), respectively, where
(57)U¯s=def(u-00,u-10,…,u-n0,…,u-0m,u-1m,…,u-nm)T,U_s=def(u_00,u_10,…,u_n0,…,u_0m,u_1m,…,u_nm)T.
Moreover,
(58)U^≤U_s(m)≤U_s(m+1)≤U_s≤U¯s≤U¯s(m+1)≤U¯s(m)≤U~,00000000000000000000000000000000im=1,2,…,
and if U* is any solution in 〈U^,U~〉, then U_s≤U*≤U¯s.Proof.
By Theorem15, the limits limU¯(m)=U¯s and limU_(m)=U_s as m→∞ exist, and the relation (58) also holds. Letting m→∞ in (18) shows that U¯s and U_s are solutions of (15). The equivalence between (10) and (15) ensures that U¯s and U_s are solutions of (10). Now if U* is a solution in 〈U^,U~〉, then U~ and U* are ordered upper and lower solutions. Using U¯s(0)=U~ and U_s(0)=U*, Theorem 15 implies that U¯s(m)≥U* for every m. Letting m→∞ gives U¯s≥U*. A similar argument using U* and U^ as ordered upper and lower solutions yields U*≥U_s. This proves the theorem.In Theorem16, U¯s and U_s are often called maximal and minimal solutions in 〈U^,U~〉, respectively. In general, these two solutions are not necessarily the same. Let A be symmetric. Then A has real and positive eigenvalues [2]. However, if σ<μ_, where μ_ is the smallest positive eigenvalue of A and
(59)σ≡max{∂fij∂u(uij):u^ij≤uij≤u~ij,(i,j)∈Υ¯},
then the following theorem holds.Theorem 17.
Let the conditions in Theorem16 hold. If either σ≤0 or σ<μ_ and A is symmetric, then U¯s=U_s and is the unique solution of (10).Proof.
LetW=U¯s-U_s and u-ij and u_ij be the components of U¯s and U_s, respectively. By (58), we have W≥0. On the other hand, by the mean value theorem, we have
(60)f(xi,yj,u-ij)-f(xi,yj,u_ij)u-ij-u_ij=∂fij∂u(uij)≤σ,
where uij lies between u_ij and u-ij. Hence,
(61)AW=A(U¯s-U_s)=AU¯s-AU_s=F(U¯s)+G*-F(U_s)-G*=F(U¯s)-F(U_s)≤σ(U¯s-U_s)=σW,
and thus
(62)(A-σI)W≤0.Case  1. If σ≤0. From the form of A, (A-σI) is strictly diagonally dominant. It follows that (A-σI)-1≥0, and thus W≤0.
Case  2. If σ<μ_. Since μ_ is the smallest positive eigenvalue of A, then μ_-1 is the biggest positive eigenvalue of A-1. From Theorem 7 and A-1≥0, we have
(63)σ-1>μ_-1≥ρ(A-1),(σ-1I-A-1)-1≥0,σ-1A-1(σ-1I-A-1)-1≥0,(A-σI)-1≥0.
Hence, W≤0. So we know that W=0. This proves U¯s=U_s. The uniqueness follows from the relation U¯s≥U*≥U_s for any solution U*∈〈U^,U~〉.Remark 18.
For system (1), the well-known method of upper and lower solutions with SORMI is applied for the case 0<ω<1 (see Theorems 15, 16, and 17). However, the nonnegative property of (1-ω)(𝒟+Γ)+ω𝒰 is not available when ω>1. A new approach for solving this problem by the boundedness of the SORMI sequences and Cauchy sequence property is proposed. To make sure of the convergence of the SORMI sequences, the assumptions (H1), (H2), and (H3) are necessary. But it should be pointed out that these constraints are not easy to be verified. It is important to weaken these constraints when the SORMI method is applied to realistic problems. Fixed point theory is a powerful tool to overcome this problem for further study.


## 6. Numerical Results

Assume that the matrixA of (10) is an n×n matrix. The componentwise SORMI algorithm is given as follows:
(64)ui(m+1)=ω[(∑j=1i-1aijuj(m+1)+∑j=i+1naijuj(m)+γ-iui(m)+hkfi(ui(m))+gi*∑j=1i-1aijuj(m+1))(aii+γ-i)-1(∑j=1i-1aijuj(m+1)+∑j=i+1naijuj(m)]+(1-ω)ui(m),i=1,…,n.
Another equivalent form is
(65)ui(m+1)=ω[(∑j=1i-1aijuj(m+1)+∑j=i+1naijuj(m)+hkfi(ui(m))+gi*∑j=1i-1aijuj(m+1))(aii+γ-i)-1]+(1-ωaiiaii+γ-i)ui(m),i=1,…,n.
The main requirement for the application of the various MI schemes is the existence of a pair of ordered upper and lower solutions. To ensure the existence, the nonlinear function f must have some necessary conditions. Hence, in Section 1, we require that fij(uij) is uniformly bounded in ℜ. Now we present some numerical results with two test problems.Example 19.
Consider the one-dimensional boundary value problem:(66)-u′′=-12u+52πsin(2x)-12xsin(2π),12xsinii(2π),0<x<π,u(0)=u(π)=0.
The exact solution is
(67)u(x)=πsin(2x)-xsin(2π).
Let f(x,u)=(-1/2)u+(5/2)πsin(2x)-(1/2)xsin(2π), and choose Γ=diag(2,2,…,2), Us(0)=(0,0,…,0)T. Then,
(68)|f(x,u1)-f(x,u2)|=12|u1-u2|=defℋ(c)|u1-u2|.
Hence we choose λ=1/2. We examine the assumptions (H3) and (H4) and the convergence of the SORMI sequences. The numerical results are given in Table 1, and the exact and approximate solutions are shown in Figure 1. Moreover, we sketch the relation between the numbers of iterations and relaxation factors ω by Figure 2.Table 1
Numbers of iterations andη values for Example 19.
ω
0.2
0.25
0.3
0.4
0.5
0.6
Number of iterations
18330
14745
12268
9046
7024
5626
∥
B
∥
0.9999
0.9998
0.9998
0.9997
0.9997
0.9996
η
0.9999
0.9999
0.9999
0.9999
0.9998
0.9998
ω
0.8
1.0
1.2
1.6
1.8
1.9
Number of iterations
3800
2645
1837
751
342
127
∥
B
∥
0.9994
0.9992
0.9990
0.9985
0.9982
0.9980
η
0.9997
0.9996
0.9995
0.9993
0.9992
0.9991
ω
1.92
1.95
1.96
1.97
1.98
1.99
Number of iterations
151
236
295
381
535
940
∥
B
∥
0.9979
0.9979
0.9979
0.9978
0.9978
0.9978
η
0.9991
0.9990
0.9990
0.9990
0.9990
0.9990Figure 1
The exact and approximate solutions for Example19.Figure 2
Numbers of iterations andω values for Example 19.The numbers of iterations for the SORMI method are listed in Table1. We focus on the SORMI method with ω=1.9. The number of iterations is 127. Compared with it, the Jacobi and Gauss-Seidel MI methods require 4905 and 2645 iterations, respectively. The resulting increase in the speed of convergence is very dramatic. Moreover, the values of ∥B∥ and η in Table 1 are smaller than 1 which verify our theory of the boundedness and convergence for the SORMI method.Example 20.
As the second test problem, consider the logistic model in population growth problem with nonlinear function(69)f(x,y,u)=σu(1-u)+q(x,y),
where σ is a positive constant, and q(x,y) is a possible internal source [6]. The discretized function is given by
(70)fij(uij)=σuij(1-uij)+qij.
For physical reasons, we suppose that f(x,y,u)≥0, q(x,y)≥0, and g(x,y)≥0, such that U^=0 is a lower solution of (10). For upper solution, consider the following.
Case  1.
q
(
x
,
y
)
>
0 and g(x,y)>0. (i) If the upper solution is dependent on σ, define K(1)=σ/4+q-+g-*, V=(K(1),K(1),…,K(1)), and AU~=V. Then U~ is an upper solution, where q- and g-* are any upper bounds of qi,j and gi,j*, respectively. (ii) If upper solution is independent of σ, then U~=P+V* is an upper solution, where P=def(1,1,…,1)T, and Q is the vector with components qi,j which satisfies Q+G*=AV*.
Case  2. (i) If g=0, then U~=(K,K,…,K)T is an upper solution, where K is a constant which satisfies σK(K-1)≥q-. (ii) If q=g=0, then U~=P is an upper solution.
We now give a model problem where the exact solution is known explicitly [6]. This problem is given by
(71)-(uxx+uyy)=σu(1-u)+q(x,y),(u)+iq(x,y),0<x<1,0<y<2,ux(0,y)=u(1,y)=u(x,0)=u(x,2)=0.
It is easy to verify that when σ=π2/4 and
(72)q(x,y)=2sin(πy2)+π24(1-x2)2sin2(πy2),
the exact solution of (71) is given by
(73)u(x,y)=(1-x2)sin(πy2).
Since 0≤q(x,y)≤2+π2/4 for (x,y)∈[0,1]×[0,2], the constant pair U~=(K,K,…,K)T and U^=0 are ordered upper and lower solutions whenever (π2/4)K(K-1)≥2+π2/4 with K=2. Hence, (71) is case 2 whenever g=0, and we have the upper and lower solutions U^=(0,0,…,0)T and U~=(2,2,…,2)T. Let f(x,y,u)=(π2/4)u(1-u)+q(x,y). We define
(74)γ=max0≤u≤2|∂f(x,y,u)∂u|=3π24,Γ=diag(γ,γ,…,γ)T.
If 0≤u1, u2≤c, then
(75)|f(x,y,u1)-f(x,y,u2)|=|σu1(1-u1)+q(x,y)00i-σu2(1-u2)-q(x,y)|=|σu1-σu12-σu2+σu22|=|σ(u22-u12)-σ(u2-u1)|=|σ(u2+u1)(u2-u1)00i-σ(u2-u1)|=|σ(u2+u1-1)(u2-u1)|=σ|u2+u1-1||u1-u2|≤σ|2c-1||u1-u2|=defℋ(c)|u1-u2|.The SORMI method takes 94 iterations withω=1.92 when U(0)=0 is applied. The approximate solution is similar to the exact solution as shown in Figure 3. Since they are similar, we omit to sketch the exact solution figure. In comparison with the SORMI method, the Jacobi and Gauss-Seidel MI methods require 2243 and 1249 iterations, respectively. The reduction of iterations is significant. The numerical results are listed in Table 2. The relation between the numbers of iterations and relaxation factors ω is shown in Figure 4. They verify our theory of the boundedness and convergence for the SORMI method again.Table 2
Numbers of iterations andη values for Example 20.
ω
0.05
0.1
0.2
0.3
Number of iterations
28503
15706
8344
5612
∥
B
∥
0.9999
0.9997
0.9995
0.9992
η
0.9999
0.9998
0.9996
0.9994
ω
0.4
0.5
0.8
1.0
Number of iterations
4155
3239
1775
1249
∥
B
∥
0.9989
0.9986
0.9976
0.9969
η
0.9992
0.9989
0.9982
0.9976
ω
1.2
1.6
1.8
1.9
Number of iterations
881
386
200
104
∥
B
∥
0.9961
0.9943
0.9933
0.9928
η
0.9970
0.9955
0.9947
0.9943
ω
1.92
1.95
1.97
1.99
Number of iterations
94
129
185
307
∥
B
∥
0.9927
0.9925
0.9924
0.9923
η
0.9942
0.9942
0.9942
0.9944Figure 3
The approximate solution for Example20.Figure 4
Numbers of iterations andω values for Example 20.


## 7. Conclusions

A new iterative method for solving nonlinear equations is developed in this paper. It combines SOR method with MI scheme and therefore gives rise to the terminology “SORMI.” The boundedness and convergence of the SORMI sequence are proven under some suitable assumptions. Some numerical examples are given to verify our theory of the boundedness and convergence for the SORMI method. Moreover, the reduction of iterations is quite significant in comparison with the Jacobi and Gauss-Seidel MI methods.



---

*Source: 487273-2013-09-09.xml*