Analysis of the Cholesky Decomposition of a Semi-Definite Matrix

Perturbation theory is developed for the Cholesky decomposition of an n \Theta n symmetric positive semi-definite matrix A of rank r. The matrix W = A \Gamma1 11 A 12 is found to play a key role in the perturbation bounds, where A 11 and A 12 are r \Theta r and r \Theta (n \Gamma r) submatrices of A respectively. A backward error analysis is given; it shows that the computed Cholesky factors are the exact ones of a matrix whose distance from A is bounded by 4r(r + 1) \Gamma kWk 2 +1 \Delta 2 ukAk 2 +O(u 2 ), where u is the unit roundoff. For the complete pivoting strategy it is shown that kWk 2 2 1 3 (n \Gamma r)(4 r \Gamma 1), and empirical evidence that kWk 2 is usually small is presented. The overall conclusion is that the Cholesky algorithm with complete pivoting is stable for semi-definite matrices. Similar perturbation results are derived for the QR decomposition with column pivoting and for the LU decomposition with complete pivoting. The results give new insig..