Newton, interpolazione di

Enciclopedia della Matematica (2013)

Newton, interpolazione di


Newton, interpolazione di metodo numerico di approssimazione di una funzione nel suo andamento generale mediante particolari polinomi interpolatori (si vedano anche le voci interpolazione; approssimazione (di una funzione)). Esso appartiene pertanto alla famiglia dei metodi di approssimazione a carattere globale, a differenza di altri metodi che permettono di calcolare il valore approssimato di una funzione in un intorno di un punto prefissato e che, quindi, hanno un carattere di approssimazione locale (per esempio, lo sviluppo in serie di Taylor di una funzione in un punto). In particolare, l’interpolazione di Newton è un metodo di interpolazione polinomiale che determina l’unica funzione polinomiale di grado n, detta polinomio interpolatore, passante per gli n + 1 punti (detti poli, o nodi) di una funzione ƒ(x). La funzione polinomiale interpolatrice di grado n è del tipo:

formula

Per calcolare i coefficienti bi si introducono le differenze divise ( differenze finite), utilizzando i poli x0, x1, ..., xn (si suppone che gli n + 1 poli siano distinti). Con la notazione ƒk[xi, ..., xi+k] si indica la differenza divisa di ordine k relativa ai poli xi, ..., xi+k. La costruzione delle differenze divise è ricorsiva: infatti per definizione la prima differenza divisa tra x0 e x1 è

formula

la seconda differenza divisa è

formula

la terza differenza divisa è

formula

e così via.

Le formule per le differenze divise sono in qualche misura simili a quelle del calcolo infinitesimale e possono essere usate per approssimare le derivate; valgono inoltre le seguenti proprietà per le differenze divise di ordine n:

• sono nulle se la funzione è costante;

• godono della proprietà di linearità:

formula

con c1, c2 due costanti;

• sono invarianti per permutazioni dei loro argomenti.

La più semplice procedura di interpolazione consiste nell’unire due soli punti con una retta; l’uguaglianza tra i coefficienti angolari delle rispettive direzioni tra i punti (x0, ƒ(x0)) e (x, ƒ(x)) e tra i punti (x0, ƒ(x0)) e (x1, ƒ(x1))

formula

permette di ricavare i coefficienti del polinomio interpolatore di Newton del primo ordine:

formula

Si ottiene così una formula per l’interpolazione lineare, essendo in questo caso il polinomio di Newton di primo grado. Il coefficiente b0 è uguale a ƒ(x0) e il coefficiente b1 è la prima differenza divisa tra x1 e x0.

Generalmente l’interpolazione è tanto più precisa quanto minore è la distanza tra due punti. Per esempio, se si vuole valutare, tramite l’interpolazione lineare, il valore di ln2, utilizzando come estremi i valori x0 = 1 e x1 = 5, sapendo che ln1 = 0 e ln5 ≅ 1,609438, si sviluppa il polinomio interpolatore

formula

ottenendo un valore approssimato (interpolato) di ln2. Si può notare che il valore di ln2 ottenuto utilizzando una calcolatrice scientifica (che consideriamo come valore “esatto” di ln5) è 0,693147, per cui l’errore relativo commesso dall’approssimazione effettuata con la precedente interpolazione è

formula

Se invece dell’estremo (5, ln5) si considera l’estremo (3, ln3), cioè se si prendono due punti più vicini, il risultato

formula

è più vicino al valore ottenuto con la calcolatrice; in questo caso l’errore relativo è:

formula

L’interpolazione lineare è tuttavia poco precisa e può portare a errori consistenti, poiché si basa sull’approssimazione di una linea generalmente curva con un segmento. Una funzione interpolatrice non lineare può dare stime migliori. Se sono noti tre punti della funzione che si vuole interpolare, si può costruire un polinomio di Newton del secondo ordine:

formula

Come nel caso dell’interpolazione lineare, b1 rappresenta l’inclinazione della retta che congiunge i punti di rispettive ascisse x0 e x1. I primi due termini del polinomio di Newton del secondo ordine equivalgono quindi a un’interpolazione lineare. L’ultimo termine b2(xx0)(xx1) introduce in più una curvatura di secondo grado. In particolare, la seconda differenza b2 rappresenta proprio la concavità della parabola che approssima la curva. Riprendendo l’esempio precedente, si può calcolare un valore approssimato di ln2 utilizzando il polinomio interpolatore per i tre punti P0(1, 0), P1(3, 1,098612), P2(5, 1,609438), essendo 1,098612 e 1,609438 rispettivamente valori attendibili di ln3 e ln5 (qui assunti come esatti). Sostituendo il valore delle differenze divise prime ƒ1[1, 3] = 0,549306, ƒ1[3, 5] = 0,255413, e la differenza divisa seconda ƒ2[1, 3, 5] = −0,073473, il polinomio interpolatore risulta

formula

Per x = 2 si ottiene p2(2) = 0,622779 con errore relativo del 10% circa.

Il metodo di interpolazione di Newton viene generalizzato considerando la funzione polinomiale interpolante di ordine ennesimo:

formula

Va sottolineato che non è necessario che i punti utilizzati per l’interpolazione siano equidistanti né che le loro ascisse siano in ordine crescente. L’espressione del polinomio di Newton richiama quella del polinomio di Taylor. In entrambi i casi l’aggiunta di nuovi termini consente di migliorare l’approssimazione: i coefficienti del polinomio di Newton sono, infatti, differenze finite divise che rappresentano approssimazioni delle derivate di ordine superiore. Come nello sviluppo di Taylor, se la funzione da approssimare è un polinomio di grado n, la formula di Newton di ordine n-esimo, basata su n + 1 punti, dà un’approssimazione priva di errore. L’errore, altrimenti detto resto, nell’interpolazione con il polinomio di Newton è definito come la differenza tra funzione da interpolare e polinomio interpolante: e(x) = ƒ(x) − p(x). Si può dimostrare che la sua espressione è:

formula

dove ƒ[x0, x1, ..., xn−1, xn, X] è la differenza finita divisa di ordine n + 1. Essa contiene però l’incognita ƒ(x) e non può essere ancora utilizzata per calcolare l’errore; se però si dispone di un ulteriore punto ƒ(xn+1) diventa possibile effettuarne una stima:

formula

I vantaggi dell’interpolazione con il polinomio di Newton si possono così riassumere: a) il polinomio di Newton di ordine n + 1 si costruisce facilmente aggiungendo un termine al polinomio di ordine n; quindi se non è stabilito a priori l’ordine del polinomio interpolatore, si possono aggiungere termini ottenendo un grado di precisione ottimale, minimizzando l’errore, e si può determinare quando l’aggiunta di nuovi termini non migliora significativamente la stima; b) anche le differenze divise si calcolano utilizzando un metodo iterativo, poiché quelle di ordine inferiore si utilizzano per calcolare quelle di ordine superiore; c) la stima dell’errore è espressa in termini di differenze divise e quindi si effettua utilizzando le differenze già calcolate per lo sviluppo del polinomio interpolatore.

Infine, nel caso di intervallo costante h tra i valori xi le differenze divise si riducono ai soli numeratori e in tal caso il polinomio di Newton assume la forma:

formula

dove yn = ƒ(xn) e

formula
TAG

Calcolatrice scientifica

Calcolo infinitesimale

Polinomio di → taylor

Metodo iterativo

Permutazioni