Cholesky Decomposition and Solution of a Linear System: 04-BS-5, May 2018, Q7

Question 7: Cholesky Decomposition and Solution of a Linear System (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. The symmetric positive-definite matrix $A=\begin{bmatrix}25&5&15\\5&5&9\\15&9&43\end{bmatrix}$ and the right-hand side $b=(-10,-1,8)^T$.

Find. (a) The Cholesky factor $L$ with $A=LL^T$. (b) The solution $x=(x_1,x_2,x_3)$ of $Ax=b$.

Approach. Equate entries of $LL^T$ to $A$ column-by-column to solve for $L$'s six unknowns in sequence, then solve $Ax=b$ in two cheap triangular sweeps: forward substitution $Lz=b$, then back substitution $L^Tx=z$. This is exactly the same linear system as a Gaussian-elimination solve, but recasting it through the symmetric factor $L$ roughly halves the arithmetic and, unlike raw elimination, never needs a pivoting strategy because positive-definiteness already guarantees every square root argument stays positive.

(a) First column: solve for $l_{11},l_{21},l_{31}$. Matching $(LL^T)_{11}=l_{11}^2=25$, $(LL^T)_{21}=l_{11}l_{21}=5$, $(LL^T)_{31}=l_{11}l_{31}=15$: $$l_{11}=\sqrt{25}=5,\qquad l_{21}=\dfrac{5}{5}=1,\qquad l_{31}=\dfrac{15}{5}=3$$
Second column: solve for $l_{22},l_{32}$. $(LL^T)_{22}=l_{21}^2+l_{22}^2=5\ \Rightarrow\ l_{22}=\sqrt{5-1^2}=2$. $(LL^T)_{32}=l_{31}l_{21}+l_{32}l_{22}=9\ \Rightarrow\ l_{32}=\dfrac{9-3(1)}{2}=3$.
Third column: solve for $l_{33}$. $(LL^T)_{33}=l_{31}^2+l_{32}^2+l_{33}^2=43\ \Rightarrow\ l_{33}=\sqrt{43-3^2-3^2}=\sqrt{25}=5$. $$\boxed{L=\begin{bmatrix}5&0&0\\1&2&0\\3&3&5\end{bmatrix}}\qquad(\text{check: }LL^T=A\ \checkmark)$$
(b) Forward substitution $Lz=b$. $5z_1=-10\Rightarrow z_1=-2$. $z_1+2z_2=-1\Rightarrow z_2=\dfrac{-1-(-2)}{2}=0.5$. $3z_1+3z_2+5z_3=8\Rightarrow z_3=\dfrac{8-3(-2)-3(0.5)}{5}=\dfrac{8+6-1.5}{5}=2.5$. $$z=(-2,\ 0.5,\ 2.5)^T$$
Back substitution $L^Tx=z$. With $L^T=\begin{bmatrix}5&1&3\\0&2&3\\0&0&5\end{bmatrix}$: $5x_3=2.5\Rightarrow x_3=0.5$. $2x_2+3(0.5)=0.5\Rightarrow x_2=\dfrac{0.5-1.5}{2}=-0.5$. $5x_1+(-0.5)+3(0.5)=-2\Rightarrow x_1=\dfrac{-2+0.5-1.5}{5}=-0.6$. $$\boxed{x_1=-0.6,\quad x_2=-0.5,\quad x_3=0.5}$$ Check: $25(-0.6)+5(-0.5)+15(0.5)=-15-2.5+7.5=-10\ \checkmark$; the other two equations check similarly.

Quantity	Result
Cholesky factor $L$	$\begin{bmatrix}5&0&0\\1&2&0\\3&3&5\end{bmatrix}$
Intermediate $z$ ($Lz=b$)	$(-2,\ 0.5,\ 2.5)$
Solution $x$	$x_1=-0.6,\ x_2=-0.5,\ x_3=0.5$

Topic: Cholesky factorization of a symmetric positive-definite matrix, and its use for solving linear systems via two triangular sweeps.

Key relations: Cholesky recursion $l_{jj}=\sqrt{a_{jj}-\sum_{k\lt j}l_{jk}^2}$, $l_{ij}=\big(a_{ij}-\sum_{k\lt j}l_{ik}l_{jk}\big)/l_{jj}$ for $i\gt j$; forward substitution $Lz=b$; back substitution $L^Tx=z$.

Why this works: a symmetric positive-definite matrix always has a real Cholesky factorization (the square roots taken are always of positive numbers), and factoring once then solving twice by substitution is roughly half the arithmetic of a general Gaussian elimination — the standard reason Cholesky is preferred whenever $A$ is known to be SPD (e.g. normal-equation systems, covariance matrices, stiffness matrices).

Common pitfall: solving the columns of $L$ out of order (e.g. attempting $l_{22}$ before $l_{21}$ is known); or forgetting that back substitution uses $L^T$, not $L$, so the sweep must run from $x_3$ down to $x_1$.

Source: Kreyszig, Advanced Engineering Mathematics, 10th ed., Ch. 20.2 (Cholesky's Method); Strang, Introduction to Linear Algebra, 6th ed., Ch. 2 (Symmetric Positive-Definite Matrices and Factorization).

Question 7 of 7: Cholesky Decomposition and Solution of a Linear System

Question 7: Cholesky Decomposition and Solution of a Linear System (a: 10; b: 10 marks)