Часть 1 Приложение C. Анатомия квадратичной сходимости: Доказательство теоремы Канторовича в $R$

Text rendered via Dual-Core compilation (Human author + LLM co-processor).
Англоязычная версия данной заметки доступна здесь https://alex-ber.medium.com/1d044c1a526c.

См. также:
Часть 1: Метод Ньютона в R. От эвристики к формальной верификации (Kernel-Level)
Часть 1 Приложение А. Пространства $L_p$ (Under the Hood): От топологических хаков к квадратичной гладкости
Часть 1 Приложение B. Другой пример Loss function на примере кросс-энтропии
Часть 1 Приложение C. Анатомия квадратичной сходимости: Доказательство теоремы Канторовича в $R$
Часть 2: Метод Ньютона в $R^n$. От Гессиана к Аппаратным Лимитам
Часть 3: Метод Ньютона для Векторных полей. Матрица Якоби, Гато и Архитектура Backpropogation
Бонусная Часть 4: Метод Ньютона в бесконечномерных пространствах (Level 99)

Теорема Канторовича: Строгая математическая формулировка

Теорема Канторовича: Пусть функция $f(x)$ непрерывна на замкнутом отрезке $D = [a, b]$ и дважды дифференцируема на интервале $(a, b)$. Пусть задана начальная точка $x_0 \in D$, для которой выполняются следующие условия:

1. Начальный шаг ограничен: $|\Delta x_0| = \left| \frac{f(x_0)}{f'(x_0)} \right| \le \eta$
2. Модуль обратной величины первой производной в начальной точке ограничен: $\left| \frac{1}{f'(x_0)} \right| \le \beta$. (Именно такая формулировка позволит нам в будущем бесшовно заменить число в знаменателе на норму обратной матрицы Якоби или Гессе в многомерном мире).
3. Модуль второй производной (кривизна) ограничен сверху: $|f''(x)| \le M$ для всех $x \in D$

Если выполняется условие $h = M \cdot \eta \cdot \beta \le \frac{1}{2}$ и отрезок $\Omega = [x_0 - t^*, x_0 + t^*]$, где $t^* = \frac{1 - \sqrt{1 - 2h}}{h} \eta \le 2\eta$, целиком принадлежит $D$, то внутри окрестности $\Omega$ гарантированно существует корень $x^*$ уравнения $f(x) = 0$, и последовательность итераций метода Ньютона $x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$ безопасно сойдется к нему, не покидая $\Omega$. При этом сходимость обладает квадратичной скоростью при $h < 1/2$ (ошибка убывает пропорционально квадрату предыдущей) и может снижаться до линейной в граничном случае $h = 1/2$. Корень $x^*$ является единственным в пределах большей окрестности радиуса $t^{**} = \frac{1 + \sqrt{1 - 2h}}{h} \eta$ (при условии, что эта окрестность также лежит в $D$).

Интуиция: Теорема как статический анализатор (API Contracts)

В современной разработке для предотвращения катастроф во время выполнения используют статические анализаторы кода (вроде TypeScript, Rust compiler или линтеров). Они проверяют типы и контракты до запуска программы. В математике роль такого статического анализатора для метода Ньютона играет приведенная выше теорема (за работы в том числе в этой области Леонид Канторович позже получил Нобелевскую премию по экономике).

Чтобы «компиляция» прошла успешно, анализатор должен просто проверить три условия контракта. При этом анализатор работает «вслепую» относительно самого корня: он сопоставляет локальные данные только в одной стартовой точке $x_0$ (размер шага и наклон) с глобальным ограничением на кривизну ($M$) во всей зоне $D$.

Важнейший философский поинт теоремы Канторовича заключается в том, что это теорема существования. Анализатору не нужно знать, где находится корень и есть ли он вообще. Если начальные условия (шаг, наклон и кривизна) удовлетворяют контракту $h \le 1/2$, теорема математически гарантирует, что корень существует, и метод его обязательно найдет. Триггер $h \le 1/2$ просто говорит: «ваш стартовый шаг достаточно мал по сравнению с максимально возможной кривизной графика».

Правило $2\eta$ и SLA алгоритма. Теорема дает программистам блестящее инженерное «правило большого пальца»: истинный корень всегда лежит на расстоянии, не превышающем удвоенного первого шага ($t^* \le 2\eta$). Кроме того, анализатор прописывает жесткий SLA (Service Level Agreement): если запас прочности есть ($h < 1/2$), количество верных знаков ответа будет удваиваться на каждой итерации. И лишь в экстремальном краевом случае ($h = 1/2$) алгоритм деградирует до обычной линейной скорости.

Замечание про современный Deep Learning. В многомерном мире алгоритмы работают с системами уравнений: там вместо деления на производную используется обратная матрица Якоби, но общая логика сохраняется. Однако в мире современных нейросетей с миллиардами параметров, где функции потерь представляют собой дикие многомерные ландшафты, аналогов теореме Канторовича не найдено. У нас нет строгого математического «анализатора» для ChatGPT. Вместо формальной верификации ML-инженеры вынуждены опираться на эмпирические эвристики (градиентный клиппинг, адаптивный learning rate, оптимизаторы вроде Adam), инженерную интуицию и своего рода высокотехнологичное шаманство. Обучение современной нейросети — это прыжок в темноту с надеждой собрать парашют в полете.

Ниже есть продолжение.

Доказательство. Фаза 1: Существование корня (Bootstrapping)

Как доказать под капотом, что корень существует, и откуда берутся эти пугающие корни $\sqrt{1-2h}$ в радиусах $t^*$ и $t^{**}$? В математике для этого есть изящный хакерский трюк: метод мажоранты (поиск абсолютно худшего сценария).

Давайте вызовем наш Low-level API (Тейлора) и спрогнозируем значение функции в нашей новой точке $x_{k+1}$, стоя в текущей точке $x_k$ (напомним, что здесь $\Delta x_k$ — это наш ньютоновский шаг, то есть $\Delta x_k = x_{k+1} - x_k$):
$f(x_{k+1}) = f(x_k) + f'(x_k)\Delta x_k + \frac{1}{2}f''(\xi_1)\Delta x_k^2$

Метод Ньютона специально подбирает свой шаг $\Delta x_k$ именно так, чтобы обнулить весь линейный прогноз: $f(x_k) + f'(x_k)\Delta x_k = 0$. Явно подставим этот ноль в Тейлора:
$f(x_{k+1}) = \underbrace{f(x_k) + f'(x_k)\Delta x_k}_{= 0} + \frac{1}{2}f''(\xi_1)\Delta x_k^2 = \frac{1}{2}f''(\xi_1)\Delta x_k^2$

Физический смысл прекрасен: если бы функция была идеально прямой, мы бы сразу попали в ноль. Ошибка на новом шаге — это целиком и полностью следствие квадратичного искривления графика.

Поскольку Теорема Канторовича проверяет наклон только на старте (для удобства вычислений в одномерном скалярном мире вернемся к обозначению $m = 1/\beta$, где $m$ — минимальный модуль производной на старте), нам нужно доказать, что знаменатель не обнулится ни на одном из следующих шагов. Для этого математики строят функцию-мажоранту — искусственный «абсолютно худший сценарий». Давайте сконструируем её с нуля, поместив старт в точку $x = 0$.

Во-первых, кривизна мажоранты должна быть максимально агрессивной, постоянно выгибая график вверх, чтобы попытаться избежать пересечения с осью. Значит, её вторая производная всегда максимальна: $P''(x) = M$. Во-вторых, стартовый наклон должен быть самым слабым из разрешенных: $P'(0) = -m$ (минус означает, что мы спускаемся к корню). В-третьих, стартовая высота функции $P(0)$ должна генерировать ровно наш максимально разрешенный шаг $\eta$. Так как размер шага — это $\left|\frac{P(0)}{P'(0)}\right| = \eta$, а $P'(0) = -m$, мы получаем высоту $P(0) = m\eta$.

Если мы возьмем константу $M$ и дважды её проинтегрируем с этими начальными условиями, мы получим обычную школьную параболу. Начинаем с константы кривизны:
$P''(x) = M$

Интегрируем первый раз, чтобы получить уравнение наклона (первую производную):
$P'(x) = \int M \, dx = Mx + C_1$

Применяем начальное условие $P'(0) = -m$, откуда получаем константу интегрирования $C_1 = -m$. Наша первая производная принимает вид: $P'(x) = Mx - m$.

Интегрируем второй раз, чтобы получить саму траекторию функции:
$P(x) = \int (Mx - m) \, dx = \frac{M}{2}x^2 - mx + C_2$
Применяем наше условие для стартовой высоты $P(0) = m\eta$, откуда следует, что вторая константа $C_2 = m\eta$. Собираем всё вместе и получаем обычную школьную параболу:
$P(x) = \frac{M}{2}x^2 - mx + m\eta$

Когда у этой худшей в мире функции существуют действительные корни? Когда её дискриминант неотрицателен ($D \ge 0$):
$D = (-m)^2 - 4 \cdot \left(\frac{M}{2}\right) \cdot (m\eta) = m^2 - 2Mm\eta \ge 0$

Теперь совершим простую алгебраическую манипуляцию. Перенесем отрицательное слагаемое вправо: $m^2 \ge 2Mm\eta$. Чтобы получить наш безразмерный параметр из теоремы ($h = \frac{M\eta}{m}$), разделим обе части неравенства на $2m^2$:
$\frac{1}{2} \ge \frac{M\eta}{m}$

Это и есть наше условие $h \le 1/2$! Это не просто эвристика, а строгое алгебраическое требование того, чтобы у мажоранты вообще был корень. Если оно нарушено, худший сценарий представляет собой параболу, висящую над осью, у которой действительных корней просто нет.

А теперь давайте найдем сами корни этой параболы через школьную формулу $x = \frac{-b \pm \sqrt{D}}{2a}$:
$x = \frac{m \pm \sqrt{m^2 - 2Mm\eta}}{M} = \frac{m}{M} \left(1 \pm \sqrt{1 - \frac{2M\eta}{m}}\right)$

Вспомним, что наш параметр $h = \frac{M\eta}{m}$. Следовательно, под корнем у нас собирается $1 - 2h$. А дробь перед скобкой $\frac{m}{M}$ можно переписать как $\frac{\eta}{h}$ (так как из $h = \frac{M\eta}{m}$ напрямую следует $\frac{m}{M} = \frac{\eta}{h}$). Подставляем всё это и получаем точные координаты корней мажоранты:
$x_{1,2} = \frac{\eta}{h} \left(1 \pm \sqrt{1 - 2h}\right)$

Заметим, что оба корня строго положительные.

Поскольку мы поместили старт нашей мажоранты в ноль, координата корня $x$ означает точную дистанцию, которую нужно пройти от старта до пересечения с осью абсцисс. Давайте посмотрим на эти дистанции внимательно.

Меньший корень (с минусом) равен $x_1 = \frac{1 - \sqrt{1 - 2h}}{h} \eta$. Это совпадает буква в букву с формулой радиуса $t^*$, которую мы заявили в контракте теоремы! А больший корень (с плюсом) равен $x_2 = \frac{1 + \sqrt{1 - 2h}}{h} \eta$, что в точности дает нам второй радиус $t^{**}$.

Дальше запустим параллельно метод Ньютона для нашей (неизвестной) функции $f(x)$ (генерируя точки $x_k$ и шаги $\Delta x_k$) и для эталонной параболы (генерируя точки $y_k$ и шаги $\Delta y_k$).

Замечание: В формулах ниже мы используем модуль для реального шага, но не используем для эталонного — $|\Delta x_k| \le \Delta y_k$. Дело в том, что реальный алгоритм на неизвестной функции $f(x)$ может «вилять» и шагать в обе стороны, поэтому нам важен модуль его смещения. А вот эталонная парабола $P(y) = \frac{M}{2}y^2 - my + m\eta$ движется строго в одном направлении. Докажем это.

Мы стартуем в точке $y_0 = 0$. Где находится дно (вершина) нашей параболы? Там, где её производная равна нулю: $P'(y) = My - m = 0$, то есть в координате $y_{vert} = \frac{m}{M}$.

А где находятся наши радиусы $t^*$ (гарантия существования) и $t^{**}$ (гарантия единственности)? Чуть выше мы вывели их точные координаты через школьную формулу корней:
$t^* = \frac{m - \sqrt{D}}{M} = \frac{m}{M} - \frac{\sqrt{D}}{M}$
$t^{**} = \frac{m + \sqrt{D}}{M} = \frac{m}{M} + \frac{\sqrt{D}}{M}$

Поскольку наш алгоритм стартует из точки $y_0 = 0$ (слева от обоих корней), корень $t^*$ (лежащий левее вершины) встречается нам первым — по отношению к старту он является ближним. А граница уникальности $t^{**}$ (лежащая правее вершины) оказывается дальним корнем. В экстремальном случае $D=0$ они слипаются на дне.

Что это значит для нашего алгоритма? Поскольку мы стартуем в нуле и стремимся к первому попавшемуся (ближнему) корню $t^*$, весь наш путь (в любой точке $y_k < t^*$) проходит исключительно по левой, нисходящей ветви параболы. Значит:

1. Значение функции положительно: $P(y_k) > 0$ (мы выше корня).

2. Производная строго отрицательна: $P'(y_k) = My_k - m < M(\frac{m}{M}) - m = 0$.

Считаем ньютоновский шаг: $\Delta y_k = - \frac{P(y_k)}{P'(y_k)}$. Минус на плюс, деленный на минус (-(+) / (-) = (+)), дает строгий плюс! Алгоритм всегда шагает только вправо.

Но вдруг он перепрыгнет корень $t^*$ (и, например, улетит к дальнему $t^{**}$)? Давайте вызовем формулу ошибки из нашей Фазы 2, применив её к самой параболе. Ошибка следующего шага равна:
$(t^* - y_{k+1}) = \frac{-P''(\xi)}{2P'(y_k)}(t^* - y_k)^2 \le \frac{-M}{2P'(y_k)}(t^* - y_k)^2$

Поскольку кривизна $M > 0$, квадрат ошибки всегда положителен, а знаменатель $P'(y_k)$ — отрицателен, вся эта дробь с минусом впереди дает строгое положительное число! То есть $(t^* - y_{k+1}) > 0$, а значит $y_{k+1} < t^*$.

Алгебра неумолима: эталонный алгоритм шагает строго вправо ($\Delta y_k > 0$) и просто не способен перепрыгнуть ближний корень ($y_{k+1} < t^*$). Поэтому все его шаги математически гарантированно положительны — это уже готовые абсолютные длины, и знак модуля им просто не нужен.

Далее, докажем методом математической индукции, что для каждого шага $k$: точка $x_k$ находится внутри безопасной зоны $\Omega$ (что легализует использование контрактов $M$ и $m$), и размер реального шага не превышает эталонного ($|\Delta x_k| \le \Delta y_k$).

• База индукции ($k = 0$): На нулевом шаге точка $x_0$ является центром зоны $\Omega$, то есть очевидно лежит внутри неё. Размер реального прыжка ограничен нашим контрактом: $|\Delta x_0| \le \eta$. Для мажоранты мы сами сконструировали стартовые условия так, чтобы её первый шаг был в точности равен $\Delta y_0 = \eta$. Значит, база верна: $|\Delta x_0| \le \Delta y_0$.
• Шаг индукции: Предположим, что наше утверждение верно вплоть до итерации $k$. Сначала докажем, что новая точка $x_{k+1}$ не вылетит за пределы безопасной зоны $\Omega$. Здесь вступает в дело алгебра и неравенство треугольника. Расстояние от старта $x_0$ до $x_{k+1}$ не превышает суммы длин всех предыдущих шагов. Так как каждый реальный шажок короче эталонного, эта дистанция ограничена:
  
  $|x_{k+1} - x_0| \le |\Delta x_0| + \dots + |\Delta x_k| \le \Delta y_0 + \dots + \Delta y_k = y_{k+1}$
  
  Мы уже знаем, что эталонная парабола сходится в свой корень $t^*$, поэтому её текущая координата $y_{k+1} < t^*$. Следовательно, $|x_{k+1} - x_0| < t^*$, и точка $x_{k+1}$ железобетонно остается внутри радиуса $\Omega$.
  
  Теперь, точно зная, что мы не покинули $\Omega$, легитимно оценим размер следующего шага: $|\Delta x_{k+1}| = \left| \frac{f(x_{k+1})}{f'(x_{k+1})} \right|$.
  
  Числитель (ошибка прогноза): Через оценки ошибки в форме Лагранжа в ряде Тейлора мы знаем, что $|f(x_{k+1})| \le \frac{1}{2} M |\Delta x_k|^2$. По индуктивному предположению это не превышает $\frac{1}{2} M (\Delta y_k)^2$. А это математически в точности равно значению самой эталонной параболы на новом шаге $P(y_{k+1})$.
  
  Знаменатель (падение производной): Теперь самое главное — доказать, что знаменатель не обнулится (то есть производная не умрет слишком рано). Как сильно могла измениться производная за время нашего путешествия от старта $x_0$ до текущей точки $x_{k+1}$? По теореме Лагранжа (или формуле конечных приращений) разность производных жестко ограничена максимальной кривизной: $|f'(x_{k+1}) - f'(x_0)| \le M \cdot |x_{k+1} - x_0|$.
  
  Мы уже доказали абзацем выше, что дистанция от старта ограничена эталоном: $|x_{k+1} - x_0| \le y_{k+1}$. Значит, $|f'(x_{k+1}) - f'(x_0)| \le M y_{k+1}$. Воспользуемся классическим неравенством треугольника для модулей $|A+B| \le |A| + |B|$, чтобы строго выразить новую производную через стартовую:
  
  $|f'(x_0)| = |f'(x_{k+1}) + (f'(x_0) - f'(x_{k+1}))| \le |f'(x_{k+1})| + |f'(x_{k+1}) - f'(x_0)|$
  
  Перенесем слагаемое, чтобы выразить искомую новую производную, и получим строгую оценку снизу:
  
  $|f'(x_{k+1})| \ge |f'(x_0)| - |f'(x_{k+1}) - f'(x_0)|$
  
  Мы знаем из стартового контракта, что уменьшаемое $|f'(x_0)| \ge m$. А вычитаемое слагаемое, как мы только что доказали, ограничено сверху: $|f'(x_{k+1}) - f'(x_0)| \le M y_{k+1}$. Подставив эти оценки, мы получаем абсолютно строгое алгебраическое неравенство:
  
  $|f'(x_{k+1})| \ge m - M y_{k+1}$
  
  А теперь посмотрим на эталонную параболу! Её производная по определению равна $P'(y) = My - m$. Поскольку мы находимся на левой (нисходящей) ветви и еще не достигли дна ($y_{k+1} < m/M$), значение $My_{k+1} - m$ отрицательно, а значит модуль её производной равен в точности $|P'(y_{k+1})| = m - M y_{k+1}$. То есть наш реальный знаменатель математически гарантированно больше (или равен) знаменателя эталонной параболы! Значит, вся реальная дробь гарантированно меньше эталонной:
  
  $|\Delta x_{k+1}| = \frac{|f(x_{k+1})|}{|f'(x_{k+1})|} \le \frac{P(y_{k+1})}{|P'(y_{k+1})|} = \Delta y_{k+1}$
  
  Таким образом, размер прыжка реальной функции на следующей итерации не превысит прыжка параболы. Шаг индукции полностью доказан!

Согласно принципу математической индукции, наше составное утверждение строго выполняется для всех натуральных индексов $k$ (включая нулевой). Именно так мы получаем абсолютную гарантию, что общая сумма всех шагов нашей реальной функции $f(x)$ строго ограничена сверху, алгоритм никогда не сломается, навсегда останется в безопасной зоне $\Omega = [x_0 - t^*, x_0 + t^*]$, а корень надежно заперт внутри неё.

Доказательство. Фаза 2: Скорость сходимости (Runtime metrics)

Теперь, когда статический анализатор дал зеленый свет, мы можем оценить, как именно выполняется заявленный в теореме SLA. Посмотрим, как убывает наша истинная ошибка $\epsilon_k = x_k - x^*$. Снова используем оценку ошибки в форме Лагранжа в ряде Тейлора, но теперь для точки $x^*$ вокруг нашей текущей точки $x_k$ (система сгенерирует новую промежуточную точку $\xi_2$):
$f(x^*) = f(x_k) + f'(x_k)(x^* - x_k) + \frac{1}{2}f''(\xi_2)(x^* - x_k)^2$

Аккуратно подставим то, что мы знаем: $f(x^*) = 0$, разница $(x^* - x_k) = -\epsilon_k$, а при возведении в квадрат минус исчезает: $(-\epsilon_k)^2 = \epsilon_k^2$. Получаем:
$0 = f(x_k) - f'(x_k)\epsilon_k + \frac{1}{2}f''(\xi_2)\epsilon_k^2$

Так как мажоранта гарантирует, что производная не равна нулю, разделим всё уравнение на $f'(x_k)$:
$0 = \frac{f(x_k)}{f'(x_k)} - \epsilon_k + \frac{f''(\xi_2)}{2f'(x_k)}\epsilon_k^2$

Вспомним формулу Ньютона: $x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$. Из неё следует, что дробь $\frac{f(x_k)}{f'(x_k)} = x_k - x_{k+1}$. Подставим это в уравнение, а заодно распишем $\epsilon_k = x_k - x^*$:
$0 = (x_k - x_{k+1}) - (x_k - x^*) + \frac{f''(\xi_2)}{2f'(x_k)}\epsilon_k^2$

Раскрываем скобки линейной части: $x_k - x_{k+1} - x_k + x^* = -(x_{k+1} - x^*) = -\epsilon_{k+1}$. Это наша ошибка на следующем шаге. Переносим её в левую часть:
$\epsilon_{k+1} = \frac{f''(\xi_2)}{2f'(x_k)}\epsilon_k^2$

Используя наши константы худшего сценария (максимальную кривизну $M$ и минимальную производную $m$), мы можем записать финальную оценку:
$\epsilon_{k+1} \le \frac{M}{2m}\epsilon_k^2$

Это и есть квадратичная сходимость. Ошибка на следующем шаге пропорциональна квадрату текущей ошибки. Если погрешность равна $10^{-2}$ (два верных знака), на следующем шаге она будет порядка $10^{-4}$, затем $10^{-8}$, $10^{-16}$. Количество верных знаков после запятой удваивается каждую итерацию.

Но обратите внимание на знаменатель $2f'(x_k)$ (или константу $2m$ в оценке худшего сценария). В нём скрыта единственная слабость алгоритма. Что происходит в граничном случае $h = 1/2$? Мы знаем из Фазы 1, что при $h = 1/2$ дискриминант эталонной параболы равен нулю ($D = 0$). Это означает, что ближний и дальний корни слипаются в один: $t^* = t^{**} = \frac{m}{M}$. Корень находится в точности на дне (в вершине) параболы!

В этом экстремальном сценарии график мажоранты не пересекает ось насквозь, а лишь едва касается её своей вершиной и уходит обратно вверх (в математике это называется кратным корнем). В самой точке касания график абсолютно горизонтален, а значит, его производная равна нулю: $P'(t^*) = 0$.

По мере того как алгоритм приближается к этому корню, производная в знаменателе стремительно падает. Давайте посмотрим, как это математически уничтожает нашу квадратичную суперсилу. Возьмем наше исходное уравнение мажоранты: $P(y) = \frac{M}{2}y^2 - my + m\eta$. Поскольку в граничном случае $h = \frac{M\eta}{m} = \frac{1}{2}$, мы можем легко выразить свободный член: $m\eta = \frac{m^2}{2M}$. Подставим его в уравнение параболы:

$P(y) = \frac{M}{2}y^2 - my + \frac{m^2}{2M}$

Вынесем множитель $\frac{M}{2}$ за скобки:

$P(y) = \frac{M}{2} \left( y^2 - \frac{2m}{M}y + \frac{m^2}{M^2} \right)$

Внутри скобок образовался классический полный квадрат (квадрат разности)! Сворачиваем его по школьной формуле:

$P(y) = \frac{M}{2} \left( y - \frac{m}{M} \right)^2$

А поскольку в этом сценарии наш слипшийся корень $t^* = \frac{m}{M}$, уравнение эталонной параболы элегантно превращается в компактный вид: $P(y) = \frac{M}{2}(y - t^*)^2$. Её производная, соответственно, равна $P'(y) = M(y - t^*)$. Подставим их в классическую формулу ньютоновского шага:

$\Delta y_k = - \frac{P(y_k)}{P'(y_k)} = - \frac{\frac{M}{2}(y_k - t^*)^2}{M(y_k - t^*)}$

Смотрите, что произошло! Множитель $(y_k - t^*)$ — это и есть наша текущая ошибка $\epsilon_k$. Константа $M$ сокращается, один квадрат ошибки в числителе сокращается с ошибкой в знаменателе, и у нас остается:

$\Delta y_k = - \frac{1}{2} (y_k - t^*) = - \frac{1}{2} \epsilon_k$

Вычисляем новую ошибку. Так как новая точка вычисляется прибавлением шага ($y_{k+1} = y_k + \Delta y_k$), то и новая ошибка $\epsilon_{k+1}$ вычисляется прибавлением этого шага к старой ошибке:

$\epsilon_{k+1} = \epsilon_k + \Delta y_k = \epsilon_k - \frac{1}{2}\epsilon_k = \frac{1}{2}\epsilon_k$.

Квадрат бесследно исчез! Умирающая производная в знаменателе «съела» одну степень ошибки из числителя, замедлив алгоритм до линейной скорости. Количество верных знаков больше не удваивается, дистанция до цели просто делится пополам на каждом шаге, что делает работу великого метода Ньютона неотличимой от метода половинного деления (binary search / bisection). Ч.т.д.

Часть 1 Приложение B. Другой пример Loss function на примере кросс-энтропии

Text rendered via Dual-Core compilation (Human author + LLM co-processor).
Англоязычная версия данной заметки доступна здесь https://alex-ber.medium.com/31a714207f1d.

См. также:
Часть 1: Метод Ньютона в R. От эвристики к формальной верификации (Kernel-Level)
Часть 1 Приложение А. Пространства $L_p$ (Under the Hood): От топологических хаков к квадратичной гладкости
Часть 1 Приложение B. Другой пример Loss function на примере кросс-энтропии
Часть 1 Приложение C. Анатомия квадратичной сходимости: Доказательство теоремы Канторовича в $R$
Часть 2: Метод Ньютона в $R^n$. От Гессиана к Аппаратным Лимитам
Часть 3: Метод Ньютона для Векторных полей. Матрица Якоби, Гато и Архитектура Backpropogation
Бонусная Часть 4: Метод Ньютона в бесконечномерных пространствах (Level 99)

Если же алгоритм угадывает категории (задача классификации), базовой метрикой ошибки и неопределенности выступает энтропия. Отличный стартовый пример — построение Дерева Решений (Decision Tree). Суть этого алгоритма в том, чтобы на каждом шаге задавать данные вопросы (например, «возраст > 30?») и разбивать датасет на ветки так, чтобы в каждом новом узле снижался уровень хаоса и оставались объекты преимущественно одного класса.

Базовой мерой этого хаоса является информационная энтропия Шеннона: $H(p) = -\sum p_c \log_2 p_c$, где $p_c$ — истинная физическая доля объектов $c$-го класса внутри конкретного узла. Если вы помните школьную физику, эта концепция вам уже знакома: философски и математически формула Шеннона является потрясающе точным эквивалентом термодинамической энтропии Гиббса-Больцмана ($S = -k_B \sum p_i \ln p_i$, где $k_B$ — постоянная Больцмана). Физический смысл этой величины — мера беспорядка, показывающая степень «размытости» системы по всем возможным микросостояниям. А её строгий математический (информационный) смысл — это мера неопределенности: среднее количество бит информации, которое нам понадобится, чтобы закодировать класс случайно вытащенного из этого узла объекта.

Ниже есть продолжение.

Важно понимать, что легитимность применения этой элегантной формулы неявно опирается на два фундаментальных физико-математических допущения. Первое — аналог теоремы Лиувилля о сохранении фазового объема. В статистической механике она гласит, что объем возможных состояний замкнутой системы со временем не сжимается и не расширяется. Ее математическим воплощением здесь выступает локальное сохранение вероятностной меры ($\sum p_c = 1$ на каждом ветвлении): при любом разбиении дерева общая «масса» данных не исчезает и не берется из ниоткуда, а строго аддитивно перераспределяется по новым веткам.

Второе допущение — эргодичность системы. Математически строго лаконичная формула энтропии Шеннона выводится исключительно в эргодичном случае. Без этого допущения в математике моментально появляются громоздкие цепи Маркова и условные вероятности, и простая формула теряет смысл. Строго говоря, в реальных физических системах (как и в «грязных» данных машинного обучения) идеальная эргодичность недостижима. Однако, усиленно махая руками и делая разумные статистические допущения (апеллируя к той же формуле Больцмана), мы получаем своеобразный «классический предел»: громоздкая истинная функция приближенно сводится к базовому макроскопическому случаю Шеннона. Эта аппроксимация железно гарантирует нужную нам логику: если в ветку попали данные только одного класса, энтропия схлопывается в нуль (абсолютный порядок), а при равном перемешивании — достигает максимума.

Деревья решений оперируют макро-уровнем: они вычисляют энтропию для узла в целом. Но когда мы переходим к алгоритмам, обучаемым с помощью градиентного спуска (Нейросети, Логистическая регрессия), нам нужен дифференцируемый интерфейс (Loss) для каждого отдельного объекта. Здесь в дело вступает кросс-энтропия: $Loss_j = -\sum y^{(j)}_c \ln \hat{p}^{(j)}_c$.

Обратите внимание на три отличия. Во-первых, $y^{(j)}_c$ — это абсолютная истина (вектор One-Hot, где одна единица и остальные нули, ведь конкретный объект принадлежит строго одному классу). Во-вторых, $\hat{p}^{(j)}_c$ — это неуверенная вероятность, предсказанная алгоритмом (обычно на выходе слоя Softmax). В-третьих, произошел каст типов: вместо $\log_2$ алгоритмы ML всегда используют натуральный логарифм $\ln$, так как его производная — это красивая дробь $1/x$, идеальная для градиентов (а результат измеряется уже не в битах, а в «натах»).

Кросс-энтропия измеряет «цену ошибки» и жестко штрафует за самоуверенные промахи. А теперь самое главное: средняя кросс-энтропия математически равна сумме энтропии Шеннона и Дивергенции Кульбака-Лейблера (KL-Divergence). В идеальном случае, когда предсказанные Softmax вероятности в точности совпадают с фактическими долями классов ($\hat{p}_c = p_c$), дивергенция обнуляется, и кросс-энтропия математически схлопывается ровно в макроскопическую энтропию Шеннона! Именно поэтому оптимизация градиентов на уровне объектов заставляет алгоритм искать идеальное макро-разбиение.

Давайте закрепим на численном примере. Представим корневой узел: датасет из 10 животных (4 кошки, 4 собаки и 2 акулы). Истинные доли $p_c$ равны $0.4$, $0.4$ и $0.2$. Если алгоритм идеально угадает эти честные вероятности, средняя кросс-энтропия совпадет с энтропией Шеннона для корня (посчитаем в битах через $\log_2$): $H_{root} = -(0.4 \log_2 0.4 + 0.4 \log_2 0.4 + 0.2 \log_2 0.2) \approx 1.52$ бита. Это наш исходный уровень хаоса.

Как дерево снижает хаос? Оно задает вопрос: «Вес животного меньше 10 кг?». Датасет разбивается на две ветки. В левую ветку уходят 6 животных (3 кошки, 2 собаки и 1 акула). Доли: $p \approx [0.50, 0.33, 0.17]$. Энтропия этого узла падает: $H_{лев} \approx 1.46$ бита. В правую ветку уходят 4 крупных животных (1 кошка, 2 собаки, 1 акула). Их доли: $p = [0.25, 0.50, 0.25]$. Энтропия правого узла: $H_{прав} = 1.50$ бита.

Дерево вычисляет метрику Information Gain (Прирост информации) по формуле $IG = H_{root} - \sum \frac{N_i}{N} H_i$. Алгоритм взвешивает энтропию новых узлов: $1.52 - (\frac{6}{10} \times 1.46 + \frac{4}{10} \times 1.50) = 1.52 - 1.476 \approx 0.044$ бита. Общий хаос снизился ($IG > 0$), поэтому разбиение принимается!

А теперь посмотрим на штраф градиентного алгоритма на уровне конкретного объекта: если в правом узле нейросеть вдруг «сойдет с ума» и через Softmax самоуверенно предскажет для конкретной собаки ($y = [0, 1, 0]$) вероятность того, что это кошка на 90% ($\hat{p} = [0.9, 0.1, 0]$), то кросс-энтропия для этого несчастного пса взлетит в космос (считаем в натах через $\ln$): $Loss = -1 \cdot \ln(0.1) \approx 2.30$. Формула жестоко наказывает алгоритм за расхождение между предсказанием и реальностью, генерируя гигантский градиент для исправления весов.

Часть 1 Приложение А. Пространства $L_p$ (Under the Hood): От топологических хаков к квадратичной гладкости

Text rendered via Dual-Core compilation (Human author + LLM co-processor).
Англоязычная версия данной заметки доступна здесь https://alex-ber.medium.com/9c213a0e3dfb.

См. также:
Часть 1: Метод Ньютона в R. От эвристики к формальной верификации (Kernel-Level)
Часть 1 Приложение А. Пространства $L_p$ (Under the Hood): От топологических хаков к квадратичной гладкости
Часть 1 Приложение B. Другой пример Loss function на примере кросс-энтропии
Часть 1 Приложение C. Анатомия квадратичной сходимости: Доказательство теоремы Канторовича в $R$
Часть 2: Метод Ньютона в $R^n$. От Гессиана к Аппаратным Лимитам
Часть 3: Метод Ньютона для Векторных полей. Матрица Якоби, Гато и Архитектура Backpropogation
Бонусная Часть 4: Метод Ньютона в бесконечномерных пространствах (Level 99)

Для начала стоит уточнить терминологию: в машинном обучении часто путают глобальные метрики качества (которые оценивают бизнес-результат работы модели для человека) и Loss-функции (функции потерь, которые алгоритм дифференцирует и оптимизирует «под капотом»). Если алгоритм предсказывает числа — допустим, цены на недвижимость (задача регрессии) — нам нужно измерить общую «величину промаха» между вектором предсказаний $\hat{y}$ и вектором наблюдаемых истинных значений (ground truth) $y$.

Для измерения таких расстояний математики используют понятие нормы. Самый простой и знакомый всем пример нормы — это обычный модуль числа (абсолютная величина). Любая норма автоматически порождает метрику (расстояние между векторами $x$ и $y$ вычисляется как $\|x - y\|$), что позволяет строго измерять расстояния. (Обратное, в общем случае, неверно: не всякая метрика порождается нормой).

В многомерных пространствах эта концепция обобщается до целого семейства $L_p$-норм. Общая формула для вектора $x = (x_1, \dots, x_n)$ выглядит так: $\|x\|_p = \left( \sum_{i=1}^n |x_i|^p \right)^{1/p}$. Компоненты этого вектора могут жить как в привычном вещественном пространстве $\mathbb{R}^n$, так и в комплексном $\mathbb{C}^n$. В обоих случаях формула работает одинаково безупречно, а $|x_i|$ выступает как универсальный модуль (абсолютная величина) числа.

Ниже есть продолжение.

Эта формула строго выполняет все аксиомы математической нормы (включая неравенство треугольника и однородность) только на интервале $p \in [1, +\infty]$. В зависимости от выбора параметра $p$ происходят самые интересные математические мутации:

• $p=1$: $\|x\|_1 = \sum_{i=1}^n |x_i|$. Это так называемое «Манхэттенское расстояние» (или $L_1$-норма), где путь измеряется строго по сетке координат. Геометрически единичный шар (множество точек, где $\|x\|_1 \le 1$) в 2D выглядит как ромб (или квадрат, повернутый на 45 градусов). В машинном обучении на ней базируется метрика MAE и $L_1$-регуляризация (Lasso), создающая разреженность признаков. А самое изящное происходит, если мы сожмем наше пространство до одного измерения $\mathbb{R}^n=\mathbb{R}^1=\mathbb{R}$ или $\mathbb{C}^n=\mathbb{C}^1=\mathbb{C}$, то есть подставим в общую формулу $\|x\|_p = \left( \sum_{i=1}^n |x_i|^p \right)^{1/p}$, при $p=1$, $n=1$ она превращается в $\|x_1\|_1 = \sum_{i=1}^1 |x_i| = |x_1|$. Т.е. мы получили на вещественных числах $\mathbb{R}$ или комплексных числах $\mathbb{C}$ метрику $\|x\| = |x|$. В зависимости от этого $|x_i|$ — это либо модуль (абсолютная величина) вещественного либо модуль комплексного числа. В частности получаем, что обычный школьный модуль действительного (или комплексного) числа — это просто частный случай многомерной $L_p$-нормы!
• $p=2$: $\|x\|_2 = \sqrt{\sum_{i=1}^n |x_i|^2}$. Это классическая евклидова норма. Это обычная школьная норма, соответствующая расстоянию по прямой линии (по теореме Пифагора), как если бы мы приложили к пространству физическую линейку. Геометрически её единичный шар в 2D — это идеальный круг (или сфера в 3D). В машинном обучении на её основе строится $L_2$-регуляризация (Ridge), которая штрафует модель за слишком большие веса, заставляя их равномерно уменьшаться.
• $0 < p < 1$: по мере убывания $p$ на интервале $p \in (0, 1)$ ломается выпуклость единичного шара и перестает работать неравенство треугольника. Докажем это: возьмем базисные векторы $x = (1, 0)$ и $y = (0, 1)$ в $\mathbb{R}^2$. Их $L_p$-нормы равны единице: $\|x\|_p = \|y\|_p = 1$. Однако норма их суммы $\|x+y\|_p = \|(1, 1)\|_p = (1^p + 1^p)^{1/p} = 2^{1/p}$. Поскольку $0 < p < 1$, показатель степени $1/p > 1$, следовательно $2^{1/p} > 2$. Мы получаем $\|x+y\|_p > \|x\|_p + \|y\|_p$, что напрямую нарушает свойство неравенства треугольника.
  
  Из этого же примера вытекает потеря выпуклости: по определению выпуклого множества середина отрезка между векторами $\frac{x+y}{2} = (0.5, 0.5)$ должна лежать внутри единичного шара. Давайте посчитаем её норму: $\|(0.5, 0.5)\|_p = (0.5^p + 0.5^p)^{1/p} = (2 \cdot 0.5^p)^{1/p} = 2^{1/p} \cdot 0.5 = 2^{1/p} \cdot 2^{-1} = 2^{1/p - 1}$.
  
  Так как $p < 1$, то дробь $1/p > 1$. Следовательно, показатель степени $1/p - 1 > 0$. Любое число больше единицы (в нашем случае двойка) в положительной степени дает результат строго больше $1$. А значит, норма середины отрезка строго больше $1$. Точка вываливается за границы единичного шара, что геометрически превращает его из выпуклой фигуры во вдавленный четырехконечный «астероид».
• $p \to \infty$: Формула схлопывается в предел, который дает максимальную норму (норму Чебышева): $\|x\|_\infty = \max_i |x_i|$. Вывод этого предела математически изящен: если мы вынесем максимальный по модулю элемент $M = \max_i |x_i|$ за скобки, общая формула примет вид $M \cdot \left( \sum_{i=1}^n \left( \frac{|x_i|}{M} \right)^p \right)^{1/p}$. При $p \to \infty$ все дроби для элементов, меньших $M$, устремятся к нулю. Слагаемые, равные максимуму, дадут единицы. Сумма внутри скобок превратится в константу $k$ (количество максимальных элементов вектора). Поскольку $\lim_{p \to \infty} k^{1/p}=1$, вся конструкция схлопывается ровно в $M$. Таким образом, эта норма оценивает вектор исключительно по его самому большому элементу, игнорируя остальные. Геометрически единичный шар для этой нормы в 2D превращается в ровный квадрат (или куб в 3D), стороны которого строго параллельны осям координат. Если сжать пространство до одного измерения ($n=1$), то $\|x\|_\infty = \max_1 |x_1| = |x_1|$, что снова безупречно возвращает нас к обычному модулю числа.
• $p \to 0$: Это самая парадоксальная точка, так как математически задать норму здесь невозможно. Если попытаться взять строгий алгебраический предел самой суммы при $p \to 0$, то для любого ненулевого числа $\lim_{p \to 0} |x_i|^p = 1$, а для нуля $\lim_{p \to 0} 0^p = 0$. Соответственно, $\lim_{p \to 0} \sum |x_i|^p$ работает просто как счетчик ненулевых элементов вектора. Если рассмотреть это в одномерном пространстве ($n=1$), то «норма» $\|x\|_0$ равна $1$ для любого ненулевого $x$ (даже миллионного) и $0$ для нулевого. И хотя строго математически это не является нормой (нарушается аксиома однородности при умножении на скаляр), в машинном обучении именно этот алгебраический предел называют «$L_0$-нормой», так как он исторически крайне полезен при регуляризации, когда алгоритму нужно занулить лишние веса и сжать модель.
  
  Однако в строгом функциональном анализе под $L_0$ понимают другое пространство. Там невозможность использовать классическую формулу обходят не через алгебраический предел суммы единиц, а задавая искусственную метрику, порождающую топологию сходимости по мере. Вывод этой метрики строится через искусственное ограничение роста слагаемых: $d(x, y) = \sum_{i=1}^n \min(|x_i - y_i|, 1)$. Если мы вернемся к одномерному случаю ($n=1$), расстояние до нуля будет вычисляться как $d(x, 0) = \min(|x|, 1)$ — то есть привычный модуль числа, но жестко «обрезанный» единицей. Это превращает наше пространство в так называемое F-пространство. (Заметим, что до идеального Гильбертова пространства — где есть скалярное произведение, углы между векторами и работает вся классическая квантовая механика — нашему пространству как до луны, ведь Гильбертовым является только $L_2$ в том смысле как мы определили выше. Но к безумным свойствам этих пространств мы детально вернемся в бонусной четвертой части).
• $-\infty < p < 0$: Этот интервал имеет огромный смысл в статистике и алгебре, где данная конструкция известна как обобщенное среднее (или среднее степенное). Например, если подставить $p = -1$ (и домножить на $n$), мы получим классическое гармоническое среднее, которое незаменимо при расчете сопротивления параллельных цепей в физике или средних центив в финансах.
  
  Однако в контексте геометрии пространств здесь полностью рушатся базовые свойства метрики из-за деления на ноль. Чтобы сделать это предельно прозрачным, давайте введем замену: пусть $p = -q$, где $q > 0$. Перепишем общую формулу, избавляясь от отрицательной степени по правилу $x^{-a} = 1/x^a$:
  
  $\|x\|_{-q} = \left( \sum_{i=1}^n |x_i|^{-q} \right)^{-1/q} = \frac{1}{\left( \sum_{i=1}^n \frac{1}{|x_i|^q} \right)^{1/q}}$
  
  Теперь возьмем вектор, у которого есть хотя бы один нулевой элемент, но сам вектор не является нулевым. Например, $x = (0, 500)$ в двумерном пространстве. Подставляем его в нашу переписанную формулу:
  $\|x\|_{-q} = \frac{1}{\left( \frac{1}{0^q} + \frac{1}{500^q} \right)^{1/q}}$
  
  Первое слагаемое в знаменателе содержит фатальное деление на ноль. В терминах пределов, дробь $\frac{1}{0}$ устремляется в бесконечность ($+\infty$). Таким образом, сумма внутри скобок в знаменателе становится бесконечно огромной. Извлечение корня из бесконечности оставляет её бесконечностью, и мы приходим к финальному виду:
  $\|x\|_{-q} \to \frac{1}{+\infty} = 0$
  
  Это катастрофа для концепции расстояния. Норма вектора $(0, 500)$ оказалась равна нулю! Нарушена самая фундаментальная аксиома невырожденности (норма может быть равна нулю только у вектора, сплошь состоящего из нулей). Из-за единственной нулевой координаты вся геометрия пространства аннигилируется.
• $p \to -\infty$: (Математическая пасхалка). Если $p \to +\infty$ выдает максимальный элемент вектора, то логично проверить систему на прочность и устремить параметр в минус бесконечность. Алгебраический предел $\lim_{p \to -\infty} \|x\|_p$ (при условии, что все $x_i \neq 0$) строго выдаст минимальный по модулю элемент: $\min_i |x_i|$. Вывод этого предела аналогичен случаю с плюсом: только мы выносим за скобки минимальный по модулю элемент $m = \min_i |x_i|$. Формула принимает вид $m \cdot \left( \sum_{i=1}^n \left( \frac{|x_i|}{m} \right)^p \right)^{1/p}$. Так как $p \to -\infty$, для всех элементов, которые строго больше $m$ (то есть значение дроби $q = \frac{|x_i|}{m} > 1$), предел слагаемого равен нулю: $\lim_{p \to -\infty} q^p = 0$. Останутся только слагаемые, соответствующие минимуму (где основание дроби в точности равно $1$, а предел $\lim_{p \to -\infty} 1^p = 1$). Сумма внутри скобок в пределе устремится к константе $k$ (числу минимальных элементов вектора), а поскольку предел внешней степени $\lim_{p \to -\infty} k^{1/p} = 1$, вся конструкция элегантно схлопывается в $m$.
  
  Однако, как и следовало ожидать из разбора предыдущего пункта, этот «хак» окончательно ломает математическую архитектуру нормы. Нарушается фундаментальная аксиома невырожденности (System Security): норма вектора должна быть равна нулю только если сам вектор состоит из нулей. Но в случае $\min_i |x_i|$ достаточно, чтобы хотя бы один элемент вектора был равен нулю, и вся конструкция схлопнется в ноль, даже если остальные элементы равны миллионам (в терминах предела — произойдет то самое деление на ноль под суммой, которое мы разобрали выше).
  
  Важное уточнение: если в парадоксальной точке $p \to 0$ математикам удалось спасти топологию пространства, искусственно задав метрику $d(x, y) = \sum_{i=1}^n \min(|x_i - y_i|, 1)$, то при $p \to -\infty$ этот трюк не пройдет. Ни эта метрика, ни какая-либо другая не способны спасти данную конструкцию. Именно поэтому ни в функциональном анализе, ни в ML предел при $p \to -\infty$ не имеет абсолютно никакого практического смысла, однако он безупречно демонстрирует эстетическую симметрию математики на крайних полюсах.

Чтобы оценить итоговое качество предсказаний модели, нам нужно превратить весь вектор ошибок $E = y - \hat{y}$ (разницу между истиной и предсказаниями) в одно итоговое число. Мы могли бы опереться на $L_1$-норму и получить среднее абсолютное отклонение (MAE): $MAE = \frac{1}{n} \|E\|_1 = \frac{1}{n} \sum |y_i - \hat{y}_i|$. Мы также могли бы использовать $L_2$-норму «как есть» (что приводит к метрике RMSE с её громоздким внешним корнем). Однако в большинстве задач регрессии стандартом де-факто выступает Loss-функция MSE (Mean Squared Error, среднеквадратичная ошибка). Она берёт за основу $L_2$-норму вектора ошибок, но возводит её в квадрат (и усредняет по $n$): $MSE = \frac{1}{n} \|E\|_2^2 = \frac{1}{n} \sum_{i=1}^n (y_i - \hat{y}_i)^2$.

Здесь важно сделать математическое уточнение: MSE определена ИСКЛЮЧИТЕЛЬНО для $L_2$-нормы. Вы не можете взять произвольную $L_p$-норму (например, $L_3$), возвести её в квадрат и назвать это «среднеквадратичной ошибкой». Само понятие MSE и её математический смысл намертво привязаны только к квадрату евклидова расстояния.

Почему алгоритмы предпочитают оптимизировать именно квадрат $L_2$-нормы (MSE), а не базовую $L_2$-норму или MAE? У этого есть две железобетонные архитектурные причины. Во-первых, возведение в квадрат элегантно уничтожает огромный внешний корень из формулы $L_2$. Сама по себе чистая $L_2$-норма в точке абсолютного нуля недифференцируема: из-за наличия квадратного корня, производная которого $1/(2\sqrt{x})$ при приближении к нулю улетает в бесконечность, геометрически она образует конус, и в его вершине возникает «излом», не позволяющий посчитать градиент. А вот без корня функция становится идеально гладкой многомерной параболой, максимально удобной для градиентного спуска.

Во-вторых, квадрат радикально меняет бизнес-логику штрафов. В отличие от MAE, которая бьет алгоритм линейно и с одинаковой силой за любые неточности (из-за чего модель может бесконечно «дрожать» вокруг минимума), MSE прощает алгоритму множество мелких отклонений. Так как производная параболы пропорциональна самой ошибке, по мере приближения к идеалу градиент затухает, и модель плавно «паркуется» в точке оптимума. Более того, оптимизация MSE строго математически эквивалентна предположению, что шум в наших данных имеет нормальное (гауссовское) распределение.

В то же время MSE агрессивно, по параболе, штрафует за крупные промахи (outliers). В реальности эта чувствительность является главным недостатком MSE — всего один аномальный выброс в «грязных» данных сгенерирует гигантский градиент и утащит за собой веса всей модели. Чтобы решить эту проблему и взять лучшее от обоих миров (квадратичную мягкую парковку у нуля от MSE и линейную защиту от выбросов от MAE), алгоритмы часто используют компромиссную функцию потерь — Loss Huber (функцию Хьюбера), которая ведёт себя как гладкая парабола при малых ошибках и превращается в прямую линию при больших.

Часть 1: Метод Ньютона в R. От эвристики к формальной верификации (Kernel-Level)

Text rendered via Dual-Core compilation (Human author + LLM co-processor).
Англоязычная версия данной заметки доступна здесь https://alex-ber.medium.com/708d04754e9e.

См. также:
Часть 1: Метод Ньютона в R. От эвристики к формальной верификации (Kernel-Level)
Часть 1 Приложение А. Пространства $L_p$ (Under the Hood): От топологических хаков к квадратичной гладкости
Часть 1 Приложение B. Другой пример Loss function на примере кросс-энтропии
Часть 1 Приложение C. Анатомия квадратичной сходимости: Доказательство теоремы Канторовича в $R$
Часть 2: Метод Ньютона в $R^n$. От Гессиана к Аппаратным Лимитам
Часть 3: Метод Ньютона для Векторных полей. Матрица Якоби, Гато и Архитектура Backpropogation
Бонусная Часть 4: Метод Ньютона в бесконечномерных пространствах (Level 99)

Dual-Core подход и Эвристика (Запускаем Систему-1)

Всякий раз, когда перед нами стоит задача найти корень функции $f(x)\; =\; 0$, мозг требует наглядности. Студенты, инженеры и дата-сайентисты обожают, когда сложные абстракции можно «потрогать». Это абсолютно нормально: чтобы погрузиться в алгоритм, нам сначала нужно запустить «Систему-1» — наше быстрое, ассоциативное и визуальное мышление.

Прежде чем закапываться в строгую математику (наш Kernel-level), давайте выведем метод Ньютона двумя максимально интуитивными — но, спойлер, математически нестрогими — путями.

Ниже есть продолжение.

Путь первый: физический (Ньютон и кинематика)

Давайте представим простейшую физическую симуляцию. Пусть наша функция $f(x)$ описывает текущую координату летящего объекта, а переменная $x$ играет роль времени. У нас есть зафиксированное положение объекта в момент времени $x_{old}$, равное $f(x_{old})$.

Из школьного курса физики мы знаем, что производная координаты по времени — это мгновенная скорость. Значит, скорость нашего объекта в данный момент равна $v = f'(x_{old})$.

Как найти координату объекта спустя мгновение $\Delta x$? Берем классическую формулу пути для равномерного движения и делаем эвристическое допущение: на коротком отрезке времени наша скорость не успеет сильно измениться. Тогда:

$f(x_{new}) \approx f(x_{old}) + v \cdot \Delta x$

В чем заключается наша главная задача? Мы ищем корень — то есть хотим узнать, на сколько нужно "перемотать" время, чтобы объект оказался точно в нулевой координате. Значит, мы требуем, чтобы $f(x_{new}) = 0$. Подставляем этот ноль в наше уравнение и выражаем шаг $\Delta x$:

$0 \approx f(x_{old}) + v \cdot \Delta x$

$\Delta x = - \frac{f(x_{old})}{v}$

Вуаля! Мы вычислили, на сколько нужно сдвинуть время, чтобы с текущей скоростью $v$ приземлиться ровно в ноль. Теперь нам остается только сделать этот шаг от старой точки, чтобы получить новую:

$x_{new} = x_{old} + \Delta x = x_{old} - \frac{f(x_{old})}{f'(x_{old})}$

На языке алгоритмов мы привыкли обозначать текущий шаг как $x_k$, а следующий как $x_{k+1}$. Переписав формулу, мы получаем классический шаг метода Ньютона-Рафсона, который мы только что «изобрели», просто вспомнив формулу $S = v \cdot t$. Конечно, поскольку в реальности скорость функции меняется (у нее есть ускорение — вторая производная), за один шаг мы в идеальный ноль не попадем. Именно поэтому метод итеративный!

Путь второй: геометрический (касательная и метод Рафсона/Симпсона)

Если физика вас не убеждает, давайте включим пространственное мышление. Рисуем график функции $f(x)$. У нас есть текущая точка $(x_k, f(x_k))$. Кривая может быть сложной, изгибаться и вести себя непредсказуемо. Что делают инженеры, когда видят нелинейность? Они ее линеаризуют!

Заменим сложную кривую в нашей текущей точке на самую лучшую локальную прямую — её касательную. Давайте выведем её уравнение.

Любая прямая на плоскости полностью задается точкой, через которую она проходит, и её наклоном. Наша прямая гарантированно проходит через точку $(x_k, f(x_k))$. Ее наклон — это отношение изменения по вертикали к изменению по горизонтали ($\frac{\Delta y}{\Delta x}$). По геометрическому смыслу производной, этот наклон в точности равен $f'(x_k)$.

Теперь возьмем абсолютно любую точку $(x, y)$ на нашей будущей прямой. Наклон отрезка между нашей зафиксированной точкой и этой произвольной точкой должен равняться производной. Запишем это:

$\frac{y - f(x_k)}{x - x_k} = f'(x_k)$

Умножаем обе части на знаменатель, и перед нами возникает уравнение касательной:

$y - f(x_k) = f'(x_k)(x - x_k)$

Нас интересует, где эта упрощенная модель пересекает ось абсцисс. Приравниваем $y = 0$ и решаем уравнение относительно $x$ (нашего нового шага $x_{k+1}$):

$- f(x_k) = f'(x_k)(x_{k+1} - x_k)$

$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$

И снова мы приходим к той же самой формуле. Мы заменили сложную задачу (поиск корня кривой) на простую (поиск корня прямой), сместились, и готовы повторить этот процесс снова.

Философский мост: Вавилонский метод vs Греческий подход

Здесь стоит сделать важную остановку. На самом деле, то, что мы сейчас обсуждаем, отражает глобальный раскол в подходах к вычислениям, который дожил до эпохи Machine Learning.

Историки математики выделяют два фундаментальных паттерна: «вавилонский» и «греческий».

«Вавилонский метод» — это чистая эмпирика, data-driven подход. Древние вавилоняне не доказывали теорем. Они собирали таблицы данных, замечали закономерности и выводили эвристические правила (алгоритмы). В современном мире вавилонский подход — это парадигма Deep Learning. Мы берем «черный ящик», заливаем в него терабайты данных, масштабируем параметры, и система индуктивно подгоняет кривые, находя решение. Почему это работает? Вавилонянам (и часто ML-инженерам) это не так важно, главное — Loss падает.

«Греческий метод» — это царство дедукции и формальных моделей. Греки (Пифагор, Евклид, Архимед) сначала строили строгую абстрактную теорию. Пусть даже их модель мира была странной (вроде хрустальных сфер в космосе), но она была математически строгой, и из неё логически выводились все следствия. Именно так Эратосфен смог вычислить радиус Земли с помощью палки и тени.

Катарсис: чёрт из табакерки

А теперь давайте столкнем эти два мира лбами. Как древние вавилоняне (за 1500 лет до н.э.) вычисляли квадратные корни, например, $\sqrt{9801}$?

У них было простое эмпирическое правило-эвристика: возьми любую начальную догадку (допустим, $x_0 = 100$, так как мы понимаем, что $100^2 = 10000$, что очень близко к цели). Подели искомое число на эту догадку.

Тут возникает важный логический момент: если начальная догадка была больше настоящего корня, то результат деления будет меньше корня. А если догадка оказалась меньше корня, то результат деления будет больше. В любом случае настоящий корень всегда оказывается зажат где-то посередине между вашей догадкой и результатом деления!

Поэтому просто возьми среднее арифметическое между ними — это и будет новая, улучшенная догадка, которая гарантированно ближе к истине. Алгоритм вавилонян выглядел так:

$x_{k+1} = \frac{1}{2} \left( x_k + \frac{9801}{x_k} \right)$

Давайте сделаем первый шаг:

$x_1 = \frac{1}{2} \left( 100 + \frac{9801}{100} \right) = \frac{1}{2} \left( \frac{10000 + 9801}{100} \right) = \frac{19801}{200}$

Истинный корень из 9801 равен ровно 99. Всего за одну итерацию алгоритм, придуманный примерно в XVII в. до н.э., промахнулся мимо правильного ответа лишь на 5 тысячных (так как $\frac{19801}{200} = 99.005$)! Но давайте сделаем второй шаг, чтобы избежать округлений, подставим наше новое точное значение $x_1$ в виде обыкновенной дроби:

$x_2 = \frac{1}{2} \left( \frac{19801}{200} + \frac{9801}{\frac{19801}{200}} \right) = \frac{1}{2} \left( \frac{19801}{200} + \frac{9801 \cdot 200}{19801} \right) = \frac{1}{2} \left( \frac{19801}{200} + \frac{1960200}{19801} \right)$

Приводим дроби в скобках к общему знаменателю ($200 \cdot 19801 = 3960200$):

$x_2 = \frac{1}{2} \left( \frac{19801^2 + 1960200 \cdot 200}{3960200} \right) = \frac{1}{2} \left( \frac{392079601 + 392040000}{3960200} \right) = \frac{784119601}{7920400}$

А теперь самая магия. Если выделить из этой монструозной дроби целую часть, мы получим ровно $99 + \frac{1}{7920400}$. Алгоритм выдал феноменальную точность без единого округления!

Спустя всего две итерации мы получили точность до седьмого знака после запятой.

А теперь включим «греческую» строгость и применим метод Ньютона к задаче поиска корня. $\sqrt{9801}$ — это положительный корень функции $f(x) = x^2 - 9801 = 0$.

Её производная в нашей текущей точке: $f'(x_k) = 2x_k$. Подставляем в общую формулу шага Ньютона $\left( x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} \right)$:

$x_{k+1} = x_k - \frac{x_k^2 - 9801}{2x_k}$

Проведем вычисления. Сначала приводим $x_k$ к общему знаменателю $2x_k$:

$x_{k+1} = \frac{2x_k^2}{2x_k} - \frac{x_k^2 - 9801}{2x_k}$

Записываем всё под одну общую черту (минус перед второй дробью меняет знаки в числителе):

$x_{k+1} = \frac{2x_k^2 - (x_k^2 - 9801)}{2x_k} = \frac{2x_k^2 - x_k^2 + 9801}{2x_k} = \frac{x_k^2 + 9801}{2x_k}$

Теперь разобьем полученную дробь на две отдельные части и сократим первую из них:

$x_{k+1} = \frac{x_k^2}{2x_k} + \frac{9801}{2x_k} = \frac{x_k}{2} + \frac{9801}{2x_k}$

Наконец, выносим множитель $\frac{1}{2}$ за скобки из обоих слагаемых:

$x_{k+1} = \frac{1}{2} \left( x_k + \frac{9801}{x_k} \right)$

Бам! Формула метода Ньютона в точности схлопнулась в эмпирическое правило вавилонян! Строгая математическая модель, которую мы вывели через кинематику и касательные, веками молча пряталась под капотом древней эвристики.

Переключение в Систему-2

Наглядно? Абсолютно. Можно ли это закодить? Да, и оно будет работать. Но строго ли это? Нет. И кинематика, и визуализация касательных — это классическое «махание руками» (hand-waving).

Наша способность визуализировать геометрию сломается, как только мы перейдем в многомерные пространства нейросетей, где касательные превращаются в абстрактные гиперплоскости, а привычный угол наклона нарисовать невозможно. Физика работает только при условии, что «скорость не меняется», что локально и не дает гарантий безопасности алгоритма.

Нам нужен строгий математический фундамент. Эвристика закончилась — мы переходим в Систему-2 и начинаем писать Kernel-level код, опираясь на формальное разложение функции в ряд Тейлора.

Переосмысление производной: Линейный Патч (Linear Patch)

Смерть касательной

Итак, мы в Системе-2. Первое, что нам нужно сделать для написания надежного математического ядра (Kernel-level) — это отказаться от школьных картинок. Визуализация через касательные и углы наклона — это отличный стартовый костыль, но в мире Machine Learning он превращается в ловушку.

Современные нейросети оптимизируют функции потерь (Loss), которые зависят от миллионов или даже миллиардов параметров. Мы находимся в огромном пространстве $\mathbb{R}^{10^9}$. В таком пространстве касательная прямая мутирует в касательную гиперплоскость. Наше пространственное воображение больше не может строго обосновать и гарантировать правильность шага — хотя мы и продолжим использовать геометрические метафоры вроде «оврагов» или «седловых точек» для интуиции. Чтобы идти дальше, мы должны перевести геометрию на язык строгой алгебры.

Производная как Линейный Оператор

В школе мы говорили, что производная $f'(x_0)$ в точке — это число (тангенс угла наклона или мгновенная скорость). В высшей математике и архитектуре ML производная — это не число. Это Линейный Оператор.

Представьте, что у вас есть сложная, непредсказуемая, нелинейная функция на каком-то отрезке [a, b]. Мы находимся в точке $x_0$ и хотим сделать небольшой шаг $\Delta x$. Нам нужно узнать, как при этом изменится значение функции (то есть найти приращение $\Delta f$).

Производная $f'(x_0)$ — это лучший локальный «Линейный Патч» (Linear Patch) для нашей функции. В классической академической математике эту функцию-трансформер называют Дифференциалом. Она принимает на вход ваш вектор смещения $\Delta x$ и линейно трансформирует его в изменение функции $\Delta f$:

$\Delta f \approx f'(x_0) \cdot \Delta x$

Кстати, та самая школьная формула касательной — это и есть просто графическое отображение работы этого патча: $y = f(x_0) + f'(x_0)(x - x_0)$.

Суть линейного патча в его поразительной предсказуемости: если вы увеличите шаг $\Delta x$ в 2 раза, то прогнозируемое изменение функции $\Delta f$ тоже увеличится ровно в 2 раза. Это идеальный, надежный интерфейс внутри хаотичного нелинейного мира.

Единый интерфейс (API) для любого измерения

Вы можете спросить: зачем называть обычное умножение на число таким тяжеловесным термином как «Линейный Оператор»?

Ответ кроется в масштабируемости. Обычное число $f'(x_0)$ из одномерного пространства $\mathbb{R}^1$ можно рассматривать как самую маленькую в мире матрицу — матрицу размера $1 \times 1$.

Когда в следующих частях нашей серии мы начнем масштабировать алгоритм, наши смещения $\Delta x$ и изменения функции $\Delta f$ перестанут быть просто числами и станут многомерными векторами или тензорами. Но алгебраическая запись линейного патча $\Delta f \approx Operator \cdot \Delta x$ не изменится вообще. Закрытый интервал [а, b] превратится в любое компактное множество, а этот крошечный скалярный оператор бесшовно и автоматически эволюционирует:

• В вектор-строку Градиента, когда мы будем минимизировать многомерный Loss.
• В прямоугольную Матрицу Якоби, когда слои нашей нейросети начнут принимать векторы и возвращать другие векторы.
• И, наконец, в Производную Фреше (Level 99), когда мы выйдем в бесконечномерные пространства непрерывной памяти (Банаховы пространства). Этот же самый интерфейс позволит нам обучать непрерывные во времени нейросети (Neural ODE) и аппаратно «взламывать» уравнения нелинейной физики.

А когда линейности перестанет хватать и нам понадобится учесть кривизну пространства для точного снайперского шага, к нашему API органично добавится следующий этаж — «Квадратичный патч», где и появится знаменитая Матрица Гессе (Гессиан).

Интерфейс патча остается неизменным на любом уровне абстракции. Смерть школьной касательной открывает нам доступ к универсальному математическому API Вселенной.

Но у этого линейного патча прямо сейчас есть одна фундаментальная уязвимость — знак «приближенно равно» ($\approx$). Настало время с ней разобраться и перейти к инкапсуляции ошибки.

Инкапсуляция ошибки: о-малое и Формула Тейлора (API)

Линейный патч прекрасен, но в реальном нелинейном мире он всегда ошибается. Знак $\approx$ в формуле $\Delta f \approx f'(x_0) \Delta x$ — это бомба замедленного действия. Чтобы построить надежный алгоритм и гарантировать System Security, нам нужно строго описать и инкапсулировать эту ошибку. Нам нужны инструменты для работы с погрешностью.

Уровень абстракции 1 (High-Level API): Черный ящик $o(\Delta x)$

Первый способ работы с ошибкой — это спрятать её в «черный ящик». В математике этот паттерн проектирования называется «о-малое» от $\Delta x$, или $o(\Delta x)$. Мы переписываем наше приближение в виде точного равенства:

$\Delta f = f'(x_0) \Delta x + o(\Delta x)$

Что такое $o(\Delta x)$?

Примечание: Здесь было отступление для ML-инженеров, но оно у меня получилось длинное, поэтому я его вынес в две отдельные заметки "Часть 1 Приложение А. Пространства $L_p$ (Under the Hood): От топологических хаков к квадратичной гладкости" и "Часть 1 Приложение B. Другой пример Loss function на примере кросс-энтропия". Вы можете как прочитать их сейчас, так и прочитать после прочтения первой части.

И «о-малое» выступает как универсальный черный ящик, валидный для функции локальной ошибки абсолютно любой природы. У этого абстрактного интерфейса есть лишь один строгий контракт: по мере уменьшения шага $\Delta x$, ошибка убывает быстрее, чем сам шаг. На языке пределов это записывается так:

$\lim_{\Delta x \to 0} \frac{o(\Delta x)}{\Delta x} = 0$

Это отличный High-Level API. Он идеален для теоретических выкладок и асимптотики (когда шаг стремится к нулю). Но для реальной разработки и доказательства стабильности метода Ньютона он недостаточен. Нам нужно точно знать, насколько большой может быть ошибка при конкретном конечном шаге, а не в абстрактном пределе. Нам нужен доступ к исходному коду ошибки.

Уровень абстракции 2 (Low-Level API): Формула Тейлора

Чтобы заглянуть под капот ошибки, мы опускаемся на уровень ниже. Здесь нам на помощь приходит Формула Тейлора (в данном случае с остаточным членом в форме Лагранжа). По сути, Формула Тейлора — это конкретная, низкоуровневая «реализация» (implementation) нашего High-Level API применительно к итеративным методам.

Теоремы Лагранжа о конечных приращениях, которая оперирует только первой производной, нам уже не хватит. Первая производная описывает только наклон, а ошибка линейного патча возникает из-за того, что функция изгибается. Значит, нам нужна кривизна, за которую архитектурно отвечает вторая производная.

Классический матанализ любит раскладывать функции в бесконечный ряд Тейлора, но это требует идеальной гладкости (строгой аналитичности — способности функции идеально совпадать со своим бесконечным рядом, а не просто быть бесконечно дифференцируемой). В реальных алгоритмах нам не нужна бесконечность, да и архитектурные требования можно сильно смягчить. Нам достаточно, чтобы функция была всего лишь дважды дифференцируемой (с непрерывной второй производной). Этого минимума уже хватает, чтобы Формула Тейлора предоставила нам конечный, точный «исходный код» для вычисления значения функции в новой точке $x = x_k + \Delta x$ (то есть $\Delta x = x - x_k$):

$f(x) = f(x_k) + f'(x_k)\Delta x + \frac{1}{2}f''(\xi)\Delta x^2$

Давайте разберем этот код по частям:

• $f(x_k)$ — наша текущая позиция (база).
• $f'(x_k)\Delta x$ — работа нашего Линейного Патча (Дифференциала).
• $\frac{1}{2}f''(\xi)\Delta x^2$ — это и есть распакованная ошибка, наш квадратичный хвост.

Здесь $\xi$ — это какая-то промежуточная точка. В матанализе стандартное требование для таких теорем — функция должна быть непрерывна на замкнутом отрезке и дифференцируема на открытом. Поэтому наша точка $\xi$ всегда прячется где-то строго внутри открытого интервала $(x_k, x)$. И хотя мы не знаем её точного местоположения, это уже не важно.

Для строгой гарантии System Security мы рассматриваем весь наш рабочий замкнутый отрезок и просто берем максимально возможное значение модуля второй производной на нём (назовем эту константу максимальной кривизны $M$). Но имеем ли мы право утверждать, что этот максимум вообще существует?

Да! Здесь нас страхует знаменитая теорема Вейерштрасса для непрерывных функций: так как наша вторая производная непрерывна на замкнутом отрезке, она математически гарантированно достигает на нем своего максимального значения.

Замечание: теорема Вейерштрасса для непрерывных функций — это лишь проекция мощного закона из общей топологии. В оригинале он звучит так: непрерывная функция на компактном множестве всегда достигает своих экстремумов. Пока мы находимся в классических размерностях — в первых трех блоках нашей серии — действует теорема Гейне–Бореля: множество компактно тогда и только тогда, когда оно замкнуто и ограничено. Но будьте осторожны! В 4-й части, когда мы шагнем в бесконечномерные Банаховы пространства, ситуация изменится. Останется верно, что если множество компактно то оно замкнуто и ограничено, однако обратное утверждение, не верно в общем случае. Там замкнутости и ограниченности больше не хватит для компактности, топология покажет свои зубы, и нам потребуются куда более хитрые инструменты.

Взяв этот гарантированный максимум $M$, мы получаем железный «худший сценарий» (worst-case bound) — точную верхнюю границу ошибки, хуже которой ситуация точно не станет.

System Security: Теорема Канторовича как Статический Анализатор

Проблема: Уязвимость в коде

Итак, мы вывели алгоритм: $x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$. Посмотрите внимательно на эту формулу глазами программиста. Что вы видите? Правильно — потенциальный DivisionByZeroException.

Что произойдет, если производная $f'(x_k)$ окажется равна нулю (или очень близка к нему)? Знаменатель схлопнется, дробь станет гигантской, и наш следующий шаг выкинет нас далеко за пределы рабочей области. Алгоритм улетит в бесконечность. Даже если мы не делим на чистый ноль, слишком широкий шаг может вышвырнуть нас из так называемой «зоны притяжения» (basin of attraction) нашего корня. Эвристика без гарантий — это бомба в продакшене.

Теорема Канторовича: Строгая математическая формулировка

Теорема Канторовича: Пусть функция $f(x)$ непрерывна на замкнутом отрезке $D = [a, b]$ и дважды дифференцируема на интервале $(a, b)$. Пусть задана начальная точка $x_0 \in D$, для которой выполняются следующие условия:

1. Начальный шаг ограничен: $|\Delta x_0| = \left| \frac{f(x_0)}{f'(x_0)} \right| \le \eta$
2. Модуль обратной величины первой производной в начальной точке ограничен: $\left| \frac{1}{f'(x_0)} \right| \le \beta$. (Именно такая формулировка позволит нам в будущем бесшовно заменить число в знаменателе на норму обратной матрицы Якоби или Гессе в многомерном мире).
3. Модуль второй производной (кривизна) ограничен сверху: $|f''(x)| \le M$ для всех $x \in D$

Если выполняется условие $h = M \cdot \eta \cdot \beta \le \frac{1}{2}$ и отрезок $\Omega = [x_0 - t^*, x_0 + t^*]$, где $t^* = \frac{1 - \sqrt{1 - 2h}}{h} \eta \le 2\eta$, целиком принадлежит $D$, то внутри окрестности $\Omega$ гарантированно существует корень $x^*$ уравнения $f(x) = 0$, и последовательность итераций метода Ньютона $x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$ безопасно сойдется к нему, не покидая $\Omega$. При этом сходимость обладает квадратичной скоростью при $h < 1/2$ (ошибка убывает пропорционально квадрату предыдущей) и может снижаться до линейной в граничном случае $h = 1/2$. Корень $x^*$ является единственным в пределах большей окрестности радиуса $t^{**} = \frac{1 + \sqrt{1 - 2h}}{h} \eta$ (при условии, что эта окрестность также лежит в $D$).

Интуиция: Теорема как статический анализатор (API Contracts)

В современной разработке для предотвращения катастроф во время выполнения используют статические анализаторы кода (вроде TypeScript, Rust compiler или линтеров). Они проверяют типы и контракты до запуска программы. В математике роль такого статического анализатора для метода Ньютона играет приведенная выше теорема (за работы в том числе в этой области Леонид Канторович позже получил Нобелевскую премию по экономике).

Чтобы «компиляция» прошла успешно, анализатор должен просто проверить три условия контракта. При этом анализатор работает «вслепую» относительно самого корня: он сопоставляет локальные данные только в одной стартовой точке $x_0$ (размер шага и наклон) с глобальным ограничением на кривизну ($M$) во всей зоне $D$.

Важнейший философский поинт теоремы Канторовича заключается в том, что это теорема существования. Анализатору не нужно знать, где находится корень и есть ли он вообще. Если начальные условия (шаг, наклон и кривизна) удовлетворяют контракту $h \le 1/2$, теорема математически гарантирует, что корень существует, и метод его обязательно найдет. Триггер $h \le 1/2$ просто говорит: «ваш стартовый шаг достаточно мал по сравнению с максимально возможной кривизной графика».

Правило $2\eta$ и SLA алгоритма. Теорема дает программистам блестящее инженерное «правило большого пальца»: истинный корень всегда лежит на расстоянии, не превышающем удвоенного первого шага ($t^* \le 2\eta$). Кроме того, анализатор прописывает жесткий SLA (Service Level Agreement): если запас прочности есть ($h < 1/2$), количество верных знаков ответа будет удваиваться на каждой итерации. И лишь в экстремальном краевом случае ($h = 1/2$) алгоритм деградирует до обычной линейной скорости.

Замечание про современный Deep Learning. В многомерном мире алгоритмы работают с системами уравнений: там вместо деления на производную используется обратная матрица Якоби, но общая логика сохраняется. Однако в мире современных нейросетей с миллиардами параметров, где функции потерь представляют собой дикие многомерные ландшафты, аналогов теореме Канторовича не найдено. У нас нет строгого математического «анализатора» для ChatGPT. Вместо формальной верификации ML-инженеры вынуждены опираться на эмпирические эвристики (градиентный клиппинг, адаптивный learning rate, оптимизаторы вроде Adam), инженерную интуицию и своего рода высокотехнологичное шаманство. Обучение современной нейросети — это прыжок в темноту с надеждой собрать парашют в полете.

Примечание: Доказательство теоремы Канторовича у меня получилось длинным, поэтому я его вынес в Часть 1 Приложение C. Анатомия квадратичной сходимости: Доказательство теоремы Канторовича в $R$

Пример: Зигзаг смерти и нарушение контрактов

Что бывает, если проигнорировать статический анализатор? Попробуем найти корень функции $f(x) = \arctan(x) = 0$. Очевидно, что истинный корень $x^* = 0$.

Производная арктангенса: $f'(x) = \frac{1}{1+x^2}$. Формула шага принимает вид: $x_{k+1} = x_k - (1+x_k^2)\arctan(x_k)$.

Если мы возьмем начальную точку $x_0 = 1.39$, метод стремительно сойдется к корню $x^* = 0$. Мы внутри безопасной зоны притяжения, условие Канторовича выполнено, маховик сходимости запущен, всё работает идеально.

Но стоит нам взять $x_0 = 1.40$, как происходит катастрофа. В этой точке график арктангенса уже начинает выполаживаться. Касательная становится слишком горизонтальной, производная падает (обратная величина $\beta$ становится слишком большой, а $h$ пробивает потолок в $1/2$). Триггер ломается на первом же шаге. Шаг становится больше, чем расстояние до корня: алгоритм перепрыгивает ноль и приземляется в точке с противоположным знаком, но еще дальше от нуля. На следующей итерации шаг будет еще шире.

Начинается расходимость, известная как «зигзаг смерти». Алгоритм будет бесконечно метаться влево-вправо, улетая в бесконечность. Это визуально и болезненно доказывает: любая красивая эвристика без проверки формальных контрактов — небезопасна.

Как современная ML-индустрия «чинит» эту проблему? Простейший способ предотвратить улет в бесконечность — искусственно ограничить длину шага, добавив множитель (Learning Rate, $\alpha \le 1$). Это гасит размах маятника и открывает дверь к целой вселенной квазиньютоновских методов и адаптивных оптимизаторов.

Undefined Behavior и Комплексная плоскость (Отключаем линтер)

В Приложении C (куда мы вынесли всю тяжелую математику) мы доказали работоспособность нашего статического анализатора для классической прямой действительных чисел $\mathbb{R}$. Там всё прозрачно: числа выстроены в ряд, работают операции «больше/меньше», а значит — работают графики, интегралы и дискриминанты.

Но что будет, если мы покинем эту уютную, математически доказанную песочницу? В комплексной плоскости $\mathbb{C}$ мы выходим в открытое 2D-поле, где направления спутались, и старая логика компараторов больше не применима. Давайте сделаем банальный каст типов от вещественных чисел (Float) к комплексным (Complex) и просто запустим нашу базовую формулу Ньютона z -= f(z)/f'(z) «на авось», полностью отключив линтер Канторовича. Мы вступаем в зону детерминированного хаоса, который для нашего статического анализатора выглядит как чистое Undefined Behavior.

Возьмем простейшее уравнение: $z^3 - 1 = 0$. В комплексной плоскости $\mathbb{C}$ у него ровно три корня (один вещественный $z=1$ и два комплексных). Представьте, что это три «сервера», к одному из которых должен подключиться наш алгоритм.

Интуиция Системы-1 подсказывает нам, что плоскость должна поделиться на три ровные, аккуратные зоны — бассейны притяжения (basins of attraction). Если мы стартуем близко к одному из корней, так оно и происходит — эвристика срабатывает, и метод мгновенно паркуется к ближайшему серверу. Но давайте раскрасим каждый стартовый пиксель $z_0$ на экране в цвет того корня, к которому в итоге пришел алгоритм, и посмотрим на границы этих зон.

Они не прямые. Они образуют Фрактал Ньютона — бесконечно сложную, психоделическую структуру, где цвета перемешаны в неразрешимую пыль. Если вы возьмете любую, даже микроскопическую область на границе этих цветов и увеличите её в миллиард раз, вы снова увидите все три цвета, переплетенные между собой.

В этой фрактальной зоне возникает математический аналог лавинного нарастания ошибки. Смещение вашей начальной догадки $z_0$ буквально на одну миллионную долю пикселя может радикально изменить итоговый корень. Детерминированный алгоритм становится вычислительно непредсказуемым. Вы никогда не знаете заранее, на каком «сервере» закончится вычисление.

Этот фрактал — это не просто красивая картинка. Это наглядный визуальный краш-дамп при жесточайшем стресс-тесте архитектуры итеративных методов. Он доказывает инженерам: «Вот как выглядит ваш продакшен, если вы просто берете красивую эвристическую формулу, выходите за пределы доказанной математической базы и надеетесь, что оно как-нибудь само сойдется». Чувствительность к начальным условиям превращает вычисления в хаос.

В будущих частях нашей серии мы увидим, как этот хаос масштабируется. Нам придется заново конструировать статические анализаторы для многомерных пространств $\mathbb{R}^n$ и абстрактных Банаховых миров. Ведь фракталы Ньютона в комплексной плоскости — это лишь 2D-превью того кошмара, который происходит в диких многомерных ландшафтах нейросетей ($\mathbb{R}^{10^9}$), где миллионы весов пытаются нащупать минимум Loss-функции.

Заключение Части 1 и мост в Machine Learning

Резюме: Kernel-level math

Давайте посмотрим, какой путь мы проделали. Мы начали с интуитивного «махания руками» — физики и геометрии, которые работают на уровне Системы-1, но ломаются в краевых случаях. Заменив касательную на Линейный Патч, инкапсулировав ошибку в форме Лагранжа в ряде Тейлора и прикрутив статический анализатор Канторовича, мы создали строгое, безопасное математическое ядро (Kernel-level). Этот алгоритм не просто «как-то работает», он аппаратно гарантирует результат.

Каст типов: Корни vs Оптимизация

Но подождите. На протяжении всей этой статьи мы решали задачу поиска корня: $f(x) = 0$. Однако в современном Machine Learning и Deep Learning мы почти никогда не ищем корни Loss-функции (идеальный нулевой Loss часто означает жесткий оверфиттинг или невозможен в принципе). В ML мы ищем минимум: $L(w) \to \min$, где $w$ — это веса нашей модели.

Как применить наш мощный метод Ньютона к задаче оптимизации? Нам нужен банальный «каст типов» (Type Casting). Вспомним теорему из базового матанализа: если в какой-то точке функция достигает локального экстремума (например, дна оврага) и дифференцируема в ней, то её первая производная в этой точке обязана быть равна нулю.

Строго говоря, обнуление производной дает нам лишь стационарную точку. Это только кандидат: точка может оказаться и локальным максимумом (вершиной холма), и коварной седловой точкой. В классическом матанализе, чтобы убедиться, что перед нами именно минимум, достаточно проверить поведение первой производной вокруг этой точки (если её знак меняется с минуса на плюс — мы на дне). Однако для численного алгоритма, «ослепшего» в конкретной координате, исследовать окрестности неудобно. Ему нужен мгновенный локальный инструмент — оценка кривизны прямо в точке (вторая производная). Но как бы мы ни проверяли статус точки в конце, базовая алгоритмическая задача минимизации $L(w) \to \min$ всегда сводится к одному: поиску корней первой производной, то есть решению уравнения $L'(w) = 0$.

Давайте возьмем нашу классическую формулу Ньютона $x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$ и просто подставим в нее вместо функции $f$ производную лосса $L'$. Что произойдет?

• Текущая позиция $x_k$ превратится в текущие веса $w_k$.
• Числитель $f(x_k)$ превратится в первую производную лосса $L'(w_k)$.
• А знаменатель $f'(x_k)$ (производная от производной) превратится во вторую производную лосса $L''(w_k)$ (в многомерном мире эта матрица кривизны называется Матрицей Гессе или Гессианом)!

Формула метода Ньютона для оптимизации (ML-версия) принимает вид:

$w_{k+1} = w_k - \frac{L'(w_k)}{L''(w_k)}$

Вот оно! Вторая производная (кривизна), которая раньше скромно сидела в остаточном члене Тейлора и служила лишь для оценки ошибки, теперь официально стала полноправной частью самого алгоритма. Она попала в знаменатель. И это изящно решает проблему слепоты алгоритма: именно вторая производная в знаменателе помогает ему «ощупать» пространство вокруг себя, понять, куда оно выгнуто (вверх или вниз), и скорректировать направление и размер шага.

В следующей части нашей серии мы масштабируем этот алгоритм на многомерные пространства $\mathbb{R}^n$, где миллионы весов нейросети заставят первую производную стать Градиентом, а вторую производную в знаменателе — исполинской Матрицей Гессе (Гессианом). Мы узнаем, почему метод Ньютона в ML — это снайперский выстрел, и почему железо (Hardware) до сих пор не позволяет нам использовать его в чистом виде для обучения GPT.

Вместо послесловия

«В классической математике метод Ньютона — это строго типизированный Rust, где компилятор Канторовича бьет по рукам за любую неточность. А современная оптимизация в Deep Learning (градиентный спуск) — это JavaScript: вместо идеального weights -= inverse(Hessian) * grad мы просто пишем weights -= lr * grad, игнорируем кривизну пространства, ловим NaN в седловых точках и молимся, чтобы костыли оптимизатора Adam (который, по сути, пытается дешево угадать диагональ этого Гессиана через дисперсию градиентов) как-нибудь сами всё разрулили».