Interpolazione polinomiale

Sia ℙ_{n} l’insieme dei polinomi di grado n in ℝ. Date n + 1 coppie (x_{0},y_{0}), …, (x_{n},y_{n}) con x_{j} ≠ x_{k} qualora j ≠ k, si calcoli p_{n} ∈ ℙ_{n} tale che

p_{n}(x_{k}) = y_{k}, k = 0, …, n

Tali polinomi p_{n} si dicono interpolare {(x_{k}, y_{k})}_{k=0,...,n}. Alcune questioni risultano di importanza fondamentale:

▶ Esiste tale polinomio?

▶ Se esiste è unico?

▶ Se esiste ed è unico, è possibile calcolarlo?

▶ Se f ∈ C([a, b]), esistono {x_{k}}_{k=0,...,n} ∈ [a, b] che rappresentano una scelta migliore di altre?

Sia ℙ_{n} l’insieme dei polinomi di grado n in ℝ. Date n + 1 coppie (x_{0},y_{0}), …, (x_{n},y_{n}) con x_{j} ≠ x_{k} qualora j ≠ k, si calcoli p_{n} ∈ ℙ_{n} tale che

p_{n}(x_{k}) = y_{k}, k = 0, …, n

Tali polinomi p_{n} si dicono interpolare {(x_{k}, y_{k})}_{k=0,...,n}. Alcune questioni risultano di importanza fondamentale:

▶ Esiste tale polinomio?

▶ Se esiste è unico?

▶ Se esiste ed è unico, è possibile calcolarlo?

▶ Se f ∈ C([a, b]), esistono {x_{k}}_{k=0,...,n} ∈ [a, b] che rappresentano una scelta migliore di altre?

Sia ℙ_{n} l’insieme dei polinomi di grado n in ℝ. Date n + 1 coppie (x_{0},y_{0}), …, (x_{n},y_{n}) con x_{j} ≠ x_{k} qualora j ≠ k, si calcoli p_{n} ∈ ℙ_{n} tale che

p_{n}(x_{k}) = y_{k}, k = 0, …, n

Tali polinomi p_{n} si dicono interpolare {(x_{k}, y_{k})}_{k=0,...,n}. Alcune questioni risultano di importanza fondamentale:

▶ Esiste tale polinomio?

▶ Se esiste è unico?

▶ Se esiste ed è unico, è possibile calcolarlo?

▶ Se f ∈ C([a, b]), esistono {x_{k}}_{k=0,...,n} ∈ [a, b] che rappresentano una scelta migliore di altre?

Sia ℙ_{n} l’insieme dei polinomi di grado n in ℝ. Date n + 1 coppie (x_{0},y_{0}), …, (x_{n},y_{n}) con x_{j} ≠ x_{k} qualora j ≠ k, si calcoli p_{n} ∈ ℙ_{n} tale che

p_{n}(x_{k}) = y_{k}, k = 0, …, n

Tali polinomi p_{n} si dicono interpolare {(x_{k}, y_{k})}_{k=0,...,n}. Alcune questioni risultano di importanza fondamentale:

▶ Esiste tale polinomio?

▶ Se esiste è unico?

▶ Se esiste ed è unico, è possibile calcolarlo?

▶ Se f ∈ C([a, b]), esistono {x_{k}}_{k=0,...,n} ∈ [a, b] che rappresentano una scelta migliore di altre?

Qualche esempio

▶ n=1: dati due punti (x_{0},y_{0}), (x_{1},y_{1}) trovare un polinomio di grado 1 che passi per i due punti. Equivale a dire: calcolare retta che passa per due punti assegnati.

▶ n=2: dati tre punti (x_{0},y_{0}), (x_{1},y_{1}), (x_{2},y_{2}) trovare un polinomio di grado 2 che passi per i tre punti. Equivale a dire: calcolare parabola

y = a_{1}x^{2} + a_{2}x + a_{3}

che passa per tre punti assegnati.

Qualche esempio

▶ n=1: dati due punti (x_{0},y_{0}), (x_{1},y_{1}) trovare un polinomio di grado 1 che passi per i due punti. Equivale a dire: calcolare retta che passa per due punti assegnati.

▶ n=2: dati tre punti (x_{0},y_{0}), (x_{1},y_{1}), (x_{2},y_{2}) trovare un polinomio di grado 2 che passi per i tre punti. Equivale a dire: calcolare parabola

y = a_{1}x^{2} + a_{2}x + a_{3}

che passa per tre punti assegnati.

Esempio di interpolazione

Figura: Grafico che illustra l’interpolazione su nodi equispaziati (la funzione ha la linea continua, il polinomio interpolatore è tratteggiato, i nodi di interpolazioni coi cerchietti).

Polinomi di Lagrange ed esistenza polinomio interpolatore

Consideriamo i polinomi di Lagrange L_{k} ∈ ℙ_{n} (rel. {x_{k}}_{k=0,...,n})

L_{k}(x) = \frac{(x − x_{0}) · . . . · (x − x_{k−1}) · (x − x_{k+1}) · . . . · (x − x_{n})}{(x_{k} − x_{0}) · . . . · (x_{k} − x_{k−1}) · (x_{k} − x_{k+1}) · . . . · (x_{k} − x_{n})}

Detto δ_{k,j} l’operatore di Kronecker, L_{k}(x_{s}) = δ_{k,s} cioè

L_{k}(x_{k}) = 1
L_{k}(x_{j}) = 0, se k ≠ j.

Allora ha le proprietà desiderate il polinomio p_{n} di grado n p_{n}(x) = ∑_{k=0}^{n}y_{k}L_{k}(x)

poichè p_{n}(x_{s}) = ∑_{k=0}^{n} y_{k}L_{k}(x_{s}) = ∑_{k=0}^{n} y_{k}δ_{k,s} = y_{s} per s = 0, …, n.

Alvise Sommariva  Interpolazione polinomiale

Unicità polinomio interpolatore

Supponiamo p_{n}, q_{n} ∈ ℙ_{n} siano tali che

p_{n}(x_{k}) = q_{n}(x_{k}) = y_{k}, k = 0, …, n.

Allora s_{n} = p_{n} − q_{n} ∈ ℙ_{n} ed è

s_{n}(x_{k}) = p_{n}(x_{k}) − q_{n}(x_{k}) = 0, k = 0, …, n

per cui

s_{n} = α(x − x_{0}) · . . . · (x − x_{n}).

Se α ≠ 0 allora s_{n} ∈ ℙ_{n+1}, cosa assurda. Quindi α = 0, il che implica p_{n} − q_{n} = s_{n} = 0 cioè p_{n} = q_{n}. Deduciamo così che il polinomio p_{n} ∈ ℙ_{n} interpolante {(x_{k}, y_{k})}_{k=0,...,n} (con x_{k} ≠ x_{s} se k ≠ s) non solo esiste ma è pure unico ed è

p_{n}(x) = ∑_{k=0}^{n}y_{k}L_{k}(x).

Esempio

Calcoliamo il polinomio di grado 2 che assume nei nodi x_{0} = −2, x_{1} = 1, x_{2} = 3 rispettivamente i valori f_{0} = −2, f_{1} = 11, f_{2} = 17.

L_{0}(x) = \frac{(x − x_{1})(x − x_{2})}{(x_{0} − x_{1})(x_{0} − x_{2})} = \frac{(x − 1)(x − 3)}{(−2 − 1)(−2 − 3)} = \frac{(x − 1)(x − 3)}{15}
L_{1}(x) = \frac{(x − x_{0})(x − x_{2})}{(x_{1} − x_{0})(x_{1} − x_{2})} = \frac{(x − (−2))(x − 3)}{(1 − (−2))(1 − 3)} = \frac{(x + 2)(x − 3)}{−6}
L_{2}(x) = \frac{(x − x_{0})(x − x_{1})}{(x_{2} − x_{0})(x_{2} − x_{1})} = \frac{(x − (−2))(x − 1)}{(3 − (−2))(3 − 1)} = \frac{(x + 2)(x − 1)}{10}

Si vede subito che L_{0}, L_{1}, L_{2} ∈ ℙ_{2} che L_{0}(x_{0}) = L_{0}(−2) = 1, L_{0}(x_{1}) = L_{0}(1) = 0, L_{0}(x_{2}) = L_{0}(3) = 0 L_{1}(x_{1}) = L_{1}(1) = 1, L_{1}(x_{0}) = L_{1}(−2) = 0, L_{1}(x_{2}) = L_{1}(3) = 0 L_{2}(x_{2}) = L_{2}(3) = 1, L_{2}(x_{0}) = L_{2}(−2) = 0, L_{2}(x_{1}) = L_{2}(1) = 0

Alvise Sommariva  Interpolazione polinomiale

Esempio

Posto p_{2}(x) = −2 L_{0}(x) + 11 L_{1}(x) + 17 L_{2}(x) abbiamo

p(x_{0}) = −2 L_{0}(x_{0})+11 L_{1}(x_{0})+17 L_{2}(x_{0}) = −2·1+11·0+17·0 = −2 = y_{0},

p(x_{1}) = −2 L_{0}(x_{1})+11 L_{1}(x_{1})+17 L_{2}(x_{1}) = −2·0+11·1+17·0 = 11 = y_{1},

p(x_{2}) = −2 L_{0}(x_{2})+11 L_{1}(x_{2})+17 L_{2}(x_{2}) = −2·0+11·0+17·1 = 17 = y_{2}.

cioè p_{2} interpola le coppie {(x_{k}, y_{k})}_{k=0,1,2}.

Utilizzo polinomio interpolatore

Usualmente i dati y_{k} corrispondono alla valutazione di una funzione f ∈ C([a, b]) in nodi x_{k} ∈ [a, b]. Si desidera che il polinomio interpolatore p_{n} approssimi la funzione f . Risulta quindi importante stimare l’errore compiuto. A tal proposito vale il seguente teorema detto del resto.

Teorema. Sia f ∈ C^{(n+1)}(a, b) e sia p_{n} il polinomio che interpola le coppie {(x_{k}, y_{k})}_{k=0,...,n} con x_{k} ≠ x_{s} se k ≠ s. Allora

f (x) − p_{n}(x) = f^{(n+1)}(ξ)\frac{∏_{i=0}^{n}(x − x_{i})}{(n + 1)!}  (1)

dove ξ ∈ I con I il più piccolo intervallo aperto contenente x_{0}, …, x_{n}.

Alcune scelte dei nodi

Consideriamo l’intervallo chiuso e limitato [a, b]. Vediamo alcuni sets di nodi.

▶ Equispaziati: x_{k} = a + k \frac{(b−a)}{n}, k = 0, …, n. ▶ Gauss-Chebyshev (scalati): fissato n, i punti sono

x_{k} = \frac{(a + b)}{2} + \frac{(b − a)}{2} t_{k}, k = 0, …, n  (2)

con

t_{k} = cos (\frac{2k + 1}{2n + 2} π) , k = 0, …, n;  (3)

▶ Gauss-Chebyshev-Lobatto (scalati): fissato n, i punti sono

x_{k} = \frac{(a + b)}{2} + \frac{(b − a)}{2} t_{k}, k = 0, …, n  (4)

con

t_{k} = − cos (\frac{kπ}{n}) , k = 0, …, n.  (5)
Alvise Sommariva  Interpolazione polinomiale

Alcune scelte dei nodi

Consideriamo l’intervallo chiuso e limitato [a, b]. Vediamo alcuni sets di nodi.

▶ Equispaziati: x_{k} = a + k \frac{(b−a)}{n}, k = 0, …, n. ▶ Gauss-Chebyshev (scalati): fissato n, i punti sono

x_{k} = \frac{(a + b)}{2} + \frac{(b − a)}{2} t_{k}, k = 0, …, n  (2)

con

t_{k} = cos (\frac{2k + 1}{2n + 2} π) , k = 0, …, n;  (3)

▶ Gauss-Chebyshev-Lobatto (scalati): fissato n, i punti sono

x_{k} = \frac{(a + b)}{2} + \frac{(b − a)}{2} t_{k}, k = 0, …, n  (4)

con

t_{k} = − cos (\frac{kπ}{n}) , k = 0, …, n.  (5)
Alvise Sommariva  Interpolazione polinomiale

Alcune scelte dei nodi

Consideriamo l’intervallo chiuso e limitato [a, b]. Vediamo alcuni sets di nodi.

▶ Equispaziati: x_{k} = a + k \frac{(b−a)}{n}, k = 0, …, n. ▶ Gauss-Chebyshev (scalati): fissato n, i punti sono

x_{k} = \frac{(a + b)}{2} + \frac{(b − a)}{2} t_{k}, k = 0, …, n  (2)

con

t_{k} = cos (\frac{2k + 1}{2n + 2} π) , k = 0, …, n;  (3)

▶ Gauss-Chebyshev-Lobatto (scalati): fissato n, i punti sono

x_{k} = \frac{(a + b)}{2} + \frac{(b − a)}{2} t_{k}, k = 0, …, n  (4)

con

t_{k} = − cos (\frac{kπ}{n}) , k = 0, …, n.  (5)
Alvise Sommariva  Interpolazione polinomiale

Convergenza ed esempio di Runge

L’interpolante polinomiale in un set di nodi prefissati non converge sempre puntualmente alla funzione da approssimare. Infatti, per la funzione di Runge

f (x) = \frac{1}{1 + x^{2}}, x ∈ [−5, 5]  (6)

si ha che il polinomio interpolatore p_{n} in nodi equispaziati non converge (puntualmente) a f . Fortunatamente ciò non succede per i nodi di Gauss-Chebyshev.

Purtroppo, per un teorema dovuto a Faber, esistono comunque funzioni continue f (ma non C^{1}!!) tali che l’interpolante p_{n} nei nodi di Gauss-Chebyshev non converge puntualmente a f . Questo teorema è generalizzabile ad una famiglia arbitraria di nodi.

Esempio di Runge

Figura: Grafico della funzione di Runge 1/(1 + x^{2}) nell’intervallo [−5, 5] e delle sue interpolanti di grado 12 nei nodi equispaziati e di Chebyshev-Gauss-Lobatto (rispettivamente linea continua, tratteggiata e a puntini, come da legenda).

Esempio di Runge

Figura: Grafico errore della funzione di Runge 1/(1 + x^{2}) nell’intervallo [−5, 5] con le sue interpolanti di grado 12 nei nodi equispaziati e di Chebyshev-Gauss-Lobatto (rispettivamente linea continua, tratteggiata e a puntini, come da legenda).