|
|
|
|
Kantorovitch's theorem
|
(Theorem)
|
|
|
Let
 be a point in
 an open neighborhood of
 in  and
 a differentiable mapping, with its derivative
![$ [\mathbf{D}\vec{f}(\mathbf{a}_0)]$](http://images.planetmath.org:8080/cache/objects/790/l2h/img6.png "$ [\mathbf{D}\vec{f}(\mathbf{a}_0)]$") invertible. Define
If
 and the derivative
![$ [\mathbf{D}\vec{f}(\mathbf{x})]$](http://images.planetmath.org:8080/cache/objects/790/l2h/img9.png "$ [\mathbf{D}\vec{f}(\mathbf{x})]$") satisfies the Lipschitz condition
for all points
 , and if the inequality
is satisfied, the equation
 has a unique solution in  , and Newton's method with initial guess
 converges to it. If we replace  with  , then it can be shown that Newton's method superconverges! If you want an even stronger version, one can replace  with the norm
 .
Let's look at the useful part of the theorem:
It is a product of three distinct properties of your function such that the product is less than or equal to a certain number, or bound. If we call the product  , then it says that
 must be within a ball of radius  . It also says that the solution
 is within this same ball. How was this ball defined?
The first term,
 , is a measure of how far the function is from the domain; in the Cartesian plane, it would be how far the function is from the x-axis. Of course, if we're solving for
 , we want this value to be small, because it means we're closer to the axis. However a function can be annoyingly close to the axis, and yet just happily curve away from the axis. Thus we need more.
The second term,
![$ \vert[\mathbf{D}\vec{f}(\mathbf{a_0})]^{-1}\vert^2$](http://images.planetmath.org:8080/cache/objects/790/l2h/img27.png "$ \vert[\mathbf{D}\vec{f}(\mathbf{a_0})]^{-1}\vert^2$") is a little more difficult. This is obviously a measure of how fast the function is changing with respect to the domain (x-axis in the plane). The larger the derivative, the faster it's approaching wherever it's going (hopefully the axis). Thus, we take the inverse of it, since we want this product to be less than a number. Why it's squared though, is because it is the denominator where a product of two terms of like units is the numerator. Thus to conserve units with the numerator, it is multiplied by itself. Combined with the first
term, this also seems to be enough, but what if the derivative changes sharply, but it changes the wrong way?
The third term is the Lipschitz ratio  . This measures sharp changes in the first derivative, so we can be sure that if this is small, that the function won't try to curve away from our goal on us too sharply.
By the way, the number
 is unitless, so all the units on the left side cancel. Checking units is essential in applications, such as physics and engineering, where Newton's method is used.
|
"Kantorovitch's theorem" is owned by stevecheng. [ full author list (3) | owner history (3) ]
|
|
(view preamble)
Cross-references: side, first derivative, ratio, Lipschitz, numerator, denominator, inverse, curve, axis, plane, domain, term, radius, ball, bound, number, function, properties, product, norm, even, converges, Newton's method, solution, equation, inequality, invertible, derivative, differentiable mapping, neighborhood, open, point
There is 1 reference to this entry.
This is version 21 of Kantorovitch's theorem, born on 2001-11-13, modified 2007-04-29.
Object id is 790, canonical name is KantorovitchsTheorem.
Accessed 4792 times total.
Classification:
| AMS MSC: | 49K10 (Calculus of variations and optimal control; optimization :: Necessary conditions and sufficient conditions for optimality :: Free problems in two or more independent variables) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
![$\displaystyle \vec{h}_0=-[\mathbf{D}\vec{f}(\mathbf{a}_0)]^{-1}\vec{f}(\mathbf{... ...\mathbf{x}\vert\: \vert\mathbf{x}-\mathbf{a}_1\vert\leq \vert\vec{h}_0\vert\}. $](http://images.planetmath.org:8080/cache/objects/790/l2h/img7.png "$\displaystyle \vec{h}_0=-[\mathbf{D}\vec{f}(\mathbf{a}_0)]^{-1}\vec{f}(\mathbf{... ...\mathbf{x}\vert\: \vert\mathbf{x}-\mathbf{a}_1\vert\leq \vert\vec{h}_0\vert\}. $"){kind=small}
![$\displaystyle \vert[\mathbf{D}\vec{f}(\mathbf{u}_1)] - [\mathbf{D}\vec{f}(\mathbf{u}_2)]\vert\leq M\vert\mathbf{u}_1-\mathbf{u}_2\vert $](http://images.planetmath.org:8080/cache/objects/790/l2h/img10.png "$\displaystyle \vert[\mathbf{D}\vec{f}(\mathbf{u}_1)] - [\mathbf{D}\vec{f}(\mathbf{u}_2)]\vert\leq M\vert\mathbf{u}_1-\mathbf{u}_2\vert $"){kind=small}
![$\displaystyle \left\vert\vec{f}(\mathbf{a_0})\right\vert\left\vert[\mathbf{D}\vec{f}(\mathbf{a_0})]^{-1}\right\vert^2M\leq\frac{1}{2} $](http://images.planetmath.org:8080/cache/objects/790/l2h/img12.png "$\displaystyle \left\vert\vec{f}(\mathbf{a_0})\right\vert\left\vert[\mathbf{D}\vec{f}(\mathbf{a_0})]^{-1}\right\vert^2M\leq\frac{1}{2} $")
![$\displaystyle \left\vert\vec{f}(\mathbf{a_0})\right\vert\left\vert[\mathbf{D}\vec{f}(\mathbf{a_0})]^{-1}\right\vert^2M\leq\frac{1}{2}. $](http://images.planetmath.org:8080/cache/objects/790/l2h/img20.png "$\displaystyle \left\vert\vec{f}(\mathbf{a_0})\right\vert\left\vert[\mathbf{D}\vec{f}(\mathbf{a_0})]^{-1}\right\vert^2M\leq\frac{1}{2}. $")