5.1 Analytical versus Computer Solutions

If the function is linear, then there is at most one root, and we can easily find it analytically with simple algebra. For example, if

then we just have to "do the math":

So 2 is the root of the function 3 x - 6, and finding it is the solution to the problem "Solve the equation 3 x = 6 for x. "

There are even formulas for roots. For the quadratic function f ( x ) = ax ² + bx + c, where a, b, and c are real, and a 0, we can use the quadratic formula we saw in Chapter 1

to obtain the roots. If the discriminant b ² - 4 ac is positive, the two roots are real and unequal . If it's 0, the two roots are real and equal, and if it's negative, the two roots are complex.

If the function f is a general polynomial, we may be able to solve it by factoring. For example, if

then we can factor it to

and so x = 1, x = 3, and x = 2 are all roots.

But how do we program the computer to find roots? An analytical solution, such as by factoring and other algebraic manipulations, is fine to do by hand but difficult to program. The quadratic formula is easy to code, but it's only for quadratic functions.

The algorithms in this chapter take advantage of a computer's computational speed?athey use brute force to find real roots iteratively by using trial and error. If we apply such algorithms intelligently, we'll maximize the chances that the trial x values (the successive approximations ) converge to a root, and converge quickly. We hope that each trial decreases the error.

For each algorithm, we'll first write a simple program that illustrates the technique by printing out the successive approximations to a function's root. Next, we'll use an interactive program that animates the algorithm for a set of functions. You select the function, and then by clicking and dragging the mouse, you can set the value of the first trial value for x and watch the program converge (or fail to converge) to a root of the function.

Before we start looking at the algorithms, we need to create some functions whose roots we're going to find and enter them all into a global function table. Listing 5-0a shows the abstract base class Function in package numbercruncher.mathutils.

Listing 5-0a The abstract base Function class.

package numbercruncher.mathutils;

/**
 * The base class for functions that can have derivatives.
 */
public abstract class Function implements Evaluatable
{
    /**
     * Return the value of the function at x.
     * (Implementation of Evaluatable.)
     * @param x the value of x
     * @return the function value
     */
    public abstract float at(float x);

    /**
     * Return the value of the function's derivative at x.
     * @param x the value of x
     * @return the derivative value
     */
    public float derivativeAt(float x) { return 0; }
}

This base class delegates to its subclasses the implementation of method at() , which will return the value of the function at x. By default, method derivativeAt() returns 0. This method may be overridden by a subclass, where it can return the value of the function's first derivative at x.

Listing 5-0b Interface Evaluatable.

package numbercruncher.mathutils;

/**
 * Interface implement by function classes.
 */
public interface Evaluatable
{
    /**
     * Return the value of the function at x.
     * @param x the value of x
     * @return the value of the function at x
     */
    float at(float x);
}

The base class implements interface Evaluatable in package numbercruncher. mathutils. See Listing 5-0b. This interface specifies the at() method. The interface will be useful when we develop classes that work with different function classes, such as the regression and interpolation function classes in Chapter 6.

Now we're ready to create some Function objects. Listing 5-0c shows parts of class RootFunctions in package numbercruncher.rootutils. It statically creates the function objects and enters them into the global hash table named TABLE.

Listing 5-0c Parts of class RootFunctions , which creates Function objects and enters them into a global hash table.

package numbercruncher.rootutils;

import java.util.Hashtable;
import numbercruncher.mathutils.Function;

/**
 * Load into a global table the functions whose roots we want to find.
 */
public class RootFunctions
{
    /** global function table */
    private static Hashtable TABLE = new Hashtable(32);

    // Enter the functions into the global function table.
    static {
       enterFunctions();
    }

    /**
     * Return the function with the given hash key
     * @param key the hash key
     * @return the function
     */
    public static Function function(String key)
    {
        return (Function) TABLE.get(key);
    }

    /**
     * Enter all the functions into the global function table.
     */
    private static void enterFunctions()
    {
        // Function f(x)  = x^2 - 4
        //          f'(x) = 2x
        TABLE.put(
            "x^2 - 4",
            new Function()
            {
                public float at(float x)
                {
                    return x*x - 4;
                }

                public float derivativeAt(float x)
                {
                    return 2*x;
                }
            });

...

        // Function g(x) = (x + 4/x)/2
        TABLE.put(
            "(x + 4/x)/2",
            new Function()
            {
                public float at(float x)
                {
                    return (x + 4/x)/2;
                }
            });

...

}

The class enters each Function object into TABLE , using a string representation of the function's expression as the hash key. Some of the functions also have a defined first derivative f' ( x ). Given a key, the function() method returns the corresponding Function object from TABLE , or null if the key is invalid.

Table 5-1 shows all the functions created by class RootFunctions. The reason some of the functions are named g will be explained later in this chapter.