Root Finding: Use Newton Method in given Interval (or alternative?)

calculusnewton raphsonroots

I need to find a root of an equation in a given interval. The Problem is that there are more than one roots.
But only within [0,$\pi$] I'm interested in the solution.

So I implemented a function find_root in my C++ code:

double find_root(std::function<double(double)> func, std::function<double(double)> deriv, const double start_value, const int it_max)
{
   // Implementation of Newton Raphson Method
   double a = start_value;
   double z;
   int it = 0;
   do
   {
      z = a - (func(a) / deriv(a)); // z is root
      a = z; // a is guess
      it++;
   } while (abs(func(z))>0.000001 && it <= it_max);
   if (it == 1000) {
      // doesn't matter...
   }
   return a;
}

Of course this works. But for some examples I receive roots I'm not interested in and not the root I'm looking for because it's outside my interval. So I asked myself is there a general way to use the Newton Method within a certain interval.

I would be thankful for help.

BG
mk3

Best Answer

The problem is that Newton's method will always follow the derivative, which can take you out of the interval you are interested in. Nothing you can do about that... I can give you two solutions:

  1. Assuming there is a single root in your interval, you can use the bissection method, which will always find a root inside of your interval. However, you loose the quadratic convergence of Newton. This could be sort of fixed by doing a mixed Bissection + Newton method: You start with a fixed number of bissection iterates, which brings you close to your solution, and then you use Newton to obtain the tolerance you want. Normally 5/10 iterations of Bissection should more than suffice.

  2. You can also launch several Newton algorithms from different points in your interval (equally spaced, for instance). Some of the solutions you will find will be outside of your interval, but you will most likely get the one you want at some point.

Cheers!

Related Question