Talk:LU decomposition

Algorithm 2 does not appear to me to be an algorithm, but rather a description of the goal of an algorithm. Too Old 17:17, 16 Jul 2004 (UTC)

---

I resumed work on this article. The following sections were ripped nearly verbatim from [[1] (http://mathworld.wolfram.com/LUDecomposition.html)] so I deleted them.

Here is a direct method for decomposing an <math>N \times N<math> matrix <math> \mathbf{A} <math> into the product of a lower triangular matrix <math> \mathbf{L}<math> and an upper triangular matrix <math> \mathbf{U} <math>,

<math> \mathbf{L} \, \mathbf{U} = \mathbf{A} <math>

For a <math>3 \times 3<math> matrix, this becomes:

<math> \begin{bmatrix}

          l_{11} & 0 & 0 \\
          l_{12} & l_{22} & 0 \\
          l_{13} & l_{23} & l_{33} \\
       \end{bmatrix}
       \cdot
       \begin{bmatrix}
          u_{11} & u_{12} & u_{13} \\
          0 & u_{22} & u_{23} \\
          0 & 0 & u_{33} \\
       \end{bmatrix}
       =
       \begin{bmatrix}
          a_{11} & a_{12} & a_{13} \\
          a_{21} & a_{22} & a_{23} \\
          a_{31} & a_{32} & a_{33} \\
       \end{bmatrix}

<math> This gives three types of equations

<math> i < j \qquad l_{i1} u_{1j} + l_{i2} u_{2j} + \dots + l_{ii} u_{ij} = a_{ij} <math>

<math> i = j \qquad l_{i1} u_{1j} + l_{i2} u_{2j} + \dots + l_{ii} u_{jj} = a_{ij} <math>

<math> i > j \qquad l_{i1} u_{1j} + l_{i2} u_{2j} + \dots + l_{ii} u_{jj} = a_{ij} <math>

This gives <math> N^2 <math> equations for <math> N^2 + N <math> unknowns (the decomposition is therefore not unique); the system can be solved using Crout's method.

Given a matrix equation and the LU decomposition of A

<math> \mathbf{A} \mathbf{x} = (\mathbf{L} \mathbf{U}) \mathbf{x} = \mathbf{L} (\mathbf{U} \mathbf{x}) = \mathbf{b},

<math> first solve <math> \mathbf{L} \mathbf{y} = \mathbf{b} <math> for <math> \mathbf{y} <math>. This can be done by forward substitution

<math> y_1 = \frac{b_1}{l_{11}} <math>

<math> y_i = \frac{1}{l_{ii}} \left( b_i - \sum_{j=1}^{i-1} l_{ij} y_{j} \right) <math>

for i=2,...,N. Then solve <math> \mathbf{U} \mathbf{x} = \mathbf{y} <math> for <math> \mathbf{x} <math>. This can be done by back substitution

<math> x_N = \frac{y_N}{u_{NN}} <math>

<math> x_i = \frac{1}{u_{ii}} \left( y_i - \sum_{j = i+1}^{N} u_{ij} x_j \right) <math>

for i=N-1,...,1

This algorithm for solving matrix equations takes O(n²) operations (excluding the LU decomposition) and is therefore much faster than using Gauss algorithm. MathMartin 16:01, 18 Jul 2004 (UTC)

I suggest the present LU decomposition article should be divided into an article which gives a general explanation of what is an LU decomposition and another article on the doolittle method for LU decomposition. The general LU decomposition article would work as an "anchor" for all the LU decomposition algorythms' articles, including the doolittle.

--Maciel 14:32, 14 Aug 2004 (UTC)

I did some work on the article recently but I am not really satisfied with the result. If you think you can improve the article go ahead and do it. But I would only split the article if it got too long, because it is easier to keep the material consistent if kept on one page. If the page grows too big you could always do a split later. MathMartin 14:53, 14 Aug 2004 (UTC)

On the LU decomposition page, what I don't like is that a matrix A is denoted A (italic font) when not in a math formula, and \mathbf{A} (bold font) when in a math formula. This makes things inconsistent. How to fix this, one way or another? I would suggest making everything italic, why on earth would one want a bold matrix? --Olegalexandrov 21:26, 5 Dec 2004 (UTC)