1

Algoritmi e dintorni:

Polinomio interpolatore di Lagrange Prof. Ettore Limoli

Formula di interpolazione Si voglia determinare il polinomio di grado N passante per gli N+1 punti:

(x0, y0); (x1, y1) … (xN, yN).

Un modo potrebbe essere quello di scrivere la generica equazione di un polinomio di grado N e imporre il

passaggio per gli N+1 punti. Si otterrebbe un sistema lineare di N+1 equazioni in N+1 incognite.

Questo metodo, tuttavia, è poco conveniente perché non è agevole risolvere un sistema molto grosso per

valori di N elevati. Un altro problema in cui si può incorrere è quello dei sistemi mal condizionati, ossia quei

sistemi che ad una minima variazione dei coefficienti determinano soluzioni profondamente diverse.

La cosa più conveniente è usare la formula di Lagrange per determinare questo polinomio.

𝑃(𝑥) = 𝑦0 ∙(𝑥−𝑥1)∙(𝑥−𝑥2) ∙⋯ (𝑥−𝑥𝑁)

(𝑥0−𝑥1)∙(𝑥0−𝑥2)⋯(𝑥0−𝑥𝑁)+ 𝑦1 ∙

(𝑥−𝑥0)∙(𝑥−𝑥2) ∙⋯ (𝑥−𝑥𝑁)

(𝑥1−𝑥0)∙(𝑥1−𝑥2)⋯(𝑥1−𝑥𝑁)+ ⋯ + 𝑦𝑁 ∙

(𝑥−𝑥0)∙(𝑥−𝑥1) ∙⋯ (𝑥−𝑥𝑁−1)

(𝑥𝑁−𝑥0)∙(𝑥𝑁−𝑥1)⋯(𝑥𝑁−𝑥𝑁−1)

Questa formula può essere sintetizzata come segue:

𝑃(𝑥) = ∑ 𝑦𝑗 ∙ 𝐿𝑗(𝑥)

𝑁

𝑗=0

Dove si è posto, per ogni j = 0, 1, …, N:

𝐿𝑗(𝑥) = ∏𝑥 − 𝑥𝑖

𝑥𝑗 − 𝑥𝑖

𝑁

𝑖=0𝑖≠𝑗

Si verifica subito che, per k = 0, 1, …, N : L j (x k) = j k . Dove j k è il delta di Kronecker, così definito:

𝛿𝑗 𝑘 = {1 𝑝𝑒𝑟 𝑗 = 𝑘0 𝑝𝑒𝑟 𝑗 ≠ 𝑘

Uso di Excel Per quanto la formula di Lagrange sia più pratica da usare rispetto alla risoluzione di un grosso sistema, per

N grande il calcolo diventa un po’ gravoso. Conviene utilizzare opportuni strumenti di calcolo. Tuttavia il

foglio elettronico di calcolo non dispone di una funzione specifica, è opportuno crearla in VBA.

Option Explicit Public Function Lagrange(x, dati) As Double Dim Somma, prodotto As Double Dim RigaIniz, RigaFin As Long Dim ColonnaIniz, ColonnaFin As Long

2

Dim i, j As Long Dim Celle As Range Set Celle = dati RigaIniz = Celle.Row RigaFin = Celle.Rows(Celle.Rows.Count).Row ColonnaIniz = Celle.Column ColonnaFin = Celle.Columns(Celle.Columns.Count).Column Somma = 0 For j = RigaIniz To RigaFin prodotto = 1 For i = RigaIniz To RigaFin If j <> i Then prodotto = prodotto * (x - Cells(i, ColonnaIniz).Value) / (Cells(j, ColonnaIniz).Value - Cells(i, ColonnaIniz).Value) End If Next i Somma = Somma + prodotto * Cells(j, ColonnaFin).Value Next j Lagrange = Somma End Function

Alla function vengono passate due variabili: x, contenente il valore in cui calcolare il polinomio di Lagrange e

dati contenente la tabella da interpolare secondo lo schema: prima colonna contiene i valori x, seconda

colonna i valori y.

Per semplicità di trattazione, la function non contiene controlli sull’imput dei dati, è quindi necessario

essere accorti nell’uso e non commettere errori o scrivere diversamente la tabella.

Le istruzioni seguenti consentono una lettura diretta delle celle del foglio elettronico. Per semplicità non

sono dati riferimenti al file, al foglio in uso e quindi il riferimento è quello attivo. Ciò comporta che non

posso fare riferimento a più fogli contemporaneamente.

Set Celle = dati Impone che la variabile Celle, di tipo Range, assuma i valori della variabile dati di tipo Variant (sottinteso).

Le seguenti istruzioni determinano e memorizzano, in opportune variabili, la riga iniziale, la riga finale, la

colonna iniziale e la colonna finale relativi al range “Celle”.

RigaIniz = Celle.Row RigaFin = Celle.Rows(Celle.Rows.Count).Row ColonnaIniz = Celle.Column ColonnaFin = Celle.Columns(Celle.Columns.Count).Column ColonnaIniz conterrà i valori delle x. ColonnaFin quella dei dati y. I vari dati saranno compresi fra RigaIniz e

RigaFin.

3

Il ciclo FOR esterno, di indice j, realizza il sommatore. Il ciclo interno, di indice i, il produttore. Tramite le

istruzioni del tipo : Cells(r, c).Value , si determina il valore del contenuto della cella posta nella r-esima riga

e alla c-esima colonna relativamente al range attivo.

Vediamo ora un semplice uso della function ora descritta.

In questa esempio si vede una sequenza numerica da continuare. La matrice dei dati è in giallo. Si vede

pure la formula introdotta nella cella [ E4 ]. La matrice dei dati è passata come indirizzo assoluto in modo

che non cambi quando si copia questa cella nelle celle sottostanti. Così, ad esempio, in [ E8 ] leggiamo:

Esempi di uso Forniamo ora un paio di esempi di utilizzo del polinomio interpolatore di Lagrange.

In questo esempio la tabella, presa da una rivista specializzata, riporta i consumi di un’auto in

corrispondenza di alcune velocità. Col calcolo si espande la tabella interpolando ed estrapolando i dati.

4

Dalla tabella calcolata si è pure ricavato il grafico del consumo istantaneo in funzione della velocità.

Un ultimo esempio è dato dalla creazione di una tabella di conversione dei punteggi delle prove scritte agli

esami di stato (maturità) in voti decimali.

La tabella dei dati (in giallo) ci dà i punti di corrispondenza assegnati dalla normativa degli esami.

In questo caso abbiamo solo interpolazione.

Prof. Ettore Limoli