Perturbation Analyses for the Cholesky Downdating Problem
Xiao-Wen Chang, Christopher C. Paige · SIAM Journal on Matrix Analysis and Applications · 1998
New perturbation analyses are presented for the block Cholesky downdating problem U T U = R T R - X T X . These show how changes in R and X alter the Cholesky factor U. There are two main cases for the perturbation matrix $\D R$ in R: (1) $\D R$ is a general matrix; (2)$\D R$ is an upper triangular matrix. For both cases, first-order perturbation bounds for the downdated Cholesky factor U are given using two approaches --- a detailed "matrix--vector equation" analysis which provides tight bounds and resulting true condition numbers, which unfortunately are costly to compute, and a simpler "matrix equation" analysis which provides results that are weaker but easier to compute or estimate. The analyses more accurately reflect the sensitivity of the problem than previous results. As $X\rightarrow 0$, the asymptotic values of the new condition numbers for case (1) have bounds that are independent of $\kappa_2(R)$ if R was found using the standard pivoting strategy in the Cholesky factorization, and the asymptotic values of the new condition numbers for case (2) are unity. Simple reasoning shows this last result must be true for the sensitivity of the problem, but previous condition numbers did not exhibit this.}