Interpolazione polinomiale

1

Approssimazione di funzioni mediante

Interpolazione polinomiale

(estatico@uninsubria.it)

Lezione basata su appunti del prof. Marco Gaviano

2

Approssimazione di funzioni

1) L’approssimazione di funzioni. Interpolazione e migliore approssimazione.

2) Interpolazione polinomiale. Esistenza e unicità.

3) Interpolazione di Lagrange e di Hermite.

4) Convergenza dell’interpolazione polinomiale.

Errore di interpolazione.

3

Approssimazione di funzioni

Sia data la tabulazione

di una funzione y=f(x), con f:RR, di cui non si conosce la sua espressione analitica.

L’obiettivo è trovare una “nuova” funzione p(x), p: RR , dotata di una rappresentazione analitica “semplice”, che approssimi la funzione f(x) (in modo tale che p(x) possa essere utilizzata al posto della f(x)).

n i

y

x _i , _i per  0 , 1 ,...,

4

Esempio

Si rileva la temperatura in una stanza ogni secondo nell’arco delle 24 ore. Si hanno quindi a disposizione 3600*24=86400 dati, ovvero le coppie

in cui la variabile x si riferisce ai secondi, e la y alle corrispondenti temperature.

86400 ,

...

, 1 , 0 per

, y i 

x

5

La conoscenza, in forma analitica, di una funzione p(x) di forma semplice che approssima la funzione vera f(x) a partire dai punti di tabulazione (x

, y

), per i=1,…,n, permette un trattamento efficiente del modello matematico che esprime il fenomeno, specie al calcolatore.

Infatti

•per memorizzare la funzione basta memorizzare la legge che definisce p(x), generalmente dipendente da meno parametri rispetto a f(x).

•posso approssimare, tramite la p(x), la f(x) anche in

qualsiasi altro punto esterno alle ascisse x

di tabulazione.

6

Osservazione

Si arriva allo stesso problema quando di una funzione f(x) si conosce la sua espressione analitica ma questa è complicata da calcolare, da derivare o da integrare.

Allora, in tal caso, tramite una tabulazione di f(x) si vuole determinare un “nuova” funzione p(x) dotata di una rappresentazione analitica “semplice” da valutare, da derivare o da integrare, che possa essere utilizzata al posto della f(x).

7

Osservazione

Il problema si generalizza al caso di funzione di 2 variabili z=f(x,y) , f:R

 R, della quale si conoscono i valori

e si vuole trovare un nuova funzione p(x,y), dotata di una rappresentazione analitica “semplice”, che possa essere utilizzata al posto della f(x,y).

m j

n i

per z

y

x

,

),

0 , 1 ,..., , 0 , 1 ,...,

(

 

8

Tecniche per la soluzione del problema

Interpolazione

si cerca quella funzione (in una fissata famiglia di funzioni) che in opportuni punti (detti nodi) assume gli stessi valori della funzione da approssimare.

Migliore approssimazione

si cerca quella funzione (in una fissata famiglia di funzioni)

la cui distanza (rispetto ad una fissata norma) dalla

funzione da approssimare risulta essere minima.

9

Punti (detti nodi di interpolazione) in cui la funzione f(x) e la sua approssimazione p(x) devono coincidere

funzione f(x) da approssimare,

conosciuta attraverso una sua

tabulazione (x

, y

)

10

Approssimazione mediante interpolazione (formulazione matematica)

Dati i punti x

,y

, i=0,1,…, n, con x

R, x

x

per ik. e una famiglia di funzioni

si cercano i valori a

, a

,…, a

(corrrispondenti ai gradi di libertà della famiglia di funzioni ) tali che

"

matematico modello

il

"

) ,...,

;

( x a

a



n i

y a

a

x

; ,...,

)

0 , 1 ,...,

(

 



11

Nel caso in cui la famiglia di funzioni (x; a

, …, a

) dipenda linearmente dai parametri a

, …, a

, ovvero nel caso in cui esistano n funzioni base 

(x) per i=1,…,n , t.c.

allora il problema è detto di interpolazione lineare.

) ( ...

) ( )

( )

,...,

;

( x a

a

 a



x  a



x   a



x



12

Esempio: Interpolazione polinomiale

La famiglia di funzioni (x; a

, …, a

) è definita da

e quindi si approssima la funzione f(x), la cui tabulazione è x

,y

, con un polinomio di grado n (da notare che i punti sono n+1 ed il polinomio è di grado n).

n n

n

a a x a x a x

a a

x    

 ( ;

,..., )

...

13

Esempio: Interpolazione trigonometrica

La famiglia di funzioni (x; a

, …, a

) è definita da

e quindi si approssima la funzione f(x), la cui tabulazione è x

,y

, con una combinazione lineare delle funzioni sen(kx) e cos(kx), per k=0,…,n, detta polinomio trigonometrico.

) (

) cos(

...

cos

) ,...,

, ,...,

; (

1 1

0

0 0

nx sen

b nx

a senx

b x

a a

b b

a a

x

n n

n n

















14

Esempio: Interpolazione nello studio delle popolazioni in biologia (dinamica delle popolazioni)

La famiglia di funzioni (x; a

, …, a

) è definita da

si approssima la funzione f(x), la cui tabulazione è x

, y

, i=0,2,…,n, con una combinazione lineare di funzioni esponenziali.

x n

x x

n n

e

a e

a e

a a

a

x    ^  ^  ^

 ( ; ₀ ,..., , ₀ ,..., ) ₀

₁

...

15

Interpolazione polinomiale

La famiglia di funzioni (x; a

, …, a

) è definita da

e si cerca il polinomio p(x)P

, dove P

rappresenta l’insieme dei polinomi di grado  n, tale che

Risultato fondamentale: il polinomio p(x), detto polinomio interpolatore, esiste ed è unico.

n n

n

p x a a x a x a x

a a

x     

 ( ;

,..., ) ( )

...

n i

y x

p ( _i )  _i ,  0 , 1 , 2 ,...,

16

Esistenza ed unicit à del polinomio interpolatore (n=3) Trova

tale che , ossia tale che

Questo è un sistema lineare 44 in cui le incognite sono i 4 parametri a

, …, a

che definiscono il polinomio.

3 3 2

2 1

)

( x a a x a x a x

p    

3 3

3 3 2

3 2 3

1 0

2 3

2 3 2

2 2 2

1 0

1 3

1 3 2

1 2 1

1 0

0 3

0 3 2

0 2 0

1 0

y x

a x

a x

a a

y x

a x

a x

a a

y x

a x

a x

a a

y x

a x

a x

a a

































n i

y x

p (

) 

,  0 , 1 , 2 ,...,

17

Il determinante della matrice del sistema è

il quale è 0 nel caso in cui x

 x

per ik (nodi distinti).

Pertanto la soluzione esiste ed è unica, e quindi il polinomio interpolatore esiste ed è unico.

3 3 2

3 3

3 2 2

2 2

3 1 2

1 1

3 0 2

0 0

1 1 1 1

x x

x

x x

x

x x

x

x x

x determinante di

Vandermonde

18

Approssimazione mediante polinomio di grado 3

punti in cui la funzione ed

il polinomio devono coincidere

funzione f(x) da approssimare, conosciuta attraverso una

sua tabulazione x

, y

, i=0,1,2,3

19

Esistenza ed unicità del polinomio interp. (caso generale) Trova

tale che

Questo è un sistema lineare (n+1)(n+1) in cui le incognite sono gli n+1 parametri a

, …, a

n n

x a x

a x

a a

x

p ( ) 





 ... 

n n

n n n

n n

n n

y x

a x

a a

y x

a x

a a

y x

a x

a a

























...

....

...

...

1 0

1 1

1 1 0

0 0

0 1 0

20

Il determinante della matrice del sistema è

il quale è 0 nel caso in cui x

,  x

per ik (nodi distinti).

Pertanto la soluzione esiste ed è unica, e quindi il polinomio interpolatore esiste ed è unico. Possiamo riassumere il risultato tramite il teorema seguente:

 









n j i

i j

n n n

n

n n n

x x

x x

x

x x

x

x x

x

x x

x

0 2

2 2

2 2

1 2

1 1

0 2

0 0

...

1

...

...

...

...

...

...

1

...

1

...

1 determinante di

Vandermonde

21

Teorema (esistenza e unicità)

Dati gli n+1 punti, detti nodi di interpolazione,

esiste ed è unico il polinomio interpolatore pP

, ossia il polinomio pP

tale che

, se

, , ,...

2 , 1 , 0 per

), ,

( x

y

i  n x

 x

i  k

n i

y x

p ( _i )  _i ,  0 , 1 , 2 ,...,

22

Osservazione

Sulla base di quanto visto, per trovare il polinomio interpolatore su n+1 nodi è sufficiente risolvere un sistema lineare in n+1 incognite.

La soluzione del sistema ci fornisce i coefficienti del polinomio.

Esistono tuttavia delle formule che danno in modo diretto

il polinomio interpolante, senza la necessità di risolvere il

sistema di Vandermonde.

23

Costruzione dei polinomi interpolanti mediante la rappresentazione di Lagrange

L’insieme dei polinomi P

è uno spazio lineare di dimensione n+1, ed una sua base è formata dai polinomi

Un’altra base è data dagli n+1 polinomi seguenti

x n

x

x , , ..., ,

1 ²

n x i

x

x x x

L

n

i j

j i j

j

i

( ) , 0 , 1 , 2 ,...,

0

 

  



24

Tale base, detta base di Lagrange, ha la proprietà

Allora, per mezzo di tale base, il polinomio interpolatore relativo ai punti x

,y

, per i=0,1,…,n, assume la semplice forma seguente

ed è chiamato polinomio interpolatore (secondo la rappresentazione) di Lagrange.

Oss. Questa rappresentazione esplicita del polinomio inter- polatore è un’altra dimostrazione di esistenza e unicità.

 

 



 



 k n

i k

se

i k

x se

L

0 , 1 ,...,

0 ) 1

(





i

i i

L x y

x p

0

) ( )

(

25

La base di polinomi è

Si osservi che

1 0

2

0 2

2 1

2 0

1

0 1

2 0

2 1

0

1 0

) (

) (

) (

x x

x x

x x

x x x

L

x x

x x

x x

x x x

L

x x

x x

x x

x x x

L



 



 



 



 



 



 

1 )

( ,

0 )

( ,

0 )

(

0 )

( ,

1 ) ( ,

0 )

(

0 )

( ,

0 )

( ,

1 ) (

2 2 1

2 0

2

2 1 1

1 0

1

2 0 1

0 0

0



















x L x

L x

L

x L x

L x

L

x L x

L x

L

26

Il polinomio interpolante (o polinomio interpolatore) è

È immediato verificare che

1 2

1 0

2

0 2

2 1

2 0

1

0 1

2 0

2 1

0

1

)

( x x

x x

x x

x y x

x x

x x

x x

x y x

x x

x x

x x

x y x

x

p 

 



 



 



 



 



 

2 2

1 1

0

0 ) , ( ) , ( )

( x y p x y p x y

p   

27

Data una funzione f(x) di cui nei punti x

, per i=0,1,…,k, si conoscono i valori y

=f(x

) e di eventuali derivate. Con l’in- terpolazione di Hermite si cerca il polinomio che nei punti x

, i=0,1,…,k, assume gli stessi valori sia della funzione che delle sue derivate.

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

) ( 0

) ( )

( 2 )

( 1

) 2 ( )

2 ( 2 )

2 ( 1 )

2 ( 0

) 1 ( )

1 ( 2 )

1 ( 1 )

1 ( 0

2 1

0

2 1

0

0

2 1









y

y y y

y y

y y

y y

y y

y y

y y

x x

x x

k

k k

k k k

nodi

valore della funzione

valore della derivata 1

valore della derivata 

di ordine massimo per x

28

Formulazione matematica dell’interpolazione di Hermite

Dati k+1 punti distinti x

, x

, … , x

e k+1 numeri interi naturali

, 

, …, 

, sia n=k+ 

+

+… +

. Per ogni insieme di numeri , i=0,1,…,k e l=0,1,…, 

, esiste ed è unico il polinomio p(x)P

(x) tale che

Tale polinomio è detto polinomio interpolatore di Hermite.

i l

l i i l

l k i

dx y x p

d ( ) 

,  0 , 1 ,..., ;  0 , 1 ,..., 

) (l

y

29

considera un solo punto x

) ha il significato seguente.

In un punto x

si conosce il valore y

di una funzione f(x) ed i valori delle sue derivate l=1,…, 

=: . Si vyole determinare il polinomio di grado n=  tale che

In tal caso il polinomio cercato corrisponde allo sviluppo di Taylor fino alla derivata  di centro x

, ovvero

 ,..., 1 , 0 ) ,

(

0

0

 y l 

dx x p

d

l l

) ( 0 0

)

(^l

( x ) y

f 





 ! ^{( )( )} ... 1

) )(

2 ( ) 1 )(

( ' )

( )

( x f x

f x

x x

f

x

x x

f

x

x x

p        

30

Osservazione

I problemi di interpolazione visti finora sono dei casi particolari del problema generale dell’interpolazione lineare.

Ovviamente i risultati teorici sull’esistenza e unicità della soluzione che si dimostrano per il problema generale valgono in ogni caso particolare (come già visto per l’interpolazione di Lagrange ed Hermite).

Spesso è richiesto esclusivamente di determinare il

valore del polinomio p(x) in un punto x fissato. In tal

caso non occorre determinare i coefficienti del

polinomio, ma si utilizza l’algoritmo seguente, più

economico.

31

Questo algoritmo permette di calcolare in un (generico) punto x

il valore del polinomio interpolatore p(x

) data la tabulazione x

, y

, i=0,2,…,n. Introducendo la notazione

...

) ,

(x ), ,

(x per 1

grado di

polinomio

il è ) ( ...

) , (x ), ,

(x per 1

grado di

polinomio

il è ) (

) ,

(x per 0

grado di

polinomio

il è )

( ...

) ,

(x per 0

grado di

polinomio

il è )

(

) ,

(x per 0

grado di

polinomio

il è )

(

1 1

1 ,

1 1 0

0 1

, 0

1 1 1

1

0 0

0 0

n n

n n-

n n

n n

n n

y y

x P

y y

x P

y y

x P

y y

x P

y y

x P











32

E’ facile verificare che, per il grado 1, si ha

) y , (x e ) y , (x per polinomio

il ) è

( )

( ) ( ) ) (

(

..

.

) y , (x e ) y , (x per polinomio

il ) è

( ) (

) ( ) ) (

(

) y , (x e ) y , (x per polinomio

il ) è

( ) (

) ( ) ) (

(

k k 1

k 1 - k 1

1 1

), 1 (

2 2 1

1 1

2

1 2 2

1 2

, 1

1 1 0

0 0

1

0 1 1

0 1

, 0







 







 







 







 

k k

k k k

k k

k

x x

x P

x x x

P x

x x P

x x

x P x x x

P x x x

P

x x

x P x x x

P x x x

P

33

Quest’ultima può essere generalizzata per ricorrenza, ottenendo la relazione ricorsiva seguente

Questo è il polinomio interpolante di grado k-i per (x

, y

), (x

, y

), …, (x

, y

).

Per k=n ed i=0, si ottiene così che il valore del polinomio interpolatore di grado n+1 nel punto x

è

i k

k i

i k k

i i

k i

i

x x

x P

x x

x P

x x x

P 





 



) ( )

( ) ( )

) (

(

,..., 1 ,

)

,..., (

1 ,

0 n x s

P

34

) (

) (

) ( )

(

) ( )

(

) ( )

(

) ( )

(

3 2

1 0

3 3

3

23

123 2

2 2

0123 12

012 1

1 1

01 0

0 0

x P y

x

x P

x P

x P y

x

x P

x P

x P

x P y

x

x P

x P y

x

k











Il procedimento (Neville) può essere schematizzato come

segue

35

Introducendo la notazione

si trova la relazione

dove T

=y

e 1k i, i=0,1,…,n.

Il procedimento di Neville con la nuova notazione per il calcolo in un generico punto x

del valore del polinomio interpolante può essere schematizzato come segue.

k i i

i k

k

i

P

T



k i i

i k

i k

i k

i k

i

x x

x T x

T T

T













 





(

)

,

36 30

3 3

31

32 20

2 2

33 21

22 10

1 1

11 00

0 0

3 2

1 0

T y

x

T

T T

y x

T T

T T

y x

T T

y x

k











Procedimento di Neville

Nell’implementazione

si opera su un unico

array T

37

Algoritmo di Neville

t(0)=y(0) for i=1:n t(i)=y(i)

for j=i-1:-1:0

t(j)=t(j+1)+(t(j+1)-t(j))*(x

-x(i))/(x(i)-x(j)) end

end

f(x

)=t(0)

38

Convergenza dell’interpolazione

È importante riuscire a stimare l’errore che si commette quando si approssima una funzione tramite un polinomio interpolatore: i risultati teorici seguenti danno delle indicazioni molto utili a tale scopo.

In generale, si utilizza il concetto di norma di funzione.

Ad esempio, la norma del massimo e la norma 1 sono

norme di funzioni usate in C[a,b], dove C[a,b] è l’insieme

di tutte le funzioni continue nell’intervallo chiuso [a,b].

39

Norma del massimo

Data una funzione f(x) C[a,b], si ha

| ) (

| max

||

) (

|| f x f x

b x a  

 

Il valore massimo assunto dalla

funzione in [a,b] è la norma del massimo.

Tale valore esiste sempre (teorema del max di Weierstrass).

a b

40

Norma 1

Data una funzione f(x) C[a,b], si ha

dx x

f x

f ^b

 a

 | ( ) |

||

) (

|| ₁

L’area del valore assoluto della

funzione è la norma 1.

41

Distanza associata alla norma del massimo

Date due funzioni f(x) e g(x)  C[a,b], si ha

| ) ( )

(

| max

||

) ( )

(

||

) ,

( f g f x g x f x g x

dist   





 

dist(f,g)=massima differenza in

valore assoluto

a b

42

Distanza associata alla norma 1

Date due funzioni f(x) e g(x)  C[a,b], si ha

dx x

g x

f x

g x

f g

f

dist ^b

 a ^





 || ( ) ( ) || | ( ) ( ) | )

,

( ₁

dist(f,g)= misura della superficie tratteggiata

a b

f(x)

g(x)

43

Generalizzazione della norma 1 per funzioni La norma 2

Data una funzione f(x)C[a,b], con C[a,b] l’insieme di tutte le funzioni continue nell’intervallo [a,b], si ha

2 / 1 2

2 ( ( ))

||

) (

|| 

 

 

   ^{f x dx}

x

f ^b

a

44

La norma p, per 1p< .

Si consideri l’insieme L

([a,b]) di tutte le funzioni per cui l’integrale

esiste ed è finito (tale insieme è uno spazio lineare).

Data una funzione f(x)L

([a,b]), la norma p di f(x) è data da

Osservazione: C[a,b] è strettamente contenuto in L

([a,b]).

dx x

b f

a

 ^{| ( ) |} p

b p

a

p

p f x dx

x f

/ 1

| ) (

|

||

) (

|| 

 

 

  

45

Teorema di Weierstrass

Sia f(x) una funzione continua su un intervallo limitato e chiuso [a,b]. Allora per ogni >0 esiste un intero n (dipendente da ), ed un polinomio P

(x) di grado al più n tale che

con || · ||

la norma del massimo per funzioni.





 ( ) ||

)

(

|| f x P

x

46

Il teorema afferma che l’insieme dei polinomi è denso in C[a,b] nella norma del massimo. Non fornisce però alcuna informazione sull’interpolazione polinomiale.

Osservazione

Il teorema di Weierstrass dimostra che l’insieme delle funzioni continue C[a,b] è separabile.

Infatti il teorema consente di concludere che l’insieme

dei polinomi 1, x, x

, x

, …. è chiuso (o completo) in

C[a,b].

47

La dimostrazione del teorema di Weierstrass fornisce un modo per costruire particolari polinomi (detti polinomi di Bernstein) che approssimano la funzione (la dimostrazione è quindi di carattere costruttivo).

Purtroppo il grado del polinomio approssimante, in generale, è molto elevato. Per esempio se si vuole approssimare la funzione (2-x)

per =0.2·10

si ottiene

10 9



n

48

Matrice di interpolazione (definizione)

Si chiama matrice di interpolazione sull’intervallo [a,b]

una matrice triangolare del tipo

con e gli elementi in ciascuna riga distinti.

Gli elementi di ciascuna riga, ognuno associato al corrispondente valore , rappresentano i j+1 nodi di interpolazione del polinomio interpolatore di grado j.

. .

. .

2 2 2

1 2

0

1 1 1

0 0 0

x x

x

x x

x

] , [ b a x



j

x

j

y

49

n

nei punti della (n+1)-sima riga. Allora vale il seguente:

Teorema di Faber

Per ogni matrice di interpolazione in un intervallo limitato [a,b], esiste una funzione continua f(x) tale che P

(f)(x) non converge uniformemente a f(x) per n, cioè tale che

Osservazione: f dipende dalla matrice di interpolazione.

0

||

) )(

( )

(

||

lim  _ 



 f x P _n f x

n

50

Osservazione

Il teorema di Faber consente di concludere che:

scelti i nodi di interpolazione, quando si vuole utilizzare

l’interpolazione polinomiale per approssimare funzioni

continue accade sempre che, per almeno una qualche

funzione particolare, pur aumentando i punti di

interpolazione (e quindi il grado del polinomio), la

distanza tra la funzione ed il polinomio non tende a

zero.

51

Non tutto è però cosi’ negativo… Vale infatti il seguente

Teorema

Se f(x) è una funzione continua su [a,b], si può scegliere

una matrice di interpolazione in modo tale che la

corrispondente successione di polinomi di interpolazione

converga uniformemente a f(x) su [a,b].

52

Osservazione

Segue dal precedente teorema che, se si deve approssimare

una funzione continua tramite un polinomio di

interpolazione, è sempre possibile scegliere in maniera

opportuna la matrice di interpolazione in modo tale che, al

crescere del numero dei nodi (e quindi del grado del

polinomio), la distanza tra la funzione ed il polinomio

interpolante tenda a zero. Si osservi che la matrice di

interpolazione non è fissata a priori (infatti vale anche il

Teorema di Faber…), ma dipende dalla particolare

funzione continua da approssimare.

53

Siano dati n+1 punti distinti, x

, x

, …,x

, dell’intervallo chiuso e limitato [a,b] in R. Sia f(x) una funzione assegnata nello spazio C

[a,b] e p(x) il polinomio di grado n tale che

Allora per ogni x[a,b] esiste un valore 

, con



[min(x, x

, x

, …,x

), max(x, x

, x

, …,x

)] tale che

. ,..., 1

, 0 ),

( )

( x f x i n

p





) ( )

)...(

)(

)! ( 1 (

) 1 ( )

( )

( x x

x x

x x

f

x n p x

f x

E   



 





errore di interpolazione, ossia errore che si commette

approssimando il valore della funzione con il valore del polinomio

54

Corollario

Posto M

=max

|f

(x)|, un limite superiore del valore assoluto dell’errore di interpolazione E(x)=f(x)-p(x) risulta essere

Questa formula è molto utile per stimare, ad esempio, il numero di nodi necessari ad ottenere un errore di

interpolazione minore di una data tolleranza massima.

)!

1 ) (

(

| ) )....(

)(

( )! |

1

| ( ) (

|

1 1

1 0

1

 







 



 



n a M

b

x x

x x

x n x

x M E

n n

n

n

55

Sia f(x)=e

. In tal caso, per ogni x[a,b], M

= e

.

Si ettiene che l’errore di interpolazione è maggiorato da

In questo caso si ha la convergenza uniforme poiché

b n

n n b

a

x e

n a b

n a M

b x

E ( 1 )!

) (

)!

1 ) (

(

| ) (

| max

1 1 1

] ,

[ 

 

 

 ^{  }



)! 0 1 (

) lim (

| ) (

| max lim

1

] ,

[





 















b n

b n a

n x

e

n a x b

E

56

Esempio

Sia f(x)=|x| nell’intervallo [a,b]=[-1,1].

La matrice di interpolazione sia costituita da punti equidistanti. In tal caso, per n  non si ha convergenza.

n=5

n=15

-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1 1.2 1.4

polinomio interpolante funzione f(x)

-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

-3 -2.5 -2 -1.5 -1 -0.5 0 0.5 1

1.5

funzione f(x)

polinomio interpolante

57

-6 -4 -2 0 2 4 6

-0.5 0 0.5 1 1.5 2 2.5 3

-6 -4 -2 0 2 4 6

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Sia f(x)=1/(1+x

) nell’intervallo [-a,a], a>5. La matrice di interpolazione sia costituita da punti equidistanti. In tal caso, per n  non si ha convergenza.

n=2

n=10

polinomio interpolante funzione f(x)

funzione f(x)

polinomio interpolante

58

Polinomi di Chebichev (definizione)

• Essi sono polinomi ortogonali in C[-1,1] rispetto alla seguente definizione di prodotto scalare

•Gli n+1 zeri di T

(x) sono interni a (-1,1) e sono dati da

• I polinomi di Chebichev sono definiti mediante l’ortogonalità in [-1,1]. Si estendono a intervalli [a,b]

mediante traslazione e dilatazione.

) ( )

( 2

) (

; )

(

; 1 )

(

1 1

1 0

x T

x xT x

T

x x

T x

T

n n

n

 





[-1,1]

su continue

f(x) e

g(x) ,

) ( )

( )

1 (

2 / 1 1

1

2

f x g x dx

x 





1 1,...n

i per )),

1 (

2 / )

1 2

cos((

,

1

    



i n

z



59

Teorema (Bernstein)

Se f(x)C

([a,b)], ovvero f(x) ha derivata prima continua nell’intervallo [a,b].

Allora il polinomio P

(f) di grado n di interpolazione di f su nodi di interpolazione corrispondenti agli zeri del polinomio di Chebichev di grado n+1 converge uniformemente a f(x) su [a,b] per n, ossia

0

||

) )(

( )

(

||

lim  _ 



 f x P _n f x

n

60

Osservazione

Il polinomio P

(f) di grado n di interpolazione di f sui nodi di Chebichev (ossia sui nodi di interpolazione corrispondenti agli zeri del polinomio di Chebichev di grado n+1), è il polinomio che interpola f(x) negli n+1 punti x

, x

, …,x

seguenti

1 1,...n

i per )),

1 (

2 / )

1 2

cos((

2 / )]

( )

[(

, 1

1 , 1

























n i

z

b a

z a b

x

i n

i n i



61

-6 -4 -2 0 2 4 6

-0.2 0 0.2 0.4 0.6 0.8 1 1.2

-6 -4 -2 0 2 4 6

-0.4 -0.2 0 0.2 0.4 0.6 0.8 1

Sia f(x)=1/(1+x

) nell’intervallo [-a,a], a>0. La matrice di interpolazione sia costituita da punti corrispondenti agli zeri dei polinomi di Chebichev. In tal caso, per n  si ha convergenza uniforme.

n=3

n=11

polinomio interpolante funzione f(x)

funzione f(x)

polinomio interpolante

62

Osservazione

Gli zeri del polinomio di Chebichev si infittiscono ai bordi dell’intervallo [a,b].

Da un punto di vista euristico, ciò consente di avere

maggiori informazioni vicino agli estremi dell’intervallo

[a,b] di interpolazione. In tal modo si evitano le oscillazioni

agli estremi presenti nell’interpolazione polinomiale della

funzione di Runge con nodi equidistanti.