Title: Use Newton's method to find the roots of equations in C#

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 - 2 * X + 5. (Because Y coordinates on the screen increase from top-to-bottom, the program actually 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 one of the equation's roots 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.

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 estimate 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 displays the guess graphically.

One odd piece of the code checks to see whether the guess is near a flat spot on the curve. If it is, then the derivative is close to 0, so the program cannot calculate -F(x0) / dFdx(x0) because that would require dividing 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. To avoid getting stuck, 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 on the right, the first guess is between the second and third roots, but the curve's slope there makes guess 2 far to the left. The following guesses then zoom in on the leftmost root.

You can use this unpredictability to generate some interesting fractals. I'll post some later.

If you need to find all of the equation's roots, you can try applying the method for many initial guesses. For example, you can try using the values of x created by the following for loop.

for (float x = -10; x <= 10; x+= 0.5) { // Try using x as the initial guess. ... }

It also helps if you know how many roots you need to find, so you know when you can stop looking.

Download the example to experiment with it and to see additional details.