# Newton-PGSS and Its Improvement Method for Solving Nonlinear Systems with Saddle Point Jacobian Matrices

Authors: Yao Xiao; Qingbiao Wu; Yuanyuan Zhang
Journal: Journal of Mathematics
 (2021)

---

## Abstract

The preconditioned generalized shift-splitting (PGSS) iteration method is unconditionally convergent for solving saddle point problems with nonsymmetric coefficient matrices. By making use of the PGSS iteration as the inner solver for the Newton method, we establish a class of Newton-PGSS method for solving large sparse nonlinear system with nonsymmetric Jacobian matrices about saddle point problems. For the new presented method, we give the local convergence analysis and semilocal convergence analysis under Hölder condition, which is weaker than Lipschitz condition. In order to further raise the efficiency of the algorithm, we improve the method to obtain the modified Newton-PGSS and prove its local convergence. Furthermore, we compare our new methods with the Newton-RHSS method, which is a considerable method for solving large sparse nonlinear system with saddle point nonsymmetric Jacobian matrix, and the numerical results show the efficiency of our new method.


---

## Body

## 1. Introduction

In this paper, we will explore effective and convenient methods for solving nonlinear nonsymmetric saddle-point problem:(1)Fx=0,where F:D⊂ℝn⟶ℝn is a continuous differentiable nonlinear function and the function F=F1,…,Fn+mT with Fi=Fix,i=1,2,…, and x=x1,…,xn+mT is defined on an open convex subset of (n + m)-dimensional real linear space ℝn+m. Moreover, the Jacobian matrix F′x is large, sparse, and nonsymmetric saddle point with the form(2)F′x=AxBx−BTx0,where Ax∈ℝn×n is a real positive definite matrix and Bx∈ℝn×m is a full-column rank matrix m<n. This kind of large sparse nonsymmetric saddle-point nonlinear systems (1) always arises in many scientific and engineering computing areas, such as elastomechanics equations and Stokes equation. Some of them have not been solved analytically, so we can only explore the method to obtain the numerical simulation at our utmost.In the past, researchers have developed some methods to solve nonlinear function [1–10]. In these methods, the most typical and popular method for solving the nonlinear system (1) is the Newton method. The principle of solving nonlinear equations by the Newton method is very simple. In each step, we expand the nonlinear equation at xk by Taylor expansion and take its linear part to construct the approximate equation of the nonlinear equation. Then, we calculate the zero point of the approximate equation as the next iteration point, and it is represented as follows:(3)xk+1=xk−F′xk−1Fxk,k=0,1,….The sequencexk calculated by this iteration will converge to the numerical solution eventually as k⟶+∞ under certain conditions. We know that an excellent algorithm is not only accurate but also efficient. When the dimension n is large, the cost of each step of the traditional Newton algorithm is very expensive. The reason for this phenomenon is that, at each iterative step, a linear system(4)F′xksk=−Fxk,k≥0,sk=xk+1−xk,must be exactly and accurately solved. We hope to give up a little bit of “precision” in exchange for greater “efficiency.” This idea led to the development of inexact Newton methods which were first proposed by Dembo et al. [11]. In recent decades, the inexact Newton method has been extensively studied and applied in some fields. The linear equation (4) can be solved efficiently by some methods which will discard some precision, but the calculation amount and time will be greatly reduced. In addition, we know that the traditional Newton method is second-order convergence, and increasing the order of convergence can make the algorithm converge to the exact solution faster. Therefore, we consider improving the Newton method to improve the order of convergence. Next, we introduce the traditional Newton method and the improved Newton method. In the inexact Newton methods, the termination condition of the Newton equation (4) is(5)F′xksk+Fxk≤ηkFxk,k≥0,where sk=xk+1−xk is obtained by applying some linear iterative methods. The inexact Newton methods usually have the unified form as shown in Algorithm 1 .Algorithm 1: Inexact Newton methods.
(1)
Let the initial guessx0 be given.(2)
Fork=0 until “convergence” do:xk+1=xk−F′xk−1Fxk,k=0,1,…,Find someηk∈0,1 and sk that satisfyFxk+F′xksk≤ηkFxk.(3)
Setxk+1=xk+sk.Here,F′xk is the Jacobian matrix and ηk∈0,1 is commonly called forcing term which is used to control the level of accuracy. The algorithm mentioned above has R-order of convergence two at least. The researchers present the modified Newton iteration to improve convergence order as shown in Algorithm 2.Algorithm 2: Inexact-modified Newton methods.
(1)
Let the initial guessx0 be given.(2)
Fork=0 until “convergence” do:xk,1=xk−F′xk−1Fxk,xk,2=xk,1−F′xk−1Fxk,1,…,xk,m−1=xk,m−2−F′xk−1Fxk,m−2xk+1=xk,m=xk,m−1−F′xk−1Fxk,m−1.Find someηk∈0,1 and sk,i,i=1,2…m that satisfyFxk,i+F′xksk,i≤ηk,iFxk.(3)
Setxk,i=xk+sk,i.From what is mentioned above, inexact-modified Newton methods only need to calculateF′xk−1 once per m step and have less computation compared with inexact-modified Newton methods. This kind of method has R-order of convergence m+1 at least as the outer iteration and the PGSS iteration method as the inner iteration. In this paper, we can establish the modified Newton-PGSS as m = 2.The inexact Newton methods consist of two parts: inner iteration and outer iteration. The outer iteration is the Newton method, which is used to solve nonlinear problems, and each iteration has to solve a linear equation in order to generate the sequencexk. Linear iterative methods, such as the classical splitting methods or the modern Krylov subspace methods [12, 13], are applied inside the Newton methods to solve the Newton equations approximately. A significant advantage of such inner-outer iterations is that one can reduce the inverse of the Jacobian matrix storage and calculation of each step, so as to improve the operation efficiency. Therefore, this kind of inner-outer iterative methods has been widely studied. Newton–Krylov subspace [3] methods which utilize the Krylov subspace iteration methods as the inner iterations have been effectively and successfully used in many fields, see [14–16].By introducing the inexact Newton method [1–4, 7, 8], we know that the efficiency of the inner iteration will affect the efficiency of the whole algorithm. Thus, we want to explore the excellent inner iteration to obtain efficient inner-outer iterative methods. In other words, efficient linear iteration should be employed to solve the Newton equation (4) with real nonsymmetric saddle-point Jacobian matrix. There are many ways to solve the saddle point linear problem [3, 17–25]. Recently, Cao et al. [26–29] proposed a method which is based on the shift-splitting iteration method presented by Bai et al. [30] to solve the saddle-point problem. This method is more efficient than other algorithms such as the Uzawa-type iteration methods, the successive over-relaxation (SOR-like) iteration methods [31, 32], and the Hermitian and skew-Hermitian splitting (HSS) iteration methods [33–35]. In addition, the PGSS iteration method is convergent unconditionally and the preconditioner generated by it is also very excellent [26]. When applying the PGSS method for solving complex linear system, at each iterative step, it needs to solve single linear subsystem with their coefficient matrices being the ℳPGSS one 1/2Ω+A. Furthermore, in order to increase the efficiency of algorithm, we optimized the outer iteration and then we propose modified Newton-PGSS method to solve the saddle problems. Because there was no Newton method to solve the saddle point system problem, we compare the Newton-PGSS method with the traditional methods, for example, the Newton-RHSS method [31, 36, 37].The organization of the paper is as follows. In Section3, we introduce the Newton-PGSS method. In Sections 4 and 5, we offer the convergence properties of this method. We establish local convergence theorem and semilocal convergence properties under some proper hypothesis for the Newton-PGSS method, respectively. We show the modified Newton-PGSS method in Section 6. Numerical examples are presented to confirm the efficiency of our new method in Section 7. Finally, in Section 8, some brief conclusions are given.


## 2. Preliminaries

First of all, we review the PGSS method [26] for solving large sparse nonsymmetric saddle-point linear system:(6)Ax=b,A∈ℝn+m×n+m,x,b∈ℝn,where A∈ℝn+m×n+m is a real nonsymmetric saddle-point matrix.The PGSS Iteration Method [27]. Given an initial guess x0∈ℝn+m, compute xk+1 for k=0,1,2,…, using the following iteration scheme until xk satisfies the stopping criterion:(7)12Ω+Axk+1=12Ω−Axk+b,where Ω is a matrix with the form αI100βI2, where I1 is a n×n identity matrix and I2 is a m× m identity matrix and α and β are real numbers greater than 0. We can get xk+1 from (7) leading to the PGSS iterative scheme:(8)xk+1=Mα,βxk+Gα,βb,where(9)Mα,β=Ω+A−1Ω−A,Gα,β=Ω+A−1.Here,Mα,β is the iteration matrix of the PGSS iteration method.Theorem 1.
(see [27]). A = b∈ℝn+m×n+m is a nonsymmetric saddle-point matrix,α is a nonnegative constant, and β is a positive constant. Then, the iteration matrix Mα,β of PGSS is(10)Mα,β=Ω+A−1Ω−A,which satisfies(11)ρMα,β≤maxλi∈λΩ−1/2AΩ−1/21−λi1+λi≤1.


## 3. The Newton-PGSS Method

In this section, we describe an inner-outer iteration method for solving systems of nonlinear equations with complex symmetric Jacobian matrices.We use Newton methods as outer iteration and apply the PGSS method as the inner solver for the modified Newton method, in other words, the PGSS iteration is employed to solve the following two linear systems:(12)F′xkdk=−Fxk,xk+1=xk+dk.Then, we get the Newton-PGSS method for solving nonlinear system (1).The Newton-PGSS Method. Let F:D⊂ℝn+m⟶ℝn+m be a continuously differentiable function with the complex symmetric Jacobian matrix F′x at any x∈D, and let(13)F′x=AxBx−BTx0,where Ax∈ℝn×n is a real-positive definite matrix and Bx∈ℝn×m is a full column rank matrix m<n. Given an initial guess x0∈D, two positive constants α and β and sequence lkk=0∞ of positive integers, compute xk+1 for k=0,1,2,…, until xk converges. The algorithm can be concluded as Algorithm 3.Algorithm 3: N-PGSS (Newton-PGSS method).
(1)
Given an initial guessx0, a nonnegative constant α, a positive constant β, and a positive integer sequences lkk=0∞.(2)
Fork=0,1,…, until Fxk≤tolFx0 do:(2.1)
Setdk,0=0.(2.2)
Forl=0,1,…,lk−1, apply algorithm PGSS to the linear system (12):Ωxk+F′xkdk,l+1=Ωxk−F′xkdk,l−Fxk,and obtaindk,lk such thatFxk+F′xkdk,lk≤ηkFxk,for someηk∈0,1,whereΩxk=αI1xk00βI2xk.I1isan×nidentity matrix andI2isam×midentity matrix(2.3)
Setxk+1=xk+dk,lk.obtain the following uniform expressions fordk,lk,dk,lk=−∑j=0lk−1Mα,βΩ;xkjGα,βΩ;xkFxk,whereMα,βΩ;x=Ωx+F′x−1Ωx−F′x,andGα,βΩ;x=2Ωx+F′x−1.Then, the Newton-PGSS method can be rewritten asxk+1=xk−∑j=0lk−1Mα,βΩ;xkjGα,βΩ;xkFxk,k=0,1,2,…,From the definitions ofMα,βV;x and Gα,βV;x, we can obtainGα,βΩ;x−1I−Mα,βΩ;x=Gα,βΩ;x−1−Gα,βΩ;x−1Mα,βΩ;x=1/2Ωx+F′x−1/2Ωx+F′xΩx+F′x−1Ωx−F′x=1/2Ωx+F′x−1/2Ωx−F′x=F′x.Then, the Newton-PGSS method can be equivalently expressed asxk+1=xk−I−Mα,βΩ;xklkF′xk−1Fxk,k=0,1,2,…,The Jacobian matrixF′x can be rewritten asF′x=Bα,βΩ;x−Cα,βΩ;x,withBα,βΩ;x=Gα,βΩ;x−1,Bα,βΩ;x−1=I−Mα,βΩ;xF′x−1,Cα,βΩ;x=Gα,βV;x−1Mα,βΩ;x.


## 4. Local Convergence of the Newton-PGSS Method

In this section, we prove the local convergence of Newton-PGSS method under the Hölder condition.LetF:D⊂ℝn⟶ℝn be G-differentiable on an open neighborhood ℕ0⊂D. Suppose F′x=PPGSSx−QPGSSx is modified generalized shift-splitting of the Jacobian matrix F′x, where PPGSSx=1/2Ωx+F′x and QPGSSx=1/2Ωx−F′x and V(x) and W(x) are defined as follows. Suppose F′x is continuous and positive definite at a point x∗∈D, at which Fx∗=0.Denote withℕx∗,r an open ball centered at x∗ with radius r>0.Assumption 1.
For allx∈ℕx∗,r⊂ℕ0, assume the following conditions hold.(A1)
The bounded condition: there exist positive constantsδ and γ such that(14)maxAx∗,Bx∗≤δ,F′x∗−1≤γ.(A2)
The Hölder condition: there exist nonnegative constantsKw and Kt such that(15)Ax−Ax∗≤Kax−x∗p,Bx−Bx∗≤Kbx−x∗p,with the exponentp∈0,1.Remark 1.
We can know the fact that Lipschitz condition is a special case of Hölder condition whenp=1, and we can call Hölder condition Lipschitz. Hence, Lipschitz condition is stronger than Hölder condition.
Now, under Assumption1, we establish the local convergence theorem for the Newton-PGSS, and we can know the properties of function F around the numerical solution x∗ and the information about the radius of the neighborhood. The properties and information mentioned above will affect the given method about the local convergence.Lemma 1.
Under Assumption1, for all x,y∈ℕx∗,r, if r∈0,1/γK1/p, then F′x−1 exists. And, the following inequalities hold with K:=Ka+Kb for all x,y∈ℕx∗,r:(16)F′x−F′x∗≤Kx−x∗p,F′x−1≤γ1−γKx−x∗p,Fx≤K1+px−x∗1+p+2δx−x∗.Proof.
(17)F′x−F′x∗≤Ax−Ax∗Bx−Bx∗−BTx−BTx∗0=Ax−Ax∗000+0Bx−Bx∗−BTx−BTx∗0=Ax−Ax∗+Bx−Bx∗≤Kax−x∗p+Kbx−x∗p=Kx−x∗p.
Since(18)F′x−1F′x−F′x∗≤γKx−x∗p<1,by Banach lemma,Fx−1 exists and inequality(19)F′x−1≤γ1−γKx−x∗p,holds, and(20)Fx∗=Ax∗Bx∗−BTx∗0≤Ax∗000+0Bx∗−BTx∗0≤Ax∗+Bx∗≤2δ.
Moreover, since(21)Fx=Fx−Fx∗−F′x∗x−x∗+F′x∗x−x∗=∫01F′x∗+tx−x∗−F′x∗dtx−x∗+F′x∗x−x∗,it holds that(22)Fx≤∫01F′x∗+tx−x∗−F′x∗dtx−x∗+F′X∗x−x∗≤∫01ktpx−x∗p+1dtx−x∗+2δx−x∗≤K1+px−x∗1+p+2δx−x∗.
This completes the proof of Lemma1.Theorem 2.
Under the assumptions of Lemma1, suppose r∈0,r0 and define r0:=min1≤j≤3r+j, where(23)r+1=τθγK1+θ+τθq,r+2=1−2δτ+1θl04+2p/1+pKγq,r+3=1γKq,with l0=liminfk⟶∞lk, and the constant l0 satisfies(24)l0>−ln2δlnτ+1θ,where the symbol ⋅ is used to denote the smallest integer no less than the corresponding real number, τ∈0,1−θ/θ is a prescribed positive constant, and(25)θ≡θα,β;x∗=Mα,βx∗≤maxλi∈λΩ1/2F′x∗Ω1/21−λi1+λi≡σα,β;x∗<1,where α,β are more than 0.
Then, for anyx∈ℕx∗,r⊂ℕ0,t∈0,r and c>l0, it holds that(26)Mα,βV;x≤τ+1θ<1,gtp;c=γ1−γKtp3+p1+pKtp+2βτ+1θc≤gr0p;l0<1.Proof.
Denote(27)Bα,βΩ;x=Gα,βΩ;x−1,Cα,βΩ;x=Gα,βΩ;x−1Mα,βΩ;x,then(28)Mα,βV;x=Bα,βΩ;x−1Cα,βΩ;x.
From the bounded condition, we have(29)Bα,βΩ;x−Bα,βΩ;x∗≤12F′x−F′x∗≤K2x−x∗p,Bα,βx∗−1=I−Mα,βx∗F′x∗−1≤2γ,and we can get the inequality(30)Bα,βx∗−1Bα,βΩ;x−Bα,βΩ;x∗≤Kγx−x∗p<1.
Hence, by making use of the Banach lemma, we can obtain(31)Bα,βx−1≤2γ1−γKx−x∗p.
Similarly,(32)Cα,βΩ;x−Cα,βΩ;x∗≤12F′x−F′x∗≤K2x−x∗p.Cα,βΩ;x−1≤2γ1−γKx−x∗p.
Then, we have(33)Mα,βΩ;x−Mα,βΩ;x∗=Bα,βx−1Cα,βx−Bα,βx∗−1Cα,βx∗=Bα,βx−1Cα,βx−Cα,βx∗+Bα,βx−1−Bα,βx∗−1Cα,βx∗=Bα,βx−1Cα,βx−Cα,βx∗+Bα,βx−1Bα,βΩ;x∗−Bα,βΩ;xBα,βx∗−1Cα,βx∗≤Bα,βΩ;x−1Cα,βΩ;x−Cα,βΩ;x∗+Bα,βΩ;x−Bα,βΩ;x∗Mα,βΩ;x∗≤−2γ1−γKx−x∗pK2x−x∗p+K2x−x∗pθ=1+θγKx−x∗p1−γKx−x∗p≤τθ.
We can use (33); hence,(34)Mα,βΩ;x≤Mα,βΩ;x−Mα,βΩ;x∗+Mα,βΩ;x∗≤1+τθ<1.
Now, we turn to estimate the error about theNewton−PGSS iteration xk0∞ defined above. Clearly, it holds that(35)xk+1−x∗=xk−x∗−I−Mα,βΩ;xklkF′xk−1Fxk=−F′xk−1F′xk−F′x∗−F′x∗xk−x∗+F′xk−1Fxk−Fx∗xk−x∗+Mα,βΩ;xklkF′xk−1Fxk,where(36)Mα,βΩ;xklkF′xk−1Fxk=Mα,βΩ;xklkF′xk−1Fxk−Fx∗−F′x∗xk−x∗+Mα,βΩ;xklkF′x∗xk−x∗.
Hence, we can obtain(37)Mα,βΩ;xklkF′x∗xk−x∗≤Mα,βΩ;xklkF′xk−1Fxk−Fx∗−F′x∗xk−x∗+F′x∗xk−x∗≤γτ+1θlk1−γKxk−x∗pK1+pxk−x∗1+p+2δxk−x∗,xk+1−x∗≤γ1−γKx−x∗pK1+pxk−x∗1+p+K|xk−x∗1+p+γτ+1θlk1−γKx−x∗pK1+pxk−x∗1+p+2δxk−x∗=γ1−γKxk−x∗p3+p1+pKxk−x∗p+2δτ+1θlk‖xk−x∗‖=gxk−x∗p;lkxk−x∗,where(38)gtp;c=γ1−γKtp3+p1+pKtp+2βτ+1θc.
This function is aboutt increasing and about c decreasing; hence,(39)gxk−x∗p;lk≤gr0p;l0<1.
In fact, fork=0, we havex0−x∗<r<r0, as x0∈ℕx∗,r. It follows that(40)x1−x∗≤gr0p;l0x0−x∗≤x0−x∗<r0.
Hence,x1∈ℕx∗,r, and by making use of mathematical methods of induction, suppose xm∈ℕx∗,r is valid for some positive integer k=m. Then, by making use of the function above again, we can straightforwardly deduce the estimate(41)xm+1−x∗≤gr0p;l0xm−x∗,which show that it also holds true for k=m+1 as the following. In addition, we have(42)xm+1−x∗≤gr0p;xm−x∗≤x0−x∗<r0,and, hence, xm+1∈ℕx∗,r0. Now, the conclusion what we are proving above is as follows.


## 5. Semilocal Convergence of the Newton-PGSS Method

Assumption 2.
For allx∈ℕx0,r⊂ℕ0, where r<1/21/Lγp, assume the following conditions hold.(A1)
The bounded condition: there exist positive constantsδ and γ such that(43)maxAx0,Bx0≤β,F′x0−1≤γ,Fx0≤δ.(A2)
The Hölder condition: there exist nonnegative constantsLa and Lb for all x, y∈ℕx0,r∈ℕ0(44)Ax−Ay≤Lax−yp,Bx−By≤Lbx−yp,with the exponent p∈0,1, and we define L:=La+Lb.Lemma 2.
Under Assumption2, for all x, y∈ℕx∗,r, then F′x−1exists, and we have the following inequations:(45)F′x−F′y≤Lx−yp,F′x≤Lx−x0p+2β,Bα,βΩ;x−Bα,βΩ;y=Cα,βΩ;x−Cα,βΩ;y≤12x−yp,Bα,βΩ;x−1≤2γ1−Lγx−yp.Proof.
The proof is omitted since it is the same as Lemma1.Theorem 3.
Under Assumption2, for all x, y ∈ℕx∗,r, then F′x−1exists, and we have the inequations in (45).
Now, we construct the following sequence of functions:(46)gt=11+pat1+p−bt+c,ht=atp−1,with the constants satisfying(47)a=γL1+η1+2pγ1+pδpLη,b=1−η,c=2γδ,where η=maxkηk<1 and r=minr1,r2; let t0=0, and the sequence tk are generated by the following formula:(48)tk+1=tk−gtkhtk.
Some properties of the functiongt and ht and the sequence tk are given by the following lemmas.Lemma 3.
Assume that constants satisfy(49)δpγp+1L≤1−η2p1+η2,(50)p1+pbap>cb.
Denotet∗=b/ap, and then, when t∈0,t∗, the following inequalities hold that(51)gt≥0,g′t<0,g″t>0,ht<g′t<0.Proof.
The proof is omitted since it is straightforward.Theorem 4.
Under the assumptions of lemma in this section,r:=minr1,r2 with(52)r1=θτγL1+τ+θτp,r2=bap,satisfying(53)r1<r2.
And, definel0=liminfk⟶∞lk, and the constant l0 satisfies(54)l0>−−lnηlnτ+1θ,where the symbol ⋅ is used to denote the smallest integer no less than the corresponding real number, τ∈0,1−θ/θ a prescribed positive constant, and(55)θ≡θα,β;x0=Mα,βx0<1.
Then, the iteration sequencexkk=0∞ generated by the Newton−PGSS is well defined and converges to x∗, which satisfies Fx∗.Proof.
Firstly, we construct the sequence(56)t0=0,tk+1=tk−gtkhtk.
We have(57)gbap>0.
Furthermore,g0=c>0; hence, we have r∗ which satisfies gr∗=0, where t1=2γδ because (49) and (50). Hence, we have(58)g2γδ>0,t1=2γδ<r∗<bap.
Therefore, we have(59)t0<t1<r∗.
Now, we assume thattk−1<tk<r∗, and by making use of mathematical methods of induction, we have(60)tk+1=tk−gtkhtk.
Because(61)htk≤g′tk<0,gtk<0,hence(62)tk+1>tk.
Furthermore,mt=t−gt/g′t⇒m′t=gtg″t/g′t2; then, m′tis an increasing function in0,b/ap and −1/htk≤−1/g′tk; hence, we have tk+1=tk−gtk/htk≤tk−gtk/g′tk≤r∗−gr∗/g′r∗<r∗<r2, and it exists as point t∗liminfk⟶∞rk.
Next, prove the following inference by mathematical induction:(63)xk+1−xk≤tk+1−tk,F′xk≤1−γLtkpγ1+ηtk+1−tk,where(64)x1−x0≤F′x0−1Fx0+Mα,βΩ;x0l∗F′x0−1Fx0≤γ1+θl∗δ,t1−t0=2γδ,Fx0≤δ≤2δ1+η=1−γLt0pγ1+ηt1−t0,Fxk≤Fxk−Fxk−1−F′xkxk−xk−1+Fxk+F′xk−1xk−xk−1≤L1+pxk−xk−1p+1+ηFxk−1.
Because(65)δpγp+1L≤1−η2p1+η≤12p,11−γLtkp≤−1htk,tk>t1>2γδ,we can derive inequality(66)1−ηγ21−γLtkp≤a−htk.
Hence,(67)γ1+η1−γLtkpFxk≤γ1+η1−γLtkp21+ptk−tk−11+p+η1−γLtk−1pγ1+ηtk−tk−1≤11+pa−htktk−tk−1p+1+η−htktk−tk−1.
And because(68)a1+ptk−tk−1p+1+ηtk−tk−1≤gtk−gtk−1−htk−1tk−tk−1=a1+ptkp+1−tk−1p+1−btk−tk−1−atkp−1tk−tk−1,=11+patkp+1−−tk−1p+1−atk−1ptk−tk−1+ηtk−tk−1,we can give(69)γ1+η1−γLtkFxk≤gtk−gtk−1−htk−1tk−tk−1−htk=gtk−htk=tk+1−tk.
Then,(70)xk+1−xk≤1−Mα,βΩ;xkl0F′tk−1Fxk≤1+τ+1θl∗γ1−γLtkFxk,and we can have inequality(71)1+ηγ1−γLtkFxk≤tk+1−tk.
Since the sequencetkk=0∞ converges to t∗ and(72)xk+1−x0≤xk+1−xk+xk−xk−1+⋯+x1−x0≤tk+1−tk+tk−tk−1+⋯+t1−t0≤r∗,where r∗<b/ap, the sequence xk also converges to x∗. The proof has been completed as above.


## 6. The Modified Newton-PGSS Method and Its Local Convergence

In this section, we improve Newton-PGSS and introduce the modified Newton-PGSS and prove the local convergence of the modified Newton-PGSS method briefly.The modified Newton method is a kind of algorithm based on the Newton method. Its principle is to reduce the calculation times of the inverse matrix of Jacobian matrix, making the algorithm more efficient. It only needs to calculate inverse matrix once every two steps. The format of the algorithm is shown below:(73)F′xkdk=−Fxk,yk=xk+dk,F′xkhk=−Fyk,xk+1=yk+hk.Then, we get the modified Newton-PGSS method for solving nonlinear system (1) (Algorithm 4).Algorithm 4: MN-PGSS (modified Newton-PGSS method).
(1)
Given an initial guessx0, a nonnegative constant α, a positive constant β, and two positive integer sequences lkk=0∞,mkk=0∞.(2)
Fork=0,1,…, until Fxk≤tolFx0 do:(2.1)
Setdk,0=hk,0:=0.(2.2)
Forl=0,1,…,lk−1, apply algorithm PGSS to the linear system (12):Ωxk+F′xkdk,l+1/2=αΩxk−F′xkdk,l−Fxk,and obtaindk,lk such thatFxk+F′xkdk,lk≤ηkFxk,for someηk∈0,1.(2.3)
Setyk=xk+dk,lk.(2.4)
Form=0,1,…,mk−1, apply algorithm PGSS to the linear system (12):Ωxk+F′xkhk,m+1=αΩxk−F′xkdk,l−Fyk,and obtainhk,mk such thatFxk+F′xkmk,hk≤ηk˜Fyk,for someηk˜∈0,1.(2.5)
Setxk+1=yk+hk,mk,WhereΩxk=αI1xk00βI2xk.I1isan×nidentitymatrixandI2isam×midentitymatrixobtain the following uniform expressions fordk,lk and hk,mk,dk,lk=−∑j=0lk−1Mα,βΩ;xkjGα,βΩ;xkFxk,hk,mk=−∑j=0mk−1Mα,βΩ;xkjGα,βΩ;xkFyk,Mα,βΩ;x and Gα,βΩ;x are defined as well as Section 3. Then, the modified Newton-PGSS method can be rewritten asxk+1=xk−∑j=0lk−1Mα,βΩ;xkjGα,βΩ;xkFxk−∑j=0mk−1Mα,βΩ;xkjGα,βΩ;xkFyk,k=0,1,2,…,The modified Newton-PGSS method can be equivalently expressed asxk+1=xk−I−Mα,βΩ;xklkF′xk−1Fxk−I−Mα,βΩ;xkmkF′xk−1Fyk,k=0,1,2,…,In the following, we analyze the local convergence, and its condition (including assumption) and local convergence theorem are the same as Theorem2 because their Mα,βΩ;x and Gα,βΩ;x are the same. Thus, we only restate them now.Assumption 3.
For allx∈ℕx∗,r⊂ℕ0, assume the following conditions hold.(A1)
The bounded condition: there exist positive constantsδ and γ such that(74)maxAx∗,Bx∗≤δ,F′x∗−1≤γ.(A2)
The Hölder condition: there exist nonnegative constantsKw and Kt such that(75)Ax−Ax∗≤Kax−x∗p,Bx−Bx∗≤Kbx−x∗p,with the exponentp∈0,1.Lemma 4.
Under Assumption3, for all x,y∈ℕx∗,r, if r∈0,1/γK1/p, then F′x−1 exists. And, the following inequalities hold with K:=Ka+Kb for all x, y∈ℕx∗,r:(76)F′x−F′x∗≤Kx−x∗p,F′x−1≤γ1−γKx−x∗p,Fx≤K1+px−x∗1+p+2δy−x∗.Theorem 5.
Under the assumptions of Lemma4, suppose r∈0,r0 and define r0:=min1≤j≤3r+j, where(77)r+1=τθγK1+θ+τθq,r+2=1−2δτ+1θl04+2p/1+pKγq,r+3=1γKq,with l0=liminfk⟶∞lk, and the constant u satisfies(78)l0>−ln2δlnτ+1θ,where the symbol ⋅ is used to denote the smallest integer no less than the corresponding real number, τ∈0,1−θ/θ is a prescribed positive constant, and(79)θ≡θα,β;x∗=Mα,βx∗≤maxλi∈λΩ1/2F′x∗Ω1/21−λi1+λi≡σα,β;x∗<1,with αandβ are more than 0.
Then, for anyx∈ℕx∗,r⊂ℕ0,t∈0,r and c>u, it holds that(80)Mα,βV;x≤τ+1θ<1,gtp;c=γ1−γKtp3+p1+pKtp+2βτ+1θc≤gr0p;u<1.Proof.
It is the same as Theorem2.
In Theorem5, we get the fact that x1−x∗≤gr0p;x0−x∗ which is the modified Newton-PGSS has the similar result as the following.Theorem 6.
Under the conditions of Theorem5, we have the fact that, for any x0∈ℕx∗,rwith corresponding lkk=0∞,mkk=0∞ of positive integers, the iteration sequence xkk=0∞ which is generated by the modified Newton-PGSS method is well defined and converges to x∗. Furthermore, it has the following properties:(81)limt⟶∞supxk−x∗1/k≤gr0p;u2.Proof.
The proof ofyk+1−x∗≤gxk−x∗p;lkxk−x∗ is the same as xk+1−x∗≤gxk−x∗p;lkxk−x∗ in Theorem 2. And, from the defination of xk and in Lemma 4, we can easily get that(82)xk+1−x∗=yk−x∗−I−Mα,β;xkmkF′xk−1Fyk=yk−x∗−F′xk−1Fyk+Mα,β;xkmkF′xk−1Fyk,where(83)yk−x∗−F′xk−1Fyk=−F′xk−1Fyk−Fx∗−F′x∗yk−x∗+F′xk−1F′xk−F′x∗yk−x∗.
By Lemma4 and similar to the proof of Fx, we can get it:(84)yk−x∗−F′xk−1Fyk≤γ1−γKxk−x∗pK1+pyk−x∗p+Kxk−x∗pyk−x∗Mα,β;xkmkF′xk−1Fyk=Mα,β;xkmkF′xk−1Fyk−Fx∗−F′x∗yk−x∗+F′x∗yk−x∗≤γτ+1θmk1−γKxk−x−∗pK1+pyk−x∗1+p+2δyk−x∗.
Combining (84) with (85), we can obtain(85)xk+1−x∗≤γK1−γKxk−x∗p1+τ+1θmk1+pyk−x∗p+xk−x∗p+2δγτ+1θmk1−γKxk−x∗pyk−x∗≤γgxk−x∗p;lk1−γKxk−x∗p2Kgxk−x∗p;lkp1+pyk−x∗p+Kxk−x∗p+2δτ+1θmkxk−x∗≤γgxk−x∗p;lk1−γKxk−x∗p3+p1+pKxk−x∗p+2δτ+1θmkxk−x∗=gxk−x∗p;lkgxk−x∗p;mkxk−x∗≤gr0p;u2xk−x∗.
By utilizing mathematical induction, we can get the fact that anyx0∈ℕx∗,r and nonnegative integer k, and we have(86)xk+1−x∗≤gr0p;u2xk−x∗≤⋯≤gr0p;u2kx1−x∗≤gr0p;u2kx1−x∗≤gr0p;u2k+1x0−x∗.
Becausegr0p;u<1, we can make a conclusion that x0 converges to x∗ as n⟶+∞ from (86. The proof of theorem is completed.


## 7. Numerical Example

In this section, we show the efficiency of the modified Newton-PGSS method. Because such problems have not been analyzed before, in this paper, the first step is that we just compare the modified Newton-PGSS method with the Newton-PGSS method and Newton-RHSS as their inner iterations are splitting methods. And, the second step, we will discuss which is more effective as preconditioner in Newton-GMRES algorithm. The numerical results in Example1 were computed using MATLAB Version R2011b, on an iMac with a 3.20 GHz Intel Core i5-6500 CPU, and 8.00 GB RAM, with machine accuracy eps =  2.22×10−16.Example 1.
Consider the Stokes flow problem. Findu and w such that(87)−v△u+▽w=f˜,inΩ,▽⋅u=g˜,inΩ,ut,x,y=0,on0,1∈∂Ω,∫Ωwxdx=0,where Ω=0,1×0,1, with ∂Ω is the boundary of Ω,u is a vector-valued function representing the velocity v> 0 is the viscosity constant,△ is the componentwise Laplace operator, and w is a scalar function representing the pressure. By discreting the function above with the upwind scheme, we obtain the saddle point problem in which(88)A=I⊗T+T⊗I00I⊗T+T⊗I∈ℝ2p2×2p2,B=I⊗FF⊗I∈ℝ2p2×p2,where(89)T=vh2⋅tridiag−1,2,−1∈ℝp×p,F=1h⋅tridiag−1,1,0∈ℝ2p2×1,f˜=eu11,eu12,…,eu21,…,eupp,ev11,ev12,…,ev21,…,evppT∈ℝp×p,g˜=1,1,…,1T∈ℝp2×1,with ⊗ being the Kronecker product symbol. By applying the centered finite difference scheme on the equidistant discretization grid with the step size Δt=h=1/N+1, the system of nonlinear equations (1) is obtained with the following form:(90)Fu=Mu+Ψu=0,where(91)M=AB−BT0,Ψu=eu11,eu12,…,eu21,…,eupp,ev11,ev12,…,ev21,…,evpp,−1,−1,…,−1T.
Then, the Jacobian matrix is(92)F′u=M+diage−u11,e−u12,…,e−u21,…,e−upp,e−v11,e−v12,…,e−v21,…,e−vpp,1,1,…,1.
Firstly, we compare the algorithms whose inner iterations are splitting methods, such as Newton RHSS, Newton PGSS, and modified Newton PGSS. The parameters needed in the problem are chosen by using the traversal method for the purpose of comparison: the initial guessu0=0, the stopping criterion for the outer iteration is set to be(93)Fuk2Fu02≤10−5,and the prescribed tolerance ηk and η˜k for controlling the accuracy of the iteration are both set to be η, which satisfies inequality(94)F′ukdk,lk+Fuk2Fuk2≤η.
For different inner toleranceη  = 0.4, 0.2, and 0.1 and problem parameters v = 1 and 0.1, the results about outer IT, inner IT, and CPU are listed in the numerical tables corresponding to the referred inexact Newton methods. Because the linear matrix of the solution is different in each iteration, there is no way to find the optimal parameters in theory. Thus, we get the most efficient algorithm by traversing for the parameters of different algorithms, and then, we tabulate these results. For the selection of a single parameter, we traverse the parameters from 0 with an interval of 1 in the beginning. When the number of steps, time, and error show an earlier increase and later decrease trend, the iteration is stopped to determine the range of parameters. We use this method to narrow the parameter range and get “the best parameters at present” until the result (such as step) does not change. For the selection of two parameters (denoted them as α and β), first, we fix the parameter α and traverse the parameter β by using the single parameter traversal method. Then, we fix the parameter β and traverse the parameter α. We repeat the process until the result does not change. We can get information from Tables 1–6 that Newton-PGSS performs better than Newton-RHSS in the iterative CPU. Moreover, the Newton-MPGSS algorithm is much better than Newton-RHSS in the number of generation steps.
As we known, Krylov subspace method is more efficient than the stationary iterative methods in saddle point. Secondly, we will compare the effects of PGSS and RHSS as preconditioners on Newton-GMRES. In Tables7–12, we can find it that PGSS and RHSS are more efficient as preprocessing operators than without them as using GMRES methods. Furthermore the PGSS is more efficient than RHSS as preconditioners. In the inner iteration, RHSS and PGSS are treated as preprocessing operators, and then the Krylov subspace method is used to solve the problem, which is better than the Krylov subspace method in CPU and step number. Although the effect of PGSS as preconditioner is not much better than that of RHSS when n is small, it can be seen that PGSS has great advantages in both steps and CPU compared with RHSS with the increase of n.Table 1
Numerical results of inexact Methods forv = 0.1 and η  = 0.4.
nMethodOptimal values ofα/α,βError estimatesCPU time (s)Outer ITInner IT16Newton-PGSS9.7,7.82.2284×10−43.89115Newton-MPGSS9.7,7.86.1064×10−54.3675Newton-RHSS14.42.3976×10−47.12131020Newton−PGSS11.3,9.23.3053×10−415.02126Newton-MPGSS11.3,9.21.6762×10−414.756.6Newton−RHSS173.3324×10−426.921313.632Newton−PGSS15.5,9.95.31×10−4227.521310.3Newton-MPGSS11.3,9.21.4157×10−4227.8714.4Newton−RHSS20.63.5082×10−4453.841528.2Table 2
Numerical results of inexact methods forv = 1 and η  = 0.4.
nMethodOptimal values ofα/α,βError estimatesCPU time (s)Outer ITInner IT16Newton-PGSS8.8,7.41.6253×10−420.741544.7Newton-MPGSS11.3,9.21.1582×10−430.8839Newton-RHSS13.21.7534×10−482.213124.920Newton−PGSS7,72.6262×10−4195.011485.9Newton-MPGSS13,63.2972×10−4140.59745.4Newton−RHSS182.2695×10−425313167.532Newton−PGSS9.4,10.22.297×10−4356215153.3Newton-MPGSS11.4,9.88.8723×10−535938135.5Newton−RHSS21.73.596×10−45488.313327.5Table 3
Numerical results of inexact methods forv = 0.1 and η  = 0.2.
nMethodOptimal values ofα/α,βError estimatesCPU time (s)Outer ITInner IT16Newton-PGSS7,77.6864×10−56.57811.5Newton-MPGSS7.7,9.62.5763×10−44.6649Newton-RHSS18.69.8486×10−58.34916.120Newton−PGSS8.2,93.3090×10−415.43812.4Newton-MPGSS12,62.5400×10414.448.4Newton−RHSS14.62.0703×10−421.44823.832Newton−PGSS8.2,9.52.2875×10−4394.4829.2Newton-MPGSS10.8,13.51.7649×10−4346.78421Newton−RHSS20.61.9104×10−4507.3748.5Table 4
Numerical results of inexact methods forv = 1 and η  = 0.2.
nMethodOptimal values ofα/α,βError estimatesCPU time (s)Outer ITInner IT16Newton-PGSS8,7.62.7300×10−441.67975.9Newton-MPGSS20,71.2180×10−433.15547.2Newton-RHSS17.88.4271×10−586.228218.820Newton−PGSS8,93.3351×10−41749112.4Newton-MPGSS8,9.63.5554×10−593.25142.3Newton−RHSS189.3834×10−52588289.632Newton−PGSS8,9.21.95×10−437849304.9Newton-MPGSS10.8,13.51.485×10−436795219.2Newton−RHSS21.71.4216×10−459448564.5Table 5
Numerical results of inexact methods forv = 0.1 and η  = 0.1.
nMethodOptimal values ofα/α,βError estimatesCPU time (s)Outer ITInner IT16Newton-PGSS8.2,72.7447×10−43710.1Newton-MPGSS13,65.8466×10−53.8547.3Newton-RHSS14.42.0678×10−46.35720.620Newton−PGSS8.2,7.63.4582×10−412.24715.6Newton-MPGSS7.6,111.0698×10−411.65417.5Newton−RHSS16.82.6135×10−423.68728.332Newton−PGSS8.2,7.53.2225×10−4369738.9Newton-MPGSS10.8,13.47.5135×10−5306331Newton−RHSS20.24.4700×10−4648662.7Table 6
Numerical results of inexact methods forv = 1 and η  = 0.1.
nMethodOptimal values ofα/α,βError estimatesCPU time (s)Outer ITInner IT16Newton-PGSS8.2,8.22.5370×10−440.885796Newton-MPGSS11,8.43.9974×10−540.9485.4Newton-RHSS163.6266×10−570.256297.320Newton−PGSS8,10.43.4557×10−41567145.1Newton-MPGSS11,7.37.1642×10−61344155.2Newton−RHSS17.23.9646×10−52726404.332Newton−PGSS10.7,11.75.1146×10−430017251.6Newton-MPGSS11.4,7.62.6628×10−432414308.8Newton−RHSS21.45.8568×10−559076790.7Table 7
Numerical results of preconditioned inexact Newton methods forv = 0.1 and η  = 0.4.
nPreconditioner for GMRESOptimal values ofα/α,βError estimatesCPU time (s)Outer ITInner IT16−−2.2319×10−41.2153.2RHSS27.52.6701×10−44.3131.1PGSS2,12.5914×10−40.77120−−2.4378×10−43.97213.95RHSS232.6537×10−413.82141.1PGSS8,11.6342×10−42.588132−−5.1384×10−416.21169.9RHSS244.0483×10−4180.06151.7PGSS5,11.7622×10−416.5281Table 8
Numerical results of preconditioned inexact Newton methods forv = 0.1 and η  = 0.2.
nPreconditioner for GMRESOptimal values ofα/α,βError estimatesCPU time (s)Outer ITInner IT16−−6.4114×10−51.0694.4RHSS142.6652×10−43.291PGSS2,21.3215×10−41.367120−−1.2495×10−41.06106.3RHSS193.3791×10−49.6391.6PGSS3,23.0298×10−41.837132−−1.5261×10−419.61017.2RHSS222.6631×10−4165.6101.9PGSS2,11.3380×10−416.6971Table 9
Numerical results of preconditioned inexact Newton methods forv = 0.1 and η  = 0.1.
nPreconditioner for GMRESOptimal values ofα/α,βError estimatesCPU time (s)Outer ITInner IT16−−1.0703×10−41.3785.3RHSS121.9074×10−43.3381.1PGSS3,22.5352×10−41.286120−−2.1225×10−41.8178.4RHSS161.3363×10−49.6181.6PGSS3,21.1526×10−42.257132−−5.0033×10−414.63720.7RHSS304.1546×10−4138.972.7PGSS1,13.2577×10−413.9861Table 10
Numerical results of preconditioned inexact Newton methods forv = 1 and η  = 0.4.
nPreconditioner for GMRESOptimal values ofα/α,βError estimatesCPU time (s)Outer ITInner IT16−−1.5522×10−43.141629.3RHSS181.7172×10−44.07131PGSS1,31.8162×10−41.8111120−−2.0082×10−49.911750RHSS181.8359×10−410.48131PGSS1,12.8163×10−43.329132−−4.5286×10−4294.573979.8RHSS263.3912×10−4138.79151.07PGSS1,33.8558×10−429.95101Table 11
Numerical results of preconditioned inexact Newton methods forv = 1 and η  = 0.2.
nPreconditioner for GMRESOptimal values ofα/ α,βError estimatesCPU time (s)Outer ITInner IT16−−7.5565×10−52.781139.5RHSS162.3989×10−43.2291PGSS3,12.1344×10−41.487120−−2.0648×10−49.241171.5RHSS193.4282×10−48.9291.2PGSS1,21.5814×10−43.277132−−3.9128×10−4264.063580RHSS235.4007×10−4119.75101.3PGSS2,45.0058×10−429.6171Table 12
Numerical results of preconditioned inexact Newton methods forv = 1 and η  = 0.1.
nPreconditioner for GMRESOptimal values ofα/α,βError estimatesCPU time (s)Outer ITInner IT16−−1.2584×10−42.23853.9RHSS212.0586×10−42.9371.3PGSS1,41.3197×10−41.095120−−1.1186×10−49.141078.8RHSS182.6957×10−48.3271.6PGSS3,21.7341×10−42.75132−−3.9128×10−4265.383580RHSS232.8212×10−4121.8481.9PGSS2,93.2145×10−426.5151


## 8. Conclusions

The Newton-PGSS method is a considerable method for solving large sparse nonlinear system with nonsymmetric saddle point problems with the nonsymmetric Jacobian matrix. This is the first time to solve this kind of problem, and we utilize the PGSS iteration as the inner solver for the Newton equation. And, we establish a modified Newton-PGSS method for solving large sparse nonlinear system with nonsymmetric saddle point problems with the nonsymmetric Jacobian matrix. We give the local convergence and semilocal convergence analysis of the new method under proper conditions. Finally, the numerical results show that the modified Newton-PGSS outperforms the other splitting method in the sense of CPU time and iterative steps. Furthermore, when we apply the Newton-GMRES method to solve the problems, PGSS will accelerate the algorithm as preconditioner and make it more efficient than RHSS.



---

*Source: 6636943-2021-02-16.xml*