Newtonsk interpolation
I numerisk analyse er newtonsk interpolation , opkaldt efter Isaac Newton , en polynomisk interpolationsmetode, der gør det muligt at opnå Lagrange-polynomet som en lineær kombination af polynomer fra det " newtonske grundlag ".
I modsætning til for eksempel Hermite-interpolering adskiller denne metode sig kun fra Lagrangian-interpolation på den måde, som polynomet beregnes, det resulterende interpolationspolynom er det samme. Af denne grund taler vi også snarere om Newtons form for Lagrange-polynomet.
Definition
Angivne point
k+1{\ displaystyle k + 1}
(x0,y0),...,(xk,yk){\ displaystyle (x_ {0}, y_ {0}), \ ldots, (x_ {k}, y_ {k})}( x j alle adskiller sig 2 til 2), den polynomiske interpolation på en Newton-basis er en lineær kombination af polynomer, der hører til dette grundlag
IKKE(x)=∑j=0kpåjikkej(x){\ displaystyle N (x) = \ sum _ {j = 0} ^ {k} a_ {j} n_ {j} (x)}
med Newtons polynomer defineret som følger
ikkej(x)=∏0≤jeg<j(x-xjeg)j=0,...,k{\ displaystyle n_ {j} (x) = \ prod _ {0 \ leq i <j} (x-x_ {i}) \ qquad j = 0, \ ldots, k}(især det tomme produkt )
ikke0=1{\ displaystyle n_ {0} = 1}
og koefficienterne svarer til de opdelte forskelle :
påj=[y0,...,yj].{\ displaystyle a_ {j} = [y_ {0}, \ ldots, y_ {j}].}Sammenfattende:
Newtons interpolationspolynom forbundet med punkter er defineret af:
IKKE(x){\ displaystyle N (x)}k+1{\ displaystyle k + 1}(x0,y0),...,(xk,yk){\ displaystyle (x_ {0}, y_ {0}), \ ldots, (x_ {k}, y_ {k})}
IKKE(x)=[y0]+[y0,y1](x-x0)+...+[y0,...,yk](x-x0)...(x-xk-1).{\ displaystyle N (x) = [y_ {0}] + [y_ {0}, y_ {1}] (x-x_ {0}) + \ ldots + [y_ {0}, \ ldots, y_ {k }] (x-x_ {0}) \ ldots (x-x_ {k-1}).}
Newtons interpolationssætning
Følgende sætning retfærdiggør navnet på "interpolationspolynom" for :
IKKE{\ displaystyle N}
Dette polynom er lig med Lagrange-interpolationspolynomet forbundet med punkterne, dvs. det unikke polynom med en grad, der er mindre end eller lig med at tilfredsstille:IKKE{\ displaystyle N}k+1{\ displaystyle k + 1}L{\ displaystyle L}k{\ displaystyle k}∀jeg∈{0,...,k}L(xjeg)=yjeg.{\ displaystyle \ forall i \ in \ {0, \ dots, k \} \ quad L (x_ {i}) = y_ {i}.}
Demonstration
Lad os første udstilling, ved induktion på , at koefficienten for graden af lig . For punkt er denne ligestilling øjeblikkelig. Antag, at det er sandt for point, og betegne interpolationspolynomet forbundet med de første punkter (med indekser til ) og det, der er knyttet til det sidste (med indekser til ). Så,
k{\ displaystyle k}k{\ displaystyle k}L{\ displaystyle L}[y0,...,yk]{\ displaystyle [y_ {0}, \ prikker, y_ {k}]}1{\ displaystyle 1}k{\ displaystyle k}P{\ displaystyle P}k{\ displaystyle k}0{\ displaystyle 0}k-1{\ displaystyle k-1}Q{\ displaystyle Q}k{\ displaystyle k}1{\ displaystyle 1}k{\ displaystyle k}
L(x)=(x-x0)Q(x)-(x-xk)P(x)xk-x0{\ displaystyle L (x) = {\ frac {(x-x_ {0}) Q (x) - (x-x_ {k}) P (x)} {x_ {k} -x_ {0}}} }derfor (ved induktion hypotese) koefficienten for graden af faktisk lig .
k{\ displaystyle k}L{\ displaystyle L}[y1,...,yk]-[y0,...,yk-1]xk-x0=[y0,...,yk]{\ displaystyle {\ frac {[y_ {1}, \ prikker, y_ {k}] - [y_ {0}, \ prikker, y_ {k-1}]} {x_ {k} -x_ {0}} } = [y_ {0}, \ prikker, y_ {k}]}
Med de samme notationer, lad os nu, igen ved induktion på , vise det . For punkt er denne ligestilling øjeblikkelig. Antag, at det er sandt for point. er af grad mindre end eller lig med og nul i, og dens gradskoefficient er lig med den af derfor ifølge ovenstående til . Derfor er lig med , det vil sige (ved induktionshypotese) til .
k{\ displaystyle k}L=IKKE{\ displaystyle L = N}1{\ displaystyle 1}k{\ displaystyle k}L-P{\ displaystyle LP}k{\ displaystyle k}x0,...,xk-1{\ displaystyle x_ {0}, \ prikker, x_ {k-1}}k{\ displaystyle k}L{\ displaystyle L}[y0,...,yk]{\ displaystyle [y_ {0}, \ prikker, y_ {k}]}L(x){\ displaystyle L (x)}P(x)+[y0,...,yk](x-x0)...(x-xk-1){\ displaystyle P (x) + [y_ {0}, \ ldots, y_ {k}] (x-x_ {0}) \ ldots (x-x_ {k-1})}IKKE(x){\ displaystyle N (x)}
Bemærk
Lagrange-interpolationspolynomet hører til vektorrummet for polynomier med en grad mindre end eller lig med , hvoraf den ovenfor definerede "Newton-base" er en base. Ifølge Newtons interpolation sætning, koordinaterne for i er , hvor den er de opdelte forskelle. En naiv metode til direkte beregning af koordinaterne for in ville være at løse systemet med lineære ligningerL{\ displaystyle L}k{\ displaystyle k}ikke: =(ikke0,...,ikkek){\ displaystyle n: = (n_ {0}, \ prikker, n_ {k})}L{\ displaystyle L}ikke{\ displaystyle n}(på0,...,påk){\ displaystyle (a_ {0}, \ prikker, a_ {k})}påjeg{\ displaystyle a_ {i}}L{\ displaystyle L}ikke{\ displaystyle n}
∑j=0jegpåjikkej(xjeg)=yjegjeg=0,...,k{\ displaystyle \ sum _ {j = 0} ^ {i} a_ {j} n_ {j} (x_ {i}) = y_ {i} \ qquad i = 0, \ dots, k},
som omskriver sig selv
(101x1-x01x2-x0(x2-x0)(x2-x1)⋮⋮⋱1xk-x0......∏j=0k-1(xk-xj))(på0⋮påk)=(y0⋮yk).{\ displaystyle {\ begin {pmatrix} 1 &&&& 0 \\ 1 & x_ {1} -x_ {0} &&& \\ 1 & x_ {2} -x_ {0} & (x_ {2} -x_ {0} ) (x_ {2} -x_ {1}) && \\\ vdots & \ vdots && \ ddots & \\ 1 & x_ {k} -x_ {0} & \ ldots & \ ldots & \ prod _ {j = 0} ^ {k-1} (x_ {k} -x_ {j}) \ end {pmatrix}} {\ begin {pmatrix} a_ {0} \\\ vdots \\ a_ {k} \ end {pmatrix} } = {\ begin {pmatrix} y_ {0} \\\ vdots \\ y_ {k} \ end {pmatrix}}.}Da dette system er forskudt og endda lavere trekantet , kunne vi løse det trin for trin, begyndende med den linje, der ville give os dengang for , beregningen af ville give os mulighed for at udlede , og så videre indtil .
jeg=0{\ displaystyle i = 0}på0{\ displaystyle a_ {0}}jeg=1{\ displaystyle i = 1}på0{\ displaystyle a_ {0}}på1{\ displaystyle a_ {1}}jeg=k{\ displaystyle i = k}
Ansøgninger
Som definitionen af delte forskelle viser , kan der tilføjes yderligere punkter for at skabe et nyt interpolationspolynom uden at genberegne koefficienterne. Desuden er det nytteløst at genberegne alle koefficienter, hvis et punkt ændres. En anden fordel er, at hvis x jeg er jævnt fordelt, beregningen af de opdelte forskelle bliver meget hurtigere. Derfor foretrækkes Newtons form til interpolationspolynomet frem for Lagrange eller endog over den naive metode ovenfor af praktiske årsager.
Newtons interpolationssætning giver os mulighed for at demonstrere, at enhver polynomfunktion er lig med sin Newton-serie .
Se også
Eksternt link
Newton-type polynomie (sic) interpolation og delte forskelle på math-linux.com
Forfatterkredit
(fr) Denne artikel er helt eller delvist taget fra Wikipedia-artiklen på
engelsk med titlen
" Newton polynomial " ( se listen over forfattere ) .
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">