Základní pojmy numerických metod

Numerická metoda, konvergence, korektnost, podmíněnost úlohy, numerická stabilita, ukončení výpočtu

Numerické metody je možno chápat, v návaznosti na studijní článek Zaměření kurzu „Numerické metody“, i jako teorii zvláštních, konstruktivních, metod matematické analýzy a algebry a jejich aplikací. Numerickou stabilitu můžeme, zjednodušeně, chápat jako vliv zaokrouhlovacích chyb na kvalitu výsledku (řešení). U nestabilní metody (algoritmu) se relativně malé chyby v jednotlivých krocích výpočtu postupně akumulují tak, že dojde ke katastrofální ztrátě přesnosti numerického řešení úlohy. Důležité je tedy, aby daná metoda nejen konvergovala, ale aby byla i numericky stabilní. Výsledky jsou pak bezprostředně prakticky využitelné. Při zkoumání podmíněnosti lze rozlišit podmíněnost problému a podmíněnost metody. Podmíněnost metody souvisí těsně s problémem „citlivosti“ metody na změny ve vstupních údajích, které mohou často reprezentovat citlivost na chyby vstupních dat. Je-li úloha dobře podmíněná, je i numericky stabilní. V opačném případě říkáme, že úloha je špatně podmíněná či numericky nestabilní. Při řešení úloh numerickými metodami se setkáváme dále s pojmy špatně a dobře podmíněný algoritmus.

Koeficient C p MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipv0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4qamaaBaaaleaacaWGWbaabeaaaaa@37F6@  podmíněnosti úlohy y=U(x) MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipv0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyEaiabg2da9iaadwfacaGGOaGaamiEaiaacMcaaaa@3B41@  je dán poměrem relativní změny výsledku k relativní změně vstupních dat; v reálných případech je dán poměrem odhadu relativních chyb, tj.:

MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipv0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcaa@360C@ C p = ‖ Δy ‖ ‖ y ‖ ‖ Δx ‖ ‖ x ‖ ≈ ∂(y) ∂(x) MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipv0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4qamaaBaaaleaacaWGWbaabeaakiabg2da9maalaaabaWaaSaaaeaadaqbdaqaaiabfs5aejaadMhaaiaawMa7caGLkWoaaeaadaqbdaqaaiaadMhaaiaawMa7caGLkWoaaaaabaWaaSaaaeaadaqbdaqaaiabfs5aejaadIhaaiaawMa7caGLkWoaaeaadaqbdaqaaiaadIhaaiaawMa7caGLkWoaaaaaaiabgIKi7oaalaaabaGaeyOaIyRaaiikaiaadMhacaGGPaaabaGaeyOaIyRaaiikaiaadIhacaGGPaaaaaaa@55CE@

Tento koeficient je tedy dán poměrem relativní chyby na výstupu k relativní chybě na vstupu

Pokud C p ≈1 MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipv0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4qamaaBaaaleaacaWGWbaabeaakiabgIKi7kaaigdaaaa@3A6C@  , říkáme, že úloha je velmi dobře podmíněná, pokud C p >100 MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipv0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4qamaaBaaaleaacaWGWbaabeaatCvAUfKttLearyqr1ngBPrgaiuaakiab=5da+iaaigdacaaIWaGaaGimaaaa@4016@ , úloha je špatně podmíněná.

U numericky nestabilní metody (při použití nestabilního algoritmu) se relativně malé chyby v jednotlivých krocích výpočtu postupně akumulují tak, že dojde ke katastrofální ztrátě přesnosti numerického řešení úlohy. Malá nepřesnost ve vstupních datech má tedy za následek nepoužitelný výsledek.

Algoritmus, který je špatně podmíněný je tedy numericky nestabilní. V algoritmech se například vyhýbáme odčítání operandů, které mají malý rozdíl v absolutní hodnotě vzhledem k operandům. Výpočet je ukončen buď po proběhnutí všech předepsaných kroků (např. u Gaussovy eliminační metody) nebo poté, co je rozhodnuto podle určitých kritérií, že jsme se dostatečně přiblížili k řešení (že jsme získali validní aproximaci). To je v případě řešení nelineárních rovnic např. rozhodnutí, zda funkční hodnota v aproximaci kořene je dostatečně blízko k nule či v případě, že dvě následně získané aproximace se v absolutní hodnotě liší již jen „málo“ atd.

Nepřesnost (chyba), platnost výsledků

Nepřesnost je vlastnost charakteristická pro řadu numerických výpočtů. V rámci modulu se setkáte s metodami, které za zvláštních okolností vedou k přesnému řešení (v některých případech je to např. metoda bisekce, Gaussova eliminační metoda atd.). Většinou však získáme aproximace přesných hodnot. Nepřesnosti (chyby) při řešení úloh lze pak rozdělit zejména na:

·        Chyby vstupních dat (např. chyby měření)

·        Chyby metody; vznikají v důsledku použití matematického a následně numerického modelu. Matematická úloha, která už mnohdy zjednodušuje skutečný problém, je převedena na numerickou. Sem lze zahrnout i tzv. chybu zbytkovou. Reálně se provádí jen určitý počet operací; proces výpočtu je ukončen poté co se přiblížíme k výsledku (po dosažení předem stanovené přesnosti). Vzhledem k tomu, že ve většině případů přesné hodnoty neznáme, jedná se pouze o odhady chyb.

·        Chyby při zpracování úlohy na počítači: zaokrouhlovací chyby; ty vznikají v důsledku zaokrouhlování při výpočtech s čísly s určitým počtem signifikantních cifer.

·        Chyby vznikající v důsledku užití špatně podmíněné úlohy.

·        Chyby vznikající v důsledku užití nestabilního algoritmu.

Použijeme-li značení:

x ^ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipv0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGabmiEayaajaaaaa@371A@

přesná hodnota; pozn. znovu připomínáme, že ve většině reálných případů přesná hodnota není známa

x MathType@MTEF@5@5@+=feaafiart1ev1aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiEaaaa@36EB@

přibližná hodnota

Teoreticky absolutní chybu definujeme vztahem E= x ^ −x MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipv0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyraiabg2da9iqadIhagaqcaiabgkHiTiaadIhaaaa@3AD4@

Teoretická relativní chyba je: RE=| E x ^ |=| x ^ −x x ^ | MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipv0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOuaiaadweacqGH9aqpdaabdaqaamaalaaabaGaamyraaqaaiqadIhagaqcaaaaaiaawEa7caGLiWoacqGH9aqpdaabdaqaamaalaaabaGabmiEayaajaGaeyOeI0IaamiEaaqaaiqadIhagaqcaaaaaiaawEa7caGLiWoaaaa@45F9@

Často je nutno používat odhady chyb, tedy:

odhad absolutní chyby ε≥| x ^ −x | MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipv0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeqyTduMaeyyzIm7aaqWaaeaaceWG4bGbaKaacqGHsislcaWG4baacaGLhWUaayjcSdaaaa@3F93@

odhad relativní chyby ρ= ε x MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipv0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeqyWdiNaeyypa0ZaaSaaaeaacqaH1oqzaeaacaWG4baaaaaa@3B87@ ; pozn. přesnou hodnotu, kterou neznáme, nahrazujeme hodnotou spočtenou.

Deterministické a stochastické metody

Většinu v kurzu uváděných metod je možno zařadit do skupin deterministických metod. Metoda Monte Carlo uváděná ve studijní jednotce Numerický výpočet určitého integrálu je příkladem stochastické metody. V poslední době se jeví jako perspektivní (pro řešení specifického okruhu problémů) tzv. genetické metody založené na použití genetických algoritmů. Jejich popis však přesahuje rámec kurzu.

Výběr metody; volba algoritmu a aplikace

Základním požadavkem je možnost vyřešení úlohy s dostatečnou přesností. Sledována je konvergence, což znamená schopnost vyřešit úlohu s libovolně vysokou přesností (omezené jen zaokrouhlovací chybou) při kroku h→0 MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipv0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaeiAaiabgkziUkaabcdaaaa@3998@  (při počtu operací N→∞ MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqipv0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yqaqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaeOtaiabgkziUkabg6HiLcaa@3A3C@  ).

Při výběru metody hraje roli i složitost algoritmu (či počet operací nutných k získání výsledku se zadanou přesností) případně paměťové nároky a to zda je k dispozici spolehlivá implementace příslušné metody. Prakticky ve všech případech v současné době užíváme pro řešení numerických úloh počítač. Přitom pro implementaci metod užíváme například aplikace Delphi, Visual Basic, C++, Matlab, Maple, Mathematica (u posledních tří zmíněných nejen jejich příkazy, ale zejména programovací jazyky). Ve speciálních případech se užívá Assembler. Velkou roli při výběru metody hraje zkušenost.