The Newton-Raphson Method is perhaps the simplest and most efficient method of root-finding except for one compromise: it requires a reasonably accurate initial estimate of the root.

Although this method may seem similar to the secant method as it uses straight lines to approximate the function, the way it derives the root is very different – it uses the tangent at the estimate instead of the secant, relying on the current estimate and its derivative function rather than an interval.

The math

For an equation 𝑓(𝑥) = 0, we choose 𝑥𝑖 as an initial approximation of the root or the estimate from the last iteration. Then through the point (x_i, f(x_i)) to get the tangent L of the curve.

L: y = f(x_i) + f(x_i)'(x-x_i)

Hence, the next iteration can be found by:

x_{i+1} = x_i – \frac{f(x_i)}{f{x_i}’)

Implementation

In NM Dev, the class NewtonRoot implements the Newton-Raphson root-finding algorithm, together with a solve function.

Note that the second solve function allows you to supply the derivative function 𝑓’ for 𝑓. Otherwise, a derivative function computed using finite differencing is automatically
generated by the code (though slower).

				
					UnivariateRealFunction f = new AbstractUnivariateRealFunction() {
 @Override
 public double evaluate(double x) {
 return x * x + 4 * x - 5; // x^2 +4x - 5 = 0
 }
};
UnivariateRealFunction df = new AbstractUnivariateRealFunction() {
 @Override
 public double evaluate(double x) {
 return 2 * x + 4; // 2x + 4
 }
};
NewtonRoot solver = new NewtonRoot(1e-8, 5);
double root = solver.solve(f, df, 5.);
double fx = f.evaluate(root);
System.out.println(String.format("f(%f) = %f", root, fx));
				
			

Output:

f(1.000000) = 0.000000

We can see from the iteration results below that the algorithm already reaches very good result in the 4th iteration, hence very good efficiency.

Iterations ix_i Error
05 
12.1428571431.33E+00
21.1576354688.51E-01
31.0039347391.53E-01
41.0000025773.93E-03
51.0000000000011072.58E-06
60.99999999999999991.11E-12