Квадратичная сходимость

Квадратичная сходимость — это свойство итерационного алгоритма, при котором на каждом шаге количество верных значащих цифр приближённого решения примерно удваивается. В математическом анализе и вычислительной математике квадратичная сходимость считается одним из самых быстрых типов сходимости численных методов, уступая лишь более высоким порядкам (кубическому и выше). Формально последовательность {xₙ} сходится к пределу L квадратично, если существует константа C > 0, такая что для всех достаточно больших n выполняется неравенство |xₙ₊₁ − L| ≤ C · |xₙ − L|².

Определение и формализация

Сходимость численного метода характеризуется порядком сходимости p. Если последовательность {xₙ} сходится к L, и для некоторого p ≥ 1 существует предел

limₙ→∞ |xₙ₊₁ − L| / |xₙ − L|ᵖ = μ,

где 0 < μ < ∞, то говорят, что метод имеет порядок сходимости p. При p = 1 сходимость называется линейной, при p = 2 — квадратичной. Для квадратичной сходимости характерно, что ошибка на следующем шаге пропорциональна квадрату ошибки на текущем шаге: εₙ₊₁ ≈ C · εₙ², где εₙ = |xₙ − L|.

Ключевое следствие: если на некотором шаге погрешность составляет 10⁻ᵏ, то на следующем шаге она станет порядка 10⁻²ᵏ, то есть количество верных десятичных знаков удваивается. Например, при εₙ = 10⁻³ (три верных знака) после одного шага εₙ₊₁ ≈ 10⁻⁶ (шесть верных знаков).

Свойства и сравнение с другими порядками

Преимущества

• Быстрое уточнение: квадратичная сходимость требует значительно меньшего числа итераций по сравнению с линейной для достижения заданной точности. Например, метод Ньютона (квадратичная сходимость) обычно сходится за 5–10 итераций, тогда как метод простой итерации (линейная сходимость) может потребовать сотни шагов.
• Локальность: квадратичная сходимость обычно является локальной — она гарантируется только при достаточно хорошем начальном приближении, близком к истинному решению.

Недостатки

• Чувствительность к начальному приближению: при плохом выборе начальной точки метод может расходиться или сходиться к другому решению.
• Вычислительная стоимость: каждый шаг квадратично сходящегося метода (например, метода Ньютона) требует вычисления производной функции, что может быть дорого для сложных задач.

Сравнение с другими порядками

• Линейная сходимость (p = 1): ошибка уменьшается в геометрической прогрессии: εₙ₊₁ ≈ q·εₙ, где q < 1. Удвоение точности требует примерно log₂(1/q) итераций.
• Сверхлинейная сходимость (1 < p < 2): например, метод секущих имеет порядок p ≈ 1.618. Скорость выше линейной, но ниже квадратичной.
• Кубическая сходимость (p = 3): ещё быстрее, но редко встречается на практике из-за высокой вычислительной сложности.

Примеры методов с квадратичной сходимостью

Метод Ньютона (метод касательных)

Наиболее известный пример. Для решения уравнения f(x) = 0 итерационная формула: xₙ₊₁ = xₙ − f(xₙ)/f′(xₙ). При условии, что f′(x) ≠ 0 в окрестности корня и начальное приближение достаточно близко, метод сходится квадратично. Скорость сходимости определяется константой C = |f″(L)|/(2|f′(L)|).

Метод Ньютона для систем нелинейных уравнений

Обобщение на многомерный случай: xₙ₊₁ = xₙ − J⁻¹(xₙ)·F(xₙ), где J — матрица Якоби. При выполнении условий регулярности сходимость также квадратична.

Метод Герона (вавилонский метод) для извлечения квадратного корня

Для вычисления √a итерация: xₙ₊₁ = (xₙ + a/xₙ)/2. Это частный случай метода Ньютона для уравнения x² − a = 0, поэтому сходимость квадратичная.

Метод Халли

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

Метод Бройдена

Квазиньютоновский метод для систем уравнений, который при определённых условиях демонстрирует сверхлинейную, но не квадратичную сходимость.

Условия квадратичной сходимости

Для гарантии квадратичной сходимости метода Ньютона необходимо выполнение следующих условий:

1. Функция f(x) дважды непрерывно дифференцируема в окрестности корня L.
2. f′(L) ≠ 0 (корень простой, кратность 1).
3. Начальное приближение x₀ находится в достаточно малой окрестности L, где выполняется условие Липшица для второй производной.

Если корень кратный (f′(L) = 0), квадратичная сходимость теряется — метод Ньютона сходится линейно. Для восстановления квадратичной сходимости применяют модификации, например, метод Ньютона с учётом кратности.

Квадратичная сходимость в оптимизации

В задачах безусловной оптимизации квадратичная сходимость означает, что последовательность приближений к точке минимума x удовлетворяет ||xₙ₊₁ − x|| ≤ C·||xₙ − x*||². Методы второго порядка (ньютоновские) обладают этим свойством вблизи строгого локального минимума, где матрица Гессе положительно определена. Методы первого порядка (градиентный спуск) обычно имеют лишь линейную сходимость.

Пример численного расчёта

Рассмотрим метод Ньютона для уравнения x² − 2 = 0 (вычисление √2 ≈ 1.414213562). Начальное приближение x₀ = 2.0:

• Шаг 1: x₁ = (2 + 2/2)/2 = 1.5 (погрешность ≈ 0.0858)
• Шаг 2: x₂ = (1.5 + 2/1.5)/2 ≈ 1.4166667 (погрешность ≈ 0.00245)
• Шаг 3: x₃ = (1.4166667 + 2/1.4166667)/2 ≈ 1.4142157 (погрешность ≈ 2.1·10⁻⁶)
• Шаг 4: x₄ ≈ 1.414213562 (погрешность ≈ 1.6·10⁻¹²)

Видно, что за четыре итерации точность возросла с 1 знака до 12 знаков — характерный признак квадратичной сходимости.

Ограничения и критика

• Локальность: квадратичная сходимость гарантирована только вблизи решения. Для глобальной сходимости требуются дополнительные меры (линейный поиск, демпфирование).
• Вычислительная сложность: каждый шаг требует вычисления производной (или матрицы Якоби), что может быть дорого для задач большой размерности.
• Чувствительность к ошибкам округления: при очень малых погрешностях (менее машинного эпсилон) квадратичная сходимость может не наблюдаться из-за ограниченной точности чисел с плавающей запятой.
• Неприменимость к разрывным функциям: метод Ньютона и другие квадратично сходящиеся методы требуют гладкости функции.

Применение

Квадратичная сходимость широко используется в:

• Численном решении нелинейных уравнений и систем (метод Ньютона, метод Гаусса — Ньютона для задач наименьших квадратов).
• Оптимизации (метод Ньютона, метод Левенберга — Марквардта).
• Обратных задачах и машинном обучении (обучение нейронных сетей с использованием методов второго порядка, хотя на практике чаще применяют стохастические методы первого порядка).
• Вычислительной физике и химии (расчёт равновесных состояний, молекулярная динамика).

Источники

1. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — М.: Бином. Лаборатория знаний, 2008.
2. Самарский А. А., Гулин А. В. Численные методы. — М.: Наука, 1989.
3. Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. — М.: Мир, 1975.
4. Калиткин Н. Н. Численные методы. — М.: Наука, 1978.
5. Дэннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. — М.: Мир, 1988.