LU (Doolittle) Decomposition and Solving a Linear System: 04-BS-5, December 2019, Q7

Question 7: LU (Doolittle) Decomposition and Solving a Linear System (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. $A=\begin{pmatrix}6&-1&5\\-18&7&-13\\12&18&21\end{pmatrix}$, unit-lower-triangular $L$, upper-triangular $U$; right-hand side $\mathbf{b}=(8,-30,-13)^T$.

Find. (a) $L$ and $U$ such that $A=LU$. (b) $\mathbf{x}=(x_1,x_2,x_3)^T$ via forward then back substitution — no other solution method (e.g. Cramer's rule, direct Gaussian elimination on the augmented system) is accepted.

Approach. Doolittle's method: eliminate column by column, recording each multiplier as an entry of $L$, and reading the reduced rows off as $U$. Then solve $L\mathbf{y}=\mathbf{b}$ by forward substitution, and $U\mathbf{x}=\mathbf{y}$ by back substitution.

Row 1 of $U$; first multipliers. $u_{11}=6,\ u_{12}=-1,\ u_{13}=5$. Eliminate column 1: $$l_{21}=\frac{-18}{6}=-3,\qquad l_{31}=\frac{12}{6}=2$$
Row 2 of $U$. $u_{22}=7-l_{21}u_{12}=7-(-3)(-1)=4$; $\ u_{23}=-13-l_{21}u_{13}=-13-(-3)(5)=2$. Eliminate column 2: $$l_{32}=\frac{18-l_{31}u_{12}}{u_{22}}=\frac{18-(2)(-1)}{4}=\frac{20}{4}=5$$
Row 3 of $U$. $u_{33}=21-l_{31}u_{13}-l_{32}u_{23}=21-(2)(5)-(5)(2)=1$. $$\boxed{L=\begin{pmatrix}1&0&0\\-3&1&0\\2&5&1\end{pmatrix},\qquad U=\begin{pmatrix}6&-1&5\\0&4&2\\0&0&1\end{pmatrix}}$$ Check: $LU=A$ exactly (verified by direct multiplication).
(b) Forward substitution, $L\mathbf{y}=\mathbf{b}$. $$y_1=8;\qquad -3y_1+y_2=-30\Rightarrow y_2=-30+3(8)=-6;\qquad 2y_1+5y_2+y_3=-13\Rightarrow y_3=-13-2(8)-5(-6)=1$$ $$\mathbf{y}=(8,-6,1)^T$$
Back substitution, $U\mathbf{x}=\mathbf{y}$. $$x_3=\frac{1}{1}=1;\qquad 4x_2+2(1)=-6\Rightarrow x_2=-2;\qquad 6x_1-(-2)+5(1)=8\Rightarrow x_1=\frac16$$ $$\boxed{x_1=\tfrac16,\qquad x_2=-2,\qquad x_3=1}$$ Check: substituting back into all three original equations reproduces $8,-30,-13$ exactly.

Quantity	Result
$L$	$\begin{pmatrix}1&0&0\\-3&1&0\\2&5&1\end{pmatrix}$
$U$	$\begin{pmatrix}6&-1&5\\0&4&2\\0&0&1\end{pmatrix}$
$\mathbf{y}$ (from $L\mathbf{y}=\mathbf{b}$)	$(8,-6,1)^T$
$\mathbf{x}$ (from $U\mathbf{x}=\mathbf{y}$)	$x_1=1/6,\ x_2=-2,\ x_3=1$

Topic: Doolittle LU decomposition and its use for solving $A\mathbf{x}=\mathbf{b}$ by forward/back substitution.

Key relations: $u_{ij}=a_{ij}-\sum_{k\lt i}l_{ik}u_{kj}$ ($i\le j$); $l_{ij}=\big(a_{ij}-\sum_{k\lt j}l_{ik}u_{kj}\big)/u_{jj}$ ($i\gt j$); solve $L\mathbf{y}=\mathbf{b}$ then $U\mathbf{x}=\mathbf{y}$.

Why this works: $L$ records exactly the row-multipliers used in Gaussian elimination, so once $A=LU$ is computed, ANY right-hand side can be solved with two cheap triangular substitutions ($O(n^2)$ each) instead of repeating the full $O(n^3)$ elimination — the practical reason LU is preferred over Cramer's rule or re-deriving row-echelon form for every new $\mathbf{b}$.

Common pitfall: mixing up which triangular factor absorbs the multipliers ($L$ is unit lower-triangular, multipliers below the diagonal; $U$ carries the actual pivot values); forgetting that $l_{32}$'s formula subtracts $l_{31}u_{12}$ (not $l_{31}u_{32}$, which doesn't exist yet).

Source: Kreyszig, Advanced Engineering Mathematics, 10th ed., Ch. 20.2 (LU-Factorization); Chapra & Canale, Numerical Methods for Engineers, 7th ed., Ch. 10.

Question 7 of 7: LU (Doolittle) Decomposition and Solving a Linear System

Question 7: LU (Doolittle) Decomposition and Solving a Linear System (a: 10 marks; b: 10 marks)