Loading AI tools
В обчислювальній математиці числова стійкість є зазвичай бажаною властивістю чисельних алгоритмів. Точне визначення стійкості залежить від контексту. Один з них — чисельна лінійна алгебра, інший — алгоритми розв'язування звичайних рівнянь і диференціальних рівнянь у часткових похідних за допомогою дискретного наближення.
У чисельній лінійній алгебрі основною проблемою є нестабільності, викликані близькістю до різних особливостей (singularity), таких як дуже малі або майже рівні власні значення. З іншого боку, в чисельних алгоритмах для диференціальних рівнянь проблема полягає в зростанні похибок округлення та/або спочатку невеликих флуктуацій у початкових даних, які можуть призвести до значного відхилення остаточної відповіді від точного розв'язку.
Деякі чисельні алгоритми можуть послабити невеликі відхилення (похибки) у вхідних даних; інші можуть збільшити такі похибки. Розрахунки, які, як можна довести, не збільшують помилок апроксимації, називають обчислювально стійкими. Одна з поширених задач чисельного аналізу — спробувати вибрати надійні алгоритми, тобто не дати дуже відмінного результату за дуже малої зміни вхідних даних.
Протилежним явищем є нестійкість. Як правило, алгоритм включає наближений метод, і в деяких випадках можна довести, що алгоритм буде наближатися до правильного розв'язку в деякій границі (за використання насправді дійсних чисел, а не чисел з рухомою комою). Навіть у цьому випадку немає гарантії, що він буде збігатися до правильного розв'язку, оскільки похибки округлення чисел із рухомою комою можуть зростати, а не зменшуватися, що призведе до експоненційного зростання відхилення від точного розв'язку.[1]
Існують різні способи формалізації концепції стійкості. У чисельній лінійній алгебрі використовують такі визначення прямої, зворотної та змішаної стійкості.
Розглянемо задачу, що розв'язується чисельним алгоритмом, як функцію 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] широко застосовують для аналізу стійкості скінченно-різницевих схем стосовно лінійних рівнянь у часткових похідних. Ці результати не виконуються для нелінійних рівнянь у часткових похідних, де загальне несуперечливе визначення стійкості ускладнюється багатьма властивостями, відсутніми в лінійних рівняннях.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
