# Anl
## Teoria błędów
Błędy:
- błąd względny $|\frac{x-\tilde x}{x}|$
- błąd bezwzględny $|x-\tilde x|$
- liczba cyfr znaczących dokładnych $acc(v, v')= -log_{10} |1 - \frac{v'}{v}|$

Maszynowa reprezentacja liczb
$S\cdot m \cdot 2^c$
S znak $\in \{-, +\}$, m mantysa $\in [\frac{1}{2}, 1)$, c cecha $\in \Bbb Z$

**Zadanie źle uwarunkowane** - względnie mała zmiana danych powoduje względnie dużą zmianę wyniku.

wskażnik uwarunkowania $|\frac{f'(x) \cdot x}{f(x)}|$

**Algorytm numerycznie poprawny** - względnie mało zaburzony wynik dokładny dla względnie mało zaburzonych danych.

## Rozwiązywanie równań nieliniowych

#### Metoda bisekcji
$I_k = [a_k, b_k]$
$m_{k+1} = \frac{a_k+b_k}{2}$
$f(m_{k+1}) == 0$ -----> :)
$f(m_{k+1}) < 0$ --------> $I_k = [m_{k+1}, b_k]$
$f(m_{k+1}) > 0$ --------> $I_k = [a_k, m_{k+1}]$

#### Metoda Newtona
puszczamy styczną z $f(x_0)$, jej przecięcie z osią OX nazywamy $x_1$ itd.,
wzor - $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$,
warunki stopu:
- wykonaliśmy ustaloną liczbę iteracji,
- $|f(x_n)| < \epsilon$,
- kolejne ileś tam iteracji zwraca to samo.

#### Metoda siecznych:
z $f(x_0)$ i $f(x_1)$ puszczamy sieczną i w miejsce jej przecięcia z OX nazywamy $x_2$ itd.,
wzor - $x_{n+1} = x_n - \frac{f(x_n)}{\frac{f(x_n)- f(x_{n-1})}{x_n-x_{n-1}}}$,
warunki stopu:
- wykonaliśmy ustaloną liczbę iteracji,
- $|f(x_n)| < \epsilon$,
- kolejne ileś tam iteracji zwraca to samo.

#### wykładnik zbieżności ciągu
p, takie że $\lim_{x \to \infty} \frac{|x_{n+1} - \alpha|}{|x_{n} - \alpha|^p} = c$
$F'(\alpha) = 0, F''(\alpha), ..., F^{(p-1)}(\alpha) = 0, F^{(p)}(\alpha) \neq0$

## Interpolacja
#### Postacie:
- potęgowa $\qquad$ $w(x) = a_0 + a_1 \cdot x+ a_2 \cdot x^2 + ... + a_n \cdot x^n$
- schemat Hornera $\qquad a_0 + x(a_1 + x(a_2 + ... + x(a_{n - 1} + x \cdot a_n) ... )$
- Newtona $\qquad \sum ^n _{i = 0} b_i p_i (x) \quad (p_i = (x - x_0)(x - x_1)...(x - x_i))$
uogólniony schemat Hornera $w_n = b_n, \quad w_k = (x - x_k)w_{k+1} + b_k \qquad (k=n-1, n-2, ..., 0)$
- postać Czebyszewa $\qquad w(x) = \frac{1}{2}c_0 T_0(x) + c_1 T_1(x) + ... + c_n T_n(x)$
$T_0(x) = 1$
$T_1(x) = x$
$T_k(x) = 2xT_{k-1}(x) - T_{k-2}(x)$
dla $x \in [-1, 1] \quad T_n(x) = cos(n \cdot arcos(x))$

#### Algorytm Clenshawa
$B_{n+1} = B_{n+2} = 0$
$B_k = 2x B_{k+1} - B_{k+2} + c_k$
$w(x) = \frac{B_0 - B_2}{2}$

#### Lagrange

$L_n(x) =\sum _{k=0} ^n \lambda_k(x)y_k$
$\lambda_k(x) = \prod ^n _{i = 0, i \neq k} \frac{x-x_i}{x_k - x_i}$

#### Newton
$L_n(x) \sum _{k=0} ^n f[x_0, x_1, ..., x_k] \cdot p_k(x)$

$p_k(x) = \prod ^{k-1} _{i = 0} (x-x_i)$

Ilorazy różnicowe
$f[x_k, x_{k+1}, ..., x_l] = \frac{f[x_{k+1}, x_{k+2}, ..., x_l] - f[x_k, x_{k+1}, ..., x_{l-1}]}{x_l - x_k}$

$x_0 \quad f(x_0)$
$x_1 \quad f(x_1) \quad f[x_0, x_1]$
$x_2 \quad f(x_2) \quad f[x_1, x_2] \quad f[x_0, x_1, x_2]$
...
$x_n \quad f(x_n) \quad f[x_{n-1}, x_n] \quad f[x_{n-2}, x_{n-1}, x_n] \quad ... \quad f[x_0, x_1, ..., x_n]$

węzły Czebyszewa $x_k = cos(\frac{2k+1}{2n+2} \pi)$

#### Błąd interpolacji

$max _{a \le x \le b} |f(x) - L_n(x)| \le \frac{1}{(n+1)!} \cdot max _{a \le x \le b} |f^{(n+1)}(x)| \cdot |p_{n+1}(x)|$

#### NIFS3
S(x) = \begin{cases}
S_1, & \text{$x_0 \le x \le x_1$} \\
S_2, & \text{$x_1 \le x \le x_2$} \\
... \\
S_n, & \text{$x_{n-1} \le x \le x_n$}
\end{cases}

Warunki:
- $S(x_k) = y_k$,
- $S, S', S'' \in C[a, b]$
- S''(a) = S''(b) = 0.

## Krzywe

#### Kombinacja Barycentryczna

$\sum _{i=0} ^n \alpha_i W_i \qquad \sum _{i=0} ^n \alpha_i = 1$

#### Wielomiany Bernsteina

$B ^n _k(t) = \binom{n}{k} t^k (1-t)^{n-k}$


#### Krzywe Beziera

$P_n(t) = \sum _{i=0} ^n B _k ^n (t) W_i$

## Aproksymacja
$||f - w^*||_2 = min_{w \in \chi} \sqrt{\sum _{i=0} ^n (f(x_i) - w(x_i))^2}$

#### Norma średniokwadratowa
$||f||_2 = \sqrt{\sum _{i=0} ^n (f(x_i))^2}$

#### iloczyn skalarny
$<f, g> = \sum _{i=0} ^n f(x_i) g(x_i)$
funkcje f i g sa ortogonalne <=> $<f, g> = 0$

#### Wielomiany ortogonalne
$P_0(x)=1$
$P_1(x)=x - c_1$
$P_k(x)= (x - c_k)P_{k-1}(x) - d_k P_{k-2}(x)$
$c_k = \frac{<xP_{k-1}, P_{k-1}>}{<P_{k-1}, P_{k-1}>}$
$d_k = \frac{<P_{k-1}, P_{k-1}>}{<P_{k-2}, P_{k-2}>}$

#### Wzór
$w^* _n (x) = \sum _{k=0} ^m a_k P_k(x)$
$a_k = \frac{<f, P_k>}{<P_k, P_k>}$

#### Błąd
$||f - w^*||_2 = \sqrt{||f||_2 - \sum _{i=0} ^n \frac{<f, P_k>^2}{<P_k, P_k>}}$

## Kwadratury

$Q_n(f) = \sum _{k = 0} ^n A_k f(x _k)$

#### Rząd = r
$\forall_{w \in \pi_{r-1}} Q_n(w) = \int _a ^b w(x)dx \quad$ i $\quad\exists_{v \in {\pi_{r} - \pi_{r-1}}} Q_n(v) \neq \int ^b _a v(x) dx$
rząd $\leq 2n + 2$

#### interpolacyjna

$A_k = \int _a ^b \prod ^n _{j= 0, j \neq k} \frac{x-x_j}{x_k-x_j}dx$

#### Błąd interpolacyjnej
$\frac{1}{(n+1)!}\int_a^b f^{(n+1)}(\eta_{n, x})(x-x_0)(x-x_1)...(x-x_n)dx$

#### Newton-Cotes
interpolacyjna z równoodległymi węzłami

$A_k = \frac{(-1)^{n-k} \cdot h}{k!(n-k)!}\int _0 ^n \prod ^n _{j= 0, j \neq k} (t-j)dx$

rząd = n + 1 dla nieparzystych i n + 2 parzystych
#### Wzór trapezów
$Q_1 ^{NC}(f) = \frac{b-a}{2}(f(a) + f(b))$
$R_1 ^{NC}(f) = n\frac{-h^3}{12}f''(\eta)$

#### Złożone trapezy
$T_n(f) = h \sum _{k=0}^n'' f(t_k)$
$R_n^T (f) = \frac{-h^3}{12}f''(\eta)$

#### Wzór Simsona

$Q_2 ^{NC}(f) = \frac{b-a}{6}(f(a) + 4 f(\frac{a+b}{2}) + f(b))$
$R_2 ^{S}(f) = \frac{-1}{90} h^5 f^{(4)}(\alpha)$

#### Złożony Simson

$S_n (f) = \frac{h}{3}(2\sum^{n/2}_{k=0}''f(t_{2k}) + 4\sum^{n/2}_{k=1}f(t_{2k-1}))$
$R_n ^S(f) = \frac{a-b}{180} f^{(4)}(\alpha)$

$S_n(f) = \frac{4T_n(f)-1 \cdot T_{n/2}(f)}{4 - 1}$

#### Metoda Romberga

$n = 2^k \quad h_k = \frac{b-a}{n} \quad x_i = a + i h_k$
$T_{0,k} = h_k \sum _{i=0} ^{2^k}'' f(x_i)$
$T_{m,k} = \frac{4^mT_{m-1, k+1} - 1 \cdot T_{m-1, k}}{4^m -1}$

$T_{m,0}, T_{m, 1}, ...$ są rzędu 2m+2