Введение

Способность численных алгоритмов сохранять точность при малых изменениях входных данных.

В математической области численного анализа, численная устойчивость является обычно желаемым свойством численных алгоритмов. Точное определение устойчивости зависит от контекста. Одним из контекстов является численный линейный анализ, а другим – алгоритмы решения обыкновенных и частных дифференциальных уравнений методом дискретных приближений. В численном линейном анализе основная проблема – неустойчивость, вызванная близостью к сингулярностям различного рода, таким как очень малые или почти совпадающие собственные значения. С другой стороны, в численных алгоритмах для дифференциальных уравнений беспокойство вызывает рост ошибок округления и/или небольших флуктуаций в начальных данных, которые могут привести к значительному отклонению конечного результата от точного решения. Некоторые численные алгоритмы могут подавлять небольшие флуктуации (ошибки) во входных данных, другие же могут усиливать такие ошибки. Вычисления, которые можно доказать, что не увеличивают ошибки приближения, называются численно устойчивыми. Одной из распространенных задач численного анализа является попытка выбора устойчивых алгоритмов – то есть, алгоритмов, которые не дают сильно отличающихся результатов при незначительных изменениях входных данных. Противоположным явлением является неустойчивость. Как правило, алгоритм включает в себя приближенный метод, и в некоторых случаях можно доказать, что алгоритм стремится к правильному решению в некотором пределе (при использовании действительных чисел, а не чисел с плавающей точкой). Даже в этом случае нет гарантии, что он сойдется к правильному решению, поскольку ошибки округления или усечения с плавающей точкой могут быть усилены, а не подавлены, что приведет к экспоненциальному росту отклонения от точного решения.

Стабильность в численной линейной алгебре

Существуют различные способы формализации концепции устойчивости. Следующие определения прямой, обратной и смешанной устойчивости часто используются в численной линейной алгебре. Рассмотрим задачу, решаемую численным алгоритмом, как функцию f, отображающую входные данные x в решение y. Результат алгоритма, обозначим его y*, обычно отличается от "точного" решения y. Основными источниками ошибок являются ошибки округления и ошибки усечения. Прямая ошибка алгоритма – это разность между полученным результатом и точным решением; в этом случае Δy = y* − y. Обратная ошибка – это наименьшее Δx, такое что f(x + Δx) = y*; другими словами, обратная ошибка показывает, какую задачу алгоритм фактически решил. Прямая и обратная ошибки связаны числом обусловленности: прямая ошибка по величине не превышает число обусловленности, умноженное на величину обратной ошибки. Во многих случаях более естественно рассматривать относительную ошибку вместо абсолютной ошибки Δx. Алгоритм считается обратно устойчивым, если обратная ошибка мала для всех входных данных x. Конечно, "малая" величина – понятие относительное, и ее определение зависит от контекста. Часто требуется, чтобы ошибка была того же порядка, или, возможно, лишь на несколько порядков величины больше, чем единица округления. Обычно определение численной устойчивости использует более общую концепцию, называемую смешанной устойчивостью, которая объединяет прямую и обратную ошибки. Алгоритм считается устойчивым в этом смысле, если он приближенно решает близкую задачу, то есть существует Δx, такое что и Δx мало, и f(x + Δx) − y* мало. Следовательно, обратно устойчивый алгоритм всегда устойчив. Алгоритм считается прямо устойчивым, если его прямая ошибка, деленная на число обусловленности задачи, мала. Это означает, что алгоритм прямо устойчив, если его прямая ошибка имеет величину, сопоставимую с прямой ошибкой некоторого обратно устойчивого алгоритма.

Стабильность в числовых дифференциальных уравнениях

Вышеуказанные определения особенно важны в ситуациях, когда погрешности усечения несущественны. В других контекстах, например, при решении дифференциальных уравнений, используется иное определение численной устойчивости. В области численных методов решения обыкновенных дифференциальных уравнений существует несколько понятий численной устойчивости, например, A-устойчивость. Они связаны с понятием устойчивости в теории динамических систем, часто с устойчивостью по Ляпунову. При решении жестких уравнений важно использовать устойчивый метод. Другое определение применяется в численных методах решения уравнений в частных производных. Алгоритм решения линейного эволюционного уравнения в частных производных считается устойчивым, если полная вариация численного решения в фиксированный момент времени остается ограниченной при стремлении размера шага к нулю. Теорема эквивалентности Лакса утверждает, что алгоритм сходится, если он является согласованным и устойчивым (в этом смысле). Устойчивость иногда достигается за счет введения численной диффузии. Численная диффузия – это математический термин, обеспечивающий рассеивание ошибок округления и других ошибок в вычислениях, предотвращая их накопление и приводящее к "взрыву" решения. Анализ устойчивости по фон Нейману – широко используемая процедура для анализа устойчивости конечно-разностных схем, применяемых к линейным уравнениям в частных производных. Эти результаты не применимы к нелинейным уравнениям в частных производных, где общее, непротиворечивое определение устойчивости усложняется множеством свойств, отсутствующих в линейных уравнениях.