В математике фиксированная точка (иногда сокращается до fixpoint ), также известная как инвариантная точка , — это значение, которое не изменяется при данном преобразовании . В частности, для функций фиксированная точка — это элемент, который функция отображает сама на себя.
Формально c является неподвижной точкой функции f, если c принадлежит как области определения , так и кодомену функции f , и f ( c ) = c .
Например, если f определяется для действительных чисел формулой
Не все функции имеют фиксированные точки: например, f ( x ) = x + 1 не имеет фиксированных точек, поскольку x никогда не равен x + 1 для любого действительного числа. В графических терминах фиксированная точка x означает, что точка ( x , f ( x )) находится на линии y = x , или, другими словами, график f имеет общую точку с этой линией.
В численном анализе итерация с фиксированной точкой — это метод вычисления фиксированных точек функции. В частности, для данной функции с той же областью определения и кодоменом, точкой в области определения итерация с фиксированной точкой равна
что приводит к последовательности повторяющихся применений функций , которая, как надеются, сойдется к точке . Если непрерывно, то можно доказать, что полученное является неподвижной точкой .
Понятия притяжения неподвижных точек, отталкивания неподвижных точек и периодических точек определяются относительно итерации с фиксированной точкой.
Теорема о неподвижной точке — это результат, утверждающий, что по крайней мере одна неподвижная точка существует при некоторых общих условиях. [1]
Например, теорема Банаха о неподвижной точке (1922 г.) дает общий критерий, гарантирующий, что, если она выполняется, итерация с фиксированной точкой всегда будет сходиться к фиксированной точке.
Теорема Брауэра о неподвижной точке (1911 г.) гласит, что любая непрерывная функция от замкнутого единичного шара в n -мерном евклидовом пространстве до самой себя должна иметь фиксированную точку, но не описывает, как найти неподвижную точку.
Теорема Лефшеца о неподвижной точке (и теорема Нильсена о неподвижной точке ) из алгебраической топологии позволяют подсчитывать неподвижные точки.
В алгебре для группы G , действующей на множестве X групповым действием , x в X называется неподвижной точкой g , если .
Подгруппа неподвижной точки автоморфизма f группы G является подгруппой G : _ _
Аналогично, подкольцо неподвижных точек автоморфизма f кольца R является подкольцом неподвижных точек f , то есть
В теории Галуа множество неподвижных точек множества полевых автоморфизмов представляет собой поле , называемое фиксированным полем множества автоморфизмов.
Говорят, что топологическое пространство обладает свойством неподвижной точки (FPP), если для любой непрерывной функции
существует такое, что .
ФПП является топологическим инвариантом , т. е. сохраняется при любом гомеоморфизме . FPP также сохраняется при любом втягивании .
Согласно теореме Брауэра о неподвижной точке , каждое компактное и выпуклое подмножество евклидова пространства имеет FPP. Сама по себе компактность не подразумевает FPP, а выпуклость даже не является топологическим свойством, поэтому имеет смысл задаться вопросом, как топологически охарактеризовать FPP. В 1932 году Борсук задался вопросом, может ли компактность вместе со сжимаемостью быть необходимым и достаточным условием существования FPP. Проблема оставалась открытой в течение 20 лет, пока гипотеза не была опровергнута Киношитой, который нашел пример компактного сжимаемого пространства без ФПП. [2]
В теории предметной области понятие и терминология неподвижных точек обобщаются до частичного порядка . Пусть ≤ — частичный порядок над множеством X , и пусть f : X → X — функция над X. Тогда префиксная точка (также пишется как префиксная точка , иногда сокращается до префиксной точки или префиксной точки ) [ нужна ссылка ] для f — это любой p такой, что f ( p ) ≤ p . Аналогично, постфиксная точка f — это любой p такой, что p ≤ f ( p ). [3] Иногда встречается противоположное употребление. [4] Малкис обосновывает представленное здесь определение следующим образом: «поскольку f стоит перед знаком неравенства в термине f ( x ) ≤ x , такой x называется предфиксированной точкой». [5] Фиксированная точка — это точка, которая является одновременно префиксной и постфиксной точкой. Префиксные и постфиксные точки находят применение в теоретической информатике . [6]
В теории порядка наименее фиксированная точка функции из частично упорядоченного множества (ЧУУ) сама по себе является фиксированной точкой, которая меньше друг друга в фиксированных точках в соответствии с порядком ЧУУ. Функция не обязательно должна иметь наименьшую фиксированную точку, но если она есть, то наименьшая фиксированная точка уникальна.
Один из способов выразить теорему Кнастера-Тарского - сказать, что монотонная функция на полной решетке имеет наименьшую неподвижную точку , которая совпадает с ее наименьшей префиксной точкой (и аналогичным образом ее наибольшая неподвижная точка совпадает с ее наибольшей постфиксной точкой). [7]
В комбинаторной логике информатики комбинатор с фиксированной точкой — это функция высшего порядка , которая возвращает фиксированную точку своей функции-аргумента, если таковая существует. Формально, если функция f имеет одну или несколько неподвижных точек, то
В математической логике логика с фиксированной точкой является расширением классической логики предикатов, которая была введена для выражения рекурсии. Их развитие было мотивировано описательной теорией сложности и их связью с языками запросов к базам данных , в частности с Datalog .
Во многих областях равновесие или стабильность являются фундаментальными понятиями, которые можно описать в терминах фиксированных точек. Ниже приведены некоторые примеры.