Stabilitate numerică
Stabilitatea numerică (de asemenea algoritmică sau de calcul ), în contextul analizei numerice , este o proprietate dorită a algoritmilor numerici. Înțelesul exact al termenului variază, dar, în general, reflectă acuratețea rezultatului.
Nu există metode generale pentru evaluarea stabilității unui algoritm. De obicei, valorile pentru care algoritmul devine instabil sunt căutate prin metode specifice - cum ar fi metoda simplex - în domeniul unui algoritm: adică cea mai mică variație a datelor duce la abateri mari în eroare.
Un exemplu clasic este calculul ariei triunghiului cu formula Heron , instabilă pentru unghiuri foarte mici.
Un alt exemplu clasic este cazul overflow / underflow : gândiți-vă doar la cele două operații
unde 10 -a este egal sau mai mic decât epsilonul mașinii și 10 b este numărul maxim reprezentabil.
O eroare, odată ce a fost generată, se va răspândi în general prin calcul. Acest lucru duce la conceptul de stabilitate numerică: se spune că un algoritm este numeric stabil dacă o eroare, odată ce a fost generată, nu crește prea mult în timpul calculului.
Stabilitate în algebră liniară
Există diferite modalități de formalizare a conceptului de stabilitate: stabilitatea înainte, stabilitatea înapoi și stabilitatea mixtă sunt de obicei utilizate în algebra liniară numerică.
Să luăm în considerare o problemă rezolvată de un algoritm constând dintr-o funcție ƒ care mapează intrările x în soluțiile y . Rezultatul algoritmului, pe care îl vom numi y *, se abate de la soluția „adevărată” y . Principalele cauze ale acestor abateri sunt erorile de rotunjire și erorile de trunchiere. Eroarea directă a algoritmului este diferența dintre rezultatul y * și soluția y , adică Δ y = y * - y. Eroarea inversă este cea mai mică Δx astfel încât f (x + Δx) = y *; cu alte cuvinte, eroarea inversă ne spune ce problemă a rezolvat algoritmul. Cele două erori sunt legate de numărul de condiționare: eroarea directă este la fel de mare ca magnitudinea numărului de condiționare înmulțită cu magnitudinea erorii înapoi.
În multe cazuri, este preferabil să se ia în considerare eroarea relativă | Δx | / | x | mai degrabă decât eroarea absolută Δx.
Se spune că un algoritm este stabil înapoi dacă eroarea înapoi este mică pentru fiecare intrare x ; mici înseamnă, în general, același ordin de mărime sau mai mic decât eroarea mașinii (eroare de rotunjire).
Se spune că un algoritm este stabil înainte dacă eroarea directă împărțită la numărul condiției problemei este mică. Aceasta înseamnă că un algoritm este stabil înainte dacă are o eroare directă de magnitudine comparabilă cu unii algoritmi stabili înapoi.
Stabilitatea mixtă este un concept mai general, care combină eroarea înainte și eroarea înapoi. Un algoritm este stabil în acest sens dacă rezolvă o problemă vecină într-un mod aproximativ, adică dacă există un Δx astfel încât atât Δx cât și f ( x + Δ x ) - y * sunt ambele mici. Conform acestei definiții, un algoritm stabil înapoi este întotdeauna stabil.
