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

Метод Ньютона, метод Пикара, MCMC, равновесие Нэша - все они являются неподвижными точками некоторых операторов. Теоремы о неподвижной точке отвечают на вопрос "существует ли решение?" прежде чем мы начинаем его искать. Без этих теорем вся вычислительная математика и теория игр теряют основание.

• Метод Ньютона и градиентный спуск: итерации к неподвижной точке T(x) = x - η∇f(x)
• Теорема Нэша (равновесие в играх): неподвижная точка отображения наилучшего ответа
• Стационарные распределения Марковских цепей: π = πP - неподвижная точка
• Существование решений ОДУ и уравнений в частных производных (метод Пикара-Лапласа)

Теорема Банаха: сжимающие отображения

**Теорема Банаха (о сжимающем отображении, 1922):** Если T: X → X - сжимающее отображение (‖Tx - Ty‖ ≤ k‖x - y‖, 0 ≤ k < 1) на полном метрическом пространстве X, то T имеет единственную неподвижную точку x* = Tx*, и итерации xₙ₊₁ = Txₙ сходятся к x* для любого начального x₀, причём ‖xₙ - x*‖ ≤ kⁿ/(1-k)·‖x₁ - x₀‖.

**Оценки скорости сходимости:** A priori оценка: ‖xₙ - x*‖ ≤ kⁿ·‖x₀ - x*‖ A posteriori оценка: ‖xₙ - x*‖ ≤ k/(1-k)·‖xₙ - xₙ₋₁‖ **Приложения теоремы Банаха:** 1. **Метод простых итераций** для уравнения x = g(x): достаточно |g'(x)| < 1 2. **Метод Пикара** (существование решений ОДУ): T[x](t) = x₀ + ∫₀ᵗ f(s,x(s))ds - сжимающее! 3. **Метод Ньютона** (локально): T(x) = x - f(x)/f'(x) - квадратичная сходимость 4. **Обратное отображение**: теорема об обратном отображении доказывается через Банах 5. **Нейронные сети**: сходимость градиентного спуска при μ-сильной выпуклости

Теорема Брауэра: топологическое обобщение

**Теорема Брауэра (1912):** Любое непрерывное отображение T: Bⁿ → Bⁿ (замкнутый единичный шар в ℝⁿ) имеет неподвижную точку. Никаких условий сжатости не нужно - только непрерывность и компактность области! Это глубокий топологический результат: из него следует принцип промежуточного значения, теорема о хаусдорфовом расстоянии и многое другое.

**Доказательство и интуиция:** **Для n=1:** T: [-1,1] → [-1,1] непрерывна. Рассмотрим g(x) = T(x) - x. g(-1) = T(-1) - (-1) ≥ 0, g(1) = T(1) - 1 ≤ 0. По теореме Больцано: ∃x*: g(x*) = 0, т.е. T(x*) = x*. **Для n=2:** Если бы неподвижной точки не было, можно построить непрерывную ретракцию шара на границу - что противоречит тому, что граница и диск гомотопически нееквивалентны (π₁(S¹) = ℤ ≠ 0). **Следствие - равновесие Нэша:** В теории игр с n игроками и конечными стратегиями функция "наилучшего ответа" - непрерывное отображение симплекса в себя → существует неподвижная точка = равновесие Нэша!

Теорема Шаудера: бесконечномерное обобщение

**Теорема Шаудера:** Если C - непустое выпуклое компактное подмножество банахова пространства X, и T: C → C - непрерывное отображение, то T имеет неподвижную точку. Или в более удобной форме: если T: C → C непрерывно и T(C) предкомпактно (T компактный оператор), то T имеет неподвижную точку.

**Приложения теоремы Шаудера:** 1. **Существование решений нелинейных интегральных уравнений:** Tf(x) = g(x) + ∫K(x,y)f(y)dy - компактный, т.е. имеет неподвижную точку (= решение). 2. **Существование решений нелинейных ОДУ/ДЧП:** Задача Коши с ростом f (не Липшица): T - компактный оператор на C([0,T]). 3. **Существование стационарных распределений** в марковских цепях: оператор перехода отображает симплекс вероятностных мер в себя (компактно). 4. **Нелинейное программирование:** операторы проекции + шаг градиента в выпуклых задачах. **Теорема Какутани** (обобщение): многозначные отображения с выпуклыми значениями тоже имеют неподвижную точку - это обобщение теоремы Нэша на игры с непрерывными стратегиями.

Ключевые идеи

• Банах: T сжимает с k<1 на полном X → ∃! неподвижная точка, итерации сходятся с геометрической скоростью
• Брауэр: T непрерывно на компактном выпуклом ⊆ ℝⁿ → ∃ неподвижная точка (топологический)
• Шаудер: T непрерывно, T(C) предкомпактно на выпуклом C ⊆ X → ∃ неподвижная точка
• Нэш (следствие Брауэра/Какутани): каждая конечная игра имеет равновесие в смешанных стратегиях
• Метод Пикара: T = оператор интегрирования - сжимающий при малом T → существование решения ОДУ
• Иерархия мощности: Шаудер → Брауэр → Банах (последний конструктивный, первые - топологические)

Связанные темы

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

• Слабые топологии — Теорема Шаудера использует слабую компактность (Банах-Алаоглу) для компактных операторов
• Компактные операторы — Теорема Шаудера требует компактности оператора T - ключевое условие

Вопросы для размышления

• Почему для теоремы Банаха нужна полнота пространства? Что ломается без неё?
• Метод Ньютона имеет квадратичную сходимость, а не геометрическую (как даёт Банах). Почему?
• Как теорема о неподвижной точке Какутани (для многозначных отображений) обобщает теорему Нэша на игры с бесконечными пространствами стратегий?

Связанные уроки

• la-01-vectors-intro