Available at www.EIsevierMathematics.com APPLIED MATHEMATICS POWERED BY●cI■Nc■@DIn■cT同 AN COMP风TATION ELSEVIER Applied Mathematics and Computation 147(2004)601-606 www.elsevier.com/locate/amc Perturbation analysis for the generalized Cholesky factorization Wei-guo Wang a,Jin-xi Zhao b.* Department of Mathematics.Ocean University of Qingdao,Shandong 266071.PR China bState Key Laboratory for Novel Software Technology.Nanjing University. Nanjing 210093,PR China Abstract Let K be a symmetric indefinite matrix.Suppose that K=LILT is the generalized Cholesky factorization of K.In this paper we present perturbation analysis for the generalized Cholesky factorization.We obtain the first-order bound on the norm of the perturbation in the generalized Cholesky factor.Also,we give rigorous perturbation bounds. 2002 Elsevier Inc.All rights reserved. Keywords:Generalized Cholesky factorization;Perturbation bounds;Augmented matrix 1.Introduction Consider the problem of solving the structured linear system (日)()=() (1) for x and y,where A E Rmxm is symmetric positive definite matrix,B E Rmx",x, b E Rm,and y,d E R",C E R"x#.This system is called an augmented system,or an equilibrium system.The system(1)has been investigated by many authors for numerical algorithms.(See,[1,2,4,7,11,12]) 'Corresponding author.Address:Department of Computer Science and Technology,Nanjing University,Nanjing 210008,China. E-mail address:jxzhao@nju.edu.cn (J.Zhao). 0096-3003/S-see front matter 2002 Elsevier Inc.All rights reserved. doi10.1016/S0096-3003(02)00798-1
Perturbation analysis for the generalized Cholesky factorization Wei-guo Wang a , Jin-xi Zhao b,* a Department of Mathematics, Ocean University of Qingdao, Shandong 266071, PR China b State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, PR China Abstract Let K be a symmetric indefinite matrix. Suppose that K ¼ LJLT is the generalized Cholesky factorization of K. In this paper we present perturbation analysis for the generalized Cholesky factorization. We obtain the first-order bound on the norm of the perturbation in the generalized Cholesky factor. Also, we give rigorous perturbation bounds. 2002 Elsevier Inc. All rights reserved. Keywords: Generalized Cholesky factorization; Perturbation bounds; Augmented matrix 1. Introduction Consider the problem of solving the structured linear system A BT B C x y ¼ b d ; ð1Þ for x and y, where A 2 Rmm is symmetric positive definite matrix, B 2 Rmn, x, b 2 Rm, and y; d 2 Rn, C 2 Rnn. This system is called an augmented system, or an equilibrium system. The system (1) has been investigated by many authors for numerical algorithms. (See, [1,2,4,7,11,12]) * Corresponding author. Address: Department of Computer Science and Technology, Nanjing University, Nanjing 210008, China. E-mail address: jxzhao@nju.edu.cn (J. Zhao). 0096-3003/$ - see front matter 2002 Elsevier Inc. All rights reserved. doi:10.1016/S0096-3003(02)00798-1 Applied Mathematics and Computation 147 (2004) 601–606 www.elsevier.com/locate/amc
602 W.Wang.J.Zhao Appl.Math.Comput.147 (2004)601-606 In [1],the generalized Cholesky factorization is presented and this method inherits the advantage of Cholesky factorization with small storage and low computation costs.We first derive the generalized Cholesky factorization theorem. Theorem 1.1 [1].Given any symmetric indefinite matrix K= -C (2) where A,B and C are the same as that defined in (1).Then we have K=LJLT, (3) =(e)J-(-) (4) where Ln E Rmxm and L2 E Raxh are lower triangular,La E R"xm,Im and In are identity matrices. Letr=K+△be a perturbation of K in which△K is symmetric.If△Kis sufficiently small,then K also has a generalized Cholesky factorization: K+△K=(L+△L)J(L+△L)T (5) There have been several results dealing with the perturbation analysis for the Cholesky factor (see [3,8,9)).They obtained the first-order perturbation result. The result is sharpened in [5,6]. About (5),K.Veslic [10]has given some eigenvalue perturbation results.In this paper we derive the first-order perturbation bound and the rigorous per- turbation bound for the generalized Cholesky factorization. 2.Perturbation theorems for the generalized Cholesky factorization In the section,two perturbation theorems on the generalized Cholesky factor will be given.The symbols ll2 and llE will be used for the spectral norm and the Frobenius norm,respectively. We need a lemma controlling the triangular indefinite decomposition of J+N for small N. Lemma 2.1 [10].Let N be a Hermitian matrix withN<1/2,then there exists a unique lower triangular matrix such that J+N=(I+)J(I+*)
In [1], the generalized Cholesky factorization is presented and this method inherits the advantage of Cholesky factorization with small storage and low computation costs. We first derive the generalized Cholesky factorization theorem. Theorem 1.1 [1]. Given any symmetric indefinite matrix K ¼ A BT B C ; ð2Þ where A, B and C are the same as that defined in (1). Then we have K ¼ LJLT; ð3Þ L ¼ L11 L21 L22 ; J ¼ Im In ; ð4Þ where L11 2 Rmm and L22 2 Rnn are lower triangular, L21 2 Rnm; Im and In are identity matrices. Let Ke ¼ K þ DK be a perturbation of K in which DK is symmetric. If DK is sufficiently small, then Ke also has a generalized Cholesky factorization: K þ DK ¼ ðL þ DLÞJðL þ DLÞ T : ð5Þ There have been several results dealing with the perturbation analysis for the Cholesky factor (see [3,8,9]). They obtained the first-order perturbation result. The result is sharpened in [5,6]. About (5), K. Veslic [10] has given some eigenvalue perturbation results. In this paper we derive the first-order perturbation bound and the rigorous perturbation bound for the generalized Cholesky factorization. 2. Perturbation theorems for the generalized Cholesky factorization In the section, two perturbation theorems on the generalized Cholesky factor will be given. The symbols kk2 and kkF will be used for the spectral norm and the Frobenius norm, respectively. We need a lemma controlling the triangular indefinite decomposition of J þ N for small N. Lemma 2.1 [10]. Let N be a Hermitian matrix with kNk < 1=2, then there exists a unique lower triangular matrix such that J þ N ¼ ðI þ CÞJðI þ C Þ; 602 W. Wang, J. Zhao / Appl. Math. Comput. 147 (2004) 601–606
W.Wang.J.Zhao Appl.Math.Comput.147 (2004)601-606 603 where V2 Irle≤1+√-2NIie Theorem 2.2.Let K be a symmetric indefinite matrix and K =LJLT its gener- alized Cholesky factorization,let GER(m+m)x(m+m)be symmetric matrix,and let △K=eG,for some s≥0.If LL) (6) then K AK has the unique generalized Cholesky factorization, K+△K=(L+△L)W(L+△L)I (7) with△L satisfying △L=L(0)+O(8), (8) where L(O)is defined by the unique generalized Cholesky factorization K+tG=L()JL(t),lt≤e (9) and so satisfies the equations LJLT(0)+L(0)JLT =G. (10) iT(0)=J up(L-'GL-TLT), (11) where the up'and low'notation is defined by X12·X1 up(X)= x22·X2n (12) 0 0 low(X)=X-up(X)=up(XT)T. (13) Proof.If (6)holds,then for all t<&the spectral radius of tL-GL-T satisfies p(L-GL-T)=p(tL-TL-G)=p(I(LLT)G)< Therefore for all t,K+tG=L(J+tL-GL-)LI is symmetric non- singular matrix,andJ+L-GL-T has m positive eigenvalues and n negative eigenvalues.From the previous Lemma 2.1.,so K+tG has the generalized Cholesky factorization (9).Notice that R(0)=R and R(s)=R+AR,so (7) holds
where kCkF 6 ffiffiffi 2 p 1 þ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 1 2kNkF p : Theorem 2.2. Let K be a symmetric indefinite matrix and K ¼ LJLT its generalized Cholesky factorization, let G 2 RðmþnÞðmþnÞ be symmetric matrix, and let DK ¼ eG, for some e P0. If qððLLTÞ 1 DKÞ < 1 2 ; ð6Þ then K þ DK has the unique generalized Cholesky factorization, K þ DK ¼ ðL þ DLÞJðL þ DLÞ T ; ð7Þ with DL satisfying DL ¼ eL_ð0Þ þ Oðe 2 Þ; ð8Þ where L_ð0Þ is defined by the unique generalized Cholesky factorization K þ tG ¼ LðtÞJLTðtÞ; jtj 6 e; ð9Þ and so satisfies the equations LJL_ Tð0Þ þ L_ð0ÞJLT ¼ G; ð10Þ L_ Tð0Þ ¼ J upðL1 GLTLTÞ; ð11Þ where the ‘up’and ‘low’ notation is defined by upðXÞ ¼ 1 2 x11 x12 x1n 0 1 2 x22 x2n 0 0 xnn 0 BB@ 1 CCA; ð12Þ lowðXÞ ¼ X upðXÞ ¼ upðX TÞ T : ð13Þ Proof. If (6) holds, then for all jtj 6 e the spectral radius of tL1GLT satisfies qðtL1 GLTÞ ¼ qðtLTL1 GÞ ¼ qðtðLLTÞ 1 GÞ < 1 2 : Therefore for all jtj 6 e, K þ tG ¼ LðJ þ tL1GLTÞLT is symmetric nonsingular matrix, and J þ tL1GLT has m positive eigenvalues and n negative eigenvalues. From the previous Lemma 2.1., so K þ tG has the generalized Cholesky factorization (9). Notice that Rð0Þ ¼ R and RðeÞ ¼ R þ DR, so (7) holds. W. Wang, J. Zhao / Appl. Math. Comput. 147 (2004) 601–606 603
604 W.Wang.J.Zhao Appl.Math.Comput.147 (2004)601-606 If we differentiate(9)and set t=0 in the result we obtain the linear equation (10).From upper triangular LT(0)L-T in (JLT(0)L-T)T+JLT(0)L-T =L-GL-T, we see with the 'up'notation in (12)that (11)holds.Finally the Taylor ex- pansion for R(t)about t=0 gives(⑧)att=e.□ Using Theorem 2.2 we can now easily obtain the first-order perturbation bound by a different approach. Theorem 2.3.Let K be symmetric indefinite matrix and K =LILT be generalized Cholesky factorization,and let AK be a real symmetric matrix satisfying △Kle≤lK2.If L-K2< (14) then K+AK has the generalized Cholesky factorization K+△K=(L+△L)J(L+△L)I (15) where 先≤方肛s+o (16) Proof.Let G=AK/a(if 8=0,the theorem is trivial).Then IGe≤Kl2: since puAK)≤ILu'aKk≤IL-1lK2< So the conclusion of Theorem 2.2 hold here.Because 2upX)f=2ow(X)呢=XI呢-，++…+)≤X唯， i.e.llup(x)(1/v2)for any symmetric X. We have from (11)that lliT(0)IlE up(L-'GL-T)LTIlE luP(L-GL-)L'GL-TIlLT ≤万L-Il2:lGle, (18)
If we differentiate (9) and set t ¼ 0 in the result we obtain the linear equation (10). From upper triangular L_ Tð0ÞLT in ðJL_ Tð0ÞLTÞ T þ JL_ Tð0ÞLT ¼ L1 GLT; we see with the up notation in (12) that (11) holds. Finally the Taylor expansion for RðtÞ about t ¼ 0 gives (8) at t ¼ e. Using Theorem 2.2 we can now easily obtain the first-order perturbation bound by a different approach. Theorem 2.3. Let K be symmetric indefinite matrix and K ¼ LJLT be generalized Cholesky factorization, and let DK be a real symmetric matrix satisfying kDKkF 6 ekKk2. If ekL1 k2 2kKk2 < 1 2 ; ð14Þ then K þ DK has the generalized Cholesky factorization K þ DK ¼ ðL þ DLÞJðL þ DLÞ T ; ð15Þ where kDLkF kLk2 6 1 ffiffiffi 2 p kL1 k 2 2kKk2e þ Oðe 2 Þ: ð16Þ Proof. Let G DK=e (if e ¼ 0, the theorem is trivial). Then kGkF 6 kKk2; ð17Þ since qððLLTÞ 1 DKÞ 6 kðLLTÞ 1 DKk2 6 kL1 k2 2ekKk2 < 1 2 : So the conclusion of Theorem 2.2 hold here. Because 2kupðXÞk2 F ¼ 2klowðXÞk2 F ¼ kXk 2 F 1 2 ðx2 11 þ x2 22 þþ x2 nnÞ 6 kXk2 F; i.e. kupðXÞkF 6 ð1= ffiffiffi 2 p ÞkXkF for any symmetric X. We have from (11) that kL_ Tð0ÞkF ¼ kJ upðL1 GLTÞLTkF ¼ kupðL1 GLTÞLTkF 6 1 ffiffiffi 2 p kL1 GLTkFkLTk2 6 1 ffiffiffi 2 p kLTk 2 2kLTk2kGkF; ð18Þ 604 W. Wang, J. Zhao / Appl. Math. Comput. 147 (2004) 601–606
W.Wang.J.Zhao Appl.Math.Comput.147 (2004)601-606 605 which,with(17),gives 器s方上guL: (19) Then from the Taylor expansion,(16)follows immediately. Clearly from(16)we see (1/v2)2 can be regarded as a measure of the sensitivity of the generalized Cholesky factorization. 3.New perturbation bound Multiplying out the right-hand side of(5)and ignoring higher-order terms, we obtain a linear matrix equation for first-order approximation AL to AL [5] LLT+LLT=△K, (20) About this equation,Our basic result is the following L=Llow(L-1△KJL)-)andL=up(L-1△KJL)-)JLT) To see this,write L(up(L-AK(JLT))(JLT))+L (low(L-AK(JLT))(LT)) =L(L-1△K(JULT)-JALT=△K. We can take norms in the expressions ALT and AL to get first-order per- turbation bounds for the generalized Cholesky factorization,but it is possible to introduce degrees of freedom in the expressions that can later used to reduce the bounds.Specifically,for any nonsingular diagonal matrix D,we have L=Llow(L-l△K(LT)-)=LDLlow(DL-1△K(JLT)) =立low(亿-1△K(JLT)-), consequently I△LlEe=Zlow(亿-△KJL)-Ie≤IZIl2Z-2ll△K2IZ-TIl2 =L-TI2MAKIlE (21) 01 Haa路 IZ2 where (L)=2-
which, with (17), gives kL_ Tð0ÞkF kLTk2 6 1 ffiffiffi 2 p kLTk 2 2kKk2: ð19Þ Then from the Taylor expansion, (16) follows immediately. Clearly from (16) we see ð1= ffiffiffi 2 p ÞkL1k2 2kKk2 can be regarded as a measure of the sensitivity of the generalized Cholesky factorization. 3. New perturbation bound Multiplying out the right-hand side of (5) and ignoring higher-order terms, we obtain a linear matrix equation for first-order approximation D fL to DL [5] LD fLT þ D fLLT ¼ DK: ð20Þ About this equation, Our basic result is the following D fL ¼ L lowðL1 DKðJLTÞ 1 Þ and D fLT ¼ upðL1 DKðJLTÞ 1 ÞðJLTÞ: To see this, write LðupðL1 DKðJLTÞ 1 ÞðJLTÞÞ þ L ðlowðL1 DKðJLTÞ 1 ÞðJLTÞÞ ¼ LðL1 DKðJLTÞ 1 ÞJDLT ¼ DK: We can take norms in the expressions D fLT and D fL to get first-order perturbation bounds for the generalized Cholesky factorization, but it is possible to introduce degrees of freedom in the expressions that can later used to reduce the bounds. Specifically, for any nonsingular diagonal matrix DL, we have D fL ¼ L lowðL1 DKðJLTÞ 1 Þ ¼ LDLlowðD1 L L1 DKðJLTÞ 1 Þ ¼ bL lowðbL1 DKðJLTÞ 1 Þ; consequently kD fLkF ¼ kbL lowðbL1 DKðJLTÞ 1 ÞkF 6 kbLk2kbL1 k2kDKkFkJk2kLTk2 ¼ kbLk2kbL1 k2kLTk2kDKkF; ð21Þ or kD fLkF kLk2 6 jðbLÞjðLÞ kDKkF kLk 2 2 ; where jðLÞ¼kLk2kL1k2. W. Wang, J. Zhao / Appl. Math. Comput. 147 (2004) 601–606 605
606 W.Wang.J.Zhao Appl.Math.Comput.147 (2004)601-606 Since Kl2,we have IA应SK①x()JAKE 匹2 IKI If K(L)=1(it cannot be less),then the bound(21)reduces to I△Lle≤lL-1l2 AKIF (22) References [1]J.Zhao,The generalized Cholesky factorization method for solving saddle point problems, Appl.Math.Comput.92 (1998)49-58. [2]G.H.Golub,C.F.Vanloan,Matrix Computation,third ed.,The Johns Hopkins University Press,Baltimore,MD,1996. [3]J.Sun,Perturbation bounds for the Cholesky and QR factorizations,BIT 31(1991)341-352. [4]P.E.Gill,M.A.Saunders,J.R.Shinnerl,On the stability of Cholesky factorization for symmetric quasidefinite systems,SIAM J.Matrix Anal.Appl.17(1)(1996)35-46. [5]G.W.Stewart.On the Perturbation of LU and Cholesky factors,IMA J.Numer.Anal.17 (1997)1-6. [6]X.Chang,C.C.Paige,G.W.Stewart,New perturbation analyses for the Cholesky fac- torization.IMA J.Numer.Anal.16(1996)457-484. [7]A.Forsgren,P.E.Gill,J.R.Shinnerl,Stability of symmetric ill-conditioned systems arising in interior methods for constrained optimization,SIAM J.Matrix Anal.17(1)(1996)187-211. [8]J.Stoer,R.Bulirsch,Introduction to Numerical Analysis,second ed.,Springer-Verlag.New York,1993. [9]G.W.Stewart,Perturbation bounds for the QR factorization of matrix,SIAM J.Numer.Anal. 14(1977509-518. [10]K.Veslic,Perturbation theory for the eigenvalues of factorised symmetric matrices,Linear Algebra Appl.309(2000)85-102. [11]A.Bjorck,C.C.Paige,Solution of augmented linear systems using orthogonal factorizations. BIT34(1994)1-24. [12]A.Bjorck,Numerical stability of methods for solving augmented systems,Contemp.Math. 204(1997)51-60
Since kKk2 6 kLk 2 2, we have kD fLkF kLk2 6 jðbLÞjðLÞ kDKkF kKk2 : If KðbLÞ ¼ 1(it cannot be less), then the bound (21) reduces to kD fLkF 6 kL1 k2kDKkF: ð22Þ References [1] J. Zhao, The generalized Cholesky factorization method for solving saddle point problems, Appl. Math. Comput. 92 (1998) 49–58. [2] G.H. Golub, C.F. Vanloan, Matrix Computation, third ed., The Johns Hopkins University Press, Baltimore, MD, 1996. [3] J. Sun, Perturbation bounds for the Cholesky and QR factorizations, BIT 31 (1991) 341–352. [4] P.E. Gill, M.A. Saunders, J.R. Shinnerl, On the stability of Cholesky factorization for symmetric quasidefinite systems, SIAM J. Matrix Anal. Appl. 17 (1) (1996) 35–46. [5] G.W. Stewart, On the Perturbation of LU and Cholesky factors, IMA J. Numer. Anal. 17 (1997) 1–6. [6] X. Chang, C.C. Paige, G.W. Stewart, New perturbation analyses for the Cholesky factorization, IMA J. Numer. Anal. 16 (1996) 457–484. [7] A. Forsgren, P.E. Gill, J.R. Shinnerl, Stability of symmetric ill-conditioned systems arising in interior methods for constrained optimization, SIAM J. Matrix Anal. 17 (1) (1996) 187–211. [8] J. Stoer, R. Bulirsch, Introduction to Numerical Analysis, second ed., Springer-Verlag, New York, 1993. [9] G.W. Stewart, Perturbation bounds for the QR factorization of matrix, SIAM J. Numer. Anal. 14 (1977) 509–518. [10] K. Veslic, Perturbation theory for the eigenvalues of factorised symmetric matrices, Linear Algebra Appl. 309 (2000) 85–102. [11] A. Bj orck, C.C. Paige, Solution of augmented linear systems using orthogonal factorizations, € BIT 34 (1994) 1–24. [12] A. Bj orck, Numerical stability of methods for solving augmented systems, Contemp. Math. € 204 (1997) 51–60. 606 W. Wang, J. Zhao / Appl. Math. Comput. 147 (2004) 601–606