EE103 (Fall 2008-09)5. The Cholesky factorization• positive (semi-)definite matrices• examples• the Cholesky factorization• solving Ax = b with A positive definite• inverse of a positive definite matrix• permutation matrices• sparse Cholesky factorization5–1Positive (semi-)definite matrices• A is positive definite if A is symmetric andxTAx > 0 for all x 6= 0• A is positive semidefinite if A is symmetric andxTAx ≥ 0 for all xNote: if A is symmetric of order n, thenxTAx =nXi=1nXj=1aijxixj=nXi=1aiix2i+ 2Xi>jaijxixjThe Cholesky factorization 5–2ExamplesA1=9 66 5, A2=9 66 4, A3=9 66 3• A1is positive definite:xTA1x = 9x21+ 12x1x2+ 5x22= (3x1+ 2x2)2+ x22• A2is positive semidefinite but not positive definite:xTA2x = 9x21+ 12x1x2+ 4x22= (3x1+ 2x2)2• A3is not positive semidefinite:xTA3x = 9x21+ 12x1x2+ 3x22= (3x1+ 2x2)2− x22The Cholesky factorization 5–3Examples• A = BTB for some matrix BxTAx = xTBTBx = kBxk2A is positive semidefiniteA is positive definite if B has a zero nullspace• diagonal AxTAx = a11x21+ a22x22+ ··· + annx2nA is positive semidefinite if its diagonal elements are nonnegativeA is positive definite if its diagonal elements are positiveThe Cholesky factorization 5–4Another exampleA =1 −1 ··· 0 0−1 2 ··· 0 0...............0 0 ··· 2 −10 0 ··· −1 1A is positive semidefinite:xTAx = (x1− x2)2+ (x2− x3)2+ ··· + (xn−1− xn)2≥ 0A is not positive definite:xTAx = 0 for x = (1, 1, . . . , 1)The Cholesky factorization 5–5Resistor circuity1y2x1x2R1R2R3Circuit model: y = Ax withA =R1+ R3R3R3R2+ R3(R1, R2, R3> 0)Interpretation of xTAx = yTxxTAx is the power delivered by the sources, dissipated by the resistorsThe Cholesky factorization 5–6A is positive definite, i.e., xTAx > 0 for all nonzero x• proof from physics:power dissipated by the resistors is positive unless both currents are zero• algebraic proof:xTAx = (R1+ R3)x21+ 2R3x1x2+ (R2+ R3)x22= R1x21+ R2x22+ R3(x1+ x2)2≥ 0and xTAx = 0 only if x1= x2= 0The Cholesky factorization 5–7Propertiesif A is positive definite of order n, then• A has a zero nullspaceproof: xTAx > 0 for all nonzero x, hence Ax 6= 0 if x 6= 0• the diagonal elements of A are positiveproof: aii= eTiAei> 0 (eiis the ith unit vector)• A22− (1/a11)A21AT21is positive definite, where A =a11AT21A21A22proof: take any v 6= 0 and w = −(1/a11)AT21vvTA22−1a11A21AT21v =w vT a11AT21A21A22wv> 0The Cholesky factorization 5–8Cholesky factorizationevery positive definite matrix A can be factored asA = LLTwhere L is lower triangular with positive diagonal elementsCost: (1/3)n3flops if A is of order n• L is called the Cholesky factor of A• can be interpreted as ‘square root’ of a positive define matrixThe Cholesky factorization 5–9Cholesky factorization algorithmpartition matrices in A = LLTasa11AT21A21A22=l110L21L22l11LT210 LT22=l211l11LT21l11L21L21LT21+ L22LT22Algorithm1. determine l11and L21:l11=√a11, L21=1l11A212. compute L22fromA22− L21LT21= L22LT22this is a Cholesky factorization of order n − 1The Cholesky factorization 5–10Proof that the algorithm works for positive definite A of order n• step 1: if A is p ositive definite then a11> 0• step 2: if A is p ositive definite, thenA22− L21LT21= A22−1a11A21AT21is positive definite (see page 5–8)• hence the algorithm works for n = m if it works for n = m − 1• it obviously works for n = 1; therefore it works for all nThe Cholesky factorization 5–11Example25 15 −515 18 0−5 0 11=l110 0l21l220l31l32l33l11l21l310 l22l320 0 l33• first column of L25 15 −515 18 0−5 0 11=5 0 03 l220−1 l32l335 3 −10 l22l320 0 l33• second column of L18 00 11−3−13 −1 =l220l32l33l22l320 l339 33 10=3 01 l333 10 l33The Cholesky factorization 5–12• third column of L: 10 − 1 = l233, i.e., l33= 3conclusion:25 15 −515 18 0−5 0 11=5 0 03 3 0−1 1 35 3 −10 3 10 0 3The Cholesky factorization 5–13Solving equations with positive definite AAx = b (A positive definite of order n)Algorithm• factor A as A = LLT• solve LLTx = b– forward substitution Lz = b– back substitution LTx = zCost: (1/3)n3flops• factorization: (1/3)n3• forward substitution: n2• backward substitution: n2The Cholesky factorization 5–14Inverse of a positive definite matrixsuppose A is positive definite with Cholesky factorization A = LLT• L is invertible (its diagonal is nonzero; see lecture 4)• X = L−TL−1is a right inverse of A:AX = LLTL−TL−1= LL−1= I• X = L−TL−1is a left inverse of A:XA = L−TL−1LLT= L−TLT= I• hence, A is invertible andA−1= L−TL−1The Cholesky factorization 5–15Summaryif A is positive definite of order n• A can be factored as LLT• the cost of the factorization is (1/3)n3flops• Ax = b can be solved in (1/3)n3flops• A is invertible: A−1= L−TL−1• A has a full range: Ax = b is solvable for all b• A has a zero nullspace: xTAx > 0 for all nonzero xThe Cholesky factorization 5–16Sparse positive definite matrices• a matrix is sparse if most of its elements are zero• a matrix is dense if it is not sparseCholesky factorization of dense matrices• (1/3)n3flops• on a current PC: a few seconds or less, for n up to a few 1000Cholesky factorization of sparse matrices• if A is very sparse, then L is often (but not always) sparse• if L is sparse, the cost of the factorization is much less than (1/3)n3• exact cost depends on n, #nonzero elements, sparsity pattern• very large sets of equations (n ∼ 106) are solved by exploiting sparsityThe Cholesky factorization 5–17Effect of orderingSparse equation (a is an (n − 1)-vector with kak < 1)1 aTa Iuv=bcFactorization1 aTa I=1 0a L221 aT0 LT22where I − aaT= L22LT22=×factorization with 100% fill-inThe Cholesky factorization 5–18Reordered equationI aaT1vu=cbFactorizationI aaT1=I 0aT√1 − aTaI a0√1 − aTa=×factorization with zero fill-inThe Cholesky factorization 5–19Permutation matricesa permutation matrix is the identity matrix with its rows reordered, e.g.,0 1 01 0 00 0 1,0 1 00 0 11 0 0• the vector Ax is a permutation of x0 1 00 0
View Full Document
Unlocking...