Cholesky decomposition

The Cholesky decomposition (also Cholesky factorization ). (After André- Louis Cholesky, 1875-1918 ) referred to in the numerical analysis a decomposition of a symmetric positive definite matrix into a product of a lower triangular matrix and its transpose It was developed by Cholesky before 1914 as part of the triangulation of Crete by the Service de l' armée Geographical location. The concept can also be defined more generally for Hermitian matrices.

Areas of application

In applying the least squares method is a way of solving the minimization problem appearing on the normal equations, which have a symmetric positive definite matrix system. This is possible by using the Cholesky decomposition and this was the motivation of Cholesky to develop the decomposition. In the Gauss -Newton method so that, at each iteration a system of equations to solve, which can be determined using the Cholesky method.

The Cholesky decomposition can also be used to obtain a Vorkonditionierungsverfahrens for systems of linear equations with positive definite matrix; for this purpose there are special variant of the incomplete Cholesky decomposition as well as the modified incomplete Cholesky decomposition.

At the same time the cutting is a test of whether a given symmetric matrix is positive definite. Otherwise, one of the entries on the diagonal is negative, so that the root can not be pulled or neutral, so that can not be divided by the entry. In both cases, the algorithm terminates. Cholesky decomposition can also be used for determining the determinant of the matrix, as it is.

Outside mathematics is the Cholesky decomposition also used in the econometric study macroeconomic relationships. Here is the order of the influence of the endogenous variables to each set in so-called vector autoregressive models (VAR ).

In addition, it is also used in the Monte Carlo simulation, to bring predetermined correlations in independently generated random number sequences (as discretization of stochastic processes ).

Formulation and application

Every symmetric positive definite matrix can be uniquely in the form

Be written. It is a lower triangle matrix whose diagonal elements are all equal to 1 and is a diagonal matrix with positive entries. The square root of the matrix and the factor is defined by

And

Is the Cholesky decomposition - equivalent - formulated as

If there is a calculation of the Cholesky decomposition, so the system of equations can be efficiently solved by forward and backward substitution:

• By forward substitution solution of the linear system

• By then backward substitution solution of the linear system

Calculation

Substituting we obtain for the elements of A:

This relationship leads to the following formulas.

Effort and stability

The Cholesky decomposition is numerically stable. In comparison, the elimination procedure requires Gaussian with its algorithmic implementation, the LU decomposition is about twice as many operations as not only a matrix, but two factors have to be calculated. In the Cholesky decomposition occur about multiplication, division and root operations.

Pseudocode

The calculations in the above formulas can be carried out in various ways. Named after Tadeusz Banachiewicz variant calculates the lower triangular matrix row by row. In pseudo code, the method of decomposition of the matrix A can in the shape of GGT as follows:

For i = 1 To n          For j = 1 To i              Sum = a (i, j)              For k = 1 To j-1                  Sum = sum - A ( i, k) * A ( j, k)              If i > j Then                  a (i, j) = sum / A ( j, j ) / / lower triangular matrix              Else if sum > 0 Then / / diagonal element                  a (i, i) = sqrt (sum ) / / ... is always greater than zero              else                  ERROR / / The matrix is ​​( at least numerically ) is not symmetric positive definite The indexes of the matrix A corresponding to the mathematical notation i = 1 ... n, j = 1 ... n, n is the number of rows and the same number of columns of the matrix A, the auxiliary variables i, j, k and Sum. The algorithm works in-place, that is to say he modifies matrix A so that it contains the lower triangular matrix G.

The algorithm only processes the lower left triangular matrix of A, the values ​​ai, j for i < j do not need to be assigned values ​​(since the matrix A is symmetric by assumption ), and if they contain values, they are not changed. If one looks so according to the Cholesky decomposition A = G according to GGT, then set the matrix elements of A above the diagonal (i < j ) is equal to zero.