Interpolacyjne metody różnicowe

Różnice skończone

Dana jest funkcja $y=f(x).$ Jej pierwsza różnica skończona wyraża się wzorem

$\Delta y=\Delta f(x)=f(x+\Delta x)-f(x),$

(1)

gdzie:

$\Delta x=h$ jest ustalonym krokiem różnicowym.

Różnice skończone wyższych rzędów otrzymuje się według reguły

$\Delta ^{n}y=\Delta ^{n-1}(\Delta y).$

Tak na przykład

${\begin{aligned}\Delta ^{2}y&=\Delta (\Delta y)\\[1ex]&=\Delta {\big [}f(x+\Delta x)-f(x){\big ]}\\[1ex]&={\big [}f(x+2\Delta x)-f(x+\Delta x){\big ]}-{\big [}f(x+\Delta x)-f(x){\big ]}\\[1ex]&=f(x+2\Delta x)-2f(x+\Delta x)+f(x).\end{aligned}}$

• Przykład

Niech będzie $P(x)=x^{3}.$ Dla $h=1$ otrzymuje się

${\begin{aligned}\Delta P(x)&=(x+1)^{3}-x^{3}=3x^{2}+3x+1,\\[1ex]\Delta ^{2}P(x)&={\big [}3(x+1)^{2}+3(x+1)+1{\big ]}-(3x^{2}+3x+1)=6x+6,\\[1ex]\Delta ^{3}P(x)&={\big [}6(x+1)+6{\big ]}-(6x+6)=6,\\[1ex]\Delta ^{n}P(x)&=0\quad \mathrm {dla} \;n>3.\end{aligned}}$

Jak widać różnica skończona trzeciego rzędu, wielomianu trzeciego stopnia ma wartość stałą. Można wykazać, że jeżeli

$P_{n}(x)=a_{0}x^{n}+a_{1}x^{n-1}+\ldots a_{n},\quad {}$

to

$\Delta ^{n}P_{n}(x)=n!a_{0}h^{n}=\mathrm {const} \quad \to \quad \Delta ^{s}P_{n}(x)=0,\quad {}$ gdy ${}\;s>n.$

Symbol $\Delta$ można traktować jako pewien operator odwzorowujący funkcję $y=f(x)$ w funkcję $\Delta y=f(x+\Delta x)-f(x).$ Operator ten ma trzy własności

1. $\Delta (u+v)=\Delta u+\Delta v,$
2. $\Delta (Cu)=C\Delta u,$
3. $\Delta ^{m}(\Delta ^{n}y)=\Delta ^{m+n}y.$

Ze wzoru (1) wynika, że

$f(x+\Delta x)=f(x)+\Delta f(x).$

Traktując operator $\Delta$ jako symboliczny mnożnik, możemy napisać

$f(x+\Delta x)=(1+\Delta )f(x),$

(2)

$f(x+n\Delta x)=(1+\Delta )^{n}f(x).$

(3)

Wykorzystując wzór dwumienny Newtona, otrzymujemy

$f(x+n\Delta x)=\sum _{m=0}^{n}C\;\!_{n}^{m}\Delta ^{m}f(x),\quad C\;\!_{n}^{m}={\frac {n!}{m!(n-m)!}}$

(4)

oraz dzięki temu, że

$\Delta =(1+\Delta )-1$

(5)

możemy napisać

${\begin{aligned}\Delta ^{n}f(x)&={\big [}(1+\Delta )-1{\big ]}^{n}f(x)\\[1ex]&=(1+\Delta )^{n}f(x)\\[1ex]&\quad -C_{n}^{1}(1+\Delta )^{n-1}f(x)\\[1ex]&\quad +C_{n}^{2}(1+\Delta )^{n-2}f(x)\\[1ex]&\quad -\ldots \\[1ex]&\quad +(-1)^{n-1}C\;\!_{n}^{n-1}(1+\Delta )f(x)\\[1ex]&\quad +(-1)^{n}f(x),\end{aligned}}$

a wykorzystując (3)

${\begin{aligned}\Delta ^{n}f(x)&=f(x+n\Delta x)\\[1ex]&\quad -C_{n}^{1}f{\big [}x+(n-1)\Delta x{\big ]}\\[1ex]&\quad +C_{n}^{2}f{\big [}x+(n-2)\Delta x{\big ]}\\[1ex]&\quad -\ldots \\[1ex]&\quad +(-1)^{n-1}C\;\!_{n}^{n-1}f(x+\Delta x)\\[1ex]&\quad +(-1)^{n}f(x).\end{aligned}}$

(6)

W przypadku gdy funkcja $f(x)$ ma ciągłą pochodną $f^{(n)}(x)$ na odcinku $(x+n\Delta x),$ można wykazać, że

$\Delta ^{n}f(x)=(\Delta x)^{n}f^{(n)}(x+\theta n\Delta x),\quad 0<\theta <1.$

(7)

Wynika stąd, że

$f^{(n)}(x+\theta n\Delta x)={\frac {\Delta ^{n}f(x)}{(\Delta x)^{n}}}\quad \to \quad f^{(n)}(x)=\lim _{\Delta x\to 0}{\frac {\Delta ^{n}f(x)}{(\Delta x)^{n}}}.$

Tablice różnic

W zagadnieniach interpolacji funkcji $y=f(x),$ której rzędne $y_{i}=f(x_{i})$ są dane dla równoodległych punktów $x_{i},\;i=0,1,2,\dots ,n,$ wykorzystuje się różnice skończone

$\Delta x_{i}=x_{i+1}-y_{i}=h=\mathrm {const} ,$ $\Delta y_{i}=y_{i+1}-y_{i},$ $\Delta ^{2}y_{i}=\Delta (\Delta y_{i})=\Delta y_{i+1}-\Delta y_{i},$ $.............................$ $\Delta ^{n}y_{i}=\Delta (\Delta ^{n-1}y_{i})=\Delta ^{n-1}y_{i+1}-\Delta ^{n-1}y_{i}.$

(8)

Z drugiej równości otrzymujemy

$y_{i+1}=y_{i}+\Delta y_{i}=(1+\Delta )y_{i},$

$y_{i+2}=(1+\Delta )y_{i+1}=(1+\Delta )^{2}y_{i},$

$y_{i+3}=(1+\Delta )y_{i+2}=(1+\Delta )^{3}y_{i},$

$............................$

$y_{i+n}=(1+\Delta )^{n}y_{i}.$

Dzięki wzorowi dwumiennemu Newtona otrzymujemy

${\begin{aligned}y_{i+n}&=y_{i}\\[1ex]&\quad +C_{n}^{1}\Delta y_{i}\\[1ex]&\quad +C_{n}^{2}\Delta ^{2}y_{i}\\[1ex]&\quad \ldots \\[1ex]&\quad +\Delta ^{n}y_{i},\end{aligned}}$

${\begin{aligned}\Delta ^{n}y_{i}&={\big [}(1+\Delta )-1{\big ]}^{n}\\[1ex]&=(1+\Delta )^{n}y_{i}\\[1ex]&\quad -C_{n}^{1}(1+\Delta )^{n-1}y_{i}\\[1ex]&\quad +\ldots \\[1ex]&\quad +C\;\!_{n}^{n-1}(1+\Delta )y_{i},\end{aligned}}$

${\begin{aligned}\Delta ^{n}y_{i}&=y_{n+i}\\[1ex]&\quad -C_{n}^{1}y_{n+i-1}\\[1ex]&\quad +C_{n}^{2}y_{n+i-2}\\[1ex]&\quad +\ldots \\[1ex]&\quad +(-1)^{n-1}C\;\!_{n}^{n-1}y_{i+1}\\[1ex]&\quad +(-1)^{n}y_{i}.\end{aligned}}$

Na przykład

$\Delta ^{2}y_{i}=y_{i+2}-2y_{i+1}+y_{i},$

$\Delta ^{3}y_{i}=y_{i+3}-3y_{i+2}+3y_{i+1}-y_{i},$

$............................$

Wzory (8) pozwalają tworzyć tablice różnic skończonych o postaci

${}\;x\;{}$	${}\;y\;{}$	$\Delta y$	$\Delta ^{2}y$	$\Delta ^{3}y$
$x_{0}$	$y_{0}$	$\Delta y_{0}$	$\Delta ^{2}y_{0}$	$\Delta ^{3}y_{0}$
$x_{1}$	$y_{1}$	$\Delta y_{1}$	$\Delta ^{2}y_{1}$	$\Delta ^{3}y_{1}$
$x_{2}$	$y_{2}$	$\Delta y_{2}$	$\Delta ^{2}y_{2}$	$\Delta ^{3}y_{2}$
$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$

Przykładowo dla wielomianu $y=2x^{3}-2x^{2}+3x-1$ otrzymuje się dla kroku $h=1$ i wartości początkowej $x_{0}=0$

${}\;x\;{}$	${}\;y\;{}$	$\Delta y$	$\Delta ^{2}y$	$\Delta ^{3}y$
0	–1	3	8	12
1	2	11	20	12
2	13	31	32	12
3	44	63	44	12
4	107	107	56	12
5	214	163	68	12
$\ldots$	$\ldots$	$\ldots$	$\ldots$	$\ldots$

Potęga uogólniona

W zagadnieniach interpolacji wygodnie jest wprowadzić pojęcie uogólnionej potęgi

$x^{[n]}=x(x-h)(x-2h)\ldots \,{\big [}x-(n-1)h{\big ]},\quad x^{[0]}=1,\quad 0^{[0]}=1,$

(9)

gdzie:

$h$ jest ustalonym krokiem.

Ze wzoru (1) wynika, że

$x^{[n]}=x^{n},\;\;\mathrm {gdy} \;h=0.$

Pierwsza różnica skończona uogólnionej potęgi, po uwzględnieniu (9), wyraża się wzorem

$\Delta x^{[n]}=(x+h)^{[n]}-x^{[n]}=nhx^{[n-1]}.$

(10)

Na zasadzie indukcji można dowieść, że

${\begin{aligned}\Delta ^{k}x^{[n]}&=n(n-1)\ldots {\big [}n-(k-1){\big ]}\ h^{k}x^{[n-k]}\\[1ex]&={\frac {n!}{(n-k)!}}\ h^{k}x^{[n-k]},\qquad k=1,2,\dots ,n.\end{aligned}}$

Ponieważ $x^{[n]}$ jest wielomianem n-tego stopnia więc oczywiście $\Delta ^{k}x^{[n]}=0,\;\;\mathrm {gdy} \;k>n.$

Pierwsza formuła Newtona

Dane są wartości $y_{i}=f(x_{i})$ funkcji $y=f(x)$ na zbiorze równoodległych punktów $x_{i}=x_{0}+ih,\;i=0,1,2,\dots ,n.$ Należy zbudować wielomian interpolacyjny $P(x)$ taki, który spełnia warunki

$P_{n}(x_{i})=f(x_{i}),\quad i=0,1,\dots ,n.$

(11)

Warunki te są równoważne warunkom

$\Delta ^{m}P_{n}(x_{0})=\Delta ^{m}y_{0},\quad m=0,1,\dots ,n.$

Zgodnie z koncepcją Newtona wielomianu $P_{n}(x)$ będziemy poszukiwać w postaci

${\begin{aligned}P_{n}(x)=a_{0}&+a_{1}(x-x_{0})\\[1ex]&+a_{2}(x-x_{0})(x-x_{1})\\[1ex]&\ldots \\[1ex]&+a_{n}(x-x_{0})(x-x_{1})\ldots (x-x_{n-1})\end{aligned}}$

lub

${\begin{aligned}P_{n}(x)=a_{0}&+a_{1}(x-x_{0})^{[1]}\\[1ex]&+a_{2}(x-x_{0})^{[2]}\\[1ex]&\ldots \\[1ex]&+a_{n}(x-x_{0})^{[n]}.\end{aligned}}$

(12)

Korzystając ze wzoru (10), możemy napisać

${\begin{aligned}P_{n}(x)=a_{0}&+a_{1}(x-x_{0})^{[1]}\\&+a_{2}(x-x_{0})^{[2]}\\&\ldots \\&+a_{n}(x-x_{0})^{[n]},\\\\\Delta P_{n}(x)=0&+a_{1}\Delta (x-x_{0})^{[1]}\\&+a_{2}\Delta (x-x_{0})^{[2]}\\&\ldots \\&+a_{n}\Delta (x-x_{0})^{[n]}\\[4px]=a_{1}h&+2a_{2}(x-x_{0})^{[1]}h\\&+3a_{3}(x-x_{0})^{[2]}h\\&\ldots \\&+na_{n}(x-x_{0})^{[n-1]}h,\\\\\Delta ^{2}P_{n}(x)=0&+1\cdot 2h^{2}a_{2}\\&+2\cdot 3h^{2}a_{3}(x-x_{0})^{[1]}\\&\ldots \\&+(n-1)nh^{2}(x-x_{0})^{[n-1]}\\[4px]=1\cdot 2a_{2}h^{2}&+2\cdot 3a_{3}(x-x_{0})h^{2}\\&\ldots \\&+(n-1)n(x-x_{0})^{[n-2]}h^{2},\end{aligned}}$

$............................................$

$\Delta ^{m}P_{n}(x)=\sum _{i=m}^{n}{\frac {i!}{(i-m)!}}a_{i}(x-x_{0})^{[i-m]}h^{m}.$

(13)

Ze wzoru (13) wynika, że dla $m=0,1,2,\dots ,n\;\;\mathrm {i} \;\;0^{[0]}=1$

$\Delta ^{m}P_{n}(x_{0})=\sum _{i=m}^{n}{\frac {i!}{(i-m)!}}a_{i}(x_{0}-x_{0})^{[i-m]}h^{m}=m!h^{m}a_{m}\quad \to \quad a_{m}={\frac {\Delta ^{m}P_{n}(x_{0})}{m!h^{m}}}.$

(14)

Na podstawie (12) i (14) otrzymujemy interpolacyjny wielomian Newtona w postaci

${\begin{aligned}P_{n}(x)=y_{0}+{}&{\frac {\Delta y_{0}}{1!h}}(x-x_{0})^{[1]}\\[1ex]+\ &{\frac {\Delta ^{2}y_{0}}{2!h^{2}}}(x-x_{0})^{[2]}\\[1ex]\ldots &\\[1ex]+\ &{\frac {\Delta ^{n}y_{0}}{n!h^{n}}}(x-x_{0})^{[n]}\\[1ex]=\sum _{i=0}^{n}&{\frac {\Delta ^{i}y_{0}}{i!h^{i}}}(x-x_{0})^{[i]},\quad \Delta ^{0}=1,\end{aligned}}$

(15)

gdzie:

$y_{0}=P_{n}(x_{0})=a_{0}.$

Na podstawie wzoru (15) można obliczyć wartości $P_{n}(x_{k}),\;k=1,2,\dots ,n,$ uwzględniając, że

${\begin{aligned}(x_{k}-x_{0})^{[i]}&=(x_{k}-x_{0})(x_{k}-x_{1})\ldots \,(x_{k}-x_{i-1})\\[1ex]&=k(k-1)(k-2)\ldots \,{\big [}k-(i-1){\big ]}h^{i}={\frac {k!}{(k-i)!}}h^{i},\end{aligned}}$

$(1+\Delta )^{k}=\sum _{i=0}^{n}C\;\!_{k}^{i}\Delta ^{i},\quad C\;\!_{k}^{i}={\frac {k!}{i!(k-i)!}}.$

Ostatecznie otrzymujemy

$P_{n}(x_{k})=\sum _{i=0}^{n}{\frac {\Delta ^{i}y_{0}}{i!h^{i}}}{\frac {k!}{(k-i)!}}h^{i}=\sum _{i=0}^{n}C\;\!_{k}^{i}\Delta ^{i}y_{0}=(1+\Delta )^{k}y_{0}.$

Po wprowadzeniu nowej zmiennej

$q={\frac {x-x_{0}}{h}}\quad \to \quad q^{[i]}={\frac {(x-x_{0})^{[i]}}{h^{i}}}$

wzór (15) przyjmuje postać pierwszej formuły Newtona

$P_{n}(x)=\sum _{i=0}^{n}{\frac {\Delta ^{i}y_{0}}{i!}}q^{[i]},\quad q^{[i]}=q(q-1)(q-2)\ldots \,{\big [}q-(i-1){\big ]},$

(16)

przy czym

${\frac {q^{[i]}}{i!}}=\sum _{m=1}^{i}c_{mi}\lambda ^{m}.$

Współczynniki $c_{mi},\;i=1,2,\dots ,n$ zostały stablicowane.

Dla $n=1,2,3$ otrzymujemy

• $P_{1}(x)=y_{0}+q\Delta y_{0}\quad {}$ – dla interpolacji liniowej,
• $P_{2}(x)=y_{0}+q\Delta y_{0}+{\frac {q(q-1)}{2}}\Delta ^{2}y_{0}\quad {}$ – dla interpolacji kwadratowej,
• $P_{3}(x)=y_{0}+q\Delta y_{0}+{\frac {q(q-1)}{2!}}\Delta ^{2}y_{0}+{\frac {q(q-1)(q-2)}{3!}}\Delta ^{3}y_{0}\quad {}$ – dla interpolacji sześciennej.

Druga formuła Newtona

Tym razem poszukuje się wielomianu o postaci

${\begin{aligned}P_{n}(x)&=a_{0}\\&\quad +a_{1}(x-x_{n})\\&\quad +a_{2}(x-x_{n})(x-x_{n-1})\\&\quad \ldots \\&\quad +a_{n}(x-x_{n})(x-x_{n-1})\ldots (x-x_{1})\\&=\sum _{i=0}^{n}a_{i}(x-x_{n-i+1})^{[i]},\end{aligned}}$

gdzie:

$(x-x_{k})^{[i]}=(x-x_{n})(x-x_{n-1})(x-x_{n-2})\ldots (x-x_{k}).$

Dla obliczenia współczynników $a_{i},\;i=0,1,\dots ,n$ wykorzystuje się wzory na kolejne różnice

${\begin{aligned}\Delta P_{n}(x)=0&+a_{1}\ h\\&+a_{2}\ 2h(x-x_{n-1})\\&+a_{3}\ 3h(x-x_{n-2})^{[2]}\\&\ldots \\&+a_{n}\ nh(x-x_{1})^{[n-1]},\end{aligned}}$

${\begin{aligned}\Delta ^{2}P_{n}(x)&=1\cdot 2a_{2}h^{2}\\&\,+2\cdot 3a_{3}h^{2}(x-x_{n-2})\\&\,+3\cdot 4a_{4}h^{2}(x-x_{n-3})^{[2]}\\&\,\dots \\&\,+n(n-1)a_{n}h^{2}(x-x_{1})^{[n-2]},\end{aligned}}$

${\begin{aligned}\Delta ^{3}P_{n}(x)&=1\cdot 2\cdot 3a_{3}h^{3}\\&\,+2\cdot 3\cdot 4a_{4}h3(x-x_{n-3})\\&\,\dots \\&\,+(n-2)(n-1)na_{n}h^{3}(x-x_{1})^{[n-3]},\end{aligned}}$

$................................$

$\Delta ^{m}P_{n}(x)=\sum _{i=m}^{n}{\frac {i!}{(i-m)!}}a_{i}h^{m}(x-x_{n-i+1})^{[i-m]}.$

Z powyższych wzorów wynika, że

$a_{m}={\frac {\Delta ^{m}P_{n}(x_{n-m})}{m!h^{m}}}$

i dzięki temu poszukiwany wielomian można zapisać w postaci

${\begin{aligned}P_{n}(x)&=\sum _{i=0}^{n}{\frac {\Delta ^{i}P_{n}(x_{n-i})}{i!h^{i}}}(x-x_{n-i+1})^{[i]}\\&=P_{n}(x_{n})+{\frac {\Delta ^{1}P_{n}(x_{n-1})}{1!h}}(x-x_{n})\\&\qquad \qquad \;+{\frac {\Delta ^{2}P_{n}(x_{n-2})}{2!h^{2}}}(x-x_{n})(x-x_{n-1})\\[1ex]&\qquad \qquad \;\ldots \\[1ex]&\qquad \qquad \;+{\frac {\Delta ^{n}P_{n}(x_{0})}{n!h^{n}}}(x-x_{n})(x-x_{n-1})\ldots (x-x_{1}).\end{aligned}}$

Po wprowadzeniu nowej zmiennej

$q={\frac {x-x_{n}}{h}}\quad \to \quad {\frac {x-x_{n-i}}{h}}=q+i,\quad i=0,1,\dots ,n-1$

powstaje druga formuła Newtona

${\begin{alignedat}{1}P_{n}(x)&=P_{n}(x_{n})&{}+{}q\Delta P_{n}(x_{n-1})\\[1ex]&&{}+{}{\frac {q(q+1)}{2!}}\Delta ^{2}P_{n}(x_{n-2})\\&&{}+{}{\frac {q(q+1)(q+2)}{3!}}\Delta ^{3}P_{n}(x_{n-3})\\&&\ \ldots \\&&{}+{}{\frac {q(q+1)\ldots {\big [}q+(n-1){\big ]}}{n!}}\Delta ^{n}P_{n}(x_{0})\\&=P_{n}(x_{n})&{}+{}\sum _{i=1}^{n}{\frac {q^{[i]}}{i!}}\Delta ^{i}P_{n}(x_{n-i}),\end{alignedat}}$

gdzie:

$q^{[i]}=q(q+1)(q+2)\ldots {\big [}q+(i-1){\big ]},\quad i=1,2,\dots ,n.$

Uwagi do formuł Newtona

Zarówno pierwsza, jak i druga formuła Newtona umożliwiają nie tylko interpolację w przedziale $(x_{0},\,x_{1}),$ ale również ekstrapolację na zewnątrz tego przedziału. Tak więc formułę pierwszą stosuje się do interpolacji wprzód i ekstrapolacji wstecz z punktu $x_{0},$ a formułę drugą do interpolacji wstecz i ekstrapolacji wprzód z punktu $x_{n}.$ Przy czym ekstrapolacja jest mniej dokładna od interpolacji.

Za pomocą obydwu formuł możliwa jest interpolacja tzw. różnicami centralnymi. Należy w tm celu, w przypadku korzystania z formuły pierwszej, zastosować wzory

$x_{i}=x_{0}+ih,\quad i=0,\,\pm 1,\,\pm 2,\dots ,\quad y_{i}=f(x_{i}),$

$\Delta y_{i}=y_{i+1}-y_{i},\quad \Delta ^{2}y_{i}=\Delta y_{i+1}-\Delta y_{i}\quad {}$ itd.

Pierwsza formuła Gaussa

Dane jest $2n+1$ równo odległych węzłów interpolacji

$x_{-n},\,x_{n-1},\dots ,\,x_{-1},\,x_{0},\,x_{1},\,x_{2},\dots ,\,x_{n-1},\,n,$

gdzie:

$\Delta x_{i}=x_{i+1}-x_{i}=h=\mathrm {const} ,\quad i=-n,\,-(n-1),\dots ,\,n-1.$

Dane są również wartości funkcji interpolowanej

$y_{i}=f(x_{i}),\quad i=0,\,\pm 1,\dots ,\,\pm n.$

Należy zbudować wielomian $P_{2n+1}(x)$ taki, że

$P_{2n+1}(x_{i})=y_{i},\quad i=0,\,\pm 1,\dots ,\pm n.$

Z żądania tego wynika, że

$\Delta ^{k}P_{2n+1}(x_{i})=\Delta ^{k}y_{i}\quad {}$ dla ${}\;i,k,\dots$

(a)

Wielomianu szukamy w postaci

${\begin{aligned}P_{2n+1}(x)=a_{0}&+a_{1}(x-x_{0})\\&+a_{2}(x-x_{0})(x-x_{1})\\&+a_{3}(x-x_{-1})(x-x_{0})(x-x_{1})\\&+a_{4}(x-x_{-1})(x-x_{0})(x-x_{1})(x-x_{2})\\&+a_{5}(x-x_{-2})(x-x_{-1})(x-x_{0})(x-x_{1})(x-x_{2})\\&\ldots \\&+a_{2n-1}(x-x_{-(n-1)})\ldots (x-x_{-1})(x-x_{0})(x-x_{1})\ldots (x-x_{n-1})\\&+a_{2n}(x-x_{-(n-1)})\ldots (x-x_{-1})(x-x_{0})(x-x_{1})\ldots (x-x_{n-1})(x-x_{n})\\=a_{0}&+a_{1}(x-x_{0})^{[1]}\\&+a_{2}(x-x_{0})^{[2]}\\&+a_{3}(x-x_{-1})^{[3]}\\&+a_{4}(x-x_{-1})^{[4]}\\&\ldots \\&+a_{2n-1}(x-x_{-(n-1)})^{[2n-1]}\\&+a_{2n}(x-x_{-(n-1)})^{[2n]}.\end{aligned}}$

Współczynniki wielomianu $P_{2n+1}(x)$ oblicza się w ten sam sposób co w formułach Newtona, wykorzystując wzór (a). Otrzymujemy w ten sposób wzory

$a_{0}=y_{0},\quad a_{2m-1}={\frac {\Delta ^{2m-1}y_{-(m-1)}}{(2m-1)!h^{2m-1}}},\quad a_{2m}={\frac {\Delta ^{2m}y_{-m}}{(2m)!h^{2m}}},\quad m=1,2,\dots ,n.$

Wprowadzając nową zmienną

$q={\frac {x-x_{0}}{h}},$

otrzymujemy pierwszą formułę Gaussa w postaci

${\begin{aligned}P_{2n+1}(x)=y_{0}&+q\Delta y_{0}\\[1ex]&+{\frac {q(q-1)}{2!}}\Delta ^{2}y_{-1}\\&+{\frac {(q+1)q(q-1)}{3!}}\Delta ^{3}y_{-1}\\&+{\frac {(q+1)q(q-1)(q-2)}{4!}}\Delta ^{4}y_{-2}\\&+{\frac {(q+2)(q+1)q(q-1)(q-2)}{5!}}\Delta ^{5}y_{-2}\\[1ex]&\ldots \\[1ex]&+{\frac {(q+n-1)\ldots \,(q-n+1)}{(2n-1)!}}\Delta ^{2n-1}y_{-(n-1)}\\&+{\frac {(q+n-1)\ldots \,(q-n)}{(2n)!}}\Delta ^{2n}y_{-n}\end{aligned}}$

(b)

albo krócej

${\begin{aligned}P_{2n+1}(x)=y_{0}&+q\Delta y_{0}\\[1ex]&+{\frac {q^{[2]}}{2!}}\Delta ^{2}y_{-1}\\[1ex]&+{\frac {(q+1)^{[3]}}{3!}}\Delta ^{3}y_{-1}\\[1ex]&+{\frac {(q+1)^{[4]}}{4!}}\Delta ^{4}y_{-2}\\[1ex]&\ldots \\[1ex]&+{\frac {(q+n-1)^{[2n-1]}}{(2n-1)!}}\Delta ^{2n-1}y_{-(n-1)}\\[1ex]&+{\frac {(q+n-1)^{[2n]}}{(2n)!}}\Delta ^{2n}y_{-n},\end{aligned}}$

(c)

gdzie:

$q={\frac {x-x_{0}}{h}},\quad q^{[m]}=q(q-1)\ldots \,{\big [}q-(m-1){\big ]}.$

Ta formuła zawiera różnice

$\Delta y_{0},\;\Delta ^{2}y_{-1},\;\Delta ^{3}y_{-1},\;\Delta ^{4}y_{-2},\;\Delta ^{5}y_{-2},\;\Delta ^{6}y_{-3},\dots ,\Delta ^{2n-1}y_{-(n-1)},\;\Delta ^{2n}y_{-n}.$

Druga formuła Gaussa

Druga formuła Gaussa ma postać

${\begin{aligned}P_{2n+1}(x)=y_{0}&+q\Delta y_{-1}\\[2px]&+{\frac {(q+1)^{[2]}}{2!}}\Delta ^{2}y_{-1}\\[2px]&+{\frac {(q+1)^{[3]}}{3!}}\Delta ^{3}y_{-2}\\[2px]&+{\frac {(q+2)^{[4]}}{4!}}\Delta ^{4}y_{-2}\\[2px]&\ldots \\[2px]&+{\frac {(q+n-1)^{[2n-1]}}{(2n-1)!}}\Delta ^{2n-1}y_{-n}\\[2px]&+{\frac {(q+n)^{[2n]}}{(2n)!}}\Delta ^{2n}y_{-n},\end{aligned}}$

(c)

gdzie:

$q={\frac {x-x_{0}}{h}}.$

Ta formuła zawiera różnice

$\Delta y_{-1},\;\Delta ^{2}y_{-1},\;\Delta ^{3}y_{-2},\;\Delta ^{4}y_{-2},\;\Delta ^{5}y_{-3},\;\Delta ^{6}y_{-3},\dots ,\Delta ^{2n-1}y_{-n},\;\Delta ^{2n}y_{-n}.$

Formuła Stirlinga

Tę formułę otrzymuje się jako średnią arytmetyczną obydwu formuł Gaussa

${\begin{aligned}P_{2n+1}(x)=y_{0}&+q\cdot {\frac {\Delta y_{-1}+\Delta y_{0}}{2}}\\[1ex]&+{\frac {q^{2}}{2}}\cdot \Delta ^{2}y_{-1}\\[2px]&+{\frac {q(q^{2}-1^{2})}{3!}}\cdot {\frac {\Delta ^{3}y_{-2}+\Delta ^{3}y_{-1}}{2}}\\[1ex]&+{\frac {q^{2}(q^{2}-1^{2})}{4!}}\cdot \Delta ^{4}y_{-2}\\[1ex]&+{\frac {q(q^{2}-1^{2})(q^{2}-2^{2})}{5!}}\cdot {\frac {\Delta ^{5}y_{-3}+\Delta ^{5}y_{-2}}{2}}\\[1ex]&+{\frac {q^{2}(q^{2}-1^{2})(q^{2}-2^{2})}{6!}}\cdot \Delta ^{6}y_{-3}\\[1ex]&\ldots \\[1ex]&+{\frac {q(q^{2}-1^{2})(q^{2}-2^{2})(q^{2}-3^{2})\ldots {\big [}q^{2}-(n-1)^{2}{\big ]}}{(2n-1)!}}\\[1ex]&\qquad \cdot {\frac {\Delta ^{2n-1}y_{-n}+\Delta ^{2n-1}y_{-(n-1)}}{2}}\\[1ex]&+{\frac {q^{2}(q^{2}-1^{2})(q^{2}-2^{2})\ldots {\big [}q^{2}-(n-1)^{2}{\big ]}}{(2n)!}}\Delta ^{2n}y_{-n},\end{aligned}}$

gdzie:

$q={\frac {x-x_{0}}{h}}.$

Formuła Bessela

Formułę Bessela można wyprowadzić na podstawie drugiej formuły Gaussa zapisanej dla punktu początkowego $x_{1}.$ W tym celu we wzorze (c) należy: 1) powiększyć o 1 wartości indeksów w różnicach skończonych i 2) zmniejszyć o 1 wartości zmiennej $q.$ W ten sposób otrzymuje się

${\begin{aligned}P_{2n+1}&=y_{1}+(q-1)\Delta y_{0}\\&+{\frac {q(q-1)}{2!}}\Delta ^{2}y_{0}\\&+{\frac {q(q-1)(q-2)}{3!}}\Delta ^{3}y_{-1}\\&+{\frac {(q+1)q(q-1)(q-2)}{4!}}\Delta ^{4}y_{-1}\\&+{\frac {(q+1)q(q-1)(q-2)(q-3)}{5!}}\Delta ^{5}y_{-2}\\[1ex]&\ldots \\[1ex]&+{\frac {(q+n-2)\ldots (q-n)}{(2n-1)!}}\Delta ^{2n-1}y_{-(n-1)}\\&+{\frac {(q+n-1)\ldots (q-n)}{(2n)!}}\Delta ^{2n}y_{-(n-1)}.\end{aligned}}$

(d)

Średnia arytmetyczna wzorów (c) i (d), po pewnych przekształceniach, daje w wyniku formułę Bessela

${\begin{aligned}P_{2n+1}(x)&={\frac {y_{0}+y_{1}}{2}}\\&+(q-{\tfrac {1}{2}})\cdot \Delta y_{0}\\&+{\frac {q(q-1)}{2!}}\cdot {\frac {\Delta ^{2}y_{-1}+\Delta ^{2}y_{0}}{2}}\\&+{\frac {(q-{\tfrac {1}{2}})q(q-1)}{3!}}\cdot \Delta ^{3}y_{-1}\\&+{\frac {q(q-1)(q+1)(q-2)}{4!}}\cdot {\frac {\Delta ^{4}y_{-2}+\Delta ^{4}y_{-1}}{2}}\\&+{\frac {(q-{\tfrac {1}{2}})q(q-1)(q+1)(q-2)}{5!}}\cdot \Delta ^{5}y_{-2}\\&+{\frac {q(q-1)(q+1)(q-2)(q+2)(q-3)}{6!}}\cdot {\frac {\Delta ^{6}y_{-3}+\Delta ^{6}y_{-2}}{2}}\\[1ex]&\ldots \\[1ex]&+{\frac {q(q-1)(q+1)(q-2)(q+2)\ldots (q-n)(q+n-1)}{2n!}}\cdot {\frac {\Delta ^{2n}y_{-n}+\Delta ^{2n}y_{-n+1}}{2}}\\&+{\frac {(q-{\tfrac {1}{2}})q(q-1)(q+1)(q-2)(q+2)\ldots (q-n)(q+n-1)}{(2n+1)!}}\cdot \Delta ^{2n+1}y_{-n}.\end{aligned}}$

Formuła Lagrange’a

Wspólną cechą wszystkich metod różnicowych jest założenie, że

$x_{i+1}=x_{i}+h,\;\;dla\;\;i=0,1,\dots ,h=\mathrm {const} .$

W formule Lagrange’a założenie to nie jest spełnione i dlatego nie jest ona zaliczana do formuł różnicowych.

Na odcinku $[a,b]$ dane są węzły interpolacji $x_{0},\,x_{1},\dots ,\,n$ i wartości $y_{i}=f(x_{i})$ interpolowanej funkcji $y=f(x).$ Poszukiwany jest wielomian $P_{n}(x)$ stopnia $n$ taki, który spełnia warunki

$P_{n}(x_{i})=y_{i}.\quad i=0,1,\dots ,n.$

Budujemy wielomian

$\varphi _{i}(x)=a_{i}(x-x_{0})(x-x_{1})\ldots (x-x_{i-1})(x-x_{i+1})\ldots (x-x_{n})$

taki, że $\varphi _{i}(x_{j})=\delta _{ij}{\begin{cases}\;1\quad {\text{gdy}}\;j=i,\\\;0\quad {\text{gdy}}\;j\neq i.\end{cases}}$

Stąd

${\begin{aligned}&\varphi _{i}(x_{i})=a_{i}(x_{i}-x_{0})(x_{i}-x_{1})\ldots (x_{i}-x_{i-1})(x_{i}-x_{i+1})\ldots (x_{i}-x_{n})=1,\\[1em]&a_{i}={\frac {1}{(x_{i}-x_{0})(x_{i}-x_{1})\ldots (x_{i}-x_{i-1})(x_{i}-x_{i+1})\ldots (x_{i}-x_{n})}},\\\\\end{aligned}}$

$\varphi _{i}(x)={\frac {(x-x_{0})(x-x_{1})\ldots (x-x_{i-1})(x-x_{i+1})\ldots (x-x_{n})}{(x_{i}-x_{0})(x_{i}-x_{1})\ldots (x_{i}-x_{i-1})(x_{i}-x_{i+1})\ldots (x_{i}-x_{n})}}$

(e)

i formuła Lagrange’a ma postać

$P_{n}(x)=\sum _{i=0}^{n}\varphi _{i}(x)y_{i}.$

Funkcję $\varphi _{i}(x)$ można zapisać w sposób bardziej zwarty, posługując się wielomianem

$w(x)=(x-x_{0})(x-x_{1})\ldots (x-x_{n})$

i jego pochodną

${\begin{aligned}w^{'}(x)&=\sum _{i=0}^{n}(x-x_{0})(x-x_{1})\ldots (x-x_{i-1})(x-x_{i+1})\ldots (x-x_{n})\\&=\sum _{i=0}^{n}{\frac {w(x)}{x-x_{i}}},\end{aligned}}$

$w^{'}(x_{i})=(x_{i}-x_{0})(x_{i}-x_{1})\ldots (x_{i}-x_{i-1})(x_{i}-x_{i+1})\ldots (x-x_{n}).$

Stąd na podstawie wzoru (e) dla $i=0,1,\dots ,n$

$\varphi _{i}(x)={\frac {w(x)}{(x-x_{i})w^{'}(x_{i})}}={\frac {w(x)}{D_{i}(x)}},$

(f)

gdzie:

${\begin{aligned}D_{i}(x)&=(x-x_{i})w^{'}(x_{i})\\[1ex]&=(x_{i}-x_{0})(x_{i}-x_{2})\\[1ex]&\qquad \ldots (x_{i}-x_{i-1})(x-x_{i})(x_{i}-x_{i+1})\\[1ex]&\qquad \ldots (x_{i}-x_{n}).\end{aligned}}$

Wielomian $D_{i}(x)$ można obliczyć jako iloczyn elementów tworzących wiersz $i+1$ macierzy

${\begin{bmatrix}x-x_{0}&x_{0}-x_{1}&x_{0}-x_{2}&\ldots &x_{0}-x_{n}\\x_{1}-x_{0}&x-x_{1}&x_{1}-x_{2}&\ldots &x_{1}-x_{n}\\x_{2}-x_{0}&x_{2}-x_{1}&x-x_{2}&\ldots &x_{2}-x_{n}\\\ldots &\ldots &\ldots &\ldots &\ldots \\x_{n}-x_{0}&x_{n}-x_{1}&x_{n}-x_{2}&\ldots &x-x_{n}\end{bmatrix}}.$

• Przykłady
• 1) Interpolacja liniowa: $n=1.$

${\begin{aligned}w(x)&=(x-x_{0})(x-x_{1}),\\[1ex]w^{'}(x)&=(x-x_{1})+(x-x_{0}),\\[1ex]w^{'}(x_{0})&=x_{0}-x_{1},\\[1ex]w^{'}(x_{1})&=x_{1}-x_{0},\\[2ex]\varphi _{0}(x)&={\frac {x-x_{1}}{x_{0}-x_{1}}},\\[1ex]\varphi _{1}(x)&={\frac {x-x_{0}}{x_{1}-x_{0}}},\\[2ex]P_{n}(x)&=\varphi _{0}(x)y_{0}+\varphi _{1}(x)y_{1}.\end{aligned}}$

• 2) Interpolacja kwadratowa: $n=2.$

${\begin{aligned}w(x)&=(x-x_{0})(x-x_{1})(x-x_{2}),\\[1ex]w^{'}(x)&=(x-x_{1})(x-x_{2})+(x-x_{0})(x-x_{2})+(x-x_{0})(x-x_{1}),\\[1ex]w^{'}(x_{0})&=(x_{0}-x_{1})(x_{0}-x_{2}),\\[1ex]w^{'}(x_{1})&=(x_{1}-x_{0})(x_{1}-x_{2}),\\[1ex]w^{'}(x_{2})&=(x_{2}-x_{0})(x_{2}-x_{1}),\\[2ex]\varphi _{0}(x)&={\frac {(x-x_{1})(x-x_{2})}{(x_{0}-x_{1})(x_{0}-x_{2})}},\\[1ex]\varphi _{1}(x)&={\frac {(x-x_{0})(x-x_{2})}{(x_{1}-x_{0})(x_{1}-x_{2})}},\\[1ex]\varphi _{2}(x)&={\frac {(x-x_{0})(x-x_{1})}{(x_{2}-x_{0})(x_{2}-x_{1})}},\\[2ex]P_{n}(x)&=\varphi _{0}(x)y_{0}+\varphi _{1}(x)y_{1}+\varphi _{2}(x)y_{2}.\end{aligned}}$

W przypadku szczególnym, gdy węzły są równoodległe:

$x_{i+1}=x_{i}+h,\quad h=\mathrm {const} ,\quad i=0,1,\dots ,n$

można wprowadzić nową zmienną $q={\frac {x-x_{0}}{h}}$ i wtedy

$w(x)=q(q-1)(q-2)\ldots (q-n)h^{n+1},$

$D_{m}(x)=(x-x_{m})w^{'}(x_{m})=(q-m)(-1)^{n-m}m!(n-m)!h^{n+1},$

$\varphi _{m}(x)={\frac {w(x)}{D_{m}(x)}}.$

Wielomian $D_{m}(x)$ można utworzyć jako iloczyn elementów wiersza $m+1$ macierzy

${\begin{bmatrix}q&-1&-2&-3&\ldots &-n\\1&q-1&-1&-2&\ldots &-(n-1)\\2&1&q-2&-1&\ldots &-(n-2)\\\ldots &\ldots &\ldots &\ldots &\ldots &\ldots &\\n&n-1&n-2&n-3&\ldots &q-n\end{bmatrix}}.$

Różnice uogólnione

Różnicowe podejście do interpolacji funkcji $y=f(x)$ o wartościach danych na zbiorze węzłów równoodległych

${}\quad x_{i+1}=x_{i}+h,\quad h=\mathrm {const} ,\quad i=0,1,\dots$

można uogólnić na przypadek węzłów, które nie są równoodległe.

W tym celu wprowadza się pojęcie różnicy uogólnionej (pierwszego rzędu) zdefiniowanej jako

$[x_{i},\,x_{i+1}]={\frac {y_{i+1}-y_{i}}{x_{i+1}-x_{i}}},\quad i=0,1,\dots ,$

przy czym

$\Delta x_{i}=x_{i+1}-x_{i}\neq 0,\quad i=0,1,\dots$

Na przykład

$[x_{0},\,x_{1}]={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}},\quad [x_{1},\,x_{2}]={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}},\quad \ldots$

Analogicznie określa się różnice uogólnione drugiego rzędu

$[x_{i},\,x_{i+1},\,x_{i+2}]={\frac {[x_{i+1},\,x_{i+2}]-[x_{i},\,x_{i+1}]}{x_{i+2}-x_{i}}},\quad \ldots$

Na przykład

$[x_{0},\,x_{1},\,x_{2}]={\frac {[x_{1},\,x_{2}]-[x_{0},\,x_{1}]}{x_{2}-x_{0}}}.$

Ogólnie

$[x_{i},\,x_{i+1},\dots ,\,x_{i+n}]={\frac {[x_{i+1},\dots ,\,x_{i+n}]-[x_{i},\dots ,\,x_{i+n-1}]}{x_{i+n}-x_{i}}},$

${}\qquad i=0,1,2,\dots ,\quad n=1,2,\dots$

Ważną własnością różnic uogólnionych jest ich symetria względem swoich argumentów. Na przykład

$[x_{0},\,x_{1}]={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}={\frac {y_{0}-y_{1}}{x_{0}-x_{1}}}=[x_{1},\,x_{0}]$

lub

$[x_{0},\,x_{1},\dots ,\,x_{k},\,x_{k+1},\dots ,\,x_{m}]=[x_{0},\,x_{1},\dots ,\,x_{k+1},\,x_{k},\dots ,\,x_{m}],$

$k=0,1,\dots ,\,m-1,\quad m=1,2,\dots$

Kolejne różnice uogólnione najwygodniej jest obliczać według schematu tablicowego

x	y	rząd 1	rząd 2	rząd 3	rząd 4
$x_{0}$	$y_{0}$
		$[x_{0},\,x_{1}]$
$x_{1}$	$y_{1}$		$[x_{0},\,x_{1},\,x_{2}]$
		$[x_{1},\,x_{2}]$		$[x_{0},\,x_{1},\,x_{2},\,x_{3}]$
$x_{2}$	$y_{2}$		$[x_{1},\,x_{2},\,x_{3}]$		$[x_{0},\,x_{1},\,x_{2},\,x_{3},\,x_{4}]$
		$[x_{2},\,x_{3}]$		$[x_{1},\,x_{2},\,x_{3},\,x_{4}]$
$x_{3}$	$y_{3}$		$[x_{2},\,x_{3},\,x_{4}]$
		$[x_{3},\,x_{4}]$
$x_{4}$	$y_{4}$

Uogólniona formuła Newtona

Lemat: Jeżeli funkcja $y=P_{n}(x)$ jest wielomianem $n$-tego stopnia, to jego różnica uogólniona rzędu $n+1$ jest tożsamościowo równa zeru, tzn.

$[x,\,x_{0},\,x_{1},\dots ,\,x_{n}]\equiv 0$

dla dowolnego zbioru liczb $x,\,x_{0},\,x_{1},\dots ,\,x_{n}$ różniących się od siebie.

• Dowód:

Wielomian $w_{n}(x)=P_{n}(x)-P_{n}(x_{0})$ jest wielomianem, który zeruje się w punkcie $x=x_{0}.$ Ponieważ ten punkt jest pierwiastkiem wielomianu $w_{n}(x)$ więc zgodnie z twierdzeniem Bezout’a wielomian ten dzieli się bez reszty przez dwumian $(x-x_{0}).$ Możemy więc napisać

$[x,\,x_{0}]={\frac {P_{n}(x)-P_{n}(x_{0})}{x-x_{0}}}=P_{n-1}(x),$

przy czym $P_{n-1}(x)$ jest wielomianem stopnia $n-1.$

I dalej

$[x,\,x_{0},\,x_{1}]={\frac {[x,\,x_{0}]-[x_{1},\,x_{0}]}{x-x_{1}}}={\frac {P_{n-1}(x)-P_{n-1}(x_{1})}{x-x_{1}}}=P_{n-2}(x).$

$[x,\,x_{0},\,x_{1},\,x_{2}]={\frac {[x,\,x_{0},\,x_{1}]-[x_{2},\,x_{0},\,x_{1}]}{x-x_{2}}}={\frac {P_{n-2}(x)-P_{n-2}(x_{2})}{x-x_{2}}}=P_{n-3}(x),$

$..................................$

${\begin{aligned}{}[x,\,x_{0},\,x_{1},\dots ,\,x_{m}]&={\frac {[x,\,x_{0},\,x_{1},\dots ,\,x_{m-1}]-[x_{m},\,x_{0},\,x_{1},\dots ,\,x_{m-1}]}{x-x_{m}}}\\&={\frac {P_{n-m}(x)-P_{n-m}(x_{m})}{x-x_{m}}}=P_{n-(m+1)}(x),\end{aligned}}$

$..................................$

$[x,\,x_{0},\,x_{1},\dots ,\,x_{n}]={\frac {P_{0}(x)-P_{0}(x_{n})}{x-x_{n}}}={\frac {C-C}{x-x_{n}}}\equiv 0.\qquad {}$ c.n.d.

Z powyższych związków wynika następująca formuła rekurencyjna

$P_{n-m}(x)=P_{n-m}(x_{m})+P_{n-(m+1)}(x)(x-x_{m}),$

dzięki której otrzymujemy uogólnioną formułę Newtona dla węzłów nierówno odległych

${\begin{aligned}P_{n}(x)=P_{n}(x_{0})&+P_{n-1}(x)(x-x_{0})\\[1ex]=P_{n}(x_{0})&+P_{n-1}(x_{1})(x-x_{0})\\[1ex]&+P_{n-2}(x_{2})(x-x_{0})(x-x_{1})\\[1ex]&\ldots \\[1ex]&+P_{n-m}(x_{m})(x-x_{0})(x-x_{1})\ldots \,(x-x_{m-1})\\[1ex]&\ldots \\[1ex]&+P_{0}(x_{n})(x-x_{0})(x-x_{1})\ldots \,(x-x_{n-1})\\[1ex]&+0\cdot (x-x_{0})(x-x_{1})\ldots \,(x-x_{n}),\end{aligned}}$

gdzie:

$P_{n-m}(x)=[x,\,x_{0},\,x_{1},\dots ,\,x_{m-1}],\quad m=1,2,\dots ,n.$

Interpolacja odwrotna

Dany jest zbiór wartości rzędnych $y_{0},\,y_{1},\dots ,\,y_{n}$ monotonicznej funkcji $y=f(x),$ określonych na zbiorze węzłów $x_{0},\,x_{1},\dots ,\,x_{n}.$

Interpolacja odwrotna polega na tym, aby obliczyć taką wartość argumentu $x\in [x_{0},\,x_{1}]$ funkcji $f(x),$ która odpowiada jej danej wartości $y\in [y_{0},\,y_{1}].$ Interpolację taką najczęściej stosuje się wtedy, gdy wartości funkcji $f(x)$ dane są za pomocą tablicy zawierającej wartości jej rzędnych $y_{i},\;i=0,1,\dots ,n.$

W przypadku węzłów równoodległych funkcję $y=f(x)$ można interpolować wielomianem Newtona o postaci

$y=y_{0}+{\frac {\Delta y_{0}}{1!}}q+{\frac {\Delta ^{2}y_{0}}{2!}}q(q-1)+\ldots +{\frac {\Delta ^{n}y_{0}}{n!}}q(q-1)\ldots \,(q-n+1),$

gdzie:

$q={\frac {x-x_{0}}{h}}.$

Zadanie interpolacji odwrotnej rozwiązuje się metodą iteracyjną kolejnych przybliżeń, przy czym korzysta się ze wzoru

$q=\varphi (q),$

w którym

${\begin{aligned}\varphi (q)&={\frac {y-y_{0}}{\Delta y_{0}}}\\[1ex]&-{\frac {\Delta ^{2}y_{0}}{2!\Delta y_{0}}}q(q-1)\\&\ldots \\&-{\frac {\Delta ^{n}y_{0}}{n!\Delta y_{0}}}q(q-1)\ldots \,(q-n+1).\end{aligned}}$

Jako pierwsze przybliżenie przyjmuje się wartość

$q_{0}={\frac {y-y_{0}}{\Delta y_{0}}},$

a następne przybliżenia otrzymuje się iteracyjnie według wzoru

$q_{m}=\varphi (q_{m-1}),\quad m=1,2,\dots$

aż do osiągnięcia wymaganej dokładności. Poszukiwaną wartość $x$ oblicza się według wzoru

$x=x_{0}+qh.$

W przypadku, gdy węzły nie są równoodległe wartość $x,$ można obliczyć, stosując formułę Newtona o postaci

${\begin{aligned}x=x_{0}&+[y_{0},\,y_{1}](y-y_{0})\\[1ex]&+[y_{0},\,y_{1},\,y_{2}](y-y_{0})(y-y_{1})\\[1ex]&\ldots \\[1ex]&+[y_{0},\,y_{1},\dots y_{n}](y-y_{0})(y-y_{1})\ldots \,(y-y_{n-1}).\end{aligned}}$

Wartość wyznacznika: $\det(A-\lambda E)$

Wyznacznik charakterystyczny (wiekowy) $D(\lambda )=\det(A-\lambda E)$ macierzy $A(n\times n)$ jest funkcją parametru $\lambda ,$ którą można interpolować na zbiorze węzłów równoodleglych $\lambda _{i}=i,\;i=0,1,2,\dots ,n$ za pomocą formuły Newtona o postaci

$D(\lambda )=D(0)+\sum _{i=1}^{n}{\frac {\Delta ^{i}D(0)}{i!}}\lambda (\lambda -1),\dots ,(\lambda -i+1),$

gdzie:

$\Delta ^{i}D(\lambda )$ jest różnicą skończoną i-tego rzędu funkcji $D(\lambda ).$

Po uwzględnieniu tożsamości

${\frac {\lambda (\lambda -1)\ldots \,(\lambda -i+1)}{i!}}=\sum _{m=1}^{i}c_{mi}\lambda ^{m}$

otrzymujemy wzór Markowa

$D(\lambda )=D(0)+\sum _{m=1}^{n}\lambda ^{m}\sum _{i=m}^{n}c_{mi}\Delta ^{i}D(0).$

W przypadku, gdy $\lambda _{i}=a+ih,\;i=0,1,2,\dots ,n,$ wzór ten przybiera postać

$D(\lambda )=D(a)+\sum _{m=1}^{n}(\lambda -a)^{m}\sum _{i=m}^{n}c_{mi}h^{i}\Delta ^{i}D(a).$

Różnice dwoiste

W przypadku, gdy funkcja dwu zmiennych $z=f(x,y)$ jest określona za pomocą tablicy jej wartości $z_{ij},$ można zdefiniować dwoiste różnice skończone pierwszego rzędu

$\Delta _{x}z_{ij}=z_{i+1,j}-z_{ij},\quad \Delta _{y}z_{ij}=z_{i,j+1}-z_{ij}$

i wyższych rzędów

${\begin{aligned}&\Delta ^{m+n}z_{ij}\\[2px]={}&\Delta _{x^{m}y^{n}}^{m+n}z_{ij}\\[2px]={}&\Delta _{x^{m}}^{m}\left(\Delta _{y^{n}}^{n}z_{ij}\right)\\[2px]={}&\Delta _{x^{n}}^{n}\left(\Delta _{y^{m}}^{m}z_{ij}\right),\end{aligned}}$

przy czym $\Delta ^{0+0}z_{ij}=0.$

Na przykład

${\begin{aligned}\Delta ^{1+2}z_{ij}&=\Delta _{x}(\Delta _{yy}^{2}z_{ij})\\[1ex]&=\Delta _{x}(z_{i,j+2}-2z_{i,j+1}+z_{ij})\\[1ex]&=(z_{i+1,j+2}-2z_{i+1,j+1}+z_{i+1,j})-(z_{i,j+2}-2z_{i,j+1}+z_{ij}).\end{aligned}}$

Dwoista formuła Newtona

Dla funkcji dwu zmiennych $z=f(x,y)$ można zbudować wielomian interpolacyjny Newtona $P(x,y)$ taki, że

$\Delta _{x^{m}y^{n}}^{m+n}P(x_{0},y_{0})=\Delta ^{m+n}f(x_{0},y_{0})=\Delta ^{m+n}z_{00},\;\;m,n=0,1,2,\dots$

Wielomian ten ma następującą postać

${\begin{aligned}P(x,y)=c_{00}&+c_{10}(x-x_{0})\\[1ex]&+c_{01}(y-y_{0})\\[1ex]&+c_{20}(x-x_{0})(x-x_{1})\\[1ex]&+c_{11}(x-x_{0})(y-y_{0})\\[1ex]&+c_{02}(y-y_{0})(y-y_{1})\\[1ex]&\ldots \end{aligned}}$

Podstawiając $x=x_{0},\,y=y_{0},$ otrzymujemy

$P(x_{0},y_{0})=z_{00}=c_{00},$

a na podstawie różnic pierwszego rzędu

$\Delta _{x}P(x,y)=c_{10}h+2c_{20}h(x-x_{0})+c_{11}h(y-y_{0})+\dots ,$

$\Delta _{y}P(x,y)=c_{01}k+c_{11}k(x-x_{0})+2c_{02}k(y-y_{0})+\dots ,$

po podstawieniu $x=x_{0},\;y=y_{0}$

$\Delta _{x}P(x_{0},y_{0})=\Delta ^{1+0}z_{00}=c_{10}h,$

$\Delta _{y}P(x_{0},y_{0})=\Delta ^{0+1}z_{00}=c_{01}k.$

Stąd otrzymujemy

$c_{10}={\frac {\Delta ^{1+0}z_{00}}{h}},\quad c_{01}={\frac {\Delta ^{0+1}z_{00}}{k}}.$

Ze wzorów na różnice drugiego rzędu

$\Delta _{xx}P(x,y)=2!c_{20}h^{2}+\ldots$

$\Delta _{xy}P(x,y)=c_{11}hk+\ldots$

$\Delta _{yy}P(x,y)=2!c_{02}k^{2}+\ldots$

wynika, po podstawieniu $x=x_{0},\;y=y_{0},$ że

$\Delta _{xx}P(x,y)=2!c_{20}h^{2},$

$\Delta _{xy}P(x,y)=c_{11}hk,$

$\Delta _{yy}P(x,y)=2!c_{02}k^{2},$

a stąd

$c_{20}={\frac {1}{2!}}{\frac {\Delta ^{2+0}z_{00}}{h^{2}}},\;\;c_{11}={\frac {\Delta ^{1+1}z_{00}}{hk}},\;\;c_{02}={\frac {1}{2!}}{\frac {\Delta ^{0+2}z_{00}}{k^{2}}}.$

Ostatecznie wielomian interpolacyjny przybiera postać

${\begin{aligned}P(x,y)=z_{00}&+\left[{\frac {\Delta ^{1+0}z_{00}}{h}}(x-x_{0})+{\frac {\Delta ^{0+1}z_{00}}{k}}(y-y_{0})\right]\\&+{\frac {1}{2!}}\left[{\frac {\Delta ^{2+0}z_{00}}{h^{2}}}(x-x_{0})^{2}+2{\frac {\Delta ^{1+1}z_{00}}{hk}}(x-x_{0})(y-y_{0})+{\frac {\Delta ^{0+2}z_{00}}{k^{2}}}(y-y_{0})^{2}\right]\\[1ex]&\ldots \end{aligned}}$

Dla wygody obliczeń wprowadza się nowe zmienne

$p={\frac {x-x_{0}}{h}},\;q={\frac {y-y_{0}}{k}},\;{\frac {x-x_{1}}{h}}=p-1,\;{\frac {y-y_{1}}{k}}=q-1$

i wtedy

${\begin{aligned}P(p,q)=z_{00}&+(p\Delta ^{1+0}z_{00}+q\Delta ^{0+1}z_{00})\\[1ex]&+{\frac {1}{2!}}\left[p(p-1)\Delta ^{2+0}z_{00}+2pq\Delta ^{1+1}z_{00}+q(q-1)\Delta ^{0+2}z_{00}\right]\\[1ex]&\ldots \end{aligned}}$