Numerikus stabilitás

A numerikus elemzésben , a matematika egyik ágában , a numerikus stabilitás a numerikus algoritmus globális tulajdonsága , amely tulajdonság szükséges az érdemi eredmények elérésének reményéhez.

A stabilitás szigorú meghatározása a kontextustól függ. A hibák terjedésére utal a számítás szakaszaiban, az algoritmus azon képességére, hogy az esetleges eltéréseket ne erősítse fel túlságosan, a kapott eredmények pontosságára.

A stabilitás fogalma nem korlátozódik a kerekítési hibákra és azok következményeire. Az algoritmusok szentelt a felbontás a differenciálegyenletek vagy parciális differenciál egyenletek (különösen a véges differencia módszer és a végeselem módszer ) alapulnak diszkretizációs vagy háló a tér (és idő); ebben az esetben a stabilitás erőteljes numerikus viselkedésre utal, amikor a diszkrétálás lépése vagy a háló mérete 0 felé halad.

Egy instabil algoritmus minősülnek használhatatlan , mert a generált eredményeket lehet teljesen megváltozott.

A numerikus elemzés egyik feladata olyan algoritmusok megtalálása, amelyek stabilitása garantált.

Példák

Polinom értékelése

Leggyakrabban a számításokat többféle módon lehet elvégezni, amelyek algebrailag egyenértékűek; a gyakorlatban azonban az eredmények eltérnek, mivel a megfelelő stabilitás nem azonos. Klasszikus eset a Ruffini-Horner-módszer a polinom értékelésére , összehasonlítva a naiv és nem hatékony módszerrel, amely az egyes monomálisok értékelését jelenti azok összegzésére.

Lineáris rendszer megoldása

A klasszikus módszerek megoldani egy-egy lineáris rendszert ( Gauss-Jordan elimináció , LU felbontás , Cholesky faktorizáció a pozitív definit mátrixok ) stabilak.

Nagy lineáris rendszerek esetében azonban ezen módszerek szekvenciális elemi számításainak számos műveletének pontatlansága jelentős hibákhoz vezethet a kapott megoldásban.

Ha az eredmény az elégedett , ahol tartják túl fontos, akkor meg kell határozni a megfelelő korrekciót , hogy megkérdezze . ${\ displaystyle {\ tilde {x}}}$ ${\ displaystyle A \; x = b}$ ${\ displaystyle A \; {\ tilde {x}} = b + \ Delta b}$ ${\ displaystyle \ displaystyle \ Delta b}$ ${\ displaystyle \ Delta x \;}$ ${\ displaystyle A \; \ Delta x = - \ Delta b}$ ${\ displaystyle x = {\ tilde {x}} + \ Delta x}$
Ahelyett, hogy egy második hasonló rendszert azonos módszerrel oldanánk meg (ami hosszú lenne, és általában gyenge eredményeket adna), jobb elvégezni a rekurzív módszer néhány ismétlését ( konjugált gradiens módszer pozitív vagy bikonjugátumként meghatározott mátrixok esetében , vagy a módszer egymást követő túlzott lazítás , amelynek megközelítése a priori egyszerűbbnek tűnik).

A felbontás módjától függetlenül a kapott eredmények pontossága közepes marad, ha a mátrix rosszul kondicionált . $NÁL NÉL$

Numerikus diagram véges különbségekkel

Hogy megoldja a problémát is kijelentette által leírt rendszer parciális differenciálegyenletek , egy numerikus rendszer a véges különbségek gyorsan vezethet, hogy teljesen hibás eredményeket, ha a stabilitást a program nem biztosított. Ilyen jelenség annak ellenére is előfordulhat, hogy a diagram tökéletesen alkalmazkodik az eredeti probléma egyenleteinek ábrázolásához ( a numerikus diagram konzisztenciája ).

Fordított stabilitás

Vegyünk egy olyan problémát, amelyet egy olyan függvénynek tekintett numerikus algoritmus segítségével oldunk meg , amely az adatokkal társítja az algebrai megoldást . A tényleges számítás eredménye (megjegyezve ) általában eltér az algebrai megoldástól. $y = f (x)$ $x$ $y$ $y ^ {*}$

A fő okok a kerekítési hibák, a csonkolási hibák és az adathibák.

Egy algoritmus downstream hibája a valós eredmény és az algebrai megoldás közötti különbség. Az upstream hiba vagy a fordított hiba a legkisebb , például ; más szavakkal, az upstream hiba megmondja, hogyan oldja meg a problémát az algoritmus. Az upstream és downstream hibákat a feltételszám kapcsolja össze : a downstream hiba legfeljebb ugyanolyan nagyságrendű, mint a feltétel szám szorozva a upstream hiba nagyságrendjével. $\ Delta x$ ${\ displaystyle f \ left (x + \ Delta x \ right) = y ^ {*}}$

Az algoritmust fordítva stabilnak vagy stabilnak tekintik az upstream irányban, ha az upstream hiba elég kicsi az összes adat számára . A "kicsi" egy relatív kifejezés, amelynek értékelése természetesen a kontextustól függ. Gyakran kívánatos, hogy a hiba azonos nagyságrendű legyen, mint ..., vagy csak nagyobb legyen ... néhány nagyságrenddel, egy egységen belül. $x$

Sok helyzetben természetes, hogy az abszolút hiba helyett a relatív hibát vesszük figyelembe . ${\ displaystyle {\ frac {| \ Delta x |} {| x |}}}$ $\ Delta x$

Lásd is

Referencia

(hu) Nicholas J. Higham , pontossága és stabilitása Numerikus algoritmusok , Society of Industrial and Applied Mathematics , Philadelphia , 1996 ( ISBN 0-89871-355-2 ) , [ olvasható online ] .