Фиксированная точка (математика)

Элемент, сопоставленный самому себе с помощью математической функции

Функция (показана красным) имеет неподвижные точки 0, 1 и 2. ${\displaystyle f(x)=x^{3}-3x^{2}+3x}$

В математике неподвижная точка ( иногда сокращается до fixpoint ), также известная как инвариантная точка , — это значение, которое не изменяется при заданном преобразовании . В частности, для функций неподвижная точка — это элемент, который отображается на себя функцией. Любой набор неподвижных точек преобразования также является инвариантным набором .

Фиксированная точка функции

Формально, c является неподвижной точкой функции f, если c принадлежит как области определения , так и области кодомена f , и f ( c ) = c . В частности, f не может иметь неподвижной точки, если ее область определения не пересекается с ее областью кодомена. Если f определена на действительных числах , то она соответствует, в графических терминах, кривой на евклидовой плоскости , и каждая неподвижная точка c соответствует пересечению кривой с линией y  =  x , см. рисунок.

Например, если f определена на действительных числах с помощью , то 2 является неподвижной точкой f , поскольку f (2) = 2 . ${\displaystyle f(x)=x^{2}-3x+4,}$

Не все функции имеют неподвижные точки: например, f ( x ) = x + 1 не имеет неподвижных точек, поскольку x никогда не равно x + 1 для любого действительного числа.

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

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

Понятия притягивания неподвижных точек, отталкивания неподвижных точек и периодических точек определяются относительно итерации неподвижной точки.

Теоремы о неподвижной точке

Теорема о неподвижной точке — это результат, утверждающий, что при некотором общем условии существует по крайней мере одна неподвижная точка. ^[1]

Например, теорема Банаха о неподвижной точке (1922) дает общий критерий, гарантирующий, что если он выполняется, итерация неподвижной точки всегда будет сходиться к неподвижной точке.

Теорема Брауэра о неподвижной точке (1911) утверждает, что любая непрерывная функция из замкнутого единичного шара в n -мерном евклидовом пространстве в себя должна иметь неподвижную точку, но она не описывает, как найти неподвижную точку.

Теорема Лефшеца о неподвижной точке (и теорема Нильсена о неподвижной точке ) из алгебраической топологии дают способ подсчета неподвижных точек.

Фиксированная точка группового действия

В алгебре для группы G , действующей на множестве X с групповым действием , x в X называется неподвижной точкой g , если . ${\displaystyle \cdot }$ ${\displaystyle g\cdot x=x}$

Подгруппа неподвижной точки автоморфизма f группы G — это подгруппа группы G : ${\displaystyle G^{f}}$ $${\displaystyle G^{f}=\{g\in G\mid f(g)=g\}.}$$

Аналогично, подкольцо неподвижных точек автоморфизма f кольца R является подкольцом неподвижных точек f , то есть , ${\displaystyle R^{f}}$ $${\displaystyle R^{f}=\{r\in R\mid f(r)=r\}.}$$

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

Топологическое свойство неподвижной точки

Говорят, что топологическое пространство имеет свойство неподвижной точки (FPP), если для любой непрерывной функции ${\displaystyle X}$

${\displaystyle f\colon X\to X}$

существует такое, что . ${\displaystyle x\in X}$ ${\displaystyle f(x)=x}$

FPP является топологическим инвариантом , т. е. сохраняется при любом гомеоморфизме . FPP также сохраняется при любой ретракции .

Согласно теореме Брауэра о неподвижной точке , каждое компактное и выпуклое подмножество евклидова пространства имеет FPP. Компактность сама по себе не подразумевает FPP, а выпуклость даже не является топологическим свойством, поэтому имеет смысл спросить, как топологически охарактеризовать FPP. В 1932 году Борсук спросил, может ли компактность вместе со сжимаемостью быть необходимым и достаточным условием для выполнения FPP. Проблема оставалась открытой в течение 20 лет, пока гипотеза не была опровергнута Киношитой, который нашел пример компактного сжимаемого пространства без FPP. ^[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 имеет одну или несколько фиксированных точек, то ${\displaystyle {\mathsf {fix}}}$

${\displaystyle \operatorname {\mathsf {fix}} f=f(\operatorname {\mathsf {fix}} f).}$

Логика с фиксированной точкой

В математической логике логики с фиксированной точкой являются расширениями классической предикатной логики, которые были введены для выражения рекурсии. Их развитие было мотивировано теорией описательной сложности и их связью с языками запросов к базам данных , в частности с Datalog .

Приложения

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

• В проективной геометрии неподвижная точка проективности называется двойной точкой . ^{[8] [9]}
• В экономике равновесие Нэша игры — это неподвижная точка соответствия наилучшего ответа игры . Джон Нэш использовал теорему Какутани о неподвижной точке для своей основополагающей работы, которая принесла ему Нобелевскую премию по экономике.
• В физике , точнее в теории фазовых переходов , линеаризация вблизи нестабильной неподвижной точки привела к удостоенной Нобелевской премии работе Вильсона по созданию группы перенормировки и к математическому объяснению термина « критическое явление ». ^{[10] [11]}
• Компиляторы языков программирования используют вычисления с фиксированной точкой для анализа программ, например, в анализе потока данных , который часто требуется для оптимизации кода . Они также являются основной концепцией, используемой обобщенным методом анализа программ абстрактной интерпретации . ^[12]
• В теории типов комбинатор с фиксированной точкой позволяет определять рекурсивные функции в нетипизированном лямбда-исчислении .
• Вектор значений PageRank всех веб-страниц является неподвижной точкой линейного преобразования, полученного из структуры ссылок Всемирной паутины .
• Стационарное распределение цепи Маркова — это неподвижная точка функции вероятности перехода на один шаг.
• Неподвижные точки используются для нахождения формул для итерационных функций .

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

• Циклы и неподвижные точки перестановок
• Собственный вектор
• Равновесие
• Неподвижные точки преобразования Мёбиуса
• Идемпотентность
• Бесконечные композиции аналитических функций

• Инвариант (математика)

Примечания

1. Браун, РФ, ред. (1988). Теория неподвижной точки и ее приложения . Американское математическое общество. ISBN 0-8218-5080-6.
2. Киносита, Синъити (1953). «О некоторых стягиваемых континуумах без свойства неподвижной точки». Fund. Math. 40 (1): 96–98. doi : 10.4064/fm-40-1-96-98 . ISSN  0016-2736.
3. Смит, Майкл Б.; Плоткин, Гордон Д. (1982). «Теоретико-категорное решение рекурсивных уравнений в области» (PDF) . Труды 18-го симпозиума IEEE по основам компьютерной науки . Журнал SIAM по вычислениям (том 11). стр. 761–783. doi :10.1137/0211062.
4. Патрик Кусо; Радхия Кусо (1979). «Конструктивные версии теорем Тарского о неподвижной точке» (PDF) . Pacific Journal of Mathematics . 82 (1): 43–57. doi :10.2140/pjm.1979.82.43.
5. Малкис, Александр (2015). «Многопоточная декартова абстрактная интерпретация многопоточных рекурсивных программ является полиномиальной» (PDF) . Проблемы достижимости . Конспект лекций по информатике. 9328 : 114–127. doi :10.1007/978-3-319-24537-9_11. ISBN 978-3-319-24536-2. S2CID  17640585. Архивировано из оригинала (PDF) 10.08.2022.
6. Yde Venema (2008) Лекции по модальному μ-исчислению Архивировано 21 марта 2012 г. в Wayback Machine
7. Yde Venema (2008) Лекции по модальному μ-исчислению Архивировано 21 марта 2012 г. в Wayback Machine
8. Коксетер, Х. С. М. (1942). Неевклидова геометрия . Издательство Торонтского университета . С. 36.
9. GB Halsted (1906) Синтетическая проективная геометрия , стр. 27
10. Уилсон, Кеннет Г. (1971). «Группа перенормировки и критические явления. I. Группа перенормировки и картина масштабирования Каданова». Physical Review B. 4 ( 9): 3174–3183. Bibcode :1971PhRvB...4.3174W. doi : 10.1103/PhysRevB.4.3174 .
11. Уилсон, Кеннет Г. (1971). «Группа перенормировки и критические явления. II. Анализ критического поведения с помощью ячеек фазового пространства». Physical Review B. 4 ( 9): 3184–3205. Bibcode : 1971PhRvB...4.3184W. doi : 10.1103/PhysRevB.4.3184 .
12. "П. Кусо и Р. Кусо, Абстрактная интерпретация: унифицированная решетчатая модель для статического анализа программ путем построения или аппроксимации неподвижных точек".

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

• Элегантное решение для рисования фиксированной точки