stringtranslate.com

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

В математике теорема о неподвижной точке — это результат, утверждающий, что функция F будет иметь по крайней мере одну неподвижную точку (точку x , для которой F ( x ) = x ) при некоторых условиях на F , которые можно сформулировать в общих чертах. [1]

В математическом анализе

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

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

Например, функция косинуса непрерывна в [−1, 1] и отображает его в [−1, 1], и, таким образом, должна иметь неподвижную точку. Это становится ясно при рассмотрении наброска графика функции косинуса; неподвижная точка возникает там, где кривая косинуса y = cos( x ) пересекает линию y = x . Численно неподвижная точка (известная как число Дотти ) приблизительно равна x = 0,73908513321516 (таким образом, x = cos( x ) для этого значения x ).

Теорема Лефшеца о неподвижной точке [4] (и теорема Нильсена о неподвижной точке ) [5] из алгебраической топологии примечательна тем, что она дает, в некотором смысле, способ подсчета неподвижных точек.

Существует ряд обобщений теоремы Банаха о неподвижной точке и далее; они применяются в теории уравнений в частных производных . См. теоремы о неподвижной точке в бесконечномерных пространствах .

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

В алгебре и дискретной математике

Теорема Кнастера –Тарского утверждает, что любая функция, сохраняющая порядок на полной решетке, имеет неподвижную точку, и, действительно, наименьшую неподвижную точку. [7] См. также теорему Бурбаки–Витта .

Теорема имеет применение в абстрактной интерпретации , форме статического анализа программ .

Распространенной темой в лямбда-исчислении является поиск неподвижных точек заданных лямбда-выражений. Каждое лямбда-выражение имеет неподвижную точку, а комбинатор с неподвижной точкой — это «функция», которая принимает на вход лямбда-выражение и выдает на выходе неподвижную точку этого выражения. [8] Важным комбинатором с неподвижной точкой является комбинатор Y, используемый для задания рекурсивных определений.

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

Такое же определение рекурсивной функции можно дать в теории вычислимости , применив теорему Клини о рекурсии . [9] Эти результаты не являются эквивалентными теоремами; теорема Кнастера–Тарского является гораздо более сильным результатом, чем тот, что используется в денотационном семантике. [10] Однако в свете тезиса Чёрча–Тьюринга их интуитивное значение одинаково: рекурсивную функцию можно описать как наименьшую неподвижную точку некоторого функционала, отображающую функции в функции.

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

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

Каждая инволюция на конечном множестве с нечетным числом элементов имеет неподвижную точку; в более общем смысле, для каждой инволюции на конечном множестве элементов число элементов и число неподвижных точек имеют одинаковую четность . Дон Загир использовал эти наблюдения, чтобы дать однопредложениеное доказательство теоремы Ферма о суммах двух квадратов , описав две инволюции на одном и том же множестве троек целых чисел, одна из которых, как можно легко показать, имеет только одну неподвижную точку, а другая имеет неподвижную точку для каждого представления данного простого числа (сравнимого с 1 mod 4) в виде суммы двух квадратов. Поскольку первая инволюция имеет нечетное число неподвижных точек, то же самое делает и вторая, и, следовательно, всегда существует представление желаемой формы. [11]

Список теорем о неподвижной точке

Смотрите также

Сноски

  1. ^ Браун, РФ, ред. (1988). Теория неподвижной точки и ее приложения . Американское математическое общество. ISBN 0-8218-5080-6.
  2. ^ Джайлс, Джон Р. (1987). Введение в анализ метрических пространств . Cambridge University Press. ISBN 978-0-521-35928-3.
  3. ^ Эберхард Цайдлер, Прикладной функциональный анализ: основные принципы и их приложения , Springer, 1995.
  4. ↑ Соломон Лефшец (1937). «О формуле неподвижной точки». Ann. of Math. 38 (4): 819–822. doi :10.2307/1968838.
  5. ^ Фенхель, Вернер ; Нильсен, Якоб (2003). Шмидт, Асмус Л. (ред.). Разрывные группы изометрий в гиперболической плоскости . De Gruyter Studies in Mathematics. Том 29. Берлин: Walter de Gruyter & Co.
  6. ^ Барнсли, Майкл. (1988). Фракталы везде . Academic Press, Inc. ISBN 0-12-079062-9.
  7. ^ Альфред Тарский (1955). «Теорема о неподвижной точке в теории решеток и ее приложения». Pacific Journal of Mathematics . 5:2 : 285–309.
  8. ^ Пейтон Джонс, Саймон Л. (1987). Реализация функционального программирования. Prentice Hall International.
  9. ^ Катланд, Нью-Джерси, Вычислимость: введение в теорию рекурсивных функций , Cambridge University Press, 1980. ISBN 0-521-29465-7 
  10. ^ Основы верификации программ , 2-е издание, Жак Лёкс и Курт Зибер, John Wiley & Sons, ISBN 0-471-91282-4 , Глава 4; теорема 4.24, стр. 83, — это то, что используется в денотационном семантике, в то время как теорема Кнастера–Тарского приводится для доказательства в качестве упражнения 4.3–5 на стр. 90. 
  11. ^ Загир, Д. (1990), «Доказательство одним предложением того, что каждое простое число p  ≡ 1 (mod 4) является суммой двух квадратов», American Mathematical Monthly , 97 (2): 144, doi :10.2307/2323918, MR  1041893.

Ссылки

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