Теорема Канторовича - Википедия - Kantorovich theorem

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

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

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

Позволять ${ Displaystyle X подмножество mathbb {R} ^ {n}}$ быть открытым подмножеством и ${ Displaystyle F: X подмножество mathbb {R} ^ {n} to mathbb {R} ^ {n}}$ а дифференцируемая функция с Якобиан ${ Displaystyle F ^ { prime} ( mathbf {x})}$ это локально Липшицева непрерывная (например, если ${ displaystyle F}$ дважды дифференцируема). То есть предполагается, что для любого открытого подмножества ${ Displaystyle U подмножество 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 В ( mathbf {x} _ {1}, | mathbf {h} _ {0} |)}$ содержится внутри множества ${ displaystyle X}$ . Позволять ${ Displaystyle M leq L}$ - константа Липшица для якобиана над этим шаром.

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

{ displaystyle { 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} | , | mathbf { h} _ {k} | [0.4em] mathbf {x} _ {k + 1} & = mathbf {x} _ {k} + mathbf {h} _ {k}. end { выровнен}}}

Заявление

Сейчас если ${ Displaystyle альфа _ {0} leq { tfrac {1} {2}}}$ тогда

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

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

{ displaystyle p (t) = left ({ tfrac {1} {2}} L | F '( mathbf {x} _ {0}) ^ {- 1} | ^ {- 1} справа) 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}}}}.}

потом

решение ${ Displaystyle mathbf {х} ^ {*}}$ существует внутри замкнутого шара ${ displaystyle { bar {B}} ( mathbf {x} _ {1}, theta | mathbf {h} _ {0} |) subset { bar {B}} ( mathbf { x} _ {0}, t ^ {*})}$
он уникален внутри большего шара ${ displaystyle B ( mathbf {x} _ {0}, t ^ {* ast})}$
и сходимость к решению ${ displaystyle F}$ преобладает сходимость итерации Ньютона квадратичного многочлена ${ displaystyle p (t)}$ к самому маленькому корню ${ Displaystyle т ^ { аст}}$ ,^[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}.}$
Квадратичная сходимость получается из оценки погрешности^[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]

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

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

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

[Zeidler-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]