Delt forskel

Den opdelte forskel er en generalisering af begrebet en afledt for et diskret sæt af punkter.

Definition

Lad en funktion defineres på et (forbundet) sæt og parvis adskilte punkter fastgøres $f$ $x,$ $x_{0},\;\ldots ,\;x_{n}\i X.$

Derefter kaldes værdien den dividerede forskel af funktionens nulorden i punktet , og den dividerede ordensforskel for punktsystemet bestemmes gennem de dividerede ordensforskelle i henhold til formlen $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}}},

i særdeleshed,

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}}}.

Egenskaber

For den opdelte forskel er formlen sand

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

i særdeleshed,

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 opdelte forskel er en symmetrisk funktion af dens argumenter, det vil sige, at enhver permutation af dem ikke ændrer dens værdi, især,

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 et fast system af punkter er den opdelte forskel en lineær funktionel , det vil sige for funktioner og og skalarer og : $(x_{0},\;\ldots ,\;x_{n})$ $f$ $g$ $-en$ $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}).

Ansøgning

Ved hjælp af opdelte forskelle kan funktionerne for noder skrives som Newtons "fremadgående" interpolationspolynomium : $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 \venstre(f(x_{0};\;x_{1})+(x-x_{1})\cdot \venstre(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å er Newtons interpolationspolynomium "baglæns":

{\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}}

Fordele:

til beregning af opdelte forskelle kræves handlinger (divisioner), hvilket er mindre end i andre algoritmer; $(n+2)(n+1)/2=O(n^{2})$
du kan beregne værdierne af interpolationspolynomiet i henhold til Horner-skemaet for handlinger (multiplikationer); $På)$
lagring er påkrævet af noden og forskellen, og forskellene kan gemmes (modtages) i de samme celler, hvor værdierne blev sat ; $(n+1)$ $(n+1)$ $f(x_{k})$
sammenlignet med Lagrange-interpolationspolynomiet er tilføjelsen af en ny node forenklet.

Ved brug af

\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ørste af formlerne kan skrives som

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

Ved at bruge Newtons polynomium kan man også opnå følgende repræsentation af opdelte forskelle som et forhold mellem 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 |}}.

Historie

Newton brugte opdelte forskelle i sin generelle interpolationsformel (se ovenfor), men udtrykket ser ud til at være blevet introduceret af O. de Morgan i 1848 [1] .

Eksempel

Billedet nedenfor viser et eksempel på beregning af de opdelte forskelle for

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

Se også

Litteratur

Bakhvalov N. S. , Zhidkov N. P. , Kobelkov G. M. Numeriske metoder. - 3. udg., tilføje. og omarbejdet. — M. : BINOM. Videnlaboratoriet, 2004. - 636 s., ill. — ISBN 5-94774-175-X .
Korn G. (Granino A. Korn, Ph.D.), Korn T. (Theresa M. Korn, MS) Matematisk håndbog for videnskabsmænd og ingeniører ( Eng. Mathematical handbook for scientist and engineers, 1968 ). - M . : Nauka, 1973. - 832 s., ill.

Noter

↑ Begrænsede forskelle. Arkiveret 12. august 2010 på Wayback Machine i Encyclopedia Around the World