LU Decomposition by hand

edited January 22 in Problems

Compute the LU Decomposition of
$$
A = \left(
\begin{array}{ccc}
1 & 4 & 1 \\
5 & 17 & 3 \\
1 & -2 & -6
\end{array}
\right)
$$
and use this to solve the system $A\vec{x} = \langle 0, 0, 1 \rangle$.

Note: While you can certainly use the computer to check your work, you should try it by hand as this is exactly the kind thing we might see on a quiz.

frank

Comments

  • dandan
    edited February 3

    Step 1.) Solve for P, by hand:
    I went ahead and did some row swaps, trying to fit the mold of the partial pivot method:

    $$
    PA = \left(\begin{array}{ccc}
    5 & 17 & 3 \\
    1 & 4 & 1 \\
    1 & -2 & -6 \\
    \end{array}\right)$$
    Than python told me my P matrix was wrong and I had to think about why that was. It seams that 4 > -2 was the best way to go, but I didn't take into account that |-2 -17|>|4-17|, assuming that this was the correct choice, I followed suit with what PA of A should be

    $$PA = \left(\begin{array}{ccc}
    5 & 17 & 3 \\
    1 & -2 & -6 \\
    1 & 4 & 1\\
    \end{array}\right)\rightarrow
    P=\left(\begin{array}{ccc}
    0 & 0 & 1 \\
    1 & 0 & 0 \\
    0 & 1 & 0 \\
    \end{array}\right)$$

    Step 2.) Solve for U and L
    I found this shorthand method online, that makes writing this down a lot easier. http://www.ohiouniversityfaculty.com/youngt/IntNumMeth/lecture12.pdf
    The short version of it is: On your way to get the U matrix, catalog your row operations in each matrix. This is done, by everytime you create a 0 to form a new pivot, put the multiplier you used to add the rows in (parenthese) of that zero. When you go to make your L matrix, take all the (parentheses) and flip the signs, along with the identity matrix. I'll demonstrate the steps here:

    $$ PA = \left(\begin{array}{ccc}
    5 & 17 & 3 \\
    1 & -2 & -6 \\
    1 & 4 & 1 \\
    \end{array}\right) \sim
    \left(\begin{array}{ccc}
    5 & 17 & 3 \\
    (-1/5) & -5.4 & -6.6 \\
    1 & 4 & 1\\
    \end{array}\right)
    \sim$$

    $$ \left(\begin{array}{ccc}
    5 & 17 & 3 \\
    (-1/5) & -5.4 & -6.6 \\
    (-1/5) & 0.6 & 0.4\\
    \end{array}\right) \sim
    \left(\begin{array}{ccc}
    5 & 17 & 3 \\
    (-1/5) & -5.4 & -6.6 \\
    (-1/5) & (1/9) & 1/3\\
    \end{array}\right)$$

    This gives us both the U and L matrix.

    Where as:

    $$ U = \left(\begin{array}{ccc}
    5 & 17 & 3 \\
    0 & -5.4 & -6.6 \\
    0 & 0 & -1/3\\
    \end{array}\right)$$

    and

    $$ L = \left(\begin{array}{ccc}
    1 & 0 & 0 \\
    1/5 & 1 & 0 \\
    1/5 & -1/9 & 1\\
    \end{array}\right)$$

    Step 3.)
    $$ A\vec{x} = \left(\begin{array{c}
    0, 0, 1\\
    \end{array}\right$$

    I went by the way of the book and class notes for this one, which seems like the easiest notation for writing it out by hand.

    Where as:

    $$LU\vec{x} = \left(\begin{array}{c}
    0, 0, 1\\
    \end{array}\right)\rightarrow $$

    $$L\vec{c} = \left(\begin{array}{c}
    0, 0, 1 \\
    \end{array}\right)$$

    $$ =\left(\begin{array}{ccc}
    1 & 0 & 0 \\
    1/5 & 1 & 0 \\
    1/5 & -1/9 & 1\\
    \end{array}\right)
    \begin{bmatrix}
    a\\
    b\\
    c\\
    \end{bmatrix}
    = \begin{bmatrix}
    0\\
    0\\
    1\\
    \end{bmatrix}$$

    $$ \rightarrow
    a =0, b =0, c = 1$$

    From here: Ux = c

    $$U = \left(\begin{array}{ccc}
    5 & 17 & 3 \\
    0 & -5.4 & -6.6 \\
    0 & 0 & -1/3\\
    \end{array}\right)
    \begin{bmatrix}
    x\\
    y\\
    z\\
    \end{bmatrix}$$

    $$ \rightarrow 5x+17y+3z = 0$$
    $$ -5.4y+66.z = 0$$
    $$z = -3$$

    $$ \rightarrow x = \frac{-32}{3}, y=\frac{11}{3}, and z = -3$$

  • edited February 5

    I did some elementary row operations,

    $$-5R_{1}+R_{2}\\
    -R_{1}+R_{3}\\
    -2R_{2}+R_{3},$$

    and found the $L$ and $U$ matrices,

    $$L = \begin{pmatrix}
    1&0&0\\
    5&1&0\\
    1&2&1\end{pmatrix}$$

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

    I then solved $L\vec{c} = \vec{b}$ and $U\vec{x} = \vec{c}$ through back substitution and found that

    $$\vec{b} = \begin{pmatrix}
    -\frac{5}{9}\\
    \frac{2}{9}\\
    -\frac{1}{3}\end{pmatrix}.$$

    mark
  • @frank I think your third elementary row operation should be $-2R_2 + R_3$.

  • Yes, that looks much better. Thanks!

    mark
Sign In or Register to comment.