Числова стійкість
В обчислювальній математиці числова стійкість є зазвичай бажаною властивістю чисельних алгоритмів. Точне визначення стійкості залежить від контексту. Один з них — чисельна лінійна алгебра, інший — алгоритми розв'язування звичайних рівнянь і диференціальних рівнянь у часткових похідних за допомогою дискретного наближення.
У чисельній лінійній алгебрі основною проблемою є нестабільності, викликані близькістю до різних особливостей (singularity), таких як дуже малі або майже рівні власні значення. З іншого боку, в чисельних алгоритмах для диференціальних рівнянь проблема полягає в зростанні похибок округлення та/або спочатку невеликих флуктуацій у початкових даних, які можуть призвести до значного відхилення остаточної відповіді від точного розв'язку.
Деякі чисельні алгоритми можуть послабити невеликі відхилення (похибки) у вхідних даних; інші можуть збільшити такі похибки. Розрахунки, які, як можна довести, не збільшують помилок апроксимації, називають обчислювально стійкими. Одна з поширених задач чисельного аналізу — спробувати вибрати надійні алгоритми, тобто не дати дуже відмінного результату за дуже малої зміни вхідних даних.
Протилежним явищем є нестійкість. Як правило, алгоритм включає наближений метод, і в деяких випадках можна довести, що алгоритм буде наближатися до правильного розв'язку в деякій границі (за використання насправді дійсних чисел, а не чисел з рухомою комою). Навіть у цьому випадку немає гарантії, що він буде збігатися до правильного розв'язку, оскільки похибки округлення чисел із рухомою комою можуть зростати, а не зменшуватися, що призведе до експоненційного зростання відхилення від точного розв'язку.[1]
Стійкість у чисельних методах лінійної алгебри
Існують різні способи формалізації концепції стійкості. У чисельній лінійній алгебрі використовують такі визначення прямої, зворотної та змішаної стійкості.
Розглянемо задачу, що розв'язується чисельним алгоритмом, як функцію f, що відображає дані x у розв'язок y. Результат алгоритму, скажімо, y*, зазвичай буде відхилятися від «істинного» розв'язку y. Основними причинами похибки є похибки округлення і похибки відкидання. Пряма похибка алгоритму — це різниця між результатом і розв'язком; у цьому випадку Δy = y* − y. Зворотна похибка є найменшою Δx такою, що f (x + Δx) = y*; іншими словами, зворотна похибка каже нам, яку задачу насправді розв'язав алгоритм. Пряма і зворотна похибки пов'язані числом обумовленості: пряма похибка за модулем не більша, ніж число обумовленості, помножене на модуль зворотної похибки.
У багатьох випадках природніше враховувати відносну похибку
замість абсолютної похибки Δx.
- Алгоритм називають зворотно стійким, якщо зворотна похибка мала для всіх вхідних x.
Звичайно «малий» — це відносний термін, і його визначення залежить від контексту. Часто ми хочемо, щоб похибка була того ж порядку, або, можливо, на кілька порядків більшою, ніж одиниця округлення.
Звичайне визначення числової стійкості використовує загальніше поняття змішаної стійкості, яка об'єднує пряму похибку і зворотну похибку. Алгоритм у цьому сенсі стійкий, якщо він приблизно розв'язує сусідню задачу, тобто якщо існує таке Δx, що і Δx мале, і f (x + Δx) − y* мале. Отже, зворотно стійкий алгоритм завжди стійкий.
- Алгоритм є стійким у прямому напрямку, якщо його пряма похибка, поділена на число обумовленості задачі, мала.
Це означає, що алгоритм є стійким у прямому напрямку, якщо він має пряму похибку величини, аналогічну зворотній похибці деякого зворотно стійкого алгоритму.
Стійкість різницевих схем диференціальних рівнянь
Наведені вище визначення особливо актуальні в ситуаціях, коли похибки відкидання не важливі. В інших контекстах, наприклад, при розв'язуванні диференціальних рівнянь, використовується інше визначення чисельної стійкості.
У чисельних звичайних диференціальних рівняннях присутні різні поняття чисельної стійкості, наприклад, A-стійкість. При розв'язуванні жорсткого рівняння важливо використовувати стійкий метод.
Ще одне визначення використовується в чисельних рівняннях у часткових похідних. Алгоритм розв'язування лінійного еволюційного рівняння в часткових похідних є стійким, якщо повна варіація чисельного розв'язку у фіксований час залишається обмеженою, коли розмір кроку наближається до нуля. Теорема еквівалентності Лакса стверджує, що алгоритм збігається, якщо він узгоджений і стійкий (у цьому сенсі). Стійкість іноді досягається включенням чисельної дифузії. Чисельна дифузія — це математичний термін, який означає, що округлення та інші похибки в обчисленнях розпорошуються і не підсумовуються, а тому не спричиняють «вибуху» обчислень. Аналіз стійкості за Нейманом широко застосовують для аналізу стійкості скінченно-різницевих схем стосовно лінійних рівнянь у часткових похідних. Ці результати не виконуються для нелінійних рівнянь у часткових похідних, де загальне несуперечливе визначення стійкості ускладнюється багатьма властивостями, відсутніми в лінійних рівняннях.
Примітки
- 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].