TITLE:
Higher Order Aitken Extrapolation with Application to Converging and Diverging Gauss-Seidel Iterations
AUTHORS:
Ababu Teklemariam Tiruneh
KEYWORDS:
Linear Equations; Gauss-Seidel Iteration; Aitken Extrapolation; Acceleration Technique; Iteration Matrix; Fixed Point Iteration
JOURNAL NAME:
Journal of Applied Mathematics and Physics,
Vol.1 No.5,
November
12,
2013
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.