View source for Newton method

<!--
n0665601.png
$#A+1 = 23 n = 0
$#C+1 = 23 : ~/encyclopedia/old_files/data/N066/N.0606560 Newton method,
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

''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|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|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|Kantorovich process]]).

I. Newton worked out his method in 1669.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  L.V. Kantorovich,   "Functional analysis and applied mathematics"  ''Nat. Bur. Sci. Rep.'' , '''1509'''  (1952)  ''Uspekhi Mat. Nauk'' , '''3''' :  6  (1948)  pp. 89–185  {{MR|0053389}} {{ZBL|0034.21203}} </TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  L.V. Kantorovich,   G.P. Akilov,   "Functionalanalysis in normierten Räumen" , Akademie Verlag  (1964)  (Translated from Russian)  {{MR|}} {{ZBL|}} </TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  L. Collatz,   "Funktionalanalysis und numerische Mathematik" , Springer  (1964)  {{MR|0165651}} {{ZBL|0139.09802}} </TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  M.A. Krasnosel'skii,   G.M. Vainikko,   P.P. Zabreiko,   et al.,   "Approximate solution of operator equations" , Wolters-Noordhoff  (1972)  (Translated from Russian)  {{MR|385655}} {{ZBL|0231.41024}} </TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  N.S. Bakhvalov,   "Numerical methods: analysis, algebra, ordinary differential equations" , MIR  (1977)  (Translated from Russian)  {{MR|0362811}} {{ZBL|0524.65001}} </TD></TR></table>

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

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P. Lax,   S. Burstein,   A. Lax,   "Calculus with applications and computing" , New York Univ. Inst. Math. Mech.  (1972)  {{MR|0354951}} {{ZBL|0264.26002}} </TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J.E., jr. Dennis,   R. Schnable,   "Least change secant updates for quasi-Newton methods"  ''SIAM Review'' , '''21'''  (1979)  pp. 443–459  {{MR|0545880}} {{ZBL|0424.65020}} </TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J.M. Ortega,   W.C. Rheinboldt,   "Iterative solution of nonlinear equations" , Acad. Press  (1970)  {{MR|0273810}} {{ZBL|0241.65046}} </TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  F.B. Hildebrand,   "Introduction to numerical analysis" , Dover, reprint  (1987)  pp. Chapt. 8  {{MR|0895822}} {{ZBL|0641.65001}} </TD></TR></table>