In mathematics, the Cholesky decomposition, named after André-Louis Cholesky, is a matrix decomposition of a symmetric positive-definite matrix into a lower triangular matrix and the transpose of the lower triangular matrix. The lower triangular matrix is the Cholesky triangle of the original, positive-definite matrix. Euclid, detail from The School of Athens by Raphael. ... André-Louis Cholesky (October 15, 1875 - August 31, 1918) was a French mathematician born in Jonzac, France. ... In the mathematical discipline of linear algebra, a matrix decomposition is a factorization of a matrix into some canonical form. ... In linear algebra, a symmetric matrix is a matrix that is its own transpose. ... In linear algebra, a positive-definite matrix is a Hermitian matrix which in many ways is analogous to a positive real number. ... In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix where the entries below or above the main diagonal are zero. ... In mathematics, and in particular linear algebra, the transpose of a matrix is another matrix, produced by turning rows into columns and vice versa. ...

Any square matrix A can be written as the product of a lower triangular matrix L and an upper triangular matrix U; this is called the LU decomposition. However, if A is symmetric and positive definite, we can choose the factors such that U is the transpose of L, and this is called the Cholesky decomposition. Both the LU and the Cholesky decomposition are used to solve systems of linear equations. When it is applicable, the Cholesky decomposition is twice as efficient as the LU decomposition. In linear algebra, the LU decomposition is a matrix decomposition which writes a matrix as the product of a lower and upper triangular matrix. ... bnrgljabvkfjabvgkjavgbkjavgkjA linear equation is an equation involving only the sum of constants or products of constants and the first power of a variable. ...

Definition

Let A be a symmetric positive-definite matrix of real numbers, then A can be decomposed as

with L a lower triangular matrix with positive diagonal entries, and L^T the transpose of L.

Extension to complex numbers

This definition can be extended to matrices of complex numbers: If A is Hermitian and positive definite, then A can be decomposed as A Hermitian matrix (or self-adjoint matrix) is a square matrix with complex entries which is equal to its own conjugate transpose — that is, the element in the ith row and jth column is equal to the complex conjugate of the element in the jth row and ith column, for...

where L^* denotes the conjugate transpose of L. In mathematics, the conjugate transpose or adjoint of an m-by-n matrix A with complex entries is the n-by-m matrix A* obtained from A by taking the transpose and then taking the complex conjugate of each entry. ...

The Cholesky decomposition is unique: given a Hermitian, positive-definite matrix A, there is only one lower triangular matrix L with positive diagonal entries such that A = LL^*. The converse is also true: if A can be written as LL^*, with L lower triangular with positive diagonal entries, then A is Hermitian and positive definite.

Sometimes the requirement that L have positive diagonal entries is dropped. In that case, a square matrix A has a Cholesky decomposition if and only if A is Hermitian and positive semi-definite.

Applications

The Cholesky decomposition is mainly used for the numerical solution of linear equations Ax = b. If A is symmetric and positive definite, then we can solve Ax = b by first computing the Cholesky decomposition A = LL^T, then solving Ly = b for y, and finally solving L^Tx = y for x.

Systems of the form Ax = b with A symmetric and positive definite arise quite often in applications. For instance, the normal equations in linear least squares problems are of this form. It may also happen that matrix A comes from an energy functional which must be positive from physical considerations; this happens frequently in the numerical solution of partial differential equations. Linear least squares is a mathematical optimization technique to find an approximate solution for a system of linear equations that has no exact solution. ... In mathematics, a partial differential equation (PDE) is a relation involving an unknown function of several independent variables and its partial derivatives with respect to those variables. ...

The Cholesky decomposition is commonly used in the Monte Carlo method for simulating systems with multiple correlated variables: The matrix of inter-variable correlations is decomposed, to give the lower-triangular L. Applying this to a vector of uncorrelated simulated shocks, u, produces a shock vector Lu with the covariance properties of the system being modelled. Monte Carlo methods are a class of computational algorithms for simulating the behavior of various physical and mathematical systems. ... In probability theory and statistics, correlation, also called correlation coefficient, is a numeric measure of the strength of linear relationship between two random variables. ...

Unscented Kalman filters commonly use the Cholesky decomposition to choose a set of so-called sigma points. The Kalman filter tracks the average state of a system as a vector x of length N and covariance as an N-by-N matrix P. The matrix P is always positive semi-definite, and can be decomposed into LL^T. The columns of L can be added and subtracted from the mean x to form a set of 2N vectors called sigma points. These sigma points completely capture the mean and covariance of the system state. The Kalman filter is an efficient recursive filter which estimates the state of a dynamic system from a series of incomplete and noisy measurements. ...

Computing the Cholesky decomposition

There are various methods for calculating the Cholesky decomposition. The algorithms described below all involve about n³/3 FLOPs, where n is the size of the matrix A. Hence, they are twice as cheap as the LU decomposition, which uses 2n³/3 FLOPs. Look up flop in Wiktionary, the free dictionary. ... In linear algebra, the LU decomposition is a matrix decomposition which writes a matrix as the product of a lower and upper triangular matrix. ...

Which of the algorithms below is faster depends on the details on the implementation. Generally, the first algorithm will be slightly slower because it accesses the data in a more irregular manner.

The Cholesky algorithm

The Cholesky algorithm, used to calculate the decomposition matrix L, is a modified version of the Gauss algorithm. In mathematics, Gaussian elimination or Gauss-Jordan elimination, named after Carl Friedrich Gauss and Wilhelm Jordan, is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining the rank of a matrix, and for calculating the inverse of an invertible square matrix. ...

The recursive algorithm starts with i := 1 and

At step i, the matrix A⁽ⁱ⁾ has the following form:

where I_i−1 denotes the identity matrix of dimension i − 1. In linear algebra, the identity matrix of size n is the n-by-n square matrix with ones on the main diagonal and zeros elsewhere. ...

If we now define the matrix L_i by

then we can write A⁽ⁱ⁾ as

where

Note that b_i b_i^* is an outer product, therefore this algorithm is called the outer product version in (Golub & Van Loan). Outer product typically refers to the tensor product or to operations with similar cardinality such as exterior product. ...

We repeat this for i from 1 to n. After n steps, we get A⁽ⁿ⁺¹⁾ = I. Hence, the lower triangular matrix L we are looking for is calculated as

The Cholesky-Banachiewicz and Cholesky-Crout algorithms

If we write out the equation A = LL^*, we obtain the following formula for the entries of L:

The expression under the square root is always positive if A is real and positive-definite. In mathematics, the principal square root of a non-negative real number is denoted and represents the non-negative real number whose square (the result of multiplying the number by itself) is For example, since This example suggests how square roots can arise when solving quadratic equations such as or...

So we can compute the (i, j) entry if we know the entries to the left and above. The computation is usually arranged in either of the following orders.

• The Cholesky-Banachiewicz algorithm starts form the upper left corner of the matrix L and proceeds to calculate the matrix row by row.
• The Cholesky-Crout algorithm starts from the upper left corner of the matrix L and proceeds to calculate the matrix column by column.

Stability of the computation

Suppose that we want to solve a well-conditioned system of linear equations. If the LU decomposition is used, then the algorithm is unstable unless we use some sort of pivoting strategy. In the latter case, the error depends on the so-called growth factor of the matrix, which is usually (but not always) small. In numerical analysis, the condition number associated with a numerical problem is a measure of that quantitys amenability to digital computation, that is, how well-posed the problem is. ...

Now, suppose that the Cholesky decomposition is applicable. As mentioned above, the algorithm will be twice as fast. Furthermore, no pivoting is necessary and the error will always be small. Specifically, if we want to solve Ax = b, and y denotes the computed solution, then y solves the disturbed system (A + E)y = b where

Here, || ||₂ is the matrix 2-norm, c_n is a small constant depending on n, and ε denotes the unit roundoff. In mathematics, the term matrix norm can have two meanings: A vector norm on matrices, i. ...

There is one small problem with the Cholesky decomposition. Note that we must compute square roots in order to find the Cholesky decomposition. If the matrix is real symmetric and positive definite, then the numbers under the square roots are always positive in exact arithmetic. Unfortunately, the numbers can become negative because of round-off errors, in which case the algorithm cannot continue. However, this can only happen if the matrix is very ill-conditioned.

See also

• symbolic Cholesky decomposition
• minimum degree algorithm

In the mathematical subfield of numerical analysis the symbolic Cholesky decomposition is an algorithm used estimate the worst possible fill-in for a symmetric sparse matrix when applying the Cholesky decomposition. ... In numerical analysis the minimum degree algorithm is an algorithm used to permute the rows and columns of a symmetric sparse matrix before applying the Cholesky decomposition, to reduce the number of non-zeros in the Cholesky factor. ...

References

• Gene H. Golub and Charles F. Van Loan, Matrix computations (3rd ed.), Section 4.2, Johns Hopkins University Press. ISBN 0-8018-5414-8.
• Roger A. Horn and Charles R. Johnson. Matrix Analysis, Section 7.2. Cambridge University Press, 1985. ISBN 0-521-38632-2.
• S. J. Julier and J.K. Uhlmann, "A new extension of the Kalman filter to nonlinear systems," in Proc. AeroSense: 11th Int. Symp. Aerospace/Defence Sensing, Simulation and Controls, 1997, pp. 182-193.

External links

• Chapter 2.9 of "Numerical Recipes in C" gives information about implementation of Cholesky algorithm in C.
• Cholesky Decomposition on PlanetMath
• Online Matrix Calculator Performs Cholesky decomposition of matrices online.
• Cholesky Matrix, riskglossary.com