Interpolointi algebrallisilla polynomeilla

Segmentin todellisen argumentin funktion interpolointi algebrallisilla polynomeilla - löytääkseen polynomin kertoimet, joiden aste on pienempi tai yhtä suuri kuin , joka ottaa argumentin arvot , joukkoa kutsutaan interpolointisolmuiksi : $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.

Lineaaristen algebrallisten yhtälöiden järjestelmällä, joka määrittää tällaisen polynomin kertoimet , on muoto: $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.

Sen determinantti on Vandermonden determinantti .

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

Se on nollasta erilainen kaikille pareittain eri arvoille , ja funktion interpolointi sen arvoilla solmuissa polynomin avulla on aina mahdollista ja ainutlaatuista. $x_{i}$ $f(x)$ $x_{i}$ $P_n(x)$

Sovellus

Tuloksena olevaa interpolointikaavaa käytetään usein likimääräiseen funktioarvojen laskemiseen muille argumenttiarvoille kuin interpolointisolmuille. Samalla erotetaan interpolointi suppeassa merkityksessä , when , ja ekstrapolointi , kun . $f(x)\approx P_{n}(x)$ $f$ $x$ $x\in\left[a,b\right]$ $x\not \in \left[a,b\right]$

Interpolointiongelma avaruudessa

Annetaan avaruudessa pisteet , joilla on jossain koordinaattijärjestelmässä sädevektorit $n$ ${\displaystyle P_{1},\ P_{2},\ \dots ,\ P_{n))$ $\mathbf {r} _{1},\ \mathbf {r} _{2},\ \dots ,\ \mathbf {r} _{n}.$

Interpoloinnin tehtävänä on muodostaa käyrä, joka kulkee määrättyjen pisteiden läpi määritetyssä järjestyksessä.

Ongelman ratkaisu

Kiinteän järjestetyn pistejoukon läpi voidaan piirtää ääretön määrä käyriä, joten mielivaltaisen funktion interpoloinnin ongelmalla ei ole ainutlaatuista ratkaisua. Ratkaisun ainutlaatuisuuden vuoksi on tarpeen asettaa tiettyjä rajoituksia funktion muodolle.

Rakennamme käyriä muotoon , jossa parametri muuttuu tietyllä aikavälillä : ${\mathbf {r}}(t)$ $t$ $[a,\b]$

a\leq t\leq b

Esitetään janalle pisteiden ruudukko : ja vaaditaan, että parametrin arvolle käyrä kulkee pisteen läpi , niin että ${\näyttötyyli [a,b]}$ $\{t_{i}\}$ $n$ $a=t_{1}<t_{2}<t_{3}<\pisteet <t_{n}=b$ ${\näyttötyyli t=t_{i))$ $P_{i}$ $\mathbf {r} (t_{i})=\mathbf {r} _{i}.$

Parametrisoinnin ja ruudukon käyttöönotto voidaan tehdä monin eri tavoin. Yleensä valitaan joko yhtenäinen ruudukko olettaen , , , tai mieluummin pisteet on yhdistetty segmenteillä ja janan pituus otetaan parametrien arvojen erotukseksi . $a=0$ $b=n-1$ $t_{i}=i-1$ ${\näyttötyyli t_{i+1}-t_{i))$ ${\displaystyle \mathbf {r} _{i+1}-\mathbf {r} _{i))$

Yksi yleisimmistä interpolointimenetelmistä on käyttää käyrää astepolynomina eli funktiona: $t$ $n-1$

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

Polynomilla on kertoimet , jotka voidaan löytää ehdoista: $n$ ${\displaystyle \mathbf {a} _{k))$

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

Nämä ehdot johtavat kertoimien lineaariseen yhtälöjärjestelmään : ${\displaystyle \mathbf {a} _{k))$

${\begin{pmatrix}1&t_{1}&t_{1}^{2}&\ldots &t_{1}^{n-1}\\1&t_{2}&t_{2}^{2}&\ lpisteet &t_{2}^{n-1}\\\vpisteet &\vpisteet &\vpisteet &&\vpisteet \\1&t_{n}&t_{n}^{2}&\lpisteet &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}}$

Huomaa, että kertoimien löytämiseksi esimerkiksi kolmiulotteisessa avaruudessa on ratkaistava kolme yhtälöjärjestelmää: for , ja koordinaatit. Niillä kaikilla on yksi kerroinmatriisi, joka käänteisesti lasketaan pisteiden sädevektorien arvojen perusteella polynomin kertoimien vektorit. Matriisin determinantti $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}&\lpisteet &t_{2}^{n-1}\\\vpisteet &\vpisteet &\vpisteet &&\vpisteet \\1&t_{n }&t_{n}^{2}&\ldots &t_{n}^{n-1}\end{vmatrix}}=\prod _{i,j,i>j}(t_{i}-t_{j })$

kutsutaan Vandermonde-determinantiksi . Jos ruudukon solmut eivät täsmää, se on nollasta poikkeava ja yhtälöjärjestelmällä on ainutlaatuinen ratkaisu.

Suoran matriisin inversion lisäksi on olemassa useita muita tapoja laskea interpolaatiopolynomi. Polynomin ainutlaatuisuuden vuoksi puhumme sen kirjoittamisen eri muodoista.

Edut

Tietylle pistejoukolle ja parametriruudukolle käyrä muodostetaan yksilöllisesti.
Käyrä on interpoloiva, eli se kulkee kaikkien annettujen pisteiden läpi.
Käyrällä on minkä tahansa järjestyksen jatkuvat derivaatat.

Haitat

Pisteiden määrän kasvaessa polynomin järjestys kasvaa, ja sen mukana kasvaa operaatioiden määrä, jotka on suoritettava pisteen laskemiseksi käyrältä.
Pisteiden määrän kasvaessa interpolaatiokäyrä voi värähdellä (katso esimerkki alla).
Pisteiden määrän kasvaessa se soveltuu huonosti ekstrapolointiin , koska interpolointisegmentin ulkopuolella olevan astepolynomin arvo poikkeaa aina äärettömyyttä kohti (mitä nopeammin, sitä enemmän ) ekstrapoloidun funktion konvergenssista riippumatta . $n>0$ $n$

Esimerkki

Klassinen esimerkki ( Runge ), joka näyttää värähtelyjen esiintymisen interpolaatiopolynomissa, on interpolointi yhtenäisellä funktioarvojen ruudukolla $f(x)={\frac {1}{1+x^{2))}.$

Otetaan käyttöön yhtenäinen ruudukko , janalle ja tarkastellaan sen polynomin käyttäytymistä, joka ottaa arvot pisteistä . $[-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})$

Kuvassa on itse funktion kaaviot (katkoviiva) ja kolme interpolaatiokäyrää : $n=3,5,9$

interpolointi ruudukossa - neliöparaabeli; $x_{1}=-5,x_{2}=0,x_{3}=5$
interpolointi ruudukossa on neljännen asteen polynomi; $x_{1}=-5,x_{2}=-2,5,x_{3}=0,x_{4}=2,5,x_{5}=5$
ruudukon interpolointi on kahdeksannen asteen polynomi. $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$

Interpolointipolynomin arvot, jopa tasaisille funktioille välipisteissä, jotka eivät ole yhtäpitäviä interpoloinnin solmujen kanssa, voivat poiketa voimakkaasti itse funktion arvoista, tällaista polynomin käyttäytymistä kutsutaan värähtelyksi.