Итерация с фиксированной точкой

Алгоритм поиска корня

В численном анализе итерация с фиксированной точкой — это метод вычисления фиксированных точек функции.

Более конкретно, если задана функция, определенная на действительных числах с действительными значениями, и задана точка в области , то итерация с фиксированной точкой приводит к последовательности итерированных применений функции , которая, как ожидается, сходится к точке . Если является непрерывной, то можно доказать, что полученная является фиксированной точкой , т.е. ${\displaystyle f}$ ${\displaystyle x_{0}}$ ${\displaystyle f}$ $${\displaystyle x_{n+1}=f(x_{n}),\,n=0,1,2,\dots }$$ ${\displaystyle x_{0},x_{1},x_{2},\dots }$ ${\displaystyle x_{0},f(x_{0}),f(f(x_{0})),\dots }$ ${\displaystyle x_{\text{fix}}}$ ${\displaystyle f}$ ${\displaystyle x_{\text{fix}}}$ ${\displaystyle f}$ $${\displaystyle f(x_{\text{fix}})=x_{\text{fix}}.}$$

В более общем смысле функцию можно определить в любом метрическом пространстве со значениями в этом же пространстве. ${\displaystyle f}$

Примеры

Итерация с фиксированной точкой x _{n +1} = sin x _n с начальным значением x ₀ = 2 сходится к 0. Этот пример не удовлетворяет предположениям теоремы Банаха о фиксированной точке , поэтому скорость его сходимости очень низкая.

• Первый простой и полезный пример — вавилонский метод вычисления квадратного корня из a > 0 , который заключается в том, чтобы взять , т. е. среднее значение x и a / x , чтобы приблизиться к пределу (от любой начальной точки ). Это частный случай метода Ньютона, цитируемого ниже. ${\displaystyle f(x)={\frac {1}{2}}\left({\frac {a}{x}}+x\right)}$ ${\displaystyle x={\sqrt {a}}}$ ${\displaystyle x_{0}\gg 0}$
• Итерация с фиксированной точкой сходится к единственной фиксированной точке функции для любой начальной точки Этот пример удовлетворяет (самое позднее после первого шага итерации) предположениям теоремы Банаха о фиксированной точке . Следовательно, ошибка после n шагов удовлетворяет (где мы можем взять , если начинаем с .) Когда ошибка меньше, чем кратно для некоторой константы q , мы говорим, что имеем линейную сходимость . Теорема Банаха о фиксированной точке позволяет получать итерации с фиксированной точкой с линейной сходимостью. ${\displaystyle x_{n+1}=\cos x_{n}\,}$ ${\displaystyle f(x)=\cos x\,}$ ${\displaystyle x_{0}.}$ ${\displaystyle |x_{n}-x|\leq {q^{n} \over 1-q}|x_{1}-x_{0}|=Cq^{n}}$ ${\displaystyle q=0.85}$ ${\displaystyle x_{0}=1}$ ${\displaystyle q^{n}}$
• Требование непрерывности f важно, как показывает следующий пример. Итерация сходится к 0 для всех значений . Однако 0 не является неподвижной точкой функции , поскольку эта функция не является непрерывной при , и фактически не имеет неподвижных точек. $${\displaystyle x_{n+1}={\begin{cases}{\frac {x_{n}}{2}},&x_{n}\neq 0\\1,&x_{n}=0\end{cases}}}$$ ${\displaystyle x_{0}}$ $${\displaystyle f(x)={\begin{cases}{\frac {x}{2}},&x\neq 0\\1,&x=0\end{cases}}}$$ ${\displaystyle x=0}$

Привлечение фиксированных точек

Итерация с фиксированной точкой x _{n +1} = cos x _n с начальным значением x ₁ = −1 .

Притягивающая неподвижная точка функции f — это неподвижная точка x _fix функции f с окрестностью U «достаточно близких» точек вокруг x _fix, такой, что для любого значения x в U последовательность итераций неподвижной точки содержится в U и сходится к x _fix . Область притяжения x _fix — это наибольшая такая окрестность U. ^[1 ] $${\displaystyle x,\ f(x),\ f(f(x)),\ f(f(f(x))),\dots }$$

Функция натурального косинуса («натуральный» означает в радианах , а не градусах или других единицах) имеет ровно одну неподвижную точку, и эта неподвижная точка является притягивающей. В этом случае «достаточно близко» вовсе не является строгим критерием — чтобы продемонстрировать это, начните с любого действительного числа и несколько раз нажмите клавишу cos на калькуляторе (сначала проверив, что калькулятор находится в режиме «радианы»). В конечном итоге она сходится к числу Дотти (около 0,739085133), которое является неподвижной точкой. Именно там график функции косинуса пересекает линию . ^[2] ${\displaystyle y=x}$

Не все неподвижные точки являются притягивающими. Например, 0 является неподвижной точкой функции f ( x ) = 2 x , но итерация этой функции для любого значения, отличного от нуля, быстро расходится. Мы говорим, что неподвижная точка является отталкивающей. ${\displaystyle f(x)=2x}$

Притягивающая неподвижная точка называется устойчивой неподвижной точкой, если она также устойчива по Ляпунову .

Неподвижная точка называется нейтрально устойчивой неподвижной точкой, если она устойчива по Ляпунову, но не притягивает. Центр линейного однородного дифференциального уравнения второго порядка является примером нейтрально устойчивой неподвижной точки.

Несколько точек притяжения можно собрать в фиксированный набор точек притяжения .

Теорема Банаха о неподвижной точке

Теорема Банаха о неподвижной точке дает достаточное условие для существования притягивающих неподвижных точек. Функция отображения сжатия, определенная на полном метрическом пространстве, имеет ровно одну неподвижную точку, и итерация неподвижной точки притягивается к этой неподвижной точке для любого начального приближения в области функции. Обычные особые случаи таковы, что (1) определена на действительной прямой с действительными значениями и является непрерывной по Липшицу с константой Липшица , и (2) функция f непрерывно дифференцируема в открытой окрестности неподвижной точки x _fix , и . ${\displaystyle f}$ ${\displaystyle x_{0}}$ ${\displaystyle f}$ ${\displaystyle L<1}$ ${\displaystyle |f'(x_{\text{fix}})|<1}$

Хотя есть и другие теоремы о неподвижной точке , эта особенно полезна, поскольку не все неподвижные точки являются привлекательными. При построении итерации с неподвижной точкой очень важно убедиться, что она сходится к неподвижной точке. Обычно мы можем использовать теорему Банаха о неподвижной точке, чтобы показать, что неподвижная точка является привлекательной.

Аттракторы

Притягивающие неподвижные точки являются частным случаем более широкой математической концепции аттракторов . Итерации неподвижных точек являются дискретной динамической системой с одной переменной. Теория бифуркаций изучает динамические системы и классифицирует различные поведения, такие как притягивающие неподвижные точки, периодические орбиты или странные аттракторы . Примером системы является логистическое отображение .

Итерационные методы

В вычислительной математике итерационный метод — это математическая процедура, которая использует начальное значение для генерации последовательности улучшающихся приближенных решений для класса задач, в которой n-е приближение выводится из предыдущих. Сходящиеся итерации с фиксированной точкой — это математически строгие формализации итерационных методов.

Примеры итеративного метода

• Метод Ньютона — это алгоритм поиска корней для нахождения корней заданной дифференцируемой функции ⁠ ⁠ ${\displaystyle f(x)}$ . Итерация — это ${\textstyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.}$

  Если мы запишем , мы можем переписать итерацию Ньютона как итерацию с фиксированной точкой . ${\textstyle g(x)=x-{\frac {f(x)}{f'(x)}}}$ ${\textstyle x_{n+1}=g(x_{n})}$

  Если эта итерация сходится к фиксированной точке g , то , поэтому ${\displaystyle x_{\text{fix}}}$ ${\textstyle x_{\text{fix}}=g(x_{\text{fix}})=x_{\text{fix}}-{\frac {f(x_{\text{fix}})}{f'(x_{\text{fix}})}}}$ ${\textstyle f(x_{\text{fix}})/f'(x_{\text{fix}})=0,}$

  следовательно , , то есть, является корнем . При предположениях теоремы Банаха о неподвижной точке итерация Ньютона, оформленная как метод неподвижной точки, демонстрирует по крайней мере линейную сходимость . Более подробный анализ показывает квадратичную сходимость , то есть, , при определенных обстоятельствах. ${\displaystyle f(x_{\text{fix}})=0}$ ${\displaystyle x_{\text{fix}}}$ ${\displaystyle f}$ ${\textstyle |x_{n}-x_{\text{fix}}|<Cq^{2^{n}}}$
• Метод Галлея похож на метод Ньютона , когда он работает правильно, но его ошибка составляет ( кубическая сходимость ). В общем случае можно разработать методы, которые сходятся со скоростью для любого . Как правило, чем выше k , тем он менее стабилен и тем более вычислительно затратен. По этим причинам методы более высокого порядка обычно не используются. ${\displaystyle |x_{n}-x_{\text{fix}}|<Cq^{3^{n}}}$ ${\displaystyle Cq^{k^{n}}}$ ${\displaystyle k\in \mathbb {N} }$
• Методы Рунге–Кутты и численные решатели обыкновенных дифференциальных уравнений в целом можно рассматривать как итерации с фиксированной точкой. Действительно, основная идея при анализе A-устойчивости решателей ОДУ заключается в том, чтобы начать с особого случая , где — комплексное число , и проверить, сходится ли решатель ОДУ к фиксированной точке всякий раз, когда действительная часть отрицательна. ^[a] ${\displaystyle y'=ay}$ ${\displaystyle a}$ ${\displaystyle y_{\text{fix}}=0}$ ${\displaystyle a}$
• Теорема Пикара –Линделёфа , показывающая, что обыкновенные дифференциальные уравнения имеют решения, по сути является применением теоремы Банаха о неподвижной точке к специальной последовательности функций, которая образует итерацию неподвижной точки, строя решение уравнения. Решение ОДУ таким способом называется итерацией Пикара , методом Пикара или итеративным процессом Пикара .
• Возможность итерации в Excel может быть использована для нахождения решений уравнения Коулбрука с точностью до 15 значащих цифр. ^{[3] [4]}
• Некоторые из схем «последовательного приближения», используемых в динамическом программировании для решения функционального уравнения Беллмана , основаны на итерациях с фиксированной точкой в ​​пространстве возвращаемой функции. ^{[5] [6]}
• Паутинная модель теории цен соответствует итерации с фиксированной точкой композиции функции предложения и функции спроса. ^[7]

Ускорение конвергенции

Скорость сходимости итерационной последовательности можно увеличить, используя метод ускорения сходимости , такой как ускорение Андерсона и дельта-квадратный процесс Эйткена . Применение метода Эйткена к итерации с фиксированной точкой известно как метод Стеффенсена , и можно показать, что метод Стеффенсена дает скорость сходимости, которая является по крайней мере квадратичной.

Игра Хаос

Треугольник Серпинского, созданный с использованием IFS, выбирающий все элементы на каждой итерации

Термин «игра хаоса» относится к методу генерации неподвижной точки любой итерируемой функциональной системы (IFS). Начиная с любой точки x ₀ , последовательные итерации формируются как x _{k +1} = f _r ( x _k ) , где f _r — член данной IFS, случайно выбранный для каждой итерации. Следовательно, игра хаоса — это рандомизированная итерация с неподвижной точкой. Игра хаоса позволяет построить общую форму фрактала, такого как треугольник Серпинского , повторяя итерационный процесс большое количество раз. Более математически, итерации сходятся к неподвижной точке IFS. Всякий раз, когда x ₀ принадлежит аттрактору IFS, все итерации x _k остаются внутри аттрактора и с вероятностью 1 образуют плотное множество в последнем.

Смотрите также

• Комбинатор с фиксированной точкой
• Паутинный участок
• цепь Маркова
• Бесконечные композиции аналитических функций
• Скорость сходимости

Ссылки

1. Некоторые итерации можно также считать A-устойчивыми, если итерации остаются ограниченными в течение длительного времени, что выходит за рамки данной статьи.

1. Рассиас, Фемистокл М.; Пардалос, Панос М. (17 сентября 2014 г.). Математика без границ: обзоры по чистой математике. Springer. ISBN 978-1-4939-1106-6.
2. Weisstein, Eric W. "Dottie Number". Wolfram MathWorld . Wolfram Research, Inc . Получено 23 июля 2016 г. .
3. MA Kumar (2010), Решение неявных уравнений (Colebrook) в рабочем листе, Createspace, ISBN 1-4528-1619-0 
4. Бркич, Деян (2017) Решение неявного уравнения Коулбрука для трения потока с использованием Excel, Электронные таблицы в образовании (eJSiE): Том 10: Выпуск 2, Статья 2. Доступно по адресу: https://sie.scholasticahq.com/article/4663-solution-of-the-implicit-colebrook-equation-for-flow-friction-using-excel
5. Беллман, Р. (1957). Динамическое программирование, Princeton University Press.
6. Снедович, М. (2010). Динамическое программирование: основы и принципы, Тейлор и Фрэнсис .
7. Онодзаки, Тамоцу (2018). "Глава 2. Одномерная нелинейная модель паутины". Нелинейность, ограниченная рациональность и неоднородность: некоторые аспекты рыночной экономики как сложных систем . Springer. ISBN 978-4-431-54971-0.

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

• Burden, Richard L.; Faires, J. Douglas (1985). "Итерация с фиксированной точкой". Численный анализ (третье изд.). PWS Publishers. ISBN 0-87150-857-5.
• Хоффман, Джо Д.; Франкель, Стивен (2001). «Итерация с фиксированной точкой». Численные методы для инженеров и ученых (второе изд.). Нью-Йорк: CRC Press. С. 141–145. ISBN 0-8247-0443-6.
• Джадд, Кеннет Л. (1998). «Итерация с фиксированной точкой». Численные методы в экономике . Кембридж: MIT Press. стр. 165–167. ISBN 0-262-10071-1.
• Стернберг, Шломо (2010). «Итерация и неподвижные точки». Динамические системы (первое издание). Dover Publications. ISBN 978-0486477053.
• Шашкин, Юрий А. (1991). "9. Метод итерации". Неподвижные точки (первое изд.). Американское математическое общество. ISBN 0-8218-9000-X.
• Роза, Алессандро (2021). «Эпизодическая история ступенчатой ​​итерационной диаграммы». Антикварные Mathematicae . 15 :3–90. дои : 10.14708/am.v15i1.7056. S2CID  247259939.

Внешние ссылки

• Алгоритмы с фиксированной точкой онлайн
• Онлайн-калькулятор итераций с фиксированной точкой (Mathematical Assistant on Web)