You are here

Iterative Methods for Solving Ax = b - Gauss-Seidel Method

Author(s): 
David M. Strong
Let us take Jacobi’s Method one step further. Where the true solution is x = (x1, x2, … , xn), if x1(k+1) is a better approximation to the true value of x1 than x1(k) is, then it would make sense that once we have found the new value x1(k+1) to use it (rather than the old value x1(k)) in finding x2(k+1), … , xn(k+1). So x1(k+1) is found as in Jacobi's Method, but in finding x2(k+1), instead of using the old value of x1(k) and the old values x3(k), … , xn(k), we now use the new value x1(k+1) and the old values x3(k), … , xn(k), and similarly for finding x3(k+1), … , xn(k+1). This technique is called the Gauss-Seidel Method -- even though, as noted by Gil Strang in his Introduction to Applied Mathematics, Gauss didn’t know about it and Seidel didn’t recommend it. It is described by

This can also be written

That is,

 ,
so that
 

Example 2

Let's apply the Gauss-Seidel Method to the system from Example 1:

 .

At each step, given the current values x1(k), x2(k), x3(k), we solve for x1(k+1), x2(k+1), x3(k+1) in

 . 

To compare our results from the two methods, we again choose x(0) = (0, 0, 0). We then find x(1) = (x1(1), x2(1), x3(1)) by solving

 .

Let us be clear about how we solve this system. We first solve for x1(1) in the first equation and find that

x1(1) = 3/4 = 0.750.

We then solve for x2(1) in the second equation, using the new value of x1(1) = 0.750, and find that

x2(1) = [9 + 2(0.750)] / 6 = 1.750.

Finally, we solve for x3(1) in the third equation, using the new values of x1(1) = 0.750 and x2(1) = 1.750, and find that

x3(1) = [-6 + 0.750 − 1.750] / 7 = − 1.000.

The result of this first iteration of the Gauss-Seidel Method is

x(1) = (x1(1), x2(1), x3(1)) = (0.750, 1.750, − 1.000).

We iterate this process to generate a sequence of increasingly better approximations x(0), x(1), x(2), … and find results similar to those that we found for Example 1.

  k   x(k) x(k)x(k-1) e(k) = xx(k) ||e(k)||
0 -0.000 -0.000 -0.000 -0.000 -0.000 -1.000 2.449
1 0.750 1.750 -1.000 -0.000 -0.000 -1.000 0.250 0.250 0.000 0.354
2 0.938 1.979 -1.006 0.188 0.229 -0.006 0.063 0.021 0.006 0.066
3 0.993 1.999 -1.001 0.056 0.020 0.005 0.007 0.001 0.001 0.007
4 0.999 2.000 -1.000 0.006 0.001 0.001 0.001 0.000 0.000 0.001
5 1.000 2.000 -1.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000

As in Example 1, we stop iterating after x(k)x(k-1), e(k), and ||e(k)|| are all 0 to three decimal places. Notice that this sequence of iterations converges to the true solution (1, -2, 1) much more quickly than we found in Example 1 using the Jacobi Method. This is generally expected, since the Gauss-Seidel Method uses new values as we find them, rather than waiting until the subsequent iteration, as is done with the Jacobi Method.

David M. Strong, "Iterative Methods for Solving [i]Ax[/i] = [i]b[/i] - Gauss-Seidel Method," Convergence (July 2005)