Newton's method calculates the roots of equations. In other words, it finds the values of x for which F(x) = 0.

This program graphs the equation X^3/3 - 2*X + 5. (Actually because Y coordinates on the screen increase from top-to-bottom, the program uses the negative of this equation to make the result look nice on the screen.)

When you click on the graph, the program uses Newton's method to find a root of the equation, starting from the X value that you clicked.

The way Newton's method works is it starts from an initial guess X0 (given by the point you clicked). It then estimates the difference between that value and a root by using the function's derivative dFdx:

    epsilon = -F(x) / dFdx(x)

The method then sets its next guess for x to be the current value plus epsilon (X(n+1) = X(n) + epsilon). It repeats this process until epsilon is smaller than some cutoff value and then stops.

The following code shows how the program uses Newton's method.

// The function.
private float F(float x)
{
    return -(x * x * x / 3 - 2 * x * x + 5);
}

// The function's derivative.
private float dFdx(float x)
{
    return -(x * x - 4 * x);
}

// Find a root by using Newton's method.
private void UseNewtonsMethod(Graphics gr, float x0)
{
    const float cutoff = 0.0000001f;
    const float tiny = 0.00001f;
    const int max_iterations = 100;
    float epsilon;
    int iterations = 0;
    using (StringFormat string_format = new StringFormat())
    {
        string_format.Alignment = StringAlignment.Center;
        using (Pen guess_pen = new Pen(Color.Red, 0))
        {
            do
            {
                // Display this guess x0.
                iterations++;
                gr.DrawString(iterations.ToString(),
                    this.Font, Brushes.Black, x0, iterations,
                    string_format);
                gr.DrawLine(guess_pen, x0, iterations, x0, 0.25f);
                Console.WriteLine(iterations + ": " + x0);

                // Make sure x0 isn't on a flat spot.
                while (Math.Abs(dFdx(x0)) < tiny) x0 += tiny;

                // Calculate the next esxtimate for x0.
                epsilon = -F(x0) / dFdx(x0);
                x0 += epsilon;
            } while ((Math.Abs(epsilon) > cutoff) && (iterations < max_iterations));
            gr.FillEllipse(Brushes.Green, x0 - 0.25f, -0.25f, 0.5f, 0.5f);
        }
    }

    this.Text = x0.ToString() + " +/-" +
        epsilon.ToString() + " in " +
        iterations.ToString() + " iterations";
}

The code is reasonably straightforward. Much of it is to display the guess graphically.

One odd piece checks to see whether the guess is near a flat spot on the curve. If it is, then the derivative is 0 so the program cannot calculate -F(x0) / dFdx(x0) because it would divide by 0. In that case, the program just moves the guess x0 a little until the derivative isn't so close to 0.

Another odd case can occur if the next guess is the same as a previous guess. In that case, the series of guesses forms an infinite loop so the code breaks out after at most 100 guesses. Usually this is far more than necessary.

Finally, note that you can't always tell which root the method will find for a given initial guess. In the figure, the first guess is between the second and third roots but the slope at the curve there makes the next guess closer to the first (leftmost) root. The following guesses then bounce around a bit until they zoom in on that root.

You can use this unpredictability to generate some interesting fractals. I'll post some in the next few days.

(If you need to find all of the equation's roots, you can try applying the method for many initial guesses. (It also helps if you know how many roots you need to find.)