CodeCogs

Calculates the zeros of a function using Aitken acceleration.

You're viewing an older version of this page (#95). View the current version.

Interface

#include <codecogs/maths/rootfinding/aitken.h>

using namespace Maths::Rootfinding;

double aitken (double (*f)(double), double x0 = 0, double eps = 1E-10, int maxit = 1000, double c = -1)

Let $(x_n)$ be a sequence with limit $\overline{x}$ . The Aitken method consists of transforming $(x_n)$ into $(y_n)$ where

$y_n = \frac {x_n x_{n + 2} - x_{n+1}^2} {x_{n+2} - 2x_{n+1} + x_n} \qquad n \geq 0$

(1)

The $(y_n)$ sequence converges more rapidly than $(x_n)$ towards the same limit $\overline{x}$ . It is good practice to avoid the above form of $(y_n)$ , which is numerically unstable, and write it in the following equivalent form:

$y_n = x_{n + 1} + \frac {1} { \frac {1} {x_{n + 2} - x_{n + 1}} - \frac {1} {x_{n + 1} - x_n}} \qquad n \geq 0$

(2)

This algorithm finds the roots of the user-defined function f starting with an initial guess x0 and iterating the sequence above until either the accuracy <em> eps </em> is achieved or the maximum number of iterations maxit is exceeded. The c factor is used to aid convergence; c = -1 is a normal value, however if divergence occurs, smaller and/or positive values should be tried.

References

Jean-Pierre Moreau's Home Page, http://perso.wanadoo.fr/jean-pierre.moreau/
F.R. Ruckdeschel, "BASIC Scientific Subroutines", Vol. II, BYTE/McGRAWW-HILL, 1981

Example 1

#include <codecogs/maths/rootfinding/aitken.h>

#include <iostream>
#include <iomanip>
#include <cmath>

// user-defined function
double f(double x) {
    return sin(x);
}

int main() 
{
    double x = Maths::RootFinding::aitken(f, 3);

    std::cout << "The calculated zero is X = " << std::setprecision(12) << x << std::endl;
    std::cout << "The associated ordinate value is Y = " << f(x) << std::endl;
    return 0;
}

Output:

The calculated zero is X = 3.14159265462
The associated ordinate value is Y = -1.02635576671e-009

Parameters

the user-defined function

Default value = 0

eps

Default value = 1E-10

maxit

Default value = 1000

Default value = -1