The GATE Grind

GATE 2022 CS – Question 45

Engineering Mathematics · Linear Algebra · 2 marks · Multiple choice

Consider solving the following system of simultaneous equations using LU decomposition.
$x_1+x_2-2x_3=4$
$x_1+3x_2-x_3=7$
$2x_1+x_2-5x_3=7$
where $L$ and $U$ are denoted as
$L=\begin{pmatrix}L_{11}&0&0\\L_{21}&L_{22}&0\\L_{31}&L_{32}&L_{33}\end{pmatrix}$, $U=\begin{pmatrix}U_{11}&U_{12}&U_{13}\\0&U_{22}&U_{23}\\0&0&U_{33}\end{pmatrix}$
Which one of the following is the correct combination of values for $L_{32}$, $U_{33}$, and $x_1$?

  1. $L_{32}=2,\ U_{33}=-\frac12,\ x_1=-1$
  2. $L_{32}=2,\ U_{33}=2,\ x_1=-1$
  3. $L_{32}=-\frac12,\ U_{33}=2,\ x_1=0$
  4. $L_{32}=-\frac12,\ U_{33}=-\frac12,\ x_1=0$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $L_{32}=-\frac12,\ U_{33}=-\frac12,\ x_1=0$

Explanation

Doolittle LU decomposition $A=LU$ ($L$ has unit diagonal):
$$A=\begin{pmatrix}1&1&-2\\1&3&-1\\2&1&-5\end{pmatrix}.$$

**Row 1 of $U$:** $U_{11}=1,\ U_{12}=1,\ U_{13}=-2$.
**Column 1 of $L$:** $L_{21}=1/1=1,\ L_{31}=2/1=2$.
**Row 2 of $U$:** $U_{22}=3-L_{21}U_{12}=3-1=2$; $U_{23}=-1-L_{21}U_{13}=-1+2=1$.
**$L_{32}$:** $L_{32}=\dfrac{1-L_{31}U_{12}}{U_{22}}=\dfrac{1-2}{2}=-\dfrac12$.
**$U_{33}$:** $U_{33}=-5-L_{31}U_{13}-L_{32}U_{23}=-5+4+\tfrac12=-\tfrac12$.

Solve $Ly=b$ with $b=(4,7,7)$: $y_1=4,\ y_2=7-4=3,\ y_3=7-2(4)+\tfrac12(3)=\tfrac12$.
Solve $Ux=y$: $x_3=\dfrac{1/2}{-1/2}=-1$, $x_2=\dfrac{3-x_3}{2}=2$, $x_1=4-x_2+2x_3=0$.

$L_{32}=-\tfrac12$, $U_{33}=-\tfrac12$, $x_1=0$: option (D).

More Linear Algebra questions

All Linear Algebra questions →