MTA-ELTE NumNet Reseach Group, Institute of Mathematics, Eotvos Lorand University, Hungary
Received April 25, 2016; Accepted April 26, 2016; Published April 28, 2016
Citation: Faragó I (2016) Some Notes on the Sequence Acceleration. J Appl Computat Math 5:303. doi:10.4172/2168-9679.1000303
Copyright: © 2016 Faragó I. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Visit for more related articles at Journal of Applied & Computational Mathematics
In the mathematical problems we seek the solution to the problem.
where F denotes some given operator (function) between two spaces. Typically we are not able to define u* in an explicit way. Therefore, by use of some numerical method, we replace (1) with the sequence of problems
Fn(un)=0, n=1,2,…, (2)
where each problem can be solved, and hence we construct the sequence To our purpose the following requirements are quite natural:
a) (un) is a convergent sequence;
From a practical point of view, it is also important to have information about the magnitude of the global error , because un (for some finite n) is considered as the numerical solution, i.e., the approximation of the exact solution u*. Clearly, convergence means that en tends to zero as n approaches infinity, i.e., en is arbitrarily small for sufficiently large values of n. In order to characterize the speed of the convergence, we assume that there exists the . We say that the convergence is linear if K∈(0,1). When K=1, then we say that the convergence is sublinear. When K=0, the convergence is called superlinear.
For the linear convergence the rate of convergence depends on how far K is from 1: the closer K to 1, the slower the convergence. The linear convergence means that the sequence is similar to the geometric sequence. This means that the convergent sequences, based on Banach’s fixed point theorem, has linear convergence.
Therefore the linear and the sublinear convergence might be very slow, and the error quite big for some (even big) value of n. Obviously, from a practical point of view, a numerical method is efficient when the global error is small for relatively small values of n. Hence, in case of slow convergence we need to accelerate the convergence rate.
We start with the example, given by the famous Japanese mathematician, Takakazu Seki, which defines an approximation to π in the following way . Let un be the perimeter of the polygon with 2n sides inscribed in a circle of diameter one. Hence
Seki computed a new value as follows:
which results in .
Therefore, he concluded that
Comparing to the exact decimal digits, we see that all the 12 digits in (4) are exact, while in the expressions for u15,u16 and u17 only the first 7, 8 and 9 digits are exact. This example shows that with a suitable operation the accuracy can be increased significantly.
The following process was suggested by Alexander Aitken .
We assume that (un) converges linearly to u*. Then, for large n we have
which yields the relation
Based on (7), we define the new approximation as
Theorem: Assume that (un) converges to u* linearly. Then
a) The sequence converges to the same limit, i.e.,
b) converges faster than (un), i.e.,
, n=1,2,…. (11)
Substituting (11) into (8), we get
In view of linear convergence, we have
Based on the identity
which can be verified directly. Since |K|<1, for n tends to infinity (12) implies
which proves the statements.
We remark that that obviously the Seki’s method is an Aitken process.
The above theorem states that the convergence of the new sequence is faster than that of the original one. We can apply this approach to fixed point iterative methods for nonlinear equations. Since for this case the sequence (un) is linearly convergent, and the Aitken’s process accelerates the convergence. Namely, the corresponding sequence converges to u* linearly, but faster than (un).
The algorithm of this method is as follows. We set an arbitrary x0, and then x1=f(x0), x2=f(x1). Having these points, we compute by (20) the new point following Aitken’s method as
and with this value we restart the fixed point iteration, i.e.,
Then we compute the approximation again by Aitken’s method as
and so on.
Steffensen’s method (similarly to Newton’s method) provides quadratic convergence. In Newton’s method we compute one function value and one derivative in each iteration step. In Steffensen’s method we have two function evaluations and a more complicated algebraic expression in each iteration, but no derivative. (However, in order to guarantee quadratic convergence for Steffensen’s method, the function f must be three times continuously differentiable, while in Newton’s method only twice.)
The following example demonstrates the methods, investigated so far.
Example: Find the unique fixed point of the function f(x)=cosx on the interval [0,1]. We use three methods :
1. Fixed point iteration: xn+1=f(xn)=cosxn.
2. Aitken’s method for the above sequence.
3. Steffensen’s method
(For each we choose x0=0.5 for the starting value) (Table 1).
Table 1: Decimal digits of accuracy.
The numerical experiment shows the following. To compute the fixed point to ten decimal digits of accuracy, the fixed point iteration requires 57 iterates, Aitken’s method 25 iterates, while Steffensen’s method requires only 3 iterates. (This yields that in the fixed point iteration for Aitken’s method 27 basic points, for Steffensen’s method 11 basic points are needed).
Aitken’s method is applicable for the acceleration of linearly convergent sequences. But, even for this case we cannot predict the magnitude of the increase. To give the characterization of the rate of convergence, we say that a sequence (un) converges to u* with order p if there exists a constant C≥0 such that the inequality holds for all, sufficiently large n. In numerical modelling, the sequence (un) is generated by solving the numerical model (2). The discrete models are typically constructed as the formulation of the model (1) on a sequence of discrete meshes (grids), and n depends on the number of grid points. Since in the discretization process the number of grid points is inversely proportional to the grid spacing parameter h, we may assume that .
Hence, the Landau notation can be written as O(hP), which means that
This can be written as
The Richardson’s method based on the following observation . When we have 2 different sequences, obtained by the same numerical method but on different meshes, formula (19) gives possibility to eliminate the term Cphp, and we obtain a method of higher order. E.g., when the sequences of p-th order are generated on the meshes of the step-size 2h and h, respectively, based on the corresponding two approximations we define the new approximation as
which will have the order of convergence p+1.
While the Aitken’s and Steffensen’s methods serve to accelerate the speed of the convergence of some fixed sequence by use of some transformation of the elements of this sequence, the Richardson’s method does the acceleration by use of two sequences, generated on by the same method but on different meshes.
Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals