Newton's method
Newton’s method or Newton-Raphson method is an iterative numerical method used to solve f(x)=0 type equations. It relies on the fixed-point method and on a particular function, g, related to the derivative of f.
Definition
Newton’s method is a fixed-point method using the application $g$:
\[g(x)=x-\displaystyle\frac{f(x)}{f'(x)}\]It can be easily inferred that looking for a fixed point for $g$ comes down to looking for a solution to the following equation
\[f(x)=0\quad (E).\]Remember that, in order to look for the fixed point, we resort to an iterative algorithm defined by the sequence
\[x_{n+1}=g(x_n)\]The numerical scheme for Newton’s method is
\[x_{n+1}=x_n-\displaystyle\frac{f(x_n)}{f'(x_n)}\]Geometrical interpretation
The tangent to the curve f at the point $(x_n,f(x_n))$ has the following equation
\[y=f(x_n)+f'(x_n)(x-x_n)\]$x_{n+1}$ is nothing less than the abscissa of the point of intersection of this tangent with the $x$-axis. Indeed
\[\begin{array}{lcl} y&=&0\\ x&=&x_n-\displaystyle\frac{f(x_n)}{f'(x_n)} \end{array}\]We then set $x_{n+1}$:
\[x_{n+1}=x_n-\displaystyle\frac{f(x_n)}{f'(x_n)}\]Convergence of Newton’s method
Theorem.
Let $f\in\mathcal{C}^2([a,b])$ and $x_*\in]a,b[$ such that
\[f(x_*)=0\]and
\[f'(x_*)\neq 0\]Then, there exists $\delta>0$ such that Newton’s method converges for all $x_0\in I_\delta=[x_*-\delta,x_*-\delta]$
Proof.
By assumption, $f’$ is continuous and $f’(x_*)\neq 0$. Therefore, there exists $\eta>0$ such that:
\[f'(x)\neq 0 \quad \forall x \in[x_*-\eta,x_*-\eta]\subset [a,b]\]The derivative of $g$ is defined by:
\[g'(x)=(x-\displaystyle\frac{f(x)}{f'(x)})'=\displaystyle\frac{f(x)f''(x)}{f'(x)^2}\]By assumption, $f(x_*)=0$ and $f’(x_*)\neq 0$. Consequently:
\[g'(x_*)=0\]Moreover, $g’$ is continuous in $[x_*-\eta,x_*-\eta]$ since
\[f'(x)\neq 0 \quad \forall x \in[x_*-\eta,x_*-\eta]\subset [a,b]\]Explicitly writing the continuity of $g’$ at $x_*$ in the interval $[x_*-\eta,x_*-\eta]$ yields to:
\[\forall \varepsilon >0 \quad |x-x*|\leq \eta \Longrightarrow |g'(x)-g'(x_*)|\leq\varepsilon\]that is
\[\forall \varepsilon >0 \quad |x-x*|\leq \eta \Longrightarrow |g'(x)|\leq\varepsilon\]Therefore, there exists $\delta<\eta$ such that
\[|g'(x)|\leq\tau,\quad\forall x\in I_\delta=[x_*-\delta,x_*-\delta],\quad\tau\in]0,1[.\]Up to now, we have proved one of the assumptions for the fixed-point theorem. We now need to prove that the interval $l_\delta$ is $g$-invariant. That is:
\[g(I_\delta)\subset I_\delta\]By means of the mean value theorem, we show that there exists an element $\xi\in]x,x_*[$ such that
\[\begin{array}{ccl} |g(x)-g(x_*)|&=&|g'(\xi)||x-x_*|\leq\tau|x-x_*|<|x-x_*|\\ |g(x)-x_*)|&<&|x-x_*| \end{array}\]hence
\[g(I_\delta)\subset I_\delta\]To sum up, we have proven that:
- $g\in\mathcal{C}^1(I_\delta)$ et $g(I_\delta)\subset I_\delta$
- there exists a constant $\tau$ in ] 0,1[ such that $|g’(x)|\leq \tau$. Via the fixed-point theorem, we can conclude that: the sequence defined by $x_{n+1} = g(x_n )$ converges toward $x_*$, the fixed point of $g$ $\forall x_0\in I_\delta$.
Order of convergence of Newton’s method
Theorem.
If
- $g’(x_*)=0$
- $g''$ is continuous on an open set $\mathcal{O}$ containing $x_*$
- $g''(x_*)\neq 0$
then, there exists $\delta>0$ such that the sequence defined by $x_{n+1} = g(x_n )$ converges toward $x_*$, the fixed point of $g$, $\forall x_0\in I_\delta=[x_*-\delta,x_*-\delta]$. Newton’s method has a $2^{nd}$-order convergence. The convergence is quadratic.
Proof.
Similar to what we have seen previously, we show that there exists $\delta>0$and $\tau\in]0,1[$ such that
\[|g'(x)|\leq\tau,\quad\forall x \in I_\delta=[x_*-\delta,x_*-\delta] \subset\mathcal{O}\]Since $g’(x_*)=0$, we introduce Taylor series for the function $g$ of the second order in the neighborhood of $x_*$. We obviously use the fact that $e_n=x_n-x_*$ approaches 0.
\[\begin{array}{ccl} x_{n+1}&=&g(x_n)\\ &=&g(e_n+x_*)\\ &=&g(x_*)+e_ng'(x_*)+\displaystyle\frac{e_n^2}{2!}g''(\xi_n)\\ &=&x_*+0+\displaystyle\frac{e_n^2}{2!}g''(\xi_n)\\ &=&x_*+\displaystyle\frac{e_n^2}{2!}g''(\xi_n)\\ \end{array}\]where $\xi_n\in]x_*,e_n+x_*[=]x_*,x_n[$. Hence:
\[e_{n+1}=x_{n+1}-x_*=\displaystyle\frac{e_n^2}{2!}g''(\xi_n)\]and
\[\lim_{n\to\infty}\frac{|e_{n+1}|}{|e_{n}|^2}=|\frac{g''(x_*)}{2}|\]The asymptotic error constant is
\[C=\displaystyle|\frac{g''(x_*)}{2}|\]The convergence is quadratic; that is, of the $2^{nd}$-order since by assumption $g''(x_*)\neq 0$.
Multiplicity of a root
Let $p\in\mathbf{N}$. f is said to have root of multiplicity (or order) $p$ if
\[\begin{array}{lcl} f(x_*)&=&f'(x_*)=f''(x_*)=f^{(3)}(x_*)=\ldots=f^{(p-1)}(x_*)=0\\ f^{(p)}(x_*)&\neq& 0 \end{array}\]and $f$ can be written as follows:
\[f(x)=(x-x_*)^ph(x)\]where $h(x_*)\neq0$.
Convergence of Newton’s method: simple root
Theorem.
If $f\in\mathcal{C}^2([a,b])$ and $f$ has a simple root, then Newton’s method converges quadratically ($2^{nd}$ order), at least.
Proof.
If $f$ has a simple root, then:
\[\begin{array}{lcl} f(x_*)&=&0\\ f^{'}(x_*)&\neq& 0 \end{array}\]Newton’s method converges. The derivative of $g$ is defined by:
\[g'(x)=(x-\displaystyle\frac{f(x)}{f'(x)})'=\displaystyle\frac{f(x)f''(x)}{f'(x)^2}\]The second derivative of $g$ is defined by:
\[g''(x)=\displaystyle\frac{f'(x)^3f''(x) + f'(x)^2f(x)f^{(3)}(x) - 2 f'(x) f''^2(x)f(x) }{f'(x)^4}\]and
\[g''(x_*)=\displaystyle\frac{f''(x_*)}{f'(x_*)}\]If $f''(x_*)\neq 0$ then
- $g’(x_*)=0$
- $g''$ is continuous on an open set $\mathcal{O}$ containing $x_*$
- $g''(x_*)\neq0$
If $f''(x_*)=0$, then $g''(x_*)=0$. It is required to deepen the investigation by introducing Taylor series of the $3^{rd}$ in the neighborhood of $x_*$ of the function $g$. Obviously, $e_n$ approaches 0. This gives
\[\begin{array}{ccl} x_{n+1}&=&g(x_n)\\ &=&g(e_n+x_*)\\ &=&g(x_*)+e_ng'(x_*)+\displaystyle\frac{e_n^2}{2!}g''(x_*) +\displaystyle\frac{e_n^3}{3!}g^{(3)}(\xi_n)\\ &=&x_*+0+0 +\displaystyle\frac{e_n^3}{3!}g^{(3)}(\xi_n)\\ &=&x_*+\displaystyle\frac{e_n^3}{3!}g^{(3)}(\xi_n)\\ \end{array}\]where $\xi_n\in]x_*,e_n+x_*[=]x_*,x_n[$. Hence:
\[e_{n+1}=x_{n+1}-x_*=\displaystyle\frac{e_n^3}{3!}g^{(3)}(\xi_n)\]and
\[\lim_{n\to\infty}\frac{|e_{n+1}|}{|e_{n}|^3}=|\displaystyle\frac{g^{(3)}(x_*)}{3!}|\]The asymptotic error constant is
\[C=\displaystyle|\frac{g^{(3)}(x_*)}{3!}|\]and the convergence is cubic if $g^{(3)}(x_*)\neq 0$; that is, of the $3^{rd}$ order. If $g^{(3)}(x_*)=0$, a Taylor series of the $4^{th}$-order of $g$ in the neighborhood of $x_*$ is required.
We have therefore proved that the convergence of Newton’s method is at least quadratic.
Convergence of Newton’s method: multiple root
Theorem.
Assume that $f$ has a root of multiplicity $p$. Then, Newton’s method converges linearly ($1^{st}$-order) and the asymptotic error constant is:
\[C=1-\frac{1}{p}\]Proof.
$f$ has a root of multiplicity $p\geq 2$. Consequently, there exists an application $h$ such that:
\[f(x)=(x-x_*)^ph(x)\]where $h(x_*)\neq0$.
The derivative $g’$ of $g$ is defined by:
\[\begin{array}{ccl} g'(x)=1&-&\displaystyle\frac{(ph(x)+(x-x_*)h'(x))(h(x)+ (x-x_*)h'(x))}{(ph(x)+(x-x_*)h'(x))^2}\\ &+& \displaystyle\frac{(x-x_*)h(x)(ph'(x)+h'(x)+(x-x_*)h''(x))}{(ph(x)+(x-x_*)h'(x))^2} \end{array}\]Thereafter:
\[g'(x_*)=1-\frac{1}{p}\]therefore: $g’(x_*)\neq 0$ since $p\geq 2$. A $1^{st}$-order Taylor series of the $g$ in the neighborhood of $x_*$gives:
\[\begin{array}{ccl} x_{n+1}&=&g(x_n)\\ &=&g(e_n+x_*)\\ &=&g(x_*)+e_ng'(\xi_n)\\ &=&x_*+e_ng'(\xi_n) \end{array}\]where $\xi_n\in]x_*,e_n+x_*[=]x_*,x_n[$. Hence:
\[e_{n+1}=x_{n+1}-x_*=e_ng'(\xi_n)\]The convergence is of the $1^{st}$-order; ie. linear, since:
\[\lim_{n\to\infty}\frac{|e_{n+1}|}{|e_{n}|}=|g'(x_*)|=|1-\frac{1}{p}|=1-\frac{1}{p}\]with an asymptotic constant
\[C=1-\frac{1}{p}.\]Modified Newton’s method
We have previously seen that when the function $f$ has multiple roots, the order of convergence is deteriorated since only a linear order of convergence is attained. How can we recover a quadratic order – order 2 – of convergence when the roots have a degree of multiplicity $p\geq 2$ ?
This is the aim of the modified Newton’s method.
Definition. The modified Newton’s method of order $p$ is the fixed-point method of the function
\[g(x)=x-p\displaystyle\frac{f(x)}{f'(x)}\]Theorem.
Assume that $f$ has a root whose multiplicity is $p$. Then, the modified Newton’s method converges at least quadratically (order 2)
Proof. The derivative $g’$ of $g$ is defined as follows:
\[\displaystyle \begin{array}{ccl} g'(x)&=&1 - p((ph(x)+(x-x_*)h'(x))(h(x)+(x-x_*)h'(x))\\ &+& (x-x_*)h(x)(ph'(x)+h'(x)+(x-x_*)h''(x)))/((ph(x)+(x-x_*)h'(x))^2) \end{array}\]Thereafter:
\[g'(x_*)=0\]We thus conclude, just like before, that the modified Newton’s is at least quadratic.
If you found this post or this website helpful and would like to support our work, please consider making a donation. Thank you!
Help Us