###### tags: `Analiza Numeryczna (L)`

# Lista 11

## 1

Pokażę, że dla dowolnej bazy funkcji, po zastosowaniu ortogonalizacji Grama-Schmidta dla dowolnych $i,j$ takich, że $i \neq j$ zachodzi $<g_i, g_j> = 0$

Dowód przeprowadzę przez indukcję:

**1$^\circ$** dla zbioru funkcji $\{f_1, f_2\}$
$g_1 = f_1$
$g_2 = f_2 - \frac{<f_2,g_1>}{<g_1,g_1>}g_1$
$<g_1,g_2> = <g_1, f_2 - \frac{<f_2,g_1>}{<g_1,g_1>}g_1>=<g_1,f_2> - <g_1, \frac{<f_2,g_1>}{<g_1,g_1>}g_1>=$
$=<g_1,f_2> - \frac{<f_2,g_1>}{<g_1,g_1>}<g_1, g_1>=<g_1,f_2> - <f_2,g_1> =$
$=<g_1,f_2> -<g_1,f_2>=0$

**2$^\circ$**
Weźmy bazę funkcji $\{f_1, f_2, ..., f_n\}$ i załóżmy, że zbiór $\{g_1, g_1, ... , g_{n-1}\}$ jest ortogonalny. Wtedy

$g_n = f_n - \displaystyle\sum_{i=1}^{n-1}\frac{<f_n,g_i>}{<g_i,g_i>}g_i$

Weźmy dowolną funkcję $g_j$, $j \neq n$
$<g_n, g_j> = <g_j, f_n - \displaystyle\sum_{i=1}^{n-1}\frac{<f_n,g_i>}{<g_i,g_i>}g_i> = <g_j, f_n> - <g_j, \displaystyle\sum_{i=1}^{n-1}\frac{<f_n,g_i>}{<g_i,g_i>}g_i>=$
$=<g_j, f_n> - \displaystyle\sum_{i=1}^{n-1}\frac{<f_n,g_i>}{<g_i,g_i>}<g_j,g_i>=$ **Z założenia indukcyjnego:**
$=<g_j, f_n> - \frac{<f_n,g_j>}{<g_j,g_j>}<g_j,g_j>=$
$=<g_j, f_n> - <f_n,g_j>=$
$=<g_j, f_n> - <g_j,f_n>=0$

Na podstawie indukcji matematycznej pokazałem, że teza zachodzi.

## 2
Wiemy, że wielomiany $P_0, P_1, ... , P_{k-1}$ tworzą bazę wielomianów stopnia maksymalnie $k-1$. Z tego wynika, że w można zapsiać jako kombinację liniową tych wielomianów.

$w=\alpha_0\times P_0 + \alpha_1\times P_1 + ... + \alpha_{k-1}\times P_{k-1}$

$<w,P_k> = <P_k, \displaystyle\sum^{k-1}_{i=0}\alpha_i\times P_i>=$

$=\displaystyle\sum^{k-1}_{i=0}\alpha_i\times<P_k,P_i>= \displaystyle\sum^{k-1}_{i=0}\alpha_i\times0=0$

## 4

$<P_j,P_j>=\displaystyle\sum_{i=0}^NP_j^2(x_i)$ N+1 mnożeń, N dodawań, czyli wykonanie takiego iloczynu skalarnego zajmuje N+1 mnożeń i N dodawań

$<xP_j,P_j>=\displaystyle\sum_{i=0}^Nx_iP_j^2(x_i)$ N+1 mnożeń i N dodawań (obliczenia te wykonam po tych wyżej, dlatego wyniki $<P_j,P_j>$ zapisuję, przez co, aby obliczyć tę wartość tylko domnażam wyniki przez $x_i$. Wyniki tego działania również zapisuje, ponieważ przydadzą się w obliczeniach $d_k$)

Najpierw obliczam $P_0$ i $P_1$

$P_0(x)=1$ 0 instrukcji
$P_1(x)=x-c_1=x-\frac{<xP_0,P_0>}{<P_0,P_0>}$ 4N + 3 instrukcji i jedno odejmowanie daje 4N + 4 instrukcji

($<P_0,P_0>$ w N + 1 mnożeń, N dodawań, $<xP_0,P_0>$ w N + 1 mnożeń, N dodawań oraz jeszcze jedno dzielenie daje razem 4N + 3 instrukcji)

potem kolejne wartości $c_k = \frac{<xP_{k-1},P_{k-1}>}{<P_{k-1},P_{k-1}>}$ podobnie jak wyżej w 4N + 3 instrukcji

wartości $d_k = \frac{<P_{k-1},P_{k-1}>}{<P_{k-2},P_{k-2}>}$ można policzyć wykonując tylko jedno dzielenie, korzystając z poprzednio wyliczonych wartości.

oraz trzeba pamiętać, żeby policzyć kolejne wartości $P_j(x_i)$ dla kolejnego j i dla każdego i, co zajmuje ze wzoru rekurencyjnego 2N mnożeń i 2N odejmowań za każdy kolejny wielomian.

$P_0(x)=1$ 0 instrukcji
$P_1(x)=x-c_1=x-\frac{xP_0,P_0}{P_0,P_0}$ 4N + 4 instrukcji

$P_k(x)=(x-c_k)P_{k-1}(x)-d_kP_{k-2}(x)$
Aby to policzyć musimy policzyć $c_k$ czyli 4N + 3, $d_k$ czyli 1 instrukcja, do tego dochodzą 2 odejmowania i 2 mnożenia co daje razem 4N + 8 instruckji

Koszt oblczenia $P_0, P_1, ... , P_n$ wynosi
$0$ dla n = 0
$(4N + 8)\times(n-1) + 4N+4 + (n-1)\times(2N + 2N)=(n-1)\times(8N + 8)+4N+4$ dla $n > 0$

dodatkowo trzeba doliczyć obliczenie wartości $P_n(x)$ (przy okazji obliczmy wartości $P_0, P_1, ... , P_{n-1}$), które można obliczyć rekurencyjnie wykonując $(n-1)\times(2 + 2) + 1 = 4n - 3$ operacji (2n -1 odejmowań i 2n - 2 mnożeń). Czyli łącznie trzeba wykonać $(n-1)\times(8N + 8)+4N+4n + 1$ instrukcji dla n > 0

## 5
$\displaystyle\sum^m_{k=0}a_kQ_k(x)=\displaystyle\sum_{k=0}^m (B_k-(x-c_{k+1})b_{k+1} + d_{k+2}B_{k+2})Q_k=$
$=\displaystyle\sum_{k=0}^mB_kQ_k - \displaystyle\sum_{k=0}^{m-1}(x-c_{k+1})B_{k+1}Q_k + \displaystyle\sum_{k=0}^{m-2}d_{k+2}B_{k+2}Q_k =$
$= B_0Q_0 + B_1Q_1 - (x-c_1)B_1Q_0 + \displaystyle\sum_{k=2}^mB_kQ_k-\displaystyle\sum_{k=1}^{m-1}(x-c_{k+1})B_{k+1}Q_k + \displaystyle\sum_{k=0}^{m-2}d_{k+2}B_{k+2}Q_k=$
$= B_0Q_0 + B_1Q_1 - (x-c_1)B_1Q_0 + \displaystyle\sum_{k=2}^mB_kQ_k-\displaystyle\sum_{k=2}^{m}(x-c_{k})B_{k}Q_{k-1} + \displaystyle\sum_{k=2}^{m}d_{k}B_{k}Q_{k-2}=$
$= B_0Q_0 + B_1(Q_1 - (x-c_1)Q_0) + \displaystyle\sum_{k=2}^m(B_kQ_k-(x-c_{k})B_{k}Q_{k-1} + d_{k}B_{k}Q_{k-2})=$
$= B_0 + B_1(Q_1 - (x-c_1)) + \displaystyle\sum_{k=2}^mB_k(Q_k-(x-c_{k})Q_{k-1} + d_{k}Q_{k-2})=$
$=B_0$

$Q_m(x)=\displaystyle\sum_{k=0}^ma_kQ_k(x)$, gdzie dla $k \neq m\quad a_k = 0$ oraz dla $k = m\quad a_k = 1$

## 6
Dane:
$x_j = -10 + 5j\qquad$ dla $j\in \{0,1,2,3,4\}$

### Sposób 1 rekurencyja podana na wykładzie

$P_0(x) = 1$

$c_1=\frac{<xP_0,P_0>}{<P_0,P_0>}=\frac{(-10)\times1 +(-5)\times1 +0\times1 +5\times1 +10\times1}{1\times1 + 1\times1 +1\times1 +1\times1 +1\times1}=\frac{0}{5}=0$

$P_1(x)=(x - c_1)=x - 0 = x$

$c_2=\frac{<xP_1,P_1>}{<P_1,P_1>}=\frac{(-10)^3+(-5)^3+0^3+5^3+10^3}{(-10)^2+(-5)^2+0^2+5^2+10^2}=\frac{-1000-125 + 0 + 125 + 1000}{100 + 25 + 0 + 25 + 100}=\frac{0}{250}=0$

$d_2=\frac{<P_1,P_1>}{<P_0,P_0>}=\frac{250}{5}=50$

$P_2(x)=(x-c_2)P_1(x)-d_2P_0(x)=(x-0)x-50\times1=x^2-50$

### Sposób 2 ortogonalizacja Grama-Schmidta

**Algorytm:**

$P_i = f_i$ $\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad$**dla i = 0**

$P_i(x) = f_i(x) - \displaystyle\sum^{i−1}_{j=0}\frac{<f_i,P_j>}{<P_j,P_j>}\times P_j$ $\qquad$ **dla i > 0**

Weźmy bazę funkcji taką, że: $f_0(x) =1$, $f_1(x) =x$, $f_2(x) =x^2$

Wtedy zgodnie z podanym wyżej algorytmem

$P_0(x) = f_0 = 1$

$P_1(x) = f_1(x) - \frac{<f_1,P_0>}{<P_0,P_0>}\times P_0 = x - \frac{<x,1>}{<1,1>}\times1= x - \frac{-10-5+5+10}{1+1+1+1+1} = x - \frac05 = x$

$P_2(x) =
f_2(x) -\frac{<f_2,P_0>}{<P_0,P_0>}\times P_0 -
\frac{<f_2,P_1>}{<P_1,P_1>}\times P_1 =x^2 -\frac{<x^2,1>}{<1,1>}\times 1 -
\frac{<x^2,x>}{<x,x>}\times x =$
$x^2 -\frac{100+25 +25+100}{1+1+1+1+1} -
\frac{-1000-125 +125+1000}{100+ 25 + 25 + 100}\times x = x^2 - \frac{250}{5} - \frac{0}{250}= x^2 -50$

## 7

Wielomian $w^∗_2\in \Pi_2$, aby wyrażenie $\displaystyle\sum_{j=0}^4[w^∗_2(x_j)−h(x_j)]^2$ przyjmowało najmniejszą możliwą wartość ma postać $w^∗_2=\displaystyle\sum_{i=0}^2a_iP_i(x)$ , gdzie wielomiany $P_i$ są ortogonalne w sensie iloczynu skalarnego z poprzedniego zadania, a
$a_i=\frac{<h,P_i>}{<P_i,P_i>}$ dla $i\in$ $\{0,1,2\}$

Z poprzedniego zadania wiemy, że:

$P_0 = 1$
$P_1 = x$
$P_2 = x^2 - 50$

$<P_0,P_0> = 5$
$<P_1,P_1> = 250$

Teraz policzę pozostałe wartości pomocnicze potrzebne do obliczenia wartości $a_i$

$<P_2,P_2> =((-10)^2-50)^2 + ((-5)^2-50)^2+(0^2-50)^2+(5^2-50)^2+(10^2-50)^2=$
$2500+625 + 2500 + 635 + 2500=8750$

$<h, P_0> =3 -5-1-5+3=-5$
$<h, P_1> =-3 \times10 + 5\times 5 -1 \times0 -5\times5 +3 \times 10 =0$
$<h, P_2> =3 \times50 + 5\times25 + 1\times50 + 5\times 25 + 3\times 50 = 600$

$a_0=\frac{<h,P_0>}{<P_0,P_0>}=-\frac55 =-1$

$a_1=\frac{<h,P_1>}{<P_1,P_1>}=\frac{0}{250}=0$

$a_2=\frac{<h,P_2>}{<P_2,P_2>}=\frac{600}{8750}=\frac{12}{175}$

$w_2^* =\displaystyle\sum_{i=0}^2a_iP_i(x)=(-1)\times 1 + 0\times x +\frac{12}{175}(x^2-50) = \frac{12}{175}x^2 -\frac{31}{7}$