/****************************************************
*        Program to demonstrate the Aitken          *
*         acceleration method subroutine            *
* ------------------------------------------------- *
* Reference: BASIC Scientific Subroutines, Vol. II  *
* By F.R. Ruckdeschel, BYTE/McGRAWW-HILL, 1981 [1]. *
*                                                   *
*             C++ version by J-P Moreau, Paris.     *
*                    (www.jpmoreau.fr)              *
* ------------------------------------------------- *
* Example: Find a real root of f(x)=(x+1)^5         *
*                                                   *
* Sample run:                                       *
*                                                   *
*  Input the initial guess:                         *
*     X0 = 0                                        *
*  Convergence criterion: 0.000001                  *
*  Convergence factor: -1                           *
*  Maximum number of iterations: 100                *
*                                                   *
*  The calculated zero is X = -1                    *
*  The associated Y value is Y =  0                 *
*  The number of iterations was:  2                 *
*                                                   *
****************************************************/
#include <stdio.h>
#include <math.h>

double  c,e,x,x0;
int     m, n;

//*************************************************
// Function subroutine                            
double Y(double x) {
  return 1+5*x+10*x*x+10*x*x*x+5*x*x*x*x+x*x*x*x*x;
}
//*************************************************

/**********************************************
*          Aitken Method Subroutine           *
* ------------------------------------------- *
* This subroutine calculates the zeroes of a  *
* function Y(x) by iterations, and employs    *
* Aitken acceleration to speed up convergence.*
* An initial guess is required, x0, and two   *
* convergence factors, c and e. e relates to  *
* the accuracy of the estimate, and c is used *
* to aid convergence. Also required is the    *
* maximum number of iterations, m. c=-1 is a  *
* normal value, if divergence occurs, smaller *
* and/or positive values should be tried.     *
* The root is returned in x, the number of    *
* iterations in n.                            *
**********************************************/
void Aitken()  {
  double x1,x2,xk,yy;
  n=0;
  x=x0;
  // Get y
e100: yy=Y(x);
  yy=x+c*yy;
  // Enough points for acceleration ? 
  if (n>0) goto e200;
  x1=yy; x=x1; n=n+1;
  goto e100;
e200: x2=yy; n=n+1;
  // Guard against a zero denominator
  if (x2-2.0*x1+x0==0)  x0=x0+0.001;
  // Perform acceleration
  xk=(x2-x1)*(x2-x1)/(x2-2.0*x1+x0);
  x2=x2-xk;
  // Test for convergence
  if (n>=m) return;
  if (fabs(xk)<e) return;
  x0=x1; x1=x2; x=x1;
  goto e100;
}


void main()  {
  printf("\n Input the initial guesses:\n\n");
  printf("    X0 = "); scanf("%lf",&x0);
  printf("\n Convergence criterion: "); scanf("%lf",&e);
  printf("\n Convergence factor: "); scanf("%lf",&c);
  printf("\n Maximum number of iterations: "); scanf("%d",&m);

  Aitken();    // Call Aitken routine

  printf("\n\n The calculated zero is X = %f\n\n",x);
  printf(" The associated Y value is Y = %f\n\n",Y(x));
  printf(" The number of steps was: %d\n\n",n);
}

// End of file Aitken.cpp