Tajniki interpolacji, część 3

W dwóch odcinkach wprowadzających do zasadniczego tematu interpolacji wielomianowej (chcę się nią w tym cyklu zająć) omawiałem interpolację liniową. Dzisiaj dalsza część wprowadzenia — poświęcona wielomianom. Zapraszam do lektury.

Interpolacja wielomianowa

Wszyscy wiemy, że wielomian stopnia $n\xge 1$ ma co najwyżej $n$ pierwiastków rzeczywistych. Dlatego jeśli jakiś wielomian stopnia nie większego niż $n$ (nazwiemy go wielomianem rzędu $n$) ma $n+1$ miejsc zerowych, to jest tożsamościowo równy zero. To prosta obserwacja. Ale ma bardzo poważne konsekwencje. Przypuśćmy bowiem, że dwa wielomiany rzędu $n$ są równe w $n+1$ punktach. Wynika stąd, że ich różnica, także będąca wielomianem rzędu $n$, ma $n+1$ miejsc zerowych, więc jest stale zerowa. Dlatego oba wielomiany są równe.

Przez każde dwa różne punkty przechodzi dokładnie jedna prosta. Przez trzy niewspółliniowe punkty płaszczyzny przechodzi dokładnie jedna parabola (jeśli punkty są różne, lecz współliniowe, przechodzi przez nie dokładnie jedna linia prosta, więc porzucając założenie niewspółliniowości mamy istnienie wielomianu rzędu $2$, którego wykres przechodzi przez te punkty). Można to uogólnić: przez dowolnych $n+1$ punktów płaszczyzny $(x_0,y_0), (x_1,y_1), (x_2,y_2), \dots, (x_n,y_n)$ (gdzie $x_0<x_1<\dots<x_n$) przechodzi wykres dokładnie jednego wielomianu rzędu $n$.

Powyżej sprawdziłem, że taki wielomian jest co najwyżej jeden. Udowodnię jeszcze istnienie tego wielomianu (zwanego interpolacyjnym). Można to zrobić na wiele sposobów, ja zdecyduję się na algebrę liniową. Oznaczmy szukany wielomian przez\[w(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n.\] Ponieważ postulujemy $y_i=w(x_i)$ dla każdego $i=0, 1, 2, \dots, n$, to otrzymujemy układ $n+1$ równań liniowych na współczynniki $a_0, a_1, a_2, \dots, a_n:$\[\left\{\begin{aligned}a_0+a_1x_0+a_2x_0^2+\dots+a_nx_0^n&=y_0\\a_0+a_1x_1+a_2x_1^2+\dots+a_nx_1^n&=y_1\\a_0+a_1x_2+a_2x_2^2+\dots+a_nx_2^n&=y_2\\&\phantom{o}\vdots\\a_0+a_1x_n+a_2x_n^2+\dots+a_nx_n^n&=y_n\end{aligned}\right.\]Jego wyznacznik to\[\begin{vmatrix}1&x_0&x_0^2&\dots&x_0^n\\1&x_1&x_1^2&\dots&x_1^n\\1&x_2&x_2^2&\dots&x_2^n\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&x_n&x_n^2&\dots&x_n^n\end{vmatrix}.\]Jest to dobrze znany wyznacznik Vandermonde’a. Ponieważ $x_0<x_1<x_2<\dots<x_n$, to jest on niezerowy i powyższy układ jest układem Cramera i jako taki jest oznaczony, czyli ma dokładnie jedno rozwiązanie $a_0, a_1, a_2, \dots, a_n$ (dlatego oprócz istnienia wielomianu $w$ innym sposobem udowodniliśmy też jego jednoznaczność).

Powyższe rozumowanie zawiera w sobie algorytm wyznaczenia wielomianu $w$. Jednak jest on wysoce nieefektywny. Analiza numeryczna zna dwa wzory pozwalające wyznaczyć ten wielomian znacznie szybciej i mniejszym nakładem pracy. Są to wzory interpolacyjne Lagrange’a i Newtona. O nich opowiedzą następne wpisy. Można by jeszcze pokazać, jaki jest błąd interpolacji wielomianem rzędu $n$. Jednak do zgrabnej jego prezentacji potrzeba aparatury związanej ze wzorem Newtona. Dlatego już zapraszam do czytania następnych odcinków cyklu. A zamierzam dojść dość daleko: do całuśnej interpolacji (nazwa jest oczywiście żartobliwa, jest dosłownym tłumaczeniem terminu angielskiego, zapraszam do jego rozszyfrowania).

Dodaj komentarz