LU (Crout) Decomposition and Solution of a Linear System: 04-BS-5, December 2014, Q7

Question 7: LU (Crout) Decomposition and Solution of a Linear System (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. $A=\begin{pmatrix}2&-4&6\\4&-11&0\\-1&4&10\end{pmatrix}$, with $U$ constrained to unit upper-triangular (Crout factorization), and right-hand side $b=(7,23,-12)^T$.

Find. (a) $L$ and $U$ such that $A=LU$. (b) $x,y,z$ solving $Ax=b$.

Approach. Multiply out $LU$ symbolically and match each entry of $A$ row-by-row/column-by-column (Crout’s algorithm) to solve for the six unknown entries of $L$ and the three of $U$ in sequence. Then solve $Ly=b$ by forward substitution and $Ux=y$ by back substitution.

Column 1 of $L$ (since $U$'s first column is $(1,0,0)^T$). Matching $A$'s first column directly gives $l_{11}=2,\ l_{21}=4,\ l_{31}=-1$.
Row 1 of $U$. $a_{12}=l_{11}u_{12}\Rightarrow u_{12}=-4/2=-2$. $a_{13}=l_{11}u_{13}\Rightarrow u_{13}=6/2=3$.
Row/column 2. $a_{22}=l_{21}u_{12}+l_{22}\Rightarrow l_{22}=-11-4(-2)=-3$. $a_{32}=l_{31}u_{12}+l_{32}\Rightarrow l_{32}=4-(-1)(-2)=2$. $a_{23}=l_{21}u_{13}+l_{22}u_{23}\Rightarrow u_{23}=\dfrac{0-4(3)}{-3}=4$.
Row/column 3. $a_{33}=l_{31}u_{13}+l_{32}u_{23}+l_{33}\Rightarrow l_{33}=10-(-1)(3)-2(4)=5$. $$\boxed{L=\begin{pmatrix}2&0&0\\4&-3&0\\-1&2&5\end{pmatrix},\qquad U=\begin{pmatrix}1&-2&3\\0&1&4\\0&0&1\end{pmatrix}}$$.
(b) Forward substitution, $Ly=b$. $$2y_1=7\Rightarrow y_1=3.5;\quad 4y_1-3y_2=23\Rightarrow y_2=\dfrac{23-14}{-3}=-3;\quad -y_1+2y_2+5y_3=-12\Rightarrow y_3=\dfrac{-12+3.5+6}{5}=-0.5$$
Back substitution, $Ux=y$. Since $U$ has unit diagonal: $z=y_3=-0.5$; $y=y_2-4z=-3-4(-0.5)=-1$; $x=y_1-(-2)y-3z=3.5+2(-1)-3(-0.5)=3.5-2+1.5=3$. $$\boxed{x=3,\quad y=-1,\quad z=-0.5}$$ Check: $2(3)-4(-1)+6(-0.5)=6+4-3=7$; $4(3)-11(-1)=12+11=23$; $-(3)+4(-1)+10(-0.5)=-3-4-5=-12$ — all three equations verified.

Q7 results
Item	Result
L	[[2,0,0],[4,−3,0],[−1,2,5]]
U	[[1,−2,3],[0,1,4],[0,0,1]]
x	3
y	−1
z	−0.5

Topic: LU (Crout) factorization and forward/back substitution.

Key relations: Crout's method fixes $U$'s diagonal to 1 (as opposed to Doolittle, which fixes $L$'s diagonal to 1); once $A=LU$ is known, any right-hand side $b$ is solved in two cheap triangular passes, $Ly=b$ then $Ux=y$, at $O(n^2)$ cost instead of re-eliminating the full system.

Why this works: matching $LU=A$ entry-by-entry in the order first-column-of-$L$, first-row-of-$U$, second-column, second-row, … always yields a solvable sequential system (each new unknown appears alone once its predecessors are known), provided no leading principal minor of $A$ is singular.

Common pitfall: confusing Doolittle ($L$ unit-diagonal) and Crout ($U$ unit-diagonal) conventions mid-calculation — the two give different individual $L,U$ factors (though the same $A$), so mixing formulas from the two conventions produces an inconsistent factorization.

Source: Kreyszig, Advanced Engineering Mathematics, Gauss Elimination, LU-Factorization (Ch. 7).

Question 7 of 7: LU (Crout) Decomposition and Solution of a Linear System

Question 7: LU (Crout) Decomposition and Solution of a Linear System (20 marks)