🔢 Численные методы

Порядок сходимости

Q: Чем квадратичная сходимость лучше линейной?

Структурой ускорения. При линейной сходимости ошибка умножается на постоянную $q < 1$: чтобы добавить один верный знак, нужна фиксированная серия шагов, например пять при $q = 0.1$. При квадратичной число верных знаков удваивается: с ошибки $0.1$ метод проходит $0.01$, $10^{-4}$, $10^{-8}$ — три шага вместо восьми. Поэтому у Ньютона последние итерации почти бесплатны: дорого стоят первые, когда ошибка ещё крупная и квадрат работает против метода.

Q: Может ли порядок сходимости обмануть?

Да, если смотреть только на показатель $p$ и забыть про константу $C$. Квадратичный метод с большой константой на ранних шагах может проигрывать линейному — квадратичность проявляется вблизи корня, когда произведение $C e_k$ стало меньше единицы. Вторая ловушка — кратные корни: у Ньютона там порядок падает до линейного. Третья — оценка по факту: реальный порядок проверяют отношениями $\ln e_{k+1}/\ln e_k$ по экспериментальным ошибкам, и он может отличаться от паспортного.

англ. Order of convergence

Скорость таяния ошибки итераций: при порядке p новая ошибка примерно C·e_k^p, от линейного умножения на q < 1 до квадратичного удвоения числа верных знаков у Ньютона.

Вклад под процент, только наоборот: ошибка не растёт, а тает, и порядок сходимости — ставка, под которую идёт таяние. Формально для приближений $x_{k}$ с ошибками $e_{k} = ∣ x_{k} - x^{*} ∣$ порядок $p$ — число, при котором $e_{k + 1} \approx C e_{k}^{p}$ . При $p = 1$ (линейная сходимость) ошибка умножается за шаг на постоянную $q < 1$ , при $p = 2$ (квадратичная) — возводится в квадрат с коэффициентом. Порядок — паспорт метода: он предсказывает, сколько итераций прожить до заданной точности, ещё до всякого запуска программы.

Числа вместо слов. Линейный метод с $q = 1/2$ : ошибки $0.1 \to 0.05 \to 0.025$ — один новый верный знак за каждые три шага. Квадратичный метод Ньютона: $0.1 \to 0.01 \to 0.0001$ — верные знаки удваиваются, и последние итерации стоят почти ничего. Между ними — сверхлинейная сходимость метода секущих с показателем около $1.618$ , золотого сечения. Ловушка: порядок привязан к корню — у Ньютона у простого корня он квадратичный, а у кратного сползает до линейного с $q = 1 - 1/ m$ . Как не растерять заработанные знаки при счёте, объясняют источники погрешностей, а где порядок решает судьбу расчёта — материал решение нелинейных уравнений; потрогать скорости руками можно в тренажёре численных методов.

k \to \infty lim \frac{ln e _{k + 1}}{ln e _{k}} = p, e_{k + 1} \approx C e_{k}^{p}

порядок сходимости по логарифмам ошибок; у Ньютона у простого корня

p = 2

: ошибки

0.1 \to 0.01 \to 0.0001

— верные знаки удваиваются за шаг

Частые вопросы

Чем квадратичная сходимость лучше линейной?

Структурой ускорения. При линейной сходимости ошибка умножается на постоянную $q < 1$ : чтобы добавить один верный знак, нужна фиксированная серия шагов, например пять при $q = 0.1$ . При квадратичной число верных знаков удваивается: с ошибки $0.1$ метод проходит $0.01$ , $1 0^{- 4}$ , $1 0^{- 8}$ — три шага вместо восьми. Поэтому у Ньютона последние итерации почти бесплатны: дорого стоят первые, когда ошибка ещё крупная и квадрат работает против метода.

Может ли порядок сходимости обмануть?

Да, если смотреть только на показатель $p$ и забыть про константу $C$ . Квадратичный метод с большой константой на ранних шагах может проигрывать линейному — квадратичность проявляется вблизи корня, когда произведение $C e_{k}$ стало меньше единицы. Вторая ловушка — кратные корни: у Ньютона там порядок падает до линейного. Третья — оценка по факту: реальный порядок проверяют отношениями $ln e_{k + 1} / ln e_{k}$ по экспериментальным ошибкам, и он может отличаться от паспортного.