27 julio 2010

LU Decomposition

In linear algebra, the LU decomposition is a matrix decomposition which writes a matrix as the product of a lower triangular matrixpermutation matrix as well. This decomposition is used in numerical analysis to solve systems of linear equations or calculate the determinant and an upper triangular matrix. The product sometimes includes a  permutation matrix as well. This decomposition is used in numerical analysis to solve systems of linear equations or calculate the determinante.

Let A be a square matrix. An LU decomposition is a decomposition of the form
A = LU, \,
where L and U are lower and upper triangular matrices (of the same size), respectively. This means that L has only zeros above the diagonal and U has only zeros below the diagonal. For a 3 \times 3 matrix, this becomes:
\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix} = \begin{bmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \\ \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \\ \end{bmatrix}.

The general equation to modify the terms 


• - factor * pivot + position to change



So  if Ax = b, then LUx = b, thus
  Ax = LUx = b

EXAMPLE

\begin{bmatrix} 4 & 3 \\ 6 & 3 \\ \end{bmatrix} = \begin{bmatrix} l_{11} & 0 \\ l_{21} & l_{22} \\ \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \\ \end{bmatrix}.
One way of finding the LU decomposition of this simple matrix would be to simply solve the linear equations by inspection. You know that:

l_{11} \cdot u_{11} + 0 \cdot 0 = 4
l_{11} \cdot u_{12} + 0 \cdot u_{22} = 3
l_{21}\cdot u_{11} + l_{22} \cdot 0 = 6
l_{21}\cdot u_{12} + l_{22} \cdot u_{22} = 3.
Such a system of equations is underdetermined. In this case any two non-zero elements of L and ULU matrices. For example, we can require the lower triangular matrix L matrices are parameters of the solution and can be set arbitrarily to any non-zero value. Therefore to find the unique LU decomposition, it is necessary to put some restriction on to be a unit one (i.e. set all the entries of its main diagonal to ones). Then the system of equations has the following solution: and 
l21 = 1.5
u11 = 4
u12 = 3
u22 = − 1.5.
Substituting these values into the LU decomposition above:
\begin{bmatrix} 4 & 3 \\ 6 & 3 \\ \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \\ \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \\ \end{bmatrix}.

Publicado por en
Etiquetas:

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)