Interpolare polinomială

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