Kantorovich theorem

Kantorovich theorem

The Kantorovich theorem is a mathematical statement on the convergence of Newton's method. It was first stated by Leonid Kantorovich in 1940.

Newton's method constructs a sequence of points that—with good luck—will converge to a solution x of an equation f(x) = 0 or a vector solution of a system of equation F(x) = 0. 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.

Contents

Assumptions

Let X\subset\R^n be an open subset and F:\R^n\supset X\to\R^n a differentiable function with a Jacobian F^{\prime}(x) that is locally Lipschitz continuous (for instance if it is twice differentiable). That is, it is assumed that for any open subset U\subset X there exists a constant L > 0 such that for any \mathbf x,\mathbf y\in U

\|F'(\mathbf x)-F'(\mathbf y)\|\le L\;\|\mathbf x-\mathbf y\|

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 v\in\R^n the inequality

\|F'(\mathbf x)(v)-F'(\mathbf y)(v)\|\le L\;\|\mathbf x-\mathbf y\|\,\|v\|

must hold.

Now choose any initial point \mathbf x_0\in X. Assume that F'(\mathbf x_0) is invertible and construct the Newton step \mathbf h_0=-F'(\mathbf x_0)^{-1}F(\mathbf x_0).

The next assumption is that not only the next point \mathbf x_1=\mathbf x_0+\mathbf h_0 but the entire ball B(\mathbf x_1,\|\mathbf h_0\|) is contained inside the set X. Let M\le L be the Lipschitz constant for the Jacobian over this ball.

As a last preparation, construct recursively, as long as it is possible, the sequences (\mathbf x_k)_k, (\mathbf h_k)_k, k)k according to

\begin{alignat}{2}
\mathbf h_k&=-F'(\mathbf x_k)^{-1}F(\mathbf x_k)\\[0.4em]
\alpha_k&=M\,\|F'(\mathbf x_k)^{-1}\|\,\|h_k\|\\[0.4em]
\mathbf x_{k+1}&=\mathbf x_k+\mathbf h_k.
\end{alignat}

Statement

Now if \alpha_0\le\tfrac12 then

  1. a solution \mathbf x^* of F(\mathbf x^*)=0 exists inside the closed ball \bar B(\mathbf x_1,\|\mathbf h_0\|) and
  2. the Newton iteration starting in \mathbf x_0 converges to \mathbf x^* with at least linear order of convergence.

A statement that is more precise but slightly more difficult to prove uses the roots t^\ast\le t^{**} of the quadratic polynomial


p(t)
  =\left(\tfrac12L\|F'(\mathbf x_0)^{-1}\|^{-1}\right)t^2
    -t+\|\mathbf h_0\|
,
t^{\ast/**}=\frac{2\|\mathbf h_0\|}{1\pm\sqrt{1-2\alpha}}

and their ratio


\theta
  =\frac{t^*}{t^{**}}
  =\frac{1-\sqrt{1-2\alpha}}{1+\sqrt{1-2\alpha}}.

Then

  1. a solution \mathbf x^* exists inside the closed ball \bar B(\mathbf x_1,\theta\|\mathbf h_0\|)\subset\bar B(\mathbf x_0,t^*)
  2. it is unique inside the bigger ball B(\mathbf x_0,t^{*\ast})
  3. and the convergence to the solution of F is dominated by the convergence of the Newton iteration of the quadratic polynomial p(t) towards its smallest root t^\ast[1], if t_0=0,\,t_{k+1}=t_k-\tfrac{p(t_k)}{p'(t_k)}, then
    \|\mathbf x_{k+p}-\mathbf x_k\|\le t_{k+p}-t_k.
  4. The quadratic convergence is obtained from the error estimate[2]
    
  \|\mathbf x_{n+1}-\mathbf x^*\|
    \le \theta^{2^n}\|\mathbf x_{n+1}-\mathbf x_n\|
    \le\frac{\theta^{2^n}}{2^n}\|\mathbf h_0\|.

Notes

  1. ^ Ortega, J. M. (1968). "The Newton-Kantorovich Theorem". Amer. Math. Monthly 75 (6): 658–660. JSTOR 2313800. 
  2. ^ Gragg, W. B.; Tapia, R. A. (1974). "Optimal Error Bounds for the Newton-Kantorovich Theorem". SIAM Journal on Numerical Analysis 11 (1): 10–13. JSTOR 2156425. 

References

Literature

  • Kantorowitsch, L. (1948): Functional analysis and applied mathematics (russ.). UMN3, 6 (28), 89–185.
  • Kantorowitsch, L. W.; Akilow, G. P. (1964): Functional analysis in normed spaces.
  • P. Deuflhard: Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms., Springer, Berlin 2004, ISBN 3-540-21099-7 (Springer Series in Computational Mathematics, Vol. 35)

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Nash embedding theorem — The Nash embedding theorems (or imbedding theorems), named after John Forbes Nash, state that every Riemannian manifold can be isometrically embedded into some Euclidean space. Isometric means preserving the length of every path. For instance,… …   Wikipedia

  • List of mathematics articles (K) — NOTOC K K approximation of k hitting set K ary tree K core K edge connected graph K equivalence K factor error K finite K function K homology K means algorithm K medoids K minimum spanning tree K Poincaré algebra K Poincaré group K set (geometry) …   Wikipedia

  • List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

  • Liste de théorèmes — par ordre alphabétique. Pour l établissement de l ordre alphabétique, il a été convenu ce qui suit : Si le nom du théorème comprend des noms de mathématiciens ou de physiciens, on se base sur le premier nom propre cité. Si le nom du théorème …   Wikipédia en Français

  • Newton's method — In numerical analysis, Newton s method (also known as the Newton–Raphson method), named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots (or zeroes) of a real valued function. The… …   Wikipedia

  • Mathematical economics — Economics …   Wikipedia

  • List of Russian people — The Millennium of Russia monument in Veliky Novgorod, featuring the statues and reliefs of the most celebrated people in the first 1000 years of Russian history …   Wikipedia

  • List of Russian mathematicians — Andrey Kolmogorov, a preeminent 20th century mathematician. This list of Russian mathematicians includes the famous mathematicians from the Russian Empire, the Soviet Union and the Russian Federation. This list is incomplete; you can help by …   Wikipedia

  • Linear programming — (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.… …   Wikipedia

  • List of important publications in mathematics — One of the oldest surviving fragments of Euclid s Elements, found at Oxyrhynchus and dated to circa AD 100. The diagram accompanies Book II, Proposition 5.[1] This is a list of important publications in mathematics, organized by field. Some… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”