TABLE OF CONTENTS Iterative algorithms for solving Ax = b are used when methods such as Gaussian elimination require too much time or too much space. Methods such as Gaussian elimination, which compute the exact answers after a finite number of steps (in the absence of roundoff!), are called direct methods. In contrast to direct methods, iterative methods generally do not produce the exact answer after a finite number of steps but decrease the error by some fraction after each step. Iteration ceases when the error is less than a user-supplied threshold. The final error depends on how many iterations one does as well as on properties of the method and the linear system. Our overall goal is to develop methods that decrease the error by a large amount at each iteration and do as little work per iteration as possible.
Much of the activity in this field involves exploiting the underlying mathematical or physical problem that gives rise to the linear system in order to design better iterative methods. The underlying problems are often finite difference or finite element models of physical systems, usually involving a differential equation. There are many kinds of physical systems, differential equations, and finite difference and finite element models, and so many methods. We cannot hope to cover all or even most interesting situations, so we will limit ourselves to a model problem, the standard finite difference approximation to Poisson's equation on a square. Poisson's equation and its close relation, Laplace's...
