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