1
$\begingroup$

I've the following matrix:

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

and I need to find the matrices $P, L$ and $U$, such that

$$PA = LU$$

what I need was to find the matrices representing the guassian elimination operations to obtain the upper triangle, and I found the following two:

$$l_2 l_2 A = U$$

specifically:

$$ l_1 =\begin{bmatrix} 0& 1& 0& 0 \\ 1& 0& 0& 0 \\ 0& 0& 1& 0 \\ 0& 0& 0& 1 \end{bmatrix} $$

$$ l_2 = \begin{bmatrix} 1& 0& 0& 0 \\ 0& 1& 0& 0 \\ 0& 0& 0& 1 \\ 0& 0& 1& 0 \end{bmatrix} $$

such that $$ l_2 l_1 A = PA = U $$

where $$ U = \begin{pmatrix} 4 & 3& 2& 1 \\ 0 & 7& 5& 1 \\0 & 0& -1& -2 \\ 0 & 0& 0& 1 \end{pmatrix} $$ So, what's the lower triangular matrix of this $LU$ decomposition? Is it the identity matrix?

$\endgroup$
  • $\begingroup$ $\text{ P = }\left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right)$, $\text{ L = }\left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right)$, $\text{ U = }\left( \begin{array}{cccc} 4 & 3 & 2 & 1 \\ 0 & 7 & 5 & 1 \\ 0 & 0 & -1 & -2 \\ 0 & 0 & 0 & 1 \\ \end{array} \right)$. Check $PA = LU$. $\endgroup$ – Moo May 1 '16 at 19:28
  • $\begingroup$ @Moo Now, try to find for example the solution to the equation $A x = (26, 9, 1, -3)^T$. At least from my calculations, i.e. using $L$ and $U$ as you're and me are saying it seems that something is wrong because the solution that I found is wrong, even though $PA = LU$. $\endgroup$ – nbro May 1 '16 at 22:50
  • $\begingroup$ Works perfectly! $\endgroup$ – Moo May 1 '16 at 23:17
  • $\begingroup$ @Moo Could you please then show me and explain how are you doing it then? I've probably misunderstood something... $\endgroup$ – nbro May 2 '16 at 10:25
  • $\begingroup$ @Moo Sorry man, I've time only now to have a look at your answer and explanations. I will give you some feedback in a few minutes. $\endgroup$ – nbro May 4 '16 at 21:05
1
$\begingroup$

For $A= \begin{pmatrix} 0& 7& 5& 1 \\ 4& 3& 2& 1 \\0 &0& 0& 1 \\ 0& 0& -1& -2 \end{pmatrix} $, we have:

$$\text{ P = }\left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right), \text{ L = }\left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right), \text{ U = }\left( \begin{array}{cccc} 4 & 3 & 2 & 1 \\ 0 & 7 & 5 & 1 \\ 0 & 0 & -1 & -2 \\ 0 & 0 & 0 & 1 \\ \end{array} \right)$$

You can easily verify that:

$$PA = LU$$

Next, we want to use this result to solve $Ax = b$ such that:

$$ \begin{pmatrix} 0& 7& 5& 1 \\ 4& 3& 2& 1 \\0 &0& 0& 1 \\ 0& 0& -1& -2 \end{pmatrix}x = \begin{pmatrix} 26 \\ 9 \\1 \\ -3 \end{pmatrix}$$

The general process is:

  • Construct $L, U, P$ as shown above
  • Compute $Pb$
  • Solve $Ly = Pb$ for $y$ using Forward Substitution
  • Solve $Ux = y$ for $x$ using Back Substitution

So, forming $Ly = P b$ and using forward substitution gives:

$$\left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right) y = \begin{pmatrix} 9 \\ 26 \\ -3 \\ 1 \end{pmatrix} \implies y = \begin{pmatrix} 9 \\ 26 \\ -3 \\ 1 \end{pmatrix}$$

Next, we form $Ux = y$ in order to be able to solve for $x$ using back substitution:

$$\begin{pmatrix} 4& 3& 2& 1 \\ 0& 7& 5& 1 \\ 0& 0& -1& -2 \\ 0 &0& 0& 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} 9 \\ 26 \\ -3 \\ 1 \end{pmatrix}$$

Using back substitution, this yields:

$$ x = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} -\dfrac{9}{14} \\ \dfrac{20}{7} \\ 1 \\ 1 \end{pmatrix}$$

$\endgroup$
  • $\begingroup$ I think you did a mistake in your calculations because the initial vector was $(9, 26, 1, -3)^T$ and not $(9, 26, -3, 1)^T$. $\endgroup$ – nbro May 5 '16 at 11:20
  • $\begingroup$ Point 1: Recall from my steps above, we MUST setup $Ly = Pb$ and use forward substitution. What is $Pb$ in this case? Point 2: Test the solution, does it satisfy the system? $\endgroup$ – Moo May 5 '16 at 11:44
  • $\begingroup$ Ok, sorry, I read part of the answer yesterday and part today. You're right, you multiplied first $P$ with $b$, what I don't understand exactly is why, maybe it's because I didn't think about how can we use $U$ and $L$ in general to solve a system of the form $Ax = b$. And yes, I got the same answer now. $\endgroup$ – nbro May 5 '16 at 11:50
  • $\begingroup$ That is the reason I added that outline, because we also need to understand how to use the items we found that include the permutation matrix, as well as $U$ and $L$. $\endgroup$ – Moo May 5 '16 at 12:03

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.