Delad skillnad

Den uppdelade skillnaden är en generalisering av begreppet en derivata för en diskret uppsättning punkter.

Definition

Låt en funktion definieras på en (ansluten) uppsättning och parvis distinkta punkter fixeras $f$ $x,$ $x_{0},\;\ldots ,\;x_{n}\in X.$

Då kallas värdet den dividerade skillnaden av funktionen nollordning i punkten , och den delade ordningsskillnaden för poängsystemet bestäms genom de delade ordningsskillnaderna enligt formeln $f$ $x_{j}$ $f(x_{j}),$ $k$ $(x_{j},\;x_{j+1},\;\ldots ,\;x_{j+k})$ $(k-1)$

f(x_{j};\;x_{j+1};\;\ldots ;\;x_{j+k-1};\;x_{j+k})={\frac {f (x_{j+1};\;\ldots ;\;x_{j+k-1};\;x_{j+k})-f(x_{j};\;x_{j+1}; \;\ldots ;\;x_{j+k-1})}{x_{j+k}-x_{j}}},

särskilt,

f(x_{0};\;x_{1})={\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0))} ,

f(x_{0};\;x_{1};\;x_{2})={\frac {f(x_{1};\;x_{2})-f(x_{0} ;\;x_{1})}{x_{2}-x_{0}}}={\dfrac {{\dfrac {f(x_{2})-f(x_{1})}{x_{2 }-x_{1))}-{\dfrac {f(x_{1})-f(x_{0})}{x_{1}-x_{0)))){x_{2}-x_{ 0}}},

f(x_{0};\;x_{1};\;\ldots ;\;x_{n-1};\;x_{n})={\frac {f(x_{1}; \;\ldots ;\;x_{n-1};\;x_{n})-f(x_{0};\;x_{1};\;\ldots ;\;x_{n-1}) }{x_{n}-x_{0}}}.

Egenskaper

För den delade skillnaden är formeln sann

f(x_{0};\;x_{1};\;\ldots ;\;x_{n})=\summa _{j=0}^{n}{\dfrac {f(x_{ j})}{\prod \limits _{i=0 \atop i\neq j}^{n}(x_{j}-x_{i))}}),

särskilt,

f(x_{0};\;x_{1})={\frac {f(x_{1})}{x_{1}-x_{0))}+{\frac {f(x_ {0})}{x_{0}-x_{1}}},

f(x_{0};\;x_{1};\;x_{2})={\frac {f(x_{2})}{(x_{2}-x_{1})( x_{2}-x_{0})}}+{\frac {f(x_{1})}{(x_{1}-x_{2})(x_{1}-x_{0})}} +{\frac {f(x_{0})}{(x_{0}-x_{2})(x_{0}-x_{1})}}.

Den uppdelade skillnaden är en symmetrisk funktion av dess argument, det vill säga att varje permutation av dem inte ändrar dess värde, i synnerhet,

f(x_{0};\;x_{1})=f(x_{1};\;x_{0}),

f(x_{0};\;x_{1};\;x_{2})=f(x_{1};\;x_{0};\;x_{2})=f(x_ {2};\;x_{1};\;x_{0}),

f(x_{0};\;x_{1};\;\ldots ;\;x_{n-1};\;x_{n})=f(x_{n};\;x_{ n-1};\;\ldots ;\;x_{1};\;x_{0}).

Med ett fast system av punkter är den delade skillnaden en linjär funktionell , det vill säga för funktioner och och skalärer och : $(x_{0},\;\ldots ,\;x_{n})$ $f$ $g$ $a$ $b$

(a\cdot f+b\cdot g)(x_{0};\;\ldots ;\;x_{n})=a\cdot f(x_{0};\;\ldots ;\; x_{n})+b\cdot g(x_{0};\;\ldots ;\;x_{n}).

Applikation

Med hjälp av uppdelade skillnader kan funktionerna för noder skrivas som Newtons "framåt" interpolationspolynom : $f$ $(x_{0},\;\ldots ,\;x_{n})$

{\begin{array}{rcl}L_{n}(x)&=&f(x_{0})+f(x_{0};\;x_{1})\cdot (x-x_{ 0})+f(x_{0};\;x_{1};\;x_{2})\cdot (x-x_{0})\cdot (x-x_{1})+\ldots +f (x_{0};\;\ldots ;\;x_{n})\cdot \prod _{k=0}^{n-1}(x-x_{k})=\\&=&f(x_ {0})+(x-x_{0})\cdot \left(f(x_{0};\;x_{1})+(x-x_{1})\cdot \left(f(x_{ 0};\;x_{1};\;x_{2})+\ldots +(x-x_{n-1})\cdot f(x_{0};\;\ldots ;\;x_{n })\ldots\right)\right),\end{array}}

så är Newtons interpolationspolynom "bakåt":

{\begin{array}{rcl}L_{n}(x)&=&f(x_{n})+f(x_{n};\;x_{n-1})\cdot (x- x_{n})+f(x_{n};\;x_{n-1};\;x_{n-2})\cdot (x-x_{n})\cdot (x-x_{n- 1})+\ldots +f(x_{n};\;\ldots ;\;x_{0})\cdot \prod _{k=1}^{n}(x-x_{k})=\ \&=&f(x_{n})+(x-x_{n})\cdot \left(f(x_{n};\;x_{n-1})+(x-x_{n-1} )\cdot \left(f(x_{n};\;x_{n-1};\;x_{n-2})+\ldots +(x-x_{1})\cdot f(x_{n };\;\ldots ;\;x_{0})\ldots \right)\right).\end{array}}

Fördelar:

för att beräkna delade skillnader krävs åtgärder (divisioner), vilket är mindre än i andra algoritmer; $(n+2)(n+1)/2=O(n^{2})$
du kan beräkna värdena för interpolationspolynomet enligt Horner-schemat för åtgärder (multiplikationer); $På)$
lagring krävs av noden och skillnaden, och skillnaderna kan lagras (ta emot) i samma celler där värdena sattes ; $(n+1)$ $(n+1)$ $f(x_{k})$
jämfört med Lagrange-interpolationspolynomet förenklas tillägget av en ny nod.

Använder sig av

\left\{{\begin{array}{rcl}\omega _{j}(x)&=&(x-x_{0})\cdot \ldots \cdot (x-x_{j-1 })=\prod \limits _{k=0}^{j-1}(x-x_{k})=\omega _{j-1}(x)\cdot (x-x_{j-1} ),\;j>0,\\\omega _{0}(x)&=&1\end{array}}\right.

Den första av formlerna kan skrivas som

L_{n}(x)=\sum _{j=0}^{n}f(x_{0};\;\ldots ;\;x_{j})\cdot \omega _{j} (x).

Med hjälp av Newtons polynom kan man också få följande representation av delade skillnader som ett förhållande mellan determinanter :

f(x_{0};\ldots ;x_{n})={\frac {\left|{\begin{array}{ccccc}1&x_{0}&\ldots &x_{0}^{n- 1}&f(x_{0})\\\vdots &\vdots &\ddots &\vdots &\vdots \\1&x_{n}&\ldots &x_{n}^{n-1}&f(x_{n} )\end{array}}\right|}{\left|{\begin{array}{ccccc}1&x_{0}&\ldots &x_{0}^{n-1}&x_{0}^{n}\ \\vdots &\vdots &\ddots &\vdots &\vdots \\1&x_{n}&\ldots &x_{n}^{n-1}&x_{n}^{n}\end{array}}\right |}}.

Historik

Newton använde delade skillnader i sin allmänna interpolationsformel (se ovan), men termen verkar ha introducerats av O. de Morgan 1848 [1] .

Exempel

Bilden nedan visar ett exempel på beräkning av de delade skillnaderna för

{\begin{array}{rcl}f(x)&=&2x^{3}-2x^{2}+3x-1,\\x_{i}&=&i,\;i=0, \ldots ,n,\\n&=&5.\end{array}}

Se även

Länkar

Hermitinterpolation med hjälp av uppdelade skillnader.

Litteratur

Bakhvalov N. S. , Zhidkov N. P. , Kobelkov G. M. Numeriska metoder. - 3:e uppl., tillägg. och omarbetat. — M. : BINOM. Kunskapslaboratoriet, 2004. - 636 s., ill. — ISBN 5-94774-175-X .
Korn G. (Granino A. Korn, Ph.D.), Korn T. (Theresa M. Korn, MS) Matematisk handbok för vetenskapsmän och ingenjörer ( Eng. Mathematical handbook for scientist and engineers, 1968 ). - M . : Nauka, 1973. - 832 s., ill.

Anteckningar

↑ Finita skillnader. Arkiverad 12 augusti 2010 på Wayback Machine i Encyclopedia Around the World