Performing LU factorization on Ax = b. Can someone show me step by step how this works?

Question

Consider matrix $$ A= \begin{bmatrix} 0 & -2 & 1 \\ 2 & 1 & -1 \\ -2 & -2 & 1 \\ \end{bmatrix} $$ and resulting vector :

b = (3
     0
     1)

Perform LU factorization with row swapping, indicating at each step the Gauss transform or pivot matrix used. Then solve Ax = b.

LU factorization is something I just cannot understand or wrap my head around. I would greatly appreciate it if someone could work this out and show the steps.

Thanks guys.

Answer 1

We are given:

$$A = \begin{bmatrix} 0 & -2 & 1 \\ 2 & 1 & -1 \\ -2 & -2 & 1 \end{bmatrix},b = \begin{bmatrix} 3 \\ 0 \\ 1 \end{bmatrix}$$

We are asked to solve $Ax = b$ using the LU factorization with pivoting. Our approach will be:

• $(1.)$ Compute $PA = LU$, if $PA = LU$, then $LU x = Pb$, so find $L, U, P$
• $(2.)$ Solve $Ly = Pb$ for $y$ using Forward Substitution
• $(3.)$ Solve $U x = y$ for $x$ using Backward Substitution

Step (1.)

We let $U = A$ and write $P$ and $L$ as the $3~x~3$ identity matrix, so:

$$U = \begin{bmatrix} 0 & -2 & 1 \\ 2 & 1 & -1 \\ -2 & -2 & 1 \end{bmatrix}, ~L = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, ~P = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

The first step of the factorization process is to determine the entry of largest magnitude in column $1$. This is the entry $2$ in row $2$. We therefore swap rows $1$ and $2$ of the matrices $U$ and $P$ to obtain:

$$U = \begin{bmatrix} 2 & 1 & -1\\ 0 & -2 & 1 \\ -2 & -2 & 1 \end{bmatrix}, ~L = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, ~P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

We then subtract suitable multiples of row $1$ of $U$ from rows $2$ through $3$, to create zeros in the first column of $U$ below the diagonal. The negative of the multiples are stored in the subdiagonal entries of the first column of the matrix $L$. These operations are ($R2$ already has a zero in the first position, so we leave it alone): $ 1 \times R1 + R3 \rightarrow R3$. This gives the matrices:

$$U = \begin{bmatrix} 2 & 1 & -1\\ 0 & -2 & 1 \\ 0 & -1 & 0 \end{bmatrix}, ~L = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix}, ~P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

We now repeat this for $R2$ and $R3$. We notice that we already have the largest magnitude in $R22$, so no row swap is needed. We now want to get zeros in the second position and see we can take $-\dfrac{1}{2} \times R2 + R3 \rightarrow R3$ and again update that entry in $L$ with the negative and we get:

$$U = \begin{bmatrix} 2 & 1 & -1\\ 0 & -2 & 1 \\ 0 & 0 & -\dfrac{1}{2} \end{bmatrix}, ~L = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & \dfrac{1}{2} & 1 \end{bmatrix}, ~P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

Since $U$ is upper triangular and $L$ is lower triangular, we now have $PA = LU$ (you can check this by multiplying those out).

Can you now do steps $(2.)$ and $(3.)$?