Jacobi and Gauss-Seidel Methods

students, imagine you have a huge system of equations with many unknowns, like the kind used to model traffic flow, electric circuits, or heat spread across a metal plate ⚡🔥. Solving such systems exactly with elimination is possible, but sometimes it is slow or inconvenient, especially for very large problems. That is where iterative methods come in. Instead of finding the answer in one giant step, we start with a guess and improve it again and again until the values stabilize.

In this lesson, you will learn how the Jacobi method and the Gauss-Seidel method work, why they are useful, and how they fit into the bigger picture of Linear Systems II. By the end, you should be able to explain the main ideas, carry out iterations on small examples, and compare the two methods using numerical reasoning.

Why iterative methods matter

A linear system can be written as $A\mathbf{x}=\mathbf{b}$, where $A$ is the coefficient matrix, $\mathbf{x}$ is the vector of unknowns, and $\mathbf{b}$ is the constant vector. In many real problems, $A$ may be large and sparse, meaning most of its entries are zero. This happens in applications like weather models, structural engineering, and image processing. For these systems, direct methods such as Gaussian elimination may be expensive in time and memory.

Iterative methods solve the system by generating a sequence of approximations $\mathbf{x}^{(0)},\mathbf{x}^{(1)},\mathbf{x}^{(2)},\dots$ that hopefully gets closer and closer to the true solution. The idea is simple but powerful: use the current estimate to build a better one. 🧠

Two of the most important iterative methods are Jacobi and Gauss-Seidel. Both are based on rearranging each equation so that one variable is isolated. Then the isolated forms are used repeatedly to update guesses.

For example, if one equation is $a_{11}x_1+a_{12}x_2+a_{13}x_3=b_1$, and $a_{11}\neq 0$, then we can solve for $x_1$ as $x_1=\frac{b_1-a_{12}x_2-a_{13}x_3}{a_{11}}$. The same idea works for each equation in the system.

The Jacobi method: updating all variables at once

The Jacobi method uses only values from the previous iteration to compute the next one. That means every new value is based on the old approximation, not on any values just updated in the same step.

Suppose we have a system of three equations:

$$a_{11}x_1+a_{12}x_2+a_{13}x_3=b_1$$

$$a_{21}x_1+a_{22}x_2+a_{23}x_3=b_2$$

$$a_{31}x_1+a_{32}x_2+a_{33}x_3=b_3$$

If each diagonal entry $a_{ii}\neq 0$, we can rewrite the system as

$$x_1=\frac{b_1-a_{12}x_2-a_{13}x_3}{a_{11}}$$

$$x_2=\frac{b_2-a_{21}x_1-a_{23}x_3}{a_{22}}$$

$$x_3=\frac{b_3-a_{31}x_1-a_{32}x_2}{a_{33}}$$

The Jacobi iteration formulas become

$$x_1^{(k+1)}=\frac{b_1-a_{12}x_2^{(k)}-a_{13}x_3^{(k)}}{a_{11}}$$

$$x_2^{(k+1)}=\frac{b_2-a_{21}x_1^{(k)}-a_{23}x_3^{(k)}}{a_{22}}$$

$$x_3^{(k+1)}=\frac{b_3-a_{31}x_1^{(k)}-a_{32}x_2^{(k)}}{a_{33}}$$

Notice that all right-hand sides use only superscript $k$ values. That is the key feature of Jacobi. It is like everyone in a group works from the same old class notes before the new notes are handed out 📚.

A small Jacobi example

Consider the system

$$4x+y=9$$

$$x+3y=5$$

Rearrange each equation:

$$x=\frac{9-y}{4}$$

$$y=\frac{5-x}{3}$$

Start with an initial guess $x^{(0)}=0$, $y^{(0)}=0$.

Using Jacobi:

$$x^{(1)}=\frac{9-0}{4}=2.25$$

$$y^{(1)}=\frac{5-0}{3}=1.666\ldots$$

Next iteration:

$$x^{(2)}=\frac{9-y^{(1)}}{4}=\frac{9-1.666\ldots}{4}=1.833\ldots$$

$$y^{(2)}=\frac{5-x^{(1)}}{3}=\frac{5-2.25}{3}=0.916\ldots$$

The approximations are changing, and with more iterations they move toward the exact solution. For this system, the exact solution is $x=2$, $y=1$. The Jacobi method does not jump straight there, but it can approach the answer step by step.

The Gauss-Seidel method: using new values immediately

The Gauss-Seidel method is very similar to Jacobi, but it is a little more efficient in many cases because it uses the newest available values as soon as they are computed. This means when finding $x_2^{(k+1)}$, the method can already use $x_1^{(k+1)}$ from the same iteration.

For the same three-equation system, Gauss-Seidel updates are

$$x_1^{(k+1)}=\frac{b_1-a_{12}x_2^{(k)}-a_{13}x_3^{(k)}}{a_{11}}$$

$$x_2^{(k+1)}=\frac{b_2-a_{21}x_1^{(k+1)}-a_{23}x_3^{(k)}}{a_{22}}$$

$$x_3^{(k+1)}=\frac{b_3-a_{31}x_1^{(k+1)}-a_{32}x_2^{(k+1)}}{a_{33}}$$

The first equation looks the same as in Jacobi, but the later equations use updated values from the current sweep. This is like a student solving one question, then using that answer immediately on the next question instead of waiting until the whole page is finished ✏️.

A small Gauss-Seidel example

Use the same system:

$$4x+y=9$$

$$x+3y=5$$

Rewrite it as

$$x=\frac{9-y}{4}$$

$$y=\frac{5-x}{3}$$

Start with $x^{(0)}=0$, $y^{(0)}=0$.

First update $x$:

$$x^{(1)}=\frac{9-y^{(0)}}{4}=\frac{9}{4}=2.25$$

Then update $y$ using the new value of $x$:

$$y^{(1)}=\frac{5-x^{(1)}}{3}=\frac{5-2.25}{3}=0.916\ldots$$

Next iteration:

$$x^{(2)}=\frac{9-y^{(1)}}{4}=\frac{9-0.916\ldots}{4}=2.0208\ldots$$

$$y^{(2)}=\frac{5-x^{(2)}}{3}=0.9930\ldots$$

Compared with Jacobi, Gauss-Seidel often gets closer to the solution faster because it uses fresh information right away.

Comparing the two methods

The main difference is how they use information during an iteration.

Jacobi uses only values from the previous iteration.
Gauss-Seidel uses the newest values as soon as they are available.

This makes Gauss-Seidel often faster in practice, but not always easier to parallelize. Jacobi is simpler to run on many processors at once because every update can be computed independently from the same old vector $\mathbf{x}^{(k)}$. That is one reason Jacobi appears in computer simulations and parallel computing.

Both methods are iterative, so they depend on an initial guess, often written as $\mathbf{x}^{(0)}$. They also may require many iterations to reach a desired accuracy. A common stopping idea is to keep iterating until the change between successive approximations is small, for example when $\|\mathbf{x}^{(k+1)}-\mathbf{x}^{(k)}\|$ is below a chosen tolerance. The norm $\|\cdot\|$ measures size or distance.

When do these methods converge?

Convergence means the sequence of approximations approaches the exact solution. Not every system guarantees convergence for Jacobi or Gauss-Seidel. A common sufficient condition is diagonal dominance. A matrix $A=[a_{ij}]$ is strictly diagonally dominant by rows if

$$|a_{ii}|>\sum_{j\neq i}|a_{ij}|$$

for every row $i$. This means each diagonal entry is larger in magnitude than the sum of the other entries in that row.

Why does this matter? If the diagonal term is strong compared with the others, each equation gives stable information for updating one variable. In many such systems, Jacobi and Gauss-Seidel converge.

For example, the matrix

$$\begin{bmatrix}4 & 1\\1 & 3\end{bmatrix}$$

is strictly diagonally dominant because $|4|>|1|$ and $|3|>|1|$. The example we used earlier fits this pattern, which helps explain why the iterations moved toward the solution.

It is important to know that diagonal dominance is sufficient but not necessary. Some systems without diagonal dominance still converge, and some with weak diagonal dominance may not. So in practice, convergence must be considered carefully.

How this fits into Linear Systems II

Jacobi and Gauss-Seidel belong to the broader study of solving linear systems numerically. In Linear Systems II, the goal is not only to find answers, but also to understand how algorithms behave: how fast they work, when they fail, how accurate they are, and how they connect to matrix properties.

These methods also connect to conditioning. If a linear system is ill-conditioned, small changes in data can cause large changes in the solution. Even a convergent iterative method may be affected by rounding errors or slow progress. So numerical analysis is not just about formulas; it is about how computation behaves in the real world.

Think of it this way: direct methods aim to solve the whole puzzle at once, while iterative methods improve a picture step by step. Jacobi and Gauss-Seidel are classic tools because they reveal the structure of the system and provide practical ways to approximate solutions when exact methods are too costly.

Conclusion

Jacobi and Gauss-Seidel are two foundational iterative methods for solving systems of linear equations. Jacobi updates every variable using only old values, while Gauss-Seidel uses the newest values immediately. Both can be effective for large sparse systems, especially when the matrix is well behaved, such as being strictly diagonally dominant. students, understanding these methods helps you see how numerical algorithms transform algebra into computation and how Linear Systems II connects theory with real applications 💡.

Study Notes

A linear system can be written as $A\mathbf{x}=\mathbf{b}$.
Iterative methods build a sequence $\mathbf{x}^{(0)},\mathbf{x}^{(1)},\mathbf{x}^{(2)},\dots$ instead of solving in one step.
In the Jacobi method, every new value uses only values from the previous iteration.
In the Gauss-Seidel method, updated values are used immediately within the same iteration.
Gauss-Seidel often converges faster than Jacobi, but Jacobi is easier to parallelize.
Both methods need an initial guess $\mathbf{x}^{(0)}$ and a stopping rule based on accuracy or tolerance.
Strict diagonal dominance, $|a_{ii}|>\sum_{j\neq i}|a_{ij}|$, is a common sufficient condition for convergence.
These methods are important in numerical analysis because they are useful for large, sparse systems where direct methods may be expensive.