LU Decomposition and Solving a Linear System: 04-BS-5, December 2013, Q7

Question 7: LU Decomposition and Solving a Linear System (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). $A=\begin{bmatrix}2&4&-3\\-4&-10&11\\6&2&10\end{bmatrix}$, with $L=\begin{bmatrix}1&0&0\\l_{21}&1&0\\l_{31}&l_{32}&1\end{bmatrix}$, $U=\begin{bmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\end{bmatrix}$.

Find (a). The entries of $L$ and $U$ such that $A=LU$.

Approach (a). Doolittle elimination: eliminate column 1 using multipliers $l_{21},l_{31}$, record them, then eliminate column 2 of the reduced $2\times2$ block using $l_{32}$; no row interchange is needed since every pivot is nonzero.

Eliminate column 1. $l_{21}=\dfrac{-4}{2}=-2$, $l_{31}=\dfrac{6}{2}=3$. Row2 $\leftarrow$ Row2 $-l_{21}\cdot$Row1 $=[-4,-10,11]-(-2)[2,4,-3]=[0,-2,5]$. Row3 $\leftarrow$ Row3 $-l_{31}\cdot$Row1 $=[6,2,10]-3[2,4,-3]=[0,-10,19]$.
Eliminate column 2. $l_{32}=\dfrac{-10}{-2}=5$. Row3 $\leftarrow[0,-10,19]-5[0,-2,5]=[0,0,-6]$.
Read off $L$ and $U$. $$L=\boxed{\begin{bmatrix}1&0&0\\-2&1&0\\3&5&1\end{bmatrix}},\qquad U=\boxed{\begin{bmatrix}2&4&-3\\0&-2&5\\0&0&-6\end{bmatrix}}$$ Direct multiplication confirms $LU=A$ exactly.

Check: the printed system in part (b) reads “$-6x_1+2x_2+10x_3=34$” for the third equation (confirmed on the source page), but part (b) explicitly instructs solving via the $L,U$ of part (a), whose third row is $[6,2,10]$ — a $+6x_1$ coefficient, not $-6x_1$. Forward/back substitution with $L,U$ is only valid for the system $Ax=b$, so the $-6x_1$ is treated here as a sign typo in the source. The solution below uses $A$'s printed row-3 coefficients, $6x_1+2x_2+10x_3=34$.

Given (b). $Ax=b$ with $b=\begin{bmatrix}-16\\52\\34\end{bmatrix}$ (row 3 read as $6x_1+2x_2+10x_3=34$, matching $A$; see check note above).

Find (b). $x_1,x_2,x_3$.

Approach (b). Forward-substitute $Ly=b$, then back-substitute $Ux=y$.

Forward substitution, $Ly=b$. $y_1=-16$. $y_2=52-(-2)(-16)=52-32=20$. $y_3=34-3(-16)-5(20)=34+48-100=-18$. $$y=\begin{bmatrix}-16\\20\\-18\end{bmatrix}$$
Back substitution, $Ux=y$. $-6x_3=-18\Rightarrow x_3=3$. $-2x_2+5(3)=20\Rightarrow x_2=-\dfrac52$. $2x_1+4\left(-\dfrac52\right)-3(3)=-16\Rightarrow2x_1=-16+10+9=3\Rightarrow x_1=\dfrac32$. $$\boxed{x_1=\dfrac32,\quad x_2=-\dfrac52,\quad x_3=3}$$ Substituting back into all three original equations confirms the solution exactly.

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

Concept & Theory

Topic. LU (Doolittle) factorization and its use for solving linear systems by forward/back substitution.

Key relations. $A=LU$ with $L$ unit-lower-triangular multipliers and $U$ the row-echelon result of Gaussian elimination; once factored, $Ax=b\iff Ly=b$ (forward substitution) then $Ux=y$ (back substitution), both $O(n^2)$ instead of the $O(n^3)$ full elimination — a major saving when solving for multiple right-hand sides against the same $A$.

Why this works. Gaussian elimination without row interchange is exactly the process of building $L$ (the recorded multipliers) and $U$ (the reduced matrix); as long as every pivot encountered is nonzero, no permutation is required and $A=LU$ holds exactly.

Common pitfall. Using the LU factors to solve a system whose coefficient matrix does not actually match $A$ (e.g. a transcription sign error in one entry) silently returns the wrong answer without any error message — always confirm the system's coefficient matrix against the one that was factored before substituting.

Source. Burden & Faires, Numerical Analysis, Ch. 6 (Direct Methods for Solving Linear Systems; LU Factorization).

Question 7 of 7: LU Decomposition and Solving a Linear System

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