In class recently we have talked about various methods such as LU factorization and Cholesky factorization that allow us to solves equations of the form Ax = b. These systems of linear equations arise in domains as varied as biology and engineering to finance. Newton’s method is a common application that requires solving such equations many times.

The problem with these factorization methods like LU factorizations is that they are of order n cubed. Thus as the system of equations begin solved grows larger, these calculations can become prohibitively expensive. In some applications, systems of partial differential equations composed of hundreds of thousands of individual equations arise. This is the domain of supercomputers and scientific computing. However, even the most powerful computers in the world can choke on problems of this scale. Hence the need for approximate solutions using iterative methods.

Iterative methods in contrast with direct methods try to solve matrices in small increments rather than in one shot. They produce a series of solutions to Ax = b. Ideally these solutions should converge to the actual solution and the algorithm can be stopped when sufficient precision has been achieved. Typically an initial value x⁽⁰⁾ is selected arbitrarily and a matrix Q is selected. The choice of the matrix Q is based on the choice the iterative algorithm. In the Richardson iteration, the identity matrix is used for Q. Jacobi iteration uses the diagonal of A to be Q. Then successive approximations to x^(k) can be generated recursively from the equation below:

Methods of the form above are called stationary iterative methods because the operations performed are the same regardless of iteration number. However newer non-stationary methods have been developed that change the value of the coefficients based on iteration number. These can allow for much faster convergence.

Iterative methods are especially valuable when working with sparse matrices composed largely of zeros. With sparse matrices direct methods can waste many steps doing pointless operations with zeros. The conjugate gradient method is a popular choice for these systems.

The appropriate iterative method and sufficient computing power allow scientists and engineers to tackle many problems which are tractable using analytical methods. These are essential in many fields where systems of partial differential equations arise from fluid flow simulations to protein synthesis problems. Iterative methods can provide a way to understand a system when analytical approaches fail and traditional direct solution methods such as factorization fail due to the complexity of the problem.

http://en.wikipedia.org/wiki/Iterative_method

http://netlib.org/linalg/html_templates/node9.html