Interpolation med algebraiske polynomier

Interpolation med algebraiske polynomier af en funktion af et reelt argument på et segment - ved at finde koefficienterne for et polynomium af grad mindre end eller lig med , som antager værdier af argumentet , kaldes mængden interpolationsnoder : $f(x)$ $[a,b]$ $P_n(x)$ $n$ $x_0,\ x_1,\ \ldots,\ x_n$ $f(x_{i})$ $x_0,\ x_1,\ \ldots,\ x_n$

P_{n}(x_{i})=f(x_{i}),\quad i=0,\ 1,\ ...,\ n.

Systemet af lineære algebraiske ligninger , der bestemmer koefficienterne for et sådant polynomium, har formen: $a_{i}$

P_{n}(x_{i})=a_{0}+a_{1}x_{i}+a_{2}x_{i}^{2}+\ldots +a_{n}x_{ i}^{n}=f(x_{i}),\quad i=0,\ 1,\ \ldots ,\ n.

Dens determinant er Vandermonde-determinanten .

\triangle ={\begin{vmatrix}1&x_{0}&x_{0}^{2}&...&x_{0}^{n}\\1&x_{1}&x_{1}^{2} &...&x_{1}^{n}\\.......\\1&x_{n}&x_{n}^{2}&...&x_{n}^{n}\end{ vmatrix}}=\prod _{i,j=0 \atop i>j}^{n}(x_{i}-x_{j}).

Den er ikke -nul for enhver parvis forskellige værdier af , og interpolation af en funktion med dens værdier ved knuderne ved hjælp af et polynomium er altid mulig og unik. $x_{i}$ $f(x)$ $x_{i}$ $P_n(x)$

Ansøgning

Den resulterende interpolationsformel bruges ofte til omtrentlig beregning af funktionsværdier for andre argumentværdier end interpolationsnoderne. Samtidig skelnes der mellem interpolation i snæver forstand , hvornår , og ekstrapolation , når . $f(x)\approx P_{n}(x)$ $f$ $x$ $x\in\left[a,b\right]$ $x\ikke \in \left[a,b\right]$

Interpolationsproblem i rummet

Lad der gives punkter i rummet , der har radiusvektorer i et eller andet koordinatsystem $n$ ${\displaystyle P_{1},\ P_{2},\ \dots ,\ P_{n))$ $\mathbf {r} _{1},\ \mathbf {r} _{2},\ \dots ,\ \mathbf {r} _{n}.$

Interpolationens opgave er at konstruere en kurve, der går gennem de specificerede punkter i den specificerede rækkefølge.

Løsning af problemet

Et uendeligt antal kurver kan tegnes gennem et fast ordnet sæt af punkter, så problemet med interpolation med en vilkårlig funktion har ikke en unik løsning. For det unikke ved løsningen er det nødvendigt at pålægge visse begrænsninger på funktionens form.

Vi vil konstruere kurver i form , hvor parameteren ændres på et bestemt interval : ${\mathbf {r}}(t)$ $t$ $[a,\b]$

a\leq t\leq b

Lad os introducere et gitter af punkter på segmentet : og kræve, at for værdien af parameteren passerer kurven gennem punktet , således at $[a,b]$ $\{t_{i}\}$ $n$ $a=t_{1}<t_{2}<t_{3}<\dots <t_{n}=b$ ${\displaystyle t=t_{i))$ $P_{i}$ $\mathbf {r} (t_{i})=\mathbf {r} _{i}.$

Indførelsen af parametrisering og grid kan gøres på forskellige måder. Normalt vælges enten et ensartet gitter under antagelse af , , , eller mere foretrukket er punkterne forbundet med segmenter, og længden af segmentet tages som forskellen mellem parameterværdierne . $a=0$ $b=n-1$ $t_{i}=i-1$ ${\displaystyle t_{i+1}-t_{i))$ ${\displaystyle \mathbf {r} _{i+1}-\mathbf {r} _{i))$

En af de almindelige interpolationsmetoder er at bruge kurven som et polynomium i grad , det vil sige som en funktion: $t$ $n-1$

\mathbf {r} (t)=\mathbf {p} ^{(n-1)}(t)=\sum _{k=1}^{n}\mathbf {a} _{k} t^{nk}.

Polynomiet har koefficienter , der kan findes ud fra betingelserne: $n$ ${\displaystyle \mathbf {a} _{k))$

\mathbf {r} (t_{i})=\mathbf {r} _{i}.

Disse betingelser fører til et system af lineære ligninger for koefficienterne : ${\displaystyle \mathbf {a} _{k))$

${\begin{pmatrix}1&t_{1}&t_{1}^{2}&\ldots &t_{1}^{n-1}\\1&t_{2}&t_{2}^{2}&\ ldots &t_{2}^{n-1}\\\vdots &\vdots &\vdots &&\vdots \\1&t_{n}&t_{n}^{2}&\ldots &t_{n}^{n-1 }\end{pmatrix}}{\begin{pmatrix}\mathbf {a} _{n}\\\mathbf {a} _{n-1}\\\vdots \\\mathbf {a} _{1} \end{pmatrix}}={\begin{pmatrix}\mathbf {r} _{1}\\\mathbf {r} _{2}\\\vdots \\\mathbf {r} _{n}\end {pmatrix}}$

Bemærk, at for at finde koefficienterne, for eksempel i tredimensionelt rum, skal tre ligningssystemer løses: for og koordinater . Alle har en matrix af koefficienter, der inverterer, som ved værdierne af punkternes radiusvektorer beregnes vektorerne for polynomiets koefficienter. Matrix determinant $x$ $y$ $z$ ${\mathbf {r}}_{i}$ ${\displaystyle \mathbf {a} _{k))$

$W(t_{1},t_{2},\ldots ,t_{n})={\begin{vmatrix}1&t_{1}&t_{1}^{2}&\ldots &t_{1}^ {n-1}\\1&t_{2}&t_{2}^{2}&\ldots &t_{2}^{n-1}\\\vdots &\vdots &\vdots &&\vdots \\1&t_{n }&t_{n}^{2}&\ldots &t_{n}^{n-1}\end{vmatrix}}=\prod _{i,j,i>j}(t_{i}-t_{j })$

kaldes Vandermonde-determinanten . Hvis gitterknudepunkterne ikke matcher, er det ikke-nul, og ligningssystemet har en unik løsning.

Ud over direkte matrixinversion er der flere andre måder at beregne interpolationspolynomiet på. På grund af polynomiets unikke karakter taler vi om forskellige former for dets skrivning.

Fordele

For et givet sæt punkter og et parametergitter er kurven konstrueret unikt.
Kurven er interpolerende, det vil sige, den passerer gennem alle givne punkter.
Kurven har kontinuerlige afledte af en hvilken som helst orden.

Ulemper

Efterhånden som antallet af punkter stiger, stiger rækkefølgen af polynomiet, og med det stiger antallet af operationer, der skal udføres for at beregne et punkt på kurven.
Når antallet af punkter stiger, kan interpolationskurven svinge (se eksemplet nedenfor).
Med en stigning i antallet af punkter er den dårligt egnet til ekstrapolering , da værdien af gradpolynomiet uden for interpolationssegmentet altid divergerer mod uendeligt (jo hurtigere, jo mere ) uanset konvergensen af den ekstrapolerede funktion. $n>0$ $n$

Eksempel

Et klassisk eksempel ( Runge ), der viser forekomsten af oscillationer i et interpolationspolynomium, er interpolation på et ensartet gitter af funktionsværdier $f(x)={\frac {1}{1+x^{2))}.$

Lad os introducere et ensartet gitter , , på segmentet og overveje adfærden af polynomiet , som tager værdierne ved punkterne . $[-5,5]$ $x_{i}=-5+(i-1)h$ $h=10/(n-1)$ $1\leq i\leq n$ $y(x)=\sum _{i=1}^{n}a_{i}x^{ni},$ $x_{i}$ $y_{i}=1/(1+x_{i}^{2})$

Figuren viser graferne for selve funktionen (stiplet linje) og tre interpolationskurver for : $n=3,5,9$

interpolation på gitteret - kvadratisk parabel; $x_{1}=-5,x_{2}=0,x_{3}=5$
interpolation på gitteret er et polynomium af fjerde grad; $x_{1}=-5,x_{2}=-2.5,x_{3}=0,x_{4}=2.5,x_{5}=5$
interpolation på gitteret er et polynomium af ottende grad. $x_{1}=-5,x_{2}=-3.75,x_{3}=-2.5,x_{4}=-1.25,x_{5}=0,x_{6}=1.25,x_ {7}=2,5,x_{8}=3,75,x_{9}=5$

Værdierne af interpolationspolynomiet, selv for glatte funktioner på mellemliggende punkter, der ikke falder sammen med interpolationens noder, kan afvige kraftigt fra værdierne af selve funktionen, sådan opførsel af polynomiet kaldes oscillationer.