Aitken

viewed 2040 times and licensed 50 times

Calculates the zeros of a function using Aitken acceleration.

Controller: CodeCogs

Contents

Interface
Aitken
Page Comments

Interface

C++

Aitken

doubleaitken(	double	(`f`)(double)[function pointer]*
	double	`x0` `= 0`
	double	`eps` `= 1E-10`
	int	`maxit` `= 1000`
	double	`c` `= -1`	)

Let $\inline (x_n)$ be a sequence with limit $\inline \overline{x}$ . The Aitken method consists of transforming $\inline (x_n)$ into $\inline (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$

(2)

The $\inline (y_n)$ sequence converges more rapidly than $\inline (x_n)$ towards the same limit $\inline \overline{x}$ . It is good practice to avoid the above form of $\inline (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$

(3)

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

f	the user-defined function
x0	Default value = 0
eps	Default value = 1E-10
maxit	Default value = 1000
c	Default value = -1

Authors

Lucian Bentea (August 2005)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.