# Thread: Compute the LU factorization

1. ## Compute the LU factorization

Compute the LU factorization of the matrix
A=
[2 1 1]
[4 1 0]
[-2 2 1]

and solve A[ $x_1$ $x_2$ $x_3$ $]^T$ = ][8 11 3 $]^T$
using back substitution.

Let A=
[1 1 1]
[1 1 2]
[1 2 5]
Find a permutation matrix $P$ $\in$ $R^{3,3}$ so that PA has an LU factoriza-
tion. Compute L and U.

this is should be an easy question, but it's been so long since i ve done matrix, so any help will be appreaciated..

2. $\displaystyle
LU=\begin{bmatrix}
l_{11} & 0 & 0\\
l_{21} & l_{22} & 0\\
l_{31} & l_{32} & l_{33}
\end{bmatrix}
\begin{bmatrix}
u_{11} & u_{12} & u_{13}\\
0 & u_{22} & u_{23}\\
0 & 0 & u_{33}
\end{bmatrix}=\begin{bmatrix}2&1&1\\4&1&0\\-2&2&1\end{bmatrix}=A$

$\displaystyle A=\sum_{i=1}^{3}L_{ji}U_{ik}$

3. $\displaystyle
\begin{bmatrix}2&1&1\\4&1&0\\-2&2&1\end{bmatrix}= \begin{bmatrix}
l_{11} & 0 & 0\\
l_{21} & l_{22} & 0\\
l_{31} & l_{32} & l_{33}
\end{bmatrix}
\begin{bmatrix}
u_{11} & u_{12} & u_{13}\\
0 & u_{22} & u_{23}\\
0 & 0 & u_{33}
\end{bmatrix}$

If this gives too many variables to solve for, make $\displaystyle
l_{nn}=1$
i.e.

$\displaystyle
\begin{bmatrix}2&1&1\\4&1&0\\-2&2&1\end{bmatrix}= \begin{bmatrix}
1 & 0 & 0\\
l_{21} & 1 & 0\\
l_{31} & l_{32} & 1
\end{bmatrix}
\begin{bmatrix}
u_{11} & u_{12} & u_{13}\\
0 & u_{22} & u_{23}\\
0 & 0 & u_{33}
\end{bmatrix}$

4. $\displaystyle \begin{bmatrix} 2 & 1 & 1\\ 4 & 1 & 0\\ -2 & 2 & 1 \end{bmatrix}$ $\displaystyle \rightarrow \displaystyle \begin{bmatrix} 2 & 1 & 1\\ 0 & -1 & -2\\ 0 & 3 & 2 \end{bmatrix}$ $\rightarrow \displaystyle \begin{bmatrix} 2 & 1 & 1\\ 0 & -1 & -2\\ 0 & 0 & -4 \end{bmatrix} = U$

$L = \displaystyle \begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ -1 & -3 & 1 \end{bmatrix}$ (where 2,-1,and -3 are the multipliers used to eliminate those three entires of the original matrix)

first solve $\displaystyle Lc = \begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ -1 & -3 & 1 \end{bmatrix} \begin{bmatrix} c_{1}\\ c_{2}\\ c_{3} \end{bmatrix}= \begin{bmatrix} 8\\ 11\\ 3 \end{bmatrix}$

then solve $\displaystyle Ux = \begin{bmatrix} 2 & 1 & 1\\ 0 & -1 & -2\\ 0 & 0 & -4 \end{bmatrix} \begin{bmatrix} x_{1}\\ x_{2}\\ x_{3} \end{bmatrix}= \begin{bmatrix} c_{1}\\ c_{2}\\ c_{3} \end{bmatrix}$

5. Originally Posted by Random Variable
$\displaystyle \begin{bmatrix} 2 & 1 & 1\\ 4 & 1 & 0\\ -2 & 2 & 1 \end{bmatrix}$ $\displaystyle \rightarrow \displaystyle \begin{bmatrix} 2 & 1 & 1\\ 0 & -1 & -2\\ 0 & 3 & 2 \end{bmatrix}$ $\rightarrow \displaystyle \begin{bmatrix} 2 & 1 & 1\\ 0 & -1 & -2\\ 0 & 0 & -4 \end{bmatrix} = U$

$L = \displaystyle \begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ -1 & -3 & 1 \end{bmatrix}$ (where 2,-1,and -3 are the multipliers used to eliminate those three entires of the original matrix)

first solve $\displaystyle Lc = \begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ -1 & -3 & 1 \end{bmatrix} \begin{bmatrix} c_{1}\\ c_{2}\\ c_{3} \end{bmatrix}= \begin{bmatrix} 8\\ 11\\ 3 \end{bmatrix}$

then solve $\displaystyle Ux = \begin{bmatrix} 2 & 1 & 1\\ 0 & -1 & -2\\ 0 & 0 & -4 \end{bmatrix} \begin{bmatrix} x_{1}\\ x_{2}\\ x_{3} \end{bmatrix}= \begin{bmatrix} c_{1}\\ c_{2}\\ c_{3} \end{bmatrix}$
thx, I got the idea, so how do I find the permutation matrix, is there something to do with the identity matrix?

6. Partial pivoting is about exchanging rows so that you are always pivoting on the entry in the column with largest absolute value. It's to try to prevent what's referred to as swamping.

Since all the entries in the first column are the same, you don't need to exchange any rows.

$\displaystyle \begin{bmatrix} 1 & 1 & 1\\ 1 & 1 & 2\\ 1 & 2 & 5 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 1 & 1\\ 0(1) & 0 & 1\\ 0(1) & 1 & 4 \end{bmatrix}$

It's a good idea to put the multipliers in parenthesis so that you can keep track of them when you exchange rows.

In this problem it's not about swamping, but rather the fact that you can't pivot on a zero. So exchange rows 2 and 3. The permuatation matrix for such a exchange is $\displaystyle \begin{bmatrix} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end{bmatrix}$

$\displaystyle \rightarrow \begin{bmatrix} 1 & 1 & 1\\ 0(1) & 1 & 4\\ 0(1) & 0 & 1 \end{bmatrix}$

then $\displaystyle PA = \begin{bmatrix} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1\\ 1 & 1 & 2\\ 1 & 2 & 5 \end{bmatrix}$ $\displaystyle = LU = \begin{bmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ 1 & 0 & 1 \end{bmatrix}\begin{bmatrix} 1 & 1 & 1\\ 0 & 1 & 4\\ 0 & 0 & 1 \end{bmatrix}$