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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Итерация с фиксированной точкой»  -  новости  · газеты  · книги  · ученый  · JSTOR ( май 2010 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

Более конкретно, учитывая функцию, определенную на действительных числах с действительными значениями и заданную точку в области определения , итерация с фиксированной точкой равна${\ 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}$${\displaystyle f}$${\displaystyle x}$${\displaystyle f}$

${\displaystyle f(x)=x.\,}$

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

Примеры [ править ]

• Первым простым и полезным примером является вавилонский метод вычисления квадратного корня из 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}$

Итерация с фиксированной точкой x _{n +1}  = sin x _n с начальным значением x ₀ = 2 сходится к 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}}$
• С фиксированной точкой итерация не будет расходиться , если . Мы говорим, что неподвижная точка отталкивает.${\displaystyle x_{n+1}=2x_{n}\,}$${\displaystyle x_{0}=0}$${\displaystyle f(x)=2x\,}$
• Требование непрерывности 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}$

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

• Метод Ньютона для нахождения корней данной дифференцируемой функции имеет вид${\displaystyle f(x)}$

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.}$

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

${\displaystyle x_{n+1}=g(x_{n})}$.

Если эта итерация сходится к фиксированной точке x элемента g , то

${\displaystyle x=g(x)=x-{\frac {f(x)}{f'(x)}}}$, так ${\displaystyle f(x)/f'(x)=0.}$

Взаимное ничего не равно нуль, следовательно , F ( х ) = 0 : х является корнем из F . В условиях теоремы Банаха о неподвижной точке итерация Ньютона, представленная как метод неподвижной точки, демонстрирует линейную сходимость . Однако более подробный анализ показывает квадратичную сходимость , т. Е.

${\displaystyle |x_{n}-x|<Cq^{2^{n}}}$, при определенных обстоятельствах.

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

• Некоторые схемы «последовательного приближения», используемые в динамическом программировании для решения функционального уравнения Беллмана, основаны на итерациях с фиксированной точкой в ​​пространстве возвращаемой функции. ^{[3] [4]}

Схватки [ править ]

Если функция, определенная на действительной прямой с действительными значениями, является липшицевой с константой Липшица , то эта функция имеет ровно одну фиксированную точку, и итерация с фиксированной точкой сходится к этой фиксированной точке для любого начального предположения. Эта теорема может быть обобщена для любого полного метрическое пространство.${\displaystyle f}$${\displaystyle L<1}$${\displaystyle x_{0}.}$

Доказательство этой теоремы:

Поскольку она липшицева с константой Липшица , то для последовательности имеем:${\displaystyle f}$${\displaystyle L<1}$${\displaystyle \{x_{n},n=0,1,2,\ldots \}}$

${\displaystyle {\begin{aligned}|x_{2}-x_{1}|=|f(x_{1})-f(x_{0})|&\leq L|x_{1}-x_{0}|,\\|x_{3}-x_{2}|=|f(x_{2})-f(x_{1})|&\leq L|x_{2}-x_{1}|,\\&\,\,\,\vdots \end{aligned}}}$

и

${\displaystyle |x_{n}-x_{n-1}|=|f(x_{n-1})-f(x_{n-2})|\leq L|x_{n-1}-x_{n-2}|.}$

Комбинирование приведенных выше неравенств дает:

${\displaystyle |x_{n}-x_{n-1}|\leq L^{n-1}|x_{1}-x_{0}|.}$

Поскольку , как${\displaystyle L<1}$${\displaystyle L^{n-1}\rightarrow 0}$${\displaystyle n\rightarrow \infty .}$

Следовательно, мы можем показать, что это последовательность Коши и, следовательно, она сходится к точке .${\displaystyle \{x_{n}\}}$${\displaystyle x^{*}}$

Для итерации отпустим на бесконечность обе части уравнения, получим . Это показывает, что это фиксированная точка для . Итак, мы доказали, что итерация в конечном итоге сходится к фиксированной точке.${\displaystyle x_{n}=f(x_{n-1})}$${\displaystyle n}$${\displaystyle x^{*}=f(x^{*})}$${\displaystyle x^{*}}$${\displaystyle f}$

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

Ускорение конвергенции [ править ]

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

См. Также [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Бэрден, Ричард Л .; Faires, Дж. Дуглас (1985). «Итерация с фиксированной точкой». Численный анализ (Третье изд.). Издатели PWS. 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.

Внешние ссылки [ править ]

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