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

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

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

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

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

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

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

В численном анализе итерация с фиксированной точкой — это метод вычисления фиксированных точек функции. В частности, если задана функция $f$ с тем же доменом и кодоменом, точка $x_{0}$ в области $f$ , итерация с фиксированной точкой

$x_{n+1}=f(x_{n}),\,n=0,1,2,\dots$

что приводит к последовательности $x_{0},x_{1},x_{2},\dots$ приложений повторяющимися функциями с $x_{0},f(x_{0}),f(f(x_{0})),\dots$ который, как надеются, сойдется к точке $x$ . Если $f$ непрерывна, то можно доказать, что полученное $x$ является фиксированной точкой $f$ .

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

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

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

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

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

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

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

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

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

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

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

Топологическое свойство фиксированной точки

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

f\colon X\to X

существует $x\in X$ такой, что $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 ]}

Комбинатор с фиксированной точкой

В комбинаторной логике информатики функцией комбинатор с фиксированной точкой является более высокого порядка. ${\mathsf {fix}}$ который возвращает фиксированную точку своей функции-аргумента, если она существует. Формально, если функция f имеет одну или несколько неподвижных точек, то

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

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

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

Приложения

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

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

См. также

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

Примечания

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

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

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

[1] Браун, РФ, изд. (1988). Теория неподвижной точки и ее приложения . Американское математическое общество. ISBN 0-8218-5080-6 .

[2] Киносита, С. (1953). «О некоторых сжимаемых непрерывностях без свойства фиксированной точки» . Фонд. Математика. 40 (1): 96–98. дои : 10.4064/fm-40-1-96-98 . ISSN 0016-2736 .

[SmythPlotkin1982-3] Смит, Майкл Б.; Плоткин, Гордон Д. (1982). «Теоретико-категорное решение рекурсивных уравнений предметной области» (PDF) . Материалы 18-го симпозиума IEEE по основам информатики . SIAM Journal of Computing (том 11). стр. 761–783. дои : 10.1137/0211062 .

[CousotCousot1979-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] «П. Кузо и Р. Кузо, Абстрактная интерпретация: унифицированная решетчатая модель для статического анализа программ путем построения или аппроксимации фиксированных точек» .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]