94
5. Solution of Linear Equation Systems
5.2.2 LU Decomposition
A number of variations on Gauss elimination have been proposed. Most are
of little interest here. One variant of value to CFD is LU decomposition. It
is presented without derivation.
We have seen that, in Gauss elimination, forward elimination reduces a
full matrix to an upper triangular one. This process can be carried out in a
more formal manner by multiplying the original matrix A by a lower triangular matrix. By itself, this is of little interest but, as the inverse of a lower
triangular matrix is also lower triangular, this result shows that any matrix
A, subject to some limitations that can be ignored here, can be factored into
the product of lower (L) and upper (U) triangular matrices:
To make the factorization unique, we require that the diagonal elements of
L, Lii, all be unity; alternatively, one could require the diagonal elements of
U to be unity.
What makes this factorization useful is that it is easily constructed. The
upper triangular matrix U is precisely the one produced by the forward phase
of Gauss elimination. Furthermore, the elements of L are the multiplicative
factors (e.g. Aji/Aii) used in the elimination process. This allows the factorization to be constructed by a minor modification of Gauss elimination.
Furthermore, the elements of L and U can be stored where the elements of
A were.
The existence of this factorization allows the solution of the system of
equations (5.1) in two stages. With the definition:
U f . p = Y ,
(5.7)
the system of equations (5.1) becomes:
The latter set of equations can be solved by a variation of the method used
in the backward substitution phase of Gauss elimination in which one starts
from the top rather than the bottom of the system. Once Eq. (5.8) has been
solved for Y , Eq. (5.7), which is identical to the triangular system solved in
the back substitution phase of Gauss elimination, can be solved for 4.
The advantage of LU factorization over Gauss elimination is that the
factorization can be performed without knowing the vector Q. As a result,
if many systems involving the same matrix are to be solved, considerable
savings can be obtained by performing the factorization first; the systems
can then be solved as required. As we shall see below, variations on LU
factorization are the basis of some of the better iterative methods of solving
systems of linear equations; this is the principal reason for introducing it
here.
5. Solution of Linear Equation Systems
5.2.2 LU Decomposition
A number of variations on Gauss elimination have been proposed. Most are
of little interest here. One variant of value to CFD is LU decomposition. It
is presented without derivation.
We have seen that, in Gauss elimination, forward elimination reduces a
full matrix to an upper triangular one. This process can be carried out in a
more formal manner by multiplying the original matrix A by a lower triangular matrix. By itself, this is of little interest but, as the inverse of a lower
triangular matrix is also lower triangular, this result shows that any matrix
A, subject to some limitations that can be ignored here, can be factored into
the product of lower (L) and upper (U) triangular matrices:
To make the factorization unique, we require that the diagonal elements of
L, Lii, all be unity; alternatively, one could require the diagonal elements of
U to be unity.
What makes this factorization useful is that it is easily constructed. The
upper triangular matrix U is precisely the one produced by the forward phase
of Gauss elimination. Furthermore, the elements of L are the multiplicative
factors (e.g. Aji/Aii) used in the elimination process. This allows the factorization to be constructed by a minor modification of Gauss elimination.
Furthermore, the elements of L and U can be stored where the elements of
A were.
The existence of this factorization allows the solution of the system of
equations (5.1) in two stages. With the definition:
U f . p = Y ,
(5.7)
the system of equations (5.1) becomes:
The latter set of equations can be solved by a variation of the method used
in the backward substitution phase of Gauss elimination in which one starts
from the top rather than the bottom of the system. Once Eq. (5.8) has been
solved for Y , Eq. (5.7), which is identical to the triangular system solved in
the back substitution phase of Gauss elimination, can be solved for 4.
The advantage of LU factorization over Gauss elimination is that the
factorization can be performed without knowing the vector Q. As a result,
if many systems involving the same matrix are to be solved, considerable
savings can be obtained by performing the factorization first; the systems
can then be solved as required. As we shall see below, variations on LU
factorization are the basis of some of the better iterative methods of solving
systems of linear equations; this is the principal reason for introducing it
here.