1
$\begingroup$

The following is a homework problem:

Let: $$A = \left[\matrix{4& 2& -5 &1\\ -8& 0& 9& 7\\ -32& -4& 43& 18\\ 24 &4 &-22 &-8\\} \right]$$

$$b = \left[\matrix{-1 \\ -1 \\ 3 \\ 14}\right]$$

Solve $A\cdot x = b$ by Naïve Gaussian elimination. Note the relationship between the subtractive row multipliers and the elements of the L matrix. How is the U matrix related to the reduced terms in the augmented matrix before back-substitution?

I have solved the problem and found $L$ and $U$ by Naïve Gaussian elimination.

$$U = \left[\matrix{4& 2& -5& 1\\ 0 &4 &-1& 9\\ 0& 0 &6 &-1\\ 0& 0& 0& 5\\}\right]$$ $$L = \left[\matrix{1& 0& 0& 0\\ -2& 0& 0& 0\\ -8& 3& 1& 0\\ 6& -2& -6 &1 \\ }\right]$$

However, what I seem to be having trouble with is the second part of the question ('How is the $U$ matrix related to the reduced terms in the augmented matrix before back-substitution?')

I understand that $U$ is the first 4 columns of the augmented $Ax$ matrix after row reduction, but what would be a proper answer to this question?

$\endgroup$
4
  • $\begingroup$ Those are not the usual $L$ and $U$, because $LU\ne A$. $\endgroup$
    – egreg
    Commented Feb 7, 2014 at 23:01
  • $\begingroup$ They actually are. Someone edited the question and messed up the values. The actual A matrix is [4 2 -5 1; -8 0 9 7; -32 -4 43 18; 24 4 -22 -8] $\endgroup$ Commented Feb 7, 2014 at 23:58
  • $\begingroup$ In the edit history there's no trace of the matrix you're saying. It has been like that since the beginning. Please, fix it in the question, not in comments. $\endgroup$
    – egreg
    Commented Feb 8, 2014 at 0:41
  • $\begingroup$ I probably copied and pasted the wrong one in the first place. anyway, fixed now $\endgroup$ Commented Feb 8, 2014 at 0:44

1 Answer 1

1
$\begingroup$

The matrix $A$ is lower triangular and invertible, because all coefficients on the diagonal are nonzero. So when you do the $LU$ decomposition, you have $L=A$ and $U$ is the identity matrix.

If you properly do Gaussian elimination, the first step (eliminating under the first pivot) will give the matrix $$ \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 3 & 1 & 0\\ 0 &-2 & 1 & 1 \end{bmatrix} $$ and so on for the other columns.


Since the original matrix has been changed, here's what can be said; after elimination according to the Gauss-Doolittle method (no reduction of pivots), we find, for the augmented matrix, the reduced form $$ [U\mid c]=\left[\begin{array}{cccc|c} 4 & 2 & -5 & 1 & -1 \\ 0 & 4 & -1 & 9 & -3 \\ 0 & 0 & 6 & -1 & 4 \\ 0 & 0 & 0 & 5 & 10 \end{array}\right] $$ and the matrix $L$ such that $L[\,U\mid c\,]=[\,A\mid b\,]$ is $$ L=\begin{bmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ -6 & -3 & 1 & 0 \\ 8 & 2 & -1 & 1 \end{bmatrix}. $$

The question ‘How is the $U$ matrix related to the reduced terms in the augmented matrix before back-substitution?’ is not really clear. What I can say is that the system $$ Ux=c, $$ where $c$ denotes the last column in the reduced augmented matrix, is equivalent to the original linear system $Ax=b$. In particular, the form of $U$ tells you that the system has a unique solution. The fact that $L[\,U\mid c\,]=[\,A\mid b\,]$ implies that $Lc=b$, so $c=L^{-1}b$.

What can be done now is to multiply the last row by $1/5$ and do “backwards elimination”, reducing the pivots: we find $$\left[\begin{array}{cccc|c} 1 & 0 & 0 & 0 & 12 \\ 0 & 1 & 0 & 0 & -5 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 2 \end{array}\right] $$ which shows the unique solution.

$\endgroup$
4
  • $\begingroup$ Someone edited the question and messed up the elements of matrix A. the actual matrix is [4 2 -5 1; -8 0 9 7; -32 -4 43 18; 24 4 -22 -8]. What happens in this case? $\endgroup$ Commented Feb 7, 2014 at 23:57
  • $\begingroup$ @RyanHannaAL-Kass Please, edit it and make it correct. $\endgroup$
    – egreg
    Commented Feb 7, 2014 at 23:59
  • $\begingroup$ Done. What happens now? $\endgroup$ Commented Feb 8, 2014 at 0:46
  • $\begingroup$ @RyanHannaAL-Kass I'll have a look tomorrow morning. Here's almost 2am. $\endgroup$
    – egreg
    Commented Feb 8, 2014 at 0:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .