Теорема канторовича - Kantorovich theorem

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

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

Предположения

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

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

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

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

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

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

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

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

${\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}}}$

Заявление

Сейчас если ${\displaystyle \alpha _{0}\leq {\tfrac {1}{2}}}$ тогда

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

Утверждение, которое более точное, но немного сложнее доказать, использует корни ${\displaystyle t^{\ast }\leq t^{**}}$ квадратичного многочлена

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

${\displaystyle t^{\ast /**}={\frac {2\|\mathbf {h} _{0}\|}{1\pm {\sqrt {1-2\alpha }}}}}$

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

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

потом

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

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

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

   ${\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}\|.}$

Следствие

В 1986 году Ямамото доказал, что оценки ошибок метода Ньютона, такие как Doring (1969), Ostrowski (1971, 1973),^[6][7] Грэгг-Тапиа (1974), Потра-Птак (1980),^[8] Миэль (1981),^[9] Потра (1984),^[10] можно вывести из теоремы Канторовича.^[11]

Обобщения

Существует q-аналог для теоремы Канторовича.^[12][13] Для других обобщений / вариаций см. Ortega & Rheinboldt (1970).^[14]

Приложения

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

Рекомендации

1. Деуфлхард, П. (2004). Методы Ньютона для нелинейных задач. Аффинная инвариантность и адаптивные алгоритмы. Серия Спрингера в вычислительной математике. Vol. 35. Берлин: Springer. ISBN  3-540-21099-7.
2. Зейдлер, Э. (1985). Нелинейный функциональный анализ и его приложения: Часть 1: Теоремы о неподвижной точке. Нью-Йорк: Спрингер. ISBN  0-387-96499-1.
3. Деннис, Джон Э.; Шнабель, Роберт Б. (1983). "Канторовича и теоремы о сжимающих отображениях". Численные методы безусловной оптимизации и нелинейных уравнений. Энглвудские скалы: Прентис-холл. С. 92–94. ISBN  0-13-627216-9.
4. Ортега, Дж. М. (1968). «Теорема Ньютона-Канторовича». Амер. Математика. Ежемесячно. 75 (6): 658–660. Дои:10.2307/2313800. JSTOR  2313800.
5. Gragg, W. B .; Тапиа, Р. А. (1974). "Границы оптимальной погрешности теоремы Ньютона-Канторовича". Журнал SIAM по численному анализу. 11 (1): 10–13. Bibcode:1974SJNA ... 11 ... 10G. Дои:10.1137/0711002. JSTOR  2156425.
6. Островский, А. М. (1971). "Метод Ньютона в пространстве Банаха". C. R. Acad. Sci. Париж. 27 (А): 1251–1253.
7. Островский, А. М. (1973). Решение уравнений в евклидовом и банаховом пространствах. Нью-Йорк: Academic Press. ISBN  0-12-530260-6.
8. Potra, F.A .; Птак, В. (1980). «Точные границы ошибки для процесса Ньютона». Нумер. Математика. 34: 63–72. Дои:10.1007 / BF01463998.
9. Миэль, Дж. Дж. (1981). «Обновленная версия теоремы Канторовича для метода Ньютона». Вычисление. 27 (3): 237–244. Дои:10.1007 / BF02237981.
10. Потра, Ф.А. (1984). «Об апостериорных оценках погрешности метода Ньютона». Beiträge zur Numerische Mathematik. 12: 125–138.
11. Ямамото, Т. (1986). «Метод нахождения точных границ погрешности метода Ньютона при предположениях Канторовича». Numerische Mathematik. 49 (2–3): 203–220. Дои:10.1007 / BF01389624.
12. Райкович, П. М .; Станкович, М. С .; Маринкович, С. Д. (2003). «О q-итерационных методах решения уравнений и систем». Нови-Сад J. Math. 33 (2): 127–137.
13. Rajković, P.M .; Marinković, S.D .; Станкович, М. С. (2005). «О методе q-Ньютона – Канторовича для решения систем уравнений». Прикладная математика и вычисления. 168 (2): 1432–1448. Дои:10.1016 / j.amc.2004.10.035.
14. Ортега, Дж. М .; Райнбольдт, В. К. (1970). Итерационное решение нелинейных уравнений с несколькими переменными.. СИАМ. OCLC  95021.
15. Oishi, S .; Танабе, К. (2009). «Численный учет оптимальной точки для линейного программирования». Письма JSIAM. 1: 5–8. Дои:10.14495 / jsiaml.1.5.

дальнейшее чтение

• Джон Х. Хаббард и Барбара Берк Хаббард: Векторное исчисление, линейная алгебра и дифференциальные формы: единый подход, Matrix Editions, ISBN  978-0-9715766-3-6 (превью 3-го издания и образец материала, включая Kant.-thm. )
• Ямамото, Тетсуро (2001). «Исторические достижения в области анализа сходимости методов Ньютона и ньютоноподобных методов». В Brezinski, C .; Wuytack, L. (ред.). Численный анализ: исторические события ХХ века. Северная Голландия. С. 241–263. ISBN  0-444-50617-9.