{2k6}
Iterpolacja wielomianowa A.D. 2009: http://www.ii.uni.wroc.pl/~sle/teaching/an-inter.pdf
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
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.
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
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)
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)
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]
7.)
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
….