1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Try youtube. $\endgroup$ – user137731 Oct 26 '16 at 2:39
  • $\begingroup$ ..........thanks $\endgroup$ – Thandor7765 Oct 26 '16 at 2:41
  • $\begingroup$ Yes!! Please post if you have one $\endgroup$ – Thandor7765 Oct 26 '16 at 4:02
1
$\begingroup$

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.)$?

$\endgroup$
  • $\begingroup$ I got it!! Thanks! $\endgroup$ – Thandor7765 Oct 26 '16 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.