Doolittle LU Decomposition and Linear System Solve: 04-BS-5, December 2015, Q7

Question 7: Doolittle LU Decomposition and Linear System Solve (a: marks n/s, b: marks n/s)

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}6 & -1 & 5\\ -18 & 7 & -13\\ 12 & 18 & 21\end{bmatrix}$, right-hand side $b=(8,-30,-13)^{T}$.

Find. (a) $L$ (unit lower triangular) and $U$ such that $A=LU$; (b) the solution $(x_1,x_2,x_3)$ of $Ax=b$.

Approach. Doolittle elimination: eliminate below each pivot, recording the multipliers as $L$'s entries and the reduced rows as $U$; then solve $Ax=b$ in two triangular sweeps, $Lw=b$ (forward) then $Ux=w$ (back-substitution).

(a) Eliminate column 1. Pivot $u_{11}=6$, so $l_{21}=-18/6=-3$ and $l_{31}=12/6=2$. Subtract $l_{21}\times$row 1 from row 2, and $l_{31}\times$row 1 from row 3: $$\text{row2}\to(-18,7,-13)-(-3)(6,-1,5)=(0,4,2), \qquad \text{row3}\to(12,18,21)-2(6,-1,5)=(0,20,11).$$
(a) Eliminate column 2. Pivot $u_{22}=4$, so $l_{32}=20/4=5$. Subtract $l_{32}\times$row 2 (of the reduced matrix) from row 3: $(0,20,11)-5(0,4,2)=(0,0,1)=u_{33}$. $$\boxed{L=\begin{bmatrix}1&0&0\\-3&1&0\\2&5&1\end{bmatrix}, \qquad U=\begin{bmatrix}6&-1&5\\0&4&2\\0&0&1\end{bmatrix}}$$ Check: $L U$ reconstructs $A$ exactly.
(b) Forward solve $Lw=b$. $w_1=8$; $-3w_1+w_2=-30\Rightarrow w_2=-30+24=-6$; $2w_1+5w_2+w_3=-13\Rightarrow w_3=-13-16-5(-6)=-13-16+30=1$. So $w=(8,-6,1)^T$.
(b) Back solve $Ux=w$. $x_3=w_3/1=1$. $4x_2+2x_3=-6\Rightarrow x_2=(-6-2)/4=-2$. $6x_1-x_2+5x_3=8\Rightarrow 6x_1 = 8+x_2-5x_3 = 8-2-5=1\Rightarrow x_1=1/6$. $$\boxed{x_1=\tfrac16,\quad x_2=-2,\quad x_3=1}$$ Substituting back into all three original equations confirms $Ax=b$ exactly.

Final results — Question 7
Quantity	Result
$L$	$\begin{bmatrix}1&0&0\\-3&1&0\\2&5&1\end{bmatrix}$
$U$	$\begin{bmatrix}6&-1&5\\0&4&2\\0&0&1\end{bmatrix}$
$x_1$	$1/6$
$x_2$	$-2$
$x_3$	$1$

Topic: Doolittle LU decomposition and the two-sweep triangular solve.

Key relations: $A=LU$ with $L$ unit lower triangular ($l_{ii}=1$), $U$ upper triangular; multipliers $l_{ij}=(\text{row }i\text{ entry below pivot})/(\text{pivot})$; solving $Ax=b$ becomes $Lw=b$ (forward substitution) then $Ux=w$ (back substitution), each an $O(n^2)$ triangular sweep instead of a fresh $O(n^3)$ elimination for every new right-hand side.

Why this works: Gaussian elimination without row interchanges is algebraically identical to factoring $A$ into the product of the elimination multipliers ($L$) and the resulting row-echelon matrix ($U$); once factored, $A$ never needs to be touched again — any number of systems $Ax=b_i$ reuse the same $L,U$, which is the entire point of doing the factorization once and solving many times.

Common pitfall: Writing the multiplier with the wrong sign (subtracting $l_{ij}\times$row $j$ means $l_{ij}$ itself is positive even when the entry being eliminated is negative, e.g. $l_{21}=-3$ here because $-18/6=-3$, not $+3$), and swapping the forward/back-substitution order.

Source: Kreyszig, Advanced Engineering Mathematics, 10th ed., Ch.7.3–7.4 (Gauss Elimination, LU-Factorization).

Question 7 of 7: Doolittle LU Decomposition and Linear System Solve

Question 7: Doolittle LU Decomposition and Linear System Solve (a: marks n/s, b: marks n/s)