Higher Order Aitken Extrapolation with Application to Converging and Diverging Gauss-Seidel Iterations

Ababu Teklemariam Tiruneh

Department of Environmental Health Science, University of Swaziland, Mbabane, Swaziland.

DOI: 10.4236/jamp.2013.15019                

Abstract

In this paper, Aitken’s extrapolation normally applied to convergent fixed point iteration is extended to extrapolate the solution of a divergent iteration. In addition, higher order Aitken extrapolation is introduced that enables successive decomposition of high Eigen values of the iteration matrix to enable convergence. While extrapolation of a convergent fixed point iteration using a geometric series sum is a known form of Aitken acceleration, it is shown that in this paper, the same formula can be used to estimate the solution of sets of linear equations from diverging Gauss-Seidel iterations. In both convergent and divergent iterations, the ratios of differences among the consecutive values of iteration eventually form a convergent (divergent) series with a factor equal to the largest Eigen value of the iteration matrix. Higher order Aitken extrapolation is shown to eliminate the influence of dominant Eigen values of the iteration matrix in successive order until the iteration is determined by the lowest possible Eigen values. For the convergent part of the Gauss-Seidel iteration, further acceleration is made possible by coupling of the extrapolation technique with the successive over relaxation (SOR) method. Application examples from both convergent and divergent iterations have been provided. Coupling of the extrapolation with the SOR technique is also illustrated for a steady state two dimensional heat flow problem which was solved using MATLAB programming.

Keywords

Linear Equations; Gauss-Seidel Iteration; Aitken Extrapolation; Acceleration Technique; Iteration Matrix; Fixed Point Iteration

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	H. L. Stone, “Iterative Solution of Implicit Approximations of Multidimensional Partial Differential Equations,” SIAM Journal on Numerical Analysis, Vol. 5, No. 3, 1968, pp. 530-558. http://dx.doi.org/10.1137/0705044
[2]	M. R. Hestenes and E. Stiefel, “Methods of Conjugate Gradients for Solving Linear Systems,” Journal of Research at the National Bureau of Standards, Vol. 49, 1952, pp. 409-436. http://dx.doi.org/10.6028/jres.049.044
[3]	G. H. Golub and C. F. Van Loan, “Matrix Computations,” 3 Edition, Johns Hopkins University Press, Baltimore, 1996.
[4]	J. C. West, “Preconditioned Iterative Solution of Scattering from Rough Surfaces,” IEEE Transactions on Antennas and Propagation, Vol. 48, No. 6, 2000, pp. 1001-1002. http://dx.doi.org/10.1109/8.865236
[5]	A. C. Aitken, “Studies in Practical Mathematics. The Evaluation of Latent Roots and Latent Vectors of a Matrix,” Proceedings of the Royal Society of Edinburgh, Vol. 57, 1937, p. 269.
[6]	M. D. Gianola and L. R. Schaffer, “Extrapolation and Convergence Criteria with Jacobi and Gauss-Seidel Iteration in Animal Models,” Journal of Diary Science, Vol. 70, No. 12, 1987, pp. 2577-2584.
[7]	B. Irons and N. G. Shrive, “Numerical Methods in Engineering and Applied Science: Numbers are Fun,” John Wiley & Sons, New York, 1987.
[8]	S. R. Capehart, “Techniques for Accelerating Iterative Methods for the Solution of Mathematical Problems,” Ph.D. Dissertation, Oklahoma State University, 1989.
[9]	P. Henrici, “Elements of Numerical Analysis,” John Wiley & Sons, New York, 1964.
[10]	S. D. Kamvar, T. H. Haveliwala, C. D. Manning and G. H. Golub, “Extrapolation Methods for Accelerating Page Rank Computations,” Proceedings of the Twelfth International World Wide Web Conference, 2003, pp. 261-270. http://dx.doi.org/10.1145/775152.775190
[11]	C. Breziniski and M. R. Zaglia, “Generalizations of Aitken’s Process for Accelerating the Convergence of Sequences,” Journal of Computational and Applied Mathematics, Vol. 26, No. 2, 2007, pp. 171-189.
[12]	A. Bjorck, “Numerical Methods in Scientific Computing,” Linkoping University Royal Institute of Technology, Vol. 2, 2009.
[13]	D. M. Young, “Iterative Solution of Large Linear Systems,” Academic Press, New York, 1971.
[14]	G. Dahlquist and A. Bjorck, “Numerical Methods,” Prentice Hall, Englewood Cliffs, 1974.
[15]	C. F. Gerald and P. O. Wheatley, “Applied Numerical Analysis,” 5th Edition, 1994.
[16]	L. A. Hageman and D. M. Young, “Applied Iterative Methods,” Academic Press, New York, 1981.