Теорема о фиксированной точке

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

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

Содержание

  • 1 В математическом анализе
  • 2 В алгебре и дискретной математике
  • 3 Список теорем о фиксированной точке
  • 4 Сноски
  • 5 Ссылки
  • 6 Внешние ссылки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сноски

  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. ^Эберхард Цейдлер, Прикладной функциональный анализ: основные принципы и их приложения, Springer, 1995.
  5. ^Соломон Лефшец (1937). «По формуле фиксированной точки». Энн. математики. 38(4): 819–822. doi : 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. ^Катленд, Нью-Джерси, Вычислимость: Введение в теорию рекурсивных функций, Cambridge University Press, 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. ^Zagier, D. (1990), «Одно- доказательство предложения, что каждое простое число p ≡ 1 (mod 4) является суммой двух квадратов », American Mathematical Monthly, 97(2): 144, doi : 10.2307 / 2323918, MR 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.

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

Последняя правка сделана 2021-05-20 07:38:24
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте