Cholesky-Type Factorization of a Symmetric Positive-Definite Matrix: 04-BS-5, December 2016, Q7

Question 7: Cholesky-Type Factorization of a Symmetric Positive-Definite Matrix (20 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 $3\times3$ SPD matrix $A$ above and the right-hand side $b=(17,14,56)^T$.

Find. The upper-triangular $U$ with $A=UU^T$, and the solution $(x,y,z)$.

Approach. Match entries of $UU^T$ to $A$ starting from the bottom-right corner (this is the Cholesky-Crout recursion applied to the "upper $U$" convention), then solve $Ax=b$ as two triangular sweeps: $Uw=b$ (back-substitution) followed by $U^Tx=w$ (forward-substitution), since $A=UU^T$ means $Ax=U(U^Tx)$.

Solve for $U$ from the bottom-right corner up. $$u_{33}^2=49\Rightarrow u_{33}=7;\qquad u_{13}u_{33}=28\Rightarrow u_{13}=4;\qquad u_{23}u_{33}=-14\Rightarrow u_{23}=-2$$ $$u_{22}^2+u_{23}^2=29\Rightarrow u_{22}^2=25\Rightarrow u_{22}=5;\qquad u_{12}u_{22}+u_{13}u_{23}=-13\Rightarrow -13=5u_{12}-8\Rightarrow u_{12}=-1$$ $$u_{11}^2+u_{12}^2+u_{13}^2=26\Rightarrow u_{11}^2=26-1-16=9\Rightarrow u_{11}=3$$ $$\boxed{U=\begin{pmatrix}3&-1&4\\0&5&-2\\0&0&7\end{pmatrix}},\qquad U^T=\begin{pmatrix}3&0&0\\-1&5&0\\4&-2&7\end{pmatrix}$$ (check: multiplying out $UU^T$ reproduces every one of the six distinct entries of $A$ exactly.)
Back-substitute the upper-triangular system $Uw=b$. $$7w_3=56\Rightarrow w_3=8;\qquad 5w_2-2w_3=14\Rightarrow5w_2=30\Rightarrow w_2=6;\qquad 3w_1-w_2+4w_3=17\Rightarrow3w_1=-9\Rightarrow w_1=-3$$ so $w=(-3,6,8)^T$.
Forward-substitute the lower-triangular system $U^T(x,y,z)^T=w$. $$3x=-3\Rightarrow x=-1;\qquad -x+5y=6\Rightarrow5y=5\Rightarrow y=1;\qquad 4x-2y+7z=8\Rightarrow7z=14\Rightarrow z=2$$ $$\boxed{x=-1,\quad y=1,\quad z=2}$$
Check against the original system. $26(-1)-13(1)+28(2)=17$; $-13(-1)+29(1)-14(2)=14$; $28(-1)-14(1)+49(2)=56$ — all three equations balance exactly.

Quantity	Result
$U$	$\begin{pmatrix}3&-1&4\\0&5&-2\\0&0&7\end{pmatrix}$
$x,y,z$	$-1,\ 1,\ 2$

Topic: Cholesky-type triangular factorization of an SPD matrix, and solving via two triangular sweeps.

Key relations: $A=UU^T$ ($U$ upper triangular); solve $Uw=b$ then $U^Tx=w$.

Why this works: every real symmetric positive-definite matrix has a unique such factorization; once computed, solving for any new right-hand side costs only two $O(n^2)$ triangular sweeps instead of a fresh $O(n^3)$ elimination — the payoff when the same $A$ recurs across multiple load cases.

Common pitfall: solving the two triangular systems in the wrong order. Because $A=UU^T$ (not $U^TU$), the upper-triangular sweep $Uw=b$ must come first; reversing the order produces a $w$ that satisfies neither triangular system correctly, and the final check against the original equations fails even though each individual substitution "worked" in isolation.

Source: Kreyszig, Advanced Engineering Mathematics, Ch. 20 (Cholesky Factorization / Numerical Linear Algebra).

Question 7 of 7: Cholesky-Type Factorization of a Symmetric Positive-Definite Matrix

Question 7: Cholesky-Type Factorization of a Symmetric Positive-Definite Matrix (20 marks)