Graphics Programs Reference
In-Depth Information
∗
2.7
Iterative Methods
Introduction
Sofar, wehave discussed only direct methods of solution. The common characteristic
of thesemethods isthat they compute the solutionwith a finite number of operations.
Moreover, if the computerwerecapable of infinite precision (no roundoff errors), the
solutionwouldbeexact.
Iterative, or
indirect methods
,start with an initial guess of the solution
x
and
thenrepeatedly improve the solutionuntil the change in
x
becomes negligible.Since
the required number of iterationscan be very large, the indirect methods are, in
general, slower than their direct counterparts. However, iterative methods dohave
the following advantages that make themattractivefor certain problems:
1.
It isfeasible to storeonly the nonzero elements of the coefficient matrix. This
makes it possible to deal with very large matrices that aresparse, but not neces-
sarily banded. In many problems, there is no need to store the coefficient matrix
at all.
2.
Iterative procedures are self-correcting, meaning that roundoff errors(or even
arithmetic mistakes) in one iterativecycle arecorrectedinsubsequentcycles.
A serious drawback of iterative methods isthat theydo not alwaysconvergetothe
solution. It can be shown thatconvergence is guaranteed onlyif the coefficient matrix
is diagonallydominant. The initial guess for
x
plays no role in determining whether
convergence takes place—if the procedureconverges for onestarting vector, it would
dosofor any starting vector. The initial guess affects only the number of iterations
that are required for convergence.
Gauss-Seidel Method
=
The equations
Ax
b
are in scalar notation
n
A
i j
x
j
=
b
i
,
i
=
1
,
2
,...,
n
j
=
1
Extracting the term containing
x
i
from the summation sign yields
n
A
ii
x
i
+
A
i j
x
j
=
b
i
,
i
=
1
,
2
,...,
n
j
=
1
j
=
i
Search WWH ::
Custom Search