Interpolacyjne metody różnicowe

Różnice skończone

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

gdzie:

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

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

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

Tak na przykład

$\begin{array}{cc}{\mathrm{\Delta }}^{2}y& =\mathrm{\Delta }(\mathrm{\Delta }y)\\ & =\mathrm{\Delta }[f(x+\mathrm{\Delta }x)-f(x)]\\ & =[f(x+2\mathrm{\Delta }x)-f(x+\mathrm{\Delta }x)]-[f(x+\mathrm{\Delta }x)-f(x)]\\ & =f(x+2\mathrm{\Delta }x)-2f(x+\mathrm{\Delta }x)+f(x).\end{array}$

• Przykład

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

$\begin{array}{cc}\mathrm{\Delta }P(x)& =(x+1{)}^3-x^3=3x^2+3x+1,\\ {\mathrm{\Delta }}^{2}P(x)& =[3(x+1{)}^2+3(x+1)+1]-(3x^2+3x+1)=6x+6,\\ {\mathrm{\Delta }}^{3}P(x)& =[6(x+1)+6]-(6x+6)=6,\\ {\mathrm{\Delta }}^{n}P(x)& =0\mathrm{d}\mathrm{l}\mathrm{a}n>3.\end{array}$

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}+\dots a_n,$

to

${\mathrm{\Delta }}^n{P}_n(x)=n!a_0{h}^n=\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\to {\mathrm{\Delta }}^s{P}_n(x)=0,$ gdy $s>n.$

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

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

Ze wzoru (1) wynika, że

$f(x+\mathrm{\Delta }x)=f(x)+\mathrm{\Delta }f(x).$

Traktując operator $\mathrm{\Delta }$ jako symboliczny mnożnik, możemy napisać Szablon:Wzór Szablon:Wzór

Wykorzystując wzór dwumienny Newtona, otrzymujemy Szablon:Wzór

oraz dzięki temu, że Szablon:Wzór

możemy napisać

$\begin{array}{cc}{\mathrm{\Delta }}^{n}f(x)& =[(1+\mathrm{\Delta })-1{]}^{n}f(x)\\ & =(1+\mathrm{\Delta }{)}^{n}f(x)\\ & -C_n^1(1+\mathrm{\Delta }{)}^{n-1}f(x)\\ & +C_n^2(1+\mathrm{\Delta }{)}^{n-2}f(x)\\ & -\dots \\ & +(-1{)}^{n-1}C{}_n^{n-1}(1+\mathrm{\Delta })f(x)\\ & +(-1{)}^{n}f(x),\end{array}$

a wykorzystując (3) Szablon:Wzór

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

Wynika stąd, że

$f^{(n)}(x+\theta n\mathrm{\Delta }x)=\frac{{\mathrm{\Delta }}^{n}f(x)}{(\mathrm{\Delta }x{)}^n}\to f^{(n)}(x)=\underset{\mathrm{\Delta }x\to 0}{\lim }\frac{{\mathrm{\Delta }}^{n}f(x)}{(\mathrm{\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 Szablon:Wzór

Z drugiej równości otrzymujemy

$y_{i+1}=y_i+\mathrm{\Delta }{y}_i=(1+\mathrm{\Delta })y_i,$

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

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

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

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

Dzięki wzorowi dwumiennemu Newtona otrzymujemy

$\begin{array}{cc}{y}_{i+n}& =y_i\\ & +C_n^1\mathrm{\Delta }{y}_i\\ & +C_n^2{\mathrm{\Delta }}^2{y}_i\\ & \dots \\ & +{\mathrm{\Delta }}^n{y}_i,\end{array}$

$\begin{array}{cc}{\mathrm{\Delta }}^n{y}_i& =[(1+\mathrm{\Delta })-1{]}^n\\ & =(1+\mathrm{\Delta }{)}^n{y}_i\\ & -C_n^1(1+\mathrm{\Delta }{)}^{n-1}{y}_i\\ & +\dots \\ & +C{}_n^{n-1}(1+\mathrm{\Delta })y_i,\end{array}$

$\begin{array}{cc}{\mathrm{\Delta }}^n{y}_i& =y_{n+i}\\ & -C_n^1{y}_{n+i-1}\\ & +C_n^2{y}_{n+i-2}\\ & +\dots \\ & +(-1{)}^{n-1}C{}_n^{n-1}{y}_{i+1}\\ & +(-1{)}^n{y}_i.\end{array}$

Na przykład

${\mathrm{\Delta }}^2{y}_i=y_{i+2}-2y_{i+1}+y_i,$

${\mathrm{\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$	$\mathrm{\Delta }y$	${\mathrm{\Delta }}^{2}y$	${\mathrm{\Delta }}^{3}y$
$x_0$	$y_0$	$\mathrm{\Delta }{y}_0$	${\mathrm{\Delta }}^2{y}_0$	${\mathrm{\Delta }}^3{y}_0$
$x_1$	$y_1$	$\mathrm{\Delta }{y}_1$	${\mathrm{\Delta }}^2{y}_1$	${\mathrm{\Delta }}^3{y}_1$
$x_2$	$y_2$	$\mathrm{\Delta }{y}_2$	${\mathrm{\Delta }}^2{y}_2$	${\mathrm{\Delta }}^3{y}_2$
$\dots$	$\dots$	$\dots$	$\dots$	$\dots$

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$	$\mathrm{\Delta }y$	${\mathrm{\Delta }}^{2}y$	${\mathrm{\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
$\dots$	$\dots$	$\dots$	$\dots$	$\dots$

Potęga uogólniona

W zagadnieniach interpolacji wygodnie jest wprowadzić pojęcie uogólnionej potęgi Szablon:Wzór

gdzie:

$h$ jest ustalonym krokiem.

Ze wzoru (1) wynika, że

$x^{[n]}=x^n,\mathrm{g}\mathrm{d}\mathrm{y}h=0.$

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

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

$\begin{array}{cc}{\mathrm{\Delta }}^k{x}^{[n]}& =n(n-1)\dots [n-(k-1)]h^k{x}^{[n-k]}\\ & =\frac{n!}{(n-k)!}{h}^k{x}^{[n-k]},k=1,2,\dots ,n.\end{array}$

Ponieważ $x^{[n]}$ jest wielomianem n-tego stopnia więc oczywiście ${\mathrm{\Delta }}^k{x}^{[n]}=0,\mathrm{g}\mathrm{d}\mathrm{y}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 Szablon:Wzór

Warunki te są równoważne warunkom

${\mathrm{\Delta }}^m{P}_n(x_0)={\mathrm{\Delta }}^m{y}_0,m=0,1,\dots ,n.$

Zgodnie z koncepcją Newtona wielomianu $P_n(x)$ będziemy poszukiwać w postaci

$\begin{array}{cc}{P}_n(x)=a_0& +a_1(x-x_0)\\ & +a_2(x-x_0)(x-x_1)\\ & \dots \\ & +a_n(x-x_0)(x-x_1)\dots (x-x_{n-1})\end{array}$

lub Szablon:Wzór

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

$\begin{array}{cc}{P}_n(x)=a_0& +a_1(x-x_0{)}^{[1]}\\ & +a_2(x-x_0{)}^{[2]}\\ & \dots \\ & +a_n(x-x_0{)}^{[n]},\\ \\ \mathrm{\Delta }{P}_n(x)=0& +a_1\mathrm{\Delta }(x-x_0{)}^{[1]}\\ & +a_2\mathrm{\Delta }(x-x_0{)}^{[2]}\\ & \dots \\ & +a_n\mathrm{\Delta }(x-x_0{)}^{[n]}\\ [4px]=a_{1}h& +2a_2(x-x_0{)}^{[1]}h\\ & +3a_3(x-x_0{)}^{[2]}h\\ & \dots \\ & +n{a}_n(x-x_0{)}^{[n-1]}h,\\ \\ {\mathrm{\Delta }}^2{P}_n(x)=0& +1\cdot 2h^2{a}_2\\ & +2\cdot 3h^2{a}_3(x-x_0{)}^{[1]}\\ & \dots \\ & +(n-1)n{h}^2(x-x_0{)}^{[n-1]}\\ [4px]=1\cdot 2a_2{h}^2& +2\cdot 3a_3(x-x_0)h^2\\ & \dots \\ & +(n-1)n(x-x_0{)}^{[n-2]}{h}^2,\end{array}$

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

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

Na podstawie (12) i (14) otrzymujemy interpolacyjny wielomian Newtona w postaci Szablon:Wzór 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{array}{cc}(x_k-x_0{)}^{[i]}& =(x_k-x_0)(x_k-x_1)\dots (x_k-x_{i-1})\\ & =k(k-1)(k-2)\dots [k-(i-1)]h^i=\frac{k!}{(k-i)!}{h}^i,\end{array}$

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

Ostatecznie otrzymujemy

$P_n(x_k)=\sum _{i=0}^n\frac{{\mathrm{\Delta }}^i{y}_0}{i!h^i}\frac{k!}{(k-i)!}{h}^i=\sum _{i=0}^{n}C{}_k^i{\mathrm{\Delta }}^i{y}_0=(1+\mathrm{\Delta }{)}^k{y}_0.$

Po wprowadzeniu nowej zmiennej

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

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

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 stablicowaneSzablon:R.

Dla $n=1,2,3$ otrzymujemy

• $P_1(x)=y_0+q\mathrm{\Delta }{y}_0$ – dla interpolacji liniowej,
• $P_2(x)=y_0+q\mathrm{\Delta }{y}_0+\frac{q(q-1)}{2}{\mathrm{\Delta }}^2{y}_0$ – dla interpolacji kwadratowej,
• $P_3(x)=y_0+q\mathrm{\Delta }{y}_0+\frac{q(q-1)}{2!}{\mathrm{\Delta }}^2{y}_0+\frac{q(q-1)(q-2)}{3!}{\mathrm{\Delta }}^3{y}_0$ – dla interpolacji sześciennej.

Druga formuła Newtona

Tym razem poszukuje się wielomianu o postaci

$\begin{array}{cc}{P}_n(x)& =a_0\\ & +a_1(x-x_n)\\ & +a_2(x-x_n)(x-x_{n-1})\\ & \dots \\ & +a_n(x-x_n)(x-x_{n-1})\dots (x-x_1)\\ & =\sum _{i=0}^n{a}_i(x-x_{n-i+1}{)}^{[i]},\end{array}$

gdzie:

$(x-x_k{)}^{[i]}=(x-x_n)(x-x_{n-1})(x-x_{n-2})\dots (x-x_k).$

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

$\begin{array}{cc}\mathrm{\Delta }{P}_n(x)=0& +a_{1}h\\ & +a_{2}2h(x-x_{n-1})\\ & +a_{3}3h(x-x_{n-2}{)}^{[2]}\\ & \dots \\ & +a_{n}nh(x-x_1{)}^{[n-1]},\end{array}$

$\begin{array}{cc}{\mathrm{\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{array}$

$\begin{array}{cc}{\mathrm{\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)n{a}_n{h}^3(x-x_1{)}^{[n-3]},\end{array}$

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

${\mathrm{\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{{\mathrm{\Delta }}^m{P}_n(x_{n-m})}{m!h^m}$

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

$\begin{array}{cc}{P}_n(x)& =\sum _{i=0}^n\frac{{\mathrm{\Delta }}^i{P}_n(x_{n-i})}{i!h^i}(x-x_{n-i+1}{)}^{[i]}\\ & =P_n(x_n)+\frac{{\mathrm{\Delta }}^1{P}_n(x_{n-1})}{1!h}(x-x_n)\\ & +\frac{{\mathrm{\Delta }}^2{P}_n(x_{n-2})}{2!h^2}(x-x_n)(x-x_{n-1})\\ & \dots \\ & +\frac{{\mathrm{\Delta }}^n{P}_n(x_0)}{n!h^n}(x-x_n)(x-x_{n-1})\dots (x-x_1).\end{array}$

Po wprowadzeniu nowej zmiennej

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

powstaje druga formuła Newtona

$\begin{array}{ccc}{P}_n(x)& =P_n(x_n)& +q\mathrm{\Delta }{P}_n(x_{n-1})\\ & & +\frac{q(q+1)}{2!}{\mathrm{\Delta }}^2{P}_n(x_{n-2})\\ & & +\frac{q(q+1)(q+2)}{3!}{\mathrm{\Delta }}^3{P}_n(x_{n-3})\\ & & \dots \\ & & +\frac{q(q+1)\dots [q+(n-1)]}{n!}{\mathrm{\Delta }}^n{P}_n(x_0)\\ & =P_n(x_n)& +\sum _{i=1}^n\frac{q^{[i]}}{i!}{\mathrm{\Delta }}^i{P}_n(x_{n-i}),\end{array}$

gdzie:

$q^{[i]}=q(q+1)(q+2)\dots [q+(i-1)],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,i=0,\pm 1,\pm 2,\dots ,y_i=f(x_i),$

$\mathrm{\Delta }{y}_i=y_{i+1}-y_i,{\mathrm{\Delta }}^2{y}_i=\mathrm{\Delta }{y}_{i+1}-\mathrm{\Delta }{y}_i$ 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:

$\mathrm{\Delta }{x}_i=x_{i+1}-x_i=h=\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t},i=-n,-(n-1),\dots ,n-1.$

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

$y_i=f(x_i),i=0,\pm 1,\dots ,\pm n.$

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

$P_{2n+1}(x_i)=y_i,i=0,\pm 1,\dots ,\pm n.$

Z żądania tego wynika, że Szablon:Wzór

Wielomianu szukamy w postaci

$\begin{array}{cc}{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)\\ & \dots \\ & +a_{2n-1}(x-x_{-(n-1)})\dots (x-x_{-1})(x-x_0)(x-x_1)\dots (x-x_{n-1})\\ & +a_{2n}(x-x_{-(n-1)})\dots (x-x_{-1})(x-x_0)(x-x_1)\dots (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]}\\ & \dots \\ & +a_{2n-1}(x-x_{-(n-1)}{)}^{[2n-1]}\\ & +a_{2n}(x-x_{-(n-1)}{)}^{[2n]}.\end{array}$

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,a_{2m-1}=\frac{{\mathrm{\Delta }}^{2m-1}{y}_{-(m-1)}}{(2m-1)!h^{2m-1}},a_{2m}=\frac{{\mathrm{\Delta }}^{2m}{y}_{-m}}{(2m)!h^{2m}},m=1,2,\dots ,n.$

Wprowadzając nową zmienną

$q=\frac{x-x_0}{h},$

otrzymujemy pierwszą formułę Gaussa w postaci Szablon:Wzór

albo krócej Szablon:Wzór

gdzie:

$q=\frac{x-x_0}{h},q^{[m]}=q(q-1)\dots [q-(m-1)].$

Ta formuła zawiera różnice

$\mathrm{\Delta }{y}_0,{\mathrm{\Delta }}^2{y}_{-1},{\mathrm{\Delta }}^3{y}_{-1},{\mathrm{\Delta }}^4{y}_{-2},{\mathrm{\Delta }}^5{y}_{-2},{\mathrm{\Delta }}^6{y}_{-3},\dots ,{\mathrm{\Delta }}^{2n-1}{y}_{-(n-1)},{\mathrm{\Delta }}^{2n}{y}_{-n}.$

Druga formuła Gaussa

Druga formuła Gaussa ma postać Szablon:Wzór

gdzie:

$q=\frac{x-x_0}{h}.$

Ta formuła zawiera różnice

$\mathrm{\Delta }{y}_{-1},{\mathrm{\Delta }}^2{y}_{-1},{\mathrm{\Delta }}^3{y}_{-2},{\mathrm{\Delta }}^4{y}_{-2},{\mathrm{\Delta }}^5{y}_{-3},{\mathrm{\Delta }}^6{y}_{-3},\dots ,{\mathrm{\Delta }}^{2n-1}{y}_{-n},{\mathrm{\Delta }}^{2n}{y}_{-n}.$

Formuła Stirlinga

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

$\begin{array}{cc}{P}_{2n+1}(x)=y_0& +q\cdot \frac{\mathrm{\Delta }{y}_{-1}+\mathrm{\Delta }{y}_0}{2}\\ & +\frac{q^2}{2}\cdot {\mathrm{\Delta }}^2{y}_{-1}\\ [2px]& +\frac{q(q^2-1^2)}{3!}\cdot \frac{{\mathrm{\Delta }}^3{y}_{-2}+{\mathrm{\Delta }}^3{y}_{-1}}{2}\\ & +\frac{q^2(q^2-1^2)}{4!}\cdot {\mathrm{\Delta }}^4{y}_{-2}\\ & +\frac{q(q^2-1^2)(q^2-2^2)}{5!}\cdot \frac{{\mathrm{\Delta }}^5{y}_{-3}+{\mathrm{\Delta }}^5{y}_{-2}}{2}\\ & +\frac{q^2(q^2-1^2)(q^2-2^2)}{6!}\cdot {\mathrm{\Delta }}^6{y}_{-3}\\ & \dots \\ & +\frac{q(q^2-1^2)(q^2-2^2)(q^2-3^2)\dots [q^2-(n-1{)}^2]}{(2n-1)!}\\ & \cdot \frac{{\mathrm{\Delta }}^{2n-1}{y}_{-n}+{\mathrm{\Delta }}^{2n-1}{y}_{-(n-1)}}{2}\\ & +\frac{q^2(q^2-1^2)(q^2-2^2)\dots [q^2-(n-1{)}^2]}{(2n)!}{\mathrm{\Delta }}^{2n}{y}_{-n},\end{array}$

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ę Szablon:Wzór

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

$\begin{array}{cc}{P}_{2n+1}(x)& =\frac{y_0+y_1}{2}\\ & +(q-\frac{1}{2})\cdot \mathrm{\Delta }{y}_0\\ & +\frac{q(q-1)}{2!}\cdot \frac{{\mathrm{\Delta }}^2{y}_{-1}+{\mathrm{\Delta }}^2{y}_0}{2}\\ & +\frac{(q-\frac{1}{2})q(q-1)}{3!}\cdot {\mathrm{\Delta }}^3{y}_{-1}\\ & +\frac{q(q-1)(q+1)(q-2)}{4!}\cdot \frac{{\mathrm{\Delta }}^4{y}_{-2}+{\mathrm{\Delta }}^4{y}_{-1}}{2}\\ & +\frac{(q-\frac{1}{2})q(q-1)(q+1)(q-2)}{5!}\cdot {\mathrm{\Delta }}^5{y}_{-2}\\ & +\frac{q(q-1)(q+1)(q-2)(q+2)(q-3)}{6!}\cdot \frac{{\mathrm{\Delta }}^6{y}_{-3}+{\mathrm{\Delta }}^6{y}_{-2}}{2}\\ & \dots \\ & +\frac{q(q-1)(q+1)(q-2)(q+2)\dots (q-n)(q+n-1)}{2n!}\cdot \frac{{\mathrm{\Delta }}^{2n}{y}_{-n}+{\mathrm{\Delta }}^{2n}{y}_{-n+1}}{2}\\ & +\frac{(q-\frac{1}{2})q(q-1)(q+1)(q-2)(q+2)\dots (q-n)(q+n-1)}{(2n+1)!}\cdot {\mathrm{\Delta }}^{2n+1}{y}_{-n}.\end{array}$

Formuła Lagrange’a

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

$x_{i+1}=x_i+h,dlai=0,1,\dots ,h=\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}.$

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.i=0,1,\dots ,n.$

Budujemy wielomian

${\phi }_i(x)=a_i(x-x_0)(x-x_1)\dots (x-x_{i-1})(x-x_{i+1})\dots (x-x_n)$

taki, że ${\phi }_i(x_j)={\delta }_{ij}\{\begin{array}{c}1\text{gdy}j=i,\\ 0\text{gdy}j\ne i.\end{array}$

Stąd

$\begin{array}{cc}& {\phi }_i(x_i)=a_i(x_i-x_0)(x_i-x_1)\dots (x_i-x_{i-1})(x_i-x_{i+1})\dots (x_i-x_n)=1,\\ & a_i=\frac{1}{(x_i-x_0)(x_i-x_1)\dots (x_i-x_{i-1})(x_i-x_{i+1})\dots (x_i-x_n)},\\ \\ \end{array}$

i formuła Lagrange’a ma postać

$P_n(x)=\sum _{i=0}^n{\phi }_i(x)y_i.$

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

$w(x)=(x-x_0)(x-x_1)\dots (x-x_n)$

i jego pochodną

$\begin{array}{cc}{w}^{\text{'}}(x)& =\sum _{i=0}^n(x-x_0)(x-x_1)\dots (x-x_{i-1})(x-x_{i+1})\dots (x-x_n)\\ & =\sum _{i=0}^n\frac{w(x)}{x-x_i},\end{array}$

$w^{\text{'}}(x_i)=(x_i-x_0)(x_i-x_1)\dots (x_i-x_{i-1})(x_i-x_{i+1})\dots (x-x_n).$

Stąd na podstawie wzoru (e) dla $i=0,1,\dots ,n$ Szablon:Wzór

gdzie:

$\begin{array}{cc}{D}_i(x)& =(x-x_i)w^{\text{'}}(x_i)\\ & =(x_i-x_0)(x_i-x_2)\\ & \dots (x_i-x_{i-1})(x-x_i)(x_i-x_{i+1})\\ & \dots (x_i-x_n).\end{array}$

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

$\left[\begin{array}{ccccc}x-x_0& x_0-x_1& x_0-x_2& \dots & x_0-x_n\\ x_1-x_0& x-x_1& x_1-x_2& \dots & x_1-x_n\\ x_2-x_0& x_2-x_1& x-x_2& \dots & x_2-x_n\\ \dots & \dots & \dots & \dots & \dots \\ x_n-x_0& x_n-x_1& x_n-x_2& \dots & x-x_n\end{array}\right].$

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

$\begin{array}{cc}w(x)& =(x-x_0)(x-x_1),\\ w^{\text{'}}(x)& =(x-x_1)+(x-x_0),\\ w^{\text{'}}(x_0)& =x_0-x_1,\\ w^{\text{'}}(x_1)& =x_1-x_0,\\ {\phi }_0(x)& =\frac{x-x_1}{x_0-x_1},\\ {\phi }_1(x)& =\frac{x-x_0}{x_1-x_0},\\ P_n(x)& ={\phi }_0(x)y_0+{\phi }_1(x)y_1.\end{array}$

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

$\begin{array}{cc}w(x)& =(x-x_0)(x-x_1)(x-x_2),\\ w^{\text{'}}(x)& =(x-x_1)(x-x_2)+(x-x_0)(x-x_2)+(x-x_0)(x-x_1),\\ w^{\text{'}}(x_0)& =(x_0-x_1)(x_0-x_2),\\ w^{\text{'}}(x_1)& =(x_1-x_0)(x_1-x_2),\\ w^{\text{'}}(x_2)& =(x_2-x_0)(x_2-x_1),\\ {\phi }_0(x)& =\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)},\\ {\phi }_1(x)& =\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)},\\ {\phi }_2(x)& =\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)},\\ P_n(x)& ={\phi }_0(x)y_0+{\phi }_1(x)y_1+{\phi }_2(x)y_2.\end{array}$

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

$x_{i+1}=x_i+h,h=\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t},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)\dots (q-n)h^{n+1},$

$D_m(x)=(x-x_m)w^{\text{'}}(x_m)=(q-m)(-1{)}^{n-m}m!(n-m)!h^{n+1},$

${\phi }_m(x)=\frac{w(x)}{D_m(x)}.$

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

$\left[\begin{array}{cccccc}q& -1& -2& -3& \dots & -n\\ 1& q-1& -1& -2& \dots & -(n-1)\\ 2& 1& q-2& -1& \dots & -(n-2)\\ \dots & \dots & \dots & \dots & \dots & \dots & \\ n& n-1& n-2& n-3& \dots & q-n\end{array}\right].$

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

$x_{i+1}=x_i+h,h=\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t},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},i=0,1,\dots ,$

przy czym

$\mathrm{\Delta }{x}_i=x_{i+1}-x_i\ne 0,i=0,1,\dots$

Na przykład

$[x_0,x_1]=\frac{y_1-y_0}{x_1-x_0},[x_1,x_2]=\frac{y_2-y_1}{x_2-x_1},\dots$

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},\dots$

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},$

$i=0,1,2,\dots ,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,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

LematSzablon:R: 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{array}{cc}[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{array}$

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

$[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.$ 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łychSzablon:R

$\begin{array}{cc}{P}_n(x)=P_n(x_0)& +P_{n-1}(x)(x-x_0)\\ =P_n(x_0)& +P_{n-1}(x_1)(x-x_0)\\ & +P_{n-2}(x_2)(x-x_0)(x-x_1)\\ & \dots \\ & +P_{n-m}(x_m)(x-x_0)(x-x_1)\dots (x-x_{m-1})\\ & \dots \\ & +P_0(x_n)(x-x_0)(x-x_1)\dots (x-x_{n-1})\\ & +0\cdot (x-x_0)(x-x_1)\dots (x-x_n),\end{array}$

gdzie:

$P_{n-m}(x)=[x,x_0,x_1,\dots ,x_{m-1}],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 tymSzablon:R, 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{\mathrm{\Delta }{y}_0}{1!}q+\frac{{\mathrm{\Delta }}^2{y}_0}{2!}q(q-1)+\dots +\frac{{\mathrm{\Delta }}^n{y}_0}{n!}q(q-1)\dots (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=\phi (q),$

w którym

$\begin{array}{cc}\phi (q)& =\frac{y-y_0}{\mathrm{\Delta }{y}_0}\\ & -\frac{{\mathrm{\Delta }}^2{y}_0}{2!\mathrm{\Delta }{y}_0}q(q-1)\\ & \dots \\ & -\frac{{\mathrm{\Delta }}^n{y}_0}{n!\mathrm{\Delta }{y}_0}q(q-1)\dots (q-n+1).\end{array}$

Jako pierwsze przybliżenie przyjmuje się wartość

$q_0=\frac{y-y_0}{\mathrm{\Delta }{y}_0},$

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

$q_m=\phi (q_{m-1}),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 postaciSzablon:R

$\begin{array}{cc}x=x_0& +[y_0,y_1](y-y_0)\\ & +[y_0,y_1,y_2](y-y_0)(y-y_1)\\ & \dots \\ & +[y_0,y_1,\dots y_n](y-y_0)(y-y_1)\dots (y-y_{n-1}).\end{array}$

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{{\mathrm{\Delta }}^{i}D(0)}{i!}\lambda (\lambda -1),\dots ,(\lambda -i+1),$

gdzie:

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

Po uwzględnieniu tożsamościSzablon:R

$\frac{\lambda (\lambda -1)\dots (\lambda -i+1)}{i!}=\sum _{m=1}^i{c}_{mi}{\lambda }^m$

otrzymujemy wzór MarkowaSzablon:R

$D(\lambda )=D(0)+\sum _{m=1}^n{\lambda }^m\sum _{i=m}^n{c}_{mi}{\mathrm{\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{\mathrm{\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

${\mathrm{\Delta }}_x{z}_{ij}=z_{i+1,j}-z_{ij},{\mathrm{\Delta }}_y{z}_{ij}=z_{i,j+1}-z_{ij}$

i wyższych rzędów

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

przy czym ${\mathrm{\Delta }}^{0+0}{z}_{ij}=0.$

Na przykład

$\begin{array}{cc}{\mathrm{\Delta }}^{1+2}{z}_{ij}& ={\mathrm{\Delta }}_x({\mathrm{\Delta }}_{yy}^2{z}_{ij})\\ & ={\mathrm{\Delta }}_x(z_{i,j+2}-2z_{i,j+1}+z_{ij})\\ & =(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{array}$

Dwoista formuła Newtona

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

${\mathrm{\Delta }}_{x^m{y}^n}^{m+n}P(x_0,y_0)={\mathrm{\Delta }}^{m+n}f(x_0,y_0)={\mathrm{\Delta }}^{m+n}{z}_{00},m,n=0,1,2,\dots$

Wielomian ten ma następującą postać

$\begin{array}{cc}P(x,y)=c_{00}& +c_{10}(x-x_0)\\ & +c_{01}(y-y_0)\\ & +c_{20}(x-x_0)(x-x_1)\\ & +c_{11}(x-x_0)(y-y_0)\\ & +c_{02}(y-y_0)(y-y_1)\\ & \dots \end{array}$

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

${\mathrm{\Delta }}_{x}P(x,y)=c_{10}h+2c_{20}h(x-x_0)+c_{11}h(y-y_0)+\dots ,$

${\mathrm{\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$

${\mathrm{\Delta }}_{x}P(x_0,y_0)={\mathrm{\Delta }}^{1+0}{z}_{00}=c_{10}h,$

${\mathrm{\Delta }}_{y}P(x_0,y_0)={\mathrm{\Delta }}^{0+1}{z}_{00}=c_{01}k.$

Stąd otrzymujemy

$c_{10}=\frac{{\mathrm{\Delta }}^{1+0}{z}_{00}}{h},c_{01}=\frac{{\mathrm{\Delta }}^{0+1}{z}_{00}}{k}.$

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

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

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

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

wynika, po podstawieniu $x=x_0,y=y_0,$ że

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

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

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

a stąd

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

Ostatecznie wielomian interpolacyjny przybiera postać

$\begin{array}{cc}P(x,y)=z_{00}& +[\frac{{\mathrm{\Delta }}^{1+0}{z}_{00}}{h}(x-x_0)+\frac{{\mathrm{\Delta }}^{0+1}{z}_{00}}{k}(y-y_0)]\\ & +\frac{1}{2!}[\frac{{\mathrm{\Delta }}^{2+0}{z}_{00}}{h^2}(x-x_0{)}^2+2\frac{{\mathrm{\Delta }}^{1+1}{z}_{00}}{hk}(x-x_0)(y-y_0)+\frac{{\mathrm{\Delta }}^{0+2}{z}_{00}}{k^2}(y-y_0{)}^2]\\ & \dots \end{array}$

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{array}{cc}P(p,q)=z_{00}& +(p{\mathrm{\Delta }}^{1+0}{z}_{00}+q{\mathrm{\Delta }}^{0+1}{z}_{00})\\ & +\frac{1}{2!}[p(p-1){\mathrm{\Delta }}^{2+0}{z}_{00}+2pq{\mathrm{\Delta }}^{1+1}{z}_{00}+q(q-1){\mathrm{\Delta }}^{0+2}{z}_{00}]\\ & \dots \end{array}$