# LU decomposition

(Difference between revisions)
 Revision as of 06:22, 3 October 2005 (view source)Zxaar (Talk | contribs)← Older edit Revision as of 20:42, 15 December 2005 (view source)Tsaad (Talk | contribs) (towards a uniform notation for linear systems : A*Phi = B)Newer edit → Line 1: Line 1: == LU Solvers == == LU Solvers == - For the system of equations '''Ax=b'''.
+ For the system of equations $A\cdot\phi=B$.
The solvers based on factorization are widely popular. The factorization of a non singular matrix '''A''' in two matrices '''L''' and '''U''', called lower and upper matrices, leads to a direct procedure for the evaluation of the inverse of the matrix. Thus making it possible to calculate the solution vector with given source vector. The solvers based on factorization are widely popular. The factorization of a non singular matrix '''A''' in two matrices '''L''' and '''U''', called lower and upper matrices, leads to a direct procedure for the evaluation of the inverse of the matrix. Thus making it possible to calculate the solution vector with given source vector. It now remains a two step process: a forward substitution followed by a backward substitution. It now remains a two step process: a forward substitution followed by a backward substitution. Line 7: Line 7: :  Calculate '''LU''' factors of '''A''' :  Calculate '''LU''' factors of '''A''' - :: '''Ax = (LU)x = L(Ux) = Ly = b''' + ::$A\cdot \phi = (LU)\cdot \phi = L(U\cdot\phi)=LY=B$ - :  Solve '''Ly = b''' by forward substitution + :  Solve $LY=B$ by forward substitution - :: '''y = L-1b''' + :: Y = L^{-1} B - :  Solve '''Ux=y''' by backward substitution + :  Solve $U\phi =Y$ by backward substitution - :: '''x = U-1y''' + :: \phi = U^{-1}Y + {{stub}} ---- ----

## LU Solvers

For the system of equations $A\cdot\phi=B$.
The solvers based on factorization are widely popular. The factorization of a non singular matrix A in two matrices L and U, called lower and upper matrices, leads to a direct procedure for the evaluation of the inverse of the matrix. Thus making it possible to calculate the solution vector with given source vector. It now remains a two step process: a forward substitution followed by a backward substitution.

## Algorithm

Calculate LU factors of A
$A\cdot \phi = (LU)\cdot \phi = L(U\cdot\phi)=LY=B$
Solve $LY=B$ by forward substitution
$Y = L^{-1} B$
Solve $U\phi =Y$ by backward substitution
$\phi = U^{-1}Y$