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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Примечания

  1. Giesela Engeln-Müllges. : [ англ. ] / Giesela Engeln-Müllges, Frank Uhlig. — 1. — Springer, 2 July 1996. — P. 10. — ISBN 978-3-540-60530-0 . . Дата обращения: 13 декабря 2018. Архивировано 19 августа 2020 года.

Литература

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

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