MN09LAB

Ćwiczenia: interpolacja wielomianowa

Ćwiczenie: Wagi wzoru barycentrycznego

Wyprowadź formułę na pierwszy wzór barycentryczny w przypadku $n+1$ węzłów równoodległych na odcinku $[0,1]$,

$w_j=(-1{)}^{n-j}\frac{1}{h^{n}j!(n-j)!}.$

Wywnioskuj stąd wzór na wagi w drugim wzorze barycentrycznym.

Wskazówka

Aby uprościć wagi w drugim wzorze barycentrycznym, zauważ, że skalowanie wszystkich wag przez tę samą stałą nie wpływa na jego wartość.

Rozwiązanie

Wyprowadzenie wzoru dla odcinka $[0,1]$ jest trywialne. Aby zaś przejść od odcinka $[0,1]$ do dowolnego $[a,b]$ należy dokonać transformacji liniowej węzłów: przesunięcie węzłów nic nie zmienia, bo we wzorze na wagi występują jedynie odległości między węzłami; natomiast skalowanie o czynnik $(b-a)$ spowoduje zmianę wszystkich wag o wspólny czynnik $(b-a{)}^{-n}$, który oczywiście upraszcza się w drugim wzorze barycentrycznym.

Ćwiczenie: Implementacja algorytmu barycentrycznego

Zaimplementuj drugi wzór barycentryczny tak, by w efekcie dostać dwie procedury:

• c = polfitb(x,y) --- wyznaczającą współczynniki$c$ wielomianu interpolującego wartości $y$ w węzłach równoodległych $x$;
• Y = polvalb(X,c) --- wyznaczającą w zadanych węzłach $X$ wartości $Y$ wielomianu interpolacyjnego o współczynnikach $c$.

Oszacuj koszt twojego algorytmu i porównaj z kosztem algorytmu różnic dzielonych (dla współczynników) i algorytmem Hornera (dla wartości) w dwóch przypadkach:

• kiedy jest dużo węzłów interpolacji, a potrzebna jest tylko jedna wartość wielomianu interpolacyjnego;
• na odwrót, kiedy jest mało węzłów interpolacji, a potrzeba wyznaczyć bardzo dużo wartości wielomianu interpolacyjnego.

Rozwiązanie

Musimy wyznaczyć współczynniki wagowe $w_j$. Jeśli z góry wiemy, że np. stopień naszego wielomianu interpolacyjnego nie przekroczy 20, to możemy przyspieszyć naszą procedurę, wykonując precomputing: wszak wagi w drugim wzorze barycentrycznym są wyznaczone niezależnie od węzłów!

Zatem musimy wyliczyć (całkowite!) wartości trójkątnej tabelki

$N=0$	1
$N=1$	1	-1
$N=2$	1	-2	1
$N=3$	1	-3	3	1
\vdots			...

a potem tylko sięgnąć do odpowiedniego wiersza.

Ćwiczenie: Dodawanie węzła interpolacji

Często w aplikacjach takich jak programy CAD zachodzi potrzeba dodania na bieżąco dodatkowego węzła interpolacji. Podaj, jak to zrobić i jaki to będzie miało koszt, gdy interpolant jest zadany w bazie

• naturalnej
• Newtona
• Lagrange'a

Rozwiązanie

Po raz kolejny okazuje się, jak niedobra jest baza naturalna: koszt wyznaczenia nowych współczynników to koszt rozwiązania układu z macierzą gęstą od nowa. Fakt, dodajemy do niej tylko dodatkowy wiersz i dodatkową kolumnę, więc przy odrobinie szczęścia możemy wykorzystać czynniki rozkładu starej (mniejszej) macierzy, ale i tak, koszt będzie co najmniej $O(N^2)$.

Dla bazy Newtona wystarczy doliczyć jeszcze jeden wiersz w tabelce różnic dzielonych (koszt $O(N)$), ale pamiętajmy, że zapewne zmienimy w ten sposób uporządkowanie węzłów, co może trochę pogroszyć numeryczne własności tak otrzymanego interpolantu.

Dla wzoru barycentrycznego, musimy po prostu aktualizować wszystkie wagi: także kosztem $O(N)$.

Ćwiczenie: Algorytm Hornera może więcej

Pokaż, że algorytm Hornera obliczania wartości $w(\xi )$ wielomianu danego w postaci potęgowej jest jednocześnie algorytmem dzielenia tego wielomianu przez jednomian $(x-\xi )$. Dokładniej, jeśli $w(x)=\sum _{j=0}^n{a}_j{x}^j$ to

$w(x)=\left(\sum _{j=1}^n{v}_j{x}^{j-1}\right)\cdot (x-\xi )+v_0,$

gdzie $v_j$ są zdefiniowane tak jak w algorytmie Hornera.

Ćwiczenie: Algorytm Hornera jest numerycznie poprawny

Pokaż numeryczną poprawność algorytmu Hornera obliczania wartości wielomianu ze względu na dane współczynniki $a_j$ tego wielomianu.

Ćwiczenie

Niech dane będą $ϵ>0$ i funkcja Parser nie mógł rozpoznać (nieznana funkcja „\toR”): {\displaystyle \displaystyle f:[a,b]\toR} , która jest nieskończenie wiele razy różniczkowalna i wszystkie jej pochodne są na $[a,b]$ ograniczone przez $M$. Napisz program znajdujący stopień $n$ oraz współczynniki w bazie Newtona wielomianu $w_{f,n}\in {\mathrm{\Pi }}_n$ interpolacyjnego $f$ z błędem

$\Vert f-w_{f,n}{\Vert }_{C([a,b])}\le ϵ.$

Rozpatrz dwa przypadki: gdy węzły interpolacji są równoodległe, oraz gdy węzły są czebyszewowskie.