An example of iterative methods using jacobi and Gauss seidal method?

Answer 1

This is gonna turn into a long answer, please bear with me. If you already know the algorithm's just skip to the examples.

Iterative techniques for solving a linear system Ax=b,where A is a square matrix with non-zero diagonal entries, start of by first rearranging the system into a form x=Tx+c where T is a fixed square matrix with zero entries along the diagonal. an initial approximation x(0) is then applied to the Tx+c part and gives the next set of of approximation values for x(1). First I'll give an example of the Jaboci method and then the Gauss-Seidal method. Both examples can be found at the start of section 7.3 of Numerical Analysis (8th edition) by R. L. Burden and J. Douglas Faires.

The Jacobi method

The Jacobi method generates the next approximation by using the formula,

xi(k+1)=Σnj=1, j=/=i (-aijxj(k))/aii + bi/aii.

Note that aii must not be equal to zero which is why we have A must be a square matrix with non-zero diagonal entries.

To show what I mean we will use the following system:

E1= 10x1 - x2 + 2x3 = 6

E2= -x1 + 11x2 - x3 + 3x4 =25

E3= 2x1 - x2 + 10x3 -x4 = -11

E4= 3x2- x3 + 8x4 = 15

Converting this from the form Ax=b to x=Tx+c we get:

x1(k+1) = x2(k)/10 - x3(k)/5 +3/5

x2(k+1) = x1(k)/11 + x3(k)/11 - 3x4(k)/11 + 25/11

x3(k+1) = -x1(k)/5 + x2(k)/10 + x4(k)/10 - 11/10

x4(k+1) = -3x2(k)/8 + x3(k)/8 + 15/8

Notice how this forms a matrix T where the diagonals are all zero and c=(3/5, 25/11, -11/10, 15/8).

For an initial approximation we shall use x(0)=(0,0,0,0) plugging these values we into the Tx+c part we get x(1)=(0.6, 2.2727, -1.1, 1.8750) and plugging these values in we get x(2)=(1.0473, 1.7159, -0.8052, 0.8852). After 10 iterations we obtain x(10)=(1.0001, 1.9998, -0.9998, 0.9998) giving us a maximum absolute error of 0.0002 as the unique solution is x=(1, 2, -1, 1)

You may notice that it does not matter in which order you compute the equations as all the variable only take the previous iteration. This is where The Gauss-Seidal method improves upon the Jacobi method to make a 'better' iteration method.

The Gauss-Seidal methodFor the G-S method the order in which you do the equations does matter, where the Jacobi takes the matrix T as it comes, the G-S method takes the upper and lower-triangular parts separately and requires using the iterations just worked out on the lower triangle.

To explain it better, go back to the iteration equations above, if you were to do them in order then for x2(k+1)=... part the first term you have is x1(k)/11, but in the previous equation you just worked out x(k+1). Surely it makes more sense to use this new value in the iteration for x2(k+1) than the old value, and this is exactly what the G-S method does! The G-S method generates the next approximation using the formula:

xi(k+1) = (-Σi-1j=1(aijxj(k+1)) - Σnj=i+1(aijxj(k)) + bi)/aii

Using our previous example this changes our iteration equations into the following:

x1(k+1) = x2(k)/10 - x3(k)/5 +3/5

x2(k+1) = x1(k+1)/11 + x3(k)/11 - 3x4(k)/11 + 25/11

x3(k+1) = -x1(k+1)/5 + x2(k+1)/10 + x4(k)/10 - 11/10

x4(k+1) = -3x2(k+1)/8 + x3(k+1)/8 + 15/8

Again starting with an initial approximation x(0)=(0, 0, 0, 0) and plugging into the equations above we get x(1) = (0.6, 2.3272, -0.9873, 0.8789) and now put these into the equations above and repeat. This time after 5 iterations we get x(5)=(1.0001, 2, -1, 1) so the G-S method has given us an answer with max absolute error of 0.0001 in half the amount of iterations that it took the Jacobi method to get an answer with max absolute error of 0.0002!