Numerical Analysis/LU decomposition exercises

LU Decomposition exercises and quiz

Exercise 1

Problem
Given the 3x3 matrix:

$A=\left[\begin{array}{ccc}2& -1& 3\\ 4& 2& 1\\ -6& -1& 2\end{array}\right]$

Find LU decomposition of A

Solution

The procedure of LU decomposition runs similar to the process of Gaussian Elimination. Firstly A is reduced to upper triangular form, which is U, using just the third elementary row operation, namely: add to one row of matrix a scalar time another row of that same matrix. Those scalar used during this process are co-efficient in the L matrix.

The final result will look like this: $A=\left[\begin{array}{ccc}2& -1& 3\\ 4& 2& 1\\ -6& -1& 2\end{array}\right]=\left[\begin{array}{ccc}1& 0& 0\\ l_{21}& 1& 0\\ l_{31}& l_{32}& 1\end{array}\right]\times \left[\begin{array}{ccc}{u}_{11}& u_{12}& u_{13}\\ 0& u_{22}& u_{23}\\ 0& 0& u_{33}\end{array}\right]$.

Here are the solution for this problem:

According to Gaussian Elimination, the first number in row 2 must be zero-out by adding the first row of matrix a scalar times second row. This scalar, fortunately, is $-l_{21}$.

Therefore:

<quiz display=simple> { |type="{}"}

$l_{21}=$ { 2 }.

And $A\to A1=\left[\begin{array}{ccc}2& -1& 3\\ 0& 4& -5\\ -6& -1& 2\end{array}\right]$.

In the similar manner we have:

$l_{31}=$ { -3 }.

And $A1\to A2=\left[\begin{array}{ccc}2& -1& 3\\ 0& 4& -5\\ 0& -4& 11\end{array}\right]$

$l_{32}=$ { -1 }.

And $A2\to A3=U=\left[\begin{array}{ccc}2& -1& 3\\ 0& 4& -5\\ 0& 0& 6\end{array}\right]$.

Eventually, A has been factorized to LU:

$A=\left[\begin{array}{ccc}2& -1& 3\\ 4& 2& 1\\ -6& -1& 2\end{array}\right]=\left[\begin{array}{ccc}1& 0& 0\\ **& 1& 0\\ **& *& 1\end{array}\right]\times \left[\begin{array}{ccc}2& -1& 3\\ 0& 4& -5\\ 0& 0& 6\end{array}\right]$.

</quiz>

Exercise 2

Use exercise 1's result to solve the system:

$\left[\begin{array}{c}2x_1-x_2+3x_3=4\\ 4x_1+2x_2+x_3=7\\ -6x_1-x_2+2x_3=-5\end{array}\right]$

Solution:

The idea of using LU decomposition to solve systems of simultaneous linear equations Ax=b is rewriting the systems as L(Ux)=b. To solve x, we first solve the systems Ly=b for y, and then, once y is determined, we solve the systems: Ux=y for x. Both systems are easy to solve, the first by forward substitution and the second by backward substitution.

Here is the solution for this exercise:

This system has the matrix form:

$A=\left[\begin{array}{ccc}2& -1& 3\\ 4& 2& 1\\ -6& -1& 2\end{array}\right]\times \left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]$ = $\left[\begin{array}{c}4\\ 7\\ -5\end{array}\right].$

Since $A=LU$, by Exercise 1 we have:

$\left[\begin{array}{ccc}1& 0& 0\\ **& 1& 0\\ **& *& 1\end{array}\right]\times \left[\begin{array}{ccc}2& -1& 3\\ 0& 4& -5\\ 0& 0& 6\end{array}\right]\times \left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}4\\ 7\\ -5\end{array}\right].$

Lets $y=U\times x$, we have:

$\left[\begin{array}{ccc}1& 0& 0\\ **& 1& 0\\ **& *& 1\end{array}\right]\times \left[\begin{array}{c}{y}_1\\ y_2\\ y_3\end{array}\right]=\left[\begin{array}{c}4\\ 7\\ -5\end{array}\right]$.

Use forward substitution we have:

<quiz display=simple> { |type="{}"}

$y_1=$ { 4 } $y_2=$ { -1 } $y_3=$ { 6 }

Next, since $Ux=y$, we have

$\left[\begin{array}{ccc}2& -1& 3\\ 0& 4& -5\\ 0& 0& 6\end{array}\right]\times \left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\end{array}\right]$.

Use backward substitution we have:

$x_1=$ { 1 } $x_2=$ { 1 } $x_3=$ { 1 } </quiz>