Дискретные динамические системы

Откройте калькулятор и нажимайте cos снова и снова. Любое начальное число - через 50 нажатий результат 0.7391... Всегда. Это аттрактор. Теперь замените cos на $\theta \mapsto \theta - \eta \nabla L(\theta)$ - и получите обучение нейросети. Один и тот же математический объект - один и тот же вопрос: куда сходится эта последовательность?

• **Обучение нейросетей:** SGD и Adam - дискретные динамические системы на пространстве весов; Neural ODE (Chen et al. 2018) - ResNet с бесконечным числом слоёв как непрерывная динамика
• **Диффузионные модели:** DDPM - итерация 1000 шагов зашумления, затем обратная динамика - 1000 шагов обратного стохастического процесса Ланжевена для генерации одного изображения
• **Экология и хаос:** модель Ферхюльста $x_{n+1} = r x_n(1-x_n)$ при $r > 3.57$ - хаос с чувствительностью к начальным условиям; то же объясняет нестабильность обучения при большом learning rate

Итерация: базовый механизм

Банковский вклад под 5% годовых. Каждый год баланс обновляется по одному и тому же правилу: новый баланс = старый баланс * 1.05. Это итерация - применение одной функции снова и снова. **Градиентный спуск, обучающий GPT, работает тем же принципом**: $\theta_{n+1} = \theta_n - \eta \nabla L(\theta_n)$ - одно правило, применяемое миллионы раз.

**Итерация (iteration)** - процесс многократного применения функции f к начальному значению x₀: x₁ = f(x₀), x₂ = f(x₁), x₃ = f(x₂), ... В общем виде: **x_{n+1} = f(x_n)**. Это дискретная динамическая система - время идёт шагами n = 0, 1, 2, 3, ...

Ключевая идея: **состояние системы полностью определяется текущим значением $x_n$ и правилом f**. Не нужно помнить всю историю - только текущий шаг. Это свойство называется **марковским** - будущее зависит только от настоящего. В ResNet каждый слой - это шаг итерации $x_{n+1} = x_n + F(x_n)$; в 2018 году Chen et al. показали, что при бесконечной глубине это предел обыкновенного дифференциального уравнения (Neural ODE).

Орбита: история системы

Когда мы запускаем итерацию из точки x₀, последовательность значений x₀, x₁, x₂, ... образует **орбиту** (orbit) точки x₀. Орбита - это полная траектория движения системы. Разные начальные точки могут давать совершенно разные орбиты.

**Орбита (orbit)** точки x₀ при отображении f - это последовательность {x₀, f(x₀), f(f(x₀)), f(f(f(x₀))), ...}. Обозначение: **O(x₀) = {f^n(x₀) : n = 0, 1, 2, ...}**, где f^n - n-кратное применение f (не степень!).

**Cobweb-диаграмма** (паутинная диаграмма) - мощный инструмент визуализации орбит. Мы рисуем график f(x) и прямую y = x. Итерация - это прыжок вверх к графику (применение f), затем горизонтально к прямой y = x (перенос результата на ось x). Получается характерный «паутинный» узор.

**Чувствительность к начальным условиям:** в хаотических системах орбиты, стартовавшие из близких точек x₀ = 0.1000 и x₀ = 0.1001, через 30 шагов могут оказаться в совершенно разных местах. Это делает долгосрочный прогноз невозможным.

Неподвижная точка: f(x*) = x*

**Если система пришла в точку x* и осталась там навсегда** - это неподвижная точка (fixed point). Математически: f(x*) = x*. Система «застревает» - одно применение функции ничего не меняет.

**Неподвижная точка** x* отображения f - это решение уравнения f(x*) = x*. Графически: пересечение графика f(x) с прямой y = x. Бывает **устойчивой** (аттрактор - соседние орбиты притягиваются) и **неустойчивой** (репеллер - соседние орбиты убегают).

**Критерий устойчивости** - производная в неподвижной точке. Если |f'(x*)| < 1, то x* устойчива: малые отклонения затухают. Если |f'(x*)| > 1, то x* неустойчива: малые отклонения растут. Если |f'(x*)| = 1 - пограничный случай, нужен дополнительный анализ.

Интуиция проста: если f сжимает окрестность x* (производная < 1 по модулю), то отклонения уменьшаются с каждой итерацией. Если растягивает (производная > 1) - отклонения растут.

Периодические орбиты и путь к хаосу

Вернёмся к банковскому вкладу из начала урока. Мы видели, что простое правило может давать сходящуюся орбиту. А что если правило чуть сложнее? **Логистическое отображение** x_{n+1} = r*x_n*(1-x_n) при разных значениях параметра r показывает поразительное разнообразие поведения.

**Периодическая орбита** периода p - это набор точек {x₀, x₁, ..., x_{p-1}}, где f^p(x₀) = x₀, но f^k(x₀) ≠ x₀ для 0 < k < p. Цикл периода 2: система прыгает между двумя точками. Периода 3: между тремя. Неподвижная точка - цикл периода 1.

**Period-doubling cascade** - каскад удвоения периода. При увеличении r происходит следующее: неподвижная точка → цикл-2 → цикл-4 → цикл-8 → ... → хаос. Каждое удвоение происходит при определённом значении r, и расстояния между этими значениями сжимаются с универсальной константой **Фейгенбаума δ ≈ 4.6692**.

**Теорема Шарковского (1964):** если отображение прямой имеет цикл периода 3, то оно имеет циклы ВСЕХ периодов. Существование цикла-3 гарантирует хаос!

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

• **Итерация $x_{n+1} = f(x_n)$** - фундаментальный механизм дискретных динамических систем; SGD, Adam, PageRank power iteration - всё это частные случаи
• **Орбита** - полная траектория; аттрактор определяет, куда сходится обучение - не глобальный минимум, а ближайший устойчивый
• **Устойчивость через производную**: $|f'(x^*)| < 1$ - аттрактор, $|f'(x^*)| > 1$ - репеллер; в ML это условие на learning rate: при $\eta > 1$ градиентный спуск расходится
• **Каскад удвоения периода** (Фейгенбаум $\delta \approx 4.669$) - универсальный сценарий рождения хаоса; чувствительность к начальным условиям объясняет, почему два запуска обучения с разным seed дают разные веса
• **Neural ODE** (Chen et al. 2018): ResNet $x_{n+1} = x_n + F(x_n)$ при $n \to \infty$ переходит в ODE $dx/dt = F(x)$ - дискретная динамика как дискретизация непрерывной

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

Дискретные динамические системы - фундамент для изучения непрерывных систем и теории устойчивости:

• Непрерывные динамические системы — Непрерывный аналог: вместо x_{n+1}=f(x_n) используется dx/dt=f(x)
• Теория устойчивости Ляпунова — Формализует понятие устойчивости через функции Ляпунова
• Теория хаоса — Углублённое изучение хаотических орбит и странных аттракторов

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

• Прогноз погоды становится ненадёжным через 7-10 дней. Как это связано с чувствительностью к начальным условиям в дискретных системах?
• Если у функции f нет неподвижных точек (например, f(x) = x + 1), что можно сказать о поведении всех орбит?
• Вернёмся к эксперименту из начала урока: нажатие cos на калькуляторе многократно сходится к 0.7391... Как доказать, что cos(0.7391) ≈ 0.7391?

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

• de-01
• calc-01-sequences