Knowledge base dedicated to Linux and applied mathematics.

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

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.

Newton’s method is a fixed-point method using the application :

It can be easily inferred that looking for a fixed point for comes down to looking for a solution to the following equation

Remember that, in order to look for the fixed point, we resort to an iterative algorithm defined by the sequence

The numerical scheme for Newton’s method is

The tangent to the curve f at the point has the following equation

is nothing less than the abscissa of the point of intersection of this tangent with the -axis. Indeed

We then set :

**Theorem.**

Let and such that

and

Then, there exists such that Newton’s method converges for all

**Proof.**

By assumption, is continuous and . Therefore, there exists such that:

The derivative of is defined by:

By assumption, and . Consequently:

Moreover, is continuous in since

Explicitly writing the continuity of at in the interval yields to:

that is

Therefore, there exists such that

Up to now, we have proved one of the assumptions for the fixed-point theorem. We now need to prove that the interval is -invariant. That is:

By means of the mean value theorem, we show that there exists an element

such that

hence

To sum up, we have proven that:

et

there exists a constant in ] 0,1[ such that .

Via the fixed-point theorem, we can conclude that:

the sequence defined by converges toward , the fixed point of .

**Theorem.**

If

is continuous on an open set containing

then, there exists such that the sequence defined by converges toward , the fixed point of , . Newton’s method has a -order convergence. The convergence is **quadratic**.

**Proof.**

Similar to what we have seen previously, we show that there exists and such that

Since , we introduce Taylor series for the function of the second order in the neighborhood of . We obviously use the fact that approaches 0.

where .

Hence:

and

The asymptotic error constant is . The convergence is quadratic; that is, of the -order since by assumption .

Let . f is said to have root of multiplicity (or order) if

and can be written as follows:

where .

**Theorem.**

If and has a simple root, then Newton’s method converges quadratically ( order), at least.

**Proof.**

If has a simple root, then:

Newton’s method converges.

The derivative of is defined by:

The second derivative of is defined by:

and

If

then

is continuous on an open set containing

If , then . It is required to deepen the investigation by introducing Taylor series of the in the neighborhood of of the function . Obviously, approaches 0. This gives

where . Hence:

and

The asymptotic error constant is and the convergence is cubic if ; that is, of the order. If , a Taylor series of the -order of in the neighborhood of is required.

We have therefore proved that the convergence of Newton’s method is at least quadratic.

**Theorem.**

Assume that has a root of multiplicity . Then, Newton’s method converges **linearly** (-order) and the asymptotic error constant is:

**Proof.**

has a root of multiplicity . Consequently, there exists an application such that:

where .

The derivative of is defined by:

Thereafter:

therefore: since . A -order Taylor series of the in the neighborhood of gives:

where . Hence:

The convergence is of the -order; ie.

with an asymptotic constant

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 ? 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

**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:

Thereafter:

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