# Analiza Numeryczna - notatki
###### tags: `notatki` `anl20`

****
### Zmiennopozycyjna reprezentacja liczb


$x = s \cdot m \cdot 2^{c}$
$s$ - znak liczby
$m$ - mantysa
$2^c$ - cecha

Dla downolnego $x \in \mathbb{R}$, $rd(x)$ jest jego reprezentacją w arytmetyce zmiennopozycyjnej, tj. liczbą będącą najbliżej $x$.

Błąd względny reprezentacji:
$\lvert \frac{rd(x)-x}{x} \rvert \leq 2^{-t}$, gdzie $t$ oznacza liczbę bitów poświęconych na mantysę.

****
### Błędy i uwarunkowanie zadania

- Utrata cyfr znaczących:
- Najczęściej jak odejmujesz od siebie liczby bardzo sobie bliskie.

- Numeryczna poprawność algorytmu:
- Symulujemy działanie algorytmu w arytmetyce zmiennopozycyjnej
- Obliczamy skumulowany błąd
- Jeżeli będziemy w stanie jakoś oszacować z góry ten skumulowany błąd, to algorytm jest numerycznie poprawny.

:::info
Ciężko jest udowodnić, że algorytm jest numerycznie **nie**poprawny.
:::

- Względna zmiana danych:
- $\lvert \frac{(x+\epsilon)-x}{x} \rvert = \lvert \frac{\epsilon}{x} \rvert$

- Względna zmiana wyniku:
- $\lvert \frac{f(x+\epsilon)-f(x)}{f(x)} \rvert$

- Wskaźnik uwarunkowania zadania:
- $Cond(f(x)) = \lvert \frac{f'(x) \cdot x}{f(x)} \rvert$

Zadanie jest **źle uwarunkowane**, jeżeli mała zmiana danych może prowadzić do dużej zmiany wyniku, tzn. jeżeli istnieje takie $x_0$, że $\lim_{x \to x_0} Cond(f(x)) = \infty$

#### Pewnie się przyda

Jestem na 100% pewien, że będą zadania typu "zmień równanie, żeby ograniczyć błędy numeryczne", a wtedy mogą się przydać rozwinięcia Taylora. Wrzucam tu kilka najpopularnijszych, żeby ograniczyć potrzebę szukania:


Kalkulator ze wzorami Taylora:
https://www.symbolab.com
Kalkulator pochodnych z krokami:
https://www.derivative-calculator.net/
Kalkulator z całkami z krokami:
https://www.integral-calculator.com/

****
### Metoda jednokrokowa
****

### Schemat Hornera

****
### Rozwiązywanie równań nieliniowych

#### Metoda bisekcji
Założenia metody bisekcji:
- funkcja $f(x)$ jest ciągła na przedziale $[a, b]$
- na końcach przedziału funkcja ma różne znaki, tj. $f(a) \cdot f(b) \lt 0$

Przebieg algorytmu:
- jeżeli $f(\frac{a+b}{2}) = 0$, lub $\lvert a-b \rvert \lt \epsilon$
- zwróć $\frac{a+b}{2}$
- wpp.
- $x_1 = \frac{a+b}{2}$
- jeżeli $f(a) \cdot f(x_1) \lt 0$
- $b = x_1$
- jeżeli $f(x_1) \cdot f(b) \lt 0$
- $a = x_1$
- powtarzaj dopóki nie osiągniesz rządanej dokładności

Oszacowanie błędu:
- $\lvert x_0 - x_k \rvert \leq \lvert \frac{a-b}{2} \rvert$

#### Metoda Regula falsi

$Regula falsi$ to dziecko metody siecznych oraz metody bisekcji. Łączy te metody i dziedziczy dobre (i złe) cechy obu rodziców.

$Regula falsi$ ma takie same warunki początkowe jak metoda bisekcji:

* Funkcja musi być określona w przedziale $[a,b]$
* Funkcja musi być ciągła w przedziale $[a,b]$
* Na krańcach przedziału $[a,b]$ funkcja musi mieć różne znaki

Gdy te warunki zostaną spełnione będziemy potępować następująco:

* Tworzymy prostą przechodzącą przez punkty $(a, f(a))$ i $(b, f(b))$. Miejsce przecięcia tej prostej z osią OX oznaczamy jako $(c,0)$
* Znajdujemy wartość $c$ dzięki równaniu $c = b - f(b){b-a \over f(b)-f(a)}$.
* Jeśli $|f(c)| < \epsilon$ (gdzie $\epsilon$ jest tolerowanym przez nas błędem) to kończymy działanie i zwracamy $c$.
* Jeśli znak $f(c)$ jest taki sam jak $f(b)$ to za $b$ podstawiamy $c$. W przeciwnym przypadku $c$ podstawiamy za $a$.

Od metody siecznych $regula falsi$ różni się warunkami wstępnymi (metoda siecznych potrzebuje dodatkowego warunku $f'(x) \neq 0$ na przedziale $[a,b]$). W przeciwieństwie do metody siecznych zawsze jest zbieżna. $Regula falsi$ jest jednak znacząco wolniejsza od metody siecznych.

#### Metoda Newtona (metoda stycznych)
Założenia metody Newtona:
- funkcja $f(x)$ ma w przedziale $[a, b]$ **dokładnie** jedno miejsce zerowe
- na końcach przedziału funkcja ma różne znaki, tj. $f(a) \cdot f(b) \lt 0$
- pierwsza i druga pochodna $f(x)$ ma stały znak na przedziale $[a, b]$

Przebieg algorytmu:
- wybieramy punkt startowy $x_1$
- kolejne przybliżenia obliczane są przy pomocy wzoru $x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$

Oszacowanie błędu:
- $\lvert x_0 - x_k \rvert \leq \frac{f(x_k)}{m}$
- $f(x_0) = 0,\ x_0 \in [a, b]$
- $m = min_{x \in [a, b]}\lvert f'(x) \rvert$

:::warning
**Ważne!**
Metoda stycznych nie zawsze jest zbieżna.
Aby mieć pewność, że metoda będzie zbieżna należy odpowiednio dobrać punkt startowy $x_1$:
Weźmy przedział $I = [a, b]$. Jeżeli:
- $\forall_{x \in I}\ f'(x) \neq 0$
- $\forall_{x \in I}\ f''(x) \lt 0$ lub $\forall_{x \in I}\ f''(x) \gt 0$
- $\lvert \frac{f(a)}{f'(a)} \rvert \lt b-a$
- $\lvert \frac{f(b)}{f'(b)} \lvert \lt b-a$

To metoda Newtona jest zbieżna dla downolnego $x \in I$
:::

#### Metoda siecznych
Założenia matody siecznych:
- na końcach przedziału funkcja ma różne znaki, tj. $f(a) \cdot f(b) \lt 0$
- $\dots$

Przebieg algorytmu:
- wybieramy krańce przedziałów $x_0$ i $x_1$
- pierwsze i kolejne przybliżenia obliczane są przy pomocy wzoru $x_{n+1} = x_n - \frac{f(x_n)}{\frac{f(x_n)-f(x_{n-1})}{x_n - x_{n-1}}}$

Oszacowanie błędu:
- Nie wiem, ale się dowiem

:::warning
**Ważne!**
Metoda siecznych nie zawsze jest zbieżna.
Tu podają, że może dojść do rozbieżności przy słabym wyborze $x_1, x_2$, jednak nie jest definiowane co ten wybór charakteryzuje.
http://www.sci.utah.edu/~beiwang/teaching/cs6210-fall-2016/lecture40.pdf
:::

****
### Rząd zbieżności metody
Niech dany będzie ciąg $\{x_n\}$ zbieżny do $\alpha$, tzn. $\lim_{n \to \infty} x_n = \alpha$. Jeżeli istnieją takie $p, C \in \mathbb{R}, C \gt 0$, że $\lim_{n \to \infty} \frac{\lvert x_{n_1}-\alpha \rvert}{\lvert x_n - \alpha \rvert^p} = C$, to $p$ nazywamy *rzędem zbieżności* ciągu $\{x_n\}$, a $C$ *stałą asymptotyczną*.
Dla $p = 1$ i $C \in (0,1)$ mówmy o zbieżności liniowej,
dla $p = 2$ i $C \in \mathbb{R}$ o zbieżności kwadratowej,
dla $p = 3$ i $C \in \mathbb{R}$ o zbieżności sześciennej itd...
Dla $p = 1$ i $C \in \mathbb{R}/(0,1)$ nie wiem co.

****
### Postacie wielomianu

#### Postać potęgowa:
$w(x) =a_{0} + a_{1}x + \dots + a_{n-1}x^{n-1} + a_{n}x^{n}$

#### Postać Newtona
$w(x) = a_0 + \sum_{i=1}^{n}a_i\prod_{j=0}^{i-1}(x-x_j) =\\ = a_{0} + a_{1}(x-x_{1}) + a_{2}(x-x_{2})(x-x_{1}) + \dots + a_{n}(x-x_{n})(x-x_{n-1})\dots(x-x_{1})$

#### Postać Lagrange'a

- $W(x)=\sum _{i=0}^{n}y_{i}\!\cdot \!\prod _{j=0\land j\neq i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}$
- więcej o tej postaci jest w interpolacji

#### Postać Czebyszewa
- Wielomiany Czebyszewa (def. rekurencyjna):
$\begin{cases}
T_{0}(x) = 1 \\
T_{1}(x) = x \\
T_{k}(x) = 2x \cdot T_{k-1}(x) - T_{k-2}(x)
\end{cases}$
- Najważniejsze własności wielomianów Czebyszewa:
- wielomian $T_{k}$ jest dokładnie k-tego stopnia
- wielomiany stopnia parzystego ($T_{2k}$) są funkcjami parzystymi, a wielomiany stopnia nieparzytego ($T_{2k+1}$) są funkcjami nieparzystymi $\to$ $T_{k}(-x) = (-1)^k \cdot T_{k}(x)$
- jeśli $x\in [-1, 1]$ to $T_{k}(x) = cos(k \cdot arccos(x)) \to$ z tego wynika, że zbiór wartości na tym przedziale to $[-1, 1]$
- każdy wielomian możemy zapisać jako kombinację liniową wielomianów Czebyszewa $\to lim{T_{0}, T_{1}, ... , T_{n}} = \Pi_n$
- $T_{k}$ ma dokładnie k pojedyńczych, rzeczywistych miejsc zerowych należących do przedziału $(-1, 1)$
- **Postać wielomianu** (kombinacja liniowa wielomianów Czebyszewa):
- $W(x) = \frac{1}{2}c_{0}T_{0}(x) + c_{1}T_{1}(x) + ... + c_{n}T_{n}(x)$
- $T_{k}$ - wielomiany Czebyszewa
- $c_{k}$ - współczynniki wielomianu postaci Czebyszewa
- Algorytm Clenshawa (zalecany do obliczania wartości wielomianu podanego w postaci Czebyszewa)
- dla $(k = n, n-1, ..., 0):$
- $\begin{cases}
B_{n+2} = 0 \\
B_{n+1} = 0 \\
B_{k} = 2x \cdot B_{k+1} - B_{k+2} + c_{k}
\end{cases}$
- $W(x) = \frac{B_{0} - B_{2}}{2}$

****
### Interpolacje

#### Błąd interpolacji

Oblicza się go wzorem:

$|f(x) - P(x)| = \frac{f^n(\eta)}{n!}\prod_{i=1}^n(x-x_i) \quad$ dla węzłów $x_1,x_2,\dots,x_n$

#### Węzły Czybyszewa

Węzły postaci

$x_i = cos(\frac{2i-1}{2n}), \quad i \in\{1,2,\dots,n\}$

Można je przenieść na dowolny przedział $<a,b>$ za pomocą przekształcenia aficznego:

$x_i = \frac{1}{2}(a+b) + \frac{1}{2}(b-a)cos(\frac{2i-1}{2n})$

Na przedziale $<-1,1>$ są przydatne do minimalizacji błędu wielomianu. Gdy ich używamy to błąd wynosi:

$|f(x) - P(x)| \leq \frac{1}{2^{n-1}n!}max_{\eta \in <-1,1>}|f^n(\eta)|$

Dla przedziału $<a,b>$ będzie to:

$|f(x) - P(x)| \leq \frac{1}{2^{n-1}n!}(\frac{b-a}{2})^nmax_{\eta \in <a,b>}|f^n(\eta)|$

#### Interpolacja wielomianowa Lagrange'a
- dane:
- $x_{0}, x_{1}, ... ,x_{n}$ - parami różne węzły (dla wielomianu stopnia $n$ jest ich $n+1$)
- $y_{0}, y_{1}, ... ,y_{n}$ - odpowiadające im wartości
- warunki:
- $\begin{cases}
L_n \in \Pi_n \\
L_n(x_k) = y_k
\end{cases}$
- rozwiązanie:
- $L_n(x)=\sum _{i=0}^{n}y_{i}\!\cdot \!\prod _{j=0\land j\neq i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}$

- ma zawsze jednoznaczne rozwiązanie
- występuje efekt Rungego

#### Naturalna interpolacyjna funkcja sklejana trzeciego stopnia (NIFS3)
Jest to inne podejście do zagadnienia interpolacji. Dla zadanych węzłów $x_0,x_1,...x_n$ i wartości w nich $y_0,y_1,...y_n$ chcemy znaleźć zbiór wielomianów trzeciego stopnia, z którego i-ty wielomian przechodzi przez punkty $x_{i-1},x_i$, ma w nich pierwszą i drugą pochodną równą odpowiednio pierwszej i drugiej pochodnej wielomianów sąsiednich. Wielomian pierwszy i ostatni ma mieć na zewnętrznych krańcach drugą pochodną równą 0 (założenie konieczne dla jednoznaczności wyniku - stąd nazwa naturalny).

Tak zdefiniowe zadanie ma zawsze dokładnie jedno rozwiązanie, ponieważ aby wyznaczyć $n$ wielomianów stopnia co najwyżej trzeciego potrzeba wyznaczyć $4n$ niewiadomych, z drugiej strony mamy n+1 punktów kontrolnych, oraz informacje o tym, że w punktach łączenia mamy zachować ciągłość wielomianów oraz ich pierwszej i drugiej pochodnej.


Układ $4n$ równań można rozwiązać w prost, ale to niewydajne - $O(n^3)$. Można to zrobić lepiej.

#### Twierdzenie

Dla danych $n\in N$, $a=x_0<x_1<...<x_n=b$ i danej funkcji $f$ określonej w tych węzłach $(y_k=f(x_k))$ zawsze istnieje dokładnie jedna NIFS3.

Niech $x\in [x_{k-1},x_k], (1\leq k\leq n)$, wtedy:
$$s(x)=h_k^{-1}\Big [\frac{1}{6}M_{k-1}(x_k-x)^3+\frac{1}{6}M_{k}(x-x_{k-1})^3 + (f(x_{k-1})-$$$$-\frac{1}{6}M_{k-1}h_k^2)(x_k-x)+(f(x_k)-\frac{1}{6}M_kh_k^2)(x-x_{k-1}) \Big ]$$

Gdzie $H_k:=x_k-x_{k-1}$ oraz $M_k:=s''(x_k)$

Momenty $M_k$ spełniają następującą zależność $(*)$:
$$\lambda_kM_{k-1}+2M_k+(1-\lambda_k)M_{k+1}=6f[x_{k-1},x_k,x_{k+1}]$$

Gdzie $f[x_{k-1},x_k,x_{k+1}]$ to iloraz różnicowy zdefiniowany wcześniej, natomiast współczynniki $\lambda_k:=\frac{h_k}{h_k+h_{k+1}}$

#### Fakt

Zbiór równań $(*)$ można zapisać w postaci macierzy trójprzekątniowej:
$$
\begin{equation}
\begin{bmatrix}
2 & 1-\lambda_1 \\
\lambda_2 & 2 & 1-\lambda_2 \\
& \lambda_3 & 2 & 1-\lambda_3 \\
& & \ddots & \ddots & \ddots \\
& & & \lambda_{n-2} & 2 & 1-\lambda_{n-2} \\
& & & &\lambda_{n-1} & 2 \\
\end{bmatrix}
\begin{bmatrix}
M_1 \\
M_2 \\
M_3 \\
\vdots \\
M_{n-2} \\
M_{n-1} \\
\end{bmatrix} =
\begin{bmatrix}
d_1 \\
d_2 \\
d_3 \\
\vdots \\
d_{n-2} \\
d_{n-1} \\
\end{bmatrix}
\end{equation}
$$

Gdzie $d_k:=6f[x_{k-1},x_k,x_{k+1}]$

Trójprzekątniowy układ równań można rozwiązywać przy pomocy algorytmu:

NIFS3 ma zastosowanie w grafice komputerowej. Mianowicie możemy dzięki niemu w prosty sposób pamiętać krzywe. Niech $\{(x_k,y_k),0\leq k\leq N\}$ będzie zbiorem punktów z krzywej którą chcemy przybliżać. Niech $s_x$ oraz $s_y$ będą NIFS3 spełniające warunki:

$$s_x(t_k)=x_k, s_y(t_k)=y_k\text{, dla } 0\leq k \leq N$$

Wtedy krzywa, której szukamy, dla $t\in[t_o,t_N]$ wyraża się wzorem:
$$\delta(t):=[(s_x(t),s_y(t))]: t_0\leq t\leq t_N]$$

Gdzie można przyjąć, że $t_k:=\frac{k}{N}$

#### Kalkulator do tego
https://tools.timodenk.com/cubic-spline-interpolation

****
### Krzywe Beziera

#### Kombinacja barycentryczna punktów

Nie jest dobrym pomysłem dodawanie punktów po współrzędnych. Zamiast tego korzysta się z kombinacj barycentrycznej. Jest to taka operacja:

$W = \alpha_0W_0 + \alpha_1W_1 + \alpha_1 + \dots + \alpha_nW_n$

Gdzie $\alpha_0 + \alpha_1 + \dots + \alpha_n = 1$, a $W_0,W_1,\dots,W_n \in \mathbb{E}^2$ (są punktami w 2D)

Operacja opisana powyżej jest równoznaczna:

$W = W_0 + \alpha_1(W_1 - W_0) + \alpha_2(W_2 - W_0) + \dots + \alpha_n(W_n - W_0)$

W powyższym równaniu wyróżnione jest $W_0$, jedank można wyróżnić w ten sposób dowolny inny punkt ze zbioru $\{W_i : i\in<0,n>\}$ i rezultat będzie taki sam. Do tego, jeśli $\alpha_0,\alpha_1,\dots,\alpha_n \geq 0$ to $W$ znajduje się w otoczce wypukłej punktów $\{W_i : i\in<0,n>\}$

#### Wielomiany Bernsteina

Wielomiany zdefiniowane takim wzorem:
$B_k^n(x) = {n\choose k}x^k(1-x)^{n-k}$
Ich właściwością charakterystyczną jest, że:
$B_0^n(x) + B_1^n(x) +\dots+B_n^n(x) = 1$
Oraz
$x\in<0,1> \implies B_k^n(x)\in<0,1>$

Te właściwości przyda się, ponieważ wielomiany Bernsteina będą nam dawać współczynniki $\alpha$ w krzywych Beziera.

Wielomiany te mają też tylko jedno maksimum w przedziale $<0,1>$, a dokładnie $x = \frac{k}{n}$

Inne własności:
* $B_k^n(x) = (1-x)B_k^{n-1}(x) + xB_{k-1}^{n-1}(x)$
* $(B_k^n(x))' = n(B_{k-1}^{n-1}(x) - B_k^{n-1}(x))$
* Wielomiany $B_0^n, B_1^n, \dots, B_n^n$ tworzą bazę przestrzeni $\prod_n$

#### Krzywa Beziera

Krzywa opisana równaniem:

$P(t) = B_0^n(t)W_0 + B_1^n(t)W_1 + \dots + B_n^n(t)W_n$

to krzywa Beziera stopnia n. $\{W_i : i\in<0,n>\}$ to jej punkty kontrolne.

Dziedziną krzywej jest przedział $<0,1>$, a zbiorem rozwiązań jest $\mathbb{E}^2$

Właściwości:
* $P(0) = W_0$
* $P(1) = W_n$
* Krzywa zawiera się w otoczce liniowej punktów $\{W_i : i\in<0,n>\}$
* $P'(0) = n(W_1 - W_0)\quad\quad$ (wektor!)
* $P'(1) = n(W_n - W_{n-1})\quad\quad$(wektor!)
* Krzywa Beziera stopnia $n$ może być opisana identycznie przez krzywą stopnia $n+1$. Przez to zawsze możemy traktować dwie krzywe jako będące tego samego stopnia, poniewać możemy podnieść stopień tej niższej.
* Dokonuje się tego poprzez wyznaczenie nowego zestawu punktów kontrolnych za pomocą wzoru:
* $W^{+1}_k = \frac{k}{n+1}W_{k-1} + (1 - \frac{k}{n+1})W_k \quad k\in\{0,1,\dots,n+1\}, W_{-1} = W_{n+1} = 0$
* W zastosowania powyższego wzoru otrzymamy zestaw punktów o mocy o 1 większej. Możemy zastosować go ile razy chcemy, np. żeby wyrównać stopnie krzywych.
* Przekształcenia z jednej krzywej w drugą dokonuje się za pomocą równania:
* $S_\alpha(t) = (1-\alpha)P(t) + \alpha Q(t)\quad$ gdzie $\alpha\in<0,1>$ jest stopniem przejścia z krzywej $P$ w krzywą $Q$

Punkty na krzywej Beziera wyznacza się za pomocą algorytmu de Casteljau.

### Algorytm de Casteljau

Załóżmy, że chcemy znaleźć punkt krzywej $P(\frac{1}{4})$

Interpretacja geometryczna tego algorytmu jest taka, że łączymy odcinkami kolejne punkty kontrolne krzywej $P$ i zaznaczamy na każdym z tych odcinków punkt w $\frac{1}{4}$ jego długości. Traktujemy te punkty jako nasz nowy zestaw punktów kontrolnych - teraz będzie ich o jeden mniej, niż we wcześniejszym zestawie. Powtarzamy algorytm aż do pozostania z jednym punktem. Ten punkt to punkt którego szukaliśmy.

We wzorach wygląda to tak (górny indeks oznacza krok algorytmu):
$W^0_k = W_k$
$W^i_k = (1-t)W_k^{i-1} + tW_{k-1}^{i-1}\quad\quad i\in\{1,2,\dots,n\}\quad k\in\{0,1,\dots\,n-i\}$
Rozwiązaniem jest $W_0^n$

Złożoność tego algorytmu to $O(n^2)$, jednak można go zbić do złożoności liniowej za pomocą schematu Hornera.

Ten algorytm umożliwia też podział krzywej Beziera na dwie krzywe (otrzymywane, jakby oryginalną krzywą przeciąć w poszukiwanym punkcie). Punktami kontrolnymi krzywej na lewo od miejsca przecięcia są punkty $\{W_0^i : i\in\{0,1,\dots,n\}\}$, a na prawo $\{W_i^{n-i} : i\in\{0,1,\dots,n\}\}$

****
### Wielomiany ortogonalne

Ciąg wielomianów $\{P_1, P_2, \dots, P_m\}\ (m \leq N)$ jest ortogonalny względem dyskretnego iloczynu skalarnego $(;)_N$ jeżeli spełnione są nastepujące warunki:
$\begin{cases}
P_k \in \Pi_k/\Pi_{k-1},\ (\Pi_{-1} = \phi, k \in ) \\
(P_i;P_j)_N = 0,\ i \neq j \\
(P_k;P_k)_N \gt 0
\end{cases}$

Nasza definicja iloczynu skalarnego to najczęściej $(f;g)_N = \sum_{k=0}^{N}f(x_k)g(x_k)$

#### Ortogonalizacja Grama-Schmidta:
Wybieramy bazę $n+1$ liniowo niezależnych funkcji. Najprościej:
- $f_0 = 1$
- $f_1 = x$
- $f_2 = x^2$
- $\dots$

$\begin{cases}
P_0(x) = f_0(x) \\
P_k(x) = f_x(x) - \sum_{i=0}^{k-1}\frac{(f_k;P_i)_N}{(P_i;P_i)_N} P_i
\end{cases}$

#### Zależność rekurencyjna:
$\begin{cases}
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)
\end{cases}$

$C_k = \frac{(xP_{k-1};P_{k-1})_N}{(P_{k-1};P_{k-1})_N}\ \ (1 \leq k \leq N)$

$D_k = \frac{(P_{k-1};P_{k-1})_N}{(P_{k-2};P_{k-2})_N}\ \ (2 \leq k \leq N)$

Ta metoda zakłada wybór najprostrzej bazy liniowo niezależnych funkcji.

****
### Aproksymacja średniokwadratowa

#### Dyskretna norma średniokwadratowa
Niech funkcja $f(x)$ będzie określona w punktach $x \in \{x_0, x_1, \dots, x_n\}$. Wtedy deskratna norma średniokwadratowa $\lvert\lvert f \rvert\rvert_2$ wyraża się wzorem $\sqrt{\sum_{k=0}^{N}(f(x_k))^2}$

Podstawowe własności $\lvert\lvert \cdot \rvert\rvert_2$:
- $||f||_2 \geq 0$
- $||f|| = 0 \Leftrightarrow f(x_n) = 0$ dla $k = 0, 1, \dots, N$
- $||\alpha \cdot f||_2 = \alpha \cdot ||f||_2$ dla $\alpha \in \mathbb{R}$
- $||f+g||_2 \leq ||f||_2 + ||g||_2$

#### Zadanie aproksymacji średniokwadratowej
Dla danej funkcji $f$ określonej w punktach $x \in \{x_0, x_1, \dots, x_n\}$ i dla ustalonego zbioru funkcji $\Psi$ (np. $\Pi_k$), najlepiej dopasowanym w sensie aproksymacji średniokwadratowej elementem $\psi^* \in \Psi$ będzie element dla którego $||f-\psi^*||_2 = \min_{\psi \in \psi} ||f-\psi||_2 \equiv \min_{\psi \in \Psi} \sqrt{\sum_{k=0}^{N}(f(x_k) \cdot \psi (x_k))^2}$

#### Metoda znajdowania optymalnego $\psi^* \in \Pi_n$
$\psi^* = \sum_{k=0}^{n}a_k P_k(x)$
$P_k(x)$ - kolejne wielomiany ortogonalne
$a_k = \frac{(f;P_k)_N}{(P_k;P_k)_N},\ k = 0, 1, \dots, n$

****
### Kwadratury
Całkowanie numeryczne. W ten sposób komputery są w stanie policzyć sobie całki.

#### Rząd kwadratury

Mówimy, że kwadratura $K$ jest rzędu $n$ gdy jest dokładna dla
wszystkich wielomianów stopnia mniejszego niż $n$ i nie jest
dokładna dla pewnego wielomianu stopnia $n$.

Jeśli kwadratura jest rzędu przynajmniej $n+1$ to musi być kwadraturą interpolacyjną.

Kwadratura interpolacyjna może być co najwyżej rzędu $2n+2$ (kwadratury Gaussa)

#### Kwadratura liniowa
Każda kwadratura opisywana przez równanie:
$\int_{a}^{b}f(x) = \sum_{k=0}^n A_k f(x_k)$

#### Kwadratura interpolacyjna

Wersja kwadratury liniowej w której współczynniki $A_k$ są otrzymywane w skutek równania:
$A_k = \int_a^b\prod_{i=0, i \neq k}^n\frac{(x-x_i)}{(x_k-x_i)}$

Gdy $f$ ma $(n+1)$ pochodną to błąd kwadratury interpolacyjnej wynosi:

$R_n(f) = \frac{1}{(n+1)!} \int_a^b f^{n+1}(\eta)(x-x_0)(x-x_1)\dots(x-x_n)\quad\quad \eta\in<a,b>$

#### Kwadratura Newtona-Cotesa
Kwadratura interpolacyjna z węzłami równoodległymi. Oznacza to, że
$x_i = a+hi$, gdzie $h = \frac{b-a}{N}$ ($N+1$ to liczba węzłów, $i \in <0,1,\dots,N>$)

Dla $N$ nieparzystych kwadratura ma rząd $N+1$, dla $N$ parzystych rząd to $N+2$

Oznacza się ją jako $Q_n^{NC}(f)$ - taka kwadratura ma $n+1$ równoodległych węzłów.

#### Wzór trapezów
Wzór trapezów to $Q_1^{NC}(f)$
$Q_1^{NC}(f) = \frac{b-a}{2}(f(a)+f(b))$
Błąd metody trapezów:
$R^{NC}_1(f)=\frac{f''(\eta)}{2!}\int_a^b(x-a)(x-b)dx=-\frac{(a-b)^3}{12}f''(\eta)$

#### Wzór Simpsona
Wzór Simpsona to $Q_2^{NC}(f)$
$Q_2^{NC}(f) = \frac{b-a}{6}[f(a)+ f(\frac{a+b}{2}) + f(b)]$
Błąd metody trapezów:
$R^{NC}_2(f)=-\frac{1}{90}(\frac{b-a}{2})^5f^4(\eta)$

### Kwadratury Złożone

Idea - dzielimy przedział całkowania na części i w każdej z nich stosujemy proste kwadratury.

#### Złożony wzór trapezów

Dzielimy przedział na $n$ równych części i w każdej z nich stosujemy wzór trapezów.

$T_n(f)$ - złożony wzór trapezów
$R_n^T(f)$ - błąd złożonego wzoru trapezów

$T_n(f) = \frac{b-a}{2}\sum_{k=0}^n''f(x_k)\quad\quad$($\sum''$ oznacza sumę gdzie pierwszy i ostatni element są dzielone przez 2)
$R_n^T(f) = -(b-a)\frac{h^2}{12}f''(\eta) \approx O(\frac{1}{n^2})$

#### Złożony wzór Simpsona

Dzielimy przedział na $n$ równych części i w każdej z nich stosujemy wzór Simpsona.

$S_n(f)$ - złożony wzór trapezów
$R_n^S(f)$ - błąd złożonego wzoru trapezów

$S_n(f) = \frac{h}{3}(2\sum_{k=0}^m''f(x_{2k}) + 4\sum_{k=1}^mf(x_{2k-1}))$
$R_n^S(f) = -(b-a)\frac{h^4}{180}f^4(\eta) \approx O(\frac{1}{n^4})$

#### Metoda Romberga

Jest to połączenie metody trapezów z metodą Simpsona. Opiera się na zależności między nimi:
$S_n(f) = \frac{4T_n(f) - T_{2n}(f)}{3}$

Tablica Romberga jest tablicą trójkątną dolną składającą się z elementów $T_{k,w}$ gdzie $k$ oznacza numer kolumny, a $m$ - numer wiersza.
Elementy $T_{0,w}$ otrzymuje się równaniem:
$T_{0,w} = \frac{b-a}{2^w}\sum_{i=0}^{2^w}''f(x_i)$
Elementy kolejnych kolumn otrzymuje się wzorem:
$T_{k,w} = \frac{4^kT_{k-1,w+1} - T_{k-1,w}}{4^k - 1}$

Właściwości tablicy Romberga:
* Kwadratury $T_{k,0},T_{k,1},\dots$ to kwadratury rzędu $2k+2$
* (intuicja) Najlepsze przybliżenia dostaje się najdalej na ukos w tablicy od pozycji 0,0

#### Linki na temat kwadratur
https://golinski.faculty.wmi.amu.edu.pl/zemn/lecture04.pdf
http://wazniak.mimuw.edu.pl/index.php?title=MN14#B.C5.82.C4.85d_kwadratur_interpolacyjnych

### Dekompozycja LU

#### Kalkulator:
https://mxncalc.com/lu-factorization-calculator

****
### Spoko linki
- https://www.mimuw.edu.pl/~przemek/przemek1_files/metnum_slajdy.pdf
- http://www.whiskeyo.pl/analiza-numeryczna-l (jak się kliknie na wykład to są notatki)
- https://www.youtube.com/playlist?list=PLnz2d3u-ZJm8KzgEx3plRvOi4CF2IVMDy kurs na yt