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

Неподвижные точки в математике не следует путать с другими вариантами использования «фиксированной точки» или стационарными точками , где f' ( x ) = 0 .

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

В математике ( фиксированная точка иногда сокращается до 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$.

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

о

Основная статья: Теоремы о неподвижной точке

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

Например, теорема Банаха о неподвижной точке (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 лет, пока гипотеза не была опровергнута Киношитой, который нашел пример компактного сжимаемого пространства без ФПП.

Фиксированные точки частичных заказов

В теории предметной области понятие и терминология неподвижных точек обобщаются до частичного порядка . Пусть ≤ — частичный порядок над множеством X , и пусть f : X → X функция над X. — Затем префиксная точка (также пишется как префиксная точка , иногда сокращается до префиксной точки или префиксной точки ) — это f любой p такой, что f ( p ) ≤ p . Аналогично, постфиксная точка f — это любой p такой, что p ≤ f ( p ). Иногда встречается противоположное употребление. Малкис обосновывает представленное здесь определение следующим образом: «поскольку f стоит перед знаком неравенства в термине f ( x ) ≤ x , такой x называется предфиксированной точкой». Фиксированная точка — это точка, которая является одновременно префиксной и постфиксной точкой. Префиксные и постфиксные точки находят применение в теоретической информатике .

Наименьшая фиксированная точка

Основная статья: Наименьшая фиксированная точка

В теории порядка наименее фиксированная точка функции (ЧУУ) сама по из частично упорядоченного множества себе является фиксированной точкой, которая меньше друг друга в фиксированных точках в соответствии с порядком ЧУУ. Функция не обязательно должна иметь наименьшую фиксированную точку, но если она есть, то наименьшая фиксированная точка уникальна.

Один из способов выразить теорему Кнастера – Тарского — сказать, что монотонная функция на полной решетке имеет наименьшую неподвижную точку , которая совпадает с ее наименьшей префиксной точкой (и аналогичным образом ее наибольшая неподвижная точка совпадает с ее наибольшей постфиксной точкой).

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

Основная статья: Комбинатор с фиксированной запятой

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

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

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

Основная статья: Логика фиксированной точки

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

Приложения

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

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

См. также

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

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

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

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