7. Iterative Methods#
Iterative methods generate a sequence of approximations that converge to the solution of a linear system. For very large sparse systems, storing matrix factors and performing elimination can be computationally expensive. Iterative methods often require less memory and can exploit sparsity efficiently.
The matrix equation of a linear system \(A\mathbf{x} = \mathbf{b}\) can be rewritten as
\(T\) is an iteration matrix and \(\mathbf{c}\) is some vector. This leads to the iterative form
where \(\mathbf{x}^{(k)}\) and \(\mathbf{x}^{(k+1)}\) are the current and improved estimates of \(\mathbf{x}\) respectively. Equation (7.1) is iterated updating the values of the estimates such that \(\mathbf{x}^{(k)} \to \mathbf{x}\) as \(k\to \infty\). Not every iteration matrix \(T\) leads to convergence. An important question is determining the conditions under which the sequence \(x^{(k)}\) converges to the true solution.
Note that unlike direct methods which will calculate the exact solution, iterative methods only calculate an estimate (albeit very close) of the exact solution.
These notes will introduce three common iterative methods
the Jacobi method: updates all variables simultaneously using values from the previous iteration
the Gauss-Seidel method: updates variables sequentially using the newest available values
the SOR method: accelerates Gauss-Seidel using a relaxation parameter