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.

• 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:

${\displaystyle 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.

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

${\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)}$

unde p trebuie să verifice:

${\displaystyle 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ă

${\displaystyle 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 ${\displaystyle a_{k}}$.

Sistemul în forma matrice-vector este

${\displaystyle {\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 ${\displaystyle a_{k}}$ pentru a construi interpolant ${\displaystyle p(x).}$ Matricea ${\displaystyle 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 ^[1], ceea ce cauzează erori mari la calculul coeficienților ${\displaystyle a_{i}}$ în cazul în care sistemul de ecuații este rezolvat cu ajutorul metodei de eliminare Gauss.

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

${\displaystyle Va=y\,}$

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

${\displaystyle \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 ${\displaystyle x_{i}-x_{j}}$ nu este niciodată la zero, prin urmare V este nesingulară și sistemul are o soluție unică.

Dacă ${\displaystyle f}$ este de ${\displaystyle n+1}$ ori derivabilă pe intervalul ${\displaystyle I=[\min(x_{0},...x_{n},x),\max(x_{0},...x_{n},x)]\,}$, iar ${\displaystyle 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

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

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

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

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

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

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

Prin urmare: ${\displaystyle 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 ${\displaystyle x_{i}=x_{0}+ih}$, rezultă că eroarea de interpolare este O${\displaystyle (h^{n+1})}$.

În cazul particular ${\displaystyle 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 ${\displaystyle [x_{0},x_{n}]\,}$ dat.

• 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

Portal Matematică

• 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.