2
$\begingroup$

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

  1. 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.
  2. 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.

$\endgroup$
1
  • 1
    $\begingroup$ When creating upper triangle, you only use the row(s) above the one you’re working with. In this case add $2/3$ of the first row to the second $\endgroup$
    – acat3
    Jan 5 at 13:34

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the complementary explanations. $\endgroup$
    – mins
    Jan 5 at 13:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .