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

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

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

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

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

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

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

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

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

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

Диаграмма, показывающая прямую ошибку Δy и обратную ошибку Δx, и их соотношение с точным решением отображения f и численного решения f*.

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

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

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

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

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

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

Смешанная устойчивость комбинирует понятия прямой и обратной ошибки.

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

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

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

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

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

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

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

См. также

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

Литература

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