Lecture 13
LU Decomposition as reported by Chris
McAloney
If we're in a situation where we need to solve
the same system -- that
is, with the same
coefficient matrix -- for multiple vectors b1,
b2,
..., bm, then the Gaussian elimination
algorithms presented during
Lectures 11 and
12 become computationally inefficient, since it
is
redundant to perform the row reductions
multiple times. The ideal
situation would be
if we could perform the row reduction once,
and
somehow preserve a record of the row
reduction which would allow us to
compute the
value of x for each of the bi vectors more
efficiently.
The LU decomposition of a
coefficient matrix A, is a pair of
matrices:
L (a lower triangular matrix) and U
(an upper triangular matrix) such
that A =
LU, and thus Ax = (LU)x = L(Ux) = b. Letting y = Ux,
then,
this gives us a pair of triangular
systems which can be solved by
backward (or
forward) substitution: Ly = b and Ux = y. Once L and
U
are computed, then, we can solve the system
for any vector bi with one
application of
forward substitution and one of backward
substitution,
which is significantly more
efficient than applying GE every time.
We
then discussed the algorithm for computing
L and U (which was only a
minor modification
of the GE algorithms) and showed how
permutation
matrices could be used to keep
track of the row swaps made during
the
Gaussian elimination with pivoting
algorithm.
Posted: Tue - October 12, 2004 at 10:07 AM