NLA MT25, Cholesky factorisation
Flashcards
Suppose $A \in \mathbb R^{n \times n}$. @State necessary and sufficient conditions for it to have a Cholesky factorisation $A = R^\top R$ for $R \in \mathbb R^{n \times n}$?
$A$ has a Cholesky factorisation iff $A$ is positive semidefinite.
@Define the Cholesky factorisation of a positive semidefinite matrix $A$.
where $R \in \mathbb R^{n \times n}$ and upper triangular.
Suppose we are finding the pivoted LU decomposition for a positive definite matrix $A \succ 0$. What simplifications can be made as you find the $L _ i$ and $U _ i$ factors, and what is the resulting factorisation called?
- $L _ i = U _ i^\top =: R _ i$ by symmetry, although now the diagonal of $R$ is no longer $1$
- No pivots are required
- The resulting factorisation is the Cholesky factorisation $A = R^\top R$
@Prove that if we are doing the pivoted LU decomposition for a positive definite matrix $A \succ 0$ then no pivots are needed.
In the first step of calculating the LU decomposition, we write
\[A=\underbrace{\begin{bmatrix} *\\ *\\ *\\ * \end{bmatrix} \begin{bmatrix} * & * & * & * & * \end{bmatrix}} _ {R _ {1}R _ {1}^{T}} \;+\; \begin{bmatrix} \, \\ \phantom * & * & * & *\\ \phantom * & * & * & *\\ \phantom * & * & * & *\\ \phantom * & * & * & * \end{bmatrix}\]This follows from showing that the second term must also be positive semidefinite if $A$ is. A positive definite matrix has an eigenvalue decomposition
\[A = VD^2 V^\top = (VDV^\top)^2 = (VDV^\top)(V DV^\top)\]Now let
\[VDV^\top = QR\]be the QR factorisation. Then $(VDV^\top)^\top (V D V^\top) = R^\top R$, but now the $0$ structure in the initial decomposition implies that the first term must be $r r^\top$, where $r^\top$ is the first row of $R$. Hence the second term must be $R _ 2^\top R _ 2$, which is positive semidefinite. Here $R^\top = [r R _ 2^\top]$.
@Define the LDLT factorisation of a positive definite matrix $A$.
where $L$ is a lower triangular matrix with $1$s on the diagonal, and $D$ is a diagonal matrix.
Stability analysis
@Justify that the Cholesky factorisation can be computed in a backwards stable way.
@todo.