**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)!}.$$