L’interpolazione costruisce una funzione che passa esattamente per un insieme di punti dati (x_i, y_i). L’approssimazione cerca la funzione più vicina ai dati in qualche senso (ad es. minimi quadrati).
Interpolazione di Newton con Differenze Divise
Le differenze divise f[x_0, \ldots, x_k] si calcolano ricorsivamente: f[x_i] = f(x_i), \qquad f[x_i, \ldots, x_k] = \frac{f[x_{i+1},\ldots,x_k] - f[x_i,\ldots,x_{k-1}]}{x_k - x_i}
Il polinomio interpolante di Newton è: p_n(x) = f[x_0] + f[x_0,x_1](x-x_0) + \cdots + f[x_0,\ldots,x_n]\prod_{i=0}^{n-1}(x-x_i)
Vantaggio rispetto a Lagrange: si aggiunge facilmente un nuovo nodo senza ricalcolare tutto.
Errore di Interpolazione
Per f \in C^{n+1}[a,b]: f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n(x - x_i)
per qualche \xi nell’intervallo più piccolo contenente x, x_0, \ldots, x_n.
Fenomeno di Runge e Nodi di Chebyshev
Con nodi equispaziati su [-1,1], aumentare il grado n può peggiorare l’approssimazione per funzioni come f(x) = 1/(1+25x^2) (fenomeno di Runge).
I nodi di Chebyshev minimizzano il fattore \prod(x-x_i): x_i = \cos\!\left(\frac{2i+1}{2(n+1)}\pi\right), \quad i = 0, \ldots, n
Spline Cubiche
Le spline cubiche interpolano i dati con polinomi di grado 3 su ciascun intervallo, raccordati con continuità di f, f' e f''. Evitano le oscillazioni di Runge e sono standard nel CAD e nella computer grafica.
Approssimazione ai Minimi Quadrati
Con più dati che parametri, si minimizza \sum_i (f(x_i) - y_i)^2. Per l’approssimazione lineare ciò porta al sistema normale A^T A \mathbf{c} = A^T \mathbf{y}.