Фиксированная точка (математика)
В математике ( фиксированная точка иногда сокращается до fixpoint ), также известная как инвариантная точка , — это значение, которое не изменяется при данном преобразовании . В частности, для функций фиксированная точка — это элемент, который функция отображает сама на себя.
Фиксированная точка функции
[ редактировать ]Формально c является неподвижной точкой функции f, если c принадлежит как области определения , так и кодомену функции f , и f ( c ) = c .
Например, если f определяется для действительных чисел формулой тогда 2 — неподвижная точка f , потому что f (2) = 2 .
Не все функции имеют фиксированные точки: например, 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 .
Приложения
[ редактировать ]Этот раздел нуждается в дополнительных цитатах для проверки . ( Июль 2018 г. ) |
Во многих областях равновесие или стабильность являются фундаментальными понятиями, которые можно описать в терминах фиксированных точек. Ниже приведены некоторые примеры.
- В проективной геометрии фиксированная точка проективности получила название двойной точки . [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 .
- ^ «П. Кусо и Р. Кузо, Абстрактная интерпретация: унифицированная решетчатая модель для статического анализа программ путем построения или аппроксимации фиксированных точек» .