Talk:LU decomposition

From Wikipedia, the free encyclopedia

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]] so I deleted them.

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

\mathbf{L} \, \mathbf{U} = \mathbf{A}

For a 3 \times 3 matrix, this becomes:

\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}

This gives three types of equations

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

This gives N2 equations for N2 + N 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

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

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

y_1 = \frac{b_1}{l_{11}}
y_i = \frac{1}{l_{ii}} \left( b_i - \sum_{j=1}^{i-1} l_{ij} y_{j} \right)

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

x_N = \frac{y_N}{u_{NN}}
x_i = \frac{1}{u_{ii}} \left( y_i - \sum_{j = i+1}^{N} u_{ij} x_j \right)

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

This algorithm for solving matrix equations takes O(n2) 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)

[edit] R in Existence and Uniqueness

In the Existence and Uniqueness section, what is the matrix R? It looks like it's referring to something defined earlier, that is no longer there. --Ben Kovitz 20:16, 4 September 2005 (UTC)

R should be U. In some languages, including Dutch and German, LU is sometimes called LR (R for right); this probably confused whoever wrote that sentence (which may well have been me). Now fixed, thanks for catching this. -- Jitse Niesen (talk) 21:29, 4 September 2005 (UTC)

[edit] Pivoting Explained? Order of the calcuation?

There is mention of PLU and PLUQ decompositions, but no explaination of their use. Should someone mention that the purpose is to have P'AQ'=LU giving P'AQ' with pivots in Gaussian elimination that lead to the least error? (Those ' are transposes, of course.) 149.43.x.x 11:10, 29 September 2006 (UTC)

[edit] Computational complexity

Intro. to Algorithms by Cormen et al. says LU deocmposition is Θ(n3) for (I think) an n×n matrix. Did I get that right. If so, it should appear prominently in this article. —Ben FrantzDale 17:18, 1 February 2007 (UTC)

That's right. More precisely, Golub & van Loan (reference as in Givens rotation) say that you need 2n3 / 3 operations, neglecting lower-order terms. This remains the case if you're doing partial pivoting, but full pivoting is more expensive. Please do put it in. -- Jitse Niesen (talk) 01:44, 2 February 2007 (UTC)
I added a bit along these lines. Perhaps not prominently, as you proposed; feel free to edit (as always). -- Jitse Niesen (talk) 07:24, 11 March 2007 (UTC)
Retrieved from "http://en.wikipedia.org../../../l/u/_/Talk%7ELU_decomposition_84e8.html"