Namespaces
Variants
Actions

Difference between revisions of "Newton method"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (MR/ZBL numbers added)
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
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''
 
''method of tangents''
  
 
A method for the approximation of the location of the roots of a real equation
 
A method for the approximation of the location of the roots of a real equation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n0665601.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
f ( x)  = 0,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n0665602.png" /> is a differentiable function. The successive approximations of Newton's method are computed by the formulas
+
where $  f $
 +
is a differentiable function. The successive approximations of Newton's method are computed by the formulas
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n0665603.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
x ^ {k + 1 }  = \
 +
x  ^ {k} -
 +
[ f ^ { \prime } ( x  ^ {k} )]  ^ {-} 1 f ( x  ^ {k} ),\ \
 +
k = 0, 1 ,\dots .
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n0665604.png" /> is twice continuously differentiable, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n0665605.png" /> is a simple root of (1) and the initial approximation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n0665606.png" /> lies sufficiently close to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n0665607.png" />, then Newton's method has quadratic convergence, that is,
+
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,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n0665608.png" /></td> </tr></table>
+
$$
 +
| x ^ {k + 1 } - x  ^ {*} |  \leq  \
 +
c  | x  ^ {k} - x  ^ {*} |  ^ {2} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n0665609.png" /> is a constant depending only on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n06656010.png" /> and the initial approximation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n06656011.png" />.
+
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:
 
Frequently, for the solution of (1) one applies instead of (2) the so-called modified Newton method:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n06656012.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \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.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n06656013.png" /> with an operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n06656014.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n06656015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n06656016.png" /> are Banach spaces, a generalization of (2) is the Newton–Kantorovich method. Its formulas are of the form
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n06656017.png" /></td> </tr></table>
+
$$
 +
u ^ {k + 1 }  = \
 +
u  ^ {k} -
 +
[ A  ^  \prime  ( u  ^ {k} )]  ^ {-} 1 A ( u  ^ {k} ),\ \
 +
k = 0, 1 \dots
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n06656018.png" /> is the [[Fréchet derivative|Fréchet derivative]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n06656019.png" /> at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n06656020.png" />, which is an invertible operator acting from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n06656021.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n06656022.png" />. Under special assumptions the Newton–Kantorovich method has quadratic convergence, and the corresponding modified method has linear convergence (cf. also [[Kantorovich process|Kantorovich process]]).
+
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.
 
I. Newton worked out his method in 1669.
Line 31: Line 79:
 
====References====
 
====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>
 
<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====
 
====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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n066/n066560/n06656023.png" /> equations.
+
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====
 
====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>
 
<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>

Latest revision as of 08:02, 6 June 2020


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