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

Функция с тремя фиксированными точками Точка сохраняется эндоморфизм

В математике, фиксированная точка (иногда сокращается до фиксированная точка, также известная как инвариантная точка ) функции является элементом домена функции, который отображается самой функцией. То есть c является неподвижной точкой функции f, если f (c) = c. Это означает, что f (f (... f (c)...)) = f (c) = c, важное завершающее соображение при рекурсивном вычислении f. Набор фиксированных точек иногда называют фиксированным набором.

Например, если f определяется в вещественных числах как

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

, тогда 2 - фиксированная точка f, потому что f (2) = 2.

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

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

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

Содержание

• 1 Привлекательные фиксированные точки
• 2 Приложения
• 3 Топологическое свойство фиксированной точки
• 4 Обобщение на частичные порядки: префиксная точка и постфиксная точка
• 5 См. Также
• 6 Примечания
• 7 Внешние ссылки

Привлекательные фиксированные точки

итерация фиксированной точки x n + 1 = cos x n с начальным значением x 1 = −1.

Притягивающая неподвижная точка функции f - это фиксированная точка x 0 функции f такая, что для любого значения x в области, достаточно близкого к x 0, итерационная функция последовательность

$x,\; f\; (x),\; f\; (f\; (x)),\; f\; (f\; (f\; (x))),\dots \; \{\backslash \; displaystyle\; x,\; \backslash \; f\; (x),\; \backslash \; f\; (f\; (x)),\; \backslash \; f\; (f\; (f\; (x))),\; \backslash \; dots\}$

сходится к x 0. Выражение предпосылок и доказательство существования такого решения дается теоремой Банаха о неподвижной точке.

Естественная функция косинуса («естественный» означает в радианах, а не градусы или другие единицы) имеет ровно одну фиксированную точку, что привлекательно. В этом случае «достаточно близко» вовсе не является строгим критерием - чтобы продемонстрировать это, начните с любого действительного числа и несколько раз нажмите клавишу cos на калькуляторе (сначала проверьте, находится ли калькулятор в режиме «радиан»). В конечном итоге она сходится к 0,739085133, что является фиксированной точкой. Здесь график функции косинуса пересекает линию $y\; =\; x\; \{\backslash \; displaystyle\; y\; =\; x\}$.

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

Привлекательные неподвижные точки являются частным случаем более широкого математического понятия аттракторов.

Притягивающая неподвижная точка называется устойчивой неподвижной точкой, если она также устойчива по Ляпунову.

Фиксированная точка называется нейтрально устойчивой фиксированной точкой, если она устойчива по Ляпунову, но не притягивает. Центр линейного однородного дифференциального уравнения второго порядка является примером нейтрально устойчивой неподвижной точки.

Несколько привлекательных очков можно собрать в привлекательный фиксированный набор.

Приложения

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

• В экономике, равновесие по Нэшу в игре является фиксированной точкой соответствия наилучшего ответа игры. Джон Нэш использовал теорему Какутани о фиксированной точке в своей основополагающей статье, которая принесла ему Нобелевскую премию по экономике.

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

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

• В теории типов, комбинатор с фиксированной точкой позволяет определять рекурсивные функции в нетипизированном лямбда-исчислении.

• Вектор значений PageRank всех веб-страниц является фиксированной точкой линейного преобразования, полученного из Вт структура звеньев всемирной паутины.

• Стационарное распределение цепи Маркова является фиксированной точкой функции вероятности перехода за один шаг.

• Логик Саул Крипке использует неподвижные точки в своей влиятельной теории истины. Он показывает, как можно сгенерировать частично определенный предикат истины (тот, который остается неопределенным для проблемных предложений типа «Это предложение не соответствует действительности»), рекурсивно определяя «истину», начиная с сегмента языка, который не содержит вхождений слова, и продолжается до тех пор, пока процесс не перестанет давать новые четко определенные предложения. (Это требует счетной бесконечности шагов.) То есть, для языка L пусть L ′ (читается как «L-простое число») будет языком, созданным добавлением к L для каждого предложения S в L, предложение «S верно». Фиксированная точка достигается, когда L 'равно L; на этом этапе предложения вроде «Это предложение не соответствует действительности» остаются неопределенными, поэтому, согласно Крипке, теория подходит для естественного языка, который содержит свой собственный предикат истинности.

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

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

$f:\; X\; \to \; X\; \{\backslash \; displaystyle\; f\; \backslash \; двоеточие\; От\; X\; \backslash \; до\; X\}$

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

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

Согласно теореме Брауэра о фиксированной точке, каждое компактное и выпуклое подмножество евклидова пространства имеет FPP. Сама по себе компактность не подразумевает FPP, а выпуклость даже не является топологическим свойством, поэтому имеет смысл спросить, как топологически охарактеризовать FPP. В 1932 году Борсук спросил, может ли компактность вместе с сжимаемостью быть необходимым и достаточным условием для удержания FPP. Проблема была открыта в течение 20 лет, пока гипотеза не была опровергнута Киношитой, который нашел пример компактного стягиваемого пространства без FPP.

Обобщение на частичные порядки: префиксная точка и постфиксная точка

Понятие и терминология обобщена до частичного порядка. Пусть ≤ - частичный порядок над множеством X и пусть f: X → X - функция над X. Тогда префиксная точка (также пишется префиксная точка ) для f - это любая p такое, что f (p) ≤ p. Аналогично постфиксная точка (или постфиксная точка ) для f - это любой p такой, что p ≤ f (p). Один из способов выразить теорему Кнастера – Тарского - сказать, что монотонная функция на полной решетке имеет наименьшую фиксированную точку, которая совпадает с его наименьшей префиксной точкой (и аналогично его наибольшая фиксированная точка совпадает с его наибольшей постфиксной точкой). Префиксные и постфиксные точки применяются в теоретической информатике.

См. Также

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

Примечания

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

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