 Home : Map : Chapter 3 : Java : Tech : Physics : Newton's Methods   Introduction Class Definition Data Fields Methods Constructors Instantiation   Demo 1   Demo 2 Static Members   Demo 3 Value&Reference   Demo 4 Overloading    Demo 5 Wrappers    Demo 6 Autobox/Unbox    Demo 7 Arrays   Demo 8 Exceptions Exercises
 Supplements MoreAboutObjects Creating Types Classes,Objs&JVM Java OOP vs C++ Garbage Collection
 About JavaTech      Codes List      Exercises      Feedback      References      Resources      Tips      Topic Index      Course Guide      What's New

The bisection method works very robustly but often very slowly. A faster approach takes advantage of the derivative of the function to get a pointer to the root.

Newton's method (also called Newton-Raphson method) follows such an approach.

For the value of f(x) at a value of x that we believe is close to the root, we can ask what is an estimate of the distance h to the root? That is, we seek h where If h is small, we can approximate this with a truncation of the Taylor expansion of the function about the point x : which assumes that the function is well behaved. Then for small h the quadratic term can be ignored and solving for h gives Since this approximation will not usually lead immediately to the root, we can create an iterative formula : This formula can provide the root very quickly if

• the initial guess is close and
• the derivative is non-zero and well behaved.

It's best to use the analytical formula for the derivative if it is known.

Discrete Newton (or Secant) Method

If an analytical derivative is not available, then a numerical derivative can substitute for it. The 2 point or central derivative around the point x for small h , This formula is called the discrete Newton method or the secant method. For this method you need two initial values.

Newton's Caveats

Beware the numerical errors that can enter into the Newton methods, especially for the discrete version. If the derivative is large, it means the function is rapidly varying and non-linearly and so the extrapolation to the root may be far off the mark. (It also means the first order truncation of the Taylor expansion is invalid.)

For the 2-point derivative calculation, if f(x+h) and f(x-h)are large values then the difference may be small and cause strong sensitivity to the accuracy of the low order bits. We know from the Chapter 2: Tech : Floating Point that care must be taken when dealing with the precision of floating point numbers.

References & Web Resources

Most introductory numerical computing books cover the Newton methods. See, for example,

Latest update: Dec.15.2003

 Tech OOP in Tech Apps Complex Number Histogram Class   Demo More Wrappers
 Physics OOP in Physics Particle Class Root Finding   Demo 1 Newton Methods   Demo 2 Exercises   Part I Part II Part III Java Core 1  2  3  4  5  6  7  8  9  10  11  12 13 14 15 16 17 18 19 20 21 22 23 24 Supplements 1  2  3  4  5  6  7  8  9  10  11  12 Tech 1  2  3  4  5  6  7  8  9  10  11  12 Physics 1  2  3  4  5  6  7  8  9  10  11  12

Java is a trademark of Sun Microsystems, Inc.