Technical Guide to Upgrading/Migrating to XenApp 5 Feature Pack 2
6
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
6
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
- exposé - matière potentielle : server console
- exposé - matière potentielle : server
- citrix license server
- delivery services
- installation steps
- xenapp
- hdx mediastream
- availability by edition
- flash
- citrix
- server
13: BrezziFortinstability of saddle point problems. Math 639 (updated: January2, 2012)
In this section, we consider a saddle point problem.This is defined 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, findx∈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 definite 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 definite 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 find 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 different notation by defin 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 specific norm is identified 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 define 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 defined 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 definition 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 semidefinite. (M.2) Wedenote the null space ofBby n kerB={x∈R:Bx=0} and assume thatAis coercive on kerBspecifically, 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 differential 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) satisfies −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). Wefirst defineu0= −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 defined and satisfies (13.13) −1−1 kpk ≤ kFk∗+kAk kuk ≤ kFk∗+kAk((1 +α)β−1kGk∗+αkFk∗). Note that (13.12) implies the first 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 first 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.
