Теорема о неподвижной точке
В математике теорема о неподвижной точке — это результат, утверждающий, что функция 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] из алгебраической топологии примечателен тем, что дает в некотором смысле способ подсчета неподвижных точек.
Существует ряд обобщений банаховой теоремы о неподвижной точке и других; они применяются в PDE теории . См. теоремы о неподвижной точке в бесконечномерных пространствах .
Теорема о коллаже во фрактальном сжатии доказывает, что для многих изображений существует относительно небольшое описание функции, которая при итеративном применении к любому исходному изображению быстро сходится к желаемому изображению. [6]
По алгебре и дискретной математике
[ редактировать ]Теорема Кнастера -Тарского утверждает, что любая сохраняющая порядок функция на полной решетке имеет фиксированную точку, причем наименьшую неподвижную точку. [7] См. также теорему Бурбаки–Витта .
Теорема имеет приложения в абстрактной интерпретации , форме статического анализа программ .
Общей темой лямбда-исчисления является поиск фиксированных точек заданных лямбда-выражений. Каждое лямбда-выражение имеет фиксированную точку, а комбинатор с фиксированной точкой — это «функция», которая принимает на вход лямбда-выражение и выдает на выходе фиксированную точку этого выражения. [8] Важным комбинатором с фиксированной точкой является комбинатор Y, используемый для предоставления рекурсивных определений.
В денотационной семантике языков программирования частный случай теоремы Кнастера – Тарского используется для установления семантики рекурсивных определений. Хотя теорема о неподвижной точке применяется к «одной и той же» функции (с логической точки зрения), развитие теории совершенно иное.
То же самое определение рекурсивной функции можно дать в теории вычислимости , применив теорему Клини о рекурсии . [9] Эти результаты не являются эквивалентными теоремами; Теорема Кнастера-Тарского - гораздо более сильный результат, чем тот, который используется в денотационной семантике. [10] Однако в свете тезиса Чёрча-Тьюринга их интуитивный смысл один и тот же: рекурсивную функцию можно описать как наименее фиксированную точку определенного функционала, отображающую функции в функции.
Описанный выше метод итерации функции для поиска фиксированной точки также можно использовать в теории множеств ; лемма о неподвижной точке для нормальных функций утверждает, что любая непрерывная строго возрастающая функция от ординалов к ординалам имеет одну (и даже много) неподвижных точек.
Каждый оператор замыкания имеет ЧУУ множество фиксированных точек; это «закрытые элементы» по отношению к оператору замыкания, и они являются основной причиной, по которой оператор замыкания был определен в первую очередь.
Каждая инволюция на конечном множестве с нечетным числом элементов имеет неподвижную точку; в более общем смысле, для каждой инволюции на конечном наборе элементов количество элементов и количество неподвижных точек имеют одинаковую четность . Дон Загер использовал эти наблюдения, чтобы дать доказательство теоремы Ферма о суммах двух квадратов в одном предложении , описав две инволюции на одном и том же наборе троек целых чисел, одна из которых, как можно легко показать, имеет только одну неподвижную точку, а другая из которых имеет фиксированную точку для каждого представления данного простого числа (соответствующего 1 по модулю 4) в виде суммы двух квадратов. Поскольку первая инволюция имеет нечетное число неподвижных точек, то и вторая, поэтому всегда существует представление искомой формы. [11]
Список теорем о неподвижной точке
[ редактировать ]- Теорема Атьи–Ботта о неподвижной точке
- Банахова теорема о неподвижной точке
- Теорема Бекича
- Теорема Бореля о неподвижной точке
- Теорема Бурбаки – Витта
- Теорема Браудера о неподвижной точке
- Теорема Брауэра о неподвижной точке
- Теорема Роте о неподвижной точке
- Вам понравилась теорема о неподвижной точке
- Диагональная лемма , также известная как лемма о фиксированной точке, для создания самореферентных предложений логики первого порядка.
- Теорема Ловера о неподвижной точке
- Дискретные теоремы о неподвижной точке
- Теорема Эрла-Гамильтона о неподвижной точке
- Комбинатор с фиксированной точкой , который показывает, что каждый термин в нетипизированном лямбда-исчислении имеет фиксированную точку.
- Лемма о фиксированной точке для нормальных функций
- Свойство фиксированной точки
- Теоремы о неподвижной точке в бесконечномерных пространствах
- Инъективное метрическое пространство
- Теорема Какутани о неподвижной точке
- Теорема Клини о неподвижной точке
- Теорема Кнастера – Тарского
- Теорема Лефшеца о неподвижной точке
- Теорема Нильсена о неподвижной точке
- Теорема Пуанкаре – Биркгофа доказывает существование двух неподвижных точек.
- Теорема Рилла-Нардзевского о неподвижной точке
- Теорема вздрагивания о неподвижной точке
- Теория топологической степени
- Теорема Тихонова о неподвижной точке
См. также
[ редактировать ]Сноски
[ редактировать ]- ^ Браун, РФ, изд. (1988). Теория неподвижной точки и ее приложения . Американское математическое общество. ISBN 0-8218-5080-6 .
- ^ Джайлз, Джон Р. (1987). Введение в анализ метрических пространств . Издательство Кембриджского университета. ISBN 978-0-521-35928-3 .
- ^ Эберхард Зейдлер, Прикладной функциональный анализ: основные принципы и их приложения , Springer, 1995.
- ^ Соломон Лефшец (1937). «О формуле фиксированной точки». Энн. математики. 38 (4): 819–822. дои : 10.2307/1968838 .
- ^ Фенхель, Вернер ; Нильсен, Якоб (2003). Шмидт, Асмус Л. (ред.). Разрывные группы изометрий в гиперболической плоскости . Де Грюйтер Исследования по математике. Том. 29. Берлин: Вальтер де Грюйтер и компания.
- ^ Барнсли, Майкл. (1988). Фракталы повсюду . Academic Press, Inc. ISBN 0-12-079062-9 .
- ^ Альфред Тарский (1955). «Теорема о неподвижной точке из теории решетки и ее приложения» . Тихоокеанский математический журнал . 5:2 : 285–309.
- ^ Пейтон Джонс, Саймон Л. (1987). Реализация функционального программирования . Прентис Холл Интернэшнл.
- ^ Катленд, Нью-Джерси, Вычислимость: введение в теорию рекурсивных функций , Cambridge University Press, 1980. ISBN 0-521-29465-7
- ^ Основы проверки программ , 2-е издание, Жак Лёккс и Курт Зибер, John Wiley & Sons, ISBN 0-471-91282-4 , глава 4; теорема 4.24, стр. 83, используется в денотационной семантике, а теорема Кнастера – Тарского дана для доказательства в виде упражнения 4.3–5 на стр. 90.
- ^ Загер, Д. (1990), «Доказательство одним предложением того, что каждое простое число p ≡ 1 (по модулю 4) является суммой двух квадратов», American Mathematical Monthly , 97 (2): 144, doi : 10.2307/2323918 , MR 1041893 .
Ссылки
[ редактировать ]- Агарвал, Рави П.; Михан, Мария; О'Риган, Донал (2001). Теория фиксированной точки и ее приложения . Издательство Кембриджского университета. ISBN 0-521-80250-4 .
- Аксой, Асуман ; Хамси, Мохамед А. (1990). Нестандартные методы в теории неподвижной точки . Спрингер Верлаг. ISBN 0-387-97364-8 .
- Беринде, Василе (2005). Итеративная аппроксимация фиксированной точки . Спрингер Верлаг. 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). Справочник по метрической теории фиксированной точки . Спрингер-Верлаг. ISBN 0-7923-7073-2 .
- Шашкин, Юрий А; Миначин, Виктор; Макки, Джордж В. (1991). Фиксированные точки . Американское математическое общество. ISBN 0-8218-9000-Х .