# Newton method

method of tangents

A method for the approximation of the location of the roots of a real equation

$$\tag{1 } f ( x) = 0,$$

where $f$ is a differentiable function. The successive approximations of Newton's method are computed by the formulas

$$\tag{2 } x ^ {k + 1 } = \ x ^ {k} - [ f ^ { \prime } ( x ^ {k} )] ^ {-} 1 f ( x ^ {k} ),\ \ k = 0, 1 ,\dots .$$

If $f$ is twice continuously differentiable, $x ^ {*}$ is a simple root of (1) and the initial approximation $x ^ {0}$ lies sufficiently close to $x ^ {*}$, then Newton's method has quadratic convergence, that is,

$$| x ^ {k + 1 } - x ^ {*} | \leq \ c | x ^ {k} - x ^ {*} | ^ {2} ,$$

where $c$ is a constant depending only on $f$ and the initial approximation $x ^ {0}$.

Frequently, for the solution of (1) one applies instead of (2) the so-called modified Newton method:

$$\tag{3 } x ^ {k + 1 } = \ x ^ {k} - [ f ^ { \prime } ( x ^ {0} )] ^ {-} 1 f ( x ^ {k} ).$$

Under the same assumptions under which Newton's method has quadratic convergence, the method (3) has linear convergence, that is, it converges with the rate of a geometric progression with denominator less than 1.

In connection with solving a non-linear operator equation $A ( u) = 0$ with an operator $A: B _ {1} \rightarrow B _ {2}$, where $B _ {1}$ and $B _ {2}$ are Banach spaces, a generalization of (2) is the Newton–Kantorovich method. Its formulas are of the form

$$u ^ {k + 1 } = \ u ^ {k} - [ A ^ \prime ( u ^ {k} )] ^ {-} 1 A ( u ^ {k} ),\ \ k = 0, 1 \dots$$

where $A ^ \prime ( u ^ {k} )$ is the Fréchet derivative of $A$ at $u ^ {k}$, which is an invertible operator acting from $B _ {1}$ to $B _ {2}$. Under special assumptions the Newton–Kantorovich method has quadratic convergence, and the corresponding modified method has linear convergence (cf. also Kantorovich process).

I. Newton worked out his method in 1669.

How to Cite This Entry:
Newton method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Newton_method&oldid=47968
This article was adapted from an original article by Yu.A. Kuznetsov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article