---
title: ANL Lista 11
tags: ANL
author: Mateusz Reis
---

# ANL LISTA 11

## Zadanie 1
**Uzasadnij proces ortogonalizacji Grama-Schmidta**

Dla liniowo niezależnych funkcji $\{f_0,f_1,f_2,f_3,..f_n\}$ możemy znaleźć liniowo niezależny układ funkcji $\{g_0,g_1,g_2,g_3,..g_n\}$, takich że iloczyn skalarny $<g_i,g_j>_N = 0$ dla $i\not=j$. Możemy to zrobić za pomocą wzoru

$$
\begin{cases}
g_0:= f_0\\
g_k:= f_k - \sum_{i=0}^{k-1} \frac{<g_i,f_k>_N}{<g_i,g_i>_N}g_i
\end{cases}
$$

Aby to pokazać posłużymy się indukcją.
Po zastosowaniu ortogonalizacji dla $\{f_0,f_1,f_2,f_3,..f_n\}$ otrzymujemy $\{g_0,g_1,g_2,...,g_n\}$. Chcemy pokazać że $\forall i,j<=n, i\not=j \implies <g_i,g_j>_N=0$.
- Podstawa:
Mamy $g_0=f_0$ oraz $g_1=f_1-\frac{<f_1,g_0>_N}{<g_0,g_0>_N}g_0$
Sprawdźmy czy $<g_0,g_1>_N = 0$.
$$
<g_0,g_1>_N=<g_0,f_1-\frac{<f_1,g_0>_N}{<g_0,g_0>_N}g_0>_N=\\
<g_0,f_1>-<g_0,\frac{<f_1,g_0>}{<g_0,g_0>}g_0>=\\
<g_0,f_1>-<g_0,g_0>*\frac{<f_1,g_0>}{<g_0,g_0>}=\\
<g_0,f_1>-<g_0,f_1>=0
$$
- Krok:
Załóżmy że układ $\{g_0,g_1,g_2,..,g_{k-1}\}$ jest ortogonalny pokażemy że $g_k$ jest ortogonalne z dowolonym $g_i, i<k$ :
$$
g_k=f_k - \sum_{l=0}^{k-1} \frac{<g_l,f_k>_N}{<g_l,g_l>_N}g_l
$$
$$
<g_i,g_k>=<g_i,f_k - \sum_{l=0}^{k-1} \frac{<g_l,f_k>} {<g_l,g_l>}g_l> =\\
<g_i,f_k>-\sum_{l=0}^{k-1} \frac{<g_l,f_k>} {<g_l,g_l>}<g_l,g_i>
$$
Z założenia wiemy że $<g_i,g_j>=0,i\not=j$ tak więc
$$
<g_i,f_k>-\frac{<g_i,f_k>}{<g_i,g_i>}<g_i,g_i>=<g_i,f_k>-<g_i,f_k>=0
$$
## Zadanie 2
Niech $P_k(1≤k≤N)$ będzie k-tym wielomianem ortogonalnym względem iloczynu skalarnego $<·,·>_N$. Pokaż, że dla dowolnego wielomianu $w∈Π_k−1$ jest $<w, P_k>_N=0$

Wielomian $w$ możemy przedstawić jako $$ \alpha_0P_0+\alpha_1P_1+\alpha_2P_2+...+\alpha_{k-1}P_{k-1}$$

wtedy
$$
<w,P_k>=
<\alpha_0P_0+\alpha_1P_1+\alpha_2P_2+...+\alpha_{k-1}P_{k-1},P_k>=\\
<\alpha_0P_0,P_k>+<\alpha_1P_1,P_k>+<\alpha_2P_2,P_k>+...+<\alpha_{k-1}P_{k-1},P_k>=\\
\alpha_0<P_0,P_k>+\alpha_1<P_1,P_k>+...+\alpha_{k-1}<P_{k-1},P_k>=0\\
\text{Poniewaz $\forall i\not=k,<P_i,P_k>=0$}
$$

## Zadanie 4
Niech $\{P_k\}$ będzie ciągiem wielomianów ortogonalnych względem iloczynu skalarnego$<f, g>_N:=∑_{k=0}^N f(x_k)g(x_k)$, gdzie $x_0, x_1, . . . , x_N$ są parami różnymi punktami. Ustalmy $x∈R$ oraz liczbę naturalną $n < N$. Ile i jakich operacji arytmetycznych należy wykonać, aby obliczyć wartości $P_0(x), P_1(x), . . . , P_n(x)$ ?

$P_n(x)$ możemy zapisać jako
$$
\begin{cases}
P_0(x)=1\\
P_1(x)=x-c_k\\
P_k(x)=(x-c_k)P_{k-1}(x)-d_kP_{k-2}(x)\\
\end{cases}\\
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}>}
$$

Zajmijmy się obliczeniem $d_k$, a jeszcze wcześniej musimy policzyć iloczyn skalarny $<P_{k-2},P_{k-2}>$ aby to zrobić potrzebujemy $(N+1)$ mnożeń $P_i(x_k)*P_i(x_k)$ oraz $N$ dodawań co daje łącznie $2N+1$ działań. Liczymy dwa różne iloczyny co daje $4N+2$ działań. Na samym końcu dzielimy, więc do policzenia $d_k$ potrzeba $4N+3$ działań.

Aby policzyć $c_k$ wykonujemy tyle samo operacji co przy $d_k$ dla $c_1$ oraz $2N+1$ mnozen i dodawan oraz $1$ dzielenie dla $c_k,k\not=1$, ponieważ mianownik $c_k$ obliczyliśmy jako licznik $d_k$.

Następnie musimy policzyć $(x-c_k)P_{k-1}(x)$ co wymaga $2(k-1)$ mnożeń.
Do policzenia $d_kP_{k-2}(x)$ użyjemy $k-2$ mnożeń.
Na samym końcu musimy jeszcze odjąć od siebie współczynniki $(x-c_k)P_{k-1}(x)$ oraz $d_kP_{k-2}(x)$. Daje to $k-2$ odejmowań.
Ostateczenie do policzenia :
- $P_1(x)$ potrzebujemy $4N+3$ działań w tym:
- $2N$ dodawań
- $2N+2$ mnożeń
- $1$ dzielenie

- $P_n(x)$ potrzebujemy $6N+3k$ działań w tym:
- $2N$ dodawań
- $2N+3k$ mnożeń
- $2$ dzielenia
- $k-2$ odejmowań

## Zadnaie 5
Niech $\{Q_k\}$ będzie ciągiem wielomianów określonych w następujący sposób:
$$
\begin{cases}
Q_0(x) = 1,\\
Q_1(x) =x−c1,\\
Q_k(x) = (x−c_k)Q_{k−1}(x)−d_kQ_{k−2}(x)(k= 2,3, . . .)
\end{cases}
$$gdzie $c_k$,$d_k$ są danymi stałymi. Udowodnij, że następujący algorytm Clenshawa:
$$
\begin{cases}
B_{m+2}:=B_{m+1}:= 0,\\
B_k:=a_k+ (x−c_{k+1})B_{k+1}−d_{k+2}B_{k+2} (k=m, m−1, . . . ,0),\\
wynik:=B_0,
\end{cases}
$$
oblicza wartość sumy $$∑_{k=0}^ma_kQ_k(x)$$

$B_0$ jest naszym wynikiem więc
$$
B_0 = a_0 + (x-c_1)B_1-d_2B_2=a_0Q_0+Q_1B_1-d_2B_2=\\
a_0Q_0+Q_1(a_1+(x-c_2)B_2-d_3B_3)-d_2B_2=\\
a_0Q_0+a_1Q_1-Q_1d_3B_3+\underbrace{Q_1(x-c_2)B_2-d_2B_2Q_0}_{Q_2B_2} =\\
a_0Q_0+a_1Q_1+Q_2B_2-Q_1d_3B_3=...\\
\sum_{i=0}^k a_iQ_i + Q_{i+1}B_{i+1}-Q_id_{i+2}B_{i+2}=...=\\
\sum_{i=0}^m a_iQ_i(x)+Q_{m+1}B_{m+1}-Q_{m}d_{m+2}B_{m+2} =
\sum_{i=0}^m a_iQ_i(x)
$$
Ponieważ $B_{m+1}=B_{m+2}=0$

TODO: Ostatni podpunkt

## Zadanie 6

Chcemy zbudować wielomiany ortogonalne $P_0,P_1,P_2$
mamy punkty
$$
\begin{array}{r|r|r|r|r}
x_0&x_1&x_2&x_3&x_4\\\hline
-10&-5&0&5&10
\end{array}
$$

I. ciąg wielomianów ortogonalnych

$$
\begin{cases}
P_0(x)=1\\
P_1(x)=x-c_k\\
P_k(x)=(x-c_k)P_{k-1}(x)-d_kP_{k-2}(x)\\
\end{cases}\\
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}>}
$$

$$
P_0=1\\
c_1=\frac{<xP_0,P_0>}{<P_0,P_0>}=\frac{(-10)+(-5)+0+5+10}{1+1+1+1+1}=\frac{0}{5}=0\\
P_1=x-0=x\\
c_2=\frac{<xP_1,P_1>}{<P_1,P_1>}=\frac{(-1000)+(-125)+0+125+1000}{100+25+0+25+100}=\frac{0}{250}=0\\
d_1=\frac{<P_1,P_1>}{<P_0,P_0>}=\frac{250}{5}=50\\
P_2=(x-0)x+50*1=x^2+50\\
$$

II.Ortogonalizacja Grama-Schmidta
Weźmy funkcje
$$
\begin{cases}
f_0(x)=1\\
f_1(x)=x\\
f_2(x)=x^2
\end{cases}
$$
$$
\begin{cases}
P_0(x)=f_0(x)\\
P_k(x)=f_k(x)-\sum_{i=0}^{k-1}\frac{<f_k,P_i>}{<P_i,P_i>}P_i
\end{cases}
$$

Liczymy
$$
P_0(x)=f_0(x)=1\\
P_1(x)=f_1(x)-\frac{<f_1,P_0>}{<P_0,P_0>}P_0= x - \frac{0}{5}*1=x\\
P_2(x)=f_2(x)-\frac{<f_2,P_0>}{<P_0,P_0>}P_0-\frac{<f_2,P_1>}{<P_1,P_1>}P_1=x^2-\frac{250}{5}*1-\frac{0}{250}*x=x^2-50
$$

## Zadanie 7

Mamy
$$
\begin{array}{r|r|r|r|r}
x_0&x_1&x_2&x_3&x_4\\\hline
-10&-5&0&5&10
\end{array}
$$
oraz
$$
\begin{array}{r|r|r|r|r}
h_0&h_1&h_2&h_3&h_4\\\hline
3&-5&-1&-5&3
\end{array}
$$
i wielomiany $P_k(x)$:
$$
P_0(x)=1\\
P_1(x)=x\\
P_2=x^2+50\\
$$

Chceamy znaleźć $w_2^*(x)∈Π_2$ taki aby wyrażenie
$$
∑_{j=0}^4[w_2^*(x_j)−h(x_j)]^2
$$
przyjmowało jak najmniejszą wartość.

Aby to zrobić użyjemy wzoru
$$
w_n^*=\sum_{i=0}^na_iP_i(x)\\
a_i=\frac{<h,P_i>}{<P_i,P_i>}\\
<h,P_0>=-5\\
<h,P_1>=-30+25-25
30=0\\
<h,P_2>=300-125-125+300=350\\
a_0=-1\\
a_1=0\\
a_2=\frac{350}{150*150+75*75+75*75*150*150}=\frac{350}{75(2*2+1+1+2*2)}=\frac{35}{75}=\frac{7}{15}\\
w_2^*=-1+\frac{7}{15}*(x^2+50)
$$