Англоязычная версия данной заметки доступна здесь 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$, для которой выполняются следующие условия:
- Начальный шаг ограничен: $|\Delta x_0| = \left| \frac{f(x_0)}{f'(x_0)} \right| \le \eta$
- Модуль обратной величины первой производной в начальной точке ограничен: $\left| \frac{1}{f'(x_0)} \right| \le \beta$. (Именно такая формулировка позволит нам в будущем бесшовно заменить число в знаменателе на норму обратной матрицы Якоби или Гессе в многомерном мире).
- Модуль второй производной (кривизна) ограничен сверху: $|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). Ч.т.д.
No comments:
Post a Comment