Let A be a symmetric positive definite nn matrix. (a) If k < n, then the leading

Chapter 6, Problem 14

(choose chapter or problem)

Let A be a symmetric positive definite nn matrix. (a) If k < n, then the leading principal submatrices Ak and Ak+1 are both positive definite and, consequently, have Cholesky factorizations Lk LT k and Lk+1LT k+1. If Ak+1 is expressed in the form Ak+1 = Ak yk yT k k where yk Rk and k is a scalar, show that Lk+1 is of the form Lk+1 = Lk 0 xT k k and determine xk and k in terms of Lk , yk , and k . (b) The leading principal submatrix A1 has Cholesky decomposition L1LT 1 , where L1 = ( a11 ). Explain how part (a) can be used to compute successively the Cholesky factorizations of A2, . . . , An. Devise an algorithm that computes L2, L3, . . . , Ln in a single loop. Since A = An, the Cholesky decomposition of A will be LnLT n . (This algorithm is efficient in that it uses approximately half the amount of arithmetic that would generally be necessary to compute an LU factorization.)