NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS
Numer.Linear Algebra Appl.2015;22:717–730
Published online15April2015in Wiley Online ).DOI:10.1002/nla.1983
The corrected Uzawa method for solving saddle point problems
C.F.Ma*,†and Q.Q.Zheng
School of Mathematics and Computer Science,Fujian Normal University,Fuzhou350117,China
SUMMARY
In this paper,we consider the solution of linear systems of saddle point type by correcting the Uzawa algorithm,which has been propod in[K.Arrow,L.Hurwicz,H.Uzawa,Studies in nonlinear programming, Stanford University Press,Stanford,CA,1958].We call this method as corrected Uzawa(CU)method.The convergence of the CU method is analyzed for solving nonsingular saddle point problem as well as the mi-convergence for the singular ca.First,the corrected model for the Uzawa algorithm is established,and the CU algorithm is prented.Then we study the geometric meaning of the CU model.
Moreover,we introduce the overall reduction coefficient˛to measure the effect of the CU process.It is shown that the CU method converges faster than the Uzawa method and veral other methods if the overall reduction coefficient˛satisfies certain conditions.Numerical experiments are prented to illustrate the theoretical results and examine the numerical effectiveness of the CU method.Copyright©2015John Wiley&Sons,Ltd.
Received7March2014;Revid2February2015;Accepted6March2015
KEY WORDS:saddle point problem;correction technique;iterative methods;Uzawa method;convergence analysis
1.INTRODUCTION
Let m and n be positive integers.We consider the following class of systems of linear equations
with the block2 2structure:
Â
A B
B>0ÃÂ
x
y
Ã
D
Â
p
q
Ã
;(1)
where A2R m m;B2R m n;p2R m;q2R n;.m>n/,and A is symmetric positive definite. Systems of linear
equations with the form(1)are called saddle point problems,which ari in many application areas.Generally speaking,both A and B are large and spar.疫情在家作文
Many practical problems arising from scientific computing and engineering applications may require the solution of systems of linear equations of the form(1),for example,computationalfluid dynamics[1–4],mixedfinite element approximation of elliptic partial differential equations[2], the Lagrange-type methods for constrained nonconvex optimization problems[5],inversion of geo-physical data[6],weighted and equality-constrained least squares estimation[7],structural analysis [8],electronic networks[1,2,9],and computer graphics[10].The system of linear equations(1) is also termed as an augmented system,or an equilibrium system,or a Karush–Kuhn–Tucker system[11–13].
Becau the matrices A and B are usually large and spar,iterative methods become more attrac-tive than direct methods for solving the saddle point problem(1),although the direct methods play an important role in the form of preconditioners embedded in an iterative framework.In the ca that the coefficient matrix of Equation(1)is nonsingular,many efficient iterative methods as well *Correspondence to:C.F.Ma,School of Mathematics and Computer Science,Fujian Normal University,Fuzhou350117, China.
†E-mail:macf@fjnu.edu.
718 C.F.MA AND Q.Q.ZHENG
as their numerical properties have been studied in the literature,for example,Uzawa-type methods [14–22],matrix splitting iterative methods[23–29],relaxation iterative methods[17,30,31],itera-tive null space methods[32,33],and the references therein.Golub,Wu,and Yuan[30]propod a successive overrelaxation(SOR)-like method for solving nonsingular saddle point problems,stud-ied the convergence rates,behavior of the spectral radius,and optimal parameters,and made some comparisons.In[15],the classical Uzawa method that is a very effective algorithm for solving the saddle point problems was propod by Arrow,Hurwicz,and Uzawa.After that,the improvement and development of the classical Uzawa method had been put forward by many other authors.Elman and Golub[3]propod the inexact Uzawa method,which was further analyzed in[14].Bai,Parlett, and Wang[17]prented an efficient parameterized Uzawa(PU)method for solving the nonsin-gular saddle point problems,also termed as the generalized SOR(GSOR)method,which includes the classical Uzawa method,the preconditioned Uzawa method[3],and the SOR-like method[30] as special cas.Theoretical analysis and numerical experiments have shown that the PU method is feasible and effective for solving the large spar saddle point problem.In addition,the authors in[34]
校园风采prove the mi-convergence of the GSOR method when it is applied to solving the singular saddle point problems.
Most often,the matrix B occurs in the form of full column rank,but this is not always the ca. If B is rank deficient,we call the linear system(1)as singular saddle point problem,becau its coefficient matrix is singular.Recently,veral authors[34–37]have paid attention to the iterative methods for the singular saddle point problem.A preconditioned minimum residual and a pre-conditioned conjugate gradient methods were propod in[38,39],respectively,for solving the rank-deficient saddle point problems.However,there are some drawbacks in the methods.The preconditioned minimum residual method needs a Cholesky decomposition with respect to the pre-conditioning matrix,and the preconditioned conjugate gradient method needs a QR decomposition or a direct projection method to determine the linearly independent rows of B before solving the sin-gular saddle point problem(1).Zheng,Bai,and Yang[34]studied the GSOR method and proved the mi-convergence of this method when it is applied to solving the singular saddle point problems. The optimal iteration parameters and the corresponding optimal mi-convergence factor for the GSOR method were also determined.Zhang et al.[40]discusd the inexact Uzawa method,which covers the Uzawa method,the preconditioned Uzawa method,and the PU method as special cas. They also proved t
he mi-convergence result under restrictions by verifying two necessary and suf-ficient conditions.Moreover,sufficient conditions for the mi-convergence of veral Uzawa-type methods were also provided by them.
In this paper,we propo the corrected Uzawa(CU)method for solving the saddle point problem (1).This new method can be applied to the nonsingular ca as well as the singular ca.We will e that the convergence of the CU method is guaranteed for solving nonsingular saddle point problem as well as the mi-convergence for the singular ca.In addition,the overall reduction coefficient is also introduced and ud in this paper to discuss the condition under which the CU method will converge faster than the Uzawa method.Numerical experiments are prented to illustrate the theoretical results and examine the numerical effectiveness of the CU method.In the following discussion,we always assume that Equation(1)is consistent.
The paper is organized as follows.In Section2,we introduce some Uzawa-type methods and establish the CU model for Equation(1),and then the CU algorithm is prented.In Section3,the CU model is solved.Moreover,we analyze the geometric meaning of the CU model,which we have obtained,and study the overall reduction coefficient˛,which is defined in Section3.In Section 4,some numerical experiments are given to show the efficiency of the CU method.Finally,some conclusions
are propod in Section5.
兔子的英语单词The following notations will be ud throughout this paper.We denote the identity matrix by I.Œu;v denotes the inner product of vectors u and v.For a matrix A,we denote the spectral norm of A by k A k2and denote the range and the null spaces of A by R.A/and N.A/,respectively.The conjugate transpo and transpo of A are denoted by A and A>,respectively.Moreover,the Moore–Penro inver of A is defined as the unique matrix A ,which satisfies the following four matrix equations:
AA A D A;A AA D A ;.AA / D AA ;.A A/ D A A:
THE CORRECTED UZAW A METHOD FOR SADDLE POINT PROBLEMS 719
2.THE CORRECTED UZAW A METHOD
For the sake of simplicity,we rewrite linear system (1)as ÂA B B >0
ÃÂx y ÃD Âp q Ã:(2)Denote
A D ÂA B
B >0Ã;X D Âx
y Ã;F D Âp
q Ã;
then (2)can be rewritten as
A X D F :
车鉴定For the coefficient matrix A of Equation (2),we utilize the matrix splitting:A D A B B >0!D A C Q 10 B >Q 2! Q 1 B 0Q 2!D M N;(3)
房屋租赁协议范本where Q 12R m m ;Q 22R n n ,with A C Q 1is nonsingular and Q 2is symmetric positive definite,then it yields the inexact Uzawa method:´x .k C 1/D x .k/C .A C Q 1/ 1 p Ax .k/ By .k/ ;y .k C 1/D y .k/C Q 12
B >x .k
C 1/ q :(4)Obviously,the iterative matrix of (4)is H
D M 1N .
诗可以兴的意思Denote X .k/D Âx .k/y .k/
Ã,then (4)can be rewritten as X .k C 1/D H X .k/C M 1F :(5)
With different choices of the matrices Q 1and Q 2,the inexact Uzawa method (4)covers veral Uzawa-type methods as follows:
(i)Uzawa method [15]:Q 1D 0;Q 2D 1 I . >0/.´x .k C 1/D x .k/C A 1 p Ax .k/ By .k/ ;y .k C 1/D y .k/C B >x .k C 1/ q :(6)
(ii)PU method (GSOR)[17]:Q 1D 1!A A;Q 2D 1 Q ,where 0<!61; >0and Q is symmetric positive definite.´x .k C 1/D .1 !/x .k/C !A 1 p By .k/ ;y .k C 1/D y .k/C Q 1 B >x .k C 1/ q :
(7)The aforementioned PU method also covers the Uzawa method and the preconditioned Uzawa method [3].That is,if we take !D 1in (7),then we will obtain the preconditioned Uzawa method.If we let !D 1;Q D I in (7),then we will obtain the Uzawa method (6).
Taking Q 1D 0;Q 2D 1 I . >0/in (4),we can obtain the matrices M and N in (3)as follows:M D A 0 B >1 I !;N D 0 B 01I !:Then we can obtain the iterative matrix H of Uzawa method,that is,H D M 1N D 0 A 1B 0I B >A 1B
!;
720 C.F.MA AND Q.Q.ZHENG
无孔不入and we can also obtain M 1F D
A 1p
B>A 1p q
!
.Letˆ.X/D H X C M 1F;.ˆW
R m C n!R m C n;X2R m C n/.Then Uzawa method(6)can be rewritten as
X.k C1/Dˆ.X.k//:(8) Assume that X1;X2; ;X c are approximate solutions of Equation(2),where c>1is a posi-tive integer and A X i¤F.i D1;2; ;c/.The basic idea of the correction model for the Uzawa method is to construct a vector X,which is a better approximate solution of Equation(2)than X i, by making u of the information that X i provided.That is,
k F A X k2<min
16i6c
k F A X i k2:(9)
The vector X that satisfies(9)is called the corrected solution of X1;X2; ;X c,and the progress to determine the vector X is called CU process.The corrected model for the Uzawa method is prented as follows.
The CU model.
X D a1X1C a2X2C C a c X c;
a1C a2C C a c D1;
k F A X k2!min:
(10)
Here,we should point out that the CU process is the method forfinding the coeffi, a1;a2; ;a
c)for X.The aforementioned Equation(10)means that a1;a2; ;a c are deter-mined by minimizing k F A X k2and the minimization process will be described later in Section3.
With the aforementioned CU model,we can obtain the following detailed algorithmic description of the CU method.
The CU algorithm.Given an initial vector X.0/2R m C n,let k D0.
While.k6k max/
X.k/
1
D X.k 1/I
For.j D2;3; ;c/
X.k/
j Dˆ
X.k/
j 1
Á
I
end For
X.k/D a.k/1X.k/
1C a.k/
2
X.k/
2
C C a.k/c X.k/
c
I
err D k F A X.k/k2
k F A X.0/k2
I
<6"/
break;
end If
k=k+1
End While
Here,k max is the maximal number of iterations,a.k/
i .i D1;2; ;c/is determined by the k th
CU progress,and"is a given sufficiently small positive number.From the aforementioned CU algorithm,we can e that the CU method is a combination of the outer iteration and the inner iteration:the outer iteration vector X.k/is the linear combination of the inner iteration vectors
X.k/
1;X.k/
2
; ;X.k/
c
and satisfies the conditions in(10).
THE CORRECTED UZAW A METHOD FOR SADDLE POINT PROBLEMS721
How to solve the aforementioned CU model will be illustrated detailedly in Section3.If Equation(9)hol
ds true,then we can prove that the quence¹X.k/ºis convergent for solving the nonsingular saddle point problem and mi-convergent for solving the singular saddle point problem.In fact,this proof is bad on the convergence and the mi-convergence of the Uzawa method for solving the nonsingular saddle point problem and the singular saddle point problem, respectively.The proof of convergence of Uzawa method for solving nonsingular saddle point problem can be found in[15,41];the proof of mi-convergence of Uzawa method for solving the singular saddle point problem can be en in[40].
3.ANALYSIS FOR THE CORRECTED UZAW A METHOD
In this ction,we will solve the CU model(10).Moreover,we analyze the geometric meaning of the CU model,which we have obtained,and study the convergence(or mi-convergence)property of the CU iteration method for solving the saddle point problem(2).
For the splitting(3),it is well known that when A is nonsingular,for any initial vector X.0/, the iteration scheme(5)converges to A 1F,which is the exact solution of the system of linear equations A X D F,if and only if .H/<1.When A is singular,the mi-convergence about the iteration scheme(5)is precily described as follows;e[42].
Definition3.1([17,34,42])
Let A D M N with M as nonsingular.Denote H D M 1N and c D M 1F.Then for any initial vector X.0/2R m C n,the iterative scheme(5)is mi-convergent to a solution f X of the system of singular linear equations A X D F if and only if the matrix H is mi-convergent. Moreover,it holds that
狗鼠属相相配吗
f X D.I H/D c C.I E/X.0/;with E D.I H/.I H/D;
where.I H/D denotes the Drazin inver of I H.
Remark3.1([43])
When A is singular,then1is an eigenvalue of the iteration matrix H.Moreover,when the spectral radius of the iteration matrix H is equal to1,that is, .H/D1,the following two conditions are necessary and sufficient for guaranteeing the mi-convergence of the iteration matrix H:
(a)The elementary divisors of the iteration matrix H associated with its eigenvalue D1
are linear.
(b)If 2 .H/,the spectrum of the iteration matrix H,satisfying j j D1,then D1,that is,
#.H/<1,where
#.H/Ámax¹j jj 2 .H/; ¤1º:
When the linear system DX D b is consistent,then the vector X02C m C n that satisfies k X0k2D min DX D b k X k2is called the minimum norm solution of linear system DX D b. When the linear system DX D b is not consistent,then the vector X02C m C n that satisfies
k X0k2D min min k DX b k
2k X k2is called the minimal norm least squares solution of linear system
DX D b.
Lemma3.1([44])
If the linear system DX D b is consistent,then D b is the unique minimum norm solution of DX D b.
Lemma3.2([44])
If the linear system DX D b is not consistent,then D b is the unique minimal norm least squares soluti
on of DX D b.
Together with Lemmas3.1and3.2,we prove the following result.
