Chapter 04.08 Gauss-Seidel Method

1 Chapter Gauss-Seidel Method After reading this Chapter , you should be able to: 1. solve a set of equations using the Gauss-Seidel Method , 2. recognize the advantages and pitfalls of the Gauss-Seidel Method , and 3. determine under what conditions the Gauss-Seidel Method always converges. Why do we need another Method to solve a set of simultaneous linear equations? In certain cases, such as when a system of equations is large, iterative methods of solving equations are more advantageous. Elimination methods , such as Gaussian elimination, are prone to large round-off errors for a large set of equations. Iterative methods , such as the Gauss-Seidel Method , give the user control of the round-off error.

2 Also, if the physics of the problem are well known, initial guesses needed in iterative methods can be made more judiciously leading to faster convergence. What is the algorithm for the Gauss-Seidel Method ? Given a general set of n equations and n unknowns, we have a11 x1 + a12 x 2 + a13 x3 + .. + a1n x n = c1. a 21 x1 + a 22 x 2 + a 23 x3 + .. + a 2 n x n = c 2.. a n1 x1 + a n 2 x 2 + a n 3 x3 + .. + a nn x n = c n If the diagonal elements are non-zero, each equation is rewritten for the corresponding unknown, that is, the first equation is rewritten with x1 on the left hand side, the second equation is rewritten with x 2 on the left hand side and so on as follows Chapter c1 a12 x 2 a13 x3 a1n x n x1 =.

3 A11. c 2 a 21 x1 a 23 x3 a 2 n x n x2 =. a 22.. c n 1 a n 1,1 x1 a n 1, 2 x 2 a n 1,n 2 x n 2 a n 1,n x n x n 1 =. a n 1,n 1. c n a n1 x1 a n 2 x 2 a n ,n 1 x n 1. xn =. a nn These equations can be rewritten in a summation form as n c1 a1 j x j j =1. j 1. x1 =. a11. n c2 a2 j x j j =1. j 2. x2 =. a 22.. n c n 1 a j =1. n 1, j xj j n 1. x n 1 =. a n 1,n 1. n c n a nj x j j =1. j n xn =. a nn Hence for any row i , n ci aij x j j =1. j i xi = , i = 1,2, , n. aii Now to find xi 's, one assumes an initial guess for the xi 's and then uses the rewritten equations to calculate the new estimates. Remember, one always uses the most recent estimates to calculate the next estimates, xi . At the end of each iteration, one calculates the absolute relative approximate error for each xi as Gauss-Seidel Method x inew x iold a = 100.

4 I x inew where xinew is the recently obtained value of xi , and xiold is the previous value of xi . When the absolute relative approximate error for each xi is less than the pre-specified tolerance, the iterations are stopped. Example 1. The upward velocity of a rocket is given at three different times in the following table Table 1 Velocity vs. time data. Time, t (s) Velocity, v (m/s). 5 8 12 The velocity data is approximated by a polynomial as v(t ) = a1t 2 + a2t + a3 , 5 t 12. Find the values of a1 , a 2 , and a3 using the Gauss-Seidel Method . Assume an initial guess of the solution as a1 1 .. a 2 = 2 . a3 5 . and conduct two iterations. Solution The polynomial is going through three data points (t1 , v1 ), (t 2 , v2 ), and (t 3 , v3 ) where from the above table t1 = 5, v1 = t 2 = 8, v 2 = t 3 = 12, v3 = Requiring that v(t ) = a1t 2 + a 2 t + a3 passes through the three data points gives v(t1 ) = v1 = a1t12 + a2t1 + a3.

5 V(t 2 ) = v2 = a1t 22 + a2t 2 + a3. v(t3 ) = v3 = a1t32 + a2t3 + a3. Substituting the data (t1 , v1 ), (t 2 , v2 ), and (t 3 , v3 ) gives ( ). a1 52 + a2 (5) + a3 = a (8 ) + a (8) + a = 1. 2. 2 3. a (12 ) + a (12) + a = 1. 2. 2 3. Chapter or 25a1 + 5a2 + a3 = 64a1 + 8a2 + a3 = 144a1 + 12a2 + a3 = The coefficients a1 , a2 , and a3 for the above expression are given by 25 5 1 a1 . 64 8 1 a = . 2 . 144 12 1 a3 . Rewriting the equations gives 5a 2 a3. a1 =. 25. 64a1 a3. a2 =. 8. 144a1 12a 2. a3 =. 1. Iteration #1. Given the initial guess of the solution vector as a1 1 . a = 2 . 2 . a3 5 . we get 5(2) (5). a1 =. 25. = 64( ) (5). a2 =. 8. = 144( ) 12( ). a3 =. 1. = The absolute relative approximate error for each xi then is 1.

6 A 1 = 100. = 2. a = 100. 2. = 5. a = 100. 3. = Gauss-Seidel Method At the end of the first iteration, the estimate of the solution vector is a1 . a = . 2 . a3 . and the maximum absolute relative approximate error is Iteration #2. The estimate of the solution vector at the end of Iteration #1 is a1 . a = . 2 . a3 . Now we get 5( ) ( ). a1 =. 25. = 64( ) ( ). a2 =. 8. = 144( ) 12( ). a3 =. 1. = The absolute relative approximate error for each xi then is a 1 = 100. = ( ). a 2 = 100. = ( ). a 3 = 100. = At the end of the second iteration the estimate of the solution vector is a1 . a = . 2 . a3 . and the maximum absolute relative approximate error is Conducting more iterations gives the following values for the solution vector and the corresponding absolute relative approximate errors.

7 Chapter Iteration a1 a 1 % a2 a 2 % a3 a 3 %. 1 2 3 4 14440 5 60072 6 19049 249580 As seen in the above table, the solution estimates are not converging to the true solution of a1 = a2 = a3 = The above system of equations does not seem to converge. Why? Well, a pitfall of most iterative methods is that they may or may not converge. However, the solution to a certain classes of systems of simultaneous equations does always converge using the Gauss-Seidel Method . This class of system of equations is where the coefficient matrix [ A] in [ A][ X ] = [C ] is diagonally dominant, that is n aii aij for all i j =1. j i n aii > aij for at least one i j =1. j i If a system of equations has a coefficient matrix that is not diagonally dominant, it may or may not converge.

8 Fortunately, many physical systems that result in simultaneous linear equations have a diagonally dominant coefficient matrix, which then assures convergence for iterative methods such as the Gauss-Seidel Method of solving simultaneous linear equations. Example 2. Find the solution to the following system of equations using the Gauss-Seidel Method . 12 x1 + 3x 2 5 x3 = 1. x1 + 5 x2 + 3 x3 = 28. 3 x1 + 7 x2 + 13x3 = 76. Use x1 1 . x = 0 . 2 . x3 1 . as the initial guess and conduct two iterations. Solution The coefficient matrix Gauss-Seidel Method 12 3 5 . [A] = 1 5 3 . 3 7 13 . is diagonally dominant as a11 = 12 = 12 a12 + a13 = 3 + 5 = 8. a 22 = 5 = 5 a 21 + a 23 = 1 + 3 = 4. a33 = 13 = 13 a31 + a32 = 3 + 7 = 10.

9 And the inequality is strictly greater than for at least one row. Hence, the solution should converge using the Gauss-Seidel Method . Rewriting the equations, we get 1 3 x 2 + 5 x3. x1 =. 12. 28 x1 3 x3. x2 =. 5. 76 3 x1 7 x 2. x3 =. 13. Assuming an initial guess of x1 1 . x = 0 . 2 . x3 1 . Iteration #1. 1 3(0 ) + 5(1). x1 =. 12. = 28 ( ) 3(1). x2 =. 5. = 76 3( ) 7( ). x3 =. 13. = The absolute relative approximate error at the end of the first iteration is 1. a 1 = 100. = 0. a 2 = 100. = 1. a 3 = 100. = Chapter The maximum absolute relative approximate error is Iteration #2. 1 3( ) + 5( ). x1 =. 12. = 28 ( ) 3( ). x2 =. 5. = 76 3( ) 7( ). x3 =. 13. = At the end of second iteration, the absolute relative approximate error is a 1 = 100.

10 = a 2 = 100. = a 3 = 100. = The maximum absolute relative approximate error is This is greater than the value of we obtained in the first iteration. Is the solution diverging? No, as you conduct more iterations, the solution converges as follows. Iteration x1 a 1 % x2 a 2 % x3 a 3 %. 1 2 3 4 5 6 This is close to the exact solution vector of x1 1 . x = 3 . 2 . x3 4 . Example 3. Given the system of equations 3 x1 + 7 x2 + 13x3 = 76. Gauss-Seidel Method x1 + 5 x2 + 3 x3 = 28. 12 x1 + 3 x2 - 5 x3 = 1. find the solution using the Gauss-Seidel Method . Use x1 1 . x = 0 . 2 . x3 1 . as the initial guess. Solution Rewriting the equations, we get 76 7 x 2 13 x3. x1 =. 3. 28 x1 3 x3. x2 =.