Введение

Условие для математической функции, чтобы отобразить некоторое значение в себя. В математике, теорема о неподвижной точке – это результат, утверждающий, что функция F будет иметь хотя бы одну неподвижную точку (точку x, для которой F(x) = x), при определенных условиях на F, которые могут быть сформулированы в общем виде.

В математическом анализе

Теорема о фиксированной точке Банаха (1922) дает общий критерий, гарантирующий, что если он выполнен, процедура итерации функции приводит к фиксированной точке. В отличие от этого, теорема о фиксированной точке Брауэра (1911) является неконструктивным результатом: она утверждает, что любая непрерывная функция из замкнутого единичного шара в n-мерном евклидовом пространстве в себя должна иметь фиксированную точку, но не описывает, как эту фиксированную точку найти (см. также лемму Спернера). Например, функция косинуса непрерывна на отрезке [−1, 1] и отображает его в отрезок [−1, 1], следовательно, должна иметь фиксированную точку. Это очевидно при рассмотрении графика функции косинуса; фиксированная точка находится в точке пересечения кривой косинуса y = cos(x) и прямой y = x. Численно фиксированная точка (известная как число Дотти) приблизительно равна x = 0.73908513321516 (то есть x = cos(x) для этого значения x). Теорема о фиксированной точке Лефшеца (и теорема о фиксированной точке Нильсена) из алгебраической топологии примечательна тем, что в некотором смысле предоставляет способ подсчета фиксированных точек. Существует ряд обобщений теоремы о фиксированной точке Банаха и других результатов; они применяются в теории уравнений в частных производных. См. теоремы о фиксированной точке в бесконечномерных пространствах. Теорема о коллаже во фрактальном сжатии доказывает, что для многих изображений существует относительно компактное описание функции, которая при итеративном применении к любому исходному изображению быстро сходится к желаемому изображению.

В алгебре и дискретной математике

Теорема Кнастера–Тарского утверждает, что любая функция, сохраняющая порядок на полной решётке, имеет фиксированную точку, и притом наименьшую фиксированную точку. См. также теорему Бурбаки–Витта. Теорема находит применение в абстрактной интерпретации, являющейся формой статического анализа программ. Распространенной темой в лямбда-исчислении является поиск фиксированных точек заданных лямбда-выражений. Каждое лямбда-выражение имеет фиксированную точку, а комбинатор фиксированной точки — это «функция», которая принимает в качестве входных данных лямбда-выражение и выдаёт в качестве выходных данных фиксированную точку этого выражения. Важным комбинатором фиксированной точки является Y-комбинатор, используемый для задания рекурсивных определений. В денотационной семантике языков программирования специальный случай теоремы Кнастера–Тарского используется для установления семантики рекурсивных определений. Хотя теорема о фиксированной точке применяется к «одной и той же» функции (с логической точки зрения), развитие теории существенно различается. То же определение рекурсивной функции можно дать в теории вычислимости, применив теорему рекурсии Клини. Эти результаты не являются эквивалентными теоремами; теорема Кнастера–Тарского представляет собой гораздо более сильный результат, чем тот, который используется в денотационной семантике. Однако, в свете тезиса Черча–Тьюринга, их интуитивное значение одинаково: рекурсивную функцию можно описать как наименьшую фиксированную точку определённого функционала, отображающего функции в функции. Описанный выше метод итерации функции для нахождения фиксированной точки также может быть использован в теории множеств; лемма о фиксированной точке для нормальных функций утверждает, что любая непрерывная строго возрастающая функция от ординалов к ординалам имеет одну (и даже множество) фиксированных точек. Каждый оператор замыкания на частично упорядоченном множестве имеет множество фиксированных точек; это «закрытые элементы» относительно оператора замыкания, и они являются основной причиной, по которой оператор замыкания был определён изначально. Каждая инволюция на конечном множестве с нечётным числом элементов имеет фиксированную точку; в более общем случае, для каждой инволюции на конечном множестве элементов число элементов и число фиксированных точек имеют одинаковую чётность. Дон Загир использовал эти наблюдения, чтобы дать доказательство теоремы Ферма о сумме двух квадратов в одно предложение, описав две инволюции на одном и том же множестве троек целых чисел, одна из которых может быть легко показана имеющей только одну фиксированную точку, а другая — фиксированную точку для каждого представления заданного простого числа (конгруэнтного 1 по модулю 4) в виде суммы двух квадратов. Поскольку первая инволюция имеет нечётное число фиксированных точек, то же самое справедливо и для второй, и, следовательно, всегда существует представление требуемой формы.