Home > Mathematics > Numerical solution of nonlinear equations > Newton’s method

Newton’s method

Saturday 30 June 2007, by Astozzia, Nadir SOUALEM

All the versions of this article: [English] [français]

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(x)=x-\displaystyle\frac{f(x)}{f'(x)}$

It can be easily inferred that looking for a fixed point for 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 has the following equation

$x_{n+1}$ is nothing less than the abscissa of the point of intersection of this tangent with the -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

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, 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 is defined by:

$g'(x)=(x-\displaystyle\frac{f(x)}{f'(x)})'=\displaystyle\frac{f(x)f''(x)}{f'(x)^2}$

By assumption, and $f'(x_*)\neq 0$ . Consequently:

Moreover, 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 at 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 -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 , the fixed point of $\forall x_0\in I_\delta$ .

Order of convergence of Newton’s method

Theorem.

If

is continuous on an open set $\mathcal{O}$ containing
$g''(x_*)\neq 0$
then, there exists $\delta>0$ such that the sequence defined by $x_{n+1} = g(x_n )$ converges toward , the fixed point of , $\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 , we introduce Taylor series for the function of the second order in the neighborhood of . We obviously use the fact that 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_*)\neq0$ .

Multiplicity of a root

Let $p\in\mathbf{N}$ . f is said to have root of multiplicity (or order) 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 can be written as follows:

where $h(x_*)\neq0$ .

Convergence of Newton’s method: simple root

Theorem.

If $f\in\mathcal{C}^2([a,b])$ and has a simple root, then Newton’s method converges quadratically ( $2^{nd}$ order), at least.

Proof.

If has a simple root, then:

$\begin{array}{lcl} f(x_*)&=&0\\ f^{'}(x_*)&\neq& 0 \end{array}$

Newton’s method converges.
The derivative of 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 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

is continuous on an open set $\mathcal{O}$ containing
$g''(x_*)\neq0$

If , then . It is required to deepen the investigation by introducing Taylor series of the $3^{rd}$ in the neighborhood of of the function . Obviously, 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 in the neighborhood of 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 has a root of multiplicity . Then, Newton’s method converges linearly ( $1^{st}$ -order) and the asymptotic error constant is:

$C=1-\frac{1}{p}$

Proof.

has a root of multiplicity $p\geq 2$ . Consequently, there exists an application such that:

where $h(x_*)\neq0$ .

The derivative of 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 in the neighborhood of 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 is the fixed-point method of the function

$g(x)=x-p\displaystyle\frac{f(x)}{f'(x)}$

Theorem.

Assume that has a root whose multiplicity is . Then, the modified Newton’s method converges at least quadratically (order 2)

Proof.
The derivative of 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:

We thus conclude, just like before, that the modified Newton’s is at least quadratic.

Any message or comments?

Forum registration required

You must be registered before participating in this forum. Please enter your personal identifier . If you have not yet registered, you must register.

Connection | register | password forgotten?

If you want to help Math-Linux.com project , Send your contributions to our team. Thanks !!!

Links

Newton’s method

Definition

Geometrical interpretation

Convergence of Newton’s method

Order of convergence of Newton’s method

Multiplicity of a root

Convergence of Newton’s method: simple root

Convergence of Newton’s method: multiple root

Modified Newton’s method

Any message or comments?

If you want to help Math-Linux.com project , Send your contributions to our team. Thanks !!!

Mathematics

Also in this section