The Newton-Raphson method

The bisection algorithm is robust but slow: it halves the error at each step, so it gains about one decimal digit every $3{,}3$ iterations. If we know the derivative of $f$ we can build a much faster algorithm: the Newton-Raphson method.

Property — Newton's iteration

Let $f$ be differentiable with derivative $f'$, and let $x_0$ be an initial estimate of a zero. The sequence $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ converges (under reasonable hypotheses) to a zero of $f$. Geometrically: one draws the tangent to the graph of $f$ at the point $(x_n,f(x_n))$ and takes as $x_{n+1}$ the intersection of the tangent with the $x$-axis.

Newton’s method for $f(x)=x^2-2$: from the estimate $x_0$ the tangent meets the $x$-axis at $x_1$, closer to the root $\sqrt{2}$; repeating, one approaches it rapidly.

Links

Topics: Continuita
Concepts: Algoritmo di bisezione · Derivata · Metodo di newton raphson · Retta · Retta tangente
Methods: Newton raphson
Skills: Interpretare grafico · Usare formule