Interpolare prin polinoame algebrice

Interpolarea prin polinoame algebrice a unei funcții a unui argument real pe un segment - găsirea coeficienților unui polinom de grad mai mic sau egal cu , care ia valori ale argumentului , mulțimea se numește noduri de interpolare : $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.

Sistemul de ecuații algebrice liniare care determină coeficienții unui astfel de polinom are forma: $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.

Determinantul său este determinantul Vandermonde .

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

Este non- zero pentru orice pereche de valori diferite ale , iar interpolarea unei funcții cu valorile sale la noduri folosind un polinom este întotdeauna posibilă și unică. $x_{i}$ $f(x)$ $x_{i}$ $P_n(x)$

Aplicație

Formula de interpolare rezultată este adesea folosită pentru calcularea aproximativă a valorilor funcției pentru valorile argumentelor, altele decât nodurile de interpolare. În același timp, se distinge interpolarea în sens restrâns , când , și extrapolarea , când . $f(x)\aprox P_{n}(x)$ $f$ $X$ $x\in\stanga[a,b\dreapta]$ $x\nu \în \left[a,b\right]$

Problemă de interpolare în spațiu

Să fie date puncte în spațiu care au vectori de rază într-un sistem de coordonate $n$ $P_{1},\P_{2},\\dots,\P_{n)$ $\mathbf {r} _{1},\ \mathbf {r} _{2},\ \dots ,\ \mathbf {r} _{n}.$

Sarcina interpolării este de a construi o curbă care trece prin punctele specificate în ordinea specificată.

Rezolvarea problemei

Un număr infinit de curbe poate fi trasat printr-un set ordonat fix de puncte, astfel încât problema interpolării printr-o funcție arbitrară nu are o soluție unică. Pentru unicitatea soluției, este necesar să se impună anumite restricții asupra formei funcției.

Vom construi curbe sub forma , unde parametrul se modifică pe un anumit interval : ${\mathbf {r}}(t)$ $t$ $[a,\b]$

a\leq t\leq b

Să introducem o grilă de puncte pe segment : și să cerem ca, pentru valoarea parametrului , curba să treacă prin punctul , astfel încât $[a,b]$ $\{t_{i}\}$ $n$ $a=t_{1}<t_{2}<t_{3}<\dots <t_{n}=b$ $t=t_{i)$ $P_{i}$ $\mathbf {r} (t_{i})=\mathbf {r} _{i}.$

Introducerea parametrizării și a grilei se poate face în diferite moduri. De obicei, fie se alege o grilă uniformă, presupunând , , , sau, mai preferabil, punctele sunt conectate prin segmente și lungimea segmentului este luată ca diferență între valorile parametrilor . $a=0$ $b=n-1$ $t_{i}=i-1$ $t_{i+1}-t_{i)$ $\mathbf {r} _{i+1}-\mathbf {r} _{i)$

Una dintre metodele comune de interpolare este utilizarea curbei ca polinom în grad , adică ca funcție: $t$ $n-1$

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

Polinomul are coeficienți care pot fi găsiți din condițiile: $n$ $\mathbf {a} _{k)$

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

Aceste condiții conduc la un sistem de ecuații liniare pentru coeficienții : $\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}}$

Rețineți că pentru a găsi coeficienții, de exemplu, în spațiul tridimensional, trebuie rezolvate trei sisteme de ecuații: pentru , și coordonate. Toate au o singură matrice de coeficienți, inversând care, prin valorile vectorilor de rază ai punctelor, se calculează vectorii coeficienților polinomului. Determinant de matrice $X$ $y$ $z$ ${\mathbf {r}}_{i}$ $\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 })$

se numeste determinant Vandermonde . Dacă nodurile grilei nu se potrivesc, acesta este diferit de zero și sistemul de ecuații are o soluție unică.

În plus față de inversarea directă a matricei, există câteva alte moduri de a calcula polinomul de interpolare. Datorită unicității polinomului, vorbim despre diverse forme de scriere a acestuia.

Beneficii

Pentru un set dat de puncte și o grilă de parametri, curba este construită în mod unic.
Curba se interpolează, adică trece prin toate punctele date.
Curba are derivate continue de orice ordin.

Dezavantaje

Pe măsură ce numărul de puncte crește, ordinea polinomului crește și, odată cu aceasta, crește și numărul de operații care trebuie efectuate pentru a calcula un punct pe curbă.
Pe măsură ce numărul de puncte crește, curba de interpolare poate oscila (vezi exemplul de mai jos).
Cu o creștere a numărului de puncte, este puțin potrivit pentru extrapolare , deoarece valoarea polinomului de grad în afara segmentului de interpolare diverge întotdeauna către infinit (cu cât mai rapid, cu atât mai mult ), indiferent de convergența funcției extrapolate. $n>0$ $n$

Exemplu

Un exemplu clasic ( Runge ), care arată apariția oscilațiilor într-un polinom de interpolare, este interpolarea pe o grilă uniformă de valori ale funcției. $f(x)={\frac {1}{1+x^{2)}}.$

Să introducem o grilă uniformă , , pe segment și să luăm în considerare comportamentul polinomului care ia valorile în puncte . $[-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})$

Figura prezintă graficele funcției în sine (linie punctată cu linii) și trei curbe de interpolare pentru : $n=3,5,9$

interpolare pe grilă - parabolă pătratică; $x_{1}=-5,x_{2}=0,x_{3}=5$
interpolarea pe grilă este un polinom de gradul al patrulea; $x_{1}=-5,x_{2}=-2,5,x_{3}=0,x_{4}=2,5,x_{5}=5$
interpolarea pe grilă este un polinom de gradul opt. $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$

Valorile polinomului de interpolare, chiar și pentru funcții netede în punctele intermediare care nu coincid cu nodurile interpolării, pot abate puternic de la valorile funcției în sine, un astfel de comportament al polinomului se numește oscilații.