 | Java Number Cruncher: The Java Programmer's Guide to Numerical Computing
By Ronald Mak
| | Table of Contents | | | | Chapter 5. Finding Roots |
5.8 Fixed-Point Iteration Enter any value greater than 0 into a calculator, and then repeatedly press the  key. The value in the display steadily converges to 1. For the square root function  , the value 1 is its fixed point for any starting x value in the interval 0 < x <  . Similarly, 0 is the fixed point for the function g ( x ) = x 2 , but only for a starting x value in the interval -1 < x < 1. If a function has a fixed point for a starting x value, then the process of repeatedly applying the function is called fixed-point iteration. For reasons that will soon become clear, we'll use g as the name of a function with which we'll do fixed-point iteration. If we plot fixed-point iteration the same way we plotted Newton's algorithm, we can generate some particularly beautiful graphs, as shown in Figure 5-3. The first graph shows the function , and the second graph shows the function  . To convey that each value of g ( x ) is "fed back" to become the next value of x ?athat is, x n + 1 = g ( x n )?awe draw the line x = y and reflect each value of g ( x ) onto the next value for x. The fixed-point iteration trace for the first function is a staircase that leads to the fixed-point value of 1, and the trace for the second function spirals down to the fixed-point value of approximately 1.76. Figure 5-3. Fixed-point iteration traces for the functions  and .  The concept of fixed-point iteration will play a major role when we examine fractals in Chapter 16. But for now, we'll consider fixed-point iteration as another open algorithm for finding roots. So what root have we found by computing the fixed point of  Starting with the iteration formula x = g ( x ), we have 
and so if we set f ( x ) = x 2 - x, we can find one of its roots, namely the value 1, by deriving the function and doing fixed-point iteration with the latter. The fixed-point value of g ( x ) is then one of the roots of f ( x ). Similarly, for the function , we have 
and so  , and its root is approximately 1.76. Class FixedPointRootFinder , shown in Listing 5-6a, implements the fixed-point iteration algorithm. Given a function f ( x ), we must manually derive a function g ( x ) that is suitable for fixed-point iteration. For our original example function f ( x ) = x 2 - 4, we can derive g ( x ) by solving for x: 
and so  The algorithm iteratively computes x n + 1 = g ( x n ) until two successive values of x are sufficiently close to each other: 
where  is the machine epsilon value. We cannot use a smaller tolerance because the values generated by fixed-point iteration can oscillate near the fixed point, with x and g ( x ) exchanging values for each iteration. Listing 5-6a The class that implements the fixed-point iteration algorithm. package numbercruncher.mathutils; /** * The root finder class that implements * the fixed-point iteration algorithm. */ public class FixedPointRootFinder extends RootFinder { private static final int MAX_ITERS = 50; private static final float TOLERANCE = 100*Epsilon.floatValue(); /** x[n] value */ private float xn = Float.NaN; /** previous x[n] value */ private float prevXn; /** g(x[n]) */ private float gn; /** * Constructor. * @param function the functions whose roots to find */ public FixedPointRootFinder(Function function) { super(function, MAX_ITERS); } /** * Reset. * @param x0 the initial x-value */ public void reset(float x0) { super.reset(); gn = x0; } //---------// // Getters // //?a--------// /** * Return the current value of x[n]. * @return the value */ public float getXn() { return xn; } /** * Return the current value of g(x[n]). * @return the value */ public float getGn() { return gn; } //-----------------------------// // RootFinder method overrides // //?a----------------------------// /** * Do the fixed point iteration procedure. (Nothing to do!) * @param n the iteration count */ protected void doIterationProcedure(int n) {} /** * Compute the next position of xn. */ protected void computeNextPosition() { prevXn = xn; xn = gn; gn = function.at(xn); } /** * Check the position of xn. * @throws PositionUnchangedException */ protected void checkPosition() throws RootFinder.PositionUnchangedException { if (xn == prevXn) { throw new RootFinder.PositionUnchangedException(); } } /** * Indicate whether or not the algorithm has converged. * @return true if converged, else false */ protected boolean hasConverged() { return Math.abs((gn - xn)/xn) < TOLERANCE; } } As we can see, the class does the least work of all the root-finding classes, but then, of course, we had to work hard ourselves to derive the function g ( x ). Program 5 §C6 instantiates a FixedPointRootFinder object. Screen 5-6a is a screen shot of the interactive version of the program performing fixed-point iteration on the function . Like the interactive version of Program 5 §C5 for Newton's method, it allows you to dynamically set the starting value for x by dragging the mouse along the x axis. Screen 5-6a. Fixed-point iteration applied to the function with the initial value x = 10.325. This screen shot is from the interactive version of Program 5 §C6.  In Screen 5-6a, we see that, if the initial value for x is negative, fixed-point iteration will find the other fixed-point value of -2, which is the other root of f ( x ) = x 2 - 4. The noninteractive version of Program 5 §C6, which performs fixed-point iteration also on the function , shows that the convergence of the fixed-point algorithm is not as good as that of Newton's algorithm, especially in the spiral case. See Listing 5-6b. Listing 5-6b The noninteractive version of Program 5 §C1 applies fixed-point iteration applied to the function with the initial value x = 10.325 and to the function  with the initial value x = -3. package numbercruncher.program5_6; import numbercruncher.mathutils.Function; import numbercruncher.mathutils.FixedPointRootFinder; import numbercruncher.mathutils.AlignRight; import numbercruncher.rootutils.RootFunctions; /** * PROGRAM 5C6: Fixed-Point Iteration * * Demonstrate Fixed-Point Iteration on a function. */ public class FixedPointIteration { /** * Main program. * @param args the array of runtime arguments */ public static void main(String args[]) { doFunction("(x + 4/x)/2", 10.325f); doFunction("exp(1/x)", -3f); } /** * Apply fixed-point iteration to a function. * @param key the function key * @param x0 the starting value */ private static void doFunction(String key, float x0) { try { FixedPointRootFinder finder; AlignRight ar = new AlignRight(); System.out.println("\ng(x) = " + key + "\n"); finder = new FixedPointRootFinder(RootFunctions.function(key)); finder.reset(x0); ar.print("n", 2); ar.print("x[n]", 15); ar.print("g(x[n])", 15); ar.underline(); // Loop until convergence or failure. boolean converged; do { converged = finder.step(); ar.print(finder.getIterationCount(), 2); ar.print(finder.getXn(), 15); ar.print(finder.getGn(), 15); ar.println(); } while (!converged); System.out.println("\nSuccess! Fixed point = " + finder.getXn()); } catch(Exception ex) { System.out.println("***** Error: " + ex); } } } Output: g(x) = (x + 4/x)/2 n x[n] g(x[n]) -------------------------------- 1 10.325 5.3562045 2 5.3562045 3.051501 3 3.051501 2.1811657 4 2.1811657 2.0075238 5 2.0075238 2.000014 6 2.000014 2.0 7 2.0 2.0 Success! Fixed point = 2.0 g(x) = exp(1/x) n x[n] g(x[n]) -------------------------------- 1 -3.0 0.7165313 2 0.7165313 4.0374465 3 4.0374465 1.2810516 4 1.2810516 2.1828005 5 2.1828005 1.5811099 6 1.5811099 1.8822485 7 1.8822485 1.7011074 8 1.7011074 1.8001182 9 1.8001182 1.7428454 10 1.7428454 1.7749537 11 1.7749537 1.7566261 12 1.7566261 1.7669822 13 1.7669822 1.7610966 14 1.7610966 1.7644305 15 1.7644305 1.7625386 16 1.7625386 1.7636112 17 1.7636112 1.7630026 18 1.7630026 1.7633477 19 1.7633477 1.763152 20 1.763152 1.763263 21 1.763263 1.7632 22 1.7632 1.7632357 23 1.7632357 1.7632155 24 1.7632155 1.763227 25 1.763227 1.7632204 Success! Fixed point = 1.763227 Table 5-2. Example functions f ( x ) and derived convergent and nonconvergent iteration functions g ( x ). | f(x) | Roots | Convergent g(x) | Divergent g(x) | | f ( x ) = x 2 - 4 | -2.00 2.00 | |  | | f ( x ) = x 2 - x - 2 | -1.00 2.00 |  | g ( x ) = x 2 - 2 | |  | | | f ( x ) = x - e - x | 0.567 | g ( x ) = e - x | g ( x ) = -ln x | | | 1.76 | |  | |  | | | f ( x ) = 2 x - sin x - 2 | 1.50 |  | | | f ( x ) = x 3 - x 2 - x - 1 | 1.84 |  | | | f ( x ) = x 3 + 2 x 2 + 10 x - 20 | 1.37 |  | | There are several ways to define the iteration function g ( x ) for a given function f ( x ). For the function f ( x ) = x 2 - 4 we could have chosen the simpler function , and for the function  we could have chosen  . Does it matter which definition of g ( x ) to use? If we do not derive the appropriate iteration function g ( x ), the algorithm can diverge, as shown in Screen 5-6b. We must derive g ( x ) such that, for all values of x within an interval that contains the fixed point value, g '( x ) < 1 for the derivative g '( x ). Then the algorithm will converge within that interval to the fixed point. Screen 5-6b. Fixed-point iteration applied to nonconvergent functions and .   Table 5-2 shows examples of functions f ( x ) and corresponding convergent and nonconvergent fixed-point iteration functions g ( x ) that can be derived. You can try all of the iteration functions using the interactive version of Program 5 §C6.  | 