** Next:** 2.2.4 Recursion Method
**Up:** 2.2 Exact Methods
** Previous:** 2.2.2 Householder Transformation

##

2.2.3 LU Decomposition

Task: Solve a linear system

Method (Banachiewicz, Cholesky and Crout):
Factorize a matrix into two triangular matrices
(ower) and
(pper):

with

When this is done, write
as

such that we have the two simpler systems of equations

and

Since
and
are triangular
these equations are easy to solve.

*Forward substitution*:

*Back substitution*:

*But first: find the matrices
and
!*

Write
as

These are equations but unknowns
.

Choose
.
Also, due to the triangular structure of
and
we may
write

Crout's procedure:

**Side result:** *Determinant*

__EXAMPLE:__
Let

(Crout)

and thus

At each step the required elements
, are already available.

**Advantage** of LU decomposition:

The vector has not been touched.
Therefore we may use the factors
and
of a given matrix
with different
vectors .

To find the **Inverse**
:

Solve
, with the
unit vectors ; combine the column vectors
to find
.

** Next:** 2.2.4 Recursion Method
**Up:** 2.2 Exact Methods
** Previous:** 2.2.2 Householder Transformation
* Franz J. Vesely Oct 2005*

See also: "Computational Physics - An Introduction," Kluwer-Plenum 2001