Теорема Канторовича

Теорема Канторовича, или теорема Ньютона – Канторовича, представляет собой математическое утверждение о полулокальной сходимости метода метода Ньютона. Впервые это было сформулировано Леонидом Канторовичем в 1948 году. Оно похоже на форму теоремы Банаха о неподвижной точке, хотя и утверждает существование и единственность нуля вместо фиксированной точки.

Метод Ньютона строит последовательность точек, которая при определенных условиях сходится к решению $x\; \{\backslash \; displaystyle\; x\}$уравнения $f\; (x)\; =\; 0\; \{\backslash \; displaystyle\; f\; (x)\; =\; 0\}$или векторное решение системы уравнений $F\; (x)\; =\; 0\; \{\backslash \; displaystyle\; F\; (x)\; =\; 0\}$. Теорема Канторовича дает условия на начальную точку этой последовательности. Если эти условия выполнены, то решение существует близко к начальной точке, и последовательность сходится к этой точке.

• 1 Допущения
• 2 Утверждение
• 3 Следствие
• 4 Обобщения
• 5 Приложения
• 6 Ссылки
• 7 Дополнительная литература

Пусть $X\; \subset \; R\; n\; \{\backslash \; displaystyle\; X\; \backslash \; subset\; \backslash \; mathbb\; \{R\}\; ^\; \{n\}\}$быть открытым подмножеством и $F:\; X\; \subset \; R\; n\; \to \; R\; n\; \{\backslash \; displaystyle\; F:\; X\; \backslash \; subset\; \backslash \; mathbb\; \{R\}\; ^\; \{n\}\; \backslash \; to\; \backslash \; mathbb\; \{R\}\; ^\; \{n\}\}$a дифференцируемая функция с якобианом $F\; \text{'}(x)\; \{\backslash \; displaystyle\; F\; ^\; \{\backslash \; prime\}\; (\backslash \; mathbf\; \{x\})\}$, который локально непрерывный по липшицу (например, если $F\; \{\backslash \; displaystyle\; F\}$дважды дифференцируемый). То есть предполагается, что для любого открытого подмножества $U\; \subset \; X\; \{\backslash \; displaystyle\; U\; \backslash \; subset\; X\}$существует константа $L>0\; \{\backslash \; displaystyle\; L>0\}$такой, что для любого $Икс,\; Y\; \in \; U\; \{\backslash \; Displaystyle\; \backslash \; mathbf\; \{x\},\; \backslash \; mathbf\; \{y\}\; \backslash \; in\; U\}$

$\Vert \; F\; \prime \; (x)\; -\; F\; \prime \; (y)\; \Vert \; \le \; L\; \Vert \; x\; -\; y\; \Vert \; \{\; \backslash \; Displaystyle\; \backslash \; |\; F\; \text{'}(\backslash \; mathbf\; \{x\})\; -F\text{'}\; (\backslash \; mathbf\; \{y\})\; \backslash \; |\; \backslash \; leq\; L\; \backslash ;\; \backslash \; |\; \backslash \; mathbf\; \{x\}\; -\; \backslash \; mathbf\; \{y\}\; \backslash \; |\}$

удерживает. Норма слева - это некоторая операторная норма, совместимая с векторной нормой справа. Это неравенство можно переписать, чтобы использовать только векторную норму. Тогда для любого вектора $v\; \in \; R\; n\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\; v\}\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{n\}\}$выполняется неравенство

$\Vert \; F\; \prime \; (x)\; (v)\; -\; F\; \prime \; (y)\; (v)\; \Vert \; \le \; L\; \Vert \; x\; -\; y\; \Vert \; \Vert \; V\; \Vert \; \{\backslash \; displaystyle\; \backslash \; |\; F\; \text{'}(\backslash \; mathbf\; \{x\})\; (\backslash \; mathbf\; \{v\})\; -F\text{'}\; (\backslash \; mathbf\; \{y\})\; (\backslash \; mathbf\; \{v\})\; \backslash \; |\; \backslash \; leq\; L\; \backslash ;\; \backslash \; |\; \backslash \; mathbf\; \{x\}\; -\; \backslash \; mathbf\; \{y\}\; \backslash \; |\; \backslash ,\; \backslash \; |\; \backslash \; mathbf\; \{v\}\; \backslash \; |\}$

должен держать.

Теперь выберите любую начальную точку $x\; 0\; \in \; X\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; \_\; \{0\}\; \backslash \; in\; X\}$. Предположим, что $F\; \prime \; (x\; 0)\; \{\backslash \; displaystyle\; F\; \text{'}(\backslash \; mathbf\; \{x\}\; \_\; \{0\})\}$обратимо, и построим шаг Ньютона $h\; 0\; =\; -\; F\; \prime \; (x\; 0)\; -\; 1\; F\; (x\; 0).\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{h\}\; \_\; \{0\}\; =\; -\; F\; \text{'}(\backslash \; mathbf\; \{x\}\; \_\; \{0\})\; ^\; \{-\; 1\}\; F\; (\backslash \; mathbf\; \{x\}\; \_\; \{0\}).\}$

следующее предположение состоит в том, что не только следующая точка $x\; 1\; =\; x\; 0\; +\; h\; 0\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; \_\; \{1\}\; =\; \backslash \; mathbf\; \{x\}\; \_\; \{0\}\; +\; \backslash \; mathbf\; \{h\}\; \_\; \{\; 0\}\}$, но весь мяч $B\; (x\; 1,\; \Vert \; h\; 0\; \Vert )\; \{\backslash \; displaystyle\; B\; (\backslash \; mathbf\; \{x\}\; \_\; \{1\},\; \backslash \; |\; \backslash \; mathbf\; \{h\}\; \_\; \{\; 0\}\; \backslash \; |)\}$содержится внутри набора $X\; \{\backslash \; displaystyle\; X\}$. Пусть $M\; \le \; L\; \{\backslash \; displaystyle\; M\; \backslash \; leq\; L\}$- константа Липшица для якобиана над этим шаром.

В качестве последней подготовки постройте рекурсивно, насколько это возможно, последовательности $(xk)\; k\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{x\}\; \_\; \{k\})\; \_\; \{k\}\}$, $(hk)\; к\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{h\}\; \_\; \{k\})\; \_\; \{k\}\}$, $(\alpha \; k)\; k\; \{\backslash \; displaystyle\; (\backslash \; alpha\; \_\; \{k\})\; \_\; \{k\}\}$согласно

$hk\; =\; -\; F\; \prime \; (xk)\; -\; 1\; F\; (xk)\; \alpha \; k\; =\; M\; \Vert \; F\; \prime \; (xk)\; -\; 1\; \Vert \; \Vert \; hk\; \Vert \; xk\; +\; 1\; =\; xk\; +\; hk.\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{alignat\}\; \{2\}\; \backslash \; mathbf\; \{h\}\; \_\; \{k\}\; =\; -\; F\; \text{'}(\backslash \; mathbf\; \{x\}\; \_\; \{k\})\; ^\; \{-\; 1\}\; F\; (\backslash \; mathbf\; \{x\}\; \_\; \{k\})\; \backslash \backslash \; [0.4em]\; \backslash \; alpha\; \_\; \{k\}\; =\; M\; \backslash ,\; \backslash \; |\; F\; \text{'}(\backslash \; mathbf\; \{x\}\; \_\; \{k\})\; ^\; \{-\; 1\}\; \backslash \; |\; \backslash ,\; \backslash \; |\; \backslash \; mathbf\; \{\; h\}\; \_\; \{k\}\; \backslash \; |\; \backslash \backslash \; [0.4em]\; \backslash \; mathbf\; \{x\}\; \_\; \{k\; +\; 1\}\; =\; \backslash \; mathbf\; \{x\}\; \_\; \{k\}\; +\; \backslash \; mathbf\; \{h\}\; \_\; \{k\}.\; \backslash \; end\; \{\; alignat\}\}\}$

Теперь, если $\alpha \; 0\; \le \; 1\; 2\; \{\backslash \; displaystyle\; \backslash \; alpha\; \_\; \{0\}\; \backslash \; leq\; \{\backslash \; tfrac\; \{1\}\; \{2\}\}\}$, затем

1. решение $x\; \ast \; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; ^\; \{*\}\}$из $F\; (x\; \ast )\; =\; 0\; \{\backslash \; displaystyle\; F\; (\backslash \; mathbf\; \{x\}\; ^\; \{*\})\; =\; 0\}$существует внутри замкнутого шара $B\; ¯\; (x\; 1,\; \Vert \; h\; 0\; \Vert )\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{B\}\}\; (\backslash \; mathbf\; \{\; x\}\; \_\; \{1\},\; \backslash \; |\; \backslash \; mathbf\; \{h\}\; \_\; \{0\}\; \backslash \; |)\}$и
2. итерация Ньютона, начиная с $x\; 0\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; \_\; \{0\}\}$сходится к $x\; \ast \; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; ^\; \{*\}\}$как минимум с линейным порядком сходимости.

В более точном, но немного более сложном для доказательства утверждении используются корни $t\; \ast \; \le \; t\; \ast \; \ast \; \{\backslash \; displaystyle\; t\; ^\; \{\backslash \; ast\}\; \backslash \; leq\; t\; ^\; \{**\}\}$из квадратичный полином al

$п\; (t)\; =\; (1\; 2\; L\; \Vert \; F\; \prime \; (x\; 0)\; -\; 1\; \Vert \; -\; 1)\; t\; 2\; -\; t\; +\; \Vert \; час\; 0\; \Vert \; \{\backslash \; displaystyle\; p\; (t)\; =\; \backslash \; left\; (\{\backslash \; tfrac\; \{\; 1\}\; \{2\}\}\; L\; \backslash \; |\; F\; \text{'}(\backslash \; mathbf\; \{x\}\; \_\; \{0\})\; ^\; \{-\; 1\}\; \backslash \; |\; ^\; \{-\; 1\}\; \backslash \; right)\; t\; ^\; \{2\}\; -t\; +\; \backslash \; |\; \backslash \; mathbf\; \{h\; \}\; \_\; \{0\}\; \backslash \; |\}$,

$t\; \ast \; /\; \ast \; \ast \; =\; 2\; \Vert \; час\; 0\; \Vert \; 1\; \pm \; 1-2\; \alpha \; \{\backslash \; displaystyle\; t\; ^\; \{\backslash \; ast\; /\; **\}\; =\; \{\backslash \; frac\; \{2\; \backslash \; |\; \backslash \; mathbf\; \{h\}\; \_\; \{0\}\; \backslash \; |\}\; \{1\; \backslash \; pm\; \{\backslash \; sqrt\; \{1-2\; \backslash \; alpha\}\}\}\}\}$

и их соотношение

$\theta \; =\; t\; \ast \; t\; \ast \; \ast \; =\; 1\; -\; 1\; -\; 2\; \alpha \; 1\; +\; 1\; -\; 2\; \alpha .\; \{\backslash \; displaystyle\; \backslash \; theta\; =\; \{\backslash \; frac\; \{t\; ^\; \{*\}\}\; \{t\; ^\; \{**\}\}\}\; =\; \{\backslash \; frac\; \{1\; -\; \{\backslash \; sqrt\; \{1-2\; \backslash \; alpha\}\}\}\; \{1\; +\; \{\backslash \; sqrt\; \{1-2\; \backslash \; alpha\}\}\}\}.\}$

Тогда

1. решение $x\; \ast \; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; ^\; \{*\}\}$существует внутри замкнутого шара $В\; ¯\; (Икс\; 1,\; \theta \; \Vert \; час\; 0\; \Vert )\; \subset \; B\; ¯\; (x\; 0,\; t\; \ast )\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{B\}\}\; (\backslash \; mathbf\; \{x\}\; \_\; \{1\},\; \backslash \; theta\; \backslash \; |\; \backslash \; mathbf\; \{h\}\; \_\; \{0\}\; \backslash \; |)\; \backslash \; subset\; \{\backslash \; bar\; \{B\}\}\; (\backslash \; mathbf\; \{x\}\; \_\; \{0\},\; t\; ^\; \{*\})\}$
2. он уникален внутри большего шара $B\; (x\; 0,\; t\; \ast \; \ast )\; \{\backslash \; displaystyle\; B\; (\backslash \; mathbf\; \{x\}\; \_\; \{0\},\; t\; ^\; \{*\; \backslash \; ast\})\}$
3. и сходимость к решению $F\; \{\; \backslash \; displaystyle\; F\}$определяется сходимостью итерации Ньютона квадратного многочлена $p\; (t)\; \{\backslash \; displaystyle\; p\; (t)\}$к его наименьшему корню $t\; \ast \; \{\backslash \; displaystyle\; t\; ^\; \{\backslash \; ast\}\}$, если $t\; 0\; =\; 0,\; tk\; +\; 1\; =\; tk\; -\; p\; (tk)\; p\; \prime \; (tk)\; \{\backslash \; displaystyle\; t\_\; \{0\; \}\; =\; 0,\; \backslash ,\; t\_\; \{k\; +\; 1\}\; =\; t\_\; \{k\}\; -\; \{\backslash \; tfrac\; \{p\; (t\_\; \{k\})\}\; \{p\; \text{'}(t\_\; \{k\})\}\}\}$, тогда

   $xk\; +\; p\; -\; xk\; \Vert \; \le \; tk\; +\; p\; -\; tk.\; \{\backslash \; displaystyle\; \backslash \; |\; \backslash \; mathbf\; \{x\}\; \_\; \{k\; +\; p\}\; -\; \backslash \; mathbf\; \{x\}\; \_\; \{k\}\; \backslash \; |\; \backslash \; leq\; t\_\; \{k\; +\; p\}\; -t\_\; \{k\}.\}$

4. Квадратичная сходимость полученная из оценки погрешности

   $\Vert \; xn\; +\; 1\; -\; x\; \ast \; \Vert \; \le \; \theta \; 2\; n\; \Vert \; xn\; +\; 1\; -\; xn\; \Vert \; \le \; \theta \; 2\; n\; 2\; n\; \Vert \; h\; 0\; \Vert .\; \{\backslash \; displaystyle\; \backslash \; |\; \backslash \; mathbf\; \{x\}\; \_\; \{n\; +\; 1\}\; -\; \backslash \; mathbf\; \{x\}\; ^\; \{*\}\; \backslash \; |\; \backslash \; leq\; \backslash \; theta\; ^\; \{2\; ^\; \{n\}\}\; \backslash \; |\; \backslash \; mathbf\; \{x\}\; \_\; \{n\; +1\}\; -\; \backslash \; mathbf\; \{x\}\; \_\; \{n\}\; \backslash \; |\; \backslash \; leq\; \{\backslash \; frac\; \{\backslash \; theta\; ^\; \{2\; ^\; \{n\}\}\}\; \{2\; ^\; \{n\}\}\}\; \backslash \; |\; \backslash \; mathbf\; \{h\}\; \_\; \{0\; \}\; \backslash \; |.\}$

В 1986 году Ямамото доказал, что оценки ошибок метода Ньютона, такие как Doring (1969), Ostrowski (1971, 1973), Gragg-Tapia (1974), Potra -Ptak (1980), Miel (1981), Potra (1984) могут быть выведены из теоремы Канторовича.

Существует q-аналог для теорема Канторовича. Другие обобщения / варианты см. В Ortega Rheinboldt (1970).

Оиши и Танабе утверждали, что теорему Канторовича можно применить для получения надежных решений линейного программирования.

• Джон Хаббард и Барбара Берк Хаббард: векторное исчисление, линейная алгебра и дифференциальные формы: унифицированный подход, выпуски матриц, ISBN 978-0-9715766-3-6 (предварительный просмотр 3. издания и образцы материалов, включая Kant.-thm. )
• Ямамото, Тетсуро (2001). «Исторические достижения в анализе сходимости для Ньютона. и ньютоноподобные методы ». In Brezinski, C.; Wuytack, L. (eds.). Numerical Analysis: Historical Developments in 20 Century. North-Holland. pp. 241–263. ISBN 0-444-50617-9.