Polynomial interpolation

I matematik , i numerisk analyse , er polynomial interpolation en teknik til at interpolere et datasæt eller en funktion ved et polynom . Med andre ord, givet et sæt punkter (opnået f.eks. Som et resultat af et eksperiment), er vi på udkig efter et polynom, der passerer gennem alle disse punkter og muligvis opfylder andre betingelser, hvis det er muligt det laveste.

Imidlertid er resultatet ikke altid op til forventningerne: i tilfælde af Lagrangian-interpolation er f.eks. Valget af interpolationspunkter kritisk. Interpolationen ved regelmæssigt fordelte punkter kan meget vel afvige, selv for meget regelmæssige funktioner ( Runge-fænomen ).

Definition

I den enkleste version (Lagrangian interpolation) pålægger vi simpelthen, at polynomet passerer gennem alle de givne punkter. Givet et sæt $n + 1$ point (dvs. par af reelle tal ) $( x i , y i )$ ( $x i$ adskiller sig 2 til 2), forsøger vi at finde et polynomium $p$ (med reelle koefficienter) af grad $n$ som mest kontrolleret :

{\ displaystyle p (x_ {i}) = y_ {i} {\ mbox {,}} i = 0, \ ldots, n}

Isolvance-sætningen specificerer, at der kun er et polynom $p$ med en grad, der er mindre end eller lig med $n,$ defineret af et sæt $n + 1$ point.

Den Hermite interpolation er at finde et polynomium, der ikke kun tager værdierne til de data abscisse, men også den afledede, så hældningen af kurven tager en værdi pålagt ved hvert af disse punkter. Selvfølgelig kræver dette et polynomium, der er større end Lagrange-polynomet. Vi kan også stadig pålægge værdien af det andet, tredje osv. Derivater. på hvert punkt. Fremgangsmåden ved newtonsk interpolering ved hjælp af delte forskelle er især velegnet til konstruktion af disse polynomer.

Opførelse af Lagrange-interpolationspolynomet

Antag at interpolationspolynomet er givet af:

{\ displaystyle p (x) = a_ {n} x ^ {n} + a_ {n-1} x ^ {n-1} + \ cdots + a_ {2} x ^ {2} + a_ {1} x + a_ {0}. \ qquad (1)}

Eller $p$ skal kontrollere:

{\ displaystyle p (x_ {i}) = y_ {i}, \ qquad \ forall i \ in \ left \ {0,1, \ dots, n \ right \}.}

således at sidstnævnte passerer gennem alle de punkter, der skal interpoleres. Ved at integrere i ligning (1) opnår vi et system med lineære ligninger af ukendte $a k$ . Matrixskrivningen er som følger:

{\ displaystyle {\ begin {pmatrix} x_ {0} ^ {n} & x_ {0} ^ {n-1} & x_ {0} ^ {n-2} & \ ldots & x_ {0} & 1 \ \ x_ {1} ^ {n} & x_ {1} ^ {n-1} & x_ {1} ^ {n-2} & \ ldots & x_ {1} & 1 \\\ vdots & \ vdots & \ vdots && \ vdots & \ vdots \ \ x_ {n} ^ {n} & x_ {n} ^ {n-1} & x_ {n} ^ {n-2} & \ ldots & x_ {n} & 1 \ slutning {pmatrix}} {\ begin {pmatrix} a_ {n} \\ a_ {n-1} \\\ vdots \\ a_ {0} \ end {pmatrix}} = {\ begin {pmatrix} y_ {0} \\ y_ {1} \\\ vdots \\ y_ {n} \ end {pmatrix}}}

For at bygge $p ( x )$ er det tilstrækkeligt at løse dette system for at opnå værdierne for $et k$ . Invertering af en fuld matrix er imidlertid en tung beregning (med en Gauss-Jordan eliminationsmetode er beregningen i størrelsesordenen $2 / 3 n 3$ operationer). Meget mere effektive metoder bruger en base af Lagrangian eller Newtonian polynomertil at opnå en henholdsvis diagonal eller trekantet matrix. I praksis erstatter beregningen af delte forskelle opløsningen af det lineære system.

Matrixen er en matrix af vandermonde matrixtypen . Dets determinant er ikke-nul, hvilket beviser isolvance-sætningen: interpolationspolynomet eksisterer og er unikt. (Det unikke skyldes også, at hvis to polynomer med en grad mindre end eller lig med $n$ falder sammen ved $n + 1$ point, så er de ens.)

Interpolationsfejl

Interpolationsfejlen under tilnærmelse af en funktion $f$ , det vil sige: når $y i = f ( x i )$ i ovenstående, er givet med en Taylor-Young-formel:

Hvis $f$ er $n + 1$ gange differentieret over $I = [min ( x 0 , ..., x n , x ), max ( x 0 , ..., x n , x )]$ så

{\ displaystyle \ eksisterer \ xi \ i I \ quad f (x) -p_ {n} (x) = {\ frac {f ^ {(n + 1)} (\ xi)} {(n + 1)! }} \ prod _ {i = 0} ^ {n} (x-x_ {i}).}

Eksistensen af en sådan $ξ$ demonstreres ved iterativ anvendelse af Rolle's sætning :

Demonstration

Enten . Hvis $x$ er et interpolationspunkt, er $f$ $($ $x$ $) -$ $p$ $n$ $($ $x$ $) = 0,$ og formlen holder. ${\ displaystyle x \ in \ mathbb {R}}$

I resten af beviset antager vi, at $x$ ikke er en interpolationsabscissa. Lad os introducere en hjælpefunktion $g$ :

{\ displaystyle g: \ mathbb {R} \ rightarrow \ mathbb {R}: t \ rightarrow g (t) = f (t) -p_ {n} (t) - {\ frac {f (x) -p_ { n} (x)} {\ prod _ {i = 0} ^ {n} (x-x_ {i})}} \ prod _ {i = 0} ^ {n} (t-x_ {i}). }

Denne funktion $g$ har $n + 2$ forskellige rødder:

{\ displaystyle x_ {0}, \ prikker, x_ {n}, x.}

Ved anvendelse af Roles sætning har $g '$ , deriveret af $g$ , $n +1$ forskellige rødder (alle placeret nøjagtigt mellem to på hinanden følgende rødder af $g$ ). Ved at anvende Rolles sætning igen $n$ gange opnår vi, at sådan (da derivatet af ordren $n$ $+1$ af $p$ $n$ er nul ). ${\ displaystyle \ findes \ xi \ i I}$ ${\ displaystyle 0 = g ^ {(n + 1)} (\ xi) = f ^ {(n + 1)} (\ xi) - {\ frac {f (x) -p_ {n} (x)} {\ prod _ {i = 0} ^ {n} (x-x_ {i})}} (n + 1)!}$

Ved at isolere $f ( x ) - p n ( x )$ opnår vi det forventede resultat:

{\ displaystyle f (x) -p_ {n} (x) = {\ frac {f ^ {(n + 1)} (\ xi)} {(n + 1)!}} \ prod _ {i = 0 } ^ {n} (x-x_ {i})}

I det specielle tilfælde, hvor $x i = x 0 + ih$ (jævnt fordelte punkter), sker en katastrofal forværring af interpolationsfejlen, kendt som Runge-fænomenet , normalt når antallet af point øges. For et givet interval $[ x 0 , x n ]$ .

Referencer

(fr) Denne artikel er helt eller delvist taget fra Wikipedia-artiklen på engelsk med titlen " Polynomial interpolation " ( se listen over forfattere ) .

(in) NJ Higham , " Fast Solution of Vandermonde-Like Systems Involving Orthogonal Polynomials " , IMA Journal of Numerical Analysis , bind. 8, nr . 4,1988, s. 473–486 ( DOI 10.1093 / imanum / 8.4.473 )
(in) Å Björck og V. Pereyra, " Solution of Vandermonde Systems of Equations " , Mathematics of Computation , American Mathematical Society, bind. 24, nr . 112,1970, s. 893–903 ( DOI 10.2307 / 2004623 , JSTOR 2004623 )
(i) D. Calvetti og L. Reichel , " Fast Inversion af Vandermonde Matrix-lide Involvering Ortogonale polynomier " , ILO , Vol. 33, nr . 33,1993, s. 473–484 ( DOI 10.1007 / BF01990529 )
(i) Endre Suli og David F. Mayers, En introduktion til numerisk analyse , Cambridge University Press , 2003, s. 183-184 på Google Bøger .

Se også