Théorème de Kantorovitch

Le théorème de Kantorovitch, ou théorème de Newton-Kantorovitch, concerne la convergence de la méthode de Newton dans des espaces de Banach. Il a été énoncé pour la première fois par Leonid Kantorovich en 1948^[1],[2].

La méthode de Newton permet de construire une suite de points qui, sous certaines conditions, converge vers une solution ${\displaystyle x}$ d'une équation ${\displaystyle F(x)=0}$, où ${\displaystyle F}$ est une fonction entre deux espaces de Banach. Le théorème de Kantorovitch donne des conditions qui, si elles sont satisfaites, permettent d'affirmer qu'une solution à l'équation ${\displaystyle F(x)=0}$ existe, et que la suite de la méthode de Newton converge vers cette solution. De plus, il permet de quantifier la vitesse de convergence de la suite.

On considère ${\displaystyle \mathbb {R} ^{n}}$ comme espace vectoriel normé, muni de la topologie issue d'une norme ${\displaystyle \|\cdot \|}$ (par example la norme euclidienne ${\displaystyle \|(x_{1},\dots ,x_{n})\|_{2}={\sqrt {x_{1}^{2}+\dots +x_{n}^{2}}}}$). Soit ${\displaystyle X\subset \mathbb {R} ^{n}}$ un ouvert pour cette topologie et ${\displaystyle F:X\subset \mathbb {R} ^{n}\to \mathbb {R} ^{n}}$ une fonction différentiable, dont la jacobienne ${\displaystyle F^{\prime }(\mathbf {x} )}$ est localement lipschitzienne. (Cela est vérifié, par exemple, si ${\displaystyle F}$ est deux fois dérivable.) Formellement, on suppose que pour tout ${\displaystyle x\in X}$, il existe un ouvert ${\displaystyle U\subset X}$ tel que ${\displaystyle x\in U}$, et il existe une constante ${\displaystyle L>0}$, tels que, pour tout couple ${\displaystyle \mathbf {x} ,\mathbf {y} \in U}$, on a

${\displaystyle \|F'(\mathbf {x} )-F'(\mathbf {y} )\|\leq L\;\|\mathbf {x} -\mathbf {y} \|.}$

La norme à sur ${\displaystyle F^{\prime }(\mathbf {x} )-F^{\prime }(\mathbf {y} )}$ est la norme d'opérateur. En d’autres termes, il suffit de vérifier que, pour tout vecteur ${\displaystyle \mathbf {v} \in \mathbb {R} ^{n}}$, on a

${\displaystyle \|F'(\mathbf {x} )(\mathbf {v} )-F'(\mathbf {y} )(\mathbf {v} )\|\leq L\;\|\mathbf {x} -\mathbf {y} \|\,\|\mathbf {v} \|.}$

Soit ${\displaystyle \mathbf {x} _{0}\in X}$, un point initial quelconque (que l'utilisateur pourra choisir judicieusement). Supposons que ${\displaystyle F'(\mathbf {x} _{0})}$ est inversible et considérons le pas de Newton ${\displaystyle \mathbf {h} _{0}=-F'(\mathbf {x} _{0})^{-1}F(\mathbf {x} _{0}).}$

On suppose que la boule ${\displaystyle B(\mathbf {x} _{1},\|\mathbf {h} _{0}\|)}$ est contenue dans l'ensemble ${\displaystyle X}$. Soit ${\displaystyle M}$ la constante de Lipschitz pour ${\displaystyle F'}$ sur cette boule. On considère alors les suites ${\displaystyle (\mathbf {x} _{k})_{k\in \mathbb {N} }}$, ${\displaystyle (\mathbf {h} _{k})_{k\in \mathbb {N} }}$, ${\displaystyle (\alpha _{k})_{k\in \mathbb {N} }}$ telles que

${\displaystyle {\begin{alignedat}{2}\mathbf {h} _{k}&=-F'(\mathbf {x} _{k})^{-1}F(\mathbf {x} _{k})\\[0.4em]\alpha _{k}&=M\,\|F'(\mathbf {x} _{k})^{-1}\|\,\|\mathbf {h} _{k}\|\\[0.4em]\mathbf {x} _{k+1}&=\mathbf {x} _{k}+\mathbf {h} _{k}.\end{alignedat}}}$

Si ${\displaystyle \alpha _{0}\leq {\tfrac {1}{2}}}$, alors on a les propriétés suivantes.

1. Il existe une unique solution ${\displaystyle \mathbf {x} ^{*}}$ à l'équation ${\displaystyle F(\mathbf {x} ^{*})=0}$ à l'intérieur de la boule fermée ${\displaystyle {\bar {B}}(\mathbf {x} _{1},\|\mathbf {h} _{0}\|)}$.
2. Les itérés de Newton ${\displaystyle (\mathbf {x} _{k})_{k}}$ convergent vers ${\displaystyle \mathbf {x} ^{*}}$, et la convergence est linéaire.

La quantité ${\displaystyle \alpha _{0}=M\|F'(\mathbf {x} _{0})^{-1}||\;\|F'(\mathbf {x} _{0})^{-1}F(\mathbf {x} _{0})\|}$ mesure donc la régularité du problème. Plus ${\displaystyle \alpha _{0}}$ est petit, plus le problème est régulier. Le point ${\displaystyle \mathbf {x} _{0}}$, laissé à la liberté de l'utilisateur, sert d'approximation à ${\displaystyle \mathbf {x} ^{*}}$, et doit donc être choisi de sorte à minimiser autant que possible à la fois la norme d'opérateur ${\displaystyle \|F'(\mathbf {x} _{0})^{-1}||}$, et l'erreur initiale ${\displaystyle \|F'(\mathbf {x} _{0})^{-1}F(\mathbf {x} _{0})\|}$ qui mesure à quel point ${\displaystyle F(\mathbf {x} _{0})}$ est loin de zéro.

Il est possible de caractériser plus précisément la vitesse de convergence de la suite ${\displaystyle (\mathbf {x} _{k})_{k}}$. Soient ${\textstyle t^{\ast }={\frac {2\|\mathbf {h} _{0}\|}{1+{\sqrt {1-2\alpha _{0}}}}}}$ et ${\textstyle t^{**}={\frac {2\|\mathbf {h} _{0}\|}{1-{\sqrt {1-2\alpha _{0}}}}}}$, les racines du polynôme de degré 2 en ${\displaystyle t}$

${\displaystyle p(t)=\left({\tfrac {1}{2}}L\|F'(\mathbf {x} _{0})^{-1}\|^{-1}\right)t^{2}-t+\|\mathbf {h} _{0}\|}$.

On peut remarque que ${\displaystyle 0\leq t^{\ast }\leq t^{**}}$, de sorte que le quotient ${\displaystyle \theta ={\frac {t^{*}}{t^{**}}}={\frac {1-{\sqrt {1-2\alpha _{0}}}}{1+{\sqrt {1-2\alpha _{0}}}}}}$ est strictement inférieur à 1.

Sous les mêmes hypothèses que précédemment, on a alors les propriétés suivantes.

1. Une solution ${\displaystyle \mathbf {x} ^{*}}$ à l'équation ${\displaystyle F(\mathbf {x} ^{*})=0}$ existe à l'intérieur de la boule fermée ${\displaystyle {\bar {B}}(\mathbf {x} _{1},\theta \|\mathbf {h} _{0}\|)\subset {\bar {B}}(\mathbf {x} _{0},t^{*})}$.
2. Cette solution est unique à l'intérieur de la boule ${\displaystyle B(\mathbf {x} _{0},t^{*\ast })}$.
3. La vitesse de convergence vers ${\displaystyle \mathbf {x} ^{*}}$ est dominée par la vitesse de convergence des itérés de Newton du polynôme ${\displaystyle p(t)}$ vers ${\displaystyle t^{\ast }}$^[3]. En effet, soient ${\displaystyle t_{0}=0}$ et ${\displaystyle t_{k+1}=t_{k}-{\tfrac {p(t_{k})}{p'(t_{k})}}}$, alors on a que

   ${\displaystyle \|\mathbf {x} _{k+p}-\mathbf {x} _{k}\|\leq t_{k+p}-t_{k}.}$

4. La vitesse de convergence est alors quadratique. Plus précisément, l'erreur est bornée par ^[4]

   ${\displaystyle \|\mathbf {x} _{n+1}-\mathbf {x} ^{*}\|\leq \theta ^{2^{n}}\|\mathbf {x} _{n+1}-\mathbf {x} _{n}\|\leq {\frac {\theta ^{2^{n}}}{2^{n}}}\|\mathbf {h} _{0}\|.}$

En 1986, Yamamoto a prouvé que les évaluations d'erreur de la méthode de Newton proposées par Doring (1969), Ostrowski (1971, 1973),^[5],[6] Gragg-Tapia (1974), Potra-Ptak (1980),^[7] Miel (1981),^[8] Potra (1984)^[9], peuvent être déduites du théorème de Kantorovich^[10].

Le théorème de Kantorovich se généralise directement au cas où ${\displaystyle F:X\to Y}$, où ${\displaystyle X}$ et ${\displaystyle Y}$ sont des espaces de Banach quelconque^[3].

Il existe également un q -analogue pour le théorème de Kantorovitch^[11],[12]. Pour d'autres généralisations/variations, voir Ortega et Rheinboldt (1970)^[13].

Oishi et Tanabe ont affirmé que le théorème de Kantorovitch peut être appliqué pour obtenir des solutions fiables de programmation linéaire^[14].

• (en) John H. Hubbard et Barbara Burke Hubbard, Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach, Matrix Editions (ISBN 9780971576681, lire en ligne), chap. 2.8 (« Newton's method »)

• Portail de l'analyse