Русская Википедия:Вычислительная устойчивость
В вычислительной математике вычислительная устойчивость является обычно желательным свойством численных алгоритмов.
Точное определение устойчивости зависит от контекста. Один из них — численная линейная алгебра, другой — алгоритмы решения обыкновенных уравнений и дифференциальных уравнений в частных производных с помощью дискретного приближения.
В численной линейной алгебре основной проблемой являются нестабильности, вызванные близостью к различным особенностям, таким как очень малые или почти совпадающие собственные значения.
С другой стороны, в численных алгоритмах для дифференциальных уравнений проблема заключается в увеличении ошибок округления и/или изначально небольших флуктуаций в исходных данных, которые могут привести к значительному отклонению окончательного ответа от точного решения.
Некоторые численные алгоритмы могут ослаблять небольшие отклонения (ошибки) во входных данных; другие могут увеличить такие ошибки. Расчёты, которые, как можно доказать, не увеличивают ошибки аппроксимации, называются вычислительно устойчивыми. Одна из распространённых задач численного анализа — попытаться выбрать надёжные алгоритмы, то есть не дать сильно отличающийся результат при очень небольшом изменении входных данных.
Противоположным явлением является неустойчивость. Как правило, алгоритм включает в себя приближённый метод, и в некоторых случаях можно доказать, что алгоритм будет приближаться к правильному решению в некотором пределе (при использовании на самом деле действительных чисел, а не чисел с плавающей запятой).
Даже в этом случае нет гарантии, что он будет сходиться к правильному решению, потому что ошибки округления или усечения с плавающей точкой могут расти, а не уменьшаться, что приведёт к экспоненциальному росту отклонения от точного решения.[1]
Устойчивость в численных методах линейной алгебры
Существуют разные способы формализации концепции устойчивости. Следующие определения прямой, обратной и смешанной устойчивости часто используются в численной линейной алгебре.
Рассмотрим задачу, решаемую численным алгоритмом, как функцию Шаблон:Mvar, отображающую данные Шаблон:Mvar в решение Шаблон:Mvar. Результат алгоритма, скажем, Шаблон:Mvar, обычно будет отклоняться от «истинного» решения Шаблон:Mvar. Основными причинами ошибки являются ошибки округления и Шаблон:Iw. Прямая ошибка алгоритма — это разница между результатом и решением; в этом случае Шаблон:Math. Обратная ошибка является наименьшей ΔШаблон:Mvar такой, что Шаблон:Math; другими словами, обратная ошибка говорит нам, какую проблему на самом деле решил алгоритм. Прямая и обратная ошибки связаны числом обусловленности: прямая ошибка не более велика по величине, чем число обусловленности, умноженное на величину обратной ошибки.
Во многих случаях более естественноШаблон:Уточнить учитывать относительную ошибку
- <math> \frac{|\Delta x|}{|x|} </math>
вместо абсолютной ΔШаблон:Mvar.
- Алгоритм называется обратно устойчивым, если обратная ошибка мала для всех входов Шаблон:Mvar.
Конечно, «малый» — это относительный термин, и его определение будет зависеть от контекста. Часто мы хотим, чтобы ошибка была того же порядка, или, возможно, на несколько порядков больше, чем единица округления.
Обычное определение вычислительной устойчивости использует более общую концепцию, называемую смешанной устойчивостью, которая объединяет прямую ошибку и обратную ошибку. Алгоритм в этом смысле устойчив, если он приблизительно решает соседнюю задачу, то есть если существует такое ΔШаблон:Mvar, что и ΔШаблон:Mvar мало, и Шаблон:Math мала. Следовательно, обратно устойчивый алгоритм всегда устойчив.
- Алгоритм является устойчивым в прямом направлении, если его прямая ошибка, деленная на число обусловленности задачи, мала.
Это означает, что алгоритм является устойчивым в прямом направлении, если он имеет прямую ошибку величины, аналогичную обратной ошибке некоторого устойчивого алгоритма.
Устойчивость разностных схем дифференциальных уравнений
Шаблон:Переписать раздел Приведенные выше определения особенно актуальны в ситуациях, когда ошибки усечения не важны. В других контекстах, например, при решении дифференциальных уравнений, используется другое определение численной устойчивости.
В численных обыкновенных дифференциальных уравнениях существуют различные понятия численной устойчивости, например, Шаблон:Iw. При решении жесткого уравнения важно использовать устойчивый метод.
Ещё одно определение используется в численных уравнениях в частных производных. Алгоритм решения линейного эволюционного уравнения в частных производных является устойчивым, если полная вариация численного решения в фиксированное время остается ограниченной, когда размер шага приближается к нулю. Шаблон:Iw утверждает, что алгоритм сходится, если он согласован и устойчив (в этом смысле). Устойчивость иногда достигается путем включения Шаблон:Iw. Численная диффузия — это математический термин, который гарантирует, что округление и другие ошибки в вычислениях распространяются и не суммируются, чтобы привести к «взрыву» вычислений. Шаблон:Iw является широко используемой процедурой для анализа устойчивости конечно-разностных схем применительно к линейным уравнениям в частных производных. Эти результаты не выполняются для нелинейных уравнений в частных производных, где общее непротиворечивое определение устойчивости усложняется многими свойствами, отсутствующими в линейных уравнениях.
См. также
Примечания
Литература
