Po czterech i pół roku od ukazania się ostatniego artykułu w tym cyklu postanowiłem powrócić do tematu interpolacji wielomianowej. W tym odcinku pokażę pewien jej ślepy zaułek. Rozpocznę od przypomnienia niezbędnych faktów.
Interpolacja wielomianowa — przypomnienie wiadomości
Interpolacja jest jedną z metod obliczania przybliżonych wartości funkcji. Zakłada się, że obliczono wartości jakiejś funkcji w iluś punktach zwanych węzłami (czyli wartości tej funkcji w punktach węzłowych są znane). Interesuje nas natomiast przybliżenie wartości naszej funkcji w punktach nie będących węzłami. W zagadnieniu interpolacji wielomianowej przyjmując \(n\) węzłów \(x_1<x_2<\dots<x_n\) oraz znając wartości \(f(x_1),f(x_2),\dots,f(x_n)\) naszej funkcji w tych węzłach poszukujemy wielomianu \(w(x)\), którego wartości będę się zgadzać z wartościami funkcji \(f(x)\) w punktach węzłowych, czyli spełniającego warunki interpolacyjne\[w(x_1)=f(x_1),\ w(x_2)=f(x_2),\ \dots,w(x_n)=f(x_n).\]Okazuje się, że istnieje dokładnie jeden wielomian \(w(x)\) rzędu \(n-1\) (tzn. stopnia co najwyżej \(n-1\)) spełniający te warunki. Można go wyznaczyć jednym z dwóch wzorów interpolacyjnych: Lagrange’a lub Newtona. Jeśli to zrobimy, możemy próbować przybliżać wartości funkcji \(f(x)\) wartościami wielomianu \(w(x)\), zwanego wielomianem interpolacyjnym w punktach \(x\) nie będących węzłami, ale spełniającymi warunek \(x_1<x<x_n\). Stosujemy więc wtedy przybliżenie \(f(x)\approx w(x)\). Znane jest oszacowanie błędu tego przybliżenia. Jest nim\[|f(x)-w(x)|\xle\frac{\|f^{(n)}\|}{n!}|(x-x_1)(x-x_2)\cdot\ldots\cdot(x-x_n)|,\]gdzie \(\|f^{(n)}\|\) to największa wartość wyrażenia \(|f^{(n)}(x)|\) dla \(x\in[x_0,x_n]\). Wydawałoby się więc, że wystarczy tylko wybrać żądaną dokładność obliczeń i określić wymagany do jej osiągnięcia rząd wielomianu interpolacyjnego. I rzeczywiście często nawet wielomiany interpolacyjne niskich rzędów bardzo dobrze przybliżają niektóre funkcje. Czasami nawet interpolacja liniowa (z tylko dwoma węzłami) przynosi dobre efekty. A jednak…
Kiedy interpolacja się nie udaje?
Czasami zachowanie się wielomianu interpolacyjnego pomiędzy punktami węzłowymi pozostawia wiele do życzenia. Może się zdarzyć, że mimo iż w węzłach wartości wielomianu interpolacyjnego są równe wartościom przybliżanej funkcji, to w punktach leżących pomiędzy węzłami przybliżenie nie jest najlepszej jakości. Na takie zjawisko zwrócił w roku 1901 uwagę niemiecki matematyk Carl Runge (stąd nazwa efekt Rungego). Dla jego zilustrowania posłużę się przykładem. Zobaczymy w nim, że powodem powstania tego efektu jest równomierne rozmieszczenie węzłów interpolacji.
Przypuśćmy mianowicie, że naszym zadaniem będzie przybliżenie wartości funkcji\[f(x)=\frac{1}{1+9x^2}\]dla \(x\in(-1,1)\) wielomianem interpolacyjnym zbudowanym na węzłach równomiernie rozmieszczonych w przedziale \([-1,1]\) (oczywiście same punkty \(-1\) oraz \(1\) też będą węzłami).
Przyjrzyjmy się kilku rysunkom (wykonałem je w programie SageMath — narzędziu matematycznym o praktycznie nieograniczonych możliwościach). Zawsze wykres funkcji \(f\) będzie zielony, zaś wykres wielomianu interpolacyjnego brązowy. Zaznaczyłem też (równomierne) rozmieszczenie węzłów na osi poziomej oraz punkty przecięcia obu wykresów (bo przecież w węzłach zachodzi równość wartości funkcji i wielomianu interpolacyjnego).
Rozpocznijmy od pięciu węzłów. Wielomian interpolacyjny jest więc rzędu \(4\). W tym przypadku jest nim \(w(x)=\frac{256}{85} x^{4} – \frac{336}{85} x^{2} + 1\).
O ile interpolacja w okolicy zera jest niezłej jakości, to największe błędy przybliżenia obserwujemy blisko końców przedziału. A może w celu poprawienia jakości przybliżenia interpolacyjnego należy przyjąć więcej węzłów? Weźmy więc \(10\) węzłów.
Tutaj widzimy, że jakość interpolacji znacznie się poprawiła „w środku” przedziału, ale znów blisko jego końców błąd jest duży. Dodajmy jeszcze więcej węzłów: np. \(25\).
Obserwujemy podobne zjawisko — w okolicach końców przedziału błąd interpolacji jest jeszcze większy niż w poprzednich przypadkach. Przeczy to intuicji mówiącej, że im więcej węzłów, tym lepsza jakość interpolacji. Spójrzmy więc na dwa ostatnie rysunki sporządzone dla odpowiednio \(40\) oraz \(50\) węzłów.
Po raz kolejny dostrzegamy, że wraz ze zwiększaniem się liczby węzłów błąd interpolacji paradoksalnie rośnie. Można udowodnić, że jeśli liczba równomiernie rozmieszczonych węzłów zmierza do nieskończoności, to maksymalny błąd interpolacji naszej funkcji odpowiednim wielomianem również zmierza do nieskończoności.
Jak uniknąć efektu Rungego?
Oczywiście dla konkretnej funkcji, którą chcemy interpolować, trudno od razu wykluczyć zajście efektu Rungego. Jak więc uniknąć możliwości jego powstania? Okazuje się (o czym wspomniałem już wcześniej), że powodem powstania tego zjawiska jest równomierne rozmieszczenie węzłów. Tak więc odpowiedni ich wybór może poprawić jakość interpolacji. Dla rozważanej tu funkcji Rungego wystarczy dodać więcej węzłów w okolicach punktów końcowych \(-1\) oraz \(1\). Dla przykładu spójrzmy na następujący układ dziesięciu nierównomiernie rozmieszczonych węzłów:\[-1,\ -0{,}9,\ -0{,}8,\ -0{,}4,\ -0{,}1,\ 0{,}1,\ 0{,}4,\ 0{,}8,\ 0{,}9,\ 1.\]
Porównując ten rysunek z rysunkiem sporządzonym dla dziesięciu równomiernie rozmieszczonych węzłów stwierdzamy nieznaczne pogorszenie się jakości interpolacji „w środku” przedziału. Jednak ewidentnie unikamy efektu Rungego.
Jak dobierać węzły interpolacji?
W powyższym przykładzie nierównomiernie rozmieszczone węzły dobrałem dość arbitralnie, biorąc jedynie pod uwagę potrzebę umieszczenia większej liczby węzłów w okolicy końców przedziału. Mówiąc kolokwialnie, zrobiłem to „na oko”. Istnieje jednak ciekawy sposób doboru węzłów uwzględniający ich gęstsze rozmieszczenie w pobliżu końców przedziału. Chodzi mianowicie o tzw. węzły Czebyszewa, o których opowiem w kolejnym odcinku.