Decomposition LU

In Linear algebra, the decomposition LU is a method of decomposition of a matrix in a triangular Matrice lower L (like " Low" , low) and a higher triangular matrix U (like " Up" , high). This decomposition is used in numerical Analyze to solve linear systems of equations.

Definition

Either has a invertible Matrice. The matrix has can be broken up thus

$PA\; =\; L\; U\; \backslash ;$

$A\; =\; P\; L\; U\; \backslash ;$

where P is a Matrice of permutation (in the same way for P ^-1), L is a triangular Matrice lower and U a triangular Matrice higher. Sometimes, the Matrice of passage P can be selected in order to be a Matrice identity. In this case, the decomposition becomes $A\; =\; L\; U.$

Example

That is to say for example the matrix:

$$

\begin{pmatrix} 2 & -1 & 0 \ \ -1 & 2 & -1 \ \ 0 & -1 & 2 \ \ \end{pmatrix}

This matrix is factorized in a product of a lower triangular matrix by a higher triangular matrix in the following way:

$$

\begin{pmatrix} 2 & -1 & 0 \ \ -1 & 2 & -1 \ \ 0 & -1 & 2 \ \ \ end {pmatrix} = \ begin {pmatrix} 1 & 0 & 0 \ \ -1/2 & 1 & 0 \ \ 0 & -2/3 & 1 \ \ \end{pmatrix}.\begin{pmatrix} 2 & -1 & 0 \ \ 0 & 3/2 & -1 \ \ 0 & 0 & 4/3 \ \ \end{pmatrix}

Applications

To solve a system of linear equations

This matric factorization makes it possible to solve linear systems of equations where the coefficients of the unknown factors are the same ones, but with several second different members. That is to say to determine the vector of unknown factors {X} associated to the second member {B}:

$A\; \backslash \; begin\; \{Bmatrix\}\; X\; \backslash \; end\; \{Bmatrix\}\; =\; \backslash \; begin\; \{Bmatrix\}\; B\; \backslash \; end\; \{Bmatrix\}$

This problem is thus equivalent to the resolution of

$L\; U\; \backslash \; begin\; \{Bmatrix\}\; X\; \backslash \; end\; \{Bmatrix\}\; =\; \backslash \; begin\; \{Bmatrix\}\; B\; \backslash \; end\; \{Bmatrix\}$

or

$L\; \backslash \; begin\; \{Bmatrix\}\; U.x\; \backslash \; end\; \{Bmatrix\}\; =\; \backslash \; begin\; \{Bmatrix\}\; B\; \backslash \; end\; \{Bmatrix\}$ which one can put, by posing $\backslash \; begin\; \{Bmatrix\}\; U.x\; \backslash \; end\; \{Bmatrix\}\; =\; \backslash \; begin\; \{Bmatrix\}\; there\; \backslash \; end\; \{Bmatrix\}$ in the form: $L\; \backslash \; begin\; \{Bmatrix\}\; there\; \backslash \; end\; \{Bmatrix\}\; =\; \backslash \; begin\; \{Bmatrix\}\; B\; \backslash \; end\; \{Bmatrix\}$

One finds the components of there one by one by elementary substitutions, since initially $y\_1\; =\; \backslash \; frac\; \{b\_1\}\; \{L\_\; \{11\}\}$, then $y\_2\; =\; \backslash \; frac\; \{b\_2-L\_\; \{21\}\; .y\_1\}\; \{L\_\; \{22\}\}$, etc

This stage is called descent , since one solves the system while going down from $y\_1$ with $y\_n$. It remains to calculate the components of the vector {X} by solving the higher triangular system:

$U.\; \backslash \; begin\; \{Bmatrix\}\; X\; \backslash \; end\; \{Bmatrix\}\; =\; \backslash \; begin\; \{Bmatrix\}\; there\; \backslash \; end\; \{Bmatrix\}$

what is done in a similar way, but by calculating $x\_n$

$x\_n\; initially\; =\; \backslash \; frac\; \{y\_n\}\; \{U\_\; \{N\}\}$, etc while going up (stage known as of gone up ).

Notation. - the triangular matrices L and U could have been reversed easily by using the elimination of Gauss-Jordan. But if one counts simply the number of operations that represents for a system with N equations, one will find that the algorithmic Complexité calculation of the matrices opposite is higher, so that if one wants to solve this system for various B , it is more interesting to carry out the decomposition LU once for all and to carry out substitutions of descent-increase rather for different the B than to use the elimination of Gauss-Jordan very often. Thus, in the majority of the publications of numerical Analyze, when the matrix has was factorized in form LU or Cholesky (cf will infra, § the symmetrical case ), one writes by abuse $b\; =\; A^\; \{-\; 1\}\; x$ to mean that the calculation of B can be done by this method of descent-increase. It is implied that it is absolutely not not question of using the algorithm by calculating the matrix reverses $A^\; \{-\; 1\}$ of has, which would be unnecessarily expensive in computing times.

To reverse a matrix

The matrices L and U can be used to determine the reverse of a matrix. The computer programs which implement this type of calculation, generally use this method.

Existence

The decomposition LU exists if and only if all under principal matrices of order 1 with N -1 are invertible.

Calculation of the decomposition

Principal idea

The decomposition LU is a particular form of elimination of Jordan Gauss. One transforms the matrix has in a higher triangular matrix U by eliminating the elements under the diagonal. Eliminations are made column after column, while starting with the left, by multiplying has by the left with a lower triangular matrix.

Algorithm

Being given a matrix of dimension $N\; \backslash \; times\; N$

$$

A= (a_ {N, N}) \; one defines

$A^\; \{(0)\}\; :\; =\; \backslash \; has;$

and the iterations are done for N = 1,…, N-1 in the following way.

On N ième column of has ^{( n-1 )} , one eliminates the elements under the diagonal while adding to the I ème line from this matrix, N ième line multiplied by

$l\_\; \{I,\; N\}:\; =\; -\; \backslash \; frac\; \{a\_\; \{I,\; N\}\; ^\; \{(n-1)\}\}\; \{a\_\; \{N,\; N\}\; ^\; \{(n-1)\}\}$

for $i\; =\; n+1,\; \backslash \; ldots,\; N$. This can be made while multiplying by the left has ^{( n-1 )} with the lower triangular matrix

$$

L_n = \begin{pmatrix} 1 & & & & & 0 \ \ & \ ddots & & & & \ \ & & 1 & & & \ \ & & l_ {n+1, N} & \ ddots & & \ \ & & \ vdots & & \ ddots & \ \ 0 & & l_ {NR, N} & & & 1 \ \ \end{pmatrix}.

$A^\; \{(N)\}\; :\; =\; L\_n\; A^\; \{(n-1)\}.\; \backslash ;$

After N-1 iterations, we eliminated all the elements under the diagonal, consequently, we have a higher triangular matrix now has ^{( N-1 )} .

We obtain the decomposition

$$

With = L_ {1} ^ {- 1} L_ {1} A^ {(0)}

L_ {1} ^ {- 1} A^ {(1)} L_ {1} ^ {- 1} L_ {2} ^ {- 1} L_ {2} A^ {(1)}

L_ {1} ^ {- 1} L_ {2} ^ {- 1} A^ {(2)} = \ ldots = L_ {1} ^ {- 1} \ ldots L_ {N-1} ^ {- 1} A^ {(N-1)}.

Let us note U the higher triangular matrix has ^{( N-1 )} and $L=L\_\; \{1\}\; ^\; \{-\; 1\}\; \backslash \; ldots\; L\_\; \{N-1\}\; ^\; \{-\; 1\}$. Knowing that the reverse of a lower triangular matrix is also a lower triangular matrix and that the product of 2 lower triangular matrices is still a lower triangular matrix, L is thus a lower triangular matrix. $A=LU$ is obtained.

Within sight of the algorithm, it is necessary that $a\_\; \{N,\; N\}\; ^\; \{(n-1)\}\backslash \; not=0$ with each iteration (see the definition of $l\_\; \{I,\; N\}$). If, during calculation, this case of figure came to occur, it is necessary to invert N ième line with another being able to continue (it is always possible to find an element not no one on the column which poses problem because the matrix is invertible). This is why the decomposition LU is generally written $P^\; \{-\; 1\}\; has\; =\; L\; U$.

The symmetrical case

• If the matrix has is a symmetrical Matrice, there exists a decomposition known as factorization of Crout

$A\; =\; L.D.\; \{\}\; ^tL$

where L is a lower triangular matrix whose diagonal includes/understands only of the 1, $\{\}\; ^tL$ is the transposed of L , and D is a diagonal matrix.

• If the matrix has is symmetrical definite positive, there exists a simpler decomposition, given by the method of Cholesky

$A\; =\; L.\; \{\}\; ^tL$

where L is a triangular matrix lower than positive diagonal and $\{\}\; ^tL$ is the transposed of L .

Random links:

Fenotiacina | Two English and the continent | Jean-Charles Trouabal | Ryszard Kapuściński | Franck Marshal | Bad Ischl | Procopius_de_Gaza

© 2007-2008 speedlook.com; article text available under the terms of GFDL, from fr.wikipedia.org