TABLE OF CONTENTS In this section we will talk about the most basic iterative methods:
Jacobi's,Gauss-Seidel,successive overrelaxation (SOR(?)),Chebyshev acceleration with symmetric successive overrelaxation(SSOR(?)).
These methods are also discussed and their implementations are provided at NETLIB/templates.
Given x 0, these methods generate a sequence x m converging to the solution A ?1 b of Ax = b, where x m+1 is cheap to compute from x m.
A splitting of A is a decomposition A = M ? K, with M nonsingular.
A splitting yields an iterative method as follows: Ax = Mx ? Kx = b implies Mx = Kx + b or x = M ?1 Kx + M ?1 b ? Rx + c. So we can take x m+1 = Rx m + c as our iterative method. Let us see when it converges.
Let be any operator norm ( 
). If R < 1, then x m+1 = Rx m + c converges for any x 0.
| Proof | Subtract x = Rx+ c from x m+1 = Rx m+ c to get x m+1 ? x = R( x m ? x). Thus x m+1 ? x ? R x m ? x ? |
