= Newton root-finding iteration
{c}
{title2=$t_{r+1}=t_r-F(t_r)/F'(t_r)$}
The Newton root-finding iteration seeks a <zero of a function> $F$ by repeatedly solving its <tangent line> approximation. At a current guess $t_r$ with <derivative> $F'(t_r)\ne0$, set
$$
0=F(t_r)+F'(t_r)(t_{r+1}-t_r),\qquad t_{r+1}=t_r-\frac{F(t_r)}{F'(t_r)}.
$$
Geometrically, follow the <tangent line> to the horizontal axis, then return to the <function graph> for the next <tangent line>. Close to a suitable <zero of a function>, the error becomes dramatically smaller.https://ocw.mit.edu/courses/18-330-introduction-to-numerical-analysis-spring-2012/5b325bfa56a599794c7196de926844b0_MIT18_330S12_Chapter4.pdf[Laurent Demanet, MIT 18.330, Chapter 4, §4.1, 2012]{ref}
For a concrete <square root> calculation, take the <polynomial> $F(t)=t^2-2$ and start at $t_0=1$. The <Newton root-finding iteration> becomes $t_{r+1}=(t_r+2/t_r)/2$, giving
$$
\begin{array}{c|c|c}
r&t_r&|t_r-\sqrt2|\\\hline
0&1&4.14214\times10^{-1}\\
1&1.5&8.57864\times10^{-2}\\
2&1.416666666667&2.45310\times10^{-3}\\
3&1.414215686275&2.12390\times10^{-6}\\
4&1.414213562375&1.59486\times10^{-12}
\end{array}
$$
The errors use the unrounded iterates. After the first step, each iterate overestimates $\sqrt2$, and the exact identity
$$
t_{r+1}-\sqrt2=\frac{(t_r-\sqrt2)^2}{2t_r}
$$
exhibits <quadratic convergence>: once close, the number of correct decimal digits roughly doubles per step. This speed makes the <Newton root-finding iteration> useful when accurate <derivatives> are available.
\Image[/newton-root-iteration.png]
{title=Newton tangent steps toward a square root and a nonconvergent two-cycle}
Global convergence requires additional care. For the <polynomial> $F(x)=x^3-2x+2$, starting at $x_0=0$ gives $F(0)=2$, $F'(0)=-2$, hence $x_1=1$. Then $F(1)=1$, $F'(1)=1$ gives $x_2=0$. The sequence repeats $0,1,0,1,\ldots$ forever, although a real <polynomial root> lies in $(-2,-1)$ by the <intermediate value theorem>. Neither point in the cycle is a <zero of a function>, and neither has zero <derivative>. A maintained sign-changing interval and fallback <bisection method> can protect a root solver from unsuitable Newton steps.
Back to article page
