Вычисления с фиксированной точкой

Вычисление неподвижной точки функции

Вычисление с фиксированной точкой относится к процессу вычисления точной или приблизительной фиксированной точки заданной функции. ^[1] В своей наиболее общей форме заданная функция удовлетворяет условию теоремы Брауэра о фиксированной точке : то есть является непрерывной и отображает единичный d -куб в себя. Теорема Брауэра о фиксированной точке гарантирует, что имеет фиксированную точку, но доказательство не является конструктивным . Были разработаны различные алгоритмы для вычисления приблизительной фиксированной точки. Такие алгоритмы используются в экономике для вычисления рыночного равновесия , в теории игр для вычисления равновесия Нэша и в динамическом системном анализе. ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f}$

Определения

График примера функции с тремя неподвижными точками

Единичный интервал обозначается как , а единичный d -мерный куб обозначается как . Непрерывная функция определена на (от до себя) . Часто предполагается, что является не только непрерывной, но и липшицевой , то есть для некоторой константы , для всех в . ${\displaystyle E:=[0,1]}$ ${\displaystyle E^{d}}$ ${\displaystyle f}$ ${\displaystyle E^{d}}$ ${\displaystyle E^{d}}$ ${\displaystyle f}$ ${\displaystyle L}$ ${\displaystyle |f(x)-f(y)|\leq L\cdot |x-y|}$ ${\displaystyle x,y}$ ${\displaystyle E^{d}}$

Неподвижная точка — это точка в такая, что . По теореме Брауэра о неподвижной точке любая непрерывная функция из в сама по себе имеет неподвижную точку. Но для общих функций невозможно точно вычислить неподвижную точку, поскольку она может быть произвольным действительным числом. Алгоритмы вычисления неподвижной точки ищут приближенные неподвижные точки. Существует несколько критериев для приближенной неподвижной точки. Несколько общих критериев: ^[2] ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle E^{d}}$ ${\displaystyle f(x)=x}$ ${\displaystyle E^{d}}$

• Остаточный критерий : при заданном параметре аппроксимации , ε- остаточная неподвижная точка — это точка в ' такая, что , где здесь обозначает максимальную норму . То есть все координаты разности должны быть не более ε . ^{[3] : 4} ${\displaystyle \varepsilon >0}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle E^{d}}$ ${\displaystyle |f(x)-x|\leq \varepsilon }$ ${\displaystyle |\cdot |}$ ${\displaystyle d}$ ${\displaystyle f(x)-x}$
• Абсолютный критерий : при заданном параметре аппроксимации δ -абсолютная неподвижная точка — это точка из , такая что , где — любая неподвижная точка из . ${\displaystyle \delta >0}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle E^{d}}$ ${\displaystyle |x-x_{0}|\leq \delta }$ ${\displaystyle x_{0}}$ ${\displaystyle f}$
• Относительный критерий : при заданном параметре аппроксимации δ -относительная неподвижная точка — это точка x в такая, что , где — любая неподвижная точка из . ${\displaystyle \delta >0}$ ${\displaystyle f}$ ${\displaystyle E^{d}}$ ${\displaystyle |x-x_{0}|/|x_{0}|\leq \delta }$ ${\displaystyle x_{0}}$ ${\displaystyle f}$

Для липшицево-непрерывных функций абсолютный критерий сильнее критерия остатка: если липшицево-непрерывно с константой , то следует . Поскольку является неподвижной точкой , это следует , поэтому . Следовательно, δ-абсолютная неподвижная точка также является ε -остаточной неподвижной точкой с . ${\displaystyle f}$ ${\displaystyle L}$ ${\displaystyle |x-x_{0}|\leq \delta }$ ${\displaystyle |f(x)-f(x_{0})|\leq L\cdot \delta }$ ${\displaystyle x_{0}}$ ${\displaystyle f}$ ${\displaystyle |f(x)-x_{0}|\leq L\cdot \delta }$ ${\displaystyle |f(x)-x|\leq (1+L)\cdot \delta }$ ${\displaystyle \varepsilon =(1+L)\cdot \delta }$

Самым базовым шагом алгоритма вычисления с фиксированной точкой является запрос значения : если задано любое в , алгоритму предоставляется оракул , который возвращает значение . Точность приближенного значения с фиксированной точкой зависит от ошибки в оракуле . ${\displaystyle x}$ ${\displaystyle E^{d}}$ ${\displaystyle {\tilde {f}}}$ ${\displaystyle f}$ ${\displaystyle f(x)}$ ${\displaystyle {\tilde {f}}(x)}$

Функция доступна через запросы оценки : для любого алгоритм может оценить . Сложность выполнения алгоритма обычно определяется числом требуемых оценок. ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle f(x)}$

Контрактивные функции

Липшицева функция с константой называется сжимающей , если ; она называется слабо сжимающей, если . Каждая сжимающая функция, удовлетворяющая условиям Брауэра, имеет единственную неподвижную точку. Более того, вычисление неподвижной точки для сжимающих функций проще, чем для общих функций. ${\displaystyle L}$ ${\displaystyle L<1}$ ${\displaystyle L\leq 1}$

Вычисление фиксированной точки с использованием итерации функции

Первым алгоритмом для вычисления с фиксированной точкой был алгоритм итерации с фиксированной точкой Банаха. Теорема Банаха о фиксированной точке подразумевает, что когда итерация с фиксированной точкой применяется к отображению сжатия, ошибка после итераций составляет . Таким образом, количество вычислений, требуемых для -относительной фиксированной точки, приблизительно равно . Сикорский и Возняковский ^[4] показали, что алгоритм Банаха оптимален, когда размерность велика. В частности, когда количество требуемых вычислений любого алгоритма для -относительной фиксированной точки больше 50% от количества вычислений, требуемых алгоритмом итерации. Обратите внимание, что когда приближается к 1, количество вычислений стремится к бесконечности. Ни один конечный алгоритм не может вычислить -абсолютную фиксированную точку для всех функций с . ^[5] ${\displaystyle t}$ ${\displaystyle O(L^{t})}$ ${\displaystyle \delta }$ ${\displaystyle \log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)}$ ${\displaystyle d\geq \log(1/\delta )/\log(1/L)}$ ${\displaystyle \delta }$ ${\displaystyle L}$ ${\displaystyle \delta }$ ${\displaystyle L=1}$

Когда < 1 и d = 1, оптимальным алгоритмом является алгоритм Fixed Point Envelope (FPE) Сикорского и Возняковского. ^[4] Он находит δ -относительную фиксированную точку с помощью запросов и δ -абсолютную фиксированную точку с помощью запросов. Это быстрее, чем алгоритм итерации с фиксированной точкой. ^[6] ${\displaystyle L}$ ${\displaystyle O(\log(1/\delta )+\log \log(1/(1-L)))}$ ${\displaystyle O(\log(1/\delta ))}$

Когда , но не слишком большое, и , оптимальным алгоритмом является алгоритм внутреннего эллипсоида (основанный на методе эллипсоида ). ^[7] Он находит ε -остаточную неподвижную точку с помощью оценок. Когда , он находит -абсолютную неподвижную точку с помощью оценок. ${\displaystyle d>1}$ ${\displaystyle L\leq 1}$ ${\displaystyle O(d\cdot \log(1/\varepsilon ))}$ ${\displaystyle L<1}$ ${\displaystyle \delta }$ ${\displaystyle O(d\cdot [\log(1/\delta )+\log(1/(1-L))])}$

Шеллман и Сикорский ^[8] представили алгоритм под названием BEFix (Bisection Envelope Fixed-point) для вычисления ε -остаточной фиксированной точки двумерной функции с ' , используя только запросы. Позже они ^[9] представили усовершенствование под названием BEDFix (Bisection Envelope Deep-cut Fixed-point) с той же гарантией в худшем случае, но с лучшей эмпирической производительностью. Когда , BEDFix также может вычислить -абсолютную фиксированную точку с помощью запросов. ${\displaystyle L\leq 1}$ ${\displaystyle 2\lceil \log _{2}(1/\varepsilon )\rceil +1}$ ${\displaystyle L<1}$ ${\displaystyle \delta }$ ${\displaystyle O(\log(1/\varepsilon )+\log(1/(1-L)))}$

Шеллман и Сикорский ^[2] представили алгоритм под названием PFix для вычисления ε -остаточной фиксированной точки d -мерной функции с L ≤ 1 с использованием запросов. Когда < 1, PFix может быть выполнен с , и в этом случае он вычисляет δ-абсолютную фиксированную точку с использованием запросов. Он более эффективен, чем итерационный алгоритм, когда близок к 1. Алгоритм рекурсивен: он обрабатывает d -мерную функцию рекурсивными вызовами ( d -1)-мерных функций. ${\displaystyle O(\log ^{d}(1/\varepsilon ))}$ ${\displaystyle L}$ ${\displaystyle \varepsilon =(1-L)\cdot \delta }$ ${\displaystyle O(\log ^{d}(1/[(1-L)\delta ]))}$ ${\displaystyle L}$

Алгоритмы для дифференцируемых функций

Когда функция дифференцируема и алгоритм может вычислить ее производную (а не только саму себя), можно использовать метод Ньютона , и он намного быстрее. ^{[10] [11]} ${\displaystyle f}$ ${\displaystyle f}$

Общие функции

Для функций с константой Липшица > 1 вычисление фиксированной точки намного сложнее. ${\displaystyle L}$

Одно измерение

Для одномерной функции ( d = 1) -абсолютная неподвижная точка может быть найдена с помощью запросов, использующих метод деления пополам : начать с интервала ; на каждой итерации пусть будет центром текущего интервала и вычислить ; если то рекурсия на подинтервале справа от ; в противном случае рекурсия на интервале слева от . Обратите внимание, что текущий интервал всегда содержит неподвижную точку, поэтому после запросов любая точка в оставшемся интервале является -абсолютной неподвижной точкой Установка , где - константа Липшица, дает ε -остаточную неподвижную точку, используя запросы. ^[3] ${\displaystyle \delta }$ ${\displaystyle O(\log(1/\delta ))}$ ${\displaystyle E:=[0,1]}$ ${\displaystyle x}$ ${\displaystyle f(x)}$ ${\displaystyle f(x)>x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle O(\log(1/\delta ))}$ ${\displaystyle \delta }$ ${\displaystyle f}$ ${\displaystyle \delta :=\varepsilon /(L+1)}$ ${\displaystyle L}$ ${\displaystyle O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))}$

Два или более измерений

Для функций в двух или более измерениях проблема гораздо сложнее. Шеллман и Сикорский ^[2] доказали, что для любых целых чисел d ≥ 2 и > 1 нахождение δ-абсолютной неподвижной точки d -мерных -липшицевых функций может потребовать бесконечно много вычислений. Идея доказательства заключается в следующем. Для любого целого числа T > 1 и любой последовательности T запросов оценки (возможно, адаптивной) можно построить две функции, которые являются непрерывными по Липшицу с константой , и дать один и тот же ответ на все эти запросы, но одна из них имеет уникальную неподвижную точку в ( x , 0), а другая имеет уникальную неподвижную точку в ( x , 1). Любой алгоритм, использующий оценки T , не может различать эти функции, поэтому не может найти δ-абсолютную неподвижную точку. Это верно для любого конечного целого числа T . ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L}$

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

• Первый алгоритм для аппроксимации неподвижной точки общей функции был разработан Гербертом Скарфом в 1967 году. ^{[12] [13]} Алгоритм Скарфа находит ε- остаточную неподвижную точку, находя полностью помеченное «примитивное множество» в конструкции, аналогичной лемме Шпернера .
• Более поздний алгоритм Гарольда Куна ^[14] использовал симплексы и симплициальные разбиения вместо примитивных множеств.
• Развивая симплициальный подход дальше, Орин Харрисон Меррилл ^[15] представил алгоритм перезапуска .
• B. Curtis Eaves ^[16] представил алгоритм гомотопии . Алгоритм работает, начиная с аффинной функции, которая приближает , и деформируя ее в направлении , следуя неподвижной точке . В книге Майкла Тодда ^[1] рассматривается ряд алгоритмов, разработанных до 1976 года. ${\displaystyle f}$ ${\displaystyle f}$
• Дэвид Гейл ^[17] показал, что вычисление фиксированной точки n -мерной функции (на единичном d -мерном кубе) эквивалентно решению, кто является победителем в d -мерной игре Hex (игра с d игроками, каждому из которых нужно соединить две противоположные грани d -куба). При заданной точности ε
  • Постройте шестиугольную доску размером kd , где . Каждая вершина z соответствует точке z / k в единичном n -кубе. ${\displaystyle k>1/\varepsilon }$
  • Вычислите разность ( z / k ) - z / k ; обратите внимание, что разность представляет собой n -вектор. ${\displaystyle f}$
  • Пометим вершину z меткой из 1, ..., d , обозначающей наибольшую координату в векторе разности.
  • Полученная маркировка соответствует возможной игре в d -мерную игру Hex среди d игроков. В этой игре должен быть победитель, и Гейл представляет алгоритм построения выигрышного пути.
  • На выигрышном пути должна быть точка, в которой f _i ( z / k ) - z / k положительна, и смежная точка, в которой f _i ( z / k ) - z / k отрицательна. Это означает, что между этими двумя точками есть фиксированная точка . ${\displaystyle f}$

В худшем случае количество вычислений функций, требуемых всеми этими алгоритмами, экспоненциально в двоичном представлении точности, то есть в . ${\displaystyle \Omega (1/\varepsilon )}$

Сложность запроса

Хирш, Пападимитриу и Вавасис доказали, что ^[3] любой алгоритм, основанный на оценках функций, который находит ε- остаточную неподвижную точку f, требует оценок функций, где — константа Липшица функции (обратите внимание, что ). Точнее: ${\displaystyle \Omega (L'/\varepsilon )}$ ${\displaystyle L'}$ ${\displaystyle f(x)-x}$ ${\displaystyle L-1\leq L'\leq L+1}$

• Для двумерной функции ( d =2) они доказывают точную границу . ${\displaystyle \Theta (L'/\varepsilon )}$
• Для любого d ≥ 3 нахождение ε -остаточной неподвижной точки d -мерной функции требует запросов и запросов. ${\displaystyle \Omega ((L'/\varepsilon )^{d-2})}$ ${\displaystyle O((L'/\varepsilon )^{d})}$

Последний результат оставляет пробел в показателе. Чэнь и Дэн ^[18] закрыли этот пробел. Они доказали, что для любого d ≥ 2 и и количество запросов, необходимых для вычисления ε- остаточной фиксированной точки, составляет . ${\displaystyle 1/\varepsilon >4d}$ ${\displaystyle L'/\varepsilon >192d^{3}}$ ${\displaystyle \Theta ((L'/\varepsilon )^{d-1})}$

Дискретное вычисление с фиксированной точкой

Дискретная функция — это функция, определенная на подмножестве ( d -мерной целочисленной сетки). Существует несколько теорем о дискретной неподвижной точке , устанавливающих условия, при которых дискретная функция имеет неподвижную точку. Например, теорема Иимуры-Муроты-Тамуры утверждает, что (в частности) если — функция из прямоугольного подмножества в себя и является гиперкубической , сохраняющей направление , то имеет неподвижную точку. ${\displaystyle \mathbb {Z} ^{d}}$ ${\displaystyle f}$ ${\displaystyle \mathbb {Z} ^{d}}$ ${\displaystyle f}$ ${\displaystyle f}$

Пусть будет функцией, сохраняющей направление от целочисленного куба к себе. Чен и Дэн ^[18] доказывают, что для любого d ≥ 2 и n > 48 d вычисление такой фиксированной точки требует оценок функции. ${\displaystyle f}$ ${\displaystyle \{1,\dots ,n\}^{d}}$ ${\displaystyle \Theta (n^{d-1})}$

Чен и Дэн ^[19] определяют другую задачу с дискретной неподвижной точкой, которую они называют 2D-BROUWER . Она рассматривает дискретную функцию на , такую, что для каждого x на сетке ( x ) - x равно либо (0, 1), либо (1, 0), либо (-1, -1). Цель состоит в том, чтобы найти квадрат в сетке, в котором встречаются все три метки. Функция должна отображать квадрат на себя, поэтому она должна отображать линии x = 0 и y = 0 либо на (0, 1), либо на (1, 0); линию x = n либо на (-1, -1), либо на (0, 1); а линию y = n либо на (-1, -1), либо на (1,0). Задача может быть сведена к 2D-SPERNER (вычисление полностью помеченного треугольника в триангуляции, удовлетворяющей условиям леммы Шпернера ), и, следовательно, она является PPAD-полной . Это означает, что вычисление приближенной фиксированной точки является PPAD-полным даже для очень простых функций. ${\displaystyle f}$ ${\displaystyle \{0,\dots ,n\}^{2}}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle \{0,\dots ,n\}^{2}}$

Связь между вычислениями с фиксированной точкой и алгоритмами поиска корня

Для данной функции из в R корень — это точка x в такая, что ( x )=0. ε -корень g — это точка x в такая, что . ${\displaystyle g}$ ${\displaystyle E^{d}}$ ${\displaystyle g}$ ${\displaystyle E^{d}}$ ${\displaystyle g}$ ${\displaystyle E^{d}}$ ${\displaystyle g(x)\leq \varepsilon }$

Вычисление с фиксированной точкой является частным случаем поиска корня: задана функция на , определите . X является фиксированной точкой тогда и только тогда, когда x является корнем , а x является ε -остаточной фиксированной точкой тогда и только тогда, когда x является ε -корнем . Таким образом, любой алгоритм поиска корня (алгоритм, который вычисляет приближенный корень функции) может быть использован для поиска приближенной фиксированной точки. ${\displaystyle f}$ ${\displaystyle E^{d}}$ ${\displaystyle g(x):=|f(x)-x|}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle g}$

Обратное неверно: нахождение приближенного корня общей функции может быть сложнее, чем нахождение приближенной неподвижной точки. В частности, Сикорский ^[20] доказал, что нахождение ε -корня требует оценок функций. Это дает экспоненциальную нижнюю границу даже для одномерной функции (в отличие от этого, ε -остаточную неподвижную точку одномерной функции можно найти с помощью запросов, использующих метод бисекции ). Вот набросок доказательства. ^{[3] : 35} Постройте функцию , которая немного больше ε везде в , за исключением некоторого малого куба вокруг некоторой точки x ₀ , где x ₀ является единственным корнем . Если непрерывна по Липшицу с константой , то куб вокруг x ₀ может иметь длину стороны . Любой алгоритм, который находит ε -корень , должен проверить набор кубов, который покрывает все ; число таких кубов не менее . ${\displaystyle \Omega (1/\varepsilon ^{d})}$ ${\displaystyle O(\log(1/\varepsilon ))}$ ${\displaystyle g}$ ${\displaystyle E^{d}}$ ${\displaystyle g}$ ${\displaystyle g}$ ${\displaystyle L}$ ${\displaystyle \varepsilon /L}$ ${\displaystyle g}$ ${\displaystyle E^{d}}$ ${\displaystyle (L/\varepsilon )^{d}}$

Однако существуют классы функций, для которых нахождение приближенного корня эквивалентно нахождению приближенной неподвижной точки. Одним из примеров ^[18] является класс функций, такой что отображается в себя (то есть: находится в для всех x в ). Это происходит потому, что для каждой такой функции функция удовлетворяет условиям теоремы Брауэра о неподвижной точке. X является неподвижной точкой тогда и только тогда, когда x является корнем , а x является ε -остаточной неподвижной точкой тогда и только тогда, когда x является ε -корнем . Чэнь и Дэн ^[18] показывают, что дискретные варианты этих задач вычислительно эквивалентны: обе задачи требуют оценки функций. ${\displaystyle g}$ ${\displaystyle g(x)+x}$ ${\displaystyle E^{d}}$ ${\displaystyle g(x)+x}$ ${\displaystyle E^{d}}$ ${\displaystyle E^{d}}$ ${\displaystyle f(x):=g(x)+x}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle \Theta (n^{d-1})}$

Сложность коммуникации

Рафгарден и Вайнштейн ^[21] изучали сложность связи при вычислении приближенной фиксированной точки. В их модели есть два агента: один из них знает функцию , а другой знает функцию . Обе функции являются непрерывными по Липшицу и удовлетворяют условиям Брауэра. Цель состоит в том, чтобы вычислить приближенную фиксированную точку составной функции . Они показывают, что детерминированная сложность связи находится в . ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle g\circ f}$ ${\displaystyle \Omega (2^{d})}$

Ссылки

1. Вычисление неподвижных точек и приложения . Конспект лекций по экономике и математическим системам. Том 124. 1976. doi :10.1007/978-3-642-50327-6. ISBN 978-3-540-07685-8.
2. Шеллман, Спенсер; Сикорский, К. (декабрь 2003 г.). «Рекурсивный алгоритм для проблемы фиксированной точки с бесконечной нормой». Journal of Complexity . 19 (6): 799–834. doi : 10.1016/j.jco.2003.06.001 .
3. Хирш, Майкл Д.; Пападимитриу, Христос Х.; Вавасис, Стивен А. (декабрь 1989 г.). «Экспоненциальные нижние границы для поиска неподвижных точек Брауэра». Journal of Complexity . 5 (4): 379–416. doi :10.1016/0885-064X(89)90017-4. S2CID  1727254.
4. Sikorski, K; Woźniakowski, H (декабрь 1987 г.). «Сложность неподвижных точек, I». Journal of Complexity . 3 (4): 388–405. doi : 10.1016/0885-064X(87)90008-2 .
5. Сикорский, Кшиштоф А. (2001). Оптимальное решение нелинейных уравнений . Oxford University Press. ISBN 978-0-19-510690-9.^{[ нужна страница ]}
6. Сикорский, К. (1989). «Быстрые алгоритмы для вычисления неподвижных точек». Надежность в идентификации и управлении . стр. 49–58. doi :10.1007/978-1-4615-9552-6_4. ISBN 978-1-4615-9554-0.
7. Хуан, З.; Хачиян, Л.; Сикорский, К. (июнь 1999 г.). «Аппроксимация неподвижных точек слабо сжимающих отображений». Журнал сложности . 15 (2): 200–213. doi : 10.1006/jcom.1999.0504 .
8. Шеллман, Спенсер; Сикорский, К. (июнь 2002 г.). «Двумерный алгоритм деления огибающей пополам для неподвижных точек». Журнал сложности . 18 (2): 641–659. doi : 10.1006/jcom.2001.0625 .
9. Шеллман, Спенсер; Сикорский, К. (сентябрь 2003 г.). «Алгоритм 825: алгоритм глубокого деления огибающей пополам для неподвижных точек». Труды ACM по математическому программному обеспечению . 29 (3): 309–325. doi :10.1145/838250.838255. S2CID  7786886.
10. Келлог, Р. Б.; Ли, Т. Ю.; Йорк, Дж. (сентябрь 1976 г.). «Конструктивное доказательство теоремы Брауэра о неподвижной точке и результаты вычислений». Журнал SIAM по численному анализу . 13 (4): 473–483. doi :10.1137/0713041.
11. Смейл, Стив (июль 1976 г.). «Конвергентный процесс корректировки цен и глобальные методы Ньютона». Журнал математической экономики . 3 (2): 107–120. doi :10.1016/0304-4068(76)90019-7.
12. Скарф, Герберт (сентябрь 1967 г.). «Аппроксимация неподвижных точек непрерывного отображения». Журнал SIAM по прикладной математике . 15 (5): 1328–1343. doi :10.1137/0115116.
13. Х. Скарф нашел первое алгоритмическое доказательство: Войцеховский, МИ (2001) [1994]. "Теорема Брауэра". Энциклопедия математики . EMS Press . ISBN 1-4020-0609-8..
14. Кун, Гарольд В. (1968). «Симплициальное приближение неподвижных точек». Труды Национальной академии наук Соединенных Штатов Америки . 61 (4): 1238–1242. doi : 10.1073/pnas.61.4.1238 . JSTOR  58762. PMC 225246. PMID  16591723 . 
15. Меррилл, Орин Харрисон (1972). Приложения и расширения алгоритма, вычисляющего неподвижные точки некоторых полунепрерывных сверху точек для множеств отображений (диссертация). OCLC  570461463. NAID  10006142329.
16. Ивс, Б. Кертис (декабрь 1972 г.). «Гомотопии для вычисления неподвижных точек». Математическое программирование . 3–3 (1): 1–22. doi :10.1007/BF01584975. S2CID  39504380.
17. Гейл, Дэвид (1979). «Игра в гексагон и теорема Брауэра о неподвижной точке». The American Mathematical Monthly . 86 (10): 818–827. doi :10.2307/2320146. JSTOR  2320146.
18. Чэнь, Си; Дэн, Сяоте (2005). «Об алгоритмах для дискретных и приближенных фиксированных точек Брауэра». Труды тридцать седьмого ежегодного симпозиума ACM по теории вычислений . стр. 323–330. doi :10.1145/1060590.1060638. ISBN 1581139608. S2CID  16942881.
19. Чэнь, Си; Дэн, Сяоте (октябрь 2009 г.). «О сложности двумерной дискретной задачи с фиксированной точкой». Теоретическая информатика . 410 (44): 4448–4456. doi :10.1016/j.tcs.2009.07.052. S2CID  2831759.
20. Сикорски, К. (июнь 1984 г.). «Оптимальное решение нелинейных уравнений, удовлетворяющих условию Липшица». Числовая математика . 43 (2): 225–240. дои : 10.1007/BF01390124. S2CID  120937024.
21. Рафгарден, Тим; Вайнштейн, Омри (2016). «О коммуникационной сложности приближенных неподвижных точек». 57-й ежегодный симпозиум IEEE по основам компьютерной науки (FOCS) 2016 г. стр. 229–238. doi :10.1109/FOCS.2016.32. ISBN 978-1-5090-3933-3. S2CID  87553.

Дальнейшее чтение

• Яннакакис, Михалис (май 2009 г.). «Равновесия, неподвижные точки и классы сложности». Computer Science Review . 3 (2): 71–85. arXiv : 0802.2831 . doi :10.1016/j.cosrev.2009.03.004.