Calcolo Numerico e programmazione - Appunti

P

Trovare (x)

n , y P

Ho 4 coppie , quindi devo cercare . Si ha, quindi:

(x ) (x)

i i 3

P y L x)+ y L x)+ y L y L x)

(x)= ( ( (x )+ (

3 0 0 1 1 2 2 3 3

L

Sarà dunque sufficiente calcolare gli .

(x)

i

x−x x−x

( )( )(x−x ) x x−6) 1

(x −3)( −5)(

1 2 3 3 2

Esempio: L (x)= = =− (x −14x +63x−90)

0 x x 2−3)(2−5)(2−6) 12

( −x )( −x )(x −x ) (

0 1 0 2 0 3 28

Quale errore si commette tramite tale approssimazione?

f x

:ℝ→ℝ∣y x

Assumo che : vale, allora, .

ε = ( )−P (x )

| |

∃f =f ( )

i i i i n i

I x ,max t I

Definisco l'intorno e considero un punto ; definisco, infine, la

=[min ( ) (x )] ∈

x i i 0 x

i i

G(t)

funzione : G(t)=f S

(t )−P (t)+ (t )⋅F(t )

n n 0

P (t )−f (t )

n 0 0

con .

S (t )=

n 0 F (t )

0 G(t) n+1

Poiché, per definizione, la funzione ha radici reali, per il teorema di Rolle

(n+1) n

G(t)

, poiché è di grado

∃η∈I ∣G (η)=0

x

n+1

Alla – esima applicazione del teorema di Rolle, si ha:

{ (n+1 )

P (η)=0

n

(n+1)

F n+1)!

(η)=(

(n+1)

G (η)=0 (n+1)

f ( η)

1)

(n+ (n +1) S

Da cui , per cui si ottiene: .

G S ! (t )=−

(t)=f (t)+ (t )⋅(n+1)

n 0 n 0 (n+1)!

G(t)=0

Si ha quindi che per vale: (n +1)

F (t)⋅f (η)

f (t)−P (t )=

n !

(n+1)

t

ma era un punto qualsiasi, quindi anche è “ indipendente ”. (v.Appendice)

∈I η

0 x 29

La formula di Lagrange, teoricamente, funziona bene per polinomi di classe alta: poiché non

conosco , approssimo:

η n+1

∣ ∣

F(t )⋅f (t)

f

∣ ∣

(t)−P (t) ≤max

n !

(n+1)

t ∈I x

−x I , b 0, b>0

Esempio: Data la funzione , per

e =[a ],a>

x n+1

| (t)|≤h

F

n+1

| |

f (t ) ≤1

n+1

h h→0

f 0

| |

(t)−P (t) ≤ →

n n+1)!

( n→+∞

Come valuto la stabilità dell'approssimazione?

̃

y=f , y f

(x) ̃ = (x)

Come mi assicuro che l'errore non sia distruttivo dell'accuratezza del calcolo?

n

~ ~

∑ | |

f f x x

ε(f − )= [f (x )− ( )]⋅L ( )

j j j

j=0

~ ~

| |

f f x f x

Vale la relazione , dove è la costante di Lebesgue.

ε(f − )≤Λ ⋅max ( )− ( ) Λ

n j j n

x∈ I x

lim

Problema: . Si ha, quindi, che l'interpolazione di Lagrange può essere stabile solo

Λ =+∞

n

n→+∞ n

per piccolo! 30

Fenomeno di Runge

Si basa su questa osservazione il cosiddetto fenomeno di Runge: interpolando, ad esempio, la

1

y=f x)=

funzione nell'intervallo , aumentando i punti d'appoggio del

I

( =[−1,1]

x

2

1+25 x

polinomio interpolatore si ottiene una funzione totalmente errata!

Vale infatti la relazione ottenuta: f x

| |

ε(f −P )≤Λ ⋅max ( )−P (x ) → +∞

n n j n j n →+∞

x∈ I x

Non sarà quindi conveniente interpolare la funzione da approssimare con polinomi di grado elevato!

31

Interpolazione Polinomiale - Differenze Divise di Newton

n+1

Dati punti, è possibile valutare il polinomio interpolatore in modo alternativo, studiando una

tabella del tipo:

x y f x , x f , x , x f ... , x

...

( ) (x ) (x )

i i i i i i i+2 0, n

+1 +1

Esempio: Dati i seguenti dati:

i 0 1 2 3

x 2 3 5 6

y 6 17.5 85.5 154

P

Trovare applicando il metodo delle differenze divise.

(x)

n

Costruisco la tabella:

i x y f x , x f x , x , x f , x , x , x

( ) ( ) (x )

i i i i i i i+2 i i i+2 i+3

+1 +1 +1

0 2 6 y y

−

1 0 =11.5

x −x

1 0 34−11.5

1 3 17.5 =7.5

x −x

2 0

y y 11.5−7.5

−

2 1 =1

=34 x −x

x −x 3 0

2 1 68.5−34

2 5 85.5 =11.5

x −x

3 1

y y

−

3 2 =68.5

x −x

3 2

3 6 154 P x)

La sequenza che fornisce i coefficienti di sarà:

(

3

y f x f x x x f x x x

, , ,

(x ) ( ) (x )

0 0, 1 0, 1, 2 0, 1, 2, 3

Il polinomio si otterrà, quindi, nel seguente modo:

P x−x x−x 1⋅(x−x x−x x−x

(x)=6+11.5⋅(x−x )+7.5⋅( )( )+ )( )( )

3 0 0 1 0 1 2

32 , y

Posso, infine, aggiungere un ulteriore fattore tramite un ulteriore punto variabile, calcolare

(x )

y− y f x)−154

(

3 , e calcolare dunque i successivi valori ottenuti nella

f x , x)=f x)=

( (6, =

3 x−x−3 x−6

tabella. n

∏

C=f x , ... , x , x

Il fattore che si ottiene è ed equivale al resto del polinomio

( )⋅ (x−x )

0 n i

i=0

interpolatore di Lagrange: n n+1

f (η)

∏

f , x , x

(x )⋅ (x−x )=F (x )⋅

0,. .. n i !

(n+1)

i=0

Osservo: È possibile interpolare con polinomi di grado maggiore se sono note informazioni sulle

derivate di (v.Appendice) , poiché vale:

f (x) f x – f x f x f

( ) ( ) ( +h)– (x )

i i i i

f x , x ' x

( )= =lim =f ( )

i i i

x – x x h) – x

( +

h →0

i i i i

n x

Note le informazione su derivate di calcolate in , sarà dunque

f x)

( i n

x

sufficiente ripetere nella tabella delle differenze divise il termine per volte.

i

( ) ( ) ( )

14 12 19 13 49 23

f , f , f

Esercizio: Dati = = =

P

1 - Trovare utilizzando la tabella delle differenze divise. È

(x)

n ( ) ( )

1 1

P

2 - Valutare .

≃f

n 5 5

√

3 - Dato , dare una maggiorazione dell'errore.

f x

(x)=

vera

1 – Costruisco la tabella di Newton:

i x y f x , x f x , x , x

( ) ( )

i i i i i i i+2

+1 +1

1 1

0 4 2 1.2

1 1

1 −1.028571

9 3 1

4 2

2 9 3

33

( ) ( )( )

1 1 1 19

P x)= x− x− x

(x)=P ( +1.2 −1.028571 −

n 2 2 4 4

( ) ( ) ( )( )

15 12 15 14 15 14 15 19

P

2 - = +1.2 − −1.028571 − − =0.4445714

2 ( )

15 1

f

√

3 - , quindi valuto , da cui l'errore:

f x)= x =

(

vera √ 5

( )

15 1

ε = −0.4445714=0.00264...

√ 5

( )

15

Cerco una maggiorazione di .

ε n+1

∣ ∣ ∣ ∣

f f ' ' '

(t) (η)

F(t) F F( x

Per Lagrange, , dove la produttoria è

∣ ∣ ∣ ∣

ε ≤max ⋅ =max (x) ⋅ )

∣ ∣

max 3 !

(n+1)!

t t I

∈I ∈

x x

( )( )( ) 3 1

1 1 4

F( x x− x− x− f ' ' ' x)=

: poiché non conosco e , approssimo il

)= ( ⋅

η

4 9 9 8 2 √

x x

( ) 1

1 x=

f ' ' ' ' ' ' f ' ' ' x)

valore di , poiché per ho il valore massimo di .

(η)≃f (

9 9

∣ )∣

( 1 1

F(x f ' ' ' F F x) F ' x

Vale quindi , ma , e la derivata

∣ ∣ | | | |

ε ≤max )

⋅ ⋅ (x) =max ( ⇒ ( )=0

∣ ∣

max 9 3 !

prima di F vale: √ 2

2 522

972 x x −4⋅61⋅972

−522 +61 x

, da cui .

F '( x)= =522±

=0 1,2 2⋅972

324

max F x) F x , F x

Si ha, dunque, , da cui:

| | | | | |

( =max { ( ) ( ) }=0.0023197

1 2

∣ )∣

( 1 1 91.125

F(x f '''

∣ ∣

ε ≤max )

⋅ ⋅ =0.0023197⋅ =0.0352285

∣ ∣

max 9 3 ! 3!

Un metodo alternativo, meno accurato ma comunque corretto, è valutare:

19 1

| |

3

x f ' ' '( ...

| |

ε ≤ −x ⋅ )

⋅ =0.56666

| |

max max min 3!

ATTENZIONE! Alla fine del calcolo, è necessario verificare che valga !

ε ≤C

numerico

34

Approssimazione Polinomiale

L'interpolazione polinomiale funziona molto bene per n piccolo, ma, come abbiamo osservato

tramite il fenomeno di Runge, il polinomio interpolatore rischia di assumere dei valori di minimo o

di massimo assolutamente incompatibili con la funzione interpolata.

P x)

Dati n punti, quindi, si preferisce trovare il polinomio che minimizzi una certa quantità

(

n

d P x y

d P x y . Si analizza quindi ,

[ ( )− ]

[ ( )− ] n i i

n i i

diversa dall'errore, poiché essa può essere definita in

modi diversi a seconda del metodo che si utilizza.

Metodo dei Minimi Quadrati

n x , y

Dati punti , si vuole valutare

( ) n

∑ 2

P d=min d , con d= y .

(x)∣ [P (x )− ]

n n i i

i=1 x

Si può applicare il metodo considerando solo

y

esatto, oppure considerando solo esatto, oppure considerando entrambi i valori affetti da errore.

Per facilitare la comprensione e l'acquisizione dei meccanismo alla base del metodo, si analizzerà il

caso in cui il polinomio sia una retta.

Caso-Esempio – Errore in Y – Scarti Verticali

n n

∑ ∑

2 2

Per definizione, d= y d '=0 , ma d= y , dove i

[P (x )− ] =min ⇒d [a +a ⋅x − ]

1 i i 0 1 i i

i=1 i=1

a a

termini e sono i coefficienti del polinomio di grado 1 .

0 1

Poiché la funzione d è definita secondo due incognite, dovrò quindi utilizzare le derivate parziali:

d

∂d ∂

,

pongo, quindi, : ottengo, dunque, le due equazioni:

=0 =0

∂a ∂a

0 1 { n

d

∂ ∑ a x y

=2 [a + − ]=0

0 1 i i

a

∂ i=1

0 n

d

∂ ∑ x y

=2⋅x ⋅ [a +a − ]=0

i 0 1 i i

a

∂ 1 i=1

{ n n

∑ ∑

n⋅a a x y

+ =

0 1 i i

che equivale al sistema i=1 i=1

n n n

∑ ∑ ∑

2

a x a x x

+ = ⋅y

0 i 1 i i i

i=1 i=1 i=1

35

Risolvere il sistema equivale a risolvere l'equazione matriciale:

( ) ( )

n n

∑ ∑

n x y

( )

i i

a

i=1 0 i=1