Po niemal czterech miesiącach milczenia wracam do cyklu dotyczącego interpolacji wielomianowej. Dziś opowiem o wzorze Newtona. W poprzednim odcinku wprowadziłem ilorazy różnicowe wyższych rzędów i pokazałem prosty sposób ich wyznaczania. Czas na zastosowanie…
Niech $x_0,x_1,\dots,x_n$ będą wzajemnie różnymi węzłami, a $f$ niech będzie funkcją określoną przynajmniej w tych węzłach. Wielomian $w$ rzędu $n$ spełniający warunki interpolacyjne\[w(x_0)=f(x_0),\;w(x_1)=f(x_1),\;\dots,\;w(x_n)=f(x_n)\](określony, jak już dobrze wiemy, jednoznacznie), można wyznaczyć według wzoru Newtona:\begin{align}w(x)=&[x_0;f]+[x_0,x_1;f](x-x_0)+[x_0,x_1,x_2;f](x-x_0)(x-x_1)+\ldots\\&\ldots+[x_0,x_1,\dots,x_{n+1};f](x-x_0)(x-x_1)\cdot\ldots\cdot(x-x_{n-1}).\tag{1}\label{w1}\end{align}Wzór ten ma niewątpliwą zaletę — pozwala na szybkie i mało pracochłonne wyznaczanie wielomianów interpolacyjnych. Dopisanie kolejnego węzła też nie stanowi żadnego problemu: opisany w poprzednim odcinku diagram trójkątny wystarczy odpowiednio rozszerzyć wpisując kolejny węzeł na jego dole. Skoro już mowa o diagramie, przypomnijmy sobie jak on wyglądał.\begin{matrix}\scriptstyle{x_0}&\scriptstyle{\color{red}{[x_0;f]=f(x_0)}}&&&\\ & &\scriptstyle{\color{red}{[x_0,x_1;f]=\frac{f(x_1)-f(x_0)}{x_1-x_0}}}&&\\\scriptstyle{x_1}&\scriptstyle{[x_1;f]=f(x_1)}&&\scriptstyle{\color{red}{[x_0,x_1,x_2;f]=\frac{[x_1,x_2;f]-[x_0,x_1;f]}{x_2-x_0}}}&\\ & &\scriptstyle{[x_1,x_2;f]=\frac{f(x_2)-f(x_1)}{x_2-x_1}}&&\scriptstyle{\color{red}{[x_0,x_1,x_2,x_3;f]=\dots}}\\ \scriptstyle{x_2}&\scriptstyle{[x_2;f]=f(x_2)}&&\scriptstyle{[x_1,x_2,x_3;f]=\frac{[x_2,x_3;f]-[x_1,x_2;f]}{x_3-x_1}}&\\ & &\scriptstyle{[x_2,x_3;f]=\frac{f(x_3)-f(x_3)}{x_3-x_2}}&&\\ \scriptstyle{x_3}&\scriptstyle{[x_3;f]=f(x_3)}&&& \end{matrix}Na czerwono zaznaczyłem ilorazy występujące we wzorze Newtona. Zauważmy jednak, że aby je wyznaczyć, należy zbudować cały diagram.
Przejdźmy do przykładu. W czwartym odcinku, poświęconym wzorowi Lagrange’a, wyznaczyłem wielomian interpolujący funkcję $f(x)=2^x$ w węzłach $1,2,3$. Oczywiście jest to trójmian kwadratowy. Wyznaczmy go ponownie, ale z użyciem wzoru Newtona. Oznaczmy w tym celu $x_0=1,\;x_1=2,\;x_2=3$. Wielomian ten, zgodnie z wzorem \eqref{w1}, ma więc postać\[w(x)=\color{red}{[x_0;f]}+\color{red}{[x_0,x_1;f]}(x-x_0)+\color{red}{[x_0,x_1,x_2;f]}(x-x_0)(x-x_1).\]Sporządźmy diagram trójkątny (tak jak przypomniałem powyżej).\begin{matrix}1&\color{red}2&&\\&&\color{red}{2}&\\2&4&&\color{red}{1}\\&&4&\\3&8&&\end{matrix}Nasz wielomian ma więc postać\[w(x)=\color{red}{2}+\color{red}{2}\cdot(x-1)+\color{red}{1}\cdot(x-1)(x-2)=x^2-x+2.\]Jako ćwiczenie proponuję dopisać kolejne dwa węzły $4$ oraz $5$ i wyznaczyć (dość szybko) wielomian interpolujący funkcję $f(x)=2^x$ w węzłach $1,2,3,4,5$.
Kto wykonał powyższe ćwiczenie, z łatwością zauważy, że aby interpolować wzorem Newtona inną funkcję, należy zbudować zupełnie nowy diagram trójkątny. Tam więc, gdzie wzór Lagrange’a ma zaletę, wzór Newtona ma wadę (i na odwrót).
Zastosowanie wzoru Newtona pozwala na bardzo łatwe wyznaczenie błędu interpolacji wielomianowej. Pozostańmy przy interpolacji funkcji $f$ w węzłach $x_0,x_1,\dots,x_n$ wielomianem rzędu $n$. Ustalmy teraz dowolne $x$ z dziedziny funkcji $f$. Dopiszmy jednak jeszcze jeden węzeł $x$ i wyznaczmy wielomian $W(t)$ spełniający warunki\[W(x_0)=f(x_0),\;W(x_1)=f(x_1),\;\dots,\;W(x_n)=f(x_n),\;W(x)=f(x).\]Korzystając z dobrodziejstw wzoru Newtona i biorąc pod uwagę wzór \eqref{w1}, możemy łatwo dostrzec, że\[W(t)=w(t)+[x_0,x_1,\dots,x_n,x;f](t-x_0)(t-x_1)\cdot\ldots\cdot(t-x_{n-1})(t-x_n).\]Ale przecież $W(x)=f(x)$, więc stosując powyższą równość dla $t=x$, dochodzimy do postaci\[f(x)=w(x)+[x_0,x_1,\dots,x_n,x;f](x-x_0)(x-x_1)\cdot\ldots\cdot(x-x_{n-1})(x-x_n),\]która ostatecznie daje nam\[f(x)-w(x)=[x_0,x_1,\dots,x_n,x;f](x-x_0)(x-x_1)\cdot\ldots\cdot(x-x_{n-1})(x-x_n).\]Jest to szukana postać różnicy pomiędzy wartością funkcji interpolowanej, a wielomianem interpolującym $w(x)$ wyznaczonym wzorem \eqref{w1} i spełniającym warunki\[w(x_0)=f(x_0),\;w(x_1)=f(x_1),\;\dots,\;w(x_n)=f(x_n).\]
Klasyczne podręczniki analizy numerycznej, przy odpowiednim założeniu regularnościowym o funkcji $f$, podają ten błąd w postaci\[f(x)-w(x)=\dfrac{f^{(n+1)}(c)}{(n+1)!}(x-x_0)(x-x_1)\cdot\ldots\cdot(x-x_{n-1})(x-x_n),\]gdzie $c$ jest pewnym punktem (na ogół zależnym od $x$) leżącym w najmniejszym przedziale zawierającym węzły $x_0,x_1,\dots,x_n$ oraz $x$. Widać stąd, że odpowiedni iloraz różnicowy $[x_0,x_1,\dots,x_n,x;f]$ musi być związany z pochodną funkcji $f$ rzędu $n$ równością\[[x_0,x_1,\dots,x_n,x;f]=\dfrac{f^{(n+1)}(c)}{(n+1)!}.\] I rzeczywiście tak jest — orzeka o tym twierdzenie o wartości średniej dla uogólnionych ilorazów różnicowych. Jest ono uogólnieniem twierdzenia Lagrange’a.