13: BrezziFortinstability of saddle point problems. Math 639 (updated: January2, 2012)

In this section, we consider a saddle point problem.This is deﬁned from a matrix (with real entries) given in the following block form: t A B A=. B0 t HereAhas dimensionn×n,Bhas dimensionm×nandB(the transpose ofB) has dimensionn×mGiven. Weseek to iteratively solve the problem: n+m n+m b∈R, ﬁndx∈Rsolving (13.1)Ax=b. This is the simplest of saddle point problems.The techniques this section as well as their application to more general saddle point problems can be found in BrezziFortin, ... Remark 1.We temporarily consider the case whenAis symmetric and positive deﬁnite and the rank ofBism. Theminimax characterization of the eigenvalues ofA, i.e., (Az, z) λj= max min. Sjz∈Sj(z, z) Here the minimum is taken over all subspacesSjof dimensionjandλ1≥ λ2≥...are the eigenvalues ofAin decreasing order.The positive deﬁnite ness ofAimmediately implies thatAhas at leastnpositive eigenvalues since n forj≤n, takingSj= [V,0]whereVis ajdimensional subspace ofRgives rise to a positive minimum. Similarly, the eigenvalues ofA, given in increasing order are given by (Az, z) µj= minmax. Sjz∈Sj(z, z) m−1t−1t t Forq∈R, we setz= [−A Bq, q]and ﬁnd that(Az, z) =−(qA Bq, B). t Since the rank ofB=m, it follows thatAhas at leastmnegative eigenval ues, i.e.,Ahasnpositive andmnegative eigenvalues and(13.1)is a saddle point problem.

We shall recast this problem in a slightly diﬀerent notation by deﬁn t t ingu= (x1, . . . , xn) ,p= (xn+1, . . . , xn+m)F= (b1, . . . , bn) andG= 1

2 (bn+1, . . . , bn+m(). Then13.1) is equivalent to the system of equations t Au+B p=F (13.2) Bu=G. n+m As we shall often be splitting vectors inR, we introduce the notation x= [u, p] andb= [F, G] for this splitting. Before investigating the iterative solution of (13.1), we consider some conditions which guarantee the existence of solutions to (13.1) for any vector n+m1 b∈R n m We let (x, y) =x∙ydenote the Euclidean inner product onR,Ror n+m Rdepending on where the vectorsxandyreside. Wealso introduce n m auxiliary norms onRandRwhich we denote bykxk(again, the speciﬁc norm is identiﬁed from wherexnorms are induced by innerresides). These n mn+m products onRandR, respectively.Forz= [w, q]∈R, we set p 2 2 kzk=kwk+kqk. We deﬁne the following (dual) norms (Ax, y) kAk= supsup, kxkkyk n n x∈Ry∈R (Bx, y) kBk= supsup. kxkkyk n m x∈Ry∈R It is immediate that t (B y,x) t kBksup= sup kxkkyk m n y∈Rx∈R (Bx, y = supsup =kBk kxkkyk m n y∈Rx∈R where we reversed the order of the supremums to derive the last equality above. n We shall use additional dual norms for vectors, i.e., forw∈R, (w, x) kwk∗= sup. kxk n x∈R m The dual normskqk∗andkyk∗forq∈Randy∈Rn+mare deﬁned analogously. Itis not hard to show that the dual norms and the matrix

1 Of course,Ais a square matrix and so existence immediately implies existence.

3 norms do indeed satisfy the norm axioms.There are obvious inequalities which are immediate from the deﬁnition of these norms, e.g., |(p, q)| ≤ kpk∗kqkandkAuk∗≤ kAk kuk. n+m Exercise 1.For allz= [w, q]∈R, kzk∗≤ kwk∗+kqk∗≤2kzk∗. Conditions on the matrixA: (M.1) ThematricesAis symmetric and positive semideﬁnite. (M.2) Wedenote the null space ofBby n kerB={x∈R:Bx=0} and assume thatAis coercive on kerBspeciﬁcally, we assume. More that there is a positive constantαsatisfying 2 αkxk ≤(Ax,∙x),for allx∈kerB. (M.3) We assume the following infsup condition, i.e., there is a positive constantβsatisfying (Bu, p) (13.3)β≤inf sup. m u∈Rkukkpk p∈Rn Remark 2.We note that(13.3)implies that (Bu, p) m (13.4)kpk ≤csupfor allp∈R kuk n u∈R with constantc= 1/βfact,. Inc= 1/βis the smallest constantcfor which (13.4)holds. These systems often come from the discretization of partial diﬀerential equations with constraints enforced by the introduction of Lagrange mul tipliers (discussed below).In this case, natural problem dependent norms n m (which we have denotedkukforu∈Randkpkforp∈R) often give rise to −1−1 constantsα,β,kAk,kBkwhich are uniformly bounded independently of the discretization or mesh size.These norms are central to the stability analysis of the original PDE as well as their discretizations (i.e., the solution of (13.1)). It is a fact from linear algebra that n t R= kerB⊕RangeB

4 is an orthogonal decomposition in the Euclidean inner product and we denote ⊥t m kerB= RangeB(. Now,13.4) implies that for each nonzerop∈R, there n is at least one (nonzero)u∈Rwith t (Bu, p) = (u, Bp)6= 0. t m⊥ This means thatBis a one to one map ofRonto kerBit follow. Thus −t t⊥ from the (13.4) thatB(the inverse ofBon kerB) satisﬁes −t t−t (uBw, B) (B uw, B) −t−1−1 kB uk ≤βsup =βsup kwk kwk n n w∈Rw∈R (13.5) (w, u) −1−1 =βsup =βkuk∗. kwk n w∈R Now there is a complementary infsup condition, namely, (Bu, p) (13.6)β1≤inf sup. kukkpk t m u∈kerB p∈R or (Bu, p) −1t (13.7)kuk ≤βsup forallu∈kerB . 1 p∈Rkuk m It turns out that (13.3) and (13.6) are equivalent and hold with the sameβ. We illustrate the proof in one direction below. t−t Suppose that (13.3) holds and thatuis in kerBfor. Thenp=B u, (13.5) implies t (u, u) (pu, B) kuk= = kuk kuk (Bu, p) (Bu, p) −1 =≤βsup kukp∈Rkpk m −1−1 This implies that (13.6) holds withβ≤β. Asimilar argument shows 1 −1−1 that if (13.6) holds then so does (13.3) withβ≤β, i.e., the infsup 1 conditions are equivalent and hold with the same constant. ⊥m−1 NowBis one to one on kerBand maps ontoR. ItsinverseBmaps m⊥ Rbijectively onto kerBinfsup condition (. The13.7) implies −1 (qBB p,) (p, q) −1−1−1 kB pk ≤βsup =βsup kqk kqk m m q∈Rq∈R (13.8) (w, u) −1−1 =βsup =βkuk∗. w∈Rkwk n

5 n+m n+m Theorem 1.Letbbe inRthere is a unique solution. Thenx∈R satisfying(13.1). Moreover,there is a constantc=c(α, β,kAk,kBk)such that kxk ≤ckbk∗. Proof.We shall construct the solution [u, pof (13.2). Weﬁrst deﬁneu0= −1−1 B G. By(??),ku0k ≤βkGk∗. Next,we setu1∈kerBto be the solution of (13.9) (Au1, θ) = (F, θ)−(Au0, θall) forθ∈kerB. That this problem has a unique solution follows from the Riesz Represen tation Theorem applied on kerBwith inner product< u,v >= (Au, v), u, v∈kerB. That<∙,∙>is an inner product on kerBfollows from the coercivity assumption (M.2).We can then boundu1by 2 αku1k ≤(Au1, u1) = (F, u1)−(Au0, u1) ≤ kFk∗ku1k+kAk ku0kku1k which immediately implies −1−1 (13.10)ku1| ≤α(kFk∗+βkGk∗). We setu=u0+u1and note that −1−1 (13.11)kuk ≤(1 +α)β−1kGk∗+αkFk∗ Set −t (13.12)p=B(F−Au). ⊥ Note that (13.9) implies thatF−Auis in kerBand hencepis well deﬁned and satisﬁes (13.13) −1−1 kpk ≤ kFk∗+kAk kuk ≤ kFk∗+kAk((1 +α)β−1kGk∗+αkFk∗). Note that (13.12) implies the ﬁrst equation in (13.2) while Bu=Bu0+Bu1=Bu0=G. This implies that [u, p] is the solution of (13.2bound in the theorem). The follows from (13.11), (13.13) and Exercise1. Remark 3.The assumption of symmetry onAcan be relaxed by replacing the Riesz Representation Theorem by the LaxMilgram Theorem. Corollary 1.There are constantsc0andc1depending only onα,β,kAk, andkBksatisfying n+m (13.14)c0kxk ≤ kAxk∗≤c1kxkfor allx∈R.

6 n+m Proof.For anyx∈R,xis the unique solution to (13.1) withb=Ax thus the ﬁrst inequality of (13.14) is the inequality of the theorem. For the second, letx= [u, pExercise]. By1, t kAxk∗≤ kAu+B pk∗+kBuk∗≤(kAk+kBk)kuk+kBkkpk √ ≤(kAk+kBk)(kuk+kpk)≤2(kAk+kBk)kxk. 2 22 We used the arithmetic geometric mean inequality (a+b)≤2(a+b) for the last inequality above.