NEW PERTURBATION ANALYSES FOR THE CHOLESKY FACTORIZATION

We present new perturbation analyses. for the Cholesky factorization A = R(T)R of a symmetric positive definite matrix A. The analyses more accurately reflect the sensitivity of the problem than previous normwi se results. The condition numbers here are altered by any symmetric pi voting used in PAP(T) = R(T)R, and both numerical results and an analy sis show that the standard method of pivoting is optimal in that it us ually leads to a condition number very close to its lower limit for an y given A. It follows that the computed R will probably have greatest accuracy when we use the standard symmetric pivoting strategy. Initial ly we give a thorough analysis to obtain both first-order and strict n ormwise perturbation bounds which are as tight as possible, leading to a definition of an optimal condition number for the problem. Then we use this approach to obtain reasonably clear first-order and strict co mponentwise perturbation bounds. We complete the work by giving a much simpler normwise analysis which provides a somewhat weaker bound, but which allows us to estimate the condition of the problem quite well w ith an efficient computation. This simpler analysis also shows why the factorization is often less sensitive than we previously thought, and adds further insight into why pivoting usually gives such good result s. We derive a useful upper bound on the condition of the problem when we use pivoting.