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

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

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

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

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

Определение

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

Вычислительную устойчивость, например, решения системы уравнений, можно определить следующим образом: допустим мы решили систему уравнения относительно $x_{1},...,x_{n}$, то есть нашли решение $P(x_{1},...,x_{n})$. Если мы незначительно изменим значения на $x_{1}',...,x_{n}'$, то новое решение $P'(x_{1}',...,x_{n}')$ должно быть в некоторой метрике близким к решению $P(x_{1},...,x_{n})$.

Пример 1: система уравнений

Дана система двух линейных уравнений: $\left\{{\begin{matrix}u+10v=11\\100u+1001v=1101\end{matrix}}\right.$

Решением является пара чисел $\left\{{1;1}\right\}.$

«Возмутим» правую часть первого уравнения на 0,01 (вместо 11 напишем 11,01) и получим новую, «возмущённую» систему, решением которой является пара чисел {11,01; 0,00}, не имеющая ничего общего с решением невозмущённой системы. Здесь изменение значения одного параметра меньше чем на $0,\!1\%$ привело к совсем другому решению.

См. также

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