Numerical linear algebra · Definition

Cholesky factorization

numerical methodsnumerical linear algebra

Before you start you need to know

When a matrix is symmetric and positive definite, it can be factored with about half the work of LU factorization. This method exploits symmetry to solve linear systems stably.

Definition

The Cholesky factorization decomposes a symmetric positive definite matrix \(A\) as \(A = LL^{T}\), where \(L\) is lower triangular with positive diagonal.

\[A = LL^{T}, \; l_{jj} = \sqrt{a_{jj} - \sum_{k

If \(A\) is symmetric positive definite, its factorization \(A = LL^{T}\) exists and is unique with positive diagonal in \(L\). Entries are computed column by column: \(l_{jj}=\sqrt{a_{jj}-\sum_{k<j}l_{jk}^{2}}\) and \(l_{ij}=(a_{ij}-\sum_{k<j}l_{ik}l_{jk})/l_{jj}\) for \(i>j\).

For \(A=\begin{pmatrix}4&2\\2&5\end{pmatrix}\), we get \(l_{11}=2\), \(l_{21}=1\), and \(l_{22}=\sqrt{5-1}=2\), so \(L=\begin{pmatrix}2&0\\1&2\end{pmatrix}\). This confirms \(LL^{T}=A\).

A typical error is applying the formula to a symmetric matrix that is not positive definite, where a square root of a negative number appears. Another common mistake is forgetting that \(L^{T}\) is the transpose of \(L\), not its inverse.

Think about it

If a symmetric matrix has a negative eigenvalue, what happens when computing \(l_{jj}\)?

A negative or zero quantity appears under a square root at some step, so the factorization does not exist because the matrix is not positive definite.

Exercises 10

  1. What property must a matrix \(A\) have to apply the Cholesky factorization?
  2. What form does the factor \(L\) have in \(A = LL^{T}\)?
  3. If \(L\) is the Cholesky factor, what does the equality \(A = LL^{T}\) express?
  4. What is the element \(l_{11}\) of the Cholesky factor when \(a_{11}=9\)?
  5. What is the relation between Cholesky and LU for a symmetric positive definite matrix?
  6. Compute \(l_{11}\) and \(l_{21}\) for \(A=\begin{pmatrix}4&2\\2&5\end{pmatrix}\).
  7. If \(a_{22}=10\) and \(l_{21}=3\), what is \(l_{22}\)?
  8. For \(A=\begin{pmatrix}9&3\\3&5\end{pmatrix}\), what is the factor \(L\)?
  9. If \(L=\begin{pmatrix}2&0\\1&2\end{pmatrix}\), what is the product \(LL^{T}\)?
  10. Solve \(Ax=b\) with \(A=\begin{pmatrix}4&2\\2&5\end{pmatrix}\) and \(b=\begin{pmatrix}2\\1\end{pmatrix}\) using the Cholesky factor \(L\). What is \(x\)?

References

  • Richard L. Burden, J. Douglas Faires, Annette M. Burden, Numerical Analysis, 10th edition, Cengage Learning, 2016.
  • Lloyd N. Trefethen, David Bau III, Numerical Linear Algebra, 1st edition, SIAM, 1997.