PERTURBATION ANALYSES FOR THE CHOLESKY DOWNDATING PROBLEM

New perturbation analyses are presented for the block Cholesky downdat ing problem U-T U = R-T R - X-T X. These show how changes in R and X a lter the Cholesky factor U. There are two main cases for the perturbat ion matrix Delta R in R: (1) Delta R is a general matrix; (2)Delta R i s an upper triangular matrix. For both cases, first-order perturbation bounds for the downdated Cholesky factor U are given using two approa ches - a detailed ''matrix-vector equation'' analysis which provides t ight bounds and resulting true condition numbers, which unfortunately are costly to compute, and a simpler ''matrix equation'' analysis whic h provides results that are weaker but easier to compute or estimate. The analyses more accurately reflect the sensitivity of the problem th an previous results. As X --> 0, the asymptotic values of the new cond ition numbers for case (1) have bounds that are independent of kappa(2 )(R) if R was found using the standard pivoting strategy in the Choles ky factorization, and the asymptotic values of the new condition numbe rs for case (2) are unity. Simple reasoning shows this last result mus t be true for the sensitivity of the problem, but previous condition n umbers did not exhibit this.