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.

References

[1]	L.V. Kantorovich, "Functional analysis and applied mathematics" Nat. Bur. Sci. Rep. , 1509 (1952) Uspekhi Mat. Nauk , 3 : 6 (1948) pp. 89–185 MR0053389 Zbl 0034.21203
[2]	L.V. Kantorovich, G.P. Akilov, "Functionalanalysis in normierten Räumen" , Akademie Verlag (1964) (Translated from Russian)
[3]	L. Collatz, "Funktionalanalysis und numerische Mathematik" , Springer (1964) MR0165651 Zbl 0139.09802
[4]	M.A. Krasnosel'skii, G.M. Vainikko, P.P. Zabreiko, et al., "Approximate solution of operator equations" , Wolters-Noordhoff (1972) (Translated from Russian) MR385655 Zbl 0231.41024
[5]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian) MR0362811 Zbl 0524.65001

Comments

The Newton method is also known as the Newton–Raphson method, cf., e.g., [a4], Sect. (10.11) for single equations and Sect. (10.13) for systems of $ n $ equations.

References

[a1]	P. Lax, S. Burstein, A. Lax, "Calculus with applications and computing" , New York Univ. Inst. Math. Mech. (1972) MR0354951 Zbl 0264.26002
[a2]	J.E., jr. Dennis, R. Schnable, "Least change secant updates for quasi-Newton methods" SIAM Review , 21 (1979) pp. 443–459 MR0545880 Zbl 0424.65020
[a3]	J.M. Ortega, W.C. Rheinboldt, "Iterative solution of nonlinear equations" , Acad. Press (1970) MR0273810 Zbl 0241.65046
[a4]	F.B. Hildebrand, "Introduction to numerical analysis" , Dover, reprint (1987) pp. Chapt. 8 MR0895822 Zbl 0641.65001