Newtonova interpolácia

[TomasRusin]

Uvažujme nasledovnú úlohu. Chceme nájsť polynóm, čo najnižšieho stupňa, ktorý bude mať v daných bodoch predpísané nejaké hodnoty.
Nech teda $x_0, x_1, ..., x_n$ a $y_0, y_1, ..., y_n$ sú dané reálne (komplexné, racionálne) čísla, pričom $x_0, x_1, ..., x_n$ sú navzájom rôzne. Hľadáme polynóm $f(x)\in \mathbb R[x]$ ($f(x)\in \mathbb C[x]$,$f(x)\in \mathbb Q[x]$), taký, že bude splnené $f(x_i)=y_i$ pre $i=0,1,...,n$.

Budeme hľadať $f(x)$ v tvare $f(x)=c_0+c_1(x-x_0)+c_2(x-x_0)(x-x_1)+\cdots+c_n(x-x_0)(x-x_1)...(x-x_{n-1})$,
kde $c_0, c_1, ..., c_n$ sú neznáme reálne (komplexné, racionálne) čísla.

Prečo v tomto tvare? Pozrime sa čo dosteneme dosadením $x_0, x_1, ..., x_n$ za $x$.
\begin{array}\\
&y_0=f(x_0)=c_0\\
&y_1=f(x_1)=c_0+c_1(x_1-x_0)\\
&y_2=f(x_2)=c_0+c_1(x_2-x_0)+c_2(x_2-x_0)(x_2-x_1)\\
&\vdots\\
&y_n=f(x_n)=c_0+c_1(x_n-x_0)+c_2(x_n-x_0)(x_n-x_1)+\cdots+c_n(x_n-x_0)(x_n-x_1)...(x_n-x_{n-1})
\end{array}
Táto sústava rovníc s parametrami $x_0, x_1, ..., x_n$ a $y_0, y_1, ..., y_n$ je riešiteľná a vieme z nej určiť $c_0, c_1, ..., c_n$.


Toto stačí, ale existuje aj metóda výpočtu $c_0, c_1, ..., c_n$ pomocou algoritmu. Predpokladajme teraz, pre jednoduchosť výpočtu, že $n=2$.
Potom máme $c_0=y_0$ a pre ďalší koeficient dostaneme
\begin{equation}\\
c_1=\frac{y_1-c_0}{x_1-x_0}=\frac{y_1-y_0}{x_1-x_0}
\end{equation}
Odvoďme teraz podobný vzťah pre $c_2$.
\begin{array}\\
c_2(x_2-x_0)(x_2-x_1)&=&y_2-c_0-c_1(x_2-x_0)\\
&=&y_2-y_0-\frac{y_1-y_0}{x_1-x_0}(x_2-x_0)\\
&=&y_2-y_0-\frac{y_1-y_0}{x_1-x_0}(x_2-x_1)-\frac{y_1-y_0}{x_1-x_0}(x_1-x_0)\\
&=&y_2-y_0-\frac{y_1-y_0}{x_1-x_0}(x_2-x_1)-(y_1-y_0)\\
&=&y_2-y_1-\frac{y_1-y_0}{x_1-x_0}(x_2-x_1)\\
&=&(\frac{y_2-y_1}{x_2-x_1}-\frac{y_1-y_0}{x_1-x_0})(x_2-x_1)
\end{array}
Teda
\begin{equation}
c_2=\frac{\frac{y_2-y_1}{x_2-x_1}-\frac{y_1-y_0}{x_1-x_0}}{x_2-x_0}
\end{equation}

Začínajú tu vystupovať zlomky tvaru $\frac{y_i-y_{i-1}}{x_i-x_{i-1}}$, teda v tvare podielu diferencií (rozdielov).
Označme
\begin{equation}
c_{i,i-1}=\frac{y_i-y_{i-1}}{x_i-x_{i-1}}
\end{equation}
\begin{equation}
c_{i,i-1,i-2}=\frac{c_{i,i-1}-c_{i-1,i-2}}{x_i-x_{i-2}}
\end{equation}

Potom $c_1=c_{1,0}$ a $c_2=c_{2,1,0}$.
Tieto skutočnosti vieme zapísať do tabuľky
\begin{array}\\
x_0 & y_0 & \\
x_1 & y_1 & c_{1,0}\\
x_2 & y_2 & c_{2,1} & c_{2,1,0}
\end{array}
Prvé dva stĺpce sú dané zo zadania, zvyšné stĺpce v tejto trojuholníkovej tabuľke vypočítame nasledovne: pri výpočte nejakej hodnoty (napr. $c_{1,0}$) sa pozrieme čo sa nacháza o jedno miesto vľavo ($y_1$) a o jedno miesto vľavo a hore ($y_0$), spravíme rozdiel týchto hodnôt ($y_1-y_0$) a vydelíme ho rozdielom tvaru $x_i-x_{i-j}$, kde $i$ zodpovedá riaku v ktorom sa nachádzame a $j$ zodpovedá stĺpcu v ktorom sa nachádzame nerátajúc prvé dve zadané stĺpce ($c_{1,0}$ sa nachádza v prvom riadku a prvom stĺpci).

Po vyplnení celej tabuľky, čísla ležiace na diagonále sú hľadané koeficienty $c_0,c_1,c_2$. V tomto prípade $c_0=y_0$, $c_1=c_{1,0}$ a $c_2=c_{2,1,0}$.

Odvodili sme to pre $n=2$ ale tento algoritmus výpočtu funguje pre ľubovoľné $n$. Funguje tam vzorec
\begin{equation}
c_{i,i-1,...,i-j}=\frac{c_{i,i-1,...,i-j+1}-c_{i-1,i-2,...,i-j}}{x_i-x_{i-j}}
\end{equation}
a pre hľadané $c_i$ máme $c_i=c_{i,i-1,...,0}$.

Príklad. Chceme odvodiť vzorec na výpočet súčtu druhých mocnín prir. čísel, teda na súčty tvaru $1^2+2^2+\cdots+x^2$ za predpokladu, že vieme, že sa jedná o polynóm tretieho stupňa, teda $1^2+2^2+\cdots+x^2=f(x)=a_3x^3+a_2x^2+a_1x+a_0$.
Zvoľme $x_1=1$, $x_2=2$, $x_3=3$, $x_4=4$. Výpočtom dostaneme $y_1=1$, $y_2=5$, $y_3=14$, $y_4=30$.

Najskôr vypočítame prvý stĺpec tabuľky
\begin{array}\\
x_i & y_i\\
1 & 1\\
2 & 5 & 4\\
3 & 14 & 9\\
4 & 30 & 16
\end{array}
Teraz $c_{2,1,0}=\frac{9-4}{3-1}=\frac{5}{2}$, $c_{3,2,1}=\frac{16-9}{4-2}=\frac{7}{2}$ a dostaneme
\begin{array}\\
x_i & y_i\\
1 & 1\\
2 & 5 & 4\\
3 & 14 & 9 & \frac{5}{2}\\
4 & 30 & 16 & \frac{7}{2}
\end{array}
Nakoniec $c_{3,2,1,0}=\frac{\frac{7}{2}- \frac{5}{2}}{4-1}= \frac{1}{3}$ a teda
\begin{array}\\
x_i & y_i\\
1 & 1\\
2 & 5 & 4\\
3 & 14 & 9 & \frac{5}{2}\\
4 & 30 & 16 & \frac{7}{2} & \frac{1}{3}
\end{array}

Dostali sme $f(x)=1+4(x-1)+\frac{5}{2}(x-1)(x-2)+ \frac{1}{3}(x-1)(x-2)(x-3)$.
Po úprave $\sum_{i=1}^xi^2=\frac{1}{6}(2x^3+3x^2+x)$.