Numerické metody

Note	Iterativní metody pro řešení nelineárních rovnic (Newtonova metoda a její modifikace). Přímé metody pro řešení systému lineárních rovnic (Gaussova eliminace, Jacobi, Gauss-Seidel, relaxační metody). Numerická diferenciace, diferenciační schémata. MA018

Numerická analýza / numerical analysis

Oblast matematiky / informatiky zabývající se tvorbou numerických metod a algoritmů, které řeší problémy matematické analýzy (např. derivace, integrály a podobný symbolický balast) pomocí numerické aproximace. [2]

Je výhodná v situacích, kdy problém nelze řešit analyticky nebo je to příliš složité a není to (výpočetní) čas.

Notace chyb

$x$ je přesná hodnota,
$\tilde{x}$ je aproximace $x$ ,
$x - \tilde{x}$ je absolutní chyba $\tilde{x}$ ,
$∣ x - \tilde{x} ∣ \leq α$ je odhad absolutní chyby,
$\frac{x - x ~}{x}$ je relativní chyba,
$\frac{x - x ~}{x} \leq α$ je odhad relativní chyby.

Numerická stabilita

Schopnost numerické metody zpracovat chyby vstupních dat a výpočetních operací.

Desetinná čísla jsou v počítačích nevyhnutelně reprezentována nepřesně. Numericky stabilní metody jsou takové, které tyto nepřesnosti nezhoršují. [15]

Řád metody / order of accuracy / order of approximation

Hodnota reprezentující, jak rychle metoda konverguje k výsledku, resp. jak přesný je její odhad.

Numerická metoda obvykle konverguje snižováním nějakého kroku $h$ . Pokud ho lze zvolit libovolně malý, a lze-li prohlásit, že pro chybu aproximace $E$ platí: [4] [16] [17]

E (h) E (h) \leq C \cdot h^{p} \in O (h^{p})

kde $C$ je konstanta. Pak $p$ je řád metody.

Iterativní metody pro řešení nelineárních rovnic

Root-finding problem

Problém nalezení kořenů (root) funkce $f$ . T.j. takových parametrů $x, ...$ , kde funkce vrací 0: [3]

f (x, ...) = 0

Iterative methods for root-finding problem

Metody pro řešení root-finding problemu, které využívají iterativního přístupu. Tedy opakují nějaký výpočet a zpřesňují svůj odhad, dokud nedosáhnou požadované přesnosti. [1] [3]

Řád metody / rate of convergence

Hodnota reprezentující, jak rychle metoda konverguje k výsledku. [4]

Prostá iterační metoda / metoda pevného bodu / fixed-point iteration

Používá se pro rovnice typu $x = g (x)$ .

Zvolíme počáteční odhad $x_{0}$ .
Opakujeme $x_{n + 1} = g (x_{n})$ dokud $∣ x_{n + 1} - x_{n} ∣ \leq α$ (kde $α$ je požadovaná přesnost).

Newtonova metoda / metoda tečen

Používá k odhadu kořene funkce $f$ její tečnu v bodě $x_{n}$ . Iterační funkce je:

g (x_{k + 1}) = x_{k} - \frac{f ( x _{k} )}{f ^{'} ( x _{k} )}

Zvolíme počáteční odhad $x_{0}$ .
Další odhad je $x_{n + 1} = g (x_{n})$ , tedy průsečík tečny fukce $f$ v bodě $x_{n}$ s osou $x$ .
Opakujeme 2. dokud nedosáhneme požadované přesnosti odhadu.

Metoda sečen / secant method

Používá k odhadu kořene funkce $f$ sečny, resp. finite difference, které aproximují derivaci funkce $f$ . Díky tomu není potřeba znát derivaci funkce $f$ . Iterační funkce je:

g (x_{k + 1}) = x_{k} - \frac{f ( x _{k} ) ( x _{k} - x _{k - 1} )}{f ( x _{k} ) - f ( x _{k - 1} )}

Metoda regula falsi

Je bracketing metoda, tedy metoda, která využívá intervalu, ve kterém se nachází kořen. Nemusí se použít iterativně, ale v iterativní podobě tento interval postupně zmenšuje. [5]

x_{k + 1} = x_{k} - \frac{x _{k} - x _{s}}{f ( x _{k} ) - f ( x _{s} )} f (x_{k})

kde $s$ je největší index takový, že $f (x_{k}) f (x_{s}) < 0$ .

Přímé metody pro řešení systému lineárních rovnic

Gaussova eliminace

Systém rovnice je přepsán do matice. Gaussova eliminace je posloupnost operací, jejichž cílem je převést matici do horní trojúhelníkové matice (row echelon form). [6] Povoleny jsou následující operace:

výměna dvou řádků,
vynásobení řádku nenulovou konstantou,
přičtení násobku jednoho řádku k jinému.

Jacobiho iterační metoda

Iterativní algoritmus pro řešení soustavy lineárních rovnic. Rozděluje vstupní matici lineárních rovnic na matici diagonál $D$ , dolní trojúhelníkovou matici $L$ a horní trojúhelníkovou matici $U$ . [7]

Nechť $A x = b$ je systém $n$ lineárních rovnic. Tedy:

A = a_{11} a_{21} ⋮ a_{n 1} a_{12} a_{22} ⋮ a_{n 2} \dots \dots ⋱ \dots a_{1 n} a_{2 n} ⋮ a_{nn}, x = x_{1} x_{2} ⋮ x_{n}, b = b_{1} b_{2} ⋮ b_{n} .

Algoritmus vypadá takto:

Zvolíme počáteční odhad $x^{(0)}$ , nejčastěji $0$ .
Nový odhad získáme ze vztahu:

$x^{(k + 1)} = D^{- 1} (b - (L + U) x^{(k)})$

Jelikož $L + U = A - D$ , dá to zapsat i jako:

x^{(k + 1)} = D^{- 1} b + (I - D^{- 1} A) x^{(k)}

Spektrální poloměr

Spektrální poloměr $ρ$ matice $A$ je největší absolutní hodnota vlastního čísla matice $A$ .

ρ (A) = i = 1, \dots, n max ∣ λ_{i} ∣

(Řádková) diagonální dominance

Matice $A$ je diagonálně dominantní, pokud platí:

∣ a_{ii} ∣ > j = 1, j \neq = i \sum n ∣ a_{ij} ∣

Tedy absolutní hodnota prvku na diagonále je větší než součet absolutních hodnot všech ostatních prvků v řádku.

Striktní: nerovnost je ostrá ( $>$ ).
Slabá: nerovnost je neostá ( $\geq$ ).

Analogicky se definuje sloupcová diagonální dominance.

Konvergence Jacobiho metody

Jacobiho metoda konveguje pokud všechny následující podmínky:

Nechť $T_{j} = I - D^{- 1} A$ je matice iterace Jacobiho metody. Pak Jacobiho metoda konverguje, pokud:

$ρ (T_{j}) < 1$
Jacobiho metoda konverguje pro libovolný počáteční odhad $x^{(0)}$ , pokud $A$ je diagonálně dominantní (sloupcově nebo řádkově).

Gaussova-Seidelova iterační metoda

Iterativní metoda pro řešení soustavy lineárních rovnic. Dělí vstupní matici na spodní trojúhelníkovou matici $L_{*}$ (včetně diagonály, tedy $L_{*} = D + L$ ) a striktně horní trojúhelníkovou matici $U$ (diagonála je nulová). Algoritmus vypadá takto: [8]

Zvolíme počáteční odhad $x^{(0)}$ .
Nový odhad získáme ze vztahu:

$x^{(k + 1)} = L_{*}^{- 1} (b - U x^{(k)}) .$

Alternativně:

T_{g s} x^{(k + 1)} = (D + L)^{- 1} U = L_{*}^{- 1} U = T_{g s} x^{(k)} + g, g = L_{*}^{- 1} b

Konvergence Gaussovy-Seidelovy metody: Analogicky jako u Jacobiho metody, ale místo matice $T_{j}$ se použije matice $T_{g s} = (D + L)^{- 1} U$ .

Relaxační iterativní metody

Modifikace Gauss-Seidelovy metody. Využívá parametr $ω$ , který určuje, jak moc se má nový odhad lišit od předchozího. Vztah pro další iteraci se mění na: [9]

x^{(k + 1)} T_{ω} = (D - ω L)^{- 1} [(1 - ω) D + ω U] x^{(k)} + ω (D - ω L)^{- 1} b = (D - ω L)^{- 1} [(1 - ω) D + ω U]

Pro $0 < ω < 1$ se názývá metodou dolní relaxace. Je vhodná v případě, kdy Gauss-Seidel nekonverguje.
Pro $ω = 1$ je totožná s Gauss-Seidelem.
Pro $ω > 1$ se názývá metodou horní relaxace / SOR metodou. Zrychluje konvergenci Gauss-Seidela.

Dekompozice matic

Metody podobné Gaussově eliminaci, ale s vlastnostmi, které mohou být vyhodné.

LU dekompozice

Rozdělení matice $A$ na horní dolní trojúhelníkovou matici $L$ a horní trojúhelníkovou matici $U$ , tak že $A = LU$ .

Je to v podstatě Gaussova eliminace. Matice $P$ je permutační matice, která prohazuje řádky:

P \cdot A = L \cdot U

Platí, že:

A \cdot x A LU \cdot x = b = LU = b

Původní problém řešení soustavy linárních rovnic se tedy převede na dva problémy:

y L \cdot y = U \cdot x = b

Řešíme tedy dva systémy rovnic s trojúhelníkovými maticemi.

Oproti Gaussovi je výhodnější pro:

Opakované řešení soustav s maticí $A$ a různými pravými stranami $b$ .
Inverzi matice $A$ .
Výpočet determinantu matice $A$ .

QR dekompozice

Rozdělení matice $A$ na ortogonální matici $Q$ a horní trojúhelníkovou matici $R$ (už ne $U$ ), tak že $A = QR$ .

A \cdot x A = QR \Rightarrow U \cdot x = b = Q^{T} \cdot b

Protože je ortogonální a tedy $Q^{- 1} = Q^{T}$ .

Má lepší numerickou stabilitu než LU dekompozice.

Numerická diferenciace

Algoritmy numerické diferenciace (derivace) počítají odhady derivace reálných funkcí — aproximují $f^{'} (x)$ . Využívají při tom známé hodnoty této funkce a jiné znalosti a předpoklady. [10]

Numerická diferenciace se využívá pro aproximaci differenciálních rovnic (převodem na diferenční rovnice).

Langrangeova interpolace

Pokud známe hodnoty $f$ můžeme mezi nimi interpolovat pomocí Lagrangeova polynomu a derivovat ten, protože derivovat polynomy je jednoduché.

Important

Lagrangeovu interpolaci řeší část otázky Křivky a povrchy.

Finite difference method

Rodina metod numerické diferenciace, které využívají konečné diference. Tedy approximují limitu v definici derivace malými posuny ve vstupních hodnotách diferenciovaných funkcí. [12]

Jednotlivým "odstínům" — konkrétním výpočetním vzorcům — téhle metody se říká diferenciační schémata.

Tip	Abych pravdu řekl, nepodařilo se mi najít zdroj pro konkrétní definici pojmu "diferenciační schéma".

(Konečné) diference prvního řádu / first-order (finite) differences

Nejjednodušší schéma numerické diferenciace. Vychází z definice derivace. [11]

Dopředná diference / forward (finite) difference

$\frac{\partial f}{\partial x} \approx \frac{f ( x + h ) - f ( x )}{h}$
Zpětná diference / backward (finite) difference

$\frac{\partial f}{\partial x} \approx \frac{f ( x ) - f ( x - h )}{h}$
Centrální diference / central (finite) difference

$\frac{\partial f}{\partial x} \approx \frac{f ( x + h ) - f ( x - h )}{2 h}$

kde $h$ je kladné číslo napodobující nekonečně malou změnu (limitu) v definici derivace. Může to být konstanta, může ale být i zvoleno adaptivně.

Tip	Tečna je tak napodobena sečnou.

Richardson extrapolation

Způsob zlepšení rate of convergence iterativních metod. [13]