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

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

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

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

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

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

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

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

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

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

Во многих случаях более естественно рассматривать относительную погрешность

$${\displaystyle {\frac {|\Delta x|}{|x|}}}$$

Δ x

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

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

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

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

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

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

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

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

Пример

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

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

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

${\displaystyle f(x)=x\left({\sqrt {x+1}}-{\sqrt {x}}\right)}$и ${\displaystyle g(x)={\frac {x}{{\sqrt {x+1}}+{\sqrt {x}}}}.}$

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

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

и

${\displaystyle {\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}}}$

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

${\displaystyle {\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]}

Смотрите также

• Алгоритмы расчета дисперсии
• Теория стабильности
• Теория хаоса
• Распространение неопределенности

Примечания

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

Рекомендации

1. Гизела Энгельн-Мюлльгес; Фрэнк Улиг (2 июля 1996 г.). Численные алгоритмы с К. М. Шоном (переводчик), Ф. Улигом (переводчик) (1-е изд.). Спрингер. п. 10. ISBN 978-3-540-60530-0.
2. Мэтьюз, Джон Х.; Финк, Куртис Д. (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.