Newton Raphson Method

The Newton-Raphson method is an iterative algorithm for approaching a real or complex root of a function by solving $ f(x) = 0 $

It is based on a local approximation of $ f $ in the vicinity of a point $ x_n $ via Taylor's series expansion at order 1: $ f(x) \approx f(x_n) + f'(x_n)(x - x_n) $

The iteration formula is: $ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $

This method is particularly effective for its quadratic convergence under good initial conditions.

The Newton-Raphson method is preferred for several reasons:

— Local quadratic convergence: when the conditions are met, the error asymptotically satisfies $ | \epsilon_{n+1} | \approx C |\epsilon_n|^2 $, which implies an approximate doubling of the number of correct significant figures at each iteration, once sufficiently close to the root.

— Efficiency: in terms of the number of iterations, it surpasses linearly convergent methods such as bisection.

— Analytical precision: it explicitly exploits the information contained in the derivative.

To maximize the chances of convergence:

— Proximity to the root: the closer $ x_0 $ is to a simple root, the more likely quadratic convergence will be.

— Prior bracketing: use a robust method like bisection to isolate a root, then apply Newton's method to speed up convergence.

— Avoid critical areas: if $ f'(x_0) \approx 0 $, the term $ \frac{f(x_0)}{f'(x_0)} $ becomes very large and can cause divergence.

The method has several limitations:

— Zero or nearly zero derivative: if $ f'(x_n) = 0 $, the iteration is impossible.

— Sensitivity to initialization: a poor choice of $ x_0 $ can lead to divergence or cycles.

— Non-differentiable functions: the method requires at least local differentiability.

— Multiple roots: if $ r $ has multiplicity $ m > 1 $, convergence becomes only linear.

Applied to complex polynomials, the method defines an iterative dynamics in the complex plane.

Each starting point $ z_0 $ converges to a given root (if convergence occurs). The set of points converging to the same root forms a basin of attraction.

Several alternative methods exist, depending on the context:

— Bisection method: Robust but slow (linear convergence), ideal for bracketing a root.

— Secant method: Less sensitive to $ x_0 $, superlinear convergence, but requires two initial estimates.

— Halley's method: Cubic convergence, but more complex to implement (uses the second derivative).

— Quasi-Newton methods (e.g., BFGS): For nonlinear systems, avoiding the explicit calculation of the Jacobian.

— Fixed-point method: Simple but linear convergence, useful for equations of the form $ x = g(x) $.