Cholesky Factorization and Solving a Linear System: 04-BS-5, May 2014, Q7

Question 7: Cholesky Factorization and Solving a Linear System (10+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). The symmetric positive-definite matrix $A=\begin{bmatrix}16&-8&12\\-8&5&-6\\12&-6&13\end{bmatrix}$.

Find (a). The lower-triangular $L$ with $A=LL^T$.

Approach (a). Apply the Cholesky recursion column by column: $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$.

Column 1. $l_{11}=\sqrt{16}=4$; $l_{21}=a_{21}/l_{11}=-8/4=-2$; $l_{31}=a_{31}/l_{11}=12/4=3$.
Column 2. $l_{22}=\sqrt{a_{22}-l_{21}^2}=\sqrt{5-4}=1$; $l_{32}=\big(a_{32}-l_{31}l_{21}\big)/l_{22}=\big(-6-(3)(-2)\big)/1=0$.
Column 3. $l_{33}=\sqrt{a_{33}-l_{31}^2-l_{32}^2}=\sqrt{13-9-0}=2$. $$\boxed{L=\begin{bmatrix}4&0&0\\-2&1&0\\3&0&2\end{bmatrix}}$$ Check: $LL^T=\begin{bmatrix}16&-8&12\\-8&5&-6\\12&-6&13\end{bmatrix}=A$. ✓

Given (b). The system $Ax=b$ with $b=(-16,\,11,\,-8)^T$, and the factorization $A=LL^T$ from part (a).

Find (b). $x_1,x_2,x_3$.

Approach (b). Solve two triangular systems: forward-substitute $Ly=b$, then back-substitute $L^Tx=y$.

Forward substitution, $Ly=b$. $$4y_1=-16\Rightarrow y_1=-4;\qquad -2y_1+y_2=11\Rightarrow y_2=11-8=3;\qquad 3y_1+2y_3=-8\Rightarrow y_3=\frac{-8+12}{2}=2$$
Back substitution, $L^Tx=y$. $L^T=\begin{bmatrix}4&-2&3\\0&1&0\\0&0&2\end{bmatrix}$. $$2x_3=2\Rightarrow x_3=1;\qquad x_2=y_2=3;\qquad 4x_1-2(3)+3(1)=-4\Rightarrow x_1=\frac{-4+6-3}{4}=-\frac14$$ $$\boxed{x_1=-\tfrac14,\quad x_2=3,\quad x_3=1}$$
Check against the original equations. $16(-\tfrac14)-8(3)+12(1)=-4-24+12=-16$; $-8(-\tfrac14)+5(3)-6(1)=2+15-6=11$; $12(-\tfrac14)-6(3)+13(1)=-3-18+13=-8$ — all three match $b$.

Cholesky factor and system solution
Quantity	Value
L	[[4,0,0],[−2,1,0],[3,0,2]]
x₁	−1/4
x₂	3
x₃	1

Topic: Cholesky ($LL^T$) factorization of a symmetric positive-definite matrix, and its use for solving linear systems.

Key relations: Cholesky recursion for $l_{ii}$, $l_{ji}$; forward substitution $Ly=b$; back substitution $L^Tx=y$.

Why this works: every symmetric positive-definite matrix has a unique Cholesky factorization with positive diagonal entries (this is why every square root in the recursion is of a positive number); once $A=LL^T$ is known, solving $Ax=b$ costs two $O(n^2)$ triangular solves instead of a fresh $O(n^3)$ elimination — valuable when the same $A$ is solved against many right-hand sides.

Common pitfall: a sign slip in $l_{21}$ or $l_{31}$ silently propagates into every later entry (here it would corrupt $l_{22}$ and $l_{32}$); forgetting to transpose $L$ for the back-substitution stage, or back-substituting with $L$ itself instead of $L^T$.

Source: Kreyszig, Advanced Engineering Mathematics, Cholesky's method (Ch. 20); Strang, Introduction to Linear Algebra, Ch. 9 (Cholesky factorization of SPD matrices).

Question 7 of 7: Cholesky Factorization and Solving a Linear System

Question 7: Cholesky Factorization and Solving a Linear System (10+10 marks)