====== Analiza numeryczna (M) - Lista 5. ======

{2k6}{{tag>[listy_zadan]}}{{:analiza_numeryczna:interpolacja_lagrange_a.pdf|}}

Iterpolacja wielomianowa A.D. 2009: [[http://www.ii.uni.wroc.pl/~sle/teaching/an-inter.pdf]]

===== Zadanie 1. =====
Niech $\mathcal{L}$ będzie odwzorowaniem, przyporządkowującym funkcji $f$ wielomian $\mathcal{L}_n^f$:\\

$\displaystyle \mathcal{L} f = L_n^f $\\


a) Sprawdzić, że $\mathcal{L}$ jest odwzorowaniem liniowym.\\

$ \displaystyle \mathcal{L}(f+g) = \sum_{k=0}^{n}(f+g)(x_k)\lambda_{k}(x) = \sum_{k=0}^{n}(f(x_k)+g(x_k))\lambda_{k}(x) = \sum_{k=0}^{n}(f)(x_k)\lambda_{k}(x) + \sum_{k=0}^{n}(g)(x_k)\lambda_{k}(x) =  \mathcal{L}(f)+ \mathcal{L}(g)$\\

$ \displaystyle \mathcal{L}(\mu \cdot f) = \sum_{k=0}^{n}(\mu \cdot f)(x_k)\lambda_{k}(x) = \sum_{k=0}^{n}\mu(f)(x_k)\lambda_{k}(x) = \mu \cdot \left(\sum_{k=0}^{n}(f)(x_k)\lambda_{k}(x)\right) = \mu\cdot\mathcal{L}(f)$\\

b) Sprawdzić, że dla każdego wielomianu $ w \in \prod_{n} $ jest $\mathcal{L}w = w$.\\

Zauważamy, że $\mathcal{L}w$ jako suma wielomianów stopnia $n$ jest wielomianem stopnia co najwyżej $n$. Dalej: $ (\mathcal{L}w - w) \in \prod_{n}$ bo jest różnicą wielomianów stopnia co najwyżej $n$. Oraz:\\

$ \displaystyle (\mathcal{L}w - w)(x_0) = w(x_0) - w(x_0) = 0 $\\
$ \ \ \ .$\\
$ \ \ \ .$\\
$ \ \ \ .$\\
$ \displaystyle (\mathcal{L}w - w)(x_n) = w(x_n) - w(x_n) = 0 $\\
Czyli $(\mathcal{L}w - w)$ ma co najmniej $n+1$ pierwiastków, a ponieważ ma stopień $\leq n$ to $\mathcal{L}w - w \equiv 0 \Rightarrow \mathcal{L}w \equiv w$

===== Zadanie 2. =====
Wykazać, że $ \sum_{k=0}^{n} \lambda_k(x) \equiv 1$.\\

Weźmy wielomian $w(x) = 1$, $w \in \prod_{n}$ dla każdego $n\in\mathbb{N}$.\\
Ponadto:\\
$\displaystyle \mathcal{L}w(x) = w(x) = 1 $\\
Wtedy:\\
$\displaystyle \mathcal{L}w(x) = \sum_{k=0}^{n}w(x_k)\lambda_k(x) = \sum_{k=0}^{n}1\cdot\lambda_k(x) = \sum_{k=0}^{n}\lambda_k(x)$\\

Stąd $ \sum_{k=0}^{n} \lambda_k(x) \equiv 1$.
===== Zadanie 3. =====
Wykazać, że:
$\displaystyle \sum_{k=0}^n \lambda_k(0)x_k^j = \begin{cases} 1 \ (j=0)\\0 \ (j=1,2,\ldots n)\end{cases} $


Niec $w(x)=x^j$, ponieważ $j\leq n$, to $w \in \prod_n$, czyli:

$\displaystyle w(x) = \mathcal{L}w(x) = \sum_{k=0}^{n}w(x_k)\lambda_k(x)$,

więc $ \displaystyle x^j = \sum_{k=0}^{n}x_{k}^j\lambda_k(x) $

no to wstawmy tam $ \displaystyle x = 0$

mamy $ \displaystyle 0^j = \sum_{k=0}^{n}x_{k}^j\lambda_k(0) $
więc:
dla $j = 0$ to mamy wielomian $ w(x) = x^0 $, czyli $ w(x)=x^0=1=Lw(x)$ co zostalo pokazane w zadaniu 2.
dla $j = 1,2 ... n$ to $ 0^j = 0$
bleh

===== Zadanie 4. =====
Wykaż, że wzór $ L_n^f(x) := \sum_{k=0}^n f(x_k)\lambda_k(x)$ można zapisać w postaci:\\

$\displaystyle L_n^f(x) = p_{n+1}(x) \left( \sum_{k=0}^n \frac{f(x_k)}{(x-x_k)p_{n+1}^\prime (x_k)}\right)$\\

gdzie $p_{n+1}(x) = (x-x_0)(x-x_1)\ldots (x-x_n)$\\

[skrypt SLE]\\

$p_0 = 1$\\

$\displaystyle p_{n+1}(x) = \prod_{j=0}^{n}(x-x_j) $\\

oraz:\\

$\displaystyle p_{n+1}^\prime (x_i) = \prod_{j=0,j\not = i}^{n}(x_i-x_j) $\\

---wytłumaczenie pochodnej: [przystępnie i wesoło]\\
$\displaystyle p_{n+1}^\prime(x_i) = (\prod_{i=0}^n(x-x_i))^\prime(x_i) =^1 (x-x_i)^\prime(x_i)\prod_{j=0,j\not =i}^n(x_i-x_j)+(x_i-x_i)(\prod_{j=0,j\not =i}^n(x-x_j))^\prime(x_i)=^2 1\cdot \prod_{j=0,j\not =i}^n(x_i-x_j)+0\cdot(\prod_{j=0,j\not =i}^n(x-x_j))^\prime(x_i)=\prod_{j=0,j\not =i}^n(x_i-x_j)$\\
1. z definicji pochodnej iloczynu i po wybraniu i-tego czynnika\\
2. bo... widać\\
----koniec----\\

Rozpisujemy wielomian intrapolacyjny Lagrange'a:\\

$\displaystyle L_n^f (x) = \sum_{k=0}^n f(x_k) \prod_{j=0,j\not = k}^n \frac{x-x_j}{x_k-x_j} = \sum_{k=0}^n f(x_k) \frac{p_{n+1}(x)}{x-x_k} \cdot \frac{1}{\prod_{j=0,j\not = k}^n (x_k-x_j)} = p_{n+1}(x) \left( \sum_{k=0}^n \frac{f(x_k)}{(x-x_k)p_{n+1}^\prime (x_k)}\right)$\\

===== Zadanie 5 =====
Wykazać, że w przypadku równoodległych węzłów\\

$\displaystyle x_k = x_0 +kh \ \ \ (k=0,1,\ldots,n;h>0)$\\

wzór intrapolacyjny Lagrange'a przybiera postać:\\

$\displaystyle L_n^f (x) = \frac{1}{n!}\sum_{k=0}^n f(x_k)(-1)^{n-k} {n \choose k} \prod_{j=0,j \not = k}^n \left( \frac{x-x_0}{h} - j \right) $\\

no to sprawdzamy:\\

$\displaystyle L_n^f (x) =  \frac{1}{n!}\sum_{k=0}^n f(x_k)(-1)^{n-k} \frac{n!}{k!(n-k)!} \prod_{j=0,j \not = k}^n \frac{x-(x_0+jh)}{h} =  \sum_{k=0}^n f(x_k)(-1)^{n-k} \frac{1}{k!(n-k)!} \prod_{j=0,j \not = k}^n \frac{x-x_j}{h}=$\\

--- tutaj mały lemacik ---\\
Pokażę, że:\\

$\displaystyle (-1)^{n-k} k! (n-k)! = \prod_{j=0,j \not =k}^n (k-j) $\\

rozpiszmy sobie prawą stronę:\\

$\displaystyle \underbrace{k\cdot (k-1) \cdot \ldots \cdot (k-k+1)}_{k!}\cdot \underbrace{(-1)\cdot (-2) \cdot \ldots \cdot (-n+k)}_{(n-k)!\cdot (-1)^{n-k}}$\\

--- koniec lemacika ---\\

$\displaystyle = \sum_{k=0}^n f(x_k)\prod_{j=0,j \not = k}^n \frac{x-x_j}{h(k-j)}  = \sum_{k=0}^n f(x_k)\prod_{j=0,j \not = k}^n \frac{x-x_j}{(x_k-x_0)-(x_j-x_0)} = \sum_{k=0}^n f(x_k)\lambda_k(x) $\\

===== Zadanie 6 =====

6.) 

Uzasadnić postać barycentryczną wielomianu:

$\displaystyle L_n^f(t) = \begin{cases} \displaystyle \sum_{i=0}^{n}\frac{\sigma_i}{t - x_i}f(x_i) \bigg / \sum_{i=0}^{n}\frac{\sigma_i}{t - x_i} \ \ \ (t \not\in\lbrace x_0,x_1,\ldots ,x_n \rbrace )\\f(x_k) \ \ \ (t=x_k, \ 0 \leq l \leq n)\end{cases} $

gdzie:

$\displaystyle \sigma_i := 1 \bigg / \prod_{j=0,j\not = i}^n (x_i-x_j) $

Kiedy $t$ jest jednym z węzłów postać jest wybitnie oczywista, pokażemy drugą:

$\displaystyle \frac{\displaystyle \sum_{k=0}^{n}\frac{\sigma_k}{t - x_k}f(x_k)}{\displaystyle\sum_{i=0}^{n}\frac{\sigma_i}{t - x_i}} \  =?= \sum_{k=0}^n f(x_k) \prod_{j=0,j\not = k}^n \frac{t - x_j}{x_k - x_j}$

$\displaystyle \ \ \ \ \ \ \ \ \Uparrow $

$\displaystyle \frac{\frac{\sigma_k}{t - x_k}f(x_k)}{\displaystyle\sum_{i=0}^{n}\frac{\sigma_i}{t - x_i}} \  =?=  f(x_k) \prod_{j=0,j\not = k}^n \frac{t - x_j}{x_k - x_j}$

$\displaystyle \ \ \ \ \ \ \ \ \Uparrow $

$\displaystyle \frac{\frac{\sigma_k}{t - x_k}}{\displaystyle\sum_{i=0}^{n}\frac{\sigma_i}{t - x_i}} \  =?= \prod_{j=0,j\not = k}^n \frac{t - x_j}{x_k - x_j}$

$\displaystyle \ \ \ \ \ \ \ \ \Uparrow $

$\displaystyle\frac{ \frac{1}{\displaystyle (t - x_k)\cdot\prod_{j=0,j\not = k}^n (x_k-x_j)}}{\displaystyle\sum_{i=0}^{n}\frac{\sigma_i}{t - x_i}} \  =?= \prod_{j=0,j\not = k}^n \frac{t - x_j}{x_k - x_j}$

$\displaystyle \ \ \ \ \ \ \ \ \Uparrow $

(tu odwracamy ułamki)

$\displaystyle (t - x_k)\cdot\prod_{j=0,j\not = k}^n (x_k-x_j)\cdot\sum_{i=0}^{n}\frac{\sigma_i}{t - x_i} \  =?= \prod_{j=0,j\not = k}^n \frac{x_k - x_j}{t - x_j}$

$\displaystyle \ \ \ \ \ \ \ \ \Uparrow $

$\displaystyle \sum_{i=0}^{n}\frac{\sigma_i}{t - x_i} \  =?= \prod_{j=0}^n \frac{1}{t - x_j}$

$\displaystyle \ \ \ \ \ \ \ \ \Uparrow $

$\displaystyle \prod_{j=0}^n (t - x_j)\left( \sum_{i=0}^{n}\frac{\sigma_i}{(t - x_i)}\right) \  =?= 1$

$\displaystyle \ \ \ \ \ \ \ \ \Uparrow $

$\displaystyle \prod_{j=0}^n (t - x_j)\left( \sum_{i=0}^{n}\frac{1}{(t - x_i)\cdot \prod_{j=0,j\not = i}^n (x_i-x_j)}\right) \  =?= 1$

$\displaystyle \ \ \ \ \ \ \ \ \Uparrow $

$\displaystyle \sum_{i=0}^{n}\frac{ \prod_{j=0}^n (t - x_j)}{(t - x_i)\cdot \prod_{j=0,j\not = i}^n (x_i-x_j)} \  =?= 1$

$\displaystyle \ \ \ \ \ \ \ \ \Uparrow $

$\displaystyle \sum_{i=0}^{n}\frac{ \prod_{j=0,j\not = i}^n (t - x_j)}{\prod_{j=0,j\not = i}^n (x_i-x_j)} \  =?= 1$

$\displaystyle \ \ \ \ \ \ \ \ \Uparrow $

$\displaystyle \sum_{i=0}^{n} \prod_{j=0,j\not = i}^n \frac{t - x_j}{x_i-x_j} \  =?= 1$

$\displaystyle \ \ \ \ \ \ \ \ \Uparrow $

$\displaystyle \sum_{i=0}^{n} \lambda_i(t) \  =?= 1$

A to jest prawdą bo, $\sum_{i=0}^{n} \lambda_i(x) \equiv 1$ [zadanie 2]
===== Zadanie 7 =====
7.) 
== Algorytm Hornera obliczania wartości wielomianu ==
Dany wielomian

$\displaystyle W(x) = b_0 + b_1 (x-x_0) + b_2 (x-x_0)(x-x_1) + \ldots + b_n (x-x_0)\cdots(x-x_{n-1})$

przekształcamy do postaci:

$W(x)=b_0+(x-x_0)(b_1+(x-x_1)(b_2+\ldots +(x-x_2)(b_{n-1}+(x-x_{n-1})b_n)\cdots))$

Następnie definiujemy:

$\displaystyle u_n = b_{n}$\\
$u_{n-1} = b_{n-1}+u_{n}(x-x_{n-1})$\\
$\vdots$\\
$u_{0} = b_{0}+u_{1}(x-x_0)$\\

Tak otrzymane $u_0$ będzie równe $W(x)$.
Rzeczywiście, jeśli podstawimy kolejno $b_n,\ldots, b_0$ do tego wielomianu, otrzymamy:



$\displaystyle W(x)  =  b_0+(x-x_0)(b_1+(x-x_1)(b_2+\ldots(x-x_{n-2})(b_{n-1}+u_n(x-x_{n-1}))))$\\
$\displaystyle W(x)  =  b_0 + (x-x_0)(b_1 +(x-x_1)(b_2 +\ldots (x-x_{n-2})u_{n-1}))$\\
$      \vdots $\\
$\displaystyle W(x)  =  b_0 + (x-x_0)u_1$\\
$\displaystyle W(x)  =  u_0$\\

....

===== Zadanie 8 =====