Zagadnienie interpolacyjne

Sformułowanie problemu

Zadaniem, jakie należy rozwiązać jest interpolacja funkcji, zadanej zbiorem $n$ punktów: $(x_i, f(x_i))$, $x_1 < x_i < x_n$. Należy napisać program numeryczny, który na podstawie podanego zbioru punktów oblicza poprzez interpolację przybliżone wartości funkcji. Działanie programu przetestować należy dla funkcji $f(x) = \sqrt{(x)}$.

Rozwiązanie

Rozwiązaniem podanego wyżej problemu jest zastosowanie wielomianu interpolacyjnego stopnia co najwyżej $n$. W programie należy wykorzystać tzw. postać Lagrange'a:

$$W_n(x) = \displaystyle\sum_{i=0}^{n}\left[f(x_i)\prod_{\overset{j=0}{i\neq j}}^{n} \frac{x-x_j}{x_i - x_j} \right]$$ (1)

gdzie:
$x_i$, $x_j$ - wartości argumentów funkcji w punktach węzłowych,
$x$ - argument, dla którego obliczana jest przybliżona wartość funkcji $f(x)$.

Wyprowadzenie

Interpolacją nazywamy wyznaczenie przybliżonej wartości funkcji $f(x):$
$[a,b] \rightarrow \mathbb{R}$ w dowolnym punkcie $x \in [a,b]$ na podstawie znanych wartości funkcji w ustalonych punktach $x_i$: $f(x_0),\ldots,f(x_i),\ldots,f(x_n)$. Funkcja interpolująca $F(x)$ musi spełniać następującą własność:

$$F(x_i) = f(x_i) = y_i$$ (2)

Najczęściej stosowanym rozwiązaniem jest wykorzystanie jako funkcji interpolującej wielomianu $W_n(x)$, którego stopień wynosi co najwyżej $n$. Można udowodnić, że istnieje dokładnie jeden wielomian interpolacyjny $W_n(x)$, który w punktach $x_0,\ldots,x_n$ przyjmuje wartości $y_0,\ldots,y_n$.

Wyprowadzenie równania (1) przeprowadza się poprzez konstruowanie tzw. wielomianów pomocniczych $W_n^i$, $i = 0,1,\ldots,n$. Każdy z wielomianów pomocniczych jest stopnia co najwyżej $n$. Wielomiany te przyjmują wartość 0 w punktach $x_j$ dla $j \neq i$ oraz 1 w punkcie $x_i$:

$$W_n^i(x) = \frac {(x-x_0)\cdots(x-x_{i-1})(x-x_{i+1})\cdots(x-x_n) } {(x_i-x_0)\cdots(x_{i} - x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_n) }$$ (3)

Wygodnie jest zapisać równanie (3) w bardziej zwięzłej postaci:

$$W_n^i(x) = \displaystyle\prod_{\overset{j=0}{j\neq i}}^{n} \frac{x-x_j}{x_i - x_j}$$ (4)

Ze względu na podane wyżej własności, wielomian taki posiada następującą cechę:

$$y_i = W_n^i(x_i)y_i$$ (5)

Poprzez zsumowanie tak skonstruowanych wielomianów otrzymujemy również wielomian stopnia co najwyżej $n$, dodatkowo spełniający warunki stawiane funkcji interpolującej:

$$W_n(x) = \displaystyle\sum_{i=0}^{n}W_n^i(x)y_i$$ (6)

Podstawiając do równania (6) równanie (4) otrzymujemy:

$$W_n(x) = \displaystyle\sum_{i=0}^{n}\left[f(x_i)\prod_{\overset{j=0}{i\neq j}}^{n} \frac{x-x_j}{x_i - x_j} \right]$$ (7)

Rozwiązanie algorytmiczne

Dla realizacji podanego powyżej schematu obliczeniowego (1) zastosować można następujący algorytm:

$W_n$ = 0.0;
dla i:= 1 do n wykonuj
rozpocznij
$p$ = 1.0;
dla j:= 1 do n wykonuj
rozpocznij
	jezeli i $\neq$ j wtedy
		$p$ = $p$ * ($x$ - $x_j$) / ($x_i$ - $x_j$);
zakoncz
$W_n$ := $W_n$ + $y_i$ * $p$;
zakoncz

Przykłady

Przykład 1 Obliczenie interpolowanej wartości $f(x) = \sqrt{x}$

Przyjmijmy 3 punkty interpolacyjne:
$x_0 = (0, 0)$
$x_1 = (4, 2)$
$x_2 = (9, 3)$
Dla $x = 1$ wartość interpolowana wynosi 6.00000000e-01. Otrzymany wynik daleki jest od oczekiwanego. Dla poprawienia jakości przybliżenia zmniejszono odległość pomiędzy punktami skrajnymi:
$x_0 = (0, 0)$
$x_1 = (0.5, 0.707106781)$
$x_2 = (1.5, 1.224744871)$
Wartość interpolowana dla $x = 1$ wynosi 1.11535507e+00.

Przykład 2 Przykład zastosowania interpolacji

Rysunek 1 przedstawia interpolację funkcji danej równaniem (8) za pomocą wielomianu stopnia czwartego.

$$f(x) = \exp (-\sin{(x^2)})$$ (8)

Rysunek: Wykres funkcji $f(x) = \exp (-\sin{(x^2)})$

Jak można zauważyć, różnice występujące pomiędzy ,,oryginalnymi'' a interpolowanymi wartościami są znaczące. Podstawowym błędem jest tutaj założenie, że za pomocą wielomianu interpolacyjnego można obliczyć cały zakres zmienności funkcji. Tymczasem interpolację stosuje się dla:

• niewielkich zakresów zmienności funkcji,
• niewielkich odległości pomiędzy punktami węzłowymi,
• lokalnie dostatecznie ,,gładkich'' funkcji.

Uwagi

1. Jak zademonstrowano powyżej, interpolacja daje zadowalające wyniki (dla punktów innych niż węzłowe) tylko wtedy, gdy odległości pomiędzy punktami węzłowymi są stosunkowo niewielkie.
2. W przypadku użycia do interpolacji wielomianów wysokiego stopnia (w praktyce oznacza to stopień piąty i wyższe) kształt funkcji interpolującej pomiędzy punktami węzłowymi może mieć charakter oscylacji. Jest to efekt silnie niepożądany.
3. Z powodów przedstawionych w punktach 1 i 2 do opracowywania danych doświadczalnych stosuje się zazwyczaj aproksymację (a nie interpolację).
4. Interpolacja znajduje jednak bardzo duże zastosowanie w analizie różnego rodzaju zagadnień teoretycznych z zakresu metod numerycznych. Wykorzystuje się ją m.in. przy wyprowadzaniu wzorów na numeryczne całkowanie i różniczkowanie oraz przy konstrukcji schematów rozwiązywania równań różniczkowych.