Системы нелинейных уравнений

Deep Equilibrium Models (Bai, Kolter, Koltun, 2019): нейросеть не разворачивается по слоям - находит неподвижную точку $F(\mathbf{x}^*) = \mathbf{x}^*$ методом Ньютона. Forward pass = решение системы нелинейных уравнений. Бесконечная глубина, O(1) памяти. SPICE симулирует микросхему с $10^6$ транзисторами, решая такую систему за 3-5 итераций Ньютона на каждый такт. Один алгоритм - от проектирования процессоров до архитектур нейросетей.

• **Deep Equilibrium Models:** forward pass нейросети = решение F(x)=x методом Ньютона; бесконечная глубина, O(1) памяти (Bai et al. 2019)
• **SPICE-симулятор:** Newton-Raphson для нелинейных схем - каждый временной шаг решает систему KCL/KVL уравнений для 10^6 транзисторов
• **scipy.optimize.fsolve:** trust region Newton под капотом; надёжен для n < 1000; автоматический числовой Якобиан
• **L-BFGS:** квазиньютоновский метод на основе идей Бройдена; стандарт для fine-tuning LLM и задач оптимизации с миллиардами параметров

Предварительные знания

• Решение нелинейных уравнений

Метод Ньютона для систем

SPICE симулирует микросхему с $10^6$ транзисторами. Каждый такт моделирования - система из $10^6$ нелинейных уравнений (законы Кирхгофа для нелинейных элементов). Newton-Raphson сходится за 3-5 итераций. Без этого алгоритма нет chip design, нет современных процессоров. Формула та же, что для скалярного случая - только производная заменяется матрицей.

Для системы $F(\mathbf{x}) = 0$, где $F: \mathbb{R}^n \to \mathbb{R}^n$, метод Ньютона обобщается заменой производной на **матрицу Якоби**. На каждом шаге решается линейная система: $J(\mathbf{x}_n)\cdot\Delta\mathbf{x} = -F(\mathbf{x}_n)$, затем $\mathbf{x}_{n+1} = \mathbf{x}_n + \Delta\mathbf{x}$. Сходимость - квадратичная вблизи простого корня.

**Итерация метода Ньютона для систем:** $\mathbf{x}_{n+1} = \mathbf{x}_n - J(\mathbf{x}_n)^{-1} \cdot F(\mathbf{x}_n)$ На практике - НЕ вычислять $J^{-1}$: решать СЛАУ $J(\mathbf{x}_n)\cdot\delta = -F(\mathbf{x}_n)$, затем $\mathbf{x}_{n+1} = \mathbf{x}_n + \delta$. **Матрица Якоби** $J \in \mathbb{R}^{n\times n}$: $J_{ij} = \partial F_i / \partial x_j$ Сложность одного шага: O(n³) для LU-декомпозиции.

Метод Ньютона для систем требует **всей матрицы Якоби** на каждой итерации - $n^2$ частных производных. При $n > 1000$ это дорого. Альтернативы: числовой Якобиан через `scipy.optimize.approx_fprime`, автодифференцирование (JAX, PyTorch) или Jacobian-free методы.

Метод Бройдена: Якобиан без пересчёта

Вычисление Якобиана на каждой итерации требует $n^2$ вычислений производных - дорого. Метод Бройдена (1965) - квазиньютоновский метод: начинаем с матрицы $B_0 \approx J(\mathbf{x}_0)$ и обновляем её **ранговой поправкой rank-1** после каждого шага, не перевычисляя все частные производные. Та же идея лежит в основе L-BFGS - стандартного оптимизатора для задач с миллионами параметров.

**Обновление Бройдена (rank-1 update):** После шага: $\mathbf{s} = \mathbf{x}_{n+1} - \mathbf{x}_n$, $\mathbf{y} = F(\mathbf{x}_{n+1}) - F(\mathbf{x}_n)$ $B_{n+1} = B_n + \frac{(\mathbf{y} - B_n\mathbf{s})\cdot\mathbf{s}^T}{\mathbf{s}^T\mathbf{s}}$ Это минимальное изменение $B$, удовлетворяющее условию секущих: $B_{n+1}\mathbf{s} = \mathbf{y}$ **Суперлинейная сходимость** вблизи корня. **Экономия:** O(n²) на итерацию вместо O(n³).

В ML метод Бройдена лежит в основе **L-BFGS** - самого популярного квазиньютоновского оптимизатора. L-BFGS хранит не всю матрицу $B$ ($n^2$ чисел), а только $m$ последних векторов $\mathbf{s}$ и $\mathbf{y}$, используя O(mn) памяти. При $n = 10^9$ параметров это разница между возможным и невозможным.

Неподвижная точка и Deep Equilibrium Models

Deep Equilibrium Models (Bai, Kolter, Koltun, 2019): нейросеть не разворачивается по слоям - находит неподвижную точку $F(\mathbf{x}^*) = \mathbf{x}^*$. Forward pass = решение системы нелинейных уравнений методом Ньютона. Бесконечная глубина, O(1) памяти по числу слоёв. Это не метафора - буквально то же уравнение $F(\mathbf{x}) = 0$.

Метод неподвижной точки записывает систему $F(\mathbf{x}) = 0$ как $\mathbf{x} = G(\mathbf{x})$ и итерирует $\mathbf{x}_{n+1} = G(\mathbf{x}_n)$. Сходимость гарантируется теоремой Банаха: если $G$ - сжимающее отображение ($\|G(\mathbf{x}) - G(\mathbf{y})\| \le L\|\mathbf{x} - \mathbf{y}\|$, $L < 1$), итерации сходятся к единственной неподвижной точке.

**Условие сходимости (теорема Банаха):** Если $\rho(J_G) < 1$ вблизи $\mathbf{x}^*$, итерации $\mathbf{x}_{n+1} = G(\mathbf{x}_n)$ сходятся. $\rho(J_G)$ - **спектральный радиус** Якоби $G$ (максимальное по модулю собственное значение). **Скорость:** линейная со скоростью $\rho(J_G)$. При $\rho = 0.5$ - каждый шаг удваивает точность.

Обучение нейросети - поиск весов $\mathbf{w}$, при которых $\nabla L(\mathbf{w}) = 0$. Стохастический градиентный спуск $\mathbf{w}_{n+1} = \mathbf{w}_n - \alpha\nabla L(\mathbf{w}_n)$ - итерации неподвижной точки $G(\mathbf{w}) = \mathbf{w} - \alpha\nabla L(\mathbf{w})$. Условие сходимости: $\rho(I - \alpha H) < 1$, где $H$ - матрица Гессе.

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

• **Метод Ньютона для систем:** xₙ₊₁ = xₙ - J⁻¹F; квадратичная сходимость; O(n³) на итерацию; нужен Якобиан
• **Метод Бройдена:** rank-1 обновление Якоби без перевычисления; суперлинейная сходимость; основа L-BFGS
• **Неподвижная точка:** x = G(x); сходится при ρ(J_G) < 1; DEQ и градиентный спуск - частные случаи
• **scipy.optimize.fsolve:** trust region Newton; автоматический числовой Якобиан; надёжно для n < 1000

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

Системы нелинейных уравнений связаны с линейной алгеброй и оптимизацией:

• Прямые методы: LU, Cholesky, QR — Каждый шаг метода Ньютона решает линейную систему J·δ = -F - нужны прямые методы
• Решение нелинейных уравнений — Метод Ньютона для систем - прямое обобщение одномерного Ньютона-Рафсона

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

• Deep Equilibrium Models решают F(x)=x методом Ньютона во время forward pass. Что значит 'сходимость' в контексте обучения таких моделей?
• SPICE решает систему из 10^6 нелинейных уравнений за 3-5 итераций. Почему квадратичная сходимость Ньютона делает это возможным, а линейная - нет?
• Каково условие сходимости итераций градиентного спуска через спектральный радиус матрицы Гессе - и как оно связывает learning rate с кривизной loss?

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

• nm-04 — Ньютон для систем - прямое обобщение одномерного Ньютона-Рафсона
• nm-06 — Каждый шаг метода Ньютона - задача для прямых методов LU/QR
• de-05 — Нахождение полюсов передаточной функции H(s) - задача F(s)=0
• dyn-01 — Равновесие динамической системы - неподвижная точка F(x)=0
• calc-06-derivative-intro — Якобиан - матрица частных производных, обобщение градиента
• la-01-vectors-intro