CHAPTER 04.08: GAUSS-SEIDEL METHOD: Pitfalls and Advantages: Part 1 of 2

 

In this segment, we're going to talk about Gauss-Seidel method, and we're going to say a little bit about what the pitfalls of Gauss-Seidel method are, and discuss then the corresponding advantages once we have some answers to the pitfalls. If I . . . if you look at the example which we have taken in the previous segment, we had 12 x1, plus 3 x2, minus 5 x3 equal to 1, we have x1, plus 5 x2, plus 3 x3 equal to 28, and then we had 3 x1, plus 7 x2, plus 13 x3 equal to 76.  So we're given three harmless simultaneous linear equations here, where we want to find x1, x2, and x3, and we started with an initial guess of x1, x2, and x3 equal to 1, 0, 1, and then what we did was we found out what x1, x2, and x3 are, and we conducted only two iterations, but I gave you the answer for at the end of the sixth iteration.  So, if you would look at the previous segment, you'll find out that the value which we obtained, and if you don't want to look at the previous segment, you can always do this as an exercise, and this is what we got, we got this as our solution. And it was converging, because we know . . . so this is at the of the sixth iteration, at the end of sixth iteration, only six iterations. So it converges pretty fast, because we know just from looking at it, that the exact solution of this particular set of equations, x1, x2, x3 is nothing but 1, 3, 4.  So it converges pretty fast.  Now what I'm going to do is I'm going to switch the first equation and the third equation, so I'm going to switch the first equation and the third equation.  What that means is that if I make this to be the first equation and make this to be the third equation, nothing has changed so far as the solution is concerned, the solution still is 1, 3, and 4. So if I switch it, this is what I'm going to get, I'm going to get 3 x1, plus 7 x2, plus 13 x3 is equal to 76, this was previously the third equation, so I'm rewriting it as the first equation now. The second equation, or the middle equation, I'm going to leave it unchanged, or I'm not changing any equations, I'm just going to leave it where it was, let's put it that way.  I'm going to take the first equation and show it as my third equation. Now, if you are going to apply Gauss-Seidel method, what you will have is that the first equation will be written as this, 76, minus 7 x2, minus 13 x3, divided by 3, your second equation, x2, will be written as 28, minus x1, minus 3 x3, divided by 5, and your last equation, x3, will be written as 1, minus 12 x1, minus 3 x2, divided by -5.  So it's the same way we did the example before, so nothing has changed.  The only which we have changed now is that we made the third equation to be the first equation and the first equation to be the third equation here.  And in this case, when I start with the initial guess same as previously, I start again with the initial guess of 1, 0, 1, so nothing has changed so far as initial guess is concerned, but when I conduct six iterations, this is what I get for x1, x2, and x3. I get -2.0579 times 10 to the power 6 for x1, for x2 I get 1.2272 times 10 to the power 5, and for the third one I get -4.8653 times 10 to the power 6, this is what I get as my, at the end of sixth iteration, let me write it down here, at the end of sixth iteration. And you can see that now it's a different story, that it's not converging at all.  If you look at the absolute relative approximate errors here, the maximum absolute relative approximate error here is 109.89 percent at the end of the sixth iteration.  And I'm sure that if you continue to do this process, it's going to eventually, it's not going to converge, and eventually you're going to most probably get overflow error, because these numbers are going to become bigger and bigger as you go on. So the question arises, what happened?  I had the same set of equations, I started with the same initial guess, the only thing which I changed was I exchanged my equation 1 with equation 3, and that does not change the solution of the set of equations, but one set is converging, and another set is not converging.  So what you've got to understand is about that the Gauss-Seidel method may or may not converge.  So Gauss-Seidel method may or may not converge. So since this is an iterative procedure, most iterative procedures fall into this pitfall, that they may or may not converge.  That's not true for every iterative procedure.  You could have an iterative procedure such as bisection method of solving nonlinear equations, once you have found the upper and the lower limit of the root, the convergence is guaranteed in that case, although it's an iterative procedure, but here . . . but most iterative procedures do fall into the category that they may or may not converge.  So does that mean that when we're going to apply Gauss-Seidel method that we are at the mercy of what our initial guesses are or how we have . . . how the equations look like that Gauss-Seidel method may or may not converge? There is some relief here, is the fact that Gauss-Seidel method does converge for certain cases for sure. So Gauss-Seidel method converges if the coefficient matrix, which is A, is diagonally dominant. So if you're going to find out that, hey, when you are setting up your A matrix that it's diagonally dominant, then you are sure that Gauss-Seidel method will converge. And, in fact, it's a good thing that many of the physical systems in heat transfer, fluid mechanics, and structural mechanics, the way the coefficient matrix turns out to be, it does turn out to be diagonally dominant.  So we don't have to be concerned about too many systems where Gauss-Seidel method may or may not converge.