2
$\begingroup$

Find the $LU$ factorization of the matrix: $$\begin{bmatrix} 1 & 1 & 1 \\ 3 & 5 & 6 \\ -2 & 2 & 7 \end{bmatrix}$$

I am aware that I need to find $L=\begin{bmatrix} 1 & 0 & 0 \\ * & 1 & 0 \\ * & * & 1 \end{bmatrix}$ and $U=\begin{bmatrix} 1 & * & * \\ 0 & 1 & * \\ 0 & 0 & 1 \end{bmatrix}$

I did row transformations and got $U=\begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 0 & 3 \end{bmatrix}$ but I couldn't understand how to find $L=\begin{bmatrix} 1 & 0 & 0 \\ * & 1 & 0 \\ * & * & 1 \end{bmatrix}$

Can anyone explain how to find $L$

$\endgroup$
  • $\begingroup$ have you tried to invert U and multiply the inversion by the right ? $\endgroup$ – GBes Jul 4 '18 at 15:33
  • $\begingroup$ No, I actually have no idea how to get $L$. So, you say that I need to invert $U$ and then multiply the inverse with $U$ itself? $\endgroup$ – user572932 Jul 4 '18 at 15:37
1
$\begingroup$

For doing LU decomposition, you need to do Gaussian elimination. Here I'll just help you with the procedure, but if you want to understand why I recommend you to see this pdf http://www.math.iit.edu/~fass/477577_Chapter_7.pdf. Lets apply Gaussian elimination to A \begin{equation*} A = \left[ \begin{matrix} 1 & 1 & 1\\ 3 & 5 & 6 \\ -2 & 2 & 7 \end{matrix} \right] \end{equation*} For eliminating $A_{12}$ and $A_{13}$, we need to multiply by $-3$ and by $2$ the first row and add this to the second and third row respectively, obtaining \begin{equation*} \left[ \begin{matrix} 1 & 1 & 1\\ 0 & 2 & 3 \\ 0 & 4 & 9 \end{matrix} \right] \end{equation*} Now we eliminate $A_{32}$ multiplying by $-2$ the second row and adding it to the third one, obtaining \begin{equation*} \left[ \begin{matrix} 1 & 1 & 1\\ 0 & 2 & 3 \\ 0 & 0 & 3 \end{matrix} \right] \end{equation*} Which is the $U$ matrix, for the $L$ matrix we use the factors by which we multiplied each row for obtaining the $U$ matrix, i.e. $3,-2,2$. We use this elements in the position of the elements they eliminated, then \begin{equation*} L = \left[ \begin{matrix} 1 & 0 & 0\\ 3 & 1 & 0 \\ -2 & 2 & 1 \end{matrix} \right] \end{equation*}

$\endgroup$
0
$\begingroup$

Going off of GBes's comment, you can find $L$ through some quick matrix multiplication. Let's call the original matrix $A$. We know that $A=LU$, and since you have $U$ (which is invertible), you can multiply by $U^{-1}$ on the right on both sides to get the following: $$\begin{align} A&=LU \\ AU^{-1}&=LUU^{-1} \\ AU^{-1}&=L\end{align}$$

$\endgroup$
0
$\begingroup$

I use to call $E_{ij}(d)$ the operation of summing to the $i$-th row the $j$-th row multiplied by $d$.

Thus the Gaussian elimination runs as \begin{align} \begin{bmatrix} 1 & 1 & 1 \\ 3 & 5 & 6 \\ -2 & 2 & 7 \end{bmatrix} &\xrightarrow{\begin{gathered} E_{31}(2) \\ E_{21}(-3) \end{gathered}} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 4 & 9 \end{bmatrix} \\[6px] &\xrightarrow{E_{32}(-2)} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 0 & 3 \end{bmatrix}=U \end{align} Now it's just a matter of replacing each transformation by its inverse: $$ L=E_{21}(3)E_{31}(-2)E_{32}(2)= \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix} $$ At place $(2,1)$ put $3$, and so on.

This is justified by the fact that, if you consider $E_{ij}(d)$ the matrix you obtain by applying the transformation to the identity, then performing the row operation is the same as multiplying by this matrix.

Thus we have written $$ U=E_{32}(-2)E_{31}(2)E_{21}(-3)A $$ (where $A$ is your original matrix) and so $$ A=\underbrace{E_{21}(3)E_{31}(-2)E_{32}(2)}_{L}U $$ If one follows a strict order in doing the Gaussian elimination (top down and left to right), filling the matrix $L$ is just putting the coefficients in the indicated place.

$\endgroup$
0
$\begingroup$

Gaussian Elimination without Pivoting is as follows. The primary purpose of Gaussian elimination if you follow this is to find $\ell_{jk}$ which zeros out the row below. That is why it is the ratio of the two rows and then you subtract them. This continues on and on.

enter image description here

Suppose that

$$ A = \begin{bmatrix} 1 & 1 & 1 \\ 3 & 5 & 6 \\ -2 & 2 & 7 \end{bmatrix} $$ $$ A = LU $$

$$ U =A, L=I$$ $$ k=1,m=3,j=2$$ $$\ell_{21} = \frac{u_{21}}{u_{11}} = \frac{a_{21}}{a_{11}} = 3 $$ $$ u_{2,1:3} = u_{2,1:3} - 3 \cdot u_{1,1:3} $$ Then we're going to subtract 3 times the 1st row from the 2nd row $$ \begin{bmatrix} 3 & 5 & 6 \end{bmatrix} - 3 \cdot \begin{bmatrix} 1 & 1 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 2 & 3\end{bmatrix} $$ Updating each of them $$U = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ -2 & 2 & 7 \end{bmatrix} $$ $$ L =\begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$ $$k=1,j=3,m=3 $$ $$\ell_{31} = \frac{u_{31}}{u_{11}} = \frac{-2}{1} = -2 $$ $$ u_{3,1:3} = u_{3,1:3} +2 \cdot u_{1,1:3} $$ Then we add two times the first row to the third row $$ \begin{bmatrix} -2 & 2 & 7 \end{bmatrix} + 2 \cdot \begin{bmatrix} 1 & 1& 1 \end{bmatrix} = \begin{bmatrix}0 & 4 & 9 \end{bmatrix} $$ Updating $$ U = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 4 & 9 \end{bmatrix} $$ $$ L =\begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & 0 & 1 \end{bmatrix} $$ $$ k=2, j=3,m=3 $$ $$ \ell_{32} = \frac{u_{32}}{u_{22}} = \frac{4}{2} = 2$$ We're subtracting out little blocks $$ u_{3,2:3} = u_{3,2:3} - 2 \cdot u_{2,2:3} $$ $$ \begin{bmatrix} 4 & 9 \end{bmatrix} - 2 \cdot\begin{bmatrix} 2& 3 \end{bmatrix} = \begin{bmatrix} 0 & 3 \end{bmatrix} $$ Updating $$ U = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 0 & 3 \end{bmatrix} $$ $$ L =\begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix} $$ It now terminates $$ A = LU $$ $$ \underbrace{\begin{bmatrix} 1 & 1 & 1 \\ 3 & 5 & 6 \\ -2 & 2 & 7 \end{bmatrix}}_{A} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix}}_{L} \underbrace{\begin{bmatrix} 1 & 1 & 1 \\ 0 & 2 & 3 \\ 0 & 0 & 3 \end{bmatrix}}_{U} $$

$\endgroup$

Your Answer

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