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

method may or may not converge.  So what does it mean that A is diagonally dominant?  It is that if you look at A for the first set which we had it's 12, 3, -5, and we have 1, 5, and 3, and 3, 7, and 13, this is the coefficient matrix for the first set of equations when we wrote it, which converged. So what makes this diagonally dominant is that what you have to do is you have to look at each of the diagonal terms, and take the absolute value of the diagonal terms, so I'm taking the absolute value of 12, then you take the absolute value of the rest of the elements, 3 and -5, and you add them up, you get 8.  Is it greater or equal to? Yes.  Same thing here, the absolute value of 5, which is here, the diagonal element, is it greater than or equal to the absolute value of 1 plus the absolute value of 3, which is the rest of the elements which are added together after taking the absolute value, which is 4, is it true?  Yes it is.  Same thing which you do here is that absolute value of 13, is it greater than the absolute value of 3 plus 7?  So absolute value of 3 plus absolute value of 7, which is 10, is it greater than or equal to?  Yes it is. So this is true.  Now, one of the things which you have to understand about diagonally dominant matrices is that, yes, you have checked whether the absolute value of the diagonal element for each of the rows is greater than or equal to the sum of the absolute value of the rest of the elements in that particular row, and it has to be true for all cases, which it is, but then also strictly greater than condition has to be met for at least one row. What that means is that we do understand that 12 is greater than or equal to 8, 5 is greater than or equal to 4, and 13 is greater than or equal to 10, but the strictly greater than condition that in one of the rows, at least, you have to have that this number here is strictly greater than the number which you're getting here, and which is the case here, in fact for all rows, this condition is met, 12 is strictly greater than 8, 5 is greater than . . . strictly greater than 4, and 13 is strictly greater than 10.  So this does fall under it being diagonally dominant, so it is diagonally dominant.  So that's why Gauss-Seidel method converges for this one.  Now, keep in mind that it's a condition saying that if A is diagonally dominant, then Gauss-Seidel method converges.  If A is not diagonally dominant, then it may or may not converge, we don't know.  So please don't think that if A is not diagonally dominant that Gauss-Seidel method will not converge.  That's not . . . we cannot prove that, or that's not true.  If A is diagonally dominant, then surely Gauss-Seidel method would converge.  If A is not diagonally dominant, Gauss-Seidel method may or may not converge.  Now, if you look at the second case where our . . . this coefficient matrix is 3, 7, 13, 1, 5, 3, 12, 3, -5.  Now, again, what you take the diagonal element, which is 3, absolute value of that, then you take the absolute value of the rest of the elements in that particular row, it's 7, and absolute value of 13 you add is 20.  Is it greater than equal to?  No, it is not greater than equal to that number, so right there, right in the first row, it tells you that it is not diagonally dominant, so it may or may not converge.  It may or may not converge. Now, some people might say that, hey, if somebody gave me the equations in the second form, I can always switch over, so let me, I'll have to go back to this particular board right here . . . right here, yeah.  So, somebody might say, hey, somebody gave me equations like this. Somebody gave me equations like this, and I know that it is not converging. So what I can do is I can always switch this row here and switch this row here, and if I do that then it's going to be diagonally dominant.  So does that mean that every set of equations which somebody might give me, that we can rewrite them in a fashion that it will be diagonally dominant?  Now, in this case it is true, because if I switch row number 3 with row number 1, what's going to happen is that the coefficient matrix which I am going to be getting will be in the form which will be diagonally dominant, and hence I can solve the set of equations and be sure that the convergence is going to take place, but that's not necessarily true for every case, so please don't think that you can take a set of equations and make them diagonally dominant.  I'll give you an example. x1, plus x2, plus x3 is equal to 3, 2 x1, plus 3 x2, plus 4 x3 is equal to 9, and x1, plus 7 x2, plus x3 is equal to 9.  You have these three equations, three unknowns. No matter how hard you try, you cannot rearrange these equations to make them diagonally dominant. So some can be . . . some can be made diagonally dominant, but all of them cannot be made diagonally dominant.  So this is an example where, no matter how hard you try, the coefficient matrix for the set of equations cannot be made diagonally dominant, and hence be assured of convergence.  So far as the advantages are concerned, let's, we have discussed them before, let's put them back again here.  The advantage of Gauss-Seidel method is that may be computationally less intensive.  So it might take less time for large n.  So if you are using your traditional Gauss elimination methods, what happens is that for large n, Gauss elimination is going to start taking a lot more time than Gauss-Seidel method in many, many cases. So if you have a very large value of n, it may be computationally less intensive, the Gauss-Seidel method.  The second one is that you can control round-off error. You cannot totally control round-off error, but since it's an iterative procedure, and you are basing your stopping criteria on the absolute relative approximate error, the maximum absolute relative approximate error being less than the pre-specified tolerance.  You can always choose this to be a smaller and smaller number, as such that you conduct more and more iterations and get a better and better estimate. Of course, there's a limit to it, because depending on how much, what is the machine epsilon of the . . . of the computer, that how much you can choose this to be, you cannot . . . if you choose epsilon-s to be n to the power -20, for single precision it's not going to do you any good, because the numbers are represented only up to maybe six or seven significant digits. So you can control round-off error a little bit better, better than Gauss elimination, because there's no way to control round-off error in Gauss elimination, but here you can do that.  So those are the advantages of using Gauss-Seidel method.  And that is the end of this segment.