Картирование сокращений

В математике , сжатое отображение или сжатие или контрактор , в метрическом пространстве ( M , d ) — это функция f из M в себя, обладающая тем свойством, что существует некоторое действительное число. $0\leq k<1$ такой, что для всех x и y в M ,

d(f(x),f(y))\leq k\,d(x,y).

Наименьшее такое значение k называется Липшица константой f . Сжимающие карты иногда называют липшицевыми картами . Если вместо этого выполняется вышеуказанное условие для k ≤ 1, то отображение называется нерасширяющим .

В более общем смысле идею сжимающего отображения можно определить для отображений между метрическими пространствами. Таким образом, если ( M , d ) и ( N , d' ) — два метрических пространства, то $f:M\rightarrow N$ является сжимающим отображением, если существует константа $0\leq k<1$ такой, что

d'(f(x),f(y))\leq k\,d(x,y)

для всех x и y в M .

Каждое сжимающее отображение является липшицевым и, следовательно, равномерно непрерывным (для липшицевой непрерывной функции константа k уже не обязательно меньше 1).

Сжимающее отображение имеет не более одной фиксированной точки . , теорема Банаха о неподвижной точке утверждает, что каждое сжимающее отображение в непустом полном метрическом пространстве имеет единственную неподвижную точку и что для любого x в M повторяющаяся последовательность функций ( x , f ( x ), f ( f Более того x )) f ( f ( f ( x ))), ... сходится к неподвижной точке. Эта концепция очень полезна для итерированных функциональных систем , где часто используются сжимающие отображения . Теорема Банаха о неподвижной точке также применяется при доказательстве существования решений обыкновенных дифференциальных уравнений и используется в одном доказательстве теоремы об обратной функции . ^[1]

Сокращающие отображения играют важную роль в задачах динамического программирования . ^[2]^[3]

Твердо нерасширяющее картографирование [ править ]

Нерасширяющее отображение с $k=1$ может быть обобщено до строго нерастягивающего отображения в гильбертовом пространстве. ${\mathcal {H}}$ если для всех x и y в ${\mathcal {H}}$ :

\|f(x)-f(y)\|^{2}\leq \,\langle x-y,f(x)-f(y)\rangle .

где

d(x,y)=\|x-y\|

.

Это частный случай $\alpha$ усредненные нерасширяющие операторы с $\alpha =1/2$ . ^[4] Строго нерасширяющее отображение всегда нерасширяющее согласно неравенству Коши – Шварца .

Класс твердо нерасширяющихся отображений замкнут относительно выпуклых комбинаций , но не композиций. ^[5] В этот класс входят проксимальные отображения собственных, выпуклых, полунепрерывных снизу функций, а значит, в него входят и ортогональные проекции на непустые замкнутые выпуклые множества . Класс твердо нерастягивающих операторов равен множеству резольвент максимально монотонных операторов . ^[6] Удивительно, но хотя итерация нерасширяющих карт не дает гарантии нахождения фиксированной точки (например, умножение на -1), твердой нерасширяемости достаточно, чтобы гарантировать глобальную сходимость к фиксированной точке, при условии, что фиксированная точка существует. Точнее, если ${\text{Fix}}f:=\{x\in {\mathcal {H}}\ |\ f(x)=x\}\neq \varnothing$ , то для любой начальной точки $x_{0}\in {\mathcal {H}}$ , итерация

$(\forall n\in \mathbb {N} )\quad x_{n+1}=f(x_{n})$

дает сходимость к фиксированной точке $x_{n}\to z\in {\text{Fix}}f$ . Эта сходимость может быть слабой в бесконечномерной ситуации. ^[5]

Карта субподряда [ править ]

Карта субсжатия или субподрядчик — это карта f в метрическом пространстве ( M , d ), такая что

d(f(x),f(y))\leq d(x,y);

d(f(f(x)),f(x))<d(f(x),x)\quad {\text{unless}}\quad x=f(x).

Если образ субподрядчика f компактен , то f имеет неподвижную точку. ^[7]

Локально выпуклые пространства [ править ]

В локально выпуклом пространстве ( E , P ) с топологией, заданной набором P полунорм такое , , можно определить для любого p ∈ P p - сжатие как отображение f что существует некоторое k _p < 1 такое, что p ( f ( Икс ) - ж ( y )) ≤ k _п п ( Икс - y ) . Если f является p -сжатием для всех p ∈ P и ( E , P ) секвенциально полно, то f имеет неподвижную точку, заданную как предел любой последовательности x _{n +1} = f ( x _n ), и если ( E , P ) хаусдорфова , то неподвижная точка единственна. ^[8]

См. также [ править ]

Ссылки [ править ]

^ Шифрин, Теодор (2005). Многомерная математика . Уайли. стр. 244–260. ISBN 978-0-471-52638-4 .
^ Денардо, Эрик В. (1967). «Отображения сокращений в теории, лежащей в основе динамического программирования». Обзор СИАМ . 9 (2): 165–177. Бибкод : 1967SIAMR...9..165D . дои : 10.1137/1009030 .
^ Стоки, Нэнси Л .; Лукас, Роберт Э. (1989). Рекурсивные методы в экономической динамике . Кембридж: Издательство Гарвардского университета. стр. 49–55. ISBN 978-0-674-75096-8 .
^ Комбеттс, Патрик Л. (2004). «Решение монотонных включений с помощью композиций нерасширяющих усредненных операторов». Оптимизация . 53 (5–6): 475–504. дои : 10.1080/02331930412331327157 . S2CID 219698493 .
↑ Перейти обратно: Перейти обратно: ^а ^б Баушке, Хайнц Х. (2017). Выпуклый анализ и теория монотонных операторов в гильбертовых пространствах . Нью-Йорк: Спрингер.
^ Комбеттс, Патрик Л. (июль 2018 г.). «Теория монотонных операторов в выпуклой оптимизации». Математическое программирование . Б170 : 177–206. arXiv : 1802.02694 . Бибкод : 2018arXiv180202694C . дои : 10.1007/s10107-018-1303-3 . S2CID 49409638 .
^ Гольдштейн, А.А. (1967). Конструктивный реальный анализ . Серия Харпера по современной математике. Нью-Йорк-Эванстон-Лондон: Харпер и Роу. п. 17. Збл 0189.49703 .
^ Каин, Г.Л. младший; Нашед, МЗ (1971). «Неподвижные точки и устойчивость суммы двух операторов в локально выпуклых пространствах» . Тихоокеанский математический журнал . 39 (3): 581–592. дои : 10.2140/pjm.1971.39.581 .

Дальнейшее чтение [ править ]

Истратеску, Василе И. (1981). Теория фиксированной точки: Введение . Голландия: Д.Рейдель. ISBN 978-90-277-1224-0 . обеспечивает введение в бакалавриат.
Гранас, Анджей; Дугунджи, Джеймс (2003). Теория фиксированной точки . Нью-Йорк: Springer-Verlag. ISBN 978-0-387-00173-9 .
Кирк, Уильям А.; Симс, Брейли (2001). Справочник по метрической теории фиксированной точки . Лондон: Клювер Академик. ISBN 978-0-7923-7073-4 .
Нейлор, Арч В.; Селл, Джордж Р. (1982). Теория линейных операторов в технике и науке . Прикладные математические науки. Том. 40 (Второе изд.). Нью-Йорк: Спрингер. стр. 125–134. ISBN 978-0-387-90748-2 .

Булло, Франческо (2022). Теория сжатия динамических систем . Kindle Direct Publishing. ISBN 979-8-8366-4680-6 .

[shifrin-1] Шифрин, Теодор (2005). Многомерная математика . Уайли. стр. 244–260. ISBN 978-0-471-52638-4 .

[2] Денардо, Эрик В. (1967). «Отображения сокращений в теории, лежащей в основе динамического программирования». Обзор СИАМ . 9 (2): 165–177. Бибкод : 1967SIAMR...9..165D . дои : 10.1137/1009030 .

[3] Стоки, Нэнси Л .; Лукас, Роберт Э. (1989). Рекурсивные методы в экономической динамике . Кембридж: Издательство Гарвардского университета. стр. 49–55. ISBN 978-0-674-75096-8 .

[4] Комбеттс, Патрик Л. (2004). «Решение монотонных включений с помощью композиций нерасширяющих усредненных операторов». Оптимизация . 53 (5–6): 475–504. дои : 10.1080/02331930412331327157 . S2CID 219698493 .

[:0-5] Перейти обратно: Перейти обратно: ^а ^б Баушке, Хайнц Х. (2017). Выпуклый анализ и теория монотонных операторов в гильбертовых пространствах . Нью-Йорк: Спрингер.

[6] Комбеттс, Патрик Л. (июль 2018 г.). «Теория монотонных операторов в выпуклой оптимизации». Математическое программирование . Б170 : 177–206. arXiv : 1802.02694 . Бибкод : 2018arXiv180202694C . дои : 10.1007/s10107-018-1303-3 . S2CID 49409638 .

[Gold17-7] Гольдштейн, А.А. (1967). Конструктивный реальный анализ . Серия Харпера по современной математике. Нью-Йорк-Эванстон-Лондон: Харпер и Роу. п. 17. Збл 0189.49703 .

[8] Каин, Г.Л. младший; Нашед, МЗ (1971). «Неподвижные точки и устойчивость суммы двух операторов в локально выпуклых пространствах» . Тихоокеанский математический журнал . 39 (3): 581–592. дои : 10.2140/pjm.1971.39.581 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]