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

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

Функция с тремя неподвижными точками

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

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

Формально c является неподвижной точкой функции f, если c принадлежит как области определения , так и кодомену функции f , и f ( c ) = c .

Например, если f определяется для действительных чисел формулой

$${\displaystyle f(x)=x^{2}-3x+4,}$$

ff (2) = 2

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

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

В численном анализе итерация с фиксированной точкой — это метод вычисления фиксированных точек функции. В частности, для данной функции с той же областью определения и кодоменом, точкой в ​​области определения итерация с фиксированной точкой равна ${\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. В 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 имеет одну или несколько неподвижных точек, то ${\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). «О некоторых сжимаемых континуумах без свойства фиксированной точки». Фонд. Математика. 40 (1): 96–98. дои : 10.4064/fm-40-1-96-98 . ISSN  0016-2736.
3. Смит, Майкл Б.; Плоткин, Гордон Д. (1982). «Теоретико-категорное решение рекурсивных уравнений предметной области» (PDF) . Материалы 18-го симпозиума IEEE по основам информатики . SIAM Journal of Computing (том 11). стр. 761–783. дои : 10.1137/0211062.
4. Патрик Кусо; Радия Кусо (1979). «Конструктивные версии теорем Тарского о неподвижной точке» (PDF) . Тихоокеанский математический журнал . 82 (1): 43–57. дои : 10.2140/pjm.1979.82.43.
5. Малкис, Александр (2015). «Многопоточная декартова абстрактная интерпретация многопоточных рекурсивных программ является полиномиальной» (PDF) . Проблемы с достижимостью . Конспекты лекций по информатике. 9328 : 114–127. дои : 10.1007/978-3-319-24537-9_11. ISBN 978-3-319-24536-2. S2CID  17640585. Архивировано из оригинала (PDF) 10 августа 2022 г.
6. Иде Венема (2008). Лекции по модальному μ-исчислению. Архивировано 21 марта 2012 г., в Wayback Machine.
7. Иде Венема (2008). Лекции по модальному μ-исчислению. Архивировано 21 марта 2012 г., в Wayback Machine.
8. Коксетер, HSM (1942). Неевклидова геометрия . Университет Торонто Пресс . п. 36.
9. ГБ Холстед (1906) Синтетическая проективная геометрия , страница 27
10. Уилсон, Кеннет Г. (1971). «Ренормгруппа и критические явления. I. Ренормгруппа и картина масштабирования Каданова». Физический обзор B . 4 (9): 3174–3183. Бибкод : 1971PhRvB...4.3174W. дои : 10.1103/PhysRevB.4.3174 .
11. Уилсон, Кеннет Г. (1971). «Ренормгруппа и критические явления. II. Анализ критического поведения фазово-пространственных ячеек». Физический обзор B . 4 (9): 3184–3205. Бибкод : 1971PhRvB...4.3184W. дои : 10.1103/PhysRevB.4.3184 .
12. «П. Кусо и Р. Кусо, Абстрактная интерпретация: унифицированная решетчатая модель для статического анализа программ путем построения или аппроксимации фиксированных точек».

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

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