Mathematics    

Cholesky Factorization

The Cholesky factorization expresses a symmetric matrix as the product of a triangular matrix and its transpose

where R is an upper triangular matrix.

Not all symmetric matrices can be factored in this way; the matrices that have such a factorization are said to be positive definite. This implies that all the diagonal elements of A are positive and that the offdiagonal elements are "not too big." The Pascal matrices provide an interesting example. Throughout this chapter, our example matrix A has been the 3-by-3 Pascal matrix. Let's temporarily switch to the 6-by-6.

The elements of A are binomial coefficients. Each element is the sum of its north and west neighbors. The Cholesky factorization is

The elements are again binomial coefficients. The fact that R'*R is equal to A demonstrates an identity involving sums of products of binomial coefficients.

The Cholesky factorization allows the linear system

to be replaced by

Because the backslash operator recognizes triangular systems, this can be solved in MATLAB quickly with

If A is n-by-n, the computational complexity of chol(A) is O(n3), but the complexity of the subsequent backslash solutions is only O(n2).


  Cholesky, LU, and QR Factorizations LU Factorization