Metody numeryczne 1 (MEN331) - Ćwiczenia 5

Kalendarium, Zasady, Ćw1, Ćw2, Ćw3, Ćw4, Ćw5, Ćw6, Ćw7, Ćw8, Ćw9, Ćw10, Ćw11, Ćw12, Ćw13
Prowadzący: Rafał Witkowski
Temat: Interpolacje wielomianowe: algorytmy Lagrange'a i Hermite'a, schemat Newtona, błędy interpolacji

Interpolacja

Interpolacja - informacje ogólne

Zagadnienie interpolacji można sformulować następująco:
W przedziale [a,b] danych jest n+1  punktów (x0,...,xn) (zwanych węzłami interpolacji) oraz wartości pewnej funkcji y=f(x) na tych punktach. Zadaniem interpolacji jest wyznaczenie przybliżonych wartości funkcji f  w punkach różnych od węzłów interpolacji oraz oszacowanie błędów tych przybliżeń. W tym celu znajduje się pewną funkcję interpolującą F(x), która w węzłach interpolacji przyjmuje odpowiednie wartości.

Funkcji interpolującej poszukuje się zawsze jako funkcji określonej postaci. U nas będą to narazie zawsze wielomiany algebraiczne. Dla takich fukncji łatwo bowiem wykonuje się działania arytmetyczne (+,-,*,/), różniczkowanie oraz całkowanie - innymi słowy mają one największe zastosowania w praktyce.

Najważniejszymi zastosowaniami interpolacji są:

Interpolacja Lagrange'a


Zagadnienie interpolacyjne Lagrange'a:
Dla danej funkcji f (danej tablicy funkcji f) postaci:
x
 f(x)
...
 ...
...
 ...
...
 ...


trzeba znaleźć wielomian Ln stopnia nie większego niż n taki, że


Zadanie interpolacyjne Lagrange'a ma jednoznaczne rozwiązanie postaci

Przykład 1

Obliczamy pierwiastek z 7 za pomocą interpolacji Lagrange'a.
Najpierw ustalmy pewne punkty, dla których łatwo obliczyć pierwiastek. Trzeba to zrobić w taki sposób, aby 7 było w środku tego przedziału. Punktów musi być co najmniej 3. Im więcej ich będzie, tym oszacowanie będzie dokładniejsze.

x
 f(x)
1
 1
4
 2
9
 3

Na ich podstawie tworzymy z wzoru wielomian interpolacyjny Lagrange'a, a potem obliczamy jego wartość w punkcie 7.

Zadanie 1
Obliczyć za pomocą interpolacji Lagrange'a następujące wartości danych funkcji:

Postać Newtona wielomianu Lagrange'a

Poprzednia postać wielomianu, jak można zauważyć, nie jest wygodna z obliczeniowego punktu widzenia. Korzystanie z tej postaci np. do obliczenia wartości wielomianu, do obliczenia jego pochodnych lub całek jest bardzo uciążliwe. Znacznie wygodniejsza jest postać Newtona wielomianu Lagrange'a

   , gdzie    



Ilorazem różnicowym rzędu k funkcji f opartym na parami różnych węzłach xi  (na których funkcja f jest określona) nazywamy wyrażenie:



W postaci Newtona wielomianu Lagrange'a współczynnik


Twierdzenie: Dla dowolnego układu parami różnych węzłów zachodzi następująca zależność:

Przykład 2

Obliczyć ilorazy różnicowe dla funkcji, której wartości są podane w tabelce:
x
 f(x)
1
 1
2
 -1
4
 3
5
 2









Przykład 3

Dla wielomianu W danego w postaci naturalnej      oraz punktów:
 
Obliczyć postać Newtona






A więc wielomian wygląda następująco


Zadanie 2
Przedstaw wielomiany w postaci Newtona
  1. dla punktów 0, 1, 3.
  2. dla punktów 3 dowolnie wybranych punktów.
  3. dla 4 dowolnie wybranych punktów.

Reszta interpolacyjna

Załóżmy, że chcemy obliczyć wartość pierwiastka 3-go stopnia z 10. Tworzymy wielomian interpolujący na podstawie 3 punktów:
x
 f(x)
1
 1
8
 2
27
 3

Z jakim błędem możemy to wykonać?

W tym celu należy obliczyć wartość r(x) z wzoru:



Ponieważ wartości funkcji w dowolnym punkcie nie znamy, dlatego musmy się posiłkować odpowiednim twierdzeniem:

Jeżeli rzeczywista funkcja f ma ciągłą pochodną (n+1) -ego rzędu na przedziale [a,b]  zawierającego węzły x0, x1, ... ,xn i punkt x (w którym liczymy wartość funkcji) to istnieje punkt   zależny od punktu x dla którego:

Przykład 4

Pokażemy z jakim błędem można obliczyć wartość sin(5*pi/7) gdy znamy dokładne wartości dla pkt sin(0), sin(pi/6), sin(pi/3), sin(pi/2), sin(2pi/3)

Zadanie 3
Oszacuj błąd powstały przy:
a) Obliczaniu pierwiastka z liczby 7 przy węzłach w punkach 1, 4 i 9.
b) Obliczania logarytmu dziesiętnego z 30 przy węzłach w punktach 1, 10 i 100

Interpolacja Hermite'a

Kiedy danych jest k+1 różnych węzłów x0, x1, ... , xk oraz liczby naturalne m0,m1, .... , mk takie że
to zadanie interpolacyjne Hermite'a polega na znalezieniu dla danej funkcji f wielomianu Hn stopnia niewyższego niż n spełniającego warunki:
dla

Konstrukcja wielomianu Hermite'a

Każda liczba l 0<=l<=n daje się jednoznacznie przedstawić w postaci l=s(i)+j, gdzie i=0,1,...k, j=0,1,2,...,mi-1


Zdefiniujmy wielomiany


Wówczas szukany wielomian Hn ma następującą postać:



Przypadek węzłów wielokrotnych

Przy podawanych poniżej założeń o regularności funkcji f, jej ilorazy różnicowe oparte na wielokrotnych węzłach określa się następująco (według odpowiedniego twierdzenia):





Otrzymujemy współczynniki b:

Przykład 5

Zajdź wielomian 3 topnia Q(x) taki, że
Q(0) = 0, Q'(0) = 1
Q(1) = 3, Q'(1) = 6











Zadanie 4
Znajdź wielomian interpolacyjny Hermite'a, wiedząc o funkcji, że: 

a) f(2)=1, f'(2) = 2, f''(2) = 0, f(3) = 1, f'(3) = 2; 
b) f(2) =1,  f(4) = 1, f'(4) = 1, f''(4) = 1

Reszta interpolacyjna

Resztę interpolacyjną wielomianu w postaci Hermite'a oblicza się zupełnie tak samo jak to było przy postaci Lagrange'a. Należy jedynie zwrócić uwagę na to, że oczywiście wielomian p(x), który jest we wzorze na obliczanie reszty wygląda nieco inaczej, a poza tym zupełnie nic sie nie zmienia.