Crout LU Decomposition and Linear System Solution: 04-BS-5, December 2017, Q7

Question 7: Crout LU Decomposition and Linear System Solution (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. $A=\begin{bmatrix}3&-9&9\\-4&17&8\\1&-5&1\end{bmatrix}$, and the requirement that $U$ have a unit diagonal (Crout's method, as opposed to Doolittle where $L$ has the unit diagonal).

Find. (a) $L$ and $U$ with $A=LU$. (b) The solution $(x,y,z)$ of $A\mathbf{x}=\mathbf{b}$, $\mathbf{b}=(-24,7,-7)^T$, via forward/back substitution.

Approach. Equate $A=LU$ entry by entry, column by column (Crout's algorithm), solving for each unknown $l_{ij}$ or $u_{ij}$ in the order it first becomes computable; then solve $L\mathbf{z}=\mathbf{b}$ by forward substitution and $U\mathbf{x}=\mathbf{z}$ by back substitution.

Column 1 of $L$ (uses $u_{11}=1$). $l_{11}=a_{11}=3,\quad l_{21}=a_{21}=-4,\quad l_{31}=a_{31}=1$.
Row 1 of $U$. $u_{12}=a_{12}/l_{11}=-9/3=-3,\quad u_{13}=a_{13}/l_{11}=9/3=3$.
Column 2 of $L$. $l_{22}=a_{22}-l_{21}u_{12}=17-(-4)(-3)=17-12=5$; $\quad l_{32}=a_{32}-l_{31}u_{12}=-5-(1)(-3)=-2$.
Row 2 of $U$. $u_{23}=\dfrac{a_{23}-l_{21}u_{13}}{l_{22}}=\dfrac{8-(-4)(3)}{5}=\dfrac{20}{5}=4$.
Column 3 of $L$. $l_{33}=a_{33}-l_{31}u_{13}-l_{32}u_{23}=1-(1)(3)-(-2)(4)=1-3+8=6$.
Box the factors. $$\boxed{L=\begin{bmatrix}3&0&0\\-4&5&0\\1&-2&6\end{bmatrix},\qquad U=\begin{bmatrix}1&-3&3\\0&1&4\\0&0&1\end{bmatrix}}$$ (Confirmed by direct multiplication: $LU=A$ exactly, entry by entry.)
(b) Forward substitution, $L\mathbf{z}=\mathbf{b}$. $$3z_1=-24\Rightarrow z_1=-8$$ $$-4(-8)+5z_2=7\Rightarrow32+5z_2=7\Rightarrow z_2=-5$$ $$1(-8)-2(-5)+6z_3=-7\Rightarrow-8+10+6z_3=-7\Rightarrow6z_3=-9\Rightarrow z_3=-1.5$$
Back substitution, $U\mathbf{x}=\mathbf{z}$. $$x_3=z_3=-1.5$$ $$x_2+4x_3=z_2\Rightarrow x_2=-5-4(-1.5)=1$$ $$x_1-3x_2+3x_3=z_1\Rightarrow x_1=-8+3(1)-3(-1.5)=-8+3+4.5=-0.5$$ $$\boxed{x=-0.5,\quad y=1,\quad z=-1.5}$$ Checked against all three original equations: $3(-0.5)-9(1)+9(-1.5)=-24$; $-4(-0.5)+17(1)+8(-1.5)=7$; $(-0.5)-5(1)+(-1.5)=-7$. ✓

Quantity	Result
$L$	$\begin{bmatrix}3&0&0\\-4&5&0\\1&-2&6\end{bmatrix}$
$U$	$\begin{bmatrix}1&-3&3\\0&1&4\\0&0&1\end{bmatrix}$
Solution	$x=-0.5,\ y=1,\ z=-1.5$

Topic: Crout LU decomposition (unit-upper-triangular $U$) and forward/back substitution.

Key relations: $a_{ij}=\sum_k l_{ik}u_{kj}$ solved column-by-column; $A\mathbf{x}=\mathbf{b}\iff L\mathbf{z}=\mathbf{b}$ then $U\mathbf{x}=\mathbf{z}$.

Why this works: triangular systems solve in $O(n^2)$ by simple substitution instead of the $O(n^3)$ cost of Gaussian elimination repeated for every new right-hand side, which is precisely why LU factorization is the standard approach when the same $A$ must be solved against several different $\mathbf{b}$ vectors. Crout's convention (unit $U$) and Doolittle's convention (unit $L$) both exist and give the same product $A$, so it is essential to match the substitution order to whichever convention is specified.

Common pitfall: confusing Crout with Doolittle and normalising by the wrong diagonal entry when computing off-diagonal $l_{ij}$/$u_{ij}$ terms, or swapping the forward/back-substitution order (forward solves $L\mathbf{z}=\mathbf{b}$ top-down; back solves $U\mathbf{x}=\mathbf{z}$ bottom-up).

Source: Kreyszig, Advanced Engineering Mathematics, 10th ed., Ch. 20.2 (Gauss Elimination and LU-Factorization); Strang, Introduction to Linear Algebra, 6th ed., Ch. 2.

Question 7 of 7: Crout LU Decomposition and Linear System Solution

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