Cholesky ($LL^{T}$) Decomposition and Linear-System Solve: 04-BS-5, May 2016, Q7

Question 7: Cholesky ($LL^{T}$) Decomposition and Linear-System Solve (a: 10, b: 10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. $A=\begin{bmatrix}4&10&8\\10&29&26\\8&26&34\end{bmatrix}$ (symmetric positive definite) and right-hand side $b=(-4,-11,-5)^{T}$.

Find. (a) The lower-triangular Cholesky factor $L$ (and $L^{T}$). (b) The solution $x=(x_1,x_2,x_3)$.

Approach. Derive $L$ entry-by-entry column-by-column from $A=LL^{T}$; then solve $Ly=b$ by forward substitution and $L^{T}x=y$ by back substitution.

(a) Column 1. $l_{11}=\sqrt{a_{11}}=\sqrt{4}=2$; $l_{21}=a_{21}/l_{11}=10/2=5$; $l_{31}=a_{31}/l_{11}=8/2=4$.
(a) Column 2. $l_{22}=\sqrt{a_{22}-l_{21}^{2}}=\sqrt{29-25}=2$; $l_{32}=(a_{32}-l_{31}l_{21})/l_{22}=(26-20)/2=3$.
(a) Column 3. $l_{33}=\sqrt{a_{33}-l_{31}^{2}-l_{32}^{2}}=\sqrt{34-16-9}=3$. Hence $$\boxed{L=\begin{bmatrix}2&0&0\\5&2&0\\4&3&3\end{bmatrix}},\qquad L^{T}=\begin{bmatrix}2&5&4\\0&2&3\\0&0&3\end{bmatrix}$$ (directly verified: $LL^{T}=A$ exactly, entry by entry).
(b) Forward substitution, $Ly=b$. $$2y_1=-4\Rightarrow y_1=-2;\qquad 5y_1+2y_2=-11\Rightarrow y_2=-\tfrac12;\qquad 4y_1+3y_2+3y_3=-5\Rightarrow y_3=\tfrac32$$
(b) Back substitution, $L^{T}x=y$. $$3x_3=\tfrac32\Rightarrow x_3=\tfrac12;\qquad 2x_2+3x_3=-\tfrac12\Rightarrow x_2=-1;\qquad 2x_1+5x_2+4x_3=-2\Rightarrow x_1=\tfrac12$$ $$\boxed{(x_1,x_2,x_3)=(0.5,\ -1,\ 0.5)}$$ (directly verified: substituting back into all three original equations reproduces $-4,-11,-5$ exactly.)

Final results — Question 7
Quantity	Result
$L$	$\begin{bmatrix}2&0&0\\5&2&0\\4&3&3\end{bmatrix}$
$y$ ($Ly=b$)	$(-2,\ -0.5,\ 1.5)$
$x$ ($L^{T}x=y$)	$(0.5,\ -1,\ 0.5)$

The whole-number entries of $L$ are not a coincidence of rounding: $A$ was built so that every square root in the Cholesky recursion lands on a perfect square (4, 4, 9), which is why this system is a natural textbook example rather than one requiring decimal approximation. Because $A$ is diagonally dominant as well as SPD, the same factorization would also succeed (numerically stably) via plain Gaussian elimination without pivoting, but Cholesky remains the cheaper choice whenever symmetry is known in advance, exactly as it is here.

Topic: Cholesky ($LL^{T}$) factorization of a symmetric positive-definite matrix, and forward/back-substitution solving.

Key relations: $l_{ii}=\sqrt{a_{ii}-\sum_{k\lt i}l_{ik}^{2}}$, $l_{ji}=\big(a_{ji}-\sum_{k\lt i}l_{jk}l_{ik}\big)/l_{ii}$ for $j\gt i$; solve $Ly=b$ (forward), then $L^{T}x=y$ (back).

Why this works: symmetric positive-definiteness guarantees every quantity under a square root stays positive, so the factorization exists without pivoting and is numerically stable; it costs about half the arithmetic of general LU ($n^{3}/6$ vs $n^{3}/3$ flops), which is why Cholesky is the default direct solver whenever SPD structure is known (as it is here — $A$ is diagonally dominant and symmetric).

Common pitfall: forgetting that the SECOND solve uses $L^{T}$ (back substitution, top row last), not $L$ again; or swapping which triangular system is solved first.

Source: Kreyszig, Advanced Engineering Mathematics, 10th ed., Ch.20.1–20.2 (Gauss Elimination, LU/Cholesky Factorization).

Question 7 of 7: Cholesky ($LL^{T}$) Decomposition and Linear-System Solve

Question 7: Cholesky ($LL^{T}$) Decomposition and Linear-System Solve (a: 10, b: 10 marks)