Вычислительная устойчивость

В вычислительной математике вычислительная устойчивость является обычно желательным свойством численных алгоритмов.

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

В численной линейной алгебре основной проблемой являются нестабильности, вызванные близостью к различным особенностям, таким как очень малые или почти совпадающие собственные значения.

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

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

Противоположным явлением является неустойчивость. Как правило, алгоритм включает в себя приближённый метод, и в некоторых случаях можно доказать, что алгоритм будет приближаться к правильному решению в некотором пределе (при использовании на самом деле действительных чисел, а не чисел с плавающей запятой).

Даже в этом случае нет гарантии, что он будет сходиться к правильному решению, потому что ошибки округления или усечения с плавающей точкой могут расти, а не уменьшаться, что приведёт к экспоненциальному росту отклонения от точного решения.^[1]

Устойчивость в численных методах линейной алгебры

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

Рассмотрим задачу, решаемую численным алгоритмом, как функцию f, отображающую данные x в решение y. Результат алгоритма, скажем, y*, обычно будет отклоняться от «истинного» решения y. Основными причинами ошибки являются ошибки округления и ошибки усечения^[en]. Прямая ошибка алгоритма — это разница между результатом и решением; в этом случае Δy = y* − y. Обратная ошибка является наименьшей Δx такой, что f (x + Δx) = y*; другими словами, обратная ошибка говорит нам, какую проблему на самом деле решил алгоритм. Прямая и обратная ошибки связаны числом обусловленности: прямая ошибка не более велика по величине, чем число обусловленности, умноженное на величину обратной ошибки.

Во многих случаях более естественно^{[уточнить]} учитывать относительную ошибку

${\displaystyle {\frac {|\Delta x|}{|x|}}}$

вместо абсолютной Δx.

• Алгоритм называется обратно устойчивым, если обратная ошибка мала для всех входов x.

Конечно, «малый» — это относительный термин, и его определение будет зависеть от контекста. Часто мы хотим, чтобы ошибка была того же порядка, или, возможно, на несколько порядков больше, чем единица округления.

Обычное определение вычислительной устойчивости использует более общую концепцию, называемую смешанной устойчивостью, которая объединяет прямую ошибку и обратную ошибку. Алгоритм в этом смысле устойчив, если он приблизительно решает соседнюю задачу, то есть если существует такое Δx, что и Δx мало, и f (x + Δx) − y* мала. Следовательно, обратно устойчивый алгоритм всегда устойчив.

• Алгоритм является устойчивым в прямом направлении, если его прямая ошибка, деленная на число обусловленности задачи, мала.

Это означает, что алгоритм является устойчивым в прямом направлении, если он имеет прямую ошибку величины, аналогичную обратной ошибке некоторого устойчивого алгоритма.

Устойчивость разностных схем дифференциальных уравнений

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

В численных обыкновенных дифференциальных уравнениях существуют различные понятия численной устойчивости, например, A-устойчивость^[en]. При решении жесткого уравнения важно использовать устойчивый метод.

Ещё одно определение используется в численных уравнениях в частных производных. Алгоритм решения линейного эволюционного уравнения в частных производных является устойчивым, если полная вариация численного решения в фиксированное время остается ограниченной, когда размер шага приближается к нулю. Теорема эквивалентности Лакса^[en] утверждает, что алгоритм сходится, если он согласован и устойчив (в этом смысле). Устойчивость иногда достигается путем включения численной диффузии^[en]. Численная диффузия — это математический термин, который гарантирует, что округление и другие ошибки в вычислениях распространяются и не суммируются, чтобы привести к «взрыву» вычислений. Анализ устойчивости по Нейману^[en] является широко используемой процедурой для анализа устойчивости конечно-разностных схем применительно к линейным уравнениям в частных производных. Эти результаты не выполняются для нелинейных уравнений в частных производных, где общее непротиворечивое определение устойчивости усложняется многими свойствами, отсутствующими в линейных уравнениях.

См. также

• Число обусловленности
• Плавающая запятая
• Фиксированная запятая

Примечания

Литература

• Е. А. Волков. Численные методы. — М.: Наука, 1987. — 248 с. — 36 000 экз.
• А. А. Самарский, А. В. Гулин. Численные методы. — М.: Наука, 1989. — 432 с.
• Lloyd N. Trefethen. Finite Difference and Spectral Methods for Ordinary and Partial Differential Equations (англ.). — 1996.

Эта страница в последний раз была отредактирована 31 июля 2023 в 00:14.