Корни нелинейных уравнений: от бисекции до Ньютона

1999. id Software. John Carmack читает странный код с числом 0x5f3759df. Это не магия - это умное начальное приближение плюс один шаг метода Ньютона. Корень из числа за 2 итерации вместо 100. L-BFGS в PyTorch решает f(x)=0 для миллионов параметров - тот же Ньютон 1669 года, только с приближённым якобианом. Квадратичная сходимость: число верных знаков удваивается на каждом шаге. Это не эффективность - это другой порядок роста.

• **scipy.optimize.brentq:** стандарт для поиска порогов в ML, нулей функций потерь, точек безубыточности в финансах. Бисекция + секущие + квадратичная интерполяция под одним вызовом.
• **L-BFGS в PyTorch/JAX:** квази-Ньютоновская оптимизация для нейросетей - тот же метод Ньютона, но якобиан вычисляется приближённо через градиентную историю.
• **PageRank как fixed-point:** ранжирование веба - уравнение x = Mx, где M - матрица ссылок. Power iteration - частный случай fixed-point iteration. Convergence condition: |g'(x)| < 1.

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

• Сплайны

Бисекция: гарантия за логарифм

scipy.optimize.brentq - стандартный инструмент поиска порогов в ML: порог классификации при заданном precision, точка безубыточности, нуль функции потерь. Под его капотом живёт бисекция. Метод: если f(a) и f(b) разного знака - корень между ними гарантирован (Больцано). Делим пополам, выбираем половину со сменой знака, повторяем.

**Сходимость метода бисекции:** После n шагов ошибка: eₙ <= (b - a) / 2ⁿ Это **линейная сходимость** со скоростью 1/2 - каждый шаг уменьшает ошибку вдвое. Для точности ε нужно n >= log₂((b - a) / ε) шагов. **Гарантия:** метод ВСЕГДА сходится при f непрерывна и f(a)·f(b) < 0.

Бисекция требует **начального отрезка со сменой знака**. Двойной корень (f(x) = (x-r)²) знак не меняет - метод неприменим.

Метод Ньютона: квадратичный взрыв сходимости

1999. id Software. John Carmack открывает странный код: вычисление 1/sqrt(x) за 2 итерации вместо 100. Число 0x5f3759df - умное начальное приближение. Затем один шаг метода Ньютона. Результат: быстрый inverse square root для Quake III Arena, который стал легендой. Сам Ньютон описал метод в 1669 году - до появления видеоигр на 330 лет.

Геометрически просто: в точке xₙ проводим касательную к f(x) и берём пересечение с осью x. Касательная линеаризует функцию - и пересечение даёт следующее приближение. Сходимость **квадратичная**: число верных знаков удваивается на каждом шаге.

**Итерационная формула Ньютона:** xₙ₊₁ = xₙ - f(xₙ) / f'(xₙ) **Квадратичная сходимость:** если f''(x*) ≠ 0 и x₀ близко к корню x*: eₙ₊₁ ≈ |f''(x*)| / (2|f'(x*)|) · eₙ² Почему так быстро? При 10⁻³ ошибке → следующая ≈ 10⁻⁶ → затем ≈ 10⁻¹².

Метод Ньютона **расходится** при плохом начальном приближении, f'(x) ≈ 0 у корня (кратный корень), или сложном рельефе функции. Кратный корень (f(x*) = f'(x*) = 0) снижает порядок до линейного. L-BFGS в PyTorch обходит это через приближённый якобиан.

Метод секущих: Ньютон без производной

Нейросеть как чёрный ящик. Дорогостоящая физическая симуляция. Числовой солвер без аналитической формулы. Во всех трёх случаях f'(x) недоступна - и метод Ньютона не работает. Метод секущих аппроксимирует производную конечной разностью по двум последним точкам. Сходимость суперлинейная: порядок φ ≈ 1.618 - золотое сечение.

**Итерация метода секущих:** xₙ₊₁ = xₙ - f(xₙ) · (xₙ - xₙ₋₁) / (f(xₙ) - f(xₙ₋₁)) Это аппроксимация Ньютона с заменой: f'(xₙ) ≈ (f(xₙ) - f(xₙ₋₁)) / (xₙ - xₙ₋₁) **Порядок сходимости:** p = (1 + √5) / 2 ≈ 1.618 (золотое сечение) **Нужны:** две начальных точки x₀ и x₁ (без требования смены знака).

Метод секущих делает только **1 вычисление f** на итерацию (f(x0) переиспользуется из предыдущего шага). Ньютон требует f и f'. При дорогих функциях секущие быстрее по реальному времени, несмотря на большее число итераций.

Метод Брента: надёжность + скорость

1973. Ричард Брент. Задача: взять гарантию бисекции и скорость метода секущих - и объединить. Ключевая идея: пробовать быстрый метод (обратная квадратичная интерполяция или секущие), но при плохом поведении мгновенно переключаться на бисекцию. Лучшее из двух миров. Именно поэтому scipy.optimize.brentq - стандарт для продакшена.

**Алгоритм Брента:** 1. Поддерживаем три точки: a (последняя смена знака), b (лучшее приближение), c (предыдущее b) 2. Пробуем обратную квадратичную интерполяцию (по a, b, c) или секущие 3. Если результат «плохой» (вне допустимых границ, шаг слишком мал) - делаем бисекцию 4. Гарантия: всегда сходимся, не хуже бисекции **scipy.optimize.brentq** - именно метод Брента под капотом.

**Практическое правило:** использовать `scipy.optimize.brentq` для скалярных уравнений по умолчанию. Метод Ньютона - только если производная доступна аналитически и важна скорость. Бисекция вручную - только для понимания.

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

• **Бисекция:** O(1/2ⁿ) сходимость, гарантированная, медленная; требует смены знака на отрезке. ~33 итерации для 1e-10.
• **Ньютон-Рафсон:** квадратичная сходимость (eₙ₊₁ ∝ eₙ²); нужна аналитическая производная; быстр, но может расходиться.
• **Метод секущих:** суперлинейная сходимость (порядок φ ≈ 1.618); производная не нужна; 1 вычисление f на итерацию.
• **Метод Брента:** гибрид бисекции + секущих + квадратичная интерполяция; стандарт для продакшена (scipy.optimize.brentq).
• **Квазиньютоновские методы** (L-BFGS, BFGS) - тот же принцип, но с приближённым якобианом. Весь PyTorch torch.optim.LBFGS.

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

Методы поиска корней - основа для более сложных задач:

• Системы нелинейных уравнений — Обобщение на вектор-функции: Ньютон с якобианом, метод Бройдена
• Сплайны — Сплайны решают СЛАУ с трёхдиагональной матрицей - частный случай линейного уравнения

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

• Почему для нахождения максимума f(x) можно применить метод Ньютона к уравнению f'(x) = 0? Что если максимум - не единственный?
• Как изменится порядок сходимости метода Ньютона, если корень кратный (f(x*) = f'(x*) = 0)? Как это обходит L-BFGS?
• Почему метод Брента переключается на бисекцию, если быстрый метод даёт результат вне отрезка [a,b]?

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

• nm-03 — Сплайны решают линейное уравнение - частный случай
• nm-05 — Системы нелинейных уравнений - Ньютон с якобианом
• de-01 — ОДУ-солверы внутри используют root-finding
• calc-01-sequences — Сходимость итераций - то же что сходимость последовательностей
• alg-10-binary-search