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)!}}*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\neq x$. Introduciamo la funzione ausiliaria

$g(t)=E(t)-{\frac {w_{n+1}(t)}{w_{n+1}(x)}}*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)}}*E(x)=0$

e $g(x_{i})=0\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)}}*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'(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)}}*E(x)$

$=f^{(n+1)}(\xi )-{\frac {n!}{w_{n+1}(x)}}*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)!}}*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\neq 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]*(t-x_{0})*(t-x_{1})*\dots *(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]*(x-x_{0})*(x-x_{1})*\dots *(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 $\max _{[a,b]}|f(x)|$. Vogliamo studiare l'errore di interpolazione $E_{n}$ per $n\to \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)=\vert f-p_{n}\vert$.

Confronto $E_{n}$ con l'errore di migliore approssimazione $E_{n}^{*}(f)$, cioè $E_{n}^{*}(f)=\vert f-P_{n}^{*}\vert$ dove $P_{n}^{*}$ è tale che $\vert f-P_{n}^{*}\vert \leq \vert f-Q\vert$ per ogni $Q$ polinomio di grado $n$.

$P_{n}^{*}$ non passa necessariamente dai nodi. Sappiamo per il teorema di Iston-Weierstrass che $E_{n}\to 0$ per $n\to \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)\leq E_{n}^{*}(f)*(1+\Lambda _{n,X})$

dove

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

dove $L_{j,n}$ è il $j$-esimo polinomio di Lagrange di grado $n$ ($\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}^{*}(y)-P_{n}^{*}(y)|$

$\leq |f(y)-P_{n}^{*}(y)|+|P_{n}^{*}(y)-P_{n}(y)|$

La differenza tra il polinomio di miglior approssimazione e la funzione può essere maggiorata con $E_{n}^{*}$, quindi

$\leq E_{n}^{*}(f)+|P_{n}^{*}(y)-P_{n}(y)|$

Argomento di proiezione: $P_{n}^{*}(f)(y)=P_{n}(P_{n}^{*}(f))(y)$ (infatti il polinomio interpolante di un polinomio è il polinomio stesso), e sostituendo:

$\leq E_{n}^{*}(f)+|P_{n}(P_{n}^{*}(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

$\leq E_{n}^{*}(f)+|P_{n}(P_{n}^{*}-f)(y)|$

e scrivendo il polinomio interpolante in forma di Lagrange:

$=E_{n}^{*}(f)+|\sum _{j=0}^{n}(f-P_{n}^{*})(x_{j}^{n})L_{j,n}(y)|$

con la disuguaglianza triangolare

$\leq E_{n}^{*}(f)+\sum {j=0}^{n}|f-p_{n}^{*}(f)|(x_{j}^{n})*|L_{j,n}|(y)$

e maggiorando $(P_{n}^{*}-f)(x_{j}^{n})$ con $E_{n}^{*}(f)$ che è il massimo sull'intervallo:

$\leq E_{n}^{*}(f)+\sum {j=0}^{n}E_{n}^{*}(f)*|L_{j,n}|(y)$

e portando $E_{n}$ fuori dalla sommatoria

$\leq E_{n}^{*}(f)*(1+\sum {j=0}^{n}|L_{j,n}|(y))$

$\leq E_{n}*(1+\lambda _{n})$

dove $\Lambda$ è come definito sopra.

Nodi di Chebyshev

Esiste una matrice $X^{*}$ che minimizza la costante di Lebesgue $\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^{*}$ a meno di termini di ordine inferiore.

Definizione

Chiamiamo polinomio di Chebyshev di grado $m$, $P_{m}(x)$ il polinomio definito come $\cos(m*\arccos x)$.

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

$\Lambda _{n}(x)>2/\pi \log(+1)-c$, e quindi $\lambda _{n}(x)\to \infty$ per $n\to \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 \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 ${\bar {f}}(x_{i})$ siano le perturbazioni di $f(x_{i})$, chiamiamo ${\bar {p}}_{n}(x)$ il polinomio interpolante rispetto ai valori perturbati. Vale che

$\vert p_{n}(x)-{\bar {p}}_{n}(x)\vert =\max _{x\in [a,b]}|\sum _{i=0}^{n}(f(x_{i})-{\bar {f}}(x_{i}))*L_{i}(x)|$

e per la disuguaglianza triangolare

$=\max \sum _{i}|f(x_{i})-{\bar {f}}(x_{i})|*|L_{i}(x)|$

$\leq \sum _{i=0}^{n}|f(x_{i})-{\bar {f}}(x_{i})|*\max _{x\in [a,b]}\sum _{i=0}^{n}|L_{i}(x)|$

$=\sum _{i=0}^{n}|f(x_{i})-{\bar {f}}(x_{i})|*\Lambda (X)$

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

$\Lambda _{n}(x)$ cresce all'aumentare di $n$, e vale il seguente risultato: se consideriamo nodi equispaziati, $\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.