7. Interpolarea Vandermonde#

Interpolarea Vandermonde este cea mai simplă interpolare polinomială. Vom începe așadar să explicăm de ce preferăm să utilizăm polinoame pentru a interpola funcții, iar apoi vom discuta despre interpolarea Vandermonde propriu-zisă.

Ce este mai simplu ca un polinom?#

Să considerăm pentru moment funcția \(f:D\subseteq\mathbb{R}\rightarrow\mathbb{R}\). Din perspectiva unui inginer, matematician, fizician etc, cam ce proprietăți căutăm? Ce ne dorim să aibă această funcție, în situația în care putem alege un set de proprietăți?

Continuitate - este greu să lucrăm cu funcții care nu sunt continue;
Derivabilitate - mergem un pas mai departe - în cazul în care vrem să analizăm o funcție, este foarte util să o studiem prin derivata sa;
Integrabilitate - există contexte în care ne-ar fi de folos să putem integra funcția fără a o prelucra suplimentar;
Viteză de evaluare - degeaba avem o funcție cu care se lucrează ușor matematic, însă pe care este prea costisitor să o evaluăm pe calculator;
Simplitate - cu cât permite calcule mai ușoare, cu atât mai bine - proprietatea aceasta merge mână-în-mână cu anterioara.

Deși există mai multe funcții care bifează o parte din criteriile de mai sus, primul exemplu care ne vine în minte și care bifează tot este cel al polinoamelor - le vom considera cele mai simple funcții posibile.

Interpolarea Vandermonde#

Să folosim acum polinoamele pentru a interpola o mulțime de puncte.

Fie polinomul \(P_n\in\mathbb{R}[x]\), unde \(n\in\mathbb{N}\) reprezintă gradul său. Pentru a ușura calculele, să considerăm forma unui polinom oarecare, având coeficienții \(a_k\in\mathbb{R}\), \(\forall k\in\overline{0,n}\), cu mențiunea că \(a_n\neq0\):

\[ P_n(x)=\sum_{k=0}^na_kx^k=a_0+a_1x+a_2x^2+\dots+a_nx^n \]

Plecăm acum de la o mulțime de \(n+1\) puncte, \(M=\Big\{(x_k,y_k)\in\mathbb{R}^2\,\big|\,k\in\overline{0,n}\Big\}\). Să încercăm să impunem ca polinomul \(P_n\) descris anterior să treacă prin toate punctele din \(M\), adică:

\[ P_n(x_k)=y_k,\forall k\in\overline{0,n}\Rightarrow\begin{cases} P_n(x_0)=a_0+a_1x_0+a_2x_0^2+\dots+a_nx_0^n=y_0\\ P_n(x_1)=a_0+a_1x_1+a_2x_1^2+\dots+a_nx_1^n=y_1\\ \,\,\,\,\,\,\,\,\vdots\\ P_n(x_n)=a_0+a_1x_n+a_2x_n^2+\dots+a_nx_n^n=y_n\\ \end{cases} \]

Așadar, matriceal, sistemul poate fi scris sub forma:

\[ \boxed{\begin{bmatrix} 1 & x_0 & x_0^2 & \dots & x_0^n\\ 1 & x_1 & x_1^2 & \dots & x_1^n\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & x_n & x_n^2 & \dots & x_n^n \end{bmatrix}\begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_n \end{bmatrix}=\begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_n \end{bmatrix}} \]

În ciuda aparențelor, acesta este un sistem de ecuații liniare - valorile de forma \(x_k^t\), unde \(k\in\overline{0,n}\) și \(t\in\overline{0,n}\), sunt constante!

Valorile \(x_k^t\) sunt constante

Amintiți-vă de unde provin valorile de forma \(x_k\), anume din mulțimea \(M=\Big\{(x_k,y_k)\in\mathbb{R}^2\,\big|\,k\in\overline{0,n}\Big\}\). Așadar, \(x_k\) este cunoscut încă de la început, ceea ce înseamnă că \(x_k^t\) este o constantă ce așteaptă să fie calculată, \(\forall t\in\overline{0,n}\).

Așadar, sistemul poate fi rezolvat folosind metodele descrise în capitolele anterioare.

În urma rezolvării sistemului, se vor obține valorile \(a_0,a_1,\dots,a_n\) aferente polinomului \(P_n\). Această metodă poartă denumirea de interpolare Vandermonde; suplimentar, matricea din partea stângă a sistemului se numește matrice Vandermonde.

Vizualizare#

Voi ilustra această metodă de interpolare (precum și problemele care apar când este utilizată în practică) folosind următoarea funcție:

\[ f(x)=\frac{\cot x}{1+64\left(x-1\right)^{2}} \]

Să considerăm că suntem interesați numai de valori din intervalul \([0.1, 1.6]\). Vom ilustra cazul în care alegem o interpolare cu \(4\), \(7\) și \(9\) puncte echidistante:

Graficul funcției \(f(x)\)

Interpolările cu \(4\), \(7\) și \(9\) puncte

Graficul din dreapta se formează evaluând punctele \((x_k,y_k)=\left(x_k,f(x_k)\right)\), unde \(k\in\overline{0,n}\), cu \(n+1\) ales drept \(4\), \(7\), respectiv \(9\), iar apoi interpolând Vandermonde această mulțime.

Spre exemplu, dacă \(n+1=4\), valorile \(x_k\) echidistante din intervalul \([0.1, 1.6]\) sunt \(x_0=0.1\), \(x_1=0.6\), \(x_2=1.1\), și \(x_3=1.6\).

Evaluând funcția în aceste puncte, se obțin valorile \(y_0\approx0.1886\), \(y_1\approx0.13\), \(y_2\approx0.3103\) și \(y_3\approx-0.0012\).

Sistemul Vandermonde \(4\times4\) este, în principiu:

\[ \begin{bmatrix} 1 & x_0 & x_0^2 & x_0^3\\ 1 & x_1 & x_1^2 & x_1^3\\ 1 & x_2 & x_2^2 & x_2^3\\ 1 & x_3 & x_3^2 & x_3^3\\ \end{bmatrix}\begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{bmatrix}=\begin{bmatrix} y_0 \\ y_1 \\ y_2 \\ y_3 \end{bmatrix} \]

Înlocuind valorile cu cele calculate anterior, obținem:

\[ \begin{bmatrix} 1 & 0.1 & 0.01 & 0.001\\ 1 & 0.6 & 0.36 & 0.216\\ 1 & 1.1 & 1.21 & 1.331\\ 1 & 1.6 & 2.56 & 4.096\\ \end{bmatrix}\begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{bmatrix}\approx\begin{bmatrix} 0.1886 \\ 0.13 \\ 0.3103 \\ -0.0012 \end{bmatrix} \]

Acest sistem poate fi rezolvat ușor - oprim explicația aici.

După cum se poate observa, interpolarea cu mai multe puncte se va apropia din ce în ce mai mult de funcția inițială. În teorie, ducând numărul de puncte către infinit, se va obține chiar funcția \(f(x)\).

Cu toate acestea, natura oscilantă a polinomului va începe să creeze probleme! Observați cum funcția obținută prin interpolarea a doar \(9\) puncte se tot sucește, mai ales în partea dreaptă a graficului, trecând de la o valoare negativă către una pozitivă într-un timp (echivalent \(\Delta x\)) foarte scurt.

Cod ilustrativ#

Interpolarea Vandermonde (funcția vander) folosește:

x - abscisele punctelor din mulțimea \(M\);
y - ordonatele punctelor din mulțimea \(M\).

Funcția returnează un polinom de interpolare, pol. În acest context, funcția se poate implementa astfel:

function pol = vander(x, y)
    n = length(x);
    A = zeros(n);
    A(1:n, 1) = 1;
    for i = [1 : n]
        for j = [1 : n]
            A(i, j) = x(i) .^ (j - 1);
        end
    end
    pol = linsolve(A, y');
end

Concluzii#

Deși acesta este cel mai ușor de înțeles algoritm de interpolare, el are dezavantajul instabilității numerice (din cauza inversării matricelor sau a rezolvării de sisteme liniare mari), motiv pentru care este folosit numai pentru mulțimi de puncte ce conțin foarte puține valori (maximum 10-20 puncte).

Licență#

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