Linear Algebra with Applications, 10th Edition

7.8 Iterative Methods

In this section, we study iterative methods for solving a linear system $A\mathbf{x}=\mathbf{b}$. Iterative methods start out with an initial approximation ${\mathbf{x}}^{\left(0\right)}$ to the solution and go through a fixed procedure to obtain a better approximation, ${\mathbf{x}}^{\left(1\right)}$. The same procedure is then repeated on ${\mathbf{x}}^{\left(1\right)}$ to obtain an improved approximation, ${\mathbf{x}}^{\left(2\right)}$, and so on. The iterations terminate when a desired accuracy has been achieved.

Iterative methods are most useful in solving large sparse systems. Such systems occur, for example, in the solution of boundary value problems for partial differential equations. The number of flops necessary to solve an $n\times n$ linear system using iterative methods is proportional to $n^2$, whereas the amount necessary using Gaussian elimination ...