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

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

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

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

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

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

держит. Норма слева — это норма оператора. Другими словами, для любого вектора $\mathbf {v} \in \mathbb {R} ^{n}$ неравенство

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

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

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

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

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

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

Заявление

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

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

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

p(t)=\left({\tfrac {1}{2}}L\|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 _{0}}}}}

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

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

Затем

решение $\mathbf {x} ^{*}$ существует внутри закрытого шара ${\bar {B}}(\mathbf {x} _{1},\theta \|\mathbf {h} _{0}\|)\subset {\bar {B}}(\mathbf {x} _{0},t^{*})$
он уникален внутри большего шара $B(\mathbf {x} _{0},t^{*\ast })$
и сходимость к решению $F$ преобладает сходимость итерации Ньютона квадратичного многочлена $p(t)$ к своему наименьшему корню $t^{\ast }$ , ^[4] если $t_{0}=0,\,t_{k+1}=t_{k}-{\tfrac {p(t_{k})}{p'(t_{k})}}$ , затем
$\|\mathbf {x} _{k+p}-\mathbf {x} _{k}\|\leq t_{k+p}-t_{k}.$
Квадратичная сходимость получается из оценки погрешности ^[5]
$\|\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 году Ямамото доказал, что ошибки оценок метода Ньютона, таких как Доринг (1969), Островский (1971, 1973), ^[6]^[7] Грагг-Тапия (1974), Потра-Птак (1980), ^[8] Мед (1981), ^[9] Потра (1984), ^[10] можно вывести из теоремы Канторовича. ^[11]

Обобщения

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

Приложения

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

Ссылки

^ Jump up to: ^а ^б Дефлхард, П. (2004). Методы Ньютона для нелинейных задач. Аффинная инвариантность и адаптивные алгоритмы . Ряд Спрингера по вычислительной математике. Том. 35. Берлин: Шпрингер. ISBN 3-540-21099-7 .
^ Jump up to: ^а ^б Зейдлер, Э. (1985). Нелинейный функциональный анализ и его приложения: Часть 1: Теоремы о неподвижной точке . Нью-Йорк: Спрингер. ISBN 0-387-96499-1 .
^ Деннис, Джон Э .; Шнабель, Роберт Б. (1983). «Теоремы Канторовича и о сжимающем отображении» . Численные методы неограниченной оптимизации и нелинейных уравнений . Энглвуд Клиффс: Прентис-Холл. стр. 92–94. ISBN 0-13-627216-9 .
^ Ортега, Дж. М. (1968). «Теорема Ньютона-Канторовича». амер. Математика. Ежемесячно . 75 (6): 658–660. дои : 10.2307/2313800 . JSTOR 2313800 .
^ Грэгг, Всемирный банк; Тапиа, РА (1974). «Оптимальные границы погрешности для теоремы Ньютона-Канторовича». SIAM Journal по численному анализу . 11 (1): 10–13. Бибкод : 1974SJNA...11...10G . дои : 10.1137/0711002 . JSTOR 2156425 .
^ Островский, AM (1971). «Метод Ньютона в банаховых пространствах». ЧР акад. наук. Париж . 27 (А): 1251–1253.
^ Островский, AM (1973). Решение уравнений в евклидовом и банаховом пространствах . Нью-Йорк: Академическая пресса. ISBN 0-12-530260-6 .
^ Потра, ФА; Птак, В. (1980). «Точные границы погрешности процесса Ньютона». Число. Математика . 34 : 63–72. дои : 10.1007/BF01463998 .
^ Миэль, Дж.Дж. (1981). «Обновленная версия теоремы Канторовича для метода Ньютона». Вычисление . 27 (3): 237–244. дои : 10.1007/BF02237981 .
^ Потра, Ф.А. (1984). «Об апостериорных оценках погрешности метода Ньютона». Вклад в числовую математику . 12 :125-138.
^ Ямамото, Т. (1986). «Метод нахождения точных оценок погрешности метода Ньютона при предположениях Канторовича». Нумерическая математика . 49 (2–3): 203–220. дои : 10.1007/BF01389624 .
^ Райкович, премьер-министр; Станкович, М.С.; Маринкович, С.Д. (2003). «О q-итерационных методах решения уравнений и систем». Нови-Сад Ж. Матем . 33 (2): 127–137.
^ Райкович, премьер-министр; Маринкович, С.Д.; Станкович, М.С. (2005). «О q-методе Ньютона–Канторовича решения систем уравнений». Прикладная математика и вычислительная техника . 168 (2): 1432–1448. дои : 10.1016/j.amc.2004.10.035 .
^ Ортега, Дж. М.; Рейнбольдт, WC (1970). Итерационное решение нелинейных уравнений с несколькими переменными . СИАМ. OCLC 95021 .
^ Оиси, С.; Танабэ, К. (2009). «Численное включение оптимальной точки для линейного программирования» . Письма JSIAM . 1 :5–8. дои : 10.14495/jsiaml.1.5 .

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

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

[Deuflhard-1] Jump up to: ^а ^б Дефлхард, П. (2004). Методы Ньютона для нелинейных задач. Аффинная инвариантность и адаптивные алгоритмы . Ряд Спрингера по вычислительной математике. Том. 35. Берлин: Шпрингер. ISBN 3-540-21099-7 .

[Zeidler-2] Jump up to: ^а ^б Зейдлер, Э. (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] Грэгг, Всемирный банк; Тапиа, РА (1974). «Оптимальные границы погрешности для теоремы Ньютона-Канторовича». SIAM Journal по численному анализу . 11 (1): 10–13. Бибкод : 1974SJNA...11...10G . дои : 10.1137/0711002 . JSTOR 2156425 .

[6] Островский, AM (1971). «Метод Ньютона в банаховых пространствах». ЧР акад. наук. Париж . 27 (А): 1251–1253.

[7] Островский, AM (1973). Решение уравнений в евклидовом и банаховом пространствах . Нью-Йорк: Академическая пресса. ISBN 0-12-530260-6 .

[8] Потра, ФА; Птак, В. (1980). «Точные границы погрешности процесса Ньютона». Число. Математика . 34 : 63–72. дои : 10.1007/BF01463998 .

[9] Миэль, Дж.Дж. (1981). «Обновленная версия теоремы Канторовича для метода Ньютона». Вычисление . 27 (3): 237–244. дои : 10.1007/BF02237981 .

[10] Потра, Ф.А. (1984). «Об апостериорных оценках погрешности метода Ньютона». Вклад в числовую математику . 12 :125-138.

[11] Ямамото, Т. (1986). «Метод нахождения точных оценок погрешности метода Ньютона при предположениях Канторовича». Нумерическая математика . 49 (2–3): 203–220. дои : 10.1007/BF01389624 .

[12] Райкович, премьер-министр; Станкович, М.С.; Маринкович, С.Д. (2003). «О q-итерационных методах решения уравнений и систем». Нови-Сад Ж. Матем . 33 (2): 127–137.

[13] Райкович, премьер-министр; Маринкович, С.Д.; Станкович, М.С. (2005). «О q-методе Ньютона–Канторовича решения систем уравнений». Прикладная математика и вычислительная техника . 168 (2): 1432–1448. дои : 10.1016/j.amc.2004.10.035 .

[14] Ортега, Дж. М.; Рейнбольдт, WC (1970). Итерационное решение нелинейных уравнений с несколькими переменными . СИАМ. OCLC 95021 .

[15] Оиси, С.; Танабэ, К. (2009). «Численное включение оптимальной точки для линейного программирования» . Письма JSIAM . 1 :5–8. дои : 10.14495/jsiaml.1.5 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]