Newton-Raphson Root Finding

The Problem

A root of an equation $f$ is any solution $x$ such that $f(x) = 0$. Roots of some equations can be found analytically; e.g. $f(x) = x + 1$, then $x = -1$ is a root which can be proven analytically ($-1 + 1 = 0$.)

However, some functions do not have analytic roots, or the roots are harder to find. Numerical methods have been developed to help find these roots algorithmically.

Newton-Raphson Method

For a given function $f(x)$, estimate $x_0$ near the desired root. Now consider the Taylor expansion of $f(x)$ around $x_0$.

\begin{equation} \eqalign{ f(x) &= f(x_0) + f'(x_0)(x - x_0) + f''(x_0)\frac{(x - x_0)^2}{2} \cdots \cr f(x) &\approx f(x_0) + f'(x_0)(x - x_0) } \label{nr-taylor} \end{equation}

Because we want to find $f(x)=0$, set $x = x_0 - \frac{f(x_0)}{f'(x_0)}$ and plug it into equation \eqref{nr-taylor}:

\begin{equation} \eqalign{ f(x) &= f(x_0) + f'(x_0)(x_0 - \frac{f(x_0)}{f'(x_0)} - x_0) \cr &= f(x_0) - f'(x_0)\frac{f(x_0)}{f'(x_0)} \cr &= f(x_0) - f(x_0) \cr &= 0 } \label{nr-taylor-0} \end{equation}

In more general terms,

\begin{equation} x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}. \label{newton-raphson} \end{equation}

Graphically, $x_{n+1}$ is equivalent to the $x$-intercept of the tangent to $f(x)$ at $x_n$.

Graphical example of the Newton-Raphson root finding method.

To approximate the root, iteratively find $x_{n+1}$ such that $x_{n+1} - x_n < \epsilon$ for some chosen tolerance value $\epsilon$.