Interpolare polinomială

În analiză numerică,interpolarea polinomială este o tehnică de interpolare a unui set de date sau a unei funcții printr-un polinom. Cu alte cuvinte, dat un set de puncte (obținut, de exemplu, ca urmare a unui experiment), vom căuta un polinom care trece prin toate aceste puncte, și, eventual, verificați pentru alte condiții, dacă este posibil, gradul cel mai mic.

Definiție

• Având un set de n +1 puncte, (x_i,y_i) (x_i diferite între ele), găsim un polinom P (cu coeficienți reali) de grad cel mult n, care satisface:

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

Se demonstrează că există un singur polinom de grad cel mult n care trece prin cele n puncte.

Construcția polinomului de interpolare

Punctele roșii corespund punctelor (x_k,y_k), iar curba albastră reprezintă polinomului de interpolare.

Punctele roșii indică punctele de date (x_k,y_k), în timp ce curba albastră arată polinomul de interpolare.

Să presupunem că polinomul de interpolare este dat de:

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

unde p trebuie să verifice:

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

astfel încât să treacă prin setul de puncte de interpolat. Afirmația că p interpolează punctele de date înseamnă că

$p(x_{i})=y_{i}\qquad {\mbox{for all }}i\in \left\{0,1,\dots ,n\right\}.$

Dacă înlocuim ecuația (1), în aici, avem un sistem de ecuații liniare din coeficienții $a_{k}$.

Sistemul în forma matrice-vector este

${\begin{bmatrix}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\end{bmatrix}}{\begin{bmatrix}a_{n}\\a_{n-1}\\\vdots \\a_{0}\end{bmatrix}}={\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{n}\end{bmatrix}}.$

Trebuie să rezolvăm acest sistem pentru $a_{k}$ pentru a construi interpolant $p(x).$ Matricea $a_{k}$ este o matrice Vandermonde.

Determinantul său este diferit de zero, ceea ce demonstrează că polinomul de interpolare există și este unic.

Rangul matricii Vandermonde poate fi mare , ceea ce cauzează erori mari la calculul coeficienților $a_{i}$ în cazul în care sistemul de ecuații este rezolvat cu ajutorul metodei de eliminare Gauss.

Unicitatea polinomului de interpolare

Având în vedere matricea Vandermonde folosit de mai sus pentru a construi interpolant, putem scrie sistemul sub forma

$Va=y\,$

Pentru a dovedi că V este matrice inversabilă, vom folosi formula determinantului Vandermonde:

$\det(V)=\prod _{i,j=0,i<j}^{n}(x_{i}-x_{j})$

Deoarece cele n + 1 puncte sunt distincte, determinantul nu poate fi zero, deoarece $x_{i}-x_{j}$ nu este niciodată la zero, prin urmare V este nesingulară și sistemul are o soluție unică.

Eroarea de interpolare

Dacă $f$ este de $n+1$ ori derivabilă pe intervalul $I=[\min(x_{0},...x_{n},x),\max(x_{0},...x_{n},x)]\,$, iar $p_{n}(x)$ este un polinom de grad cel mult n care interpolează f în n + 1 puncte distincte {x_i} (i=0,1,...,n) în acel interval, atunci

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

Această formulă este demonstrată prin aplicarea iterativă a teoremei lui Rolle pe subintervalele $[x_{i-1},x_{i}]\,$.

Pentru fiecare x în intervalul de definiție există $\xi$ în acel interval astfel încât

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

Să notăm termenul de eroare cu $R_{n}(x)=f(x)-p_{n}(x)$ și considerăm o funcție auxiliară $Y(t)=R_{n}(t)-{\frac {R_{n}(x)}{W(x)}}\ W(t)$ unde $W(t)=\prod _{i=0}^{n}(t-x_{i})$ și $W(x)=\prod _{i=0}^{n}(x-x_{i})$ Deoarece $x_{i}$ sunt rădăcinile funcției $f-p_{n}$, vom avea $Y(x)=R_{n}(x)-{\frac {R_{n}(x)}{W(x)}}\ W(x)=0$ și $Y(x_{i})=R_{n}(x_{i})-{\frac {R_{n}(x)}{W(x)}}\ W(x_{i})=0$ Atunci $Y(t)$ are n +2 rădăcini. Din teorema lui Rolle, $Y^{\prime }(t)$ are n +1 rădăcini, apoi $Y^{(n+1)}(t)$ are o rădăcină $\xi$, unde $\xi$ este în intervalul I. Astfel încât să putem obține $Y^{(n+1)}(t)=R_{n}^{(n+1)}(t)-{\frac {R_{n}(x)}{W(x)}}\ (n+1)!$

Deoarece $p_{n}(x)$ este un polinom de grad cel mult n, atunci $R_{n}^{(n+1)}(t)=f^{(n+1)}(t)$ Astfel $Y^{(n+1)}(t)=f^{(n+1)}(t)-{\frac {R_{n}(x)}{W(x)}}\ (n+1)!$

Deoarece $\xi$ este rădăcina lui $Y^{(n+1)}(t)$, atunci $Y^{(n+1)}(\xi )=f^{(n+1)}(\xi )-{\frac {R_{n}(x)}{W(x)}}\ (n+1)!=0$

Prin urmare: $R_{n}(x)=f(x)-p_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i})$.

În cazul nodurilor de interpolare la distanțe egale $x_{i}=x_{0}+ih$, rezultă că eroarea de interpolare este O$(h^{n+1})$.

În cazul particular $x_{i}=x_{0}+ih\,$ (puncte distribuite uniform), apare de obicei o eroare foarte mare de interpolare, cunoscută sub numele de fenomenul Runge, atunci când crește numărul de puncte pentru un interval $[x_{0},x_{n}]\,$ dat.

Note

Bibliografie

• Constantin Ilioi, Probleme de optimizare și algoritmi de aproximare a soluțiilor, Editura Academiei Republicii Socialiste România, București, 1980.
• www.utgjiu.ro/math/mbuneci/book/mn2009.pdf/ Metode numerice - Aspecte teoretice și practice, Mădălina Roxana Buneci, Editura Academică Brâncuși, Târgu Jiu, 2009
• http://cs.upm.ro/~bela.finta/.files/carti/Numerika.pdf Arhivat în 7 septembrie 2012, la Wayback Machine.
• www.vpetrehus.home.ro/Lectii_AN.pdf/ Lecții de analiză numerică, Viorel Petrehus, Universitatea Tehnică de Construcții București, 2010

Legături externe

• www.utgjiu.ro/math/mbuneci/book/mn2009.pdf
• http://cs.upm.ro/~bela.finta/.files/carti/Numerika.pdf Arhivat în 7 septembrie 2012, la Wayback Machine.