Численная стабильность

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

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

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

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

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

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

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

Во многих случаях более естественно рассматривать относительную погрешность ${\frac {|\Delta x|}{|x|}}$ вместо абсолютной ошибки $Δ x$ .

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

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

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

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

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

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

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

Пример

Вычисление квадратного корня из 2 (что примерно равно 1,41421) является корректной задачей . Многие алгоритмы решают эту проблему, начиная с начального приближения x ₀ до ${\sqrt {2}}$ , например x ₀ = 1,4, а затем вычисление улучшенных предположений x ₁ , x ₂ и т. д. Одним из таких методов является знаменитый вавилонский метод , который задается формулой x _{k +1} = ( x _k + 2/ x _k )/2 . Другой метод, называемый «методом X», определяется выражением x _{k +1} = ( x _k² − 2) ² + х _к . ^{[примечание 1]} Несколько итераций каждой схемы рассчитаны в виде таблицы ниже с начальными предположениями x ₀ = 1,4 и x ₀ = 1,42.

вавилонский	вавилонский	Метод Х	Метод Х
х ₀ = 1,4	х ₀ = 1,42	х ₀ = 1,4	х ₀ = 1,42
х ₁ = 1,4142857...	х ₁ = 1,41422535...	х ₁ = 1,4016	х ₁ = 1,42026896
х ₂ = 1,414213564...	х ₂ = 1,41421356242...	х ₂ = 1,4028614...	х ₂ = 1,42056...
		...	...
		х _1000000 = 1,41421...	х ₂₇ = 7280,2284...

Обратите внимание, что вавилонский метод сходится быстро независимо от первоначального предположения, тогда как метод X сходится чрезвычайно медленно с начальным предположением x ₀ = 1,4 и расходится для начального предположения x ₀ = 1,42. Следовательно, вавилонский метод численно стабилен, а метод X численно нестабилен.

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

f(x)=x\left({\sqrt {x+1}}-{\sqrt {x}}\right)

и

g(x)={\frac {x}{{\sqrt {x+1}}+{\sqrt {x}}}}.

Сравнивая результаты

f(500)=500\left({\sqrt {501}}-{\sqrt {500}}\right)=500\left(22.38-22.36\right)=500(0.02)=10

и

{\begin{alignedat}{3}g(500)&={\frac {500}{{\sqrt {501}}+{\sqrt {500}}}}\\&={\frac {500}{22.38+22.36}}\\&={\frac {500}{44.74}}=11.17\end{alignedat}}

Сравнивая два приведенных выше результата, становится ясно, что потеря значимости (вызванная здесь катастрофической отменой из-за вычитания приближений к близлежащим числам) ${\sqrt {501}}$ и ${\sqrt {500}}$ , несмотря на то, что вычитание вычисляется точно) оказывает огромное влияние на результаты, хотя обе функции эквивалентны, как показано ниже.

{\begin{alignedat}{4}f(x)&=x\left({\sqrt {x+1}}-{\sqrt {x}}\right)\\&=x\left({\sqrt {x+1}}-{\sqrt {x}}\right){\frac {{\sqrt {x+1}}+{\sqrt {x}}}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&=x{\frac {({\sqrt {x+1}})^{2}-({\sqrt {x}})^{2}}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&=x{\frac {x+1-x}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&=x{\frac {1}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&={\frac {x}{{\sqrt {x+1}}+{\sqrt {x}}}}\\&=g(x)\end{alignedat}}

Желаемое значение, вычисленное с бесконечной точностью, составляет 11,174755... ^{[примечание 2]}

См. также

Примечания

^ Это итерация с фиксированной точкой для уравнения $x=(x^{2}-2)^{2}+x=f(x)$ , решения которого включают ${\sqrt {2}}$ . Итерации всегда перемещаются вправо, поскольку $f(x)\geq x$ . Следовательно $x_{1}=1.4<{\sqrt {2}}$ сходится и $x_{1}=1.42>{\sqrt {2}}$ расходится.
^ Пример представляет собой модификацию примера, взятого из Mathews & Fink (1999) . ^[2]

Ссылки

^ Гизела Энгельн-Мюлльгес; Фрэнк Улиг (2 июля 1996 г.). Численные алгоритмы с C. М. Шон (переводчик), Ф. Улиг (переводчик) (1-е изд.). Спрингер. п. 10. ISBN 978-3-540-60530-0 .
^ Мэтьюз, Джон Х.; Финк, Куртис Д. (1999). «Пример 1.17». Численные методы с использованием MATLAB (3-е изд.). Прентис Холл. п. 28.

Николас Дж. Хайэм (1996). Точность и устойчивость численных алгоритмов . Филадельфия: Общество промышленной и прикладной математики. ISBN 0-89871-355-2 .
Ричард Л. Берден; Дж. Дуглас Фейрес (2005). Численный анализ (8-е изд.). США: Томсон Брукс/Коул. ISBN 0-534-39200-8 .
Меснар, Оливье; Барба, Лорена А. (2017). «Воспроизводимая и воспроизводимая вычислительная гидродинамика: это сложнее, чем вы думаете». Вычисления в науке и технике . 19 (4): 44–55. arXiv : 1605.04339 . Бибкод : 2017CSE....19d..44M . дои : 10.1109/MCSE.2017.3151254 . S2CID 11288122 .

[2] Это итерация с фиксированной точкой для уравнения $x=(x^{2}-2)^{2}+x=f(x)$ , решения которого включают ${\sqrt {2}}$ . Итерации всегда перемещаются вправо, поскольку $f(x)\geq x$ . Следовательно $x_{1}=1.4<{\sqrt {2}}$ сходится и $x_{1}=1.42>{\sqrt {2}}$ расходится.

[4] Пример представляет собой модификацию примера, взятого из Mathews & Fink (1999) . ^[2]

[1] Гизела Энгельн-Мюлльгес; Фрэнк Улиг (2 июля 1996 г.). Численные алгоритмы с C. М. Шон (переводчик), Ф. Улиг (переводчик) (1-е изд.). Спрингер. п. 10. ISBN 978-3-540-60530-0 .

[3] Мэтьюз, Джон Х.; Финк, Куртис Д. (1999). «Пример 1.17». Численные методы с использованием MATLAB (3-е изд.). Прентис Холл. п. 28.

[1]

[примечание 1]

[примечание 2]

[2]

v т и Линейная алгебра
Контур Глоссарий
Основные понятия	Скаляр Вектор Векторное пространство Скалярное умножение Векторная проекция Линейный пролет Линейная карта Линейная проекция Линейная независимость Линейная комбинация Многолинейная карта Основа Изменение базы Векторы-строки и столбцы Пространства строк и столбцов Ядро Собственные значения и собственные векторы Транспонировать Линейные уравнения
Матрицы	Блокировать Разложение Обратимый Незначительный Умножение Классифицировать Трансформация Правило Крамера Исключение по Гауссу
Билинейный	Ортогональность Скалярное произведение Произведение Адамара Внутреннее пространство продукта Внешний продукт Продукт Кронекера Процесс Грама – Шмидта
Полилинейная алгебра	Определитель Перекрестное произведение Тройной продукт Семимерное векторное произведение Геометрическая алгебра Внешняя алгебра Бивектор Многовекторный Тензор Аутэрморфизм
Векторные космические конструкции	Двойной Прямая сумма Функциональное пространство частное Подпространство Тензорное произведение
Числовой	Плавающая точка Численная стабильность Основные подпрограммы линейной алгебры Разреженная матрица Сравнение библиотек линейной алгебры
Категория