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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

Вычисление квадратного корня из 2 (что примерно равно 1,41421) является хорошо поставленной задачей . Многие алгоритмы решают эту задачу, начиная с начального приближения x ₀ к , например, x ₀ = 1,4, а затем вычисляя улучшенные догадки x ₁ , x ₂ и т. д. Одним из таких методов является знаменитый вавилонский метод , который задается как x _{k +1} = ( x _k + 2/ x _k )/2. Другой метод, называемый «методом 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. Этот пример является модификацией примера, взятого из работы Мэтьюза и Финка (1999). ^[2]

Ссылки

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

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