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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

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

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

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

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

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

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

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

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

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

Змішана стійкість комбінує поняття прямої і зворотної помилки.

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

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

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

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

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

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

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

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. Giesela Engeln-Müllges; Frank Uhlig (2 July 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].