Solutions to Comprehensive : Numerical Analysis (30
points). Autumn 1993
Problem 1 (16 points). Iterative Solution of Linear Equations
This question concerns the solution of systems of linear equations in the form
where A is a rn x m matrix and x and b are vectors of length m.
(a) Describe the simplest form of iterative improvement
(also known as residual correction) to solve
( 1 ) . Describe, and briefly explain, the effect of machine precision on this
algorithm .
SOLUTION :
Given an approximation xm to the solution x of (I), the residual rm is defined
by
Iterative improvement generates the sequence! of approximations
where
is the computed solution of
For such an ite ration it is important to obtain accurate
dues for rm relative to the precision
used in the remainder of the calculation . The reason is simply that otherwise
the errors in
may
be comparable with the errors in the original calculation.
(b) Given a matrix C which approximates the inverse of A,
consider the fol lowing general residual
correction method for the solution of (1):
State the precise condition under which this iteration converges; prove your
assertion.
SOLUTION: The iteration converges provided that the spectral radius of the
matrix I - CA is less
than one. To prove this note that the iteration gives
Hence the error
satisfies
It is well-known that it is necessary and sufficient for the spectral radius of
I - CA to be less than
one for the iterates
to converge to zero , independent of the choice of initial vector.
(c) Given that A may be written as A = L+ D + U where L
and U are lower and upper triangular
respectively and D is diagonal, define the Jacobi and Gauss-Siedel iterations
for the solution of (1).
SOLUTION: We have
The Jacobi iteration is to generate xm according to
This also shows that
and the induction is complete. Letting
gives the desired
result.
(c) Using part (b) show that Newton iteration converges to
a root a of (2) provided that f is twice
continuously differentiable and
and the initial guess is sufficiently close to
SOLUTION: We can write Newton iteration in the form of (b) with
Thus
Thus it follows that
and hence there is an interval [a, b], including
and
such that
The result follows.
