Interpolazione polinomiale

Si immagini di disporre di:

$$(x_i,y_i), \quad i = 0,\dots,n \quad y = f(x_i)$$

Si vuole ricercare un cosiddetto polinomio interpolatore $\phi_n \in \Pi_n$ interpolante la $f(x)$ sulle ascisse $x_i \in [a,b]$, $x_i < x_j$ se $i < j, \ x_i \ne x_j$ se $i \ne j$, tale che:

$$\phi(x) \in \Pi_n \quad \phi(x_i) = f(x_i) \quad i = 0 \dots n$$

Teorema 4.1 (Esistenza di un unico polinomio interpolatore)   Per ogni insieme di coppie $(x_i,\,y_i),\,\,i = 0,\,1,\,\dots,\,n$, con nodi $x_i$ distinti fra loro, $\exists ! \,\, \phi_n \in \Pi_n$ tale che

$$\phi_n(x_i) = y_i, \quad i = 0,\, \dots,\,n$$

$&sstarf#star;$ Dimostrazione 4.1 (Unicità del polinomio interpolatore)   Si supponga per assurdo che che esistano due polinomi $p, q$ di grado $n$, entrambi interpolatori per i punti $(x_i,\,y_i),\,\,i = 0,\,1,\,\dots,\,n$. Allora,

$$p(x_i) = q(x_i), \quad i = 0,\,1,\,\dots,\,n$$

Per il teorema fondamentale dell'algebra $p$ e $q$ hanno esattamente $n$ zeri complessi e al più $n$ zeri reali.

Si consideri il polinomio $r$ differenza tra i due:

$$r(x) = p(x) - q(x)$$

$r(x)$ è di grado $n$, in quanto differenza di due polinomi di grado $n$, e ha $n+1$ zeri, poichè

$$r(x_i) = p(x_i) - q(x_i) = y_i - y_i = 0, \quad i = 0,\,\dots,\,n$$

Ma per il teorema fondamentale $r(x)$ non può esistere, dunque:

$$r(x) = p(x) - q(x) = 0 \quad \implies \quad p(x) = q(x)$$

$\qedsymbol$

$&sstarf#star;$ Dimostrazione 4.2 (Esistenza del polinomio interpolatore)   Si dimostra l'esistenza di tale polinomio mostrando che è sempre possibile costruirne uno.

Il polinomio interpolatore è nella forma:

$$\phi_n(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n$$

Le condizioni di interpolazione sono rappresentabili da un sistema di $n+1$ equazioni (una per ogni campione) e $n+1$ incognite $a_0,\,\dots a_n$, che costituiscono i coefficienti del polinomio.

$$\left\{ \begin{array}{l} \phi_n(x_0) = a_0 + a_1 x_0 + \dots a_... ... \phi_n(x_n) = a_0 + a_1 x_n + \dots a_n x_n^n = y_n \\ \end{array} \right.$$

Il sistema è nella forma $Ax = b$, con $A$ matrice di Vandermonde:

Definizione 4.6 (Matrice di Vandermonde)   Una matrice di Vandermonde è una matrice in cui gli elementi delle righe costituiscono una progressione geometrica, ovvero:

$$V_{i,j} = \alpha_i^{j-1} \qquad V = \begin{pmatrix} 1 & \alpha_1 ... ...\vdots \\ 1 & \alpha_m & \alpha_m^2 & \dots & \alpha_m^{n-1} \\ \end{pmatrix}$$

Il determinante di $A$ può essere espresso come:

$$\det A = \prod_{0 \leq i < j \leq n} (x_j - x_i)$$

Se $\det A = 0$, la matrice è singolare e ha infinite soluzioni. Per ipotesi, però, i nodi $x_i$ sono distinti tra loro, quindi $\det A \neq 0$, la matrice è invertibile e il sistema ammette soluzione unica $x = A^{-1}b$.

$\qedsymbol$

Dimostrazione 4.2   Un'ulteriore dimostrazione di esistenza consiste nel costruire il polinomio nella cosiddetta forma di Lagrange. Siano $\varphi_i(x) \in \Pi_n$ polinomi definiti come segue:

$$\varphi_i(x) = \prod_{j = 0,\,j \neq i}^{n} \frac{(x - x_j)}{(x_i - x_j)}$$

Tali particolari polinomi sono definiti polinomi caratteristici di Lagrange. Si noti che il loro comportamento è analogo al delta di Kronecker $\delta_{ij}$:

$$\varphi_i(x_j) = \delta_{ij} = \begin{cases} 1& \text{se $i = j$} \\ 0& \text{se $i \neq j$} \end{cases}$$

Dai polinomi $\varphi_i(x)$ si ottiene $\phi_n(x)$ per sovrapposizione degli effetti:

$$\phi_n(x) = \sum_{i = 0}^{n} y_i \, \varphi_i(x)$$

Tale polinomio soddisfa le condizioni di interpolarizzazione ed è pertanto un polinomio interpolatore, espresso in forma di Lagrange.

Definizione 4.7 (Errore di interpolazione)   Si chiama errore di interpolazione $E_n(x)$ la distanza tra una funzione $f$ e il polinomio interpolatore $\pi_n$ al passo $n$:

$$E_n(x) = \mathit{dist}(f,\,\Pi_n) = \max \, \{ \, \vert\pi_n(x) - f(x)\vert,\quad \forall x \in [a,\,b] \, \}$$

Teorema 4.2   Sia $I$ un intervallo limitato e siano $\{x_i : i = 0, \ldots, n\}$ nodi di interpolazione distinti in $I$. Sia $f \in \mathcal{C}^{n+1} [a,\,b]$ in $I$. Allora $\forall x \in I : (\exists\ \xi \in I)$ t.c.

$$E_n = f(x) - \Pi_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \, (x - x_0)(x - x_1) \dots (x - x_n)$$ (3)

Tale espressione rappresenta l'errore di interpolazione di ordine $n$ nella forma di Lagrange.

Dimostrazione 4.3   Si vuole dimostrare la (3) per ogni $x \in [a,\,b]$. Se $x = x_i,\;i=0,\,\dots,\,n$, la tesi è triviale.

$$f(x_i) - \Pi_n(x_i) = 0 \Leftrightarrow f(x_i) = \Pi_n(x_i)$$   per definizione di$$\; \Pi_n$$

$$\frac{f^{(n+1)}(\xi)}{(n+1)!} \, (x_i - x_0) \dots \underbrace{(x_i - x_i)}_{0} \dots (x_i - x_n) = 0$$

Sia $x \notin \{x_0,\,\dots,\,x_n\}$ fissato, e sia $z \in [a,\,b]$. Definiamo $G(z)$ come:

$$G(z) = E_n(z) - \omega(z) \; \frac{E_n(x)}{\omega(x)}$$

dove

$$\omega(z) = \prod_{i = 0}^{n} (x - x_i)$$

Si ricordi allora il teorema di Rolle:

Teorema 4.3 (Teorema di Rolle)   Sia $f$ continua in $[a,\,b]$ e derivabile in $(a,\,b)$ tale che $f(a) = f(b)$. Allora, $\exists \, c \in (a,\,b)$ tale che

$$f'(c) = 0$$

I nodi $x_i$ e $x$ suddividono l'intervallo $[a,\,b]$ in $n+1$ intervalli, dove G(z) si annulla trivialmente. Allora, per il teorema di Rolle, in ogni intervallo $i$-esimo $\exists \, z_{1,\,i} : G'(z_{1,\,i}) = 0$. Analogamente, i punti $z_{1,\,i}$ suddividono l'intervallo $\mathrm{int}\,(z_{1,\,0},\,z_{1,\,1},\,\dots,\,z_{1,\,n})$ in $n$ intervalli dove $G''(z_{2,\,i}) = 0$. Reiterando Rolle, si ottiene:

$$\exists \, \xi : G^{(n+1)}(\xi) = 0$$

Per la linearità dell'operatore di derivazione, si ha:

$$G^{(n+1)}(z) = \mathcal{D}^{n+1} \left( f(z) - \Pi_n(z) \right) - \frac{E_n(x)}{\omega(x)} \mathcal{D}^{n+1}\left( \omega(z) \right)$$

$$= f^{(n+1)}(z) - \Pi_n^{(n+1)}(z) - \frac{E_n(x)}{\omega(x)} \; \omega^{(n+1)}(z)$$

$\Pi_n(z)$ ha grado $n$, pertanto $\Pi_n^{(n+1)}(z) = 0$. $\omega(z)$ ha termine di grado massimo $z^{n+1}$, quindi $\omega^{(n+1)}(z) = (n+1)!$. Quindi, si ha

$$\underbrace{G^{(n+1)}(\xi)}_{0} = f^{(n+1)}(\xi) - \frac{E_n(x)}{\omega(x)} \; (n+1)!$$

$$E_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \; \prod_{i = 0}^{n} (x - x_i)$$

$\qedsymbol$

Lemma 4.2 (Maggiorazione dell'errore)  

$$\begin{split}E_n = \abs{f(x) - \Pi_n(x)}& = \abs{f^{(n+1)}(\xi)} ... ...frac{(b-a)^{n+1}}{(n+1)!}\\ & = M_{n+1} \frac{(b-a)^{n+1}}{(n+1)!} \end{split}$$

Dove $M_{n+1}$ è la massima derivata $n+1$-esima.

Lemma 4.3 (Convergenza)   Poichè

$$\lim_{n \to \infty} \frac{(b-a)^{n+1}}{(n+1)!} = 0$$

Se $\exists M : M_n \leq M$

$$\lim_{n\to \infty} E_n(x) \leq \lim_{n\to \infty} M \frac{(b-a)^{n+1}}{(n+1)!} = 0$$

Esempio 4.1   Si consideri $f(x) = e^x$. Si ha che

$$M_{n+1} = \max_{x \in [a,b]} \abs{f^{(n+1)}(x)} \leq e^b$$

$M_{n+1}$ è limitata dalla costante $e^b$, pertanto $E_n(x) \to 0$. Tale stima vale per ogni distribuzione dei nodi.

Lemma 4.4   Come si può dimostrare, in caso di distribuzione esclusivamente equidistante, l'errore è inoltre maggiorabile come segue:

$$\vert E_n(x)\vert \leq M_{n+1} \; \frac{h^{n+1}}{4\,(n+1)} \qquad h = \frac{b-a}{n}$$

Lemma 4.5   In generale, con l'interpolazione polinomiale, non c'è convergenza uniforme (neppure convergenza puntuale).

Dimostrazione 4.4 (Esempio di Runge)   Il cosiddetto esempio di Runge vale come controesempio di 4.5.

Sia $f(x) = \frac{1}{1+x^2}$ e $f \in C^\infty$

Eseguiamo un campionamento a passo costante, ovvero prendiamo dei punti equispaziati tra loro. Notiamo che più aumentiamo di grado il nostro polinomio interpolatore più le oscillazioni agli estremi aumentano. Questo problema è dovuto alla scelta di campionamento a passo costante. Sicuramente non c'è convergenza uniforme e, vicino agli estremi non c'è neppure quella puntuale.