Дискретная теорема о неподвижной точке

В дискретной математике дискретная фиксированная точка — это фиксированная точка для функций, определенных на конечных множествах, обычно подмножествах целочисленной сетки. $\mathbb {Z} ^{n}$.

Дискретные теоремы о неподвижной точке были разработаны Иимурой, Мурота и Тамура, Чен и Дэн и другие. Который предоставляет опрос.

Основные понятия

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

Непрерывные теоремы о неподвижной точке часто требуют выпуклого множества . Аналогом этого свойства для дискретных множеств является целовыпуклое множество .

Неподвижная точка дискретной функции f определяется точно так же, как и для непрерывных функций: это точка x, для которой f ( x ) = x .

Для функций на дискретных множествах

Мы фокусируемся на функциях $f:X\to \mathbb {R} ^{n}$, где область X — непустое подмножество евклидова пространства $\mathbb {R} ^{n}$. ( X ) обозначает выпуклую оболочку X ch .

Теорема Иимура-Мурота-Тамура : Если X — конечное целовыпуклое подмножество $\mathbb {Z} ^{n}$, и $f:X\to {\text{ch}}(X)$ является гиперкубической функцией, сохраняющей направление (HDP) , то f имеет фиксированную точку.

Теорема Чена-Дэна : Если X — конечное подмножество $\mathbb {R} ^{n}$, и $f:X\to {\text{ch}}(X)$ является упрощенно сохраняющим направление (SDP) , то f имеет фиксированную точку.

Теоремы Янга :

• [3.6] Если X — конечное цело-выпуклое подмножество $\mathbb {Z} ^{n}$, $f:X\to \mathbb {R} ^{n}$ является упрощенно грубым сохранением направления (SGDP) , и для всех x в X существует некоторый g ( x )>0 такой, что $x+g(x)f(x)\in {\text{ch}}(X)$, то f имеет нулевую точку.
• [3.7] Если X — конечное гиперкубическое подмножество $\mathbb {Z} ^{n}$, с точкой минимума a и точкой максимума b , $f:X\to \mathbb {R} ^{n}$ является ВВП, и для любого x в X : $f_{i}(x_{1},\ldots ,x_{i-1},a_{i},x_{i+1},\ldots ,x_{n})\leq 0$ и $f_{i}(x_{1},\ldots ,x_{i-1},b_{i},x_{i+1},\ldots ,x_{n})\geq 0$, то f имеет нулевую точку. Это дискретный аналог теоремы Пуанкаре–Миранды . Это следствие предыдущей теоремы.
• [3.8] Если X — конечное цело-выпуклое подмножество $\mathbb {Z} ^{n}$, и $f:X\to {\text{ch}}(X)$ таков, что $f(x)-x$ является SGDP , то f имеет фиксированную точку. Это дискретный аналог теоремы Брауэра о неподвижной точке .
• [3.9] Если X = $\mathbb {Z} ^{n}$, $f:X\to \mathbb {R} ^{n}$ ограничен и $f(x)-x$ является SGDP, то f имеет неподвижную точку (это легко следует из предыдущей теоремы, если взять X в качестве подмножества $\mathbb {Z} ^{n}$ которая ограничивает f ).
• [3.10] Если X — конечное целовыпуклое подмножество $\mathbb {Z} ^{n}$, $F:X\to 2^{X}$ отображение точки -множества и для всех x в X : $F(x)={\text{ch}}(F(x))\cap \mathbb {Z} ^{n}$ , и существует функция f такая, что $f(x)\in {\text{ch}}(F(x))$ и $f(x)-x$ является ВВП, то существует точка y в X такая, что $y\in F(y)$. Это дискретный аналог теоремы Какутани о неподвижной точке , а функция f является аналогом непрерывной функции выбора .
• [3.12] Пусть X — конечное целовыпуклое подмножество $\mathbb {Z} ^{n}$и оно также симметрично в том смысле, что находится в X тогда и только тогда, когда -x находится в X. x Если $f:X\to \mathbb {R} ^{n}$ является SGDP относительно слабо симметричной триангуляции ch( X ) (в том смысле, что если s является симплексом на границе триангуляции тогда и только тогда, когда - s является), и $f(x)\cdot f(-y)\leq 0$ для каждой пары симплициально-связных точек x , y на границе ch( X ), то f имеет нулевую точку.
• Посмотреть опрос дополнительные теоремы.

Для разрывных функций на непрерывных множествах

Дискретные теоремы о неподвижной точке тесно связаны с теоремами о неподвижной точке о разрывных функциях. Они также используют условие сохранения направления вместо непрерывности.

Теорема Герингса-Лана-Тальмана-Янга о неподвижной точке :

Пусть X — непустое выпуклое компактное подмножество $\mathbb {R} ^{n}$. Пусть f : X → X — локально грубая функция, сохраняющая направление (LGDP) : в любой точке x , которая не является фиксированной точкой f , направление $f(x)-x$ в значительной степени сохраняется в некоторой окрестности x .: в том смысле, что для любых двух точек y , z в этой окрестности его внутренний продукт неотрицательен, т. е $(f(y)-y)\cdot (f(z)-z)\geq 0$. Тогда f неподвижную точку в X. имеет

Первоначально теорема сформулирована для многогранников, но Филипп Бич распространил ее на выпуклые компакты. Обратите внимание, что каждая непрерывная функция является LGDP, но функция LGDP может быть разрывной. Функция LGDP может даже не быть ни верхней, ни нижней полунепрерывной . Более того, существует конструктивный алгоритм аппроксимации этой неподвижной точки.

Приложения

Дискретные теоремы о неподвижной точке использовались для доказательства существования равновесия Нэша в дискретной игре и существования равновесия Вальраса на дискретном рынке.