Calcolo numerico/Stabilità condizionamento e convergenza

Errore analitico

Teorema 5.4

Sia $I_x$ il più piccolo intervallo che contiene i nodi di interpolazione, e supponiamo che contenga anche il punto $x$ in cui vogliamo valutare l'errore. Supponiamo che $F\in C_{n+1}(I_x)$. Allora esiste $\xi \in I_x$ tale che

$E_x=|f(x)-p_n(x)|=\frac{f^{(n+1)}(\xi )}{(n+1)!}\ast w_{n+1}(x)$

(analogia con la formula di Taylor, centrata però in tutti gli $x_i$)

Dimostrazione

Se $x$ è un nodo di interpolazione, allora $E_0=0$.

Altrimenti, supponiamo di considerare $t\in I_x$, $t\ne x$. Introduciamo la funzione ausiliaria

$g(t)=E(t)-\frac{w_{n+1}(t)}{w_{n+1}(x)}\ast E(x)$

di classe $C_{n+1}(I_x)$.

Osserviamo che valutando $g$ in uno dei nodi di interpolazione $x_i$, siccome $w_{n+1}(x_i)=0$ e $E(x_i)=0$ si ha:

$g(x_i)=E(x_i)-\frac{w_{n+1}(x_i)}{w_{n+1}(x)}\ast E(x)=0$

e $g(x_i)=0\mathrm{\forall }i=1,\dots ,n$.

Valutando $g$ nel nodo $x$ si ha:

$g(x)=E(x)-\frac{w_{n+1}(x)}{w_{n+1}(x)}\ast E(x)=E(x)-E(x)=0$

quindi la funzione si annulla in $n+2$ nodi, gli $x_i$ e $v$.

Per il teorema di Rolle: $g^{\prime }(t)$ si annulla in $n+1$ punti, e $g^{(n+1)}(t)$ si annulla in un punto $\xi \in I_x$.

$g^{(n+1)}(\xi )=E^{(n+1)}(\xi )-\frac{w_{n+1}^{(n+1)}(t)}{w_{n+1}(x)}\ast E(x)$

$=f^{(n+1)}(\xi )-\frac{n!}{w_{n+1}(x)}\ast E(x)$

e siccome $g^{(n+1)}(\xi )=0$ per il teorema di Rolle, si ha

$E(x)=\frac{f^{(n+1)}(\xi )}{(n+1)!}\ast w_{n+1}(x)$

Rappresentiamo $I_x$ usando le differenze divise. Chiamiamo $E_n(f)(x)$ l'errore dell'approssimazione di $f(x)$ con $P_n$. Sia $P_n(t)$ il polinomio interpolante. Sia $x\ne x_i$, considerato come nuovo nodo di interpolazione.

Scriviamo il polinomio interpolante nei nodi $x_i$, con $i=0,\dots ,n+1$. Aumento di 1 il grado del polinomio interpolante

$p_{n+1}(t)=p_n(t)+f[x_0,\dots ,x_n,x]\ast (t-x_0)\ast (t-x_1)\ast \dots \ast (t-x_n)$

Siccome $f(x)=p_{n+1}(x)$ per la formula di Newton, ricavo che

$E_n(f)(x)=f(x)-p_n(x)=f[x_0,\dots ,x_n,x]\ast (x-x_0)\ast (x-x_1)\ast \dots \ast (x-x_n)$

e se $f\in C_{n+1}(I_x)$, segue che $f[x_0,\dots ,x_n,x]=\frac{f^{(n+1)}(\xi )}{(n+1)!}$.

Convergenza del polinomio interpolante

Sia $f\in C^0(a,b)$, allora possiamo definire la norma infinito di $f$ come max $\underset{[a,b]}{max}|f(x)|$. Vogliamo studiare l'errore di interpolazione $E_n$ per $n\to \mathrm{\infty }$.

Introduco una matrice di interpolazione sull'intervallo $[a,b]$, cioè definisco $X=(x_{ij})$ di dimensione infinita che contiene i nodi di interpolazione, è una matrice triangolare inferiore, che su ogni riga ha i nodi di interpolazione del polinomio che ha come grado l'indice della riga.

Fissati $f,X$, chiamiamo $E_n(f,X)=|f-p_n|$.

Confronto $E_n$ con l'errore di migliore approssimazione $E_n^{\ast }(f)$, cioè $E_n^{\ast }(f)=|f-P_n^{\ast }|$ dove $P_n^{\ast }$ è tale che $|f-P_n^{\ast }|\le |f-Q|$ per ogni $Q$ polinomio di grado $n$.

$P_n^{\ast }$ non passa necessariamente dai nodi. Sappiamo per il teorema di Iston-Weierstrass che $E_n\to 0$ per $n\to \mathrm{\infty }$.

Esiste una relazione tra errore di interpolazione e errore di miglior approssimazione.

Supponiamo di avere una funzione continua su $[a,b]$, e una matrice di interpolazione $i$ su tale intervallo. Vale il seguente risultato.

Teorema 5.5

L'errore di interpolazione

$E_n(f,X)\le E_n^{\ast }(f)\ast (1+{\mathrm{\Lambda }}_{n,X})$

dove

$\mathrm{\Lambda }=|\sum _{j=0}^n|L_{j,n}||$

dove $L_{j,n}$ è il $j$-esimo polinomio di Lagrange di grado $n$ ($\mathrm{\Lambda }$ viene chiamata costante di Lebesgue).

Dimostrazione

Poniamo $P_n=P_n(X,f)$, per ogni $y\in [a,b]$, consideriamo

$|E_y|=|f(y)-P_n(y)|=|f(y)-P_n(y)+P_n^{\ast }(y)-P_n^{\ast }(y)|$

$\le |f(y)-P_n^{\ast }(y)|+|P_n^{\ast }(y)-P_n(y)|$

La differenza tra il polinomio di miglior approssimazione e la funzione può essere maggiorata con $E_n^{\ast }$, quindi

$\le E_n^{\ast }(f)+|P_n^{\ast }(y)-P_n(y)|$

Argomento di proiezione: $P_n^{\ast }(f)(y)=P_n(P_n^{\ast }(f))(y)$ (infatti il polinomio interpolante di un polinomio è il polinomio stesso), e sostituendo:

$\le E_n^{\ast }(f)+|P_n(P_n^{\ast }(y))-P_n(y)|$

Argomento di linearità: la differenza tra polinomi interpolanti di $H_1$ e $H_2$ è il polinomio interpolante della differenza $H_1-H_2$, quindi

$\le E_n^{\ast }(f)+|P_n(P_n^{\ast }-f)(y)|$

e scrivendo il polinomio interpolante in forma di Lagrange:

$=E_n^{\ast }(f)+|\sum _{j=0}^n(f-P_n^{\ast })(x_j^n)L_{j,n}(y)|$

con la disuguaglianza triangolare

$\le E_n^{\ast }(f)+\sum {j=0}^n|f-p_n^{\ast }(f)|(x_j^n)\ast |L_{j,n}|(y)$

e maggiorando $(P_n^{\ast }-f)(x_j^n)$ con $E_n^{\ast }(f)$ che è il massimo sull'intervallo:

$\le E_n^{\ast }(f)+\sum {j=0}^n{E}_n^{\ast }(f)\ast |L_{j,n}|(y)$

e portando $E_n$ fuori dalla sommatoria

$\le E_n^{\ast }(f)\ast (1+\sum {j=0}^n|L_{j,n}|(y))$

$\le E_n\ast (1+{\lambda }_n)$

dove $\mathrm{\Lambda }$ è come definito sopra.

Nodi di Chebyshev

Esiste una matrice $X^{\ast }$ che minimizza la costante di Lebesgue ${\mathrm{\Lambda }}_n(x)$, ma non ne abbiamo la forma esplicita. Si considerano i nodi del polinomio di Chebyshev, che danno la migliore approssimazione di $X^{\ast }$ a meno di termini di ordine inferiore.

Poniamo $\theta =\arccos x$, allora $P_m(\theta )=\cos (m\theta )$, e dobbiamo risolvere $\cos (m\theta )=0$, e questo è vero se

$m\theta =\pi /2+k\pi ,k\in \mathbb{Z}$

quindi gli zeri sono

${\theta }_k=\frac{\pi }{2m}+\frac{k\pi }{m}$

Definiamo

$x_k=\cos {\theta }_k,k=1,\dots ,m-1$

$x_k\in [-1,1]$, sono tutti interni all'intervallo, e hanno la proprietà che si infittiscono verso gli estremi e sono più radi al centro.

$x\in [-1,1]$, consideriamo $z=\alpha x+\beta$, impongo $a=-\alpha +\beta$, $b=\alpha +\beta$, e ricaviamo che $\alpha =(b-a)/2$ e $\beta =(b+a)/2$, quindi i nodi mappati su $(a,b)$ sono $(b+a)/2+x_k(b-a)/2$. In generale, per ogni scelta dei nodi di interpolazione, esiste una costante $c>0$ tale che

${\mathrm{\Lambda }}_n(x)>2/\pi \log (+1)-c$, e quindi ${\lambda }_n(x)\to \mathrm{\infty }$ per $n\to \mathrm{\infty }$.

Teorema 5.6 (teorema di Faber)

Data $X$ matrice di interpolazione sull'intervallo $[a,b]$, esiste almeno una funzione $f$ continua su $[a,b]$ tale che $P_n(X,f)$ non converge uniformemente a $f$ per $n\to \mathrm{\infty }$.

Questo significa che una matrice di interpolazione non va bene per tutte le funzioni.

Funzione di Runge

Consideriamo la funzione di Runge:

$f(x)=\frac{1}{1+x^2}$

L'interpolazione polinomiale di questa funzione con nodi equispaziati non dà buoni risultati. Invece con i nodi di Chebyshev si ottiene un risultato migliore.

Condizionamento

Supponiamo che $\overline{f}(x_i)$ siano le perturbazioni di $f(x_i)$, chiamiamo ${\overline{p}}_n(x)$ il polinomio interpolante rispetto ai valori perturbati. Vale che

$|p_n(x)-{\overline{p}}_n(x)|=\underset{x\in [a,b]}{max}|\sum _{i=0}^n(f(x_i)-\overline{f}(x_i))\ast L_i(x)|$

e per la disuguaglianza triangolare

$=max\sum _i|f(x_i)-\overline{f}(x_i)|\ast |L_i(x)|$

$\le \sum _{i=0}^n|f(x_i)-\overline{f}(x_i)|\ast \underset{x\in [a,b]}{max}\sum _{i=0}^n|L_i(x)|$

$=\sum _{i=0}^n|f(x_i)-\overline{f}(x_i)|\ast \mathrm{\Lambda }(X)$

quindi la costante di Lebesgue può essere interpretata come numero di condizionamento e amplifica la perturbazione sui dati.

${\mathrm{\Lambda }}_n(x)$ cresce all'aumentare di $n$, e vale il seguente risultato: se consideriamo nodi equispaziati, ${\mathrm{\Lambda }}_n=\frac{2^{n+1}}{E_n\log n}$ e si ha una crescita esponenziale. Invece, considerando i nodi di Cevicev, la crescita è solo logaritmica.