1

I understand how to do LU factorisation but I'm not sure I'm being very efficient. I first find the row echelon form of A, noting the elementary operations $E_i$ in order.

$$ E_1E_2...E_nA = U $$ then $$ L = E_1^{-1}E_2^{-1}...E_n^{-1} $$

But is this the quickest way for a 4x4 matrix?

I've been given a class problem which (going by every other question) shouldn't take as long as it's taken me. I'd be interested to hear what method you'd be using!

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

Brian
  • 385

1 Answers1

3

We can use Doolittle's Method:

$$\begin{bmatrix} 1 & 0 & 0 &0\\ l_{21} & 1 & 0 &0 \\ l_{31} & l_{32} & 1 &0 \\ l_{41} & l_{42} & l_{43} & 1 \end{bmatrix} \cdot \begin{bmatrix} u_{11} & u_{12} & u_{13} &u_{14}\\ 0 & u_{22} & u_{23} &u_{24} \\ 0 & 0 & u_{33} &u_{34} \\0 & 0 & 0 & u_{44} \end{bmatrix} = \begin{bmatrix} 1 & -2 & -2 & -3 \\ 3 & -9 & 0 & -9 \\ -1 & 2 & 4 & 7 \\ -3 & -6 & 26 & 2 \end{bmatrix}$$

Solving for each of the variables, in the correct order yields:

  • $u_{11} = 1, u_{12} = -2, u_{13} = -2, u_{14} = -3$
  • $l_{21} = 3, u_{22} = -3, ...$
  • $l_{31} = -1, l_{32} = 4, ...$
  • $\ldots $

So, we arrive at:

$$A = \begin{bmatrix} 1 & -2 & -2 & -3 \\ 3 & -9 & 0 & -9 \\ -1 & 2 & 4 & 7 \\ -3 & -6 & 26 & 2 \end{bmatrix} = LU = \begin{bmatrix} 1 & 0 & 0 & 0\\ 3 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ -3 & 4 & -2 & 1\end{bmatrix} \cdot \begin{bmatrix} 1 & -2 & -2 & -3 \\ 0 & -3 & 6 & 0 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

We could have also used Crout's or Choleski's Method for the $LU$ approach. See: what are pivot numbers in LU decomposition? please explain me in an example

Please note that sometimes an LU decomposition is not possible, and sometimes, when it is, we have to resort to using permutation matrices and other approaches.

Community
  • 1
Amzoti
  • 56,093
  • Thank you very much! Doolittle's method certainly proved much quicker. It's certainly not a well taught concept, but your post here and on the link really helped. Much appreciated. – Brian Apr 01 '14 at 17:28
  • Gil Strang explains it very well in the first few lectures of his 18.06 linear algebra course (videos available for free on the MIT open courseware site). – Brad S. Apr 02 '14 at 04:48