3.6 Iterative Methods for Solving Linear Systems

The methods discussed so far for the solution of simultaneous systems of linear equations have been direct, which required a finite number of arithmetic operations. The elimination methods for solving such systems usually yield sufficiently accurate solutions for approximately 20 to 25 simultaneous equations, where most of the unknowns are present in all of the equations. When the coefficients matrix is sparse (has many zeros), a considerably large number of equations can be handled by the elimination methods. But these methods are generally impractical when many hundreds or thousands of equations must be solved simultaneously.

There are, however, several methods which can be used to solve large numbers of simultaneous equations. These methods are called iteative methods by which an approximation to the solution of a system of linear equations may be obtained. The iterative methods are used most often for large sparse systems of linear equations and efficient in terms of computer storage and time requirements. Systems of this type arise frequently in the numerical solution of boundary value problems and partial differential equations. Unlike the direct methods, iterative methods may not always yield a solution, even if the coefficients matrix is nonsingular.

The iterative methods to solve the system of linear equations

start with an initial approximation x ⁽⁰⁾ ? ? to the solution x of linear system (3.47), and generate a sequence of vectors that converge to x. Most of these iterative methods involve...