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\text{ , }i=0,\dots ,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.(1)$

unde p trebuie să verifice:

$p(x_i)=y_i,\mathrm{\forall }i\in \{0,1,\dots ,n\}.$

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\text{for all }i\in \{0,1,\dots ,n\}.$

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

$\left[\begin{array}{cccccc}{x}_0^n& x_0^{n-1}& x_0^{n-2}& \dots & x_0& 1\\ x_1^n& x_1^{n-1}& x_1^{n-2}& \dots & x_1& 1\\ ⋮& ⋮& ⋮& & ⋮& ⋮\\ x_n^n& x_n^{n-1}& x_n^{n-2}& \dots & x_n& 1\end{array}\right]\left[\begin{array}{c}{a}_n\\ a_{n-1}\\ ⋮\\ a_0\end{array}\right]=\left[\begin{array}{c}{y}_0\\ y_1\\ ⋮\\ y_n\end{array}\right].$

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