Przejdź do treści

Tajniki interpolacji, część 9

W kolejnym odcinku cyklu poświęconego interpolacji kontynuujemy temat wielomianów Czebyszewa w kontekście poprawienia jakości interpolacji wielomianowej wobec możliwości pojawienia się efektu Rungego. Powodem powstania tego zjawiska było równomierne rozmieszczenie węzłów interpolacji. Można to zniwelować przez dołożenie węzłów w okolicy końców przedziału interpolacji. Jedną z możliwych metod osiągnięcia tego celu jest zastosowanie węzłów Czebyszewa.

Węzły Czebyszewa

Przypomnę, że wzór\[T_n(x)=\cos(n\arccos x)\quad\text{dla}\quad x\in[-1,1]\]określa wielomian Czebyszewa stopnia \(n\). Każdy wielomian stopnia \(n\) ma co najwyżej \(n\) pierwiastków. Natomiast wielomian \(T_n\) ma dokładnie \(n\) wzajemnie różnych pierwiastków, a wszystkie leżą w przedziale \((-1,1)\). Są to właśnie węzły Czebyszewa. Okazuje się, że można je bardzo łatwo wyznaczyć dysponując powyższym wzorem trygonometrycznym. Rozwiążmy zatem równanie \(T_n(x)=0\).\begin{align*}\cos(n\arccos x)&=0\\n\arccos x&=\frac{\pi}{2}+k\pi,\quad\text{gdzie}\quad k\in\mathbb{Z}\\n\arccos x&=\frac{2k+1}{2}\pi\\\arccos x&=\frac{2k+1}{2n}\pi\\x&=\cos\biggl(\frac{2k+1}{2n}\pi\biggr)\end{align*}Wszystkie te liczby należą do przedziału \((-1,1)\) (ze względu na zbiór wartości cosinusa). Natomiast dla \(k=0,1,\dots,n-1\) otrzymujemy różne wartości \(x\). Dalej wartości te będą się cyklicznie powtarzać. Podsumowując, węzły Czebyszewa (przy danym \(n\)) wyznaczamy wg wzoru\[\cos\biggl(\frac{2k+1}{2n}\pi\biggr)\quad\text{dla}\quad k=0,1,\dots,n-1.\]Po dokonaniu przenumerowania tak, aby liczyć dla \(k=1,2,\dots,n\), otrzymamy\[x_k=\cos\biggl(\frac{2k-1}{2n}\pi\biggr)\quad\text{dla}\quad k=1,2,\dots,n.\]

Niwelacja efektu Rungego

Powróćmy teraz do interpolacji funkcji Rungego\[f(x)=\frac{1}{1+9x^2}\]w przedziale\([-1,1]\). Dla węzłów równo rozmieszczonych powstawał efekt Rungego polegający na tym, że maksymalny błąd interpolacji zmierzał do nieskończoności wraz ze zwiększaniem liczby węzłów. Wystarczy obejrzeć rysunki zamieszczone w siódmym odcinku tego cyklu. Poniżej przedstawiam analogiczne rysunki sporządzone dla interpolacji w węzłach Czebyszewa.

Efekt Rungego został zatem całkowicie wyeliminowany. Wykresy wielomianów interpolacyjnych wraz ze zwiększaniem liczby węzłów Czebyszewa coraz dokładniej przylegają do wykresu interpolowanej funkcji Rungego.

Co na to teoria?

Wybór węzłów Czebyszewa nie jest przypadkowy. Podejdźmy bowiem do zagadnienia interpolacji w ten sposób, żeby uzyskać możliwie najmniejszy maksymalny błąd interpolacji. Przy dowolnym wyborze \(n\) węzłów \(x_1,x_2,\dots,x_n\) błąd ten ograniczała liczba\[\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[-1,1]\). Przy ustalonej funkcji \(f\) współczynnik \(\frac{\|f^{(n)}\|}{n!}\) jest stały, więc maksymalny błąd interpolacji osiągniemy wtedy, gdy wyrażenie\[|(x-x_1)(x-x_2)\cdot\ldots\cdot(x-x_n)|\]przyjmie wartość największą. Wobec tego nadszedł czas na znalezienie takiego sposobu dobrania węzłów \(x_1,x_2,\dots,x_n\), aby największa wartość powyższego wyrażenia plasowała się na możliwie najniższym poziomie. Można udowodnić, że tym sposobem jest właśnie zastosowanie węzłów Czebyszewa.

Coś na deser

W roku 1939 genialny polski matematyk Józef Marcinkiewicz (już rok później zamordowany przez Rosjan w Charkowie) udowodnił twierdzenie, z którego wynika, że dla każdej funkcji, którą chcemy interpolować wielomianem \(w_{n-1}(x)\) rzędu \(n-1\), istnieje taki układ \(n\) węzłów interpolacji, że przy \(n\to\infty\) wyrażenie \(\|f-w_{n-1}\|\) (czyli największa bezwzględna wartość różnicy \(|f(x)-w_{n-1}(x)|\) w przedziale interpolacji) zmierza do zera. To jeden z najlepszych wyników w zakresie interpolacji. Można udowodnić, że dla funkcji Rungego ten optymalny układ węzłów stanowią\[x_k=\cos\biggl(\frac{k-1}{n-1}\pi\biggr)\quad\text{dla}\quad k=1,2,\dots,n.\]Określmy te węzły mianem węzłów Marcinkiewicza dla funkcji Rungego (aczkolwiek nigdzie nie widziałem takiej nazwy). Znajdowanie tych węzłów związane jest z konkretną funkcją. Różne funkcje mogą mieć różne węzły Marcinkiewicza. Na poniższym rysunku pokazałem interpolację funkcji Rungego w piętnastu węzłach Marcinkiewicza i dla porównania w piętnastu węzłach Czebyszewa. Jak można zauważyć, różnice między tymi węzłami są nieznaczne, a i wielomiany interpolacyjne zachowują się bardzo podobnie. Oczywiście oba rodzaje węzłów likwidują efekt Rungego.

Co dalej?

Wielomiany nie stanowią jedynej klasy funkcji stosowanych w interpolacji. Inny rodzaj takich funkcji stanowią funkcje sklejane czyli spliny. Ale to już temat na znacznie szerszy wykład.

2 komentarze do “Tajniki interpolacji, część 9”

  1. Witaj Szymon,
    wkrótce podejmę pracę nauczyciela w technikum samochodowym. Jest tam też nauczycielami kilku naszych wspólnych znajomych z ATH. I teraz się przygotowuję do tego wyzwania. W książce „Rysunek techniczny”, T. Dobrzański znalazłem rysunki tzw. „krzywików”, które to krzywiki w czasach mojej edukacji średniej (a nawet wyższej) wypełniały nasze tornistry. Moje pytanie: jak to zaprojektowano? Model matematyczny? Czym te krzywe aproksymowano? A może interpolowano? Będę wdzięczny za wyjaśnienia. Oczywiście dziś można to zdigitalizować i dobrać jakikolwiek model 2D, mniej lub bardziej adekwatny. Ale krzywiki były najpierw, zanim pojawiły się możliwości skaningu, który to skaning jest dziś ułatwiony zwykłym smartfonem.

    1. Nie potrafię odpowiedzieć na to pytanie. Po prostu nie wiem, jak projektowano krzywiki. Istotnie, można a posteriori zrobić jakiś model matematyczny.

Napisz komentarz