Jump to content

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

В математике теорема о неподвижной точке — это результат, говорящий, что функция 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]

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

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

См. также

[ редактировать ]
  1. ^ Браун, РФ, изд. (1988). Теория неподвижной точки и ее приложения . Американское математическое общество. ISBN  0-8218-5080-6 .
  2. ^ Джайлз, Джон Р. (1987). Введение в анализ метрических пространств . Издательство Кембриджского университета. ISBN  978-0-521-35928-3 .
  3. ^ Эберхард Зейдлер, Прикладной функциональный анализ: основные принципы и их приложения , Springer, 1995.
  4. ^ Соломон Лефшец (1937). «О формуле фиксированной точки». Энн. математики. 38 (4): 819–822. дои : 10.2307/1968838 .
  5. ^ Фенхель, Вернер ; Нильсен, Джейкоб (2003). Шмидт, Асмус Л. (ред.). Разрывные группы изометрий в гиперболической плоскости . Де Грюйтер Исследования по математике. Том. 29. Берлин: Вальтер де Грюйтер и компания.
  6. ^ Барнсли, Майкл. (1988). Фракталы повсюду . Academic Press, Inc. ISBN  0-12-079062-9 .
  7. ^ Альфред Тарский (1955). «Теорема о неподвижной точке из теории решетки и ее приложения» . Тихоокеанский математический журнал . 5:2 : 285–309.
  8. ^ Пейтон Джонс, Саймон Л. (1987). Реализация функционального программирования . Прентис Холл Интернэшнл.
  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 (по модулю 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-Х .
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 4573f9f5802136aaa5438ed00a531c4a__1706910660
URL1:https://arc.ask3.ru/arc/aa/45/4a/4573f9f5802136aaa5438ed00a531c4a.html
Заголовок, (Title) документа по адресу, URL1:
Fixed-point theorem - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)