# Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

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

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

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

### Geometrical interpretation

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 :

### Convergence of Newton’s method

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 .

### Order of convergence of Newton’s method

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 .

### Multiplicity of a root

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

and can be written as follows:

where .

### Convergence of Newton’s method: simple root

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.

### Convergence of Newton’s method: multiple root

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. linear, since:

with an asymptotic constant

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