'*****************************************************
'*        Program to demonstrate the Aitken          *
'*             acceleration subroutine               *
'* ------------------------------------------------- *
'* Reference: BASIC Scientific Subroutines, Vol. II  *
'* by F.R. Ruckdeschel, BYTE/McGRAWW-HILL, 1981 [1]. *
'* ------------------------------------------------- *
'* 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                 *
'*                                                   *
'*****************************************************
defint i-n
defdbl a-h,o-z
cls
print
print " Input the initial guess:"
print
input "    X0 = ",x0
print
input " Convergence criterion: ",e
print
input " Convergence factor: ",c
print
input " Maximum number of iterations: ",m

gosub 2000  'Call Aitken routine

print
print
print " The calculated zero is X = "; x
print
gosub 1000
print " The associated Y value is Y = "; y
print
print " The number of iterations was: "; n
print
end
'*************************************
1000 ' Function subroutine
  y = 1+5*x+10*x*x+10*x^3+5*x^4+x^5
  return
'*************************************

'***********************************************
'*       Aitken acceleration 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.                            *
'***********************************************
2000 n=0
  x=x0
  'Get y
2100 gosub 1000
  y=x+c*y
  'Enough points for acceleration ?
  if n>0 then goto 2200
  x1=y : x=x1 : n=n+1
  goto 2100
2200 x2=y : n=n+1
  'Guard against a zero denominator
  if x2-2#*x1+x0=0 then x0=x0+0.001
  'Perform acceleration
  xk=(x2-x1)*(x2-x1)/(x2-2#*x1+x0)
  x2=x2-xk
  'Test for convergence
  if n>=m then return
  if ABS(xk)<e then return
  x0=x1 : x1=x2 : x=x1
  goto 2100
return

'End of file Aitken.bas