Question from Jesse about Gaussian Elimination and LU factorisation.

In summary, the system $\displaystyle \begin{align*} A\,\mathbf{x} = \mathbf{b} \end{align*}$ can be written as a matrix equation, which can then be solved using Gaussian Elimination to find the lower triangular matrix $\displaystyle \begin{align*} L \end{align*}$ and the upper triangular matrix $\displaystyle \begin{align*} U \end{align*}$. The system is then reduced to two simpler matrix equations, which can be solved to find the values of $\displaystyle \begin{align*} x_1, x_2, x_3, x_4 \end{align*}$.
  • #1
Prove It
Gold Member
MHB
1,465
24
View attachment 5370

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*}$.
 

Attachments

  • gelu.jpg
    gelu.jpg
    67 KB · Views: 51
Mathematics news on Phys.org
  • #2


Thank you for the detailed explanation, it was very helpful! It's interesting to see how the Gaussian Elimination process can be broken down into smaller, simpler equations.
 

1. What is Gaussian Elimination?

Gaussian Elimination is a method used to solve a system of linear equations. It involves systematically eliminating variables from the equations until a solution can be found.

2. How does Gaussian Elimination work?

Gaussian Elimination works by using elementary row operations to reduce a matrix representing the system of equations to its row-echelon form. This process involves adding, subtracting, or multiplying rows to eliminate variables and create zeros in specific positions.

3. What is LU factorisation?

LU factorisation is a method to decompose a square matrix into an upper triangular matrix and a lower triangular matrix. This decomposition is useful in solving systems of linear equations, as it simplifies the calculations involved in Gaussian Elimination.

4. How is LU factorisation related to Gaussian Elimination?

LU factorisation is closely related to Gaussian Elimination, as the LU decomposition is used to simplify the calculations involved in Gaussian Elimination. Once the matrix is decomposed, the Gaussian Elimination process can be applied to solve the system of equations.

5. What are the advantages of using LU factorisation over Gaussian Elimination?

One advantage of LU factorisation is that it can be applied to any square matrix, while Gaussian Elimination is limited to systems of linear equations. Additionally, once a matrix is decomposed using LU factorisation, it can be easily solved for different sets of constant values, making it more efficient for solving multiple systems of equations with the same coefficients.

Similar threads

  • General Math
Replies
1
Views
4K
Replies
1
Views
4K
Replies
1
Views
5K
Replies
0
Views
4K
  • General Math
Replies
1
Views
4K
Replies
1
Views
6K
Replies
2
Views
5K
  • General Math
Replies
1
Views
11K
Replies
1
Views
10K
Back
Top