Stabilitate computațională

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 14 februarie 2022; verificările necesită 2 modificări .

În matematica computațională, robustețea computațională este de obicei o proprietate de dorit a algoritmilor numerici.

Definiția exactă a durabilității depinde de context. Unul dintre ele este algebra liniară numerică, celălalt este algoritmi pentru rezolvarea ecuațiilor obișnuite și a ecuațiilor cu diferențe parțiale folosind aproximarea discretă.

În algebra liniară numerică, principala problemă este instabilitatea cauzată de apropierea de diferite caracteristici, cum ar fi valori proprii foarte mici sau aproape identice.

Pe de altă parte, în algoritmii numerici pentru ecuații diferențiale, problema este creșterea erorilor de rotunjire și/sau fluctuații inițial mici ale datelor de intrare, ceea ce poate duce la o abatere semnificativă a răspunsului final de la soluția exactă.

Unii algoritmi numerici pot atenua mici abateri (erori) în datele de intrare; altele pot spori astfel de erori. Se spune că calculele despre care se poate demonstra că nu măresc erorile de aproximare sunt stabile din punct de vedere computațional. Una dintre problemele comune în analiza numerică este încercarea de a alege algoritmi robusti, adică să nu dea un rezultat foarte diferit cu o modificare foarte mică a datelor de intrare.

Opusul este instabilitatea. De regulă, algoritmul include o metodă de aproximare, iar în unele cazuri se poate dovedi că algoritmul va aproxima soluția corectă într-o anumită limită (folosind efectiv numere reale , nu numere în virgulă mobilă ).

Chiar și în acest caz, nu există nicio garanție că va converge către soluția corectă, deoarece erorile de rotunjire sau trunchiere în virgulă mobilă pot crește mai degrabă decât să scadă, ceea ce duce la o creștere exponențială a abaterii de la soluția exactă. [unu]

Stabilitate în metodele numerice ale algebrei liniare

Există diferite moduri de a oficializa conceptul de durabilitate. Următoarele definiții ale stabilității directe, inverse și mixte sunt utilizate frecvent în algebra liniară numerică.

Considerăm o problemă rezolvată de un algoritm numeric ca o funcție f care mapează datele x la soluția y . Rezultatul algoritmului, să spunem y* , se va abate de obicei de la soluția „adevărată” y . Principalele cauze ale erorii sunt erorile de rotunjire și erorile de trunchiere . Eroarea directă a algoritmului este diferența dintre rezultat și soluție; în acest caz Δ y = y * − y . Eroarea inversă este cea mai mică Δ x astfel încât f  ( x + Δ x ) = y * ; cu alte cuvinte, eroarea înapoi ne spune ce problemă a rezolvat algoritmul. Erorile înainte și înapoi sunt legate de numărul condiției : eroarea directă nu este mai mare ca mărime decât numărul condiției înmulțit cu eroarea inversă.

În multe cazuri este mai natural[ clarify ] consider error relative

în loc de Δx absolut .

Desigur, „mic” este un termen relativ, iar definiția lui va depinde de context. Adesea dorim ca eroarea să fie de același ordin de mărime sau poate cu mai multe ordine de mărime mai mare decât unitatea de rotunjire .

Definiția obișnuită a robusteței computaționale folosește un concept mai general numit robustețe mixtă , care combină eroarea directă și eroarea inversă. Un algoritm în acest sens este stabil dacă rezolvă aproximativ o problemă învecinată, adică dacă există Δ x astfel încât atât Δ x este mic, cât și f  ( x + Δ x ) − y * este mic. Prin urmare, un algoritm stabil înapoi este întotdeauna stabil.

Aceasta înseamnă că un algoritm este înainte stabil dacă are o eroare de magnitudine înainte similară cu eroarea înapoi a unui algoritm stabil.

Stabilitatea schemelor de diferențe ale ecuațiilor diferențiale

Definițiile de mai sus sunt relevante în special în situațiile în care erorile de trunchiere nu sunt importante. În alte contexte, cum ar fi atunci când se rezolvă ecuații diferențiale, este utilizată o definiție diferită a stabilității numerice.

În ecuațiile diferențiale ordinare numerice, există diferite concepte de stabilitate numerică, de exemplu, A-stabilitate . Când rezolvați o ecuație rigidă , este important să folosiți o metodă stabilă.

O altă definiție este utilizată în ecuațiile numerice cu diferențe parțiale. Un algoritm pentru rezolvarea unei ecuații diferențiale parțiale evolutive lineare este stabil dacă variația totală a soluției numerice la un timp fix rămâne mărginită pe măsură ce dimensiunea pasului se apropie de zero. Teorema de echivalență a lui Lax afirmă că un algoritm converge dacă este consistent și stabil (în acest sens). Stabilitatea se realizează uneori prin includerea difuziei numerice . Difuzia numerică este un termen matematic care asigură că rotunjirea și alte erori în calcule se propagă și nu se adună pentru a duce la o „explozie” de calcule. Analiza de stabilitate Neumann este o procedură utilizată pe scară largă pentru analiza stabilității schemelor de diferențe finite aplicate ecuațiilor diferențiale parțiale liniare. Aceste rezultate nu sunt valabile pentru ecuațiile diferențiale parțiale neliniare, unde definiția generală consistentă a stabilității este complicată de multe proprietăți care lipsesc din ecuațiile liniare.

Vezi și

Note

  1. ↑ Giesela Engeln-Müllges. Algoritmi numerici  cu C ]  / Giesela Engeln-Müllges, Frank Uhlig. - 1. - Springer, 2 iulie 1996. - P. 10. - ISBN 978-3-540-60530-0 . Arhivat pe 19 august 2020 la Wayback Machine

Literatură