Числова стійкість

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

У чисельній лінійній алгебрі основною проблемою є нестабільності, викликані близькістю до різних особливостей (singularity), таких як дуже малі або майже рівні власні значення. З іншого боку, в чисельних алгоритмах для диференціальних рівнянь проблема полягає в зростанні похибок округлення та/або спочатку невеликих флуктуацій у початкових даних, які можуть призвести до значного відхилення остаточної відповіді від точного розв'язку.

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

Протилежним явищем є нестійкість. Як правило, алгоритм включає наближений метод, і в деяких випадках можна довести, що алгоритм буде наближатися до правильного розв'язку в деякій границі (за використання насправді дійсних чисел, а не чисел з рухомою комою). Навіть у цьому випадку немає гарантії, що він буде збігатися до правильного розв'язку, оскільки похибки округлення чисел із рухомою комою можуть зростати, а не зменшуватися, що призведе до експоненційного зростання відхилення від точного розв'язку.^[1]

Стійкість у чисельних методах лінійної алгебри

Існують різні способи формалізації концепції стійкості. У чисельній лінійній алгебрі використовують такі визначення прямої, зворотної та змішаної стійкості.

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

У багатьох випадках природніше враховувати відносну похибку

{\frac {|\Delta x|}{|x|}}

замість абсолютної похибки Δ $x$ .

Алгоритм називають зворотно стійким, якщо зворотна похибка мала для всіх вхідних $x$ .

Звичайно «малий» — це відносний термін, і його визначення залежить від контексту. Часто ми хочемо, щоб похибка була того ж порядку, або, можливо, на кілька порядків більшою, ніж одиниця округлення.

Звичайне визначення числової стійкості використовує загальніше поняття змішаної стійкості, яка об'єднує пряму похибку і зворотну похибку. Алгоритм у цьому сенсі стійкий, якщо він приблизно розв'язує сусідню задачу, тобто якщо існує таке Δ $x$ , що і Δ $x$ мале, і $f (x + Δ x) - y *$ мале. Отже, зворотно стійкий алгоритм завжди стійкий.

Алгоритм є стійким у прямому напрямку, якщо його пряма похибка, поділена на число обумовленості задачі, мала.

Це означає, що алгоритм є стійким у прямому напрямку, якщо він має пряму похибку величини, аналогічну зворотній похибці деякого зворотно стійкого алгоритму.

Стійкість різницевих схем диференціальних рівнянь

Наведені вище визначення особливо актуальні в ситуаціях, коли похибки відкидання не важливі. В інших контекстах, наприклад, при розв'язуванні диференціальних рівнянь, використовується інше визначення чисельної стійкості.

У чисельних звичайних диференціальних рівняннях присутні різні поняття чисельної стійкості, наприклад, A-стійкість. При розв'язуванні жорсткого рівняння важливо використовувати стійкий метод.

Ще одне визначення використовується в чисельних рівняннях у часткових похідних. Алгоритм розв'язування лінійного еволюційного рівняння в часткових похідних є стійким, якщо повна варіація чисельного розв'язку у фіксований час залишається обмеженою, коли розмір кроку наближається до нуля. Теорема еквівалентності Лакса^[en] стверджує, що алгоритм збігається, якщо він узгоджений і стійкий (у цьому сенсі). Стійкість іноді досягається включенням чисельної дифузії^[en]. Чисельна дифузія — це математичний термін, який означає, що округлення та інші похибки в обчисленнях розпорошуються і не підсумовуються, а тому не спричиняють «вибуху» обчислень. Аналіз стійкості за Нейманом^[en] широко застосовують для аналізу стійкості скінченно-різницевих схем стосовно лінійних рівнянь у часткових похідних. Ці результати не виконуються для нелінійних рівнянь у часткових похідних, де загальне несуперечливе визначення стійкості ускладнюється багатьма властивостями, відсутніми в лінійних рівняннях.

Див. також

Примітки

↑ Giesela Engeln-Müllges; Frank Uhlig (2 липня 1996). Numerical Algorithms with C. M. Schon (Translator), F. Uhlig (Translator) (вид. 1). Springer. с. 10. ISBN 978-3-540-60530-0.

Література

Е. А. Волков. Численные методы. — М. : Наука, 1987. — 248 с. — 36000 прим. (рос.)
А. А. Самарский, А. В. Гулин. Численные методы. — М. : Наука, 1989. — 432 с. (рос.)
Lloyd N. Trefethen. Finite Difference and Spectral Methods for Ordinary and Partial Differential Equations. — 1996.
Nicholas J. Higham (1996). Accuracy and Stability of Numerical Algorithms. Philadelphia: Society of Industrial and Applied Mathematics. ISBN 0-89871-355-2.
Richard L. Burden; J. Douglas Faires (2005). Numerical Analysis (вид. 8th). U.S.: Thomson Brooks/Cole. ISBN 0-534-39200-8.
Mesnard, Olivier; Barba, Lorena A. (2016). Reproducible and replicable CFD: It's harder than you think. arXiv:1605.04339 [physics.comp-ph].

[1] Giesela Engeln-Müllges; Frank Uhlig (2 липня 1996). Numerical Algorithms with C. M. Schon (Translator), F. Uhlig (Translator) (вид. 1). Springer. с. 10. ISBN 978-3-540-60530-0.

[1]