Relaxation method

Here we have included details about relaxation method and some examples .
Contribution - Parinda Rajapakha, Hashan Wanniarachchi, Sameera Horawalawithana, Thilina Gamalath, Samudra Herath and Pavithri Fernando.

1. Relaxation Method

2. Introduction Relaxation method is an iterative approach solution to systems of linear equations. Basic idea behind this method is to improve the solution vector successively by reducing the largest residual at a particular iteration.

3. What is a residual? Suppose x ( i ) € R is an approximation to the solution of the linear system defined by Ax=b Residual vector for x ( i ) with respect to this system is R ( i ) =b-A x ( i ) in i th iteration

4. The error: E (I ) = x-x ( i ) R ( i ) = b –Ax ( i ) = Ax –Ax ( i ) = A(x –x ( i ) ) = AE ( i ) : Residual equation: AE ( i ) =R ( i )

5. Let x (p) =( x 1 (p) ,x 2 (p) … x n (p) ) T be the solution vector obtained after p th iteration. If R i (p) denotes residual, a i1 x 1 + a i2 x 2 + … + a in x n = b i Define by, R i (p) = bi- (a i1 x 1 + a i2 x 2 + … + a in x n )

6. Applying relaxation method Transfer all the terms to the right hand side of the equation Reorder the equations in a way such that largest co-efficient in the equations appear on the diagonal Select the largest residual and give an increment dx =-r( i )/ a ii Change x ( i ) to x ( i ) + dx ( i ) to relax R( i ) that is to reduce R( i ) to zero

7. Example : 6x 1 -3x 2 +x 3 = 11 2x 1 +x 2 -8x 3 =-15 x 1 -7x 2 +x 3 = 10 0= 11- 6x 1 - 3x 2 - x 3 R1 0= 10- x 1 + 7x 2 - x 3  R2 0= - 15- 2x 1 - x 2 + 8x 3  R3

8. Start with initial guesses x 1 =x 2 =x 3 =0 R 1 =11, R 2 =10, R 3 =-15 Largest residual is R 3 So that dx 3 = - R 3 / a 33 dx 3 = - 15/- 8 = 1.875

9. New guesses: x 1 =0 x 2 =0 and x 3 =1.875 Continue the process until r  0

10. Final result would be like this Iteration no R1 R2 R3 Max Ri dx ( i ) x1 x2 x3 11 10 -15 1.875 1 -9.125 8.125 9.125 1.5288 1.875 2 0.0478 6.5962 -3.0576 6.5962 -0.9423 1.5288 1.875 3 -2.8747 0.0001 -2.1153 -2.8747 -0.4791 1.5288 -0.9423 1.875 4 -0.0031 0.4792 -1.1571 -1.1571 0.1446 1.0497 -0.9423 1.875 5 0.1447 0.3346 0.0003 0.3346 -0.0478 1.0497 -0.9423 2.0196 6 0.2881 0.0000 0.0475 0.2881 0.0480 1.0497 -0.9901 2.0196 7 -0.0001 0.048 0.1435 0.1435 -0.0179 1.0017 -0.9901 2.0196 8 0.0178 0.0659 0.0003 - - 1.0017 -0.9901 2.0017

11. At i th iteration we can see that R 1 ,R 2 and R 3 are small enough, So x i values in this iteration x 1 = 1.007, x 2 = -0.9901, x 3 = 2.0017 Which are very close to the Exact solutions x 1 = 1.0 x 2 = -1.0 x 3 = 2.0

12. Convergence Converges slowly for large systems of equations (large n)

13. Special cases Simple to implement Not useful as a stand alone solution method Key ingredients to multi grid methods Jacobi Gauss seidel red

14. Comparison with Other Methods

15. Methods available to find solutions Direct Elimination Gaussian elimination Gauss-Jordan elimination Decomposition Court's reduction ( Cholesky's reduction) Iterative Jacobi's method Gauss-Seidel method Relaxation method

16. Advantages and Disadvantages Relaxation method is the core part of linear algebra. This method provide preconditions for new methods. Easily adoptable to computers. Can solve more than 100s of linear equations simultaneously . Slower progress than the competing methods

17. Solve: 6x - 3y + z = 11 2x + y - 8z = -15 x - 7y + z = 10 Gaussian Elimination Gauss- Jordan Elimination Courts Reduction Relaxation method X 1 1 1 1.0017 Y -1 -1 -1 -0 9901 Z 2 2 2 2.0017

18. Relaxation method is the best method for : Relaxation method is highly used for image processing . This method has been developed for analysis of hydraulic structures . Solving linear equations relating to the radiosity problem. Relaxation methods are iterative methods for solving systems of equations, including nonlinear systems. Relaxation method used with other numerical methods in mono-tropic programs.

19. Completed Researches

20. Why relaxation methods? Direct methods are robust. Direct methods are less computational costly. But They require high memory access. Slow in convergence.

21. Evolution of relaxation methods Gauss Siedel Iteration Gauss’s letter to Gerling Era of electronic computing

22. Work of David Young Notions - “Consistent Ordering” and “Property A” Convergence of the methods Ostrowski (1937) Relevant properties for M-Matrices Theorem of Stein – Rosenburg (1948) Asymptotic rates Concept of Irreducibility Grid oriented matrices

23. Concept of Cyclic Matrices Convergence theory of SOR methods Varga’s Contribution Generalization of Young’s results Matrix Iterative Analysis (1962) Notions – Regular Splittings Theories - Stieltjes and M-Matrices Semi Iterative Methods Richard Varga

24. 1960s and 1970s Chaotic Relaxations Chazan , Miranker , Miellou , Robert Multigrid Methods Krylov subspace method Use of Eugene values

25. References Rao , K.S., Year. Numerical Methods for Scientists and Engineers. 2 nd ed. Delhi: Prentice-Hall of India. Yousef Sadd and , Henk A. van der Vorst, Iterative Solution of Linear Systems in the 20 th Century [ pdf ]. Available at: < www-users.cs.umn.edu/~ saad /PDF/umsi-99-152.pdf> Accessed [12 th July 2012 ] Relaxation Methods for Iterative Solution to Linear Systems of Equations Gerald Recktenwald Portland State University Mechanical Engineering Department Scientic Computing II Relaxation MethodsMichael Bader Summer term 2012

26. Working scenario

27. Demonstration