'*****************************************************
'*   Program to demonstrate the Aitken Steffenson    *
'*              iteration subroutine                 *
'* ------------------------------------------------- *
'* Reference: BASIC Scientific Subroutines, Vol. II  *
'* By F.R. Ruckdeschel, BYTE/McGRAWW-HILL, 1981 [1]. *
'* ------------------------------------------------- *
'* SAMPLE RUN:                                       *
'* (Example: find a real root of f(x) = x-2*SIN(x))  *
'*                                                   *
'* Input the initial guess:                          *
'*                                                   *
'*    X0 = -2                                        *
'*                                                   *
'* Convergence criterion: 1e-6                       *
'*                                                   *
'* Convergence factor: -1                            *
'*                                                   *
'* Maximum number of iterations: 25                  *
'*                                                   *
'*                                                   *
'* The calculated zero is X = -1.895494              *
'*                                                   *
'* The associated Y value is Y = -0.000000           *
'*                                                   *
'* The number of iterations was: 3                   *
'*                                                   *
'* ------------------------------------------------- *
'* Note: this algorithm fails with function (x+1)^5. *
'*****************************************************
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 Steffenson routine

print
print
print using " The calculated zero is X = ##.######"; x
print
gosub 1000
print using " The associated Y value is Y = ##.######"; y
print
print " The number of iterations was: "; n
print
end
'*************************************
1000 ' Function subroutine
  y = x-2#*SIN(x)
  c=1#-2#*COS(x)
  c=-1/c
  return
'*************************************

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

'End of file steffen.bas