12.1 Linear One-Step Stationary Schemes

The theme of this chapter is iterative solution of the linear system

where A is a d d real nonsingular matrix and b ? . The most general iterative method is a rule that for every k = 0, 1, and x ^[0] , x ^[1], , x ^{[ k ]} ? generates a new vector x ^{[ k +1]} ? . In other words, it is a family of functions such that

and

The most fundamental question with regard to the scheme (12.2) is about its convergence. Firstly, does it converge for every starting value x ^[0] ? ? ^[1] Secondly, provided that it converges, is the limit bound to be the true solution of the linear system (12.1)?

Unless (12.2) always converges to the true solution the scheme is, obviously, unsuitable. However, not all convergent iterative methods are equally good. Our main consideration being to economize on computational cost, we must consider how fast convergence takes place and what is the expense of each iteration.

An iterative scheme (12.2) is said to be linear if each h _k is linear in all its arguments. It is m-step if h _k depends solely on x ^{[ k ? m +1]}, x ^{[ k ? m +2]}, , x ^{[ k ]}, k = m ? 1, m, Finally,...