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

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

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

Более конкретно, если функция определена на действительных числах с действительными значениями и задана точка в области , итерация с фиксированной точкой равна ${\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 важно, как показывает следующий пример. Итерация
  $${\displaystyle x_{n+1}={\begin{cases}{\frac {x_{n}}{2}},&x_{n}\neq 0\\1,&x_{n}=0\end{cases}}}$$
  сходится к 0 для всех значений . Однако 0 не является фиксированной точкой функции ${\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 последовательность итераций с фиксированной точкой

$${\displaystyle x,\ f(x),\ f(f(x)),\ f(f(f(x))),\dots }$$

Uсходитсяx _fixx _fixU^[1]

Функция натурального косинуса («естественный» означает радианы , а не градусы или другие единицы измерения) имеет ровно одну фиксированную точку, и эта фиксированная точка притягивает. В этом случае «достаточно близко» вообще не является строгим критерием — чтобы продемонстрировать это, начните с любого действительного числа и несколько раз нажмите клавишу 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-стабильности решателей ОДУ состоит в том, чтобы начать с частного случая , где - комплексное число , и проверить, сходится ли решатель ОДУ к фиксированной точке, когда действительная часть отрицательна. ^[а] ${\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. Всякий раз, когда _x0 принадлежит аттрактору IFS, все итерации xk _{остаются} внутри аттрактора и с вероятностью 1 образуют в последнем плотное множество .

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

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

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

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

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

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

• Берден, Ричард Л.; Фейрес, Дж. Дуглас (1985). «Итерация с фиксированной точкой». Численный анализ (Третье изд.). Издательство ПВС. 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). «Итерация и фиксированные точки». Динамические системы (Первое изд.). Дуврские публикации. ISBN 978-0486477053.
• Шашкин, Юрий А. (1991). «9. Итерационный метод». Фиксированные точки (Первое изд.). Американское математическое общество. ISBN 0-8218-9000-Х.
• Роза, Алессандро (2021). «Эпизодическая история ступенчатой ​​итерационной диаграммы». Антикварные Mathematicae . 15 :3–90. дои : 10.14708/am.v15i1.7056. S2CID  247259939.

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

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