Interpolazione polinomiale

(1)

Il problema Forma di Lagrange L'errore Costanti di Lebesgue Nodi equispaziati Risultati con MATLAB Nodi di Jacobi Risultati con MATLAB Bibliograa

Interpolazione polinomiale

Andrea Azzarelli

Relatore: prof. Giuseppe Rodriguez

Università degli Studi di Cagliari Corso di laurea in Matematica

(2)

Interpolazione polinomiale

È una tecnica di approssimazione di funzioni in cui si cerca un polinomio che assuma esattamente il valore della funzione originale in un certo numero di punti detti nodi.

-3 -2.5 -2 -1.5 -1 -0.5 0 0.5 1 -1 -0.5 0 0.5 1 1.5 2 2.5 funzione polinomio nodi -3 -2.5 -2 -1.5 -1 -0.5 0 0.5 1 -0.5 0 0.5 1 1.5 2 2.5 funzione polinomio nodi

(3)

Esempi di applicazioni

Trattamento di dati sperimentali:

I Conoscere il valore di una funzione in un intervallo la quale è nota solo in alcuni punti;

Risoluzione di problemi matematici computazionalmente complessi:

I Formule di quadratura, derivazione numerica o altri

processi che si semplicano grazie alla proiezione di una funzione che appartiene a uno spazio di

dimensione innita sullo spazio funzionale Pn di

dimensione nita:

Pn= a0+ a1x + a2x2+ · · · + anxn

a_i ∈ R

(4)

Esempi di applicazioni

Trattamento di dati sperimentali:

I Conoscere il valore di una funzione in un intervallo la quale è nota solo in alcuni punti;

Risoluzione di problemi matematici computazionalmente complessi:

I Formule di quadratura, derivazione numerica o altri processi che si semplicano grazie alla proiezione di una funzione che appartiene a uno spazio di dimensione innita sullo spazio funzionale Pn di

dimensione nita:

Pn= a0+ a1x + a2x2+ · · · + anxn

a_i ∈ R

(5)

Denizione rigorosa

Denizione (polinomio interpolante)

Data una funzione y = f (x) della quale si conoscono i valori yj = f (xj), j =0, . . . , n,

un polinomio p ∈ Pn interpola la funzione f nei punti xj se

p(xj) = yj, j =0, . . . , n. Teorema (Esistenza e unicità)

Fissati n + 1 nodi, il polinomio interpolante di grado n esiste ed

(6)

Denizione rigorosa

Denizione (polinomio interpolante)

Data una funzione y = f (x) della quale si conoscono i valori yj = f (xj), j =0, . . . , n,

un polinomio p ∈ Pn interpola la funzione f nei punti xj se

p(xj) = yj, j =0, . . . , n. Teorema (Esistenza e unicità)

Fissati n + 1 nodi, il polinomio interpolante di grado n esiste ed è unico se e solo se xi 6= xj per ogni i 6= j.

(7)

Rappresentazioni

Canonica È la più immediata, serve per dimostrare il teorema di esistenza e unicità ma risulta instabile:

pn(x ) = n

X

i =0

aixi.

Newton (1670) Si basa su una formula ricorsiva ed è utile quando si vuole aggiungere un nuovo punto alla volta conservando tutti gli altri.

Lagrange (1795) Si basa sulla creazione di una particolare

(8)

Rappresentazioni

pn(x ) = n

X

i =0

aixi.

Lagrange (1795) Si basa sulla creazione di una particolare

(9)

Rappresentazioni

pn(x ) = n

X

i =0

aixi.

Lagrange (1795) Si basa sulla creazione di una particolare base dello spazio dei polinomi Pn.

(10)

Forma di Lagrange

I polinomi che costituiscono la base per la rappresentazione di Lagrange sono detti polinomi caratteristici di Lagrange: L(n)_j (x ) = n Y k=0 k6=j (x − xk) (xj − xk) .

Figura:Joseph Louis Lagrange Torino, 1736 Parigi, 1813.

(11)

Questi polinomi possiedono una proprietà notevole in relazione ai nodi: L(n)_j (xi) = δij =(1 i = j 0 i 6= j -1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 1.2 L₀ _L 1 L2 L3

la quale rende estremamente semplice la scrittura del polinomio interpolante, in questa base infatti i suoi coecienti sono semplicemente i valori f (xj): pn(x ) = n X j =0 f (xj)L(n)_j (x ).

(12)

Questi polinomi possiedono una proprietà notevole in relazione ai nodi: L(n)_j (xi) = δij =(1 i = j 0 i 6= j -1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 1.2 L₀ _L 1 L2 L3

la quale rende estremamente semplice la scrittura del polinomio interpolante, in questa base infatti i suoi coecienti sono semplicemente i valori f (xj): pn(x ) = n X j =0 f (xj)L(n)_j (x ).

(13)

L'errore

Teorema (Weierstrass)

Sia f ∈ C([a, b]). Per ogni ε > 0 esiste un intero n e un polinomio pn∈ Pn tale che

kEn(x )k := kf − pnk∞< ε. Denizione

Deniamo polinomio di migliore approssimazione di grado n il polinomio p∗_n tale che

kf − p_n∗k∞= min

pn∈Pn

kf − pnk∞:= E_n∗(f ).

La quantità E∗

(14)

L'errore

Teorema (Weierstrass)

Sia f ∈ C([a, b]). Per ogni ε > 0 esiste un intero n e un polinomio pn∈ Pn tale che

kEn(x )k := kf − pnk∞< ε. Denizione

Deniamo polinomio di migliore approssimazione di grado n il polinomio p∗_n tale che

kf − p_n∗k∞= min pn∈Pn

kf − pnk∞:= E_n∗(f ).

La quantità E∗

(15)

Il problema Forma di Lagrange L'errore Costanti di Lebesgue Nodi equispaziati Risultati con MATLAB Nodi di Jacobi Risultati con MATLAB Bibliograa Teorema Sia f ∈ Cn+1_{([a, b])} _{e p}

n il polinomio interpolante, allora per

ogni x ∈ [a, b] esiste un punto ξx ∈ [a, b]tale che

En(x ) := f (x ) − pn(x ) =

f(n+1)(ξx)

(n +1)! ωn(x ), dove ωn(x ) = (x − x0)(x − x1) · · · (x − xn).

Questo teorema ha delle importanti conseguenze:

I se |f(n+1)(x )| è limitata per ogni n su [a, b], allora

f(n+1)_(ξx₎

(n+1)! tende a zero al crescere di n;

I kω_n(x )k∞ tende all'innito al crescere di n, la velocità di

(16)

En(x ) := f (x ) − pn(x ) =

f(n+1)(ξx)

Questo teorema ha delle importanti conseguenze: I se |f(n+1)(x )| è limitata per ogni n su [a, b], allora

f(n+1)_(ξ_x₎

(17)

En(x ) := f (x ) − pn(x ) =

f(n+1)(ξx)

Questo teorema ha delle importanti conseguenze: I se |f(n+1)(x )| è limitata per ogni n su [a, b], allora

f(n+1)_(ξ_x₎

(18)

Costanti di Lebesgue

Raccogliamo nelle righe di una matrice X , detta matrice di interpolazione, i nodi scelti:

X =     x₀(0) x₀(1) x₁(1) x₀(2) x₁(2) x₂(2) .. . ... ... ...     ,

Sia Pn(X , f )l'operatore che a ciascuna funzione f associa il

polinomio di grado n determinato dai nodi della corrispondente riga di X , si dimostra che

En(X , f ) := kf − Pn(X , f )k∞≤ 1 + Λn(X )En∗(f ),

dove abbiamo introdotto le cosiddette costanti di Lebesgue: Λn(X ) = n X j =0 L (n) j (x ) ∞.

(19)

Costanti di Lebesgue

Raccogliamo nelle righe di una matrice X , detta matrice di interpolazione, i nodi scelti:

X =     x₀(0) x₀(1) x₁(1) x₀(2) x₁(2) x₂(2) .. . ... ... ...     ,

Sia Pn(X , f )l'operatore che a ciascuna funzione f associa il

polinomio di grado n determinato dai nodi della corrispondente riga di X , si dimostra che

En(X , f ) := kf − Pn(X , f )k∞≤ 1 + Λn(X )En∗(f ),

dove abbiamo introdotto le cosiddette costanti di Lebesgue:

Λn(X ) = n X j =0 L (n) j (x ) ∞.

(20)

Costanti di Lebesgue e stabilità

Quindi le costanti di Lebesgue esprimono il condizionamento assoluto della rappresentazione di Lagrange.

(21)

Andamento delle costanti di Lebesgue

Teorema

Per ogni X matrice di interpolazione esiste una costante c tale che

Λn(X ) ≥ 2

π log n − c.

Quindi per n −→ ∞ la successione Λn diverge con crescita

almeno logaritmica.

Teorema (Nodi equispaziati)

Le costanti di Lebesgue associate ai nodi equispaziati crescono in modo esponenziale.

(22)

Andamento delle costanti di Lebesgue

Teorema

Per ogni X matrice di interpolazione esiste una costante c tale che

Λn(X ) ≥ 2

π log n − c.

Quindi per n −→ ∞ la successione Λn diverge con crescita

almeno logaritmica.

Teorema (Nodi equispaziati)

Le costanti di Lebesgue associate ai nodi equispaziati crescono in modo esponenziale.

(23)

Per analizzare alcuni aspetti dell'interpolazione sono stati sviluppati su MATLAB dei programmi che permettono di calcolare

I i nodi di interpolazione;

I le costanti di Lebesgue dati i nodi;

I il polinomio interpolante su un intervallo col metodo di Lagrange dati i nodi e la funzione.

I programmi sono stati testati su diversi problemi, di seguito riportiamo i risultati relativi a uno di essi.

(24)

Nodi equispaziati

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 0 2 4 6 8 10 4 nodi funzione polinomio nodi

(25)

Nodi equispaziati

(26)

Nodi equispaziati

(27)

Nodi equispaziati

(28)

Nodi equispaziati

101 102 10-20 100 1020 1040 1060 1080 10100 Errore

Figura:Interpolazione della funzione f (x) = |x3₋_{2| −}√3_x_.

(29)

Nodi equispaziati

50 100 150 200 250 300 350 100 1020 1040 1060 1080 Costanti di Lebesgue nodi equispaziati log n

(30)

Polinomi ortogonali di Jacobi

La ricerca di nodi più ecienti ha portato a scegliere come ascisse di interpolazione le radici di particolari polinomi:

Denizione

Fissati α, β > −1 sono detti pesi di Jacobi le funzioni ω_βα(x ) := (1 − x)α(1 + x)β.

I polinomi ortogonali di Jacobi sono una successione di

polinomi pk ∈ Pk che risultano reciprocamente ortogonali

rispetto al prodotto scalare pesato: hp_k, pji =

Z 1

−₁

pk(x )pj(x )ωαβ(x )dx = 0, j 6= k,

denito sullo spazio L2

(31)

Polinomi ortogonali di Jacobi

La ricerca di nodi più ecienti ha portato a scegliere come ascisse di interpolazione le radici di particolari polinomi:

Denizione

Fissati α, β > −1 sono detti pesi di Jacobi le funzioni ω_βα(x ) := (1 − x)α(1 + x)β.

I polinomi ortogonali di Jacobi sono una successione di polinomi pk ∈ Pk che risultano reciprocamente ortogonali

rispetto al prodotto scalare pesato:

hp_k, pji =

Z 1

−₁

pk(x )pj(x )ωαβ(x )dx = 0, j 6= k,

denito sullo spazio L2

(32)

Nodi di Jacobi

Teorema

Per ogni n ∈ N il polinomio pn+1 ha n + 1 radici

I semplici; I reali;

I contenute in (−1, 1).

Chiamiamo nodi di Jacobi tali radici, indichiamo con Xα β la

relativa matrice di interpolazione.

Una classe particolare di nodi di Jacobi è quella che si ottiene

per α = β = −1

2, essi sono detti nodi di Chebychev e si

possono calcolare in maniera semplice con la formula: x_k(n)= cos

2k + 1

2n + 2

(33)

Nodi di Jacobi

Teorema

Per ogni n ∈ N il polinomio pn+1 ha n + 1 radici

I semplici; I reali;

I contenute in (−1, 1).

Chiamiamo nodi di Jacobi tali radici, indichiamo con Xα β la

relativa matrice di interpolazione.

Una classe particolare di nodi di Jacobi è quella che si ottiene per α = β = −1

2, essi sono detti nodi di Chebychev e si

possono calcolare in maniera semplice con la formula: x_k(n)= cos

2k + 1 2n + 2

(34)

Il problema Forma di Lagrange L'errore Costanti di Lebesgue Nodi equispaziati Risultati con MATLAB Nodi di Jacobi Risultati con MATLAB Bibliograa Teorema

Fissati p−1 =0, p0=1 i polinomi ortogonali di Jacobi sono

univocamente deniti dalla formula ricorsiva a tre termini pk+1(x ) = (x − αk)pk(x ) − βk2pk−1(x ), dove αk = hxp_k, pki hp_k, pki , β₀2 =0, β_k2 = hxpk, pk−1i hp_k−₁, pk−1i .

Le radici del polinomio ortogonale

pn+1 corrispondono agli autovalori

della matrice tridiagonale simmetrica:       α₀ β₁ β₁ α₁ ... ... ... βn βn αn       .

(35)

Il problema Forma di Lagrange L'errore Costanti di Lebesgue Nodi equispaziati Risultati con MATLAB Nodi di Jacobi Risultati con MATLAB Bibliograa Teorema

Fissati p−1 =0, p0=1 i polinomi ortogonali di Jacobi sono

univocamente deniti dalla formula ricorsiva a tre termini pk+1(x ) = (x − αk)pk(x ) − βk2pk−1(x ), dove αk = hxp_k, pki hp_k, pki , β₀2 =0, β_k2 = hxpk, pk−1i hp_k−₁, pk−1i .

Le radici del polinomio ortogonale pn+1 corrispondono agli autovalori

della matrice tridiagonale simmetrica:       α₀ β₁ β₁ α₁ ... ... ... βn βn αn       .

(36)

Costanti di Lebesgue dei nodi di Jacobi

Teorema (Nodi di Chebychev)

Le costanti di Lebesgue relative ai nodi di Chebychev hanno una crescita al più logaritmica

Λn(X−−_0.50.5) <

2

π log n +4.

Più in generale vale il seguente Teorema (Nodi di Jacobi) Per ogni n ∈ N

Λn(Xβα) ∼

(

log n −1 < α, β ≤ −1₂;

(37)

Costanti di Lebesgue dei nodi di Jacobi

Teorema (Nodi di Chebychev)

Le costanti di Lebesgue relative ai nodi di Chebychev hanno una crescita al più logaritmica

Λn(X−−_0.50.5) <

2

π log n +4. Più in generale vale il seguente

Teorema (Nodi di Jacobi)

Per ogni n ∈ N

Λn(Xβα) ∼

(

log n −1 < α, β ≤ −1₂; nmax{α,β}+12 altrimenti.

(38)

Nodi di Jacobi

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 0 2 4 6 8 10 4 nodi funzione = 1.3, = 1.3 = -0.5, = -0.5

(39)

Nodi di Jacobi

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 0 2 4 6 8 10 7 nodi funzione = 1.3, = 1.3 = -0.5, = -0.5

(40)

Nodi di Jacobi

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 0 2 4 6 8 10 15 nodi funzione = 1.3, = 1.3 = -0.5, = -0.5

(41)

Nodi di Jacobi

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 0 2 4 6 8 10 31 nodi funzione = 1.3, = 1.3 = -0.5, = -0.5

(42)

Nodi di Jacobi

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 0 2 4 6 8 10 31 nodi funzione = 1.3, = 1.3 = -0.5, = -0.5

(43)

Nodi di Jacobi

1.6 1.65 1.7 1.75 1.8 1.85 1.9 1.95 2 2.5 3 3.5 4 4.5 31 nodi funzione = 1.3, = 1.3 = -0.5, = -0.5

(44)

Nodi di Jacobi

101 102 10-2 10-1 100 101 Errore = -0.8, = 1.3 = 1.3, = 1.3 = -0.8, = -0.8 = -0.5, = -0.5

(45)

Nodi di Jacobi

0 50 100 150 200 250 300 350 100 101 102 103 104 105 Costanti di Lebesgue = -0.8, = 1.3 = 1.3, = 1.3 = -0.8, = -0.8 = -0.5, = -0.5 n1.8 log n

(46)

Nodi di Jacobi

101 102 10-5 100 105 1010 1015 Errore = 5, = 10 = 10, = 10 = 5, = 5 = -0.5, = -0.5

(47)

Nodi di Jacobi

0 50 100 150 200 250 300 350 400 100 105 1010 1015 1020 1025 1030 Costanti di Lebesgue n5.5 n10.5 log n = 5, = 10 = 10, = 10 = 5, = 5 = -0.5, = -0.5

(48)

Riferimenti bibliograci

[1] Luisa Fermo.

Applicable Approximation Theory. Cagliari, 2019. [2] Walter Gautschi.

Orthogonal Polynomials, Computation and Approximation. Oxford University Press, 2004.

[3] Giuseppe Rodriguez.

Interpolazione polinomiale

Interpolazione polinomiale

Interpolazione polinomiale

Esempi di applicazioni

Esempi di applicazioni

Denizione rigorosa

Denizione rigorosa

Rappresentazioni

Rappresentazioni

Rappresentazioni

Forma di Lagrange

L'errore

L'errore

Costanti di Lebesgue

Costanti di Lebesgue

Costanti di Lebesgue e stabilità

Andamento delle costanti di Lebesgue

Andamento delle costanti di Lebesgue

Nodi equispaziati

Nodi equispaziati

Nodi equispaziati

Nodi equispaziati

Nodi equispaziati

Nodi equispaziati

Polinomi ortogonali di Jacobi

Polinomi ortogonali di Jacobi

Nodi di Jacobi

Nodi di Jacobi

Costanti di Lebesgue dei nodi di Jacobi

Costanti di Lebesgue dei nodi di Jacobi

Nodi di Jacobi

Nodi di Jacobi

Nodi di Jacobi

Nodi di Jacobi

Nodi di Jacobi

Nodi di Jacobi

Nodi di Jacobi

Nodi di Jacobi

Nodi di Jacobi

Nodi di Jacobi

Riferimenti bibliograci

Denizione rigorosa

Denizione rigorosa

Riferimenti bibliograci