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