Numerical linear algebra · Definition

Jacobi and Gauss-Seidel methods

numerical methodsnumerical linear algebra

Before you start you need to know

When a system has many unknowns, solving it by direct elimination can be costly. These methods offer an alternative based on successive iterations.

Definition

The Jacobi and Gauss-Seidel methods are iterative procedures that approximate the solution of a linear system \(A\mathbf{x}=\mathbf{b}\) by repeatedly updating its components.

\[x_i^{(k+1)}=\frac{1}{a_{ii}}\left(b_i-\sum_{j\neq i}a_{ij}x_j^{(k)}\right)\]

Jacobi uses at each step only the values from the previous iteration, while Gauss-Seidel immediately incorporates the already updated components. If \(A\) is strictly diagonally dominant, both methods converge for any initial vector.

Consider the system \(4x+y=9\), \(x+3y=7\). Starting from \((0,0)\), Jacobi gives \(x^{(1)}=9/4\), \(y^{(1)}=7/3\), while Gauss-Seidel immediately uses the new \(x\) to compute \(y\), speeding up convergence.

A typical mistake is applying these methods to matrices without diagonal dominance and expecting convergence; in that case the iterations may diverge. It is wise to check the condition before iterating.

Think about it

Is strict diagonal dominance necessary for Jacobi to converge? Justify.

No: it is sufficient, but there are matrices without strict dominance where Jacobi converges, so it is not a necessary condition.

Exercises 10

  1. Which method updates the components using values already computed in the same iteration?
  2. Which property of the matrix guarantees convergence of both methods?
  3. In the update formula, why is division by \(a_{ii}\) performed?
  4. What is the usual initial vector in these methods when no estimate is known?
  5. What type of system is solved with these methods?
  6. For \(4x+y=9\), \(x+3y=7\), what is \(x^{(1)}\) with Jacobi from \((0,0)\)?
  7. For \(4x+y=9\), \(x+3y=7\), with Gauss-Seidel from \((0,0)\), what is \(y^{(1)}\)?
  8. If \(a_{22}=0\) in a 2x2 system, what happens when applying the update formula to the second unknown?
  9. Which of these statements comparing both methods is correct?
  10. Given \(A=\begin{pmatrix}2&1\\1&2\end{pmatrix}\) and \(\mathbf{b}=(3,3)\), what is \(x^{(2)}\) with Jacobi from \((0,0)\)?

References

  • Richard L. Burden, J. Douglas Faires, Annette M. Burden, Numerical Analysis, 10th edition, Cengage Learning, 2016.
  • Lloyd N. Trefethen, David Bau III, Numerical Linear Algebra, 1st edition, SIAM, 1997.