Definice: Nechť $D$ je množina přípustných dat a $U$ úloha definovaná pro vstupy z $D$. Řekneme, že $U$ je korektní ve smyslu Hadamarda, pokud pro každé $d \in D$ existuje právě jedno řešení $U(d)$ a $U$ je v jistém smyslu spojité na $D$. Pokud úloha není korektní, říkáme, že je ill-posed.

Definice: O úloze $U$ na množině dat $D$ řekneme, že je dobře podmíněná, pokud pro libovolné $d \in D$, $d + \Delta d \in D$, $\frac{||\Delta d||}{||d||} << 1$, platí $\frac{||U(d+\Delta d) - U(d)||}{||U(d)||} <<1$. V opačném případě je úloha špatně podmíněná.

Definice: Nechť $D$ je množina dat a $f$ je výpočetní schéma dané úlohy. Řekneme, že algoritmus $f$ je zpětně stabilní, pokud pro libovolné $d \in D$ existuje $\Delta d \in D$ takové, že $\frac{||\Delta d||}{||d||} << 1$ a $f(d + \Delta d) = \text{FPA}( f(d) )$.

Věta: Nechť $L$, $U$ jsou FPA výsledky Gaussovy eliminace matice $A$ řádu $n$. Pak existuje $\Delta A$ řádu $n$ taková, že $A+\Delta A = LU$ a $$||\Delta A||_{\infty} \leq 2n \epsilon_{mach} ||L||_{\infty} ||U||_{\infty} + \mathcal{O}(\epsilon_{mach}^2).$$

Věta: $LU$ rozklad s pivotací je podmínečně zpětně stabilní, tj. pokud je vstupní matice $A$ řádu $n$ a vypočtené faktory $L$,$U$, pak je algoritmus zpětně stabilní pro malý růstový faktor $\frac{||U||_{\infty}}{||A||_{\infty}}$.

Věta (Schurova pro reálný rozklad): Nechť $A$ je matice řádu $n$. Pak existuje $U$ ortogonální taková, že $U^{T} A U$ je kvazihorní, tj. je horní trojúhelníková po blocích velikosti 1x1 a 2x2.

Věta (Wilkinson, Turing): Nechť $A$ je komplexní matice a $U$ je elementární Givensova rotace nebo Householderova reflexe. Pak existuje $\Delta A$ taková, že $U(A+\Delta A) = \text{FPA}(UA)$ a $$\frac{||\Delta A||}{||A||} \leq \gamma n^2 \epsilon_{mach} + \mathcal{O}(\epsilon_{mach}^2)$$

pro $\gamma$ kladnou konstantu.

Věta: Nechť $A$ je řádu $n$, $Q$, $R$ jsou spočtené faktory $QR$ rozkladu. Pak platí následující asymptotická chování pro ztrátu ortogonality $E_Q = ||I - Q^*Q||$:

• CGS: $E_Q \sim \kappa^2(A) \epsilon_{mach}$

• MGS: $E_Q \sim \kappa(A) \epsilon_{mach}$

• ICGS, HH, Giv: $E_Q \sim \epsilon_{mach}$

Věta: Nechť $A$ je řádu $n$ a $Q$, $R$ jsou spočtené faktory $QR$ rozkladu. Pak $\frac{||A-QR||}{||A||} \sim \epsilon_{mach}$.

Definice: Uvažujme nekompatibilní úlohu $A\mathbf{x} = \mathbf{b}$. Metodou nejmenších čtverců (LSM) rozumíme metodu perturbování $\mathbf{b}$. Metodou úplných nejmenších čtverců (TLSM) rozumíme perturbování $A$ i $\mathbf{b}$. Data Least Squares (DLS) rozumíme perturbování $A$. Škálovanou úplnou metodou nejmenších čtverců rozumíme třídu metod danou $\gamma \in (0, \infty)$, při níž se perturbuje $A$ i $\mathbf{b}$ a minimalizuje se $||(\gamma \Delta\mathbf{b} \mid \Delta A)||$.

TODO Řešení LSM

Definice: Pro vektor $\mathbf{v}$ a matici $A$ definujeme Rayleighův podíl jako $$\frac{\mathbf{v}^* A \mathbf{v}}{||\mathbf{v}||^2}.$$

Definice: Pro matici $A$ rozumíme shiftováním použití mocninné metody na matice $(A - \rho I)^{-1}$ pro nějaké $\rho$.

Definice: $k$-tým Krylovovým prostorem matice $A$ a vektoru $\mathbf{v}$ rozumíme prostor $$\mathcal{K}_k (A, \mathbf{v}) := \text{LO} \{\mathbf{v}, A\mathbf{v}, \dots, A^{k-1}\mathbf{v}\}.$$

Stupněm vektoru k matici rozumíme nejmenší $l$ takové, že $\mathcal{K}_{l} = \mathcal{K}_{l+1}$ (tehdy je prostor $A$-invariantní).

Věta: Pro Arnoldiho proces platí $$AV_k = V_{k+1}H_{k+1,k},$$ případně $$AV_k = V_k H_k + h_{k+1,k} \mathbf{v_{k+1}} \mathbf{e_{k+1}}^T.$$

TODO Arnoldi a vlastní čísla

Definice: Jacobiho metodou rozumíme $$\mathbf{x_i} = \mathbf{x_{i-1}} + D^{-1} (\mathbf{b} - A\mathbf{x_{i-1}}).$$

Definice: Gauss-Seidelovou metodou rozumíme $$\mathbf{x_i} = \mathbf{x_{i-1}} + (D-L)^{-1} (\mathbf{b} - A\mathbf{x_{i-1}}).$$

Definice: Successive Overrelaxation (SOR metoda) je $$\mathbf{x_i} = (1-\omega)\mathbf{x_{i-1}} + \omega D^{-1} (\mathbf{b} - A\mathbf{x_{i-1}})$$

pro $\omega \in (0,2)$ relaxační parametr.

Definice: Obecnou stacionární iterační metodou rozumíme pro nějaké štěpení $A = M-N$ a $M$ regulární $$\mathbf{x_i} = M^{-1} (\mathbf{b} + N\mathbf{x_{i-1}}).$$

$M^{-1}N$ nazýváme iterační matice.

Věta (Oldenburg): Nechť $A$ je komplexní čtvercová matice. Pak $$\rho(A) < 1 \iff A^n \longrightarrow O.$$

Věta (Geršgorin): Nechť $A$ je komplexní matice řádu $n$ a $$D_{k} = \{z \in \mathbb{C} \mid |z - a_{kk}| < \sum_{k \not = i=1}^n |a_{ki}|\}$$

je $k$-tý Geršgorinův kruh. Pak $\sigma(A) \subset \bigcup_{i=1}^n D_i$.

Definice: Řekneme, že $A$ řádu $n$ je ostře diagonálně dominantní, pokud pro každé $k$ platí $$\sum_{k \not = i=1}^n |a_{ki}| < |a_{kk}|.$$

Definice: Nechť $(x_i) \longrightarrow x^$. Řekneme, že posloupnost má řád konvergence $p$, pokud $$\lim \frac{|x^-x_{n+1}|}{|x^*-x_n|} \in (0, \infty).$$

Řekneme, že metoda je řádu $p$, pokud všechny posloupnosti dané metody jsou řádu alespoň $p$ a alespoň jedna posloupnost má řád přesně $p$.

Věta: Nechť $f \in \mathcal{C}^2 ([a,b])$, $x^* \in [a,b]$, $f(x^) = 0$, $f'(x^) \neq 0$. Pak existuje $\delta > 0$ takové, že libovolnou počáteční volbu $x_0 \in B(x^, \delta)$ posloupnost získaná Newtonowou metodou kvadraticky konverguje k $x^$.

TODO Zbytek Newtona a metoda pevného bodu

Definice: O $\mathbf{d}$ řekneme, že je to spádový směr $f$ v $\mathbf{a}$, pokud $$\exists \delta > 0 \forall \lambda \in (0, \delta): f(\mathbf{x} + \lambda \mathbf{d}) < f(\mathbf{x}).$$ Metodou spádových směrů obecně rozumíme $$\mathbf{x_i} = \mathbf{x_{i-1}} + \alpha_i \mathbf{d_i}$$

pro $\alpha_i > 0$ délku kroku a $\mathbf{d_i}$ spádový směr. Metodou největšího spádu rozumíme volbu $\mathbf{d_i} = \nabla f(\mathbf{x})$. Metodou optimálního kroku / line search rozumíme hledání optimálního $\alpha_i$ v každém kroku.

Definice: Obecnou metodou hledání minima rozumíme $$\mathbf{x_i} = \mathbf{x_{i-1}} - \alpha_i M_i \nabla f(\mathbf{x_{i-1}}).$$

Pro $M_i = I$ dostáváme metodu největšího spádu, pro $M_i = H_{f}(\mathbf{x_{i-1}})$ (Hessovu matici) Newtonovu metodu.

Věta: Pro monické Legendreovy polynomy na $[-1,1]$ a kanonický skalární integrální součin (bez váhové funkce) platí rekurence $$(n+1)L_{n+1}(x) = (2n+1)xL_n(x) - n L_n(x).$$

Definice: Čebyševovy polynomy jsou dány vztahem $T_n(x) = \cos(n \arccos x)$, zároveň je lze získat ortogonalizací na $[-1,1]$ vzhledem k váhové funkci $w(x) = (1-x^2)^{-\frac{1}{2}}$.

Věta (Cauchy): Nechť $f \in \mathcal{C}^{n+1}([a,b])$, $a \leq x_0 < x_1 < \dots < x_n \leq b$, $L_{n}$ je Lagrangeův interpolační polynom. Pak pro každé $x \in [a,b]$ existuje $\xi \in [a,b]$ takové, že $$f(x) - L_n(x) = \frac{1}{(n+1)!} f^{(n+1)}(\xi) \prod_{i=0}^n (x-x_i).$$

Věta: Nechť $f$ je lipschitzovská na $[a,b]$ a $D_n$ je posloupnost zjemňujících se dělení na $[a,b]$, $D_n$ má jako dělicí body kořeny Čebyševova polynomu řádu $n$ na $[a,b]$. Pak Lagrangeův interpolační polynom $L_n$ konverguje stejnoměrně k $f$ na $[a,b]$ pro $n \rightarrow \infty$.

Definice: Nechť $f$ je funkce na $[a,b]$ a $a \leq x_0 < x_1 < \dots < x_n \leq b$. Přirozeným kubickým interpolačním splinem rozumíme interpolaci pomocí funkce $S$ třídy $\mathcal{C}^2([a,b])$, která je na každém dělicím intervalu $[x_i, x_{i+1}]$ kubická a $S''(a) = S''(b) = 0$.

Věta: Pro momenty kubického splinu $M_i = S'(x_i)$ s dělicím krokem $h$ rovnoměrného dělení platí $$M_{i-1} + 4M_i + M_{i+1} = \frac{6}{h^2} (f(x_{i-1} - 2f(x_i) + f(x_{i+1})).$$

Věta: Nechť $(x_i){i=0}^n$ je dělení $[a,b]$, $h = \max{x_i - x{i-1}}$, $f$ je třídy $\mathcal{C}^4([a,b])$ a $S$ je interpolační kubický spline. Pak pro každé $k \in \{0,1,2\}$ existuje $c_k \in \mathbb{R}$ taková, že $$\max |f^(k)(x) - S^(k) (x)| \leq c_k h^{4-k} \max |f^{(4)} (x)|.$$

Navíc již spojitost $f$ zaručuje konvergenci splinu k $f$ pro zjemňování dělení jdoucí normou k nule.

Definice: Obdelníkovým pravidlem rozumíme $$Q_o (f) = (b-a) f(\frac{a+b}{2}).$$

Definice: Newton-Cotesovými kvadraturními vzorci rozumíme kvadratury pomocí Lagrangeových interpolačních polynomů na rovnoměrném dělení $[a,b]$.

• Pro $n=1$ lichoběžníkové pravidlo $$Q_L(f) = \frac{b-a}{2}(f(a)+f(b))$$

• Pro $n=2$ Simpsonovo pravidlo $$Q_S (f) = \frac{b-a}{6}(f(a) + 4f(\frac{a+b}{2}) + f(b))$$

Definice: Algrebraickým řádem kvadratury $Q$ rozumíme $k$ takové, že pro libovolný polynom $p$ řádu nejvýše $k$ platí $Q(p) = \int_{a}^{b} p(x) dx$.

Věta: Pro dělení $(x_i)_{i=0}^n$ a $n$ liché má Newton-Cotesova metoda řád $n$, pro $n$ sudé má řád $(n+1)$.

Věta: Nechť $Q$ je lagrangeovská kvadratura s obecnými uzly $x_0, \dots, x_n$ a $f \in \mathcal{C}^{n+1}([a,b])$. Pak $$|\int_a^b f - Q(f)| \leq \frac{1}{(n+1)!} \max |f^{(n+1)}(x)| \int_a^b \prod_{i=0}^n |x-x_i| dx.$$ Pro lichoběžníkové pravidlo je $$|\int_a^b f - Q_L(f)| \leq \frac{1}{12}(b-a)^3 \max |f''(x)|.$$ Pro Simpsonovo pravidlo je $$|\int_a^b f - Q_S(f)| \leq \frac{1}{196} (b-a)^4 \max |f'''(x)|.$$

TODO Gaussova kvadratura

Definice: Eulerovou metodou rozumíme explicitní schéma $$y_{n+1} = y_n + hf(x_n, y_n).$$ Heunovou metodou rozumíme implicitní schéma $$y_{n+1} = y_n + \frac{1}{2}h(f(x_n,y_n) + f(x_{n+1},y_{n+1}).$$

Definice: Přírůstkovou funkcí jednokrokové metody rozumíme funkci $\Phi$ odpovídající obecnému jednokrokovému schématu $$\frac{y_{n+1} - y_n}{h} = \Phi(x_n, y_n, h).$$

Definice: Jednokroková metoda je konzistentní, pokud $$lim_{h \to 0_{+}} \Phi(x,y,h) = f(x,y),$$ a je konvergentní, pokud $$\lim_{h \to 0_{+}} \max_{0\leq i \leq n} |y(x_i) - y_i| = 0.$$

Definice: Globální chybou jednokrokové metody rozumíme $$e_n := y(x_n) - y_n.$$ Lokální diskretizační chybou jednokrokové metody rozumíme $$\tau(x,h) := \frac{y(x+h) - y(x)}{h} - \Phi(x,y(x),h).$$

Věta: Jednokroková metoda je konzistentní právě tehdy, když pro každé $x \in [a,b]$ je $\lim_{h \to 0_+} \tau(x,h) = 0$.

Definice: Řekneme, že jednokroková metoda je řádu $p$, pokud $$\exists K > 0 \exists \delta > 0 \forall x \in [a,b] \forall h \in (0, \delta): |\tau(x,h)| \leq Kh^p.$$

Věta: Nechť přírůstková funkce jednokrokové metody $\Phi$ je $L$-lipschitzovská vzhledem k $y$ a metoda je řádu $p$. Pak je $$\max_{0 \leq i \leq n} |y(x_i) - y_i| \leq \frac{K}{L}(e^{L(b-a)}-1) h^p.$$

Věta: Nechť $\Phi$ je lipschitzovská přírůstková funkce v $y$. Pak je metoda konzistentní právě tehdy, když je konvergentní.

Definice: Obecná Runge-Kuttova metoda ($S$-stage Method) je dána přírůstkovou funkcí $$\Phi(x,y,h) = \sum_{i=1}^S w_i K_i,$$ kde $$K_j = f(x+\alpha_j h, y+ \sum_{i=1}^{j-1} \beta_{ji} h K_i)$$

a $\alpha_i, \beta_{ij}, w_i$ jsou vhodné konstanty.

Definice: Metoda polovičního kroku jednokrokové metody je aposteriorní odhad $$y_{2n}^{h/2} - y_n^h \sim K (\frac{h}{2})^p (2^p - 1),$$ z něhož lze určit neznámé $K$.

Definice: $k$-krokovou metodou rozumíme schéma $$\sum_{i=0}^k \alpha_i y_{n+i} = h \sum_{i=0}^k \beta_i f_{n+i},$$

kde $f_{j} := f(x_j, y_j)$.

Věta: Pro obecnou funkci vícekrokové metody $$G(z) = \frac{1}{\alpha_k} \sum_{i=0}^{k-1} (h \beta_i f_{n+i} - \alpha_i y_{n+i}) + h \frac{\beta_k}{\alpha_k} f(x_{n+k}, z)$$

existuje $h > 0$ takové, že $G$ je kontrakce, a tedy pro libovolnou počáteční volbu $z_0$ posloupnost $z_{i+1} = G(z_i)$ konverguje k pevnému bodu $y_{n+k}$.

Definice: Adams-Bashforthovy metody jsou vícekrokové explicitní metody dané extrapolací do $x_{n+1}$ polynomem spočteným na $x_{n-k+1}, \dots, x_n$ a následnou aproximací integrálu $\int_{x_n}^{x_{n+1}} f(x,y(x)) dx$.

Definice: Adams-Moultonovy metody jsou vícekrokové implicitní metody dané interpolací polynomem spočteným na $x_{n-k+1}, \dots, x_n$ a $x_{n+1}$ s neznámým $y_{n+1}$ a následnou aproximací integrálu $\int_{x_n}^{x_{n+1}} f(x,y(x)) dx$.

Definice: Lokální diskretizační chybou vícekrokové metody rozumíme $$\tau(x,h) := \frac{1}{h} \sum_{i=0}^k \alpha_i y(x+ih) - \sum_{i=0}^k \beta_i f(x+ih, y(x+ih)).$$

Řekneme, že metoda je řádu $p$, pokud $$\exists K > 0 \exists \delta >0 \forall x \in [a,b] \forall h \in (0,\delta): |\tau(x,h)| \leq Kh^p.$$

Věta: Vícekroková metoda je řádu $p$ právě tehdy, když $\sum_{i=0}^k \alpha_i = 0$ a zároveň $$\forall r \in \{1,\dots,p\}: \sum_{i=0}^k \frac{i^r \alpha_i}{r!} = \sum_{i=0}^k \frac{i^{r-1} \beta_i}{(r-1)!}.$$