Deriving the Jacobi Iteration

From a Linear System to an Iteration

Gaussian elimination aims to solve a linear system in a finite sequence of steps. An iterative method takes a different approach: it starts with an initial guess and repeatedly applies a rule that is intended to produce better approximations. The Jacobi iteration is one such rule. Its derivation comes directly from separating the diagonal terms of the equations from all the other terms.

Consider a square system \(\mathbf{A}\mathbf{x}=\mathbf{b}\), where \(\mathbf{A}\in\mathbb{R}^{n\times n}\), \(\mathbf{x},\mathbf{b}\in\mathbb{R}^n\), and each diagonal entry \(a_{ii}\) is nonzero. The condition on the diagonal entries is essential: the update will require division by each \(a_{ii}\). Define \(\mathbf{D}\) to be the diagonal matrix with the same diagonal entries as \(\mathbf{A}\), and let \(\mathbf{R}\) contain the off-diagonal entries of \(\mathbf{A}\).

To derive the rule, write \(\mathbf{A}\mathbf{x}=\mathbf{b}\) as \((\mathbf{D}+\mathbf{R})\mathbf{x}=\mathbf{b}\). Rearranging gives \(\mathbf{D}\mathbf{x}=\mathbf{b}-\mathbf{R}\mathbf{x}\). Since the diagonal entries of \(\mathbf{D}\) are all nonzero, \(\mathbf{D}\) is invertible, with diagonal entries \(1/a_{ii}\) in its inverse. Applying \(\mathbf{D}^{-1}\) gives the fixed-point equation \(\mathbf{x}=\mathbf{D}^{-1}(\mathbf{b}-\mathbf{R}\mathbf{x})\). The iteration uses the right-hand side to construct a new vector from the current one.

In coordinates, the \(i\)th equation of the original system is \(a_{ii}x_i+\sum_{j\ne i}a_{ij}x_j=b_i\). Solving this equation for \(x_i\), then using the old coordinates to calculate the new ones, gives

Every new coordinate uses coordinates from the same previous iterate \(\mathbf{x}^{(k)}\). The updates are therefore computed as a group: a value calculated for one coordinate is not inserted into the formula for another coordinate until the next iteration.

Why the Fixed Points Are Solutions

Proof. A vector is a fixed point precisely when \(\mathbf{x}=\mathbf{D}^{-1}(\mathbf{b}-\mathbf{R}\mathbf{x})\). Multiplying both sides by the invertible matrix \(\mathbf{D}\) gives \(\mathbf{D}\mathbf{x}=\mathbf{b}-\mathbf{R}\mathbf{x}\), or \((\mathbf{D}+\mathbf{R})\mathbf{x}=\mathbf{b}\). By the definition of the splitting, \(\mathbf{D}+\mathbf{R}=\mathbf{A}\), so this is \(\mathbf{A}\mathbf{x}=\mathbf{b}\). Conversely, if \(\mathbf{A}\mathbf{x}=\mathbf{b}\), then \((\mathbf{D}+\mathbf{R})\mathbf{x}=\mathbf{b}\), hence \(\mathbf{D}\mathbf{x}=\mathbf{b}-\mathbf{R}\mathbf{x}\). Multiplication by \(\mathbf{D}^{-1}\) gives the fixed-point equation. Thus each condition implies the other. \(\square\)

This result identifies what the iteration is trying to reach, but it does not say that the sequence reaches a fixed point. The existence of a well-defined update only requires nonzero diagonal entries; whether repeated updates converge is a separate question.

Computing Successive Iterates

The matrix form can also be written as \(\mathbf{x}^{(k+1)}=\mathbf{D}^{-1}\mathbf{b}-\mathbf{D}^{-1}\mathbf{R}\mathbf{x}^{(k)}\). This form makes the repeated operation explicit: multiply the current vector by a fixed matrix, then add a fixed vector. It also confirms that the update is defined whenever \(\mathbf{D}\) is invertible.

Reading the Update as a Matrix Formula

In the two-variable example, \(\mathbf{D}^{-1}=\begin{bmatrix}1/4&0\\0&1/3\end{bmatrix}\). The full Jacobi update can therefore be written

The diagonal part determines the division used for each new coordinate; the off-diagonal part collects the contributions from the other coordinates. This organization is useful because it turns a system of equations into a uniform rule that can be repeated. In applications with many variables, the update can be implemented by repeatedly using the known diagonal entries and the off-diagonal interactions.

There is an important limitation in the derivation. If any \(a_{ii}=0\), then \(\mathbf{D}^{-1}\) does not exist, and the displayed Jacobi rule cannot be applied in this form. A zero diagonal entry is not repaired by simply dividing by it; the system or method must first be reconsidered. Even when all diagonal entries are nonzero, the derivation alone gives no guarantee that successive iterates approach a solution.

Common Mistake: Updating Coordinates in Sequence

For the first example with \(\mathbf{x}^{(0)}=\begin{bmatrix}0\\0\end{bmatrix}\), the correct first iterate is \(\mathbf{x}^{(1)}=\begin{bmatrix}9/4\\7/3\end{bmatrix}\). A tempting but incorrect calculation is to find \(x_1^{(1)}=9/4\), then use that newly calculated value to set \(x_2^{(1)}=(7-9/4)/3=19/12\). That produces \(\begin{bmatrix}9/4\\19/12\end{bmatrix}\), not the Jacobi iterate, because the second coordinate formula must use \(x_1^{(0)}=0\). The correction is to compute every coordinate from the same old vector first; only then do the new coordinates form \(\mathbf{x}^{(1)}\).

Another useful check is to distinguish an iterate from a solution. An iterate is obtained by applying the update, while a solution satisfies \(\mathbf{A}\mathbf{x}=\mathbf{b}\). They coincide at a fixed point, as proved above, but an intermediate iterate need not satisfy the system exactly. Substitution into the original equations, or multiplication to find \(\mathbf{A}\mathbf{x}^{(k)}-\mathbf{b}\), checks how far the computed vector is from being an exact solution.