Cholesky factorization of a symmetric positive-definite matrix: 04-BS-5, May 2015, Q7

Question 7: Cholesky factorization of a symmetric positive-definite matrix (a) 10 marks; (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{pmatrix}16&-8&-4\\-8&29&12\\-4&12&41\end{pmatrix}$, symmetric positive-definite; right-hand side $b=(-20,80,20)^T$.

Find. (a) $L$ with $A=LL^T$; (b) solve $Ax=b$ using $L$ and $L^T$.

Approach. Cholesky's algorithm: build $L$ column by column from $l_{ii}=\sqrt{a_{ii}-\sum_{k\lt i}l_{ik}^2}$ and $l_{ji}=\big(a_{ji}-\sum_{k\lt i}l_{jk}l_{ik}\big)/l_{ii}$; then forward-substitute $Lw=b$ and back-substitute $L^Tx=w$.

First column. $l_{11}=\sqrt{16}=4$; $l_{21}=a_{21}/l_{11}=-8/4=-2$; $l_{31}=a_{31}/l_{11}=-4/4=-1$.
Second column. $l_{22}=\sqrt{a_{22}-l_{21}^2}=\sqrt{29-4}=5$; $l_{32}=(a_{32}-l_{31}l_{21})/l_{22}=(12-(-1)(-2))/5=10/5=2$.
Third column. $$\boxed{l_{33}=\sqrt{a_{33}-l_{31}^2-l_{32}^2}=\sqrt{41-1-4}=6}$$ $$L=\begin{pmatrix}4&0&0\\-2&5&0\\-1&2&6\end{pmatrix},\qquad L^T=\begin{pmatrix}4&-2&-1\\0&5&2\\0&0&6\end{pmatrix}$$ (check: $LL^T=A$ holds exactly.)
Forward substitution $Lw=b$. $4w_1=-20\Rightarrow w_1=-5$; $-2w_1+5w_2=80\Rightarrow5w_2=80-10=70\Rightarrow w_2=14$; $-w_1+2w_2+6w_3=20\Rightarrow6w_3=20-5-28=-13\Rightarrow w_3=-13/6$.
Back substitution $L^Tx=w$ (solve for $z,y,x$ in that order). $$6z=-\dfrac{13}{6}\Rightarrow z=-\dfrac{13}{36}=-0.36111$$ $$5y+2z=14\Rightarrow y=\dfrac{14-2(-13/36)}{5}=\dfrac{53}{18}=2.94444$$ $$4x-2y-z=-5\Rightarrow x=\dfrac{-5+2(53/18)+(-13/36)}{4}=\dfrac{19}{144}=0.13194$$ $$\boxed{(x,y,z)=(0.13194,\ 2.94444,\ -0.36111)}$$ (checked by substituting back into all three original equations.)

Final results — Question 7
Quantity	Value
$L$	$\begin{pmatrix}4&0&0\\-2&5&0\\-1&2&6\end{pmatrix}$
$x$	$19/144\approx0.13194$
$y$	$53/18\approx2.94444$
$z$	$-13/36\approx-0.36111$

Topic: Cholesky (LL$^T$) factorization for a symmetric positive-definite system.

Key relations: $l_{ii}=\sqrt{a_{ii}-\sum_{k\lt i}l_{ik}^2}$, $l_{ji}=(a_{ji}-\sum_{k\lt i}l_{jk}l_{ik})/l_{ii}$ for $j\gt i$; solve $Ax=b$ via $Lw=b$ (forward) then $L^Tx=w$ (back).

Why this works: a symmetric positive-definite matrix always has a real Cholesky factor (guaranteed by the positive leading principal minors / positive eigenvalues), and factoring once lets both the forward and back substitutions run in $O(n^2)$ time each — roughly half the arithmetic of a general LU factorization, exploiting the symmetry.

Common pitfall: forgetting to take the square root when computing diagonal entries $l_{ii}$ (confusing Cholesky with a plain LU/Doolittle factorization); mixing up rows and columns when back-substituting with $L^T$ rather than $L$.

Source: Kreyszig, Advanced Engineering Mathematics, 10th ed., §20.4 (Cholesky's Method).

Question 7 of 7: Cholesky factorization of a symmetric positive-definite matrix

Question 7: Cholesky factorization of a symmetric positive-definite matrix (a) 10 marks; (b) 10 marks