The Cholesky factorization of a symmetric positive definite matrix is the factorization , where is upper triangular with positive diagonal elements. It is a generalization of the property that a positive real number has a unique positive square root. The Cholesky factorization always exists and the requirement that the diagonal of be positive ensures that it is unique.
As an example, the Cholesky factorization of the matrix with element (
gallery('gcdmat',4) in MATLAB) is
The Cholesky factorization of an matrix contains other Cholesky factorizations within it: , , where is the leading principal submatrix of order . For example, for with , .
Inverting the Cholesky equation gives , which implies the interesting relation that the element of is . So has element . We also have , so for this matrix.
The Cholesky factorization is named after André-Louis Cholesky (1875–1918), a French military officer involved in geodesy and surveying in Crete and North Africa, who developed it for solving the normal equations arising in least squares problems.
The existence and uniqueness of the factorization can be proved by induction on , and the proof also serves as a method for computing it. Partition as
We know that is positive definite (any principal submatrix of a positive definite matrix is easily shown to be positive definite). Assume that has a unique Cholesky factorization and define the upper triangular matrix
which equals if and only if
The first equation has a unique solution since is nonsingular. Then the second equation gives . It remains to check that there is a unique real, positive satisfying this equation. From the inequality
we see that , hence there is a unique . This completes the inductive step.
The quantity is the Schur complement of in . The essential reason why Cholesky factorization works is that the Schur complements of a positive definite matrix are themselves positive definite. Indeed we have the congruence
and since congruences preserve definiteness it follows that .
In textbooks it is common to see element-level equations for computing the Cholesky factorization, which come from directly solving the matrix equation . If we equate elements on both sides, taking them a column at a time, starting with , then the following algorithm is obtained:
What happens if this algorithm is executed on a general (indefinite) symmetric matrix that is, one that has both positive and negative eigenvalues? Line 5 will either attempt to take the square root of a negative number for some or it will produce and on the next iteration of the loop we will have a division by zero. In floating-point arithmetic it is possible for the algorithm to fail for a positive definite matrix, but only if it is numerically singular: the algorithm is guaranteed to run to completion if the condition number is safely less than , where is the unit roundoff.
The MATLAB function
chol normally returns an error message if the factorization fails. But a second output argument can be requested, which is set to the number of the stage on which the factorization failed, or to zero if the factorization succeeded. In the case of failure, the partially computed factor, returned in the first argument, can be used to compute a direction of negative curvature for , which is a vector such that . Here is an example. The code
n = 8; A = gallery('lehmer',n) - 0.3*eye(n); % Indefinite matrix. [R,p] = chol(A) z = [-R\(R'\A(1:p-1,p)); 1; zeros(n-p,1)]; neg_curve = z'*A*z
produces the output
R = 8.3666e-01 5.9761e-01 3.9841e-01 0 5.8554e-01 7.3193e-01 0 0 7.4536e-02 p = 4 neg_curve = -9.1437e+00
Cholesky factorization has excellent numerical stability. The computed factor satisfies
where is a constant. Unlike for LU factorization there is no possibility of element growth; indeed for ,
so the elements of are nicely bounded relative to those of .
Once we have a Cholesky factorization we can use it to solve a linear system , by solving the lower triangular system and then the upper triangular system . The computed solution can be shown to satisfy
where is another constant. Thus has a small backward error.
Finally, what if is only symmetric positive semidefinite, that is, for all , so that is possibly singular? There always exists a Cholesky factorization (we can take the factor in the QR factorization of the positive semidefinite square root of ) but it may not be unique. For example, we have
for any and such that . Note that has rank 3 but has two zero diagonal elements. When is positive semidefinite of rank what is usually wanted is a Cholesky factorization in which is zero in its last rows. Such a factorization can be obtained by using complete pivoting, which at each stage permutes the largest remaining diagonal element into the pivot position, which gives a factorization
where is a permutation matrix. For example, with the identity matrix with its columns in reverse order,
which clearly displays the rank of .
This is a minimal set of references, which contain further useful references within.
- Claude Brezinski, The Life and Work of André Cholesky, Numer. Algorithms 43, 279–288, 2006.
- Nicholas J. Higham, Cholesky factorization, WIREs Comp. Stat. 1(2), 251–254, 2009.
- Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, second edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2002. Chapter 10.
Related Blog Posts
This article is part of the “What Is” series, available from https://nhigham.com/category/what-is and in PDF form from the GitHub repository https://github.com/higham/what-is.
One thought on “What Is a Cholesky Factorization?”
Thank you for your blogger and article, it’s been a great help to me.
This blog says ” the cholesky is guaranteed to run to completion if the condition number k2(A) is safely less than u^-1″. But you have used Wilkinson’s bound in other articles and books, namely 20n^(3/2)*k2(A)*u^-1 < 1. Did I miss something?