7. Indirect Methods

Indirect methods for solving systems of linear equations use an iterative approach to repeatedly update estimates of the exact solution to the linear system. They are called indirect methods since multiple applications of the method is required to calculate a solution unlike matrix decomposition methods such as Gaussian elimination and LU decomposition which require a single application to calculate the solution. However, direct methods are inefficient for large systems of equations for which we tend to use indirect methods instead.

An indirect method for solving a system of linear equations of the form $A\mathbf{x}=\mathbf{b}$ is

(7.1)$${\mathbf{x}}^{(k+1)}=T{\mathbf{x}}^{(k)}+\mathbf{c},$$

where ${\mathbf{x}}^{(k)}$ and ${\mathbf{x}}^{(k+1)}$ are the current and improved estimates of $\mathbf{x}$ respectively, $T$ is an iteration matrix and $\mathbf{c}$ is some vector. This equation is iterated updating the values of the estimates such that ${\mathbf{x}}^{(k)}\to \mathbf{x}$ as $k\to \mathrm{\infty }$. Note that unlike direct methods which will calculate the exact solution, indirect methods only calculate an estimate (albeit very close) of the exact solution.

These notes will introduce three common indirect methods

• the Jacobi method;

• the Gauss-Seidel method;

• the SOR method