В математике теорема о фиксированной точке является результатом, говорящим, что функция F будет иметь по крайней мере одну фиксированную точку (точку x, для которой F (x) = x) при некоторых условиях на F, которые можно сформулировать в общих чертах. Результаты такого рода являются одними из наиболее часто используемых в математике.
Теорема Банаха о фиксированной точке дает общий критерий, гарантирующий, что в случае его выполнения процедура итерация функции дает фиксированную точку.
Напротив, теорема Брауэра о фиксированной точке не- конструктивный результат : она говорит, что любой непрерывная функция от замкнутого единичного шара в n-мерном евклидовом пространстве до самой себя должна иметь фиксированную точку, но не описывает, как найти фиксированную точку. точка (см. также лемму Спернера ).
Например, функция косинус непрерывна в [-1,1] и отображает его в [-1,1], и поэтому должна иметь фиксированную точку. Это становится ясно, если изучить схематический график функции косинуса; фиксированная точка находится там, где косинусная кривая y = cos (x) пересекает линию y = x. Численно фиксированная точка приблизительно равна x = 0,73908513321516 (таким образом, x = cos (x) для этого значения x).
Теорема Лефшеца о неподвижной точке (и теорема Нильсена о неподвижной точке ) из алгебраической топологии примечательна тем, что дает в некоторых смысл, способ подсчета фиксированных точек.
Существует ряд обобщений теоремы Банаха о неподвижной точке и других; они применяются в теории PDE. См. теоремы о неподвижной точке в бесконечномерных пространствах.
Теорема коллажа в фрактальном сжатии доказывает, что для многих изображений существует относительно небольшое описание функции. что при итеративном применении к любому начальному изображению быстро сходится к желаемому.
Теорема Кнастера – Тарского утверждает, что любое функция сохранения порядка на полной решетке имеет фиксированную точку, и, действительно, наименьшую фиксированную точку. См. Также Теорема Бурбаки – Витта.
Теорема имеет приложения в абстрактной интерпретации, форме статического анализа программ.
Общая тема в лямбда-исчислении заключается в поиске неподвижных точек заданных лямбда-выражений. Каждое лямбда-выражение имеет фиксированную точку, а комбинатор с фиксированной точкой - это «функция», которая принимает на вход лямбда-выражение и производит в качестве выходных данных фиксированную точку этого выражения. Важным комбинатором с фиксированной точкой является комбинатор Y, используемый для получения рекурсивных определений.
В денотационной семантике языков программирования, частный случай теоремы Кнастера – Тарского используется для установления семантики рекурсивных определений. Хотя теорема о неподвижной точке применяется к «той же» функции (с логической точки зрения), развитие теории совершенно иное.
Такое же определение рекурсивной функции может быть дано в теории вычислимости, применяя теорему о рекурсии Клини. Эти результаты не являются эквивалентными теоремами; Теорема Кнастера – Тарского является гораздо более сильным результатом, чем то, что используется в денотационной семантике. Однако в свете тезиса Черча-Тьюринга их интуитивный смысл тот же: рекурсивная функция может быть описана как наименьшая фиксированная точка определенного функционала, отображающая функции в функции.
Вышеупомянутый метод итерации функции для поиска фиксированной точки также может использоваться в теории множеств ; лемма о неподвижной точке для нормальных функций утверждает, что любая непрерывная строго возрастающая функция от ординалов до ординалов имеет одну (а на самом деле много) неподвижных точек.
Каждый оператор замыкания в poset имеет много фиксированных точек; это «закрытые элементы» по отношению к оператору замыкания, и они являются основной причиной, по которой оператор замыкания был определен в первую очередь.
Каждая инволюция на конечном множестве с нечетным числом элементов имеет фиксированную точку; в более общем смысле, для каждой инволюции на конечном наборе элементов количество элементов и количество фиксированных точек имеют одинаковую четность. Дон Загье использовал эти наблюдения, чтобы дать одно предложение доказательства теоремы Ферма о суммах двух квадратов, описав две инволюции на одном и том же наборе троек целых чисел, одна из которых может легко показать, что у него есть только одна фиксированная точка, а у другой есть фиксированная точка для каждого представления данного простого числа (конгруэнтного 1 по модулю 4) в виде суммы двух квадратов. Поскольку первая инволюция имеет нечетное количество неподвижных точек, то же самое и вторая, и поэтому всегда существует представление желаемой формы.