# LU Decomposition exercises and quiz

## Exercise 1

Problem
Given the 3x3 matrix:

${\displaystyle A={\begin{bmatrix}2&-1&3\\4&2&1\\-6&-1&2\end{bmatrix}}}$

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: ${\displaystyle A={\begin{bmatrix}2&-1&3\\4&2&1\\-6&-1&2\end{bmatrix}}={\begin{bmatrix}1&0&0\\l_{21}&1&0\\l_{31}&l_{32}&1\end{bmatrix}}\times {\begin{bmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\end{bmatrix}}}$.

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 ${\displaystyle -l_{21}}$.

Therefore:

 ${\displaystyle \displaystyle \ l_{21}=}$ . And ${\displaystyle A\rightarrow A1={\begin{bmatrix}2&-1&3\\0&4&-5\\-6&-1&2\end{bmatrix}}}$. In the similar manner we have: ${\displaystyle \displaystyle \ l_{31}=}$ . And ${\displaystyle A1\rightarrow A2={\begin{bmatrix}2&-1&3\\0&4&-5\\0&-4&11\end{bmatrix}}}$ ${\displaystyle \displaystyle \ l_{32}=}$ . And ${\displaystyle A2\rightarrow A3=U={\begin{bmatrix}2&-1&3\\0&4&-5\\0&0&6\end{bmatrix}}}$. Eventually, A has been factorized to LU: ${\displaystyle A={\begin{bmatrix}2&-1&3\\4&2&1\\-6&-1&2\end{bmatrix}}={\begin{bmatrix}1&0&0\\**&1&0\\**&*&1\end{bmatrix}}\times {\begin{bmatrix}2&-1&3\\0&4&-5\\0&0&6\end{bmatrix}}}$.

## Exercise 2

Use exercise 1's result to solve the system:

${\displaystyle {\begin{bmatrix}2x_{1}-x_{2}+3x_{3}=4\\4x_{1}+2x_{2}+x_{3}=7\\-6x_{1}-x_{2}+2x_{3}=-5\end{bmatrix}}}$

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:

${\displaystyle A={\begin{bmatrix}2&-1&3\\4&2&1\\-6&-1&2\end{bmatrix}}\times {\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\end{bmatrix}}}$ = ${\displaystyle {\begin{bmatrix}4\\7\\-5\end{bmatrix}}.}$

Since ${\displaystyle A=LU}$, by Exercise 1 we have:

${\displaystyle {\begin{bmatrix}1&0&0\\**&1&0\\**&*&1\end{bmatrix}}\times {\begin{bmatrix}2&-1&3\\0&4&-5\\0&0&6\end{bmatrix}}\times {\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\end{bmatrix}}={\begin{bmatrix}4\\7\\-5\end{bmatrix}}.}$

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

${\displaystyle {\begin{bmatrix}1&0&0\\**&1&0\\**&*&1\end{bmatrix}}\times {\begin{bmatrix}y_{1}\\y_{2}\\y_{3}\end{bmatrix}}={\begin{bmatrix}4\\7\\-5\end{bmatrix}}}$.

Use forward substitution we have:

 ${\displaystyle \displaystyle \ y_{1}=}$ ${\displaystyle \displaystyle \ y_{2}=}$ ${\displaystyle \displaystyle \ y_{3}=}$ Next, since ${\displaystyle Ux=y}$, we have ${\displaystyle {\begin{bmatrix}2&-1&3\\0&4&-5\\0&0&6\end{bmatrix}}\times {\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\end{bmatrix}}={\begin{bmatrix}y_{1}\\y_{2}\\y_{3}\end{bmatrix}}}$. Use backward substitution we have: ${\displaystyle \displaystyle \ x_{1}=}$ ${\displaystyle \displaystyle \ x_{2}=}$ ${\displaystyle \displaystyle \ x_{3}=}$