AND

We present new perturbation analyses, for the Cholesky factorization A = RJR of a symmetric positive definite matrix A. The analyses more accurately reflect the sensitivity of the problem than previous normwise results. The condition numbers here are altered by any symmetric pivoting used in PAP1 = RTR, and both numerical results and an analysis show that the standard method of pivoting is optimal in that it usually leads to a condition number very close to its lower limit for any given A. It follows that the computed R will probably have greatest accuracy when we use the standard symmetric pivoting strategy. Initially we give a thorough analysis to obtain both first-order and strict normwise 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 componentwise 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 with 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 results. We derive a useful upper bound on the condition of the problem when we use pivoting. 1