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