Interpolarea Neville#

Interpolarea Neville folosește un algoritm foarte asemănător interpolării Lagrange. Cu alte cuvinte, se declară câteva polinoame intermediare.

Menționez că, la bază, metoda utilizează diferențe divizate - motivul pentru care am ales să prezint acest concept abia în cadrul interpolării Newton este pentru că acestea pot fi momentan evitate. După cum am tot menționat, metodele numerice nu ne permit prezentarea conceptelor într-o manieră liniară.

Polinoame intermediare Neville#

Fie \(M=\Big\{(x_k,y_k)\in\mathbb{R}^2\,|\,k\in\overline{0,n}\Big\}\), unde \(n\in\mathbb{N}^*\) și \(x_k\lt x_{k+1}\), \(\forall k\lt n\), o mulțime de \(n+1\) puncte distincte ordonate crescător.

Să considerăm următoarele \(\dfrac{1}{2}(n+1)(n+2)\) polinoame \(P_{i,j}:[x_0,x_n]\rightarrow\mathbb{R}\), astfel încât \(i\in\overline{0,n}\), \(j\in\overline{i,n}\):

\[ \boxed{P_{i,j}(x)=\begin{cases} y_i,&\text{dacă } i=j\\ \dfrac{x_j-x}{x_j-x_i}P_{i,j-1}(x)+\dfrac{x-x_i}{x_j-x_i}P_{i+1,j}(x),&\text{dacă }i\lt j \end{cases}} \]

Considerăm aceste polinoame intermediare, în sensul că vor fi utilizate în interpolare. Vom reveni asupra modului în care acestea sunt utile.

Pentru început însă, vom căuta o paralelă între acestea și multiplicatorii Lagrange.

Proprietăți#

Pornim de la polinoamele de forma \(P_{i,i+1}\), unde \(i\in\overline{0,n-1}\), și evaluăm polinomul în \(x_i\), respectiv \(x_{i+1}\):

\[ P_{i,i+1}(x)=\frac{x_{i+1}-x}{x_{i+1}-x_i}P_{i,i}(x)+\frac{x-x_i}{x_{i+1}-x_i}P_{i+1,i+1}(x) \] \[ \Rightarrow\begin{cases} P_{i,i+1}(x_i)=P_{i,i}(x_i)=y_i\\ P_{i,i+1}(x_{i+1})=P_{i+1,i+1}(x_{i+1})=y_{i+1} \end{cases} \]

Observăm deci cum aceste polinoame iau valori speciale în punctele de indice \(i\) și \(i+1\):

\[ P_{i,i+1}(x)=\begin{cases} P_{i,i}(x_i)=y_i,&\text{dacă }x=x_i\\ P_{i+1,i+1}(x_{i+1})=y_{i+1},&\text{dacă }x=x_{i+1}\\ \text{neimportant},&\text{altfel} \end{cases},\,\forall i\in\overline{0,n-1} \]

Cu pași mărunți, ne îndreptăm atenția către polinoamele de forma \(P_{i,i+2}\), unde \(i\in\overline{0,n-2}\). Ne propunem acum să evaluăm acest polinom în punctele \(x_i\), \(x_{i+1}\) și \(x_{i+2}\). Cunoaștem:

\[ P_{i,i+2}(x)=\frac{x_{i+2}-x}{x_{i+2}-x_i}P_{i,i+1}(x)+\frac{x-x_i}{x_{i+2}-x_i}P_{i+1,i+2}(x) \]

Evaluarea în punctele \(x_i\) și \(x_{i+2}\) este ușor de făcut, se aseamănă cu ce am discutat anterior:

\[\begin{split} P_{i,i+2}(x_i)&=\dfrac{x_{i+2}-x_i}{x_{i+2}-x_i}P_{i,i+1}(x_i)+\dfrac{x_i-x_i}{x_{i+2}-x_i}P_{i+1,i+2}(x_i)\\ &=P_{i,i+1}(x_i)=y_i\\ P_{i,i+2}(x_{i+1})&=\dfrac{x_{i+2}-x_{i+1}}{x_{i+2}-x_i}P_{i,i+1}(x_{i+1})+\dfrac{x_{i+1}-x_i}{x_{i+2}-x_i}P_{i+1,i+2}(x_{i+1})\\ &=\dfrac{x_{i+2}-x_{i+1}}{x_{i+2}-x_i}y_{i+1}+\dfrac{x_{i+1}-x_i}{x_{i+2}-x_i}y_{i+1}=y_{i+1}\\ P_{i,i+2}(x_{i+2})&=\dfrac{x_{i+2}-x_{i+2}}{x_{i+2}-x_i}P_{i,i+1}(x_{i+2})+\dfrac{x_{i+2}-x_i}{x_{i+2}-x_i}P_{i+1,i+2}(x_{i+2})\\ &=P_{i+1,i+2}(x_{i+2})=y_{i+2} \end{split}\]

Observăm deci cum și aceste polinoame iau valori speciale în punctele de indice \(i\), \(i+1\) și \(i+2\) - mai exact:

\[ P_{i,i+2}(x)=\begin{cases} y_i,&\text{dacă }x=x_i\\ y_{i+1},&\text{dacă }x=x_{i+1}\\ y_{i+2},&\text{dacă }x=x_{i+2}\\ \text{neimportant},&\text{altfel} \end{cases},\,\forall i\in\overline{0,n-2} \]

Prin inducție (se vor presupune propozițiile \(\pi_{i,j}\) și \(\pi_{i+1, j+1}\) adevărate pentru a se demonstra valoarea de adevăr a propoziției \(\pi_{i, j+1}\), unde fiecărei propoziții \(\pi_{i,j}\) îi este atribuită corectitudinea formulei \(P_{i,j}\)), obținem proprietatea generalizată a polinoameor de forma \(P_{i,j}\), unde \(i\in\overline{0,n}\), \(j\in\overline{i,n}\):

\[ \boxed{P_{i,j}(x_k)=y_k}\,,\,\,\forall k\in\overline{i,j} \]

Remarcați acum similitudinea cu multiplicatorii Lagrange?

Interpolarea Neville#

Utilizând proprietatea descrisă anterior, observăm cum \(P_{0,n}\) este un polinom special, întrucât:

\[ \boxed{P_{0,n}(x_k)=y_k}\,,\,\,\forall k\in\overline{0,n} \]

Deoarece \(P_{0,n}\) este un polinom de grad \(n\), acesta va reprezenta chiar interpolarea polinomială a punctelor din mulțimea \(M\).

Cu alte cuvinte, interpolarea Neville presupune calcularea lui \(P_{0,n}\) folosind polinoamele intermediare descrise mai sus.

Simplificare#

Pentru a nu exista dubii în ceea ce privește formula de recurență, poate fi schițat oricând următorul desen ce permite reținerea mai ușoară a algoritmului - de exemplu, pentru \(n=3\):

Desen ce ilustrează recurența interpolării Neville

Desenul explică dependența dintre polinoamele intermediare Neville. Astfel, cu cât ne deplasăm mai mult de la stânga la dreapta, cu atât ne apropiem mai mult de interpolarea finală Neville.

Cod ilustrativ#

O variantă de implementare (în care polinoamele sunt indexate de la \(1\) în loc de \(0\) din cauza restricțiilor impuse de Matlab) este prezentată mai jos sub forma funcției interpolare_neville, în baza notațiilor:

  • M - o matrice de două coloane, unde fiecare linie reprezintă o pereche de puncte;

  • xp - punctul în care se vrea evaluarea interpolării;

  • idx_i - indexul \(i\) al polinomului intermediar \(P_{i,j}\) ce se vrea evaluat;

  • idx_j - indexul \(j\) al polinomului intermediar \(P_{i,j}\) ce se vrea evaluat.

Funcția returnează yp, evaluarea în punctul xp. 

function yp = interpolare_neville(M, xp, idx_i, idx_j)
    if idx_i == idx_j
        yp = M(idx_i,2);
    else
        P_left = interpolare_neville(M, xp, idx_i, idx_j-1);
        P_right = interpolare_neville(M, xp, idx_i+1, idx_j);
        yp = ((M(idx_j,1) - xp) * P_left + (xp - M(idx_i,1)) * P_right);
        yp /= (M(idx_j,1) - M(idx_i,1));
    end
end

Concluzii#

Metoda se folosește în practică numai atunci când se vrea calcularea valorii \(P_{0,n}(t)\) pentru o valoarea \(t\) cunoscută. Vom discuta alți algoritmi pentru a afla polinomul în sine.

Licență#

The book "Metode Numerice", written by Valentin-Ioan Vintilă, is licensed under CC BY-NC-SA 4.0

Results will appear as you type