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

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

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

Предположения [ править ]

Пусть открытое подмножество и дифференцируемая функция с якобианом , локально липшицевы (например , если дважды дифференцируемы). То есть предполагается, что для любого открытого подмножества существует такая константа , что для любого${\ Displaystyle X \ подмножество \ 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. а сходимость к решению определяется сходимостью итерации Ньютона квадратного многочлена к его наименьшему корню , ^[4] если , то${\displaystyle F}$${\displaystyle p(t)}$${\displaystyle t^{\ast }}$${\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]} Gragg-Tapia (1974), Potra-Ptak (1980), ^[8] Miel (1981), ^[9] Potra (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. (ред.). Численный анализ: исторические события в 20 веке . Северная Голландия. С. 241–263. ISBN 0-444-50617-9.