The Kantorovich theorem, or Newton–Kantorovich theorem, is a mathematical statement on the semi-local
convergence
Convergence may refer to:
Arts and media Literature
*''Convergence'' (book series), edited by Ruth Nanda Anshen
*Convergence (comics), "Convergence" (comics), two separate story lines published by DC Comics:
**A four-part crossover storyline that ...
of
Newton's method. It was first stated by
Leonid Kantorovich
Leonid Vitalyevich Kantorovich ( rus, Леони́д Вита́льевич Канторо́вич, , p=lʲɪɐˈnʲit vʲɪˈtalʲjɪvʲɪtɕ kəntɐˈrovʲɪtɕ, a=Ru-Leonid_Vitaliyevich_Kantorovich.ogg; 19 January 19127 April 1986) was a Sovie ...
in 1948.
It is similar to the form of the
Banach fixed-point theorem
In mathematics, the Banach fixed-point theorem (also known as the contraction mapping theorem or contractive mapping theorem) is an important tool in the theory of metric spaces; it guarantees the existence and uniqueness of fixed points of certa ...
, although it states existence and uniqueness of a
zero
0 (zero) is a number representing an empty quantity. In place-value notation such as the Hindu–Arabic numeral system, 0 also serves as a placeholder numerical digit, which works by multiplying digits to the left of 0 by the radix, usual ...
rather than a
fixed point.
Newton's method constructs a sequence of points that under certain conditions will converge to a solution
of an equation
or a vector solution of a system of equation
. The Kantorovich theorem gives conditions on the initial point of this sequence. If those conditions are satisfied then a solution exists close to the initial point and the sequence converges to that point.
Assumptions
Let
be an open subset and
a
differentiable function
In mathematics, a differentiable function of one real variable is a function whose derivative exists at each point in its domain. In other words, the graph of a differentiable function has a non-vertical tangent line at each interior point in it ...
with a
Jacobian that is locally
Lipschitz continuous
In mathematical analysis, Lipschitz continuity, named after German mathematician Rudolf Lipschitz, is a strong form of uniform continuity for functions. Intuitively, a Lipschitz continuous function is limited in how fast it can change: there e ...
(for instance if
is twice differentiable). That is, it is assumed that for any
there is an open subset
such that
and there exists a constant
such that for any
:
holds. The norm on the left is some operator norm that is compatible with the vector norm on the right. This inequality can be rewritten to only use the vector norm. Then for any vector
the inequality
:
must hold.
Now choose any initial point
. Assume that
is invertible and construct the Newton step
The next assumption is that not only the next point
but the entire ball
is contained inside the set
. Let
be the Lipschitz constant for the Jacobian over this ball (assuming it exists).
As a last preparation, construct recursively, as long as it is possible, the sequences
,
,
according to
:
Statement
Now if
then
#a solution
of
exists inside the closed ball
and
#the Newton iteration starting in
converges to
with at least linear order of convergence.
A statement that is more precise but slightly more difficult to prove uses the roots
of the quadratic polynomial
:
,
:
and their ratio
:
Then
#a solution
exists inside the closed ball
#it is unique inside the bigger ball
#and the convergence to the solution of
is dominated by the convergence of the Newton iteration of the quadratic polynomial
towards its smallest root
, if
, then
#:
#The quadratic convergence is obtained from the error estimate
#:
Corollary
In 1986, Yamamoto proved that the error evaluations of the Newton method such as Doring (1969), Ostrowski (1971, 1973), Gragg-Tapia (1974), Potra-Ptak (1980), Miel (1981), Potra (1984), can be derived from the Kantorovich theorem.
Generalizations
There is a
''q''-analog for the Kantorovich theorem. For other generalizations/variations, see Ortega & Rheinboldt (1970).
Applications
Oishi and Tanabe claimed that the Kantorovich theorem can be applied to obtain reliable solutions of
linear programming.
References
Further reading
*
John H. Hubbard and
Barbara Burke Hubbard
Barbara Burke Hubbard (born 1948) is an American science journalist, mathematics popularizer, textbook author, and book publisher, known for her books on wavelet transforms and multivariable calculus.
Life
Burke Hubbard is the daughter of ''Los ...
: ''Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach'', Matrix Editions,
preview of 3. edition and sample material including Kant.-thm.
* {{cite book , first=Tetsuro , last=Yamamoto , chapter=Historical Developments in Convergence Analysis for Newton's and Newton-like Methods , pages=241–263 , editor-first=C. , editor-last=Brezinski , editor2-first=L. , editor2-last=Wuytack , title=Numerical Analysis : Historical Developments in the 20th Century , publisher=North-Holland , year=2001 , isbn=0-444-50617-9
Functional analysis
Numerical analysis
Theorems in analysis
Optimization in vector spaces
Optimization algorithms and methods