1

INTERPOLAZIONE

Quali condizioni si possono richiedere sulla funzione interpolante ?

Quali condizioni si possono richiedere sulla funzione interpolante ?

Problema generale di INTERPOLAZIONE

Dati n punti distinti (xi,yi)i=1,..,n

si vuole costruire una funzione f(x)

tale che nei nodi (xi)i=1,..n

soddisfi a certe condizioni, dette

Condizioni di interpolazione

2

Esempio 1

condizioni di interpolazione:la funzione deve passare per i punti assegnati

in ciascun nodo xi è assegnata una condizione sulla funzione interpolante

x1 x2 xn…y1 y2 y2

Interpolazione di Lagrange

3

Interpolazione di Lagrange: formulazione generale

Sia F uno spazio di funzioni di variabile reale o complessa.

Assegnati:• n valori distinti reali o complessi {xi} i=1,..n

• n valori distinti reali o complessi {yi} i=1,..n

Si cerca una funzione f(x)∈F tale che:

f(xi)=yi i=1,…,n

Condizioni di interpolazione di Lagrange

Esempio 2

condizioni di interpolazione:la funzione deve passare per i punti assegnati

con una fissata tangente

4

N.B.….se è assegnata in un nodo la condizione sulla derivata di ordine q, deve essere assegnata anche la condizione sulle

derivate dall’ordine 0 fino a q-1.

y1ny1

n-1…y12y1

1

y0ny0

n-1…y02y0

1

y32

xn

y2n-1

xn-1

…y22

x2x1

In ciascun nodo sono assegnate condizionisulla funzione f(x) e sulle sue derivate….

Interpolazione di Hermite

Interpolazione di Hermite: Formulazione generale

Sia F uno spazio di funzioni di variabile reale o complessa.

Si cerca una funzione f ∈F tale che:

f(j)(xi)=yji i=1,…,n j=0,1,…,l i-1

Condizioni di interpolazione di Hermite

n numeri interi {li} i=1,..n tali che Σ ni=1 li = m+1

n valori distinti reali o complessi {xi}i=1,..n

m+1 valori distinti reali o complessi {yji} i=1,…,n

j=0,1,…,li-1

Assegnati

5

In ciascun nodo c’è almeno una condizionesulla funzione o sulla derivata di

qualunque ordine

y1n…y1

1

y0ny0

n-1…y02y0

1

y32

xn

y2n-1

xn-1

…y22

x2x1

Interpolazione di Hermite-Birkoff

….quale forma può avere una

funzione interpolante

?

….quale forma può avere una

funzione interpolante

?

OVVERO:

quale spazio di funzioni Futilizzare

?

OVVERO:

quale spazio di funzioni Futilizzare

?

6

Esempio

-0.97

3

-1.58

π/2

-0.39

π/3

-0.31

-1

1.08

-π/2

y 0.41

-2x

-0.97

3

-1.58

π/2

-0.39

π/3

-0.31

-1

1.08

-π/2

y 0.41

-2x

Interpolazione mediante polinomio di quinto grado

7

-0.97

3

-1.58

π/2

-0.39

π/3

-0.31

-1

1.08

-π/2

y 0.41

-2x

Interpolazione mediante polinomio trigonometrico di quinto grado

un confronto ……

Quale funzione scegliere ?

8

• dal costo computazionale relativo alla costruzione ed alla valutazione della funzione interpolante

la scelta della forma della funzione interpolante ovvero

la scelta dello spazio F dipende :

• dalle caratteristiche del problema reale

In generale,

….fissiamo

lo spazio dei polinomi ….fissiamo

lo spazio dei polinomi

…. Costruiamo il polinomio interpolante di Lagrange

…. Costruiamo il polinomio interpolante di Lagrange

….è unico ?

9

Esempio: Siano P1, P2 due punti fissati.

Esistono infinite parabole per P1, P2

Ma una sola retta per P1, P2

dati i due punti che grado deve avere il polinomio affinché la curva

interpolante sia univocamente determinata?

dati i due punti che grado deve avere il polinomio affinché la curva

interpolante sia univocamente determinata?

10

2) Per m =1 (in generale m=n-1 )

Esiste un unico polinomio di grado 1 interpolante i due punti( esiste un’unica retta passante per due punti )

1) Per m < 1 (in generale m< n-1 )

Non esiste alcun polinomio interpolante ( tranne se i due punti hanno la stessa ordinata )

3) Per m > 1 (in generale m >n-1 )

Esistono infiniti polinomi di grado maggiore di 1 interpolanti i due punti

( esistono infinite parabole, cubiche , etc. per due punti )

Quindi...

Teorema

Dati n nodi distinti {xi} i=1,..nn valori corrispondenti {yi} i=1,..n

il polinomio p(x)∈Πm tale che:

p(xi) = yi i=1,…,n

è unico se:m = n-1

11

Siano p(x), q(x) ∈Πn-1 tali che:

p(xi) = yi i=1,..nq(xi) = yi i=1,..n

Dimostriamo che i due polinomi sono identicamente uguali. Posto:

z(x) = p(x)- q(x) (z(x) ∈Πn-1 )

Si ha:z(xi) = 0 i=1,..n

1/2

Dimostrazione 1

1)Se z(xi) = 0 i=1,..n ⇒ il polinomio ha n zeri distinti⇓

z(x) =a(x- x1) (x- x2)… (x- xn) a∈ℜ

2) Un polinomio non nullo di grado al più n-1 ha al più n-1 zeri distinti

(Teorema fondamentale dell’algebra)

3) L’unico polinomio al più di grado n-1 che ha n zeri distinti è il polinomio identicamente nullo

z(x) è il polinomio identicamente nullocioè p(x)=q(x)

2/2

12

Dimostrazione 2

Se p(x) ∈Πn-1 è il polinomio interpolante gli n punti:(xi, yi ) i=1,..n

dovendo soddisfare le condizioni di interpolazionep(xi) = yi i=1,..n

⇓a0 + a1x1 +…+ an-1x1

n-1 =y1………………………………………………………………a0 + a1xi +…+ an-1xi

n-1 =yi………………………………………………………………a0 + a1xn +…+ an-1xn

n-1 =yn

Sistema lineare di dimensione n

1/4

La matrice dei coefficienti di questo sistema è:

Matrice di Vandermonde

2/4

=

−

−

−

1

122

111

...1............

...1

...1

nnn

n

n

xx

xxxx

V

∏>=

−=n

jij

ji xxV1

)()det(

13

Esistenza ed unicità del polinomio

Dimostriamo che il sistema ammette una ed una sola soluzione

Esistenza ed unicità della soluzione del sistema lineare

3/4

4/4

Poiché i nodi sono a due a due distinti alloradet(V)≠0

Esiste un’unica soluzione

c.v.d

Il sistema è non singolare

14

….quali condizioni garantiscono

l’unicità del polinomio

interpolante di Hermite?

….quali condizioni garantiscono

l’unicità del polinomio

interpolante di Hermite?

ESEMPIO 6 Traiettoria di una pallottola

Una pallottola è sparata vero l’alto dalla sommità di un edificio alto 100 m. Dopo 10 sec. dal lancio la pallottola raggiunge la

massima altezza a 590 . Disegnare la traiettoria della pallottola.

QQ11(0,100)(0,100)

QQ22(10,590)(10,590)

15

Come costruire la parabola che descrive la

traiettoria della pallottola ?

Come costruire la parabola che descrive la

traiettoria della pallottola ?

L’espressione della parabola è p(x) = axL’espressione della parabola è p(x) = ax2 2 + + bxbx + c+ c

Q1 (0,100)

•Q2 (10,590)

Sappiamo che p(0)=100Sappiamo che p(0)=100p(10)=590p(10)=590

Sappiamo inoltre che il punto Q2 è il vertice della parabola

Possono esistere Possono esistere Più parabole…Più parabole…

Esiste una sola Esiste una sola parabola…parabola…

I condizione

II condizione

III condizione

16

p(xp(x11)=y)=y11

p(xp(x22)=y)=y22

p’(xp’(x22)=0)=0

Si ottiene il sistema …Si ottiene il sistema …

2ax2ax22+b=0+b=0

axax222 2 + bx+ bx22 + c=y+ c=y22

axax112 2 + bx+ bx11 + c=y+ c=y11

c=100100 a + 10 b + 100=59020a+b=0

b=88b=88c=100c=100

a=4.4a=4.4

UNICA SOLUZIONE

Interpolazione di Hermite

n=2 nodi ( 2 punti per cui deve passare la parabola)

m=3 nodi condizioni di interpolazione(appartenenza dei due punti alla parabola + vertice nel primo)

# condizioni =

# incognite

17

TEOREMA

Dati n nodi distinti {xi} i=1,..nn numeri interi positivi {li} i=1,..n tali che

Σ ni=1 li = m+1

ed m+1 valori {yji} con i=1,…,n j=0,1,…,li-1

Il polinomio p (x) ∈ Πq tale che:

p(j)(xi)=yji

è unico se:q = m

Siano p(x), q(x) ∈Πm tali che:

p(j) (xi) = yji i=1,..n j=0,1,…,li-1

q(j) (xi) = yji i=1,..n j=0,1,…,li-1

dimostriamo che i due polinomi sono identicamente uguali. Posto:

z(x) = p(x)- q(x) (z(x) ∈Πm )

dimostriamo che z(x) è un polinomio identicamente nullo. Si ha:

z(j) (xi) = 0

1/2

Dimostrazione

18

Un polinomio z∈Πm tali che:

z(j) (xi) = yji i=1,..n j=0,1,…,li-1

È necessariamente del tipo:

z(x) =a(x- x1)l1 (x- x2) l2 … (x- xn) ln a∈ℜ

Cioè ammette n zeri distinti x1 x2 … xn rispettivamente con molteplicità :

l1 , l2 ,… ,lnPoiché Σ n

i=1 li=m+1 e siccome z(x) ha la più grado m, z(x) è necessariamente il polinomio identicamente nullo.

c.v.d2/2

In generale…

Se poniamo F = Πmspazio dei polinomi di

grado al più m

Interpolazione polinomiale

di Lagrange di Hermite

19

Sia per l’interpolazione di Lagrange

che per l’interpolazione di Hermite

# condizioni =

# incognite

l’unicità

della soluzione è garantita

Metodi costruttivi del polinomio interpolante di

di LAGRANGE

20

p(x) ∈Πn-1 è p(x)= a0 + a1x +…+ an-1xn-1

METODO DEI COEFFICIENTI INDETERMINATI

Imponendo le condizioni di interpolazionep(xi) = yi i=1,..n

a0 + a1 x1 +…+ an-1 x1 n-1 =y1

a0 + a1 x2 +…+ an-1 x2 n-1 =y2

a0 + a1 xn +…+ an-1 xnn-1 =yn

……………………………

Sistema di equazioni lineari di ordine n

p(x1) = y1

p(x2) = y2

p(xn) = yn

…..…..

La matrice dei coefficienti di questo sistema è:

=

−

−

−

1nnn

1n22

1n11

x...x1............

x...x1x...x1

V ∏>=

−=n

ji1j

ji )x(xdet(V)

Matrice di Vandermonde( mal condizionata!)

21

Formula di Lagrange

Esempio: Siano Esempio: Siano P1(x1,y1), P2(x2,y2) punti del piano.punti del piano.Costruiamo il polinomio Costruiamo il polinomio p(x) interpolante interpolante P1, P2 ..

Poniamo Poniamo p(x) =y1 l1 (x) + y2 l2(x) con lcon l11(x), l(x), l22(x)(x)ppolinomi olinomi ddi primo grado.i primo grado.

Di che tipo devono essere i polinomi lDi che tipo devono essere i polinomi l11(x) e l(x) e l22(x)?(x)?

ll11(x)= a (x(x)= a (x--xx22))ll22(x)= b (x(x)= b (x--xx11))

ll11(x(x11)= a (x)= a (x11--xx22) =1) =1ll22(x(x22)= b (x)= b (x22--xx11)=1)=1

ll11(x(x11)=1)=1ll22(x(x22)=1)=1

11

11

ll11(x(x22)=0)=0ll22(x(x11)=0)=0

00

00

a=1/(xa=1/(x11--xx22))b=1/(xb=1/(x22--xx11))

p(xp(x11) = y) = y11 ll11 (x(x11) + y) + y22 ll22(x(x11) = y) = y11

p(xp(x22) = y) = y11 ll11 (x(x22) + y) + y22 ll22(x(x22) = y) = y22

Dalle condizioni di interpolazione

22

)x(x)x(xy

)x(x)x(xyp(x)

12

12

21

21 −

−+

−−

=

IN GENERALEIN GENERALE: :

Cioè:Cioè:

(x)ly...(x) ly(x) lyp(x) n n2211 +++=

i i --mo polinomio mo polinomio fondamntalefondamntaledi di LagrangeLagrange

FORMULA DI FORMULA DI LAGRANGELAGRANGE

∏≠= −

−=

n

ij1j

ji

ji )x(x

)x(x(x) l

con

Complessità computazionale della formula di Lagrange

∏≠= −

−=

n

ji1i ji

ii )x(x

)x(x(x)l )12)(1( MAn +−

∑=

=n

1iii (x)lyp(x) [ ]MMAnn ++− )12)(1(

complessità computazionale di un polinomio fondamentale di Lagrange

complessità computazionale della formula di Lagrange

)O(n(n)T 2=

23

zyx ii ),(

nodi punto divalutazione

)(zp

valore del polinomio in z

formula diLagrange

Complessità computazionale

)O(n(n)T 2=

E se si vuolecambiare il punto di

valutazione z ?

Formula di Lagrange

Osservazione

(x)ly...(x) ly(x) lyp(x) n n2211 +++=

La formula di Lagrange

valuta il polinomio contemporaneamente alla sua determinazione

cambiare punto divalutazione

Rifare tutti i calcoli(Complessità computazionale

))O(n(n)T 2=

24

MAse si conoscessero i coefficienti,quanto costerebbe valutare il polinomio?

L’algoritmo di Horner valuta un polinomiocon una complessità T(n)=O(n)

Obiettivo:Separare il calcolo dei coefficienti

del polinomio di Lagrangedalla valutazione del polinomio stesso

FORMULA DI NEWTONFORMULA DI NEWTON

xx11

yy11

Assegnato il punto P1=(x1,y1)Qual’e’ il polinomio P(0)(x)= a0 di grado 0

che interpola P1 ?

Imponendo la condizione di interpolazione P(0)(x1)= y1

a0 = y1 P(0)(x)= y1

25

P(0)(x)=y1

Assegnato ora il punto P2=(x2,y2)

((xx22, y, y22))

Qual’e’ il polinomio P(1)(x) di grado 1che interpola P2 (oltre che P1 ) ?

P(1)(x) = P(0)(x) + a1 (x-x1) = y1+a1 (x-x1)

incognita

Determiniamo a1 imponendo che la retta passi oltre che per (x 1,y1 ) anche per (x2,y2):

12

121 xx

yya−−

=y2 = P(1)(x2) =y1+a1(x2-x1)

)x(xa a(x)P 110(1) −+=

con

12

12110 xx

yyaya−−

==

26

P(2)(x) = P(1)(x) +a2 (x-x1)(x-x2) = a0+a1 (x-x1) +a2 (x-x1)(x-x2)

incognita

Qual e’ il polinomio P(2)(x) di grado 2che interpola P3 (oltre che P1 e P2 )?

P(1)(x)=y1+a1 (x-x1)

Assegnato ora il punto P3=(x3,y3)

((xx33, y, y33))

Determiniamo a2 imponendo che la retta passi oltre che per (x 1,y1 ) e (x2,y2) anche per (x3,y3):

)x)(xx(xa)x(xa a(x)P 212110(1) −−+−+=

con

12

12110 xx

yyaya−−

==23

12

12

13

13

2 xxxxyy

xxyy

a−

−−

−−−

=

y3 = P(2)(x3) =y1 + a1 (x-x1) +a2 (x-x1)(x-x2)

23

12

12

13

13

2 xxxxyy

xxyy

a−

−−

−−−

=

27

il polinomio P(k-1) interpolante k punti (xi,yi) i=1,…,k a partire

dal polinomio P(k-2) interpolante k-1 punti (xi,yi) i=1,…,k-1

FORMULA DI NEWTONFORMULA DI NEWTON

IDEA: costruire

P(k-1)(x) = P(k-2)(x) + Q(x) k=1,2,....

con Q(x) = ak-1 (x-x1)(x-x2)...(x-xk-2) e P(0)(x)= y1

FORMULA DI NEWTONFORMULA DI NEWTON

P(x)=a0+a1(x-x1)+…+an-1(x-x1)…(x-xn-1)

12

121

10

xxyya

ya

−−

=

=

23

12

12

13

13

2 xxxxyy

xxyy

a−

−−

−−−

=

OsservazioneI coefficienti del polinomio

dipendono solo dai nodi di interpolazione:

In generale come calcolare ak ?

28

Definizione:

[ ]12

1221 xx

yyx,xy−−

=

differenza divisa del primo ordine

[ ] [ ] [ ]1k

1-k21k32k21 xx

xx,xyxx,xyxx,xy−

−=

,...,,...,,...,

differenza divisa di ordine k-1

Proprietà fondamentale delle differenze divise:

Esempi:

[ ] [ ]12,21, xxyxxy = [ ] [ ]123321 x,x,xyx,x,xy =

Detta k21 i,...,i,i una permutazione degli indici 1,2,..,k

[ ] [ ]k21 i,...,i,ik2,...,1, xxxyxxxy =

non è importante l’ordine con cui vengono interpolati i nodi

29

Teorema:

Dati n nodi distinti {xi} i=1,..nn valori corrispondenti {yi} i=1,..n

DettoP(x)=a0+a1(x-x1)+…+an-1(x-x1)…(x-xn-1)il polinomio interpolante di Lagrange

ak = y[x1x2…xk-1] k=0,1,..,n-1

i coefficienti del polinomio di Lagrangesono differenze divise

Dimostrazione (per induzione)

Siano:

• P(k-1)(x) polinomio interpolante i nodi x1,x2,…,xk

P(k-1)(x) = P(k-2)(x) + y[x1… xk](x-x1)…(x-xk-1) P(k-1) ∈∏k-1

• Q(k-1)(x) polinomio interpolante i nodi x2,…,xk+1

Q(k-1)(x) = Q(k-2)(x) + y[x2… xk+1](x-x2)…(x-xk) Q(k-1) ∈∏k-1

(per ip. di induzione)

(per ip. di induzione)

30

Consideriamo il polinomio:

k1k

1)-(k1k

1)-(k1

xx(x))Px(x(x)Q)x(xR(x)

−−−−

=+

+ R(x) ∈ ∏k

Poiché R(xi)=yi i=1,…,k+1

( R(x) interpola i nodi x1, x2,…, xk+1)

Per l’unicità del polinomio interpolante

R(x) = P(k)(x)

per il principio di identità dei polinomi

coefficiente di

grado massimo di P(k) (x)

coincide

coefficiente di

grado massimo di R(x)

11k

k11k2k xx

]...xxy[]...xxy[a−−

=+

+

[ ]1k1 x,...,xy +=

31

nodo 1 x1 y1

Algoritmo costruttivo delle differenze divise

nodo 5 x5 y5 y[x1 x5] y[x1 x2 x5] y[x1 x2 x3 x5] y[x1x2x3x4x5]

nodo 4 x4 y4 y[x1 x4] y[x1 x2 x4] y[x1 x2 x3 x4]

nodo 3 x3 y3 y[x1 x3] y[x1 x2 x3]

nodo 2 x2 y2 y[x1 x2]

a0

a1

a2

a3

a4

Complessità computazionale della formula di Newton

calcolo di a1 1 differenza divisa

calcolo di a2 2 differenze divise

calcolo di a3 3 differenze divise

calcolo di an-1 n-1 differenze divise

Totale = 1 + 2 +....+ n-1 = n(n-1)/2 differenze divise

( ) )( 2nO=+−

= 1M2A2

1)n(nT(n)

32

E se si vuolecambiare il punto di

valutazione z ?

Formula di Newton)y,(x ii

nodi

formula diNewton

)O(n(n)T 2=

coefficienti

p(z)valore del

polinomio in z

punto divalutazione

algoritmo diHorner

z

O(n)(n)T =Solo algoritmo

di HornerO(n)(n)T =

E se si vuole aggiungere un nodo?

nodo 1 x 1 y1

nodo 5 x5 y5 y[x1 x5] y[x1 x2 x5] y[x1 x2 x3 x5] y[x1x2x3x4x5]

nodo 4 x4 y4 y[x1 x4] y[x1 x2 x4] y[x1 x2 x3 x4]

nodo 3 x3 y3 y[x1 x3] y[x1 x2 x3]

nodo 2 x2 y2 y[x1 x2]

nodo 6 x6 y6 y[x1 x6] y[x1 x2 x6] y[x1 x2 x3 x6] y[x1x2x3x4x6] y[x1x2x3x4 x5x6]

a5

calcolo del solo coefficiente a5 T(n)=O(n)

33

Algoritmo di Horner per la valutazione dei polinomi

Si vuole valutare un polinomio p(x) di grado n in un punto z.

Esempio:

p(x) = a0 + a1 x + a2 x2 + a3 x3 + … + an xn

Idea dell’algoritmo

L’algoritmo si basa sull’idea di calcolare il valore del polinomio

nell’indeterminata x, mediante successive messe in evidenza.

34

Un polinomio di grado 3

P(x)=a3 x3 + a2 x2 + a1 x + a0

può scrivere nella forma:

(a3 x2 + a2 x + a1) x + a0

e ancora come:

((a3 x + a2) x + a1) x + a0 .

Esempio

Da cui si ricava una semplice relazione per ricorrenza:

y1 = a3 * x;y2 = y1 + a2;y3 = y2 * x;

y4 = y3 + a1;y5 = y4 * x;

y6 = y5 + a0;

35

p(x)= an xn + … + a3 x3 + a2 x2 + a1 x + a0

avremo:

y1 = an * x;y2 = y1 + an-1;

…yn-1 = yn-2 * x;yn = yn-1 + a0.

In generale

function p=valnewton(a,x,xval)n=length(x);nval=length(xval);p=a(n)*ones(1,nval);for i=n:-1:1p=p.*(xval-x(i))+a(i);

end

In matlab