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

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

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

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

Напротив, Теорема Брауэра о неподвижной точке не-конструктивный результат: там сказано, что любой непрерывная функция из закрытого единичный мяч в п-размерный Евклидово пространство для себя должен иметь фиксированную точку,[4] но он не описывает, как найти фиксированную точку (см. также Лемма Спернера ).

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

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

Есть ряд обобщений на Теорема Банаха о неподвижной точке и далее; они применяются в PDE теория. Увидеть теоремы о неподвижной точке в бесконечномерных пространствах.

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

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

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

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

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

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

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

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

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

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

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

Сноски

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

использованная литература

  • Agarwal, Ravi P .; Михан, Мария; О'Реган, Донал (2001). Теория фиксированной точки и приложения. Издательство Кембриджского университета. ISBN  0-521-80250-4.
  • Аксой, Асуман; Хамси, Мохамед А. (1990). Нестандартные методы теории неподвижной точки. Springer Verlag. ISBN  0-387-97364-8.
  • Беринде, Василе (2005). Итерационное приближение фиксированной точки. Springer Verlag. ISBN  978-3-540-72233-5.
  • Граница, Ким С. (1989). Теоремы о неподвижной точке в приложениях к экономике и теории игр. Издательство Кембриджского университета. ISBN  0-521-38808-2.
  • Кирк, Уильям А .; Гебель, Казимеж (1990). Темы метрической теории фиксированной точки. Издательство Кембриджского университета. ISBN  0-521-38289-0.
  • Кирк, Уильям А .; Хамси, Мохамед А. (2001). Введение в метрические пространства и теорию неподвижной точки. Джон Вили, Нью-Йорк. ISBN  978-0-471-41825-2.
  • Кирк, Уильям А .; Симс, Брейли (2001). Справочник по метрической теории неподвижной точки. Springer-Verlag. ISBN  0-7923-7073-2.
  • Шашкин, Юрий А; Миначин, Виктор; Макки, Джордж У. (1991). Фиксированные точки. Американское математическое общество. ISBN  0-8218-9000-X.

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