In this course, the authors introduce a method for Cholesky decomposition of matrix $A$, based on row reduction:
Procedure 7.4.1: Finding the Cholesky Factorization
- Using only type 3 elementary row operations (multiples of rows added to other rows) put A in upper triangular form. Call this matrix $\hat U$. Then $\hat U$ has positive entries on the main diagonal.
- Divide each row of $\hat U$ by the square root of the diagonal entry in that row. The result is the matrix $U$.
Example:
$$\begin{bmatrix} 9 & -6 & 3 \\ -6 & 5 & -3 \\ 3 & -3 & 6 \\ \end{bmatrix} \rightarrow \begin{bmatrix} 9 & -6 & 3 \\ 0 & 1 & -1 \\ 0 & -1 & 5 \\ \end{bmatrix} \rightarrow \begin{bmatrix} 9 & -6 & 3 \\ 0 & 1 & -1 \\ 0 & 0 & 4 \\ \end{bmatrix} $$
- I wasn't able to find this algorithm on other sites, which seems strange,
- I don't understand how this algorithm is used on the example provided.
For example, which row operations (of type 3) can change the second row from $[-6, 5, -3]$ to $[0, 1, -1]$? Adding 2xR3 to R2 gives $[0, -1, 9]$ and from there I cannot figure out how this can be improved.
Help appreciated, thanks.
There is a mistake in the algorithm: the allowed operations must be adding a multiple of a row to other rows below it. Only these elementary operations are implemented by lower triangular matrices with $1$ on the diagonal, and in this case we will indeed obtain the $U$ part of $LU$ decomposition, from which it is possible to get Cholesky decomposition.
In the example we add $\frac23$ of the first row to the second and subtract $\frac13$ of the first row from the third.