# Question from Jesse about Gaussian Elimination and LU factorisation.

#### Prove It

##### Well-known member
MHB Math Helper

This system can be written as a matrix equation \displaystyle \begin{align*} A\,\mathbf{x} = \mathbf{b} \end{align*} as

\displaystyle \begin{align*} \left[ \begin{matrix} \phantom{-}2 & 4 & \phantom{-}0 & 1 \\ \phantom{-}2 & 8 & -2 & 7 \\ -2 & 2 & -2 & 7 \\ \phantom{-}0 & 8 & -5 & 11 \end{matrix} \right] \left[ \begin{matrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{matrix} \right] = \left[ \begin{matrix} \phantom{-}7 \\ \phantom{-}3 \\ -7 \\ -12 \end{matrix} \right] \end{align*}

To get the LU factorisation we need to use Gaussian Elimination on the coefficient matrix...

\displaystyle \begin{align*} A = \left[ \begin{matrix} \phantom{-}2 & 4 & \phantom{-}0 & 1 \\ \phantom{-}2 & 8 & -2 & 7 \\ -2 & 2 & -2 & 7 \\ \phantom{-}0 & 8 & -5 & 11 \end{matrix} \right] \end{align*}

To eliminate the terms under the main diagonal in the first column, we will apply Row 2 - Row 1 to Row 3 and Row 3 - (-1)Row 1 to Row 3. As we are eliminating the elements \displaystyle \begin{align*} a_{2,1} \end{align*} and \displaystyle \begin{align*} a_{3, 1} \end{align*}, that means in our lower triangular matrix, which has 1 as all the elements on the main diagonal and the multipliers of the rows as its coefficients under the main diagonal, will have \displaystyle \begin{align*} \mathcal{l}_{2,1} = 1 \end{align*} and \displaystyle \begin{align*} \mathcal{l}_{3,1} = -1 \end{align*}. Since we didn't have to do anything with element \displaystyle \begin{align*} a_{4,1} \end{align*} that means the multiplier is 0, and thus \displaystyle \begin{align*} \mathcal{l}_{4,1} = 0 \end{align*}. A has now become

\displaystyle \begin{align*} \left[ \begin{matrix} 2 & 4 & \phantom{-}0 & 1 \\ 0 & 4 & -2 & 6 \\ 0 & 6 & -2 & 8 \\ 0 & 8 & -5 & 11 \end{matrix} \right] \end{align*}

To eliminate the terms under the main diagonal in the second column, we will apply Row 3 - (3/2)Row 2 to Row 3 and Row 4 - 2 Row 2 to Row 4. As we are eliminating the elements \displaystyle \begin{align*} a_{3,2} \end{align*} and \displaystyle \begin{align*} a_{4,2} \end{align*}, this means that \displaystyle \begin{align*} \mathcal{l}_{3,2} = \frac{3}{2} \end{align*} and \displaystyle \begin{align*} \mathcal{l}_{4,2} = 2 \end{align*}. A has now become

\displaystyle \begin{align*} \left[ \begin{matrix} 2 & 4 & \phantom{-}0 & \phantom{-}1 \\ 0 & 4 & -2 & \phantom{-}6 \\ 0 & 0 & \phantom{-}1 & -1 \\ 0 & 0 & -1 & \phantom{-}1 \end{matrix} \right] \end{align*}

To eliminate the term under the main diagonal in the third column, we will apply Row 4 - (-1)Row 3 to Row 4. As we are eliminating the element \displaystyle \begin{align*} a_{4,3} \end{align*} that means that \displaystyle \begin{align*} \mathcal{l}_{4,3} = -1 \end{align*}. A has now become

\displaystyle \begin{align*} \left[ \begin{matrix} 2 & 4 & \phantom{-}0 & \phantom{-}1 \\ 0 & 4 & -2 & \phantom{-}6 \\ 0 & 0 & \phantom{-}1 & -1 \\ 0 & 0 & \phantom{-}0 & -2 \end{matrix} \right] \end{align*}

So we have found that our lower triangular matrix \displaystyle \begin{align*} L = \left[ \begin{matrix} \phantom{-}1 & 0 & \phantom{-}0 & 0 \\ \phantom{-}1 & 1 & \phantom{-}0 & 0 \\ -1 & \frac{3}{2} & \phantom{-}1 & 0 \\ \phantom{-}0 & 2 & -1 & 1 \end{matrix} \right] \end{align*} and our upper triangular matrix \displaystyle \begin{align*} U = \left[ \begin{matrix} 2 & 4 & \phantom{-}0 & \phantom{-}1 \\ 0 & 4 & -2 & \phantom{-}6 \\ 0 & 0 & \phantom{-}1 & -1 \\ 0 & 0 & \phantom{-}0 & -2 \end{matrix} \right] \end{align*}.

This reduces the system to \displaystyle \begin{align*} L\,U\,\mathbf{x} = \mathbf{b} \end{align*}. Notice that \displaystyle \begin{align*} U\,\mathbf{x} \end{align*} is a column matrix when multiplied out, which we can call \displaystyle \begin{align*} \mathbf{g} \end{align*}. This now reduces the system to two simpler matrix equations, as the coefficient matrices are diagonal. They are \displaystyle \begin{align*} L\,\mathbf{g} = \mathbf{b} \end{align*} and \displaystyle \begin{align*} U\,\mathbf{x} = \mathbf{g} \end{align*}.

Solving for \displaystyle \begin{align*} \mathbf{g} \end{align*} we have

\displaystyle \begin{align*} \left[ \begin{matrix} \phantom{-}1 & 0 & \phantom{-}0 & 0 \\ \phantom{-}1 & 1 & \phantom{-}0 & 0 \\ -1 & \frac{3}{2} & \phantom{-}1 & 0 \\ \phantom{-}0 & 2 & -1 & 1 \end{matrix} \right] \left[ \begin{matrix} g_1 \\ g_2 \\ g_3 \\ g_4 \end{matrix} \right] = \left[ \begin{matrix} \phantom{-}7 \\ \phantom{-}3 \\ -7 \\ -12 \end{matrix} \right] \end{align*}

We can see \displaystyle \begin{align*} g_1 = 7 \end{align*}. Forward substituting gives

\displaystyle \begin{align*} g_1 + g_2 &= 3 \\ 7 + g_2 &= 3 \\ g_2 &= -4 \end{align*}

Forward substituting gives

\displaystyle \begin{align*} -g_1 + \frac{3}{2}\,g_2 + g_3 &= -7 \\ -7 - 6 + g_3 &= -7 \\ g_3 &= 6 \end{align*}

Forward substituting gives

\displaystyle \begin{align*} 2\,g_2 - g_3 + g_4 &= -12 \\ -8 - 6 + g_4 &= -12 \\ -14 + g_4 &= -12 \\ g_4 &= 2 \end{align*}

Now solving \displaystyle \begin{align*} U\,\mathbf{x} = \mathbf{g} \end{align*} for \displaystyle \begin{align*} \mathbf{x} \end{align*} gives

\displaystyle \begin{align*} \left[ \begin{matrix} 2 & 4 & \phantom{-}0 & \phantom{-}1 \\ 0 & 4 & -2 & \phantom{-}6 \\ 0 & 0 & \phantom{-}1 & -1 \\ 0 & 0 & \phantom{-}0 & -2 \end{matrix} \right] \left[ \begin{matrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{matrix} \right] = \left[ \begin{matrix} \phantom{-}7 \\ -4 \\ \phantom{-}6 \\ \phantom{-}2 \end{matrix} \right] \end{align*}

We can see that

\displaystyle \begin{align*} -2x_4 &= 2 \\ x_4 &= -1 \end{align*}

Back substituting gives

\displaystyle \begin{align*} x_3 - x_4 &= 6 \\ x_3 + 1 &= 6 \\ x_3 &= 5 \end{align*}

Back substituting gives

\displaystyle \begin{align*} 4\,x_2 - 2\,x_3 + 6\,x_4 &= -4 \\ 4\,x_2 - 10 - 6 &= -4 \\ 4\,x_2 &= 12 \\ x_2 &= 3 \end{align*}

Back substituting gives

\displaystyle \begin{align*} 2\,x_1 + 4\,x_2 + x_4 &= 7 \\ 2\,x_1 + 12 - 1 &= 7 \\ 2\,x_1 &= -4 \\ x_1 &= -2 \end{align*}

So to answer your question we have \displaystyle \begin{align*} g_1 = 7 , \, g_2 = -4 , \, g_3 = 6 , \, g_4 = 2, \, x_1 = -2 , \, x_2 = 3 , \, x_3 = 5 \end{align*} and \displaystyle \begin{align*} x_4 = -1 \end{align*}.