Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . ( Февраль 2012 г. ) |
В математическом подполе численного анализа , устойчивость численная является в целом желательным свойством численных алгоритмов . Точное определение стабильности зависит от контекста. Один из них - это числовая линейная алгебра, а другой - алгоритмы решения обыкновенных дифференциальных уравнений и уравнений в частных производных с помощью дискретной аппроксимации.
В числовой линейной алгебре основной проблемой являются нестабильности, вызванные близостью к особенностям различного типа, таким как очень малые или почти совпадающие собственные значения . С другой стороны, в численных алгоритмах для дифференциальных уравнений проблема заключается в росте ошибок округления и / или небольших флуктуаций исходных данных, которые могут вызвать большое отклонение окончательного ответа от точного решения. [ необходима цитата ]
Некоторые численные алгоритмы могут подавлять небольшие колебания (ошибки) во входных данных; другие могут преувеличивать такие ошибки. Расчеты, которые, как можно доказать, не увеличивают погрешности аппроксимации, называются численно стабильными . Одна из распространенных задач численного анализа - попытаться выбрать алгоритмы, которые являются надежными, то есть не дают сильно отличающегося результата при очень небольшом изменении входных данных.
Противоположное явление неустойчивости . Как правило, алгоритм включает приближенный метод, и в некоторых случаях можно доказать, что алгоритм приблизится к правильному решению в некотором пределе (при использовании реальных действительных чисел, а не чисел с плавающей запятой). Даже в этом случае нет гарантии, что оно сойдется к правильному решению, потому что ошибки округления с плавающей запятой или усечения могут быть увеличены, а не затухают, вызывая экспоненциальный рост отклонения от точного решения. [1]
Есть разные способы формализовать понятие устойчивости. Следующие определения прямой, обратной и смешанной устойчивости часто используются в числовой линейной алгебре .
Рассмотрим задачу, решаемую численным алгоритмом, как функцию f, отображающую данные x в решение y . Результат алгоритма, скажем y *, обычно будет отклоняться от «истинного» решения y . Основные причины ошибок являются ошибками округления и усечения ошибок . Вперед ошибки алгоритма представляет собой разность между результатом и решением; в этом случае Δ y = y * - y . Назад , ошибка является наименьшим Δ х таким образом, что F ( х+ Δ x ) = y * ; Другими словами, обратная ошибка говорит нам, какую проблему на самом деле решил алгоритм. Прямая и обратная ошибка связаны с помощью номера условия : прямая ошибка по величине не больше, чем номер условия, умноженный на величину обратной ошибки.
Во многих случаях более естественно рассматривать относительную погрешность
вместо абсолютной ошибки Δ x .
Алгоритм считается обратно устойчивым, если обратная ошибка мала для всех входов x . Конечно, «маленький» - понятие относительное, и его определение будет зависеть от контекста. Часто мы хотим, чтобы ошибка была того же порядка, или, возможно, только на несколько порядков больше, чем округление единицы .
Обычное определение числовой устойчивости использует более общую концепцию, называемую смешанной стабильностью , которая объединяет прямую ошибку и обратную ошибку. Алгоритм в этом смысле устойчив, если он решает близкую задачу приближенно, т. Е. Если существует Δ x такое, что как Δ x мало, так и f ( x + Δ x ) - y * мало. Следовательно, обратный стабильный алгоритм всегда стабилен.
Алгоритм является стабильным в прямом направлении, если его прямая ошибка, деленная на число обусловленности проблемы, мала. Это означает, что алгоритм является стабильным в прямом направлении, если он имеет прямую ошибку величины, подобную некоторому алгоритму обратной устойчивости.
Приведенные выше определения особенно актуальны в ситуациях, когда ошибки усечения не важны. В других контекстах, например, при решении дифференциальных уравнений , используется другое определение числовой устойчивости.
В числовых обыкновенных дифференциальных уравнениях существуют различные концепции числовой устойчивости, например A-устойчивость . Они связаны с некоторым понятием устойчивости в смысле динамических систем , часто с устойчивостью по Ляпунову . При решении жесткого уравнения важно использовать устойчивый метод .
Еще одно определение используется в численных уравнениях в частных производных . Алгоритм решения линейного эволюционного уравнения в частных производных является устойчивым, если полное изменение численного решения в фиксированное время остается ограниченным, поскольку размер шага стремится к нулю. Теорема эквивалентности Лакса утверждает, что алгоритм сходится, если он непротиворечив и устойчив (в этом смысле). Стабильность иногда достигается за счет численного распространения . Числовая диффузия - это математический термин, который гарантирует, что округление и другие ошибки в расчетах будут разбросаны, а не суммируются, чтобы вызвать «взрыв» расчета.Анализ устойчивости фон Неймана - это обычно используемая процедура для анализа устойчивости конечно-разностных схем применительно к линейным уравнениям в частных производных. Эти результаты не верны для нелинейных УЧП, где общее согласованное определение устойчивости осложняется многими свойствами, отсутствующими в линейных уравнениях.