5.2 Direct Methods
93
All of the elements except those in the first row differ from those in the original
matrix A. As the elements of the original matrix will never be needed again,
it is efficient to store the modified elements in place of the original ones.
(In the rare case requiring that the original matrix be saved, a copy can be
created prior to starting the elimination procedure.)
This portion of the algorithm just described is called forward elimination.
The elements on the right hand side of the equation, Qi, are also modified in
this procedure.
The upper triangular system of equations resulting from forward elimination is easily solved. The last equation contains only one variable, 4, and is
readily solved:
Q n
& = - .
Ann
The next to last equation contains only
and 4, and, once 4, is known,
it can be solved for
Proceeding upward in this manner, each equation
is solved in turn; the ith equation yields 4i:
The right hand side is calculable because all of the dk appearing in the
sum have already been evaluated. In this way, all of the variables may be
computed. The part of the Gauss elimination algorithm which starts with
the triangular matrix and computes the unknowns is called back substitution.
It is not difficult to show that, for large n , the number of operations
required to solve a linear system of n equations by Gauss elimination is proportional to n 3 / 3 . The bulk of this effort is in the forward elimination phase;
the back substitution requires only n2/2 arithmetic operations and is much
less costly than the forward elimination. Gauss elimination is thus expensive
but, for full matrices, it is as good as any method available. The high cost
of Gauss elimination provides incentive to search for more efficient special
solvers for matrices such as the sparse ones arising from the discretization of
differential equations.
For large systems that are not sparse, Gauss elimination is susceptible
to accumulation of errors (see Golub and van Loan, 1990) which makes it
unreliable if not modified. The addition of pivoting or interchange of rows
in order to make the pivot elements (the diagonal elements that appear in
the denominators) as large as possible, keeps the error growth in check. Fortunately, for sparse matrices, error accumulation is rarely a problem so this
issue is not important here.
Gauss elimination does not vectorize or parallelize well and is rarely used
without modification in CFD problems.
93
All of the elements except those in the first row differ from those in the original
matrix A. As the elements of the original matrix will never be needed again,
it is efficient to store the modified elements in place of the original ones.
(In the rare case requiring that the original matrix be saved, a copy can be
created prior to starting the elimination procedure.)
This portion of the algorithm just described is called forward elimination.
The elements on the right hand side of the equation, Qi, are also modified in
this procedure.
The upper triangular system of equations resulting from forward elimination is easily solved. The last equation contains only one variable, 4, and is
readily solved:
Q n
& = - .
Ann
The next to last equation contains only
and 4, and, once 4, is known,
it can be solved for
Proceeding upward in this manner, each equation
is solved in turn; the ith equation yields 4i:
The right hand side is calculable because all of the dk appearing in the
sum have already been evaluated. In this way, all of the variables may be
computed. The part of the Gauss elimination algorithm which starts with
the triangular matrix and computes the unknowns is called back substitution.
It is not difficult to show that, for large n , the number of operations
required to solve a linear system of n equations by Gauss elimination is proportional to n 3 / 3 . The bulk of this effort is in the forward elimination phase;
the back substitution requires only n2/2 arithmetic operations and is much
less costly than the forward elimination. Gauss elimination is thus expensive
but, for full matrices, it is as good as any method available. The high cost
of Gauss elimination provides incentive to search for more efficient special
solvers for matrices such as the sparse ones arising from the discretization of
differential equations.
For large systems that are not sparse, Gauss elimination is susceptible
to accumulation of errors (see Golub and van Loan, 1990) which makes it
unreliable if not modified. The addition of pivoting or interchange of rows
in order to make the pivot elements (the diagonal elements that appear in
the denominators) as large as possible, keeps the error growth in check. Fortunately, for sparse matrices, error accumulation is rarely a problem so this
issue is not important here.
Gauss elimination does not vectorize or parallelize well and is rarely used
without modification in CFD problems.