EXPLANATION FILE OF PROGRAM STEFFEN
                       ===================================


  Aitken-Steffenson Iteration
  ---------------------------

    Aitken-Steffenson iteration is a variation on the Aitken acceleration sche-
  me. lt has very good convergence properties (quadratic) if the initial guess
  is in the vicinity of the root. This is to be contrasted with some of the al-
  gorithms discussed earlier which can diverge even if the initial guess is ve-
  ry close to the root. 

    As with Aitken acceleration (see file aitken.txt), this method is designed
  to find the fixed points of x = g(x). If we again define g(x) = x + cy(x),
  then the Aitken-Steffenson iteration formula is

                                 [g(xn) - xn]²
                  x'n = xn - ----------------------          (6.12.1)
                             g[g(xn)] - 2g(xn) + xn 

  x'n is employed to directly calculate xn+l using xn+l = g(x'n). This procedure
  differs from that of the Aitken acceleration algorithm which requires three
  prior values in order to perform the acceleration calculation. 

    The Aitken-Steffenson iteration scheme is applied in program Steffen. The
  results of using this subroutine to find the roots associated with the three
  following equations are shown below. 

            A) y(x) = x - 2 sin x               initial guess x0 = pi/2 
            B) y(x) = x^3 + 2x^2 - X - 2        initial guess x0 = -1.5
            C) y(x) = sin x                     initial guess x0 = 20

  Example A)
  ----------
                               Convergence Factor, c 

          E       -0.1 	        +0.1 	       -1 	     1 	     -l/dy/dx
           
        0.1   1.9105667(4)  1.8999486(4)  1.9066462(4)  1.8623822(5)  2.0006853 
     0.0001   1.8955203(8)  1.8954486(6)  1.8955338(8)  1.8954390(13) 1.8955769 
   0.000001   1.8954931(10) 1.8954929(10) 1.8954944(12) 1.8954938(19) 1.8954942
  0.0000001       ---           ---           ---           0(39)         ---

 True Value   1.8954942     1.8954942     1.8954942           0       1.8954942  

  Example B)
  ----------
                               Convergence Factor, c 
 
          E 	  -0.1 	        +0.1 	       -1 	     1 	     -l/dy/dx
           	   
        0.1  -1.5646928(3) 	----	 -2.0584778(5) 	-0.9918552(4)  -1.053669 	   
     0.0001  -1.999971(15) 	----	 -2.0000454(13) -0.9999888(8)  -0.999998 	   
   0.000001  -1.9999996(19) 	----	 -2.0000004(18) -0.9999996(10) -1 (6) 	   
  0.0000001  -1.9999999(21) 	----	 -2 (20) 	-1 (12)        -1 (6) 	   

 True Value       -2 		               -2 	     -1 	    -1 	   

  Example C)
  ----------
   
		               Convergence Factor, c
                                			   
          E 	  -0.1 	        +0.1 	       -1      	     1 	      -l/dy/dx 	   
        0.1  31.440408(12) 15.659416(26)  18.849381(4) 	28.283849(6)  15.813427 	   
     0.0001  31.415944(22) 50.265578(104) 18.849556(5) 	28.274334(6)  15.707963 	   
   0.000001     ---	      ---         18.849556(5) 	28.274334(6)  15.707963 	   
  0.0000001 	---	      ---	  18.849556(5) 	28.274334(6)  15.707963 	   

 True Value  31.415927 	   50.265482 	  18.849556 	28.274334     15.707963 	 

    If we use these examples as a guide, and compare them to the results of file
  Aitken.txt, we will see that Aitken-Steffenson iteration appears to behave
  much the same as Aitken acceleration. But it is somewhat slower in convergence
  --more iterations are required. ln 12 of the 60 examples, the iteration did
  not termina te at a11, probably because of round-off error problems in the
  calculation. 

    As with Aitken acceleration, convergence can be slow if the chosen c is too 
  small. Also, jumps can occur if c is too large and/or of the wrong sign (see
  example (A) for the case E = 0.0000001, c = 1). 

    Convergence can also be poor if |dg/dx| == 1 near the root. Because the de- 
  rivative of g(x) is 
                                              c
                                dg/dx = 1 + -----
                                            dy/dx

  poor convergence can occur if dy/dx == O. Geometrica11y, this result is not
  surprising.
   
    Even with these limitations, Aitken-Steffenson iteration and its relative,
  Aitken acceleration, are perhaps among the most powerful of the simple root-
  finding techniques available.

  From [BIBLI 01].
---------------------------------------------
End of file Steffen.txt