Contents

• 1  PA = LU decomposition
• 2  Forward substitution Ly = Pb
• 3  Backward substitution Ux = y

Consider the system $A\mathbf{x}=\mathbf{b}$ with

$$ A=\left(\begin{array}{crc} 0 & 1 & 3\\ 3 & 0 & 1\\ 1 & -2 & 1 \end{array}\right) \quad \mathbf{b}=\left(\begin{array}{c} -2\\ -1\\ -3 \end{array}\right) $$

Find $\mathbf{x}$ using the $LU$ decomposition with partial pivoting.

---

The $LU$ has the same problem as Gauss elimination: it is not fully functional if we do not apply pivoting.

In order to store the row permutations, the permutation matrix $P$ is used. Initially, it is the identity matrix and is modified every time there is a swapping of rows.

The steps are

1. Decomposition: $PA=LU$
2. Forward substitution: $PAx=Pb \Longrightarrow LUx=Pb \Longrightarrow Ly = Pb$. We solve $Ly=Pb$.
3. Backward substitution: We solve $Ux=y$.

PA = LU decomposition

Matrices $A$ and $P$ will start as

$$ A=\left(\begin{array}{crc} \mathbf{0} & 1 & 3\\ 3 & 0 & 1\\ 1 & -2 & 1 \end{array}\right) \qquad P_{0}=\left(\begin{array}{crr} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{array}\right) $$

We apply pivoting: in the first step we look for the element with the maximum absolute value below the pivot $a_{11}$. This is $a_{21}$ and we swap rows 2 and 1 both in $P$ and $A.$

$$ A_{1}=\left(\begin{array}{rrr} \mathbf{3} & 0 & 1\\ 0 & 1 & 3\\ 1 & -2 & 1 \end{array}\right)\qquad P_{1}=\left(\begin{array}{crr} 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{array}\right) $$

Now, we make zeros below the $a_{11}$ element by subtracting the first row multiplied by a factor with the pivot ($a_{11}$) in the denominator and the element of that row below the pivot ($a_{21}$ and $a_{31}$ respectively) in the numerator.

$$ \begin{array}{c} r_{1}\\ r_{2}\\ r_{3} \end{array}\left(\begin{array}{rrr} \mathbf{3} & 0 & 1\\ 0 & 1 & 3\\ 1 & -2 & 1 \end{array}\right)\quad\begin{array}{lclcrr} r_{1} & \rightarrow & r_{1}\\ r_{2} & \rightarrow & r_{2} & - & \color{red}{\fbox{0/3}} & r_{1}\\ r_{3} & \rightarrow & r_{3} & - & \color{blue}{\fbox{1/3}} & r_{1} \end{array} $$

We construct the $L$ matrix with the factors that appear in the boxes. We insert them into the matrix, in the place of the obtained zeros (to save storage space). The transformed matrix is

$$ \left(\begin{array}{rrr} 3 & 0 & 1\\ \color{red}{\fbox{0}} & \mathbf{1} & 3\\ \color{blue}{\fbox{1/3}} & -2 & 2/3 \end{array}\right) $$

We apply the pivot strategy again: we look for the element with the maximum absolute value below the pivot $a_{22}$. This turns out to be $a_{32}$ so we swap rows 2 and 3 in $P$, $A$ and $L$.

$$ \left(\begin{array}{rrr} 3 & 0 & 1\\ \color{blue}{\fbox{1/3}} & \mathbf{-2} & 2/3\\ \color{red}{\fbox{0}} & 1 & 3 \end{array}\right)\qquad P_{2}=\left(\begin{array}{crr} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{array}\right) $$

Now, we make zeros below $a_{22}$ subtracting the second row multiplied by a factor with the pivot ($a_{22}$) in the denominator and the element of that row below the pivot ($a_{32}$) in the numerator.

$$ \left(\begin{array}{rrr} 3 & 0 & 1\\ \color{blue}{\fbox{1/3}} & \mathbf{-2} & 2/3\\ \color{red}{\fbox{0}} & 1 & 3 \end{array}\right)\quad\begin{array}{lclcrr} r_{1} & \rightarrow & r_{1}\\ r_{2} & \rightarrow & r_{2}\\ r_{3} & \rightarrow & r_{3} & - & \color{ForestGreen}{\fbox{$1/(-2)$}} & r_{2} \end{array} $$

We arrive at the matrix that simultaneously stores $L$ and $U$.

$$ \left(\begin{array}{rrr} 3 & 0 & 1\\ \color{blue}{\fbox{1/3}} & -2 & 2/3\\ \color{red}{\fbox{0}} & \color{ForestGreen}{\fbox{$-1/2$}} & 10/3 \end{array}\right) $$

And the matrices $L$, $U$ and $P$ are:

$$ L = \left(\begin{array}{rrr} 1 & 0 & 0\\ \color{blue}{\fbox{1/3}} & 1 & 0\\ \color{red}{\fbox{0}} & \color{ForestGreen}{\fbox{$-1/2$}} & 1 \end{array}\right) \quad U=\left(\begin{array}{rrr} 3 & 0 & 1 \\ 0 & -2 & 2/3\\ 0 & 0 & 10/3 \end{array}\right) \qquad P_{2}=\left(\begin{array}{crr} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{array}\right) $$

And $\mathbf{b}$ and $P\,\mathbf{b}$ are

$$ \mathbf{b}=\left(\begin{array}{c} -2\\ -1\\ -3 \end{array}\right) \qquad P\,\mathbf{b}=\left(\begin{array}{c} -1\\ -3\\ -2 \end{array}\right) $$

Forward substitution Ly = Pb

$$ \begin{array}{rrrrrrr} & y_1 & & & & & = &-1\\ & 1/3 y_1& + &y_2 & + & & = & -3\\ & & - &1/2 y_2 & + & y_3 & =& -2& \end{array} $$

From the first equation $$ y_1 = -1$$ From the second one $$ y_2 = -3 -(1/3) y_1= -3 -(1/3)(-1) = -8/3$$ And from the third one $$ y_3 = -2+(1/2)y_2=-2+(1/2)(-8/3)=-10/3$$ That is $$ y_1 = -1 \quad y_2 = -8/3 \quad y_3 = -10/3$$

Backward substitution Ux = y

$$ \begin{array}{rrrrrrr} & 3x_1 & &&+ & x_3 & = &-1\\ & & - &2x_2 & + & (2/3)x_3 & = & -8/3\\ & & & & & (10/3)x_3 & =& -10/3& \end{array} $$

From the third equation $$ x_3 = -1$$ From the second one $$ x_2 = \frac{-(8/3) -(2/3) x_3}{-2} = \frac{-(8/3) -(2/3) (-1)}{-2} = 1$$ And from the first one $$ x_1 = \frac{-1-x_3}{3}=\frac{-1-(-1)}{3} =0$$ That is $$ x_1 = 0 \quad x_2 = 1 \quad x_3 = -1$$