Iterative Methods for Linear Equations
We introduce the basic concepts and components of
iterative methods for
the solution of a system of linear equations , Consider the solution of linear
equation system
Ax = b, A ∈ Rn×n, b ∈ span(A)
(4)
Assume that the null space of A has no nonzero vector. Denote by
the
unique solution. Define
r = r(x) = b - Ax,
as the residual at x with respect to the system (A, b). The residual at
the
exact solution is zero .
The fixed-point iteration
We develop an iterative method as follows. First, a system of linear equations
of (4) can be written in many mathematically equivalent forms , we consider a
particular form involving the residual in order to make corrections,
, B is nonsingular:
(5)
We refer to this form as the form of fixed-point equations. We shall see shortly
the role of matrix B.
Next, starting with an initial guess 
, we obtain iteratively new guesses,
The iteration may or may converge, depending on the
selection of matrix B.
The error in 
is
. The iteration converges to the true solution,
if and only if
.
Convergence analysis
In convergence analysis, we obtain the error propagation equations first from
(5) and (6)
The matrix (I - BA) is the error propagation matrix, it
relates the errors in
two successive iteration steps, and hence relates the error at every step k to
the initial one, 
.
It is easy to check that the necessary and sufficient condition for the errors
to converge to zero with arbitrary initial guess is
where 
denotes the spectrum radius of matrix M. The
smaller 
is, the faster the convergence. The extreme case is
BA) = 0, which means B = A-1 and we are brought back to where we start.
We are left to consider the the remaining case
In this case, matrix B may be viewed as the inverse of a portion of the matrix
A as we shall see shortly.
A design approach: matrix splittings
We choose the matrix B in the fixed-point iteration to satisfy the convergence
criterion (8). Write A in a split form
A = M - N, M is nonsingular.
(9)
We refer to matrix M the splitting matrix. Then, A = M(I - M-1N). Let
B = M-1. Then, (I - BA) = M-1N. The convergence criterion (8) becomes
the following splitting criterion
The error propagation equation can be rewritten in terms of the split matrices
The iteration procedure (6) takes the following specific form,
We note that computing the right hand side 
involves matrixvector
multiplication and vector addition, the computation of
then involves
the solution of 
. In splitting, we choose M so that the
system can be solved easily .
Iterations Based on Diagonal-Triangular Splitting
Diagonal systems and triangular systems are easy to solve. Many iteration
methods are based on the diagonal-triangular split form of A:
A = D - L - U, (13)
where D is diagonal (not necessarily equal to the diagonal portion of A) and
nonsingular, and L is strict lower triangular (
). In particular, D - L
may be the lower portion of A.
•
Jacobi Iteration: M = D = diag(A).
Sufficient condition for convergence: A is diagonally dominant.
•
Gauss-Seidel(GS) Iteration: M = D - L = tril(A).
Sufficient condition for convergence: A is diagonally dominant.
•
Successive Over-Relaxation(SOR): M = ω-1(D - ωL), ω is a
scalar.
When ω = 1, SOR recovers the GS iteration.
Sufficient condition for convergence : if A is symmetric, positive definite ,
the SOR iteration converges for any ω ∈ (0, 2). There are many studies
on determining the optimal parameter ω.
•
Symmetric SOR(SSOR):
It invokes two successive triangular systems solutions per iteration. Try
to write down the computational procedure.
Is the iteration matrix symmetric when A is spd ?
Remarks.
In the Jacobi
iteration, all elements are updated at the same time and
the computation can be done in parallel in a trivial way.
In the GS/SOR iteration, the update of the
(i+1)th element depends on
the update of the i-th element, as in the substitution procedure . There
still exists some extent of parallelism in the computation.
The Jacobi iteration and the GS iteration
cost the same in flops per
iteration. Try to find out which one converges faster for a given diagonally
dominant matrix A.
Matrix-vector norms are used in bounding
in the convergence
analysis.
The above iterative methods are stationary, i.e., the error propagation
matrix in a method does not change over the iteration procedure. There
are many kinds of non-stationary methods that are found more effective.
In particular, the conjugate gradient method and its variants are used
more often.
| Prev | Next |