Cholesky Decomposition and Linear System Solution: 04-BS-5, December 2018, Q7

Question 7: Cholesky Decomposition and Linear System Solution (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. Symmetric matrix $A=\begin{pmatrix}9&-6&12\\-6&5&-3\\12&-3&45\end{pmatrix}$ (the problem's own label "$L$ upper triangular" is the printed exam's naming; the matrix constructed is the standard lower-triangular Cholesky factor satisfying $A=LL^T$); right-hand side $\mathbf b=(8,-8,-4)^T$.

Find. (a) The Cholesky factor $L$ (and $L^T$). (b) The solution $(x,y,z)$ via forward substitution ($L\mathbf w=\mathbf b$) then back substitution ($L^T\mathbf x=\mathbf w$).

Approach. $A$ is symmetric; confirm it is positive definite by the Cholesky process succeeding (all diagonal entries under the square root staying positive), building $L$ column by column with $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}$ for $j\gt i$.

Column 1. $l_{11}=\sqrt{a_{11}}=\sqrt9=3$. $l_{21}=a_{21}/l_{11}=-6/3=-2$. $l_{31}=a_{31}/l_{11}=12/3=4$.
Column 2. $l_{22}=\sqrt{a_{22}-l_{21}^2}=\sqrt{5-4}=1$. $l_{32}=(a_{32}-l_{31}l_{21})/l_{22}=(-3-(4)(-2))/1=5$.
Column 3. $l_{33}=\sqrt{a_{33}-l_{31}^2-l_{32}^2}=\sqrt{45-16-25}=\sqrt4=2$. $$\boxed{L=\begin{pmatrix}3&0&0\\-2&1&0\\4&5&2\end{pmatrix},\qquad L^T=\begin{pmatrix}3&-2&4\\0&1&5\\0&0&2\end{pmatrix}}$$ Check: $LL^T$ reproduces $A$ exactly.
(b) Forward substitution, $L\mathbf w=\mathbf b$. $$3w_1=8\Rightarrow w_1=\tfrac83;\quad -2w_1+w_2=-8\Rightarrow w_2=-8+2(\tfrac83)=-\tfrac83;\quad 4w_1+5w_2+2w_3=-4\Rightarrow w_3=\tfrac{-4-4(\frac83)-5(-\frac83)}{2}=-\tfrac23$$
Back substitution, $L^T\mathbf x=\mathbf w$. $$2z=-\tfrac23\Rightarrow z=-\tfrac13;\quad y+5z=-\tfrac83\Rightarrow y=-\tfrac83-5(-\tfrac13)=-1;\quad 3x-2y+4z=\tfrac83\Rightarrow x=\dfrac{\frac83+2(-1)-4(-\frac13)}{3}=\tfrac23$$ $$\boxed{x=\tfrac23,\quad y=-1,\quad z=-\tfrac13}$$ Check: substituting back into all three original equations reproduces $(8,-8,-4)$ exactly.

Quantity	Result
$L$	$\begin{pmatrix}3&0&0\\-2&1&0\\4&5&2\end{pmatrix}$
$L^T$	$\begin{pmatrix}3&-2&4\\0&1&5\\0&0&2\end{pmatrix}$
$(x,y,z)$	$(2/3,\ -1,\ -1/3)$

Topic: Cholesky ($LL^T$) factorization of a symmetric positive-definite matrix; forward/back substitution.

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 $A\mathbf x=\mathbf b$ as $L\mathbf w=\mathbf b$ then $L^T\mathbf x=\mathbf w$.

Why this works: because $A$ is symmetric, Cholesky needs only about half the arithmetic of a general LU factorization and, unlike Doolittle/Crout, produces a single triangular factor whose transpose is the other one for free; the process succeeding without a negative number appearing under any square root is itself the practical certificate that $A$ is positive definite. Splitting the solve into two triangular systems avoids ever forming $A^{-1}$ and is numerically the standard way to solve multiple right-hand sides against the same $A$ cheaply.

Common pitfall: forgetting that $L$ (not the exam's mislabelled "upper triangular") is lower triangular by the standard Cholesky convention; mixing up which triangular system uses $L$ vs. $L^T$ during forward/back substitution; sign slips carrying $l_{21}=-2$ through the column-2 and column-3 computations.

Source: Kreyszig, Advanced Engineering Mathematics, 10th ed., Ch. 20.2 (Numeric Linear Algebra: LU/Cholesky Factorization).

Question 7 of 7: Cholesky Decomposition and Linear System Solution

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