<s>[INST] Performing LU factorization on Ax = b. Can someone show me step by step how this works? 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.
 [/INST] 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.)$?
</s>