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) = x − x(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.