Next steps

The iterative solution of large linear systems is a vast and difficult subject. A broad yet detailed introduction to the subject, including classical topics such as Jacobi and Gauss–Seidel methods not mentioned in this chapter, is Saad (2003). A more focused introduction to Krylov methods is given in van der Vorst (2003).

The conjugate gradient method was originally intended to be a direct method. Theoretically, the answer is found in $n$ steps if there are $n$ unknowns if the arithmetic is perfect. However, for floating-point arithmetic this result no longer holds. The trouble is that as the method progresses, the succeeding search directions become closer to being dependent, and this causes problems for conditioning and floating-point computation. The method was not successful until it came to be viewed as an iterative method that could be stopped once a reasonable approximation was reached. The method was discovered by Hestenes and Stiefel independently, but they joined forces to publish the widely cited paper Hestenes & Stiefel (1952) as part of an early research program in computing run by what was then called the (US) National Bureau of Standards (now called the National Institute of Standards and Technology). It took until the 1970s for the method to catch on as a computational method (Golub & O'Leary (1989)). The interested reader can visit the SIAM History Project’s articles at http://history.siam.org/hestenes.htm to find an article by Hestenes that recounts the discovery (reprinted from Nash (1990)).

An important instance of matrix-free iteration occurs in using Newton’s method to solve a nonlinear system of equations. The key step is to solve a linear system with the Jacobian matrix, which can be expensive to compute. However, applying the Jacobian to a vector is equivalent to taking a derivative in the direction of that vector, which can be approximated by a single finite difference. This observation leads to the idea of Newton–Krylov methods. A good introduction to this topic is given in Knoll & Keyes (2004).

For those not experienced with preconditioning, it can seem like something of an art. The approach that works best very often depends on the application. Summaries of some approaches can be found in Quarteroni et al. (2007) and Trefethen & Bau (1997).