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 }\le 2n{ϵ}_{mach}||L|{|}_{\infty }||U|{|}_{\infty }+\mathcal{O}({ϵ}_{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}AU$ 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||}\le \gamma n^2{ϵ}_{mach}+\mathcal{O}({ϵ}_{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^{\ast }Q||$:

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

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

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

Věta: Nechť $A$ je řádu $n$ a $Q$, $R$ jsou spočtené faktory $QR$ rozkladu. Pak $\frac{||A-QR||}{||A||}\sim {ϵ}_{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}}^{\ast }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í $$A{V}_k=V_{k+1}{H}_{k+1,k},$$ případně $$A{V}_k=V_k{H}_k+h_{k+1,k}{\mathbf{v}}_{\mathbf{k}+1}{{\mathbf{e}}_{\mathbf{k}+1}}^T.$$

TODO Arnoldi a vlastní čísla

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

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

Definice: Successive Overrelaxation (SOR metoda) je $${\mathbf{x}}_{\mathbf{i}}=(1-\omega ){\mathbf{x}}_{\mathbf{i}-1}+\omega D^{-1}(\mathbf{b}-A{\mathbf{x}}_{\mathbf{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}}_{\mathbf{i}}=M^{-1}(\mathbf{b}+N{\mathbf{x}}_{\mathbf{i}-1}).$$

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

Věta (Oldenburg): Nechť $A$ je komplexní čtvercová matice. Pak $$\rho (A)<1⟺A^n⟶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\ne 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\ne i=1}^n|a_{ki}|<|a_{kk}|.$$

Definice: Nechť $(x_i)⟶x^{\ast }$. Řekneme, že posloupnost má řád konvergence $p$, pokud $$\lim \frac{|x^{\ast }-x_{n+1}|}{|x^{\ast }-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^{\ast }\in [a,b]$, $f(x^{\ast })=0$, $f^{\prime }(x^{\ast })\ne 0$. Pak existuje $\delta >0$ takové, že libovolnou počáteční volbu $x_0\in B(x^{\ast },\delta )$ posloupnost získaná Newtonowou metodou kvadraticky konverguje k $x^{\ast }$.

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}}_{\mathbf{i}}={\mathbf{x}}_{\mathbf{i}-1}+{\alpha }_i{\mathbf{d}}_{\mathbf{i}}$$

pro ${\alpha }_i>0$ délku kroku a ${\mathbf{d}}_{\mathbf{i}}$ spádový směr. Metodou největšího spádu rozumíme volbu ${\mathbf{d}}_{\mathbf{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}}_{\mathbf{i}}={\mathbf{x}}_{\mathbf{i}-1}-{\alpha }_i{M}_i\nabla f({\mathbf{x}}_{\mathbf{i}-1}).$$

Pro $M_i=I$ dostáváme metodu největšího spádu, pro $M_i=H_f({\mathbf{x}}_{\mathbf{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)x{L}_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\le x_0<x_1<\cdots <x_n\le 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\to \infty$.

Definice: Nechť $f$ je funkce na $[a,b]$ a $a\le x_0<x_1<\cdots <x_n\le 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^{\prime \prime }(a)=S^{\prime \prime }(b)=0$.

Věta: Pro momenty kubického splinu $M_i=S^{\prime }(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)|\le 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)|\le \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)|\le \frac{1}{12}(b-a{)}^3\max |f^{\prime \prime }(x)|.$$ Pro Simpsonovo pravidlo je $$|{\int }_a^{b}f-Q_S(f)|\le \frac{1}{196}(b-a{)}^4\max |f^{\prime \prime \prime }(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 $$li{m}_{h\to 0_{+}}\Phi (x,y,h)=f(x,y),$$ a je konvergentní, pokud $$\underset{h\to 0_{+}}{\lim }\underset{0\le i\le n}{\max }|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)|\le K{h}^p.$$

Věta: Nechť přírůstková funkce jednokrokové metody $\Phi$ je $L$-lipschitzovská vzhledem k $y$ a metoda je řádu $p$. Pak je $$\underset{0\le i\le n}{\max }|y(x_i)-y_i|\le \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)|\le K{h}^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)!}.$$