Jump to content

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

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

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

Приложения

[ редактировать ]

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

См. также

[ редактировать ]

Примечания

[ редактировать ]
  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. ^ «П. Кусо и Р. Кузо, Абстрактная интерпретация: унифицированная решетчатая модель для статического анализа программ путем построения или аппроксимации фиксированных точек» .
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: f8984cbb741da4c3b9814fc0d19a7c91__1711467540
URL1:https://arc.ask3.ru/arc/aa/f8/91/f8984cbb741da4c3b9814fc0d19a7c91.html
Заголовок, (Title) документа по адресу, URL1:
Fixed point (mathematics) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)