Riassunto esame Calcolo Numerico e programmazione, prof. Putti

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)

( −3)(x −5)( −1

1 2 3 3 2

Esempio: L x x x−90)

(x)= = = ( −14 +63

0 x x 12

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

0 1 0 2 0 3

Quale errore si commette tramite tale approssimazione? f

:ℝ→ℝ∣y x

Assumo che : se esiste la funzione f, allora vale: .

| |

ε = (x )−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)

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

n +1 .

grG=n

∃η∈I ∣G (η)=0,

x

Alla n+1 – 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 (η)

n+1 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 ”.

∈I η

0 x

(per la dimostrazione del risultato, vedi “ Errore di Lagrange ”)

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: , per

e =[a ],a>

x n+1

| |

F (t) ≤h

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

Ma vale anche la relazione , dove è la costante di

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

n j j n

x∈ I x

Lebesgue. lim

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

Λ =+∞

n

n→+∞

per n piccolo! Fenomeno di Runge

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

1

y=f x)= I

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

( =[−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!

Interpolazione Polinomiale - Differenze Divise di Newton

Dati n + 1 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:

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

i ( ) ( ) (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

, 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 6, x

( )=f ( )= =

3, x x−6

−x−3

tabella. n

∏

C=f , x , x x−x

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

(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

1 1 1 1 4 2

f , f , f

Esercizio: Dati ( )= ( )= ( )=

4 2 9 3 9 3

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:

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

i ( ) ( )

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

1 1 1 1

P x)= x x−

(x)=P ( +1.2( − )−1.028571(x− )( )

n 2 2 4 4 9

1 1 1 1 1 1 1 1

P

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

2 5 2 5 4 5 4 5 9

1 1

f

√

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

f x)= x ( )=

(

vera 5 √ 5

1 1 ...

ε( )= −0.4445714=0.00264

5 √ 5

1

Cerco una maggiorazione di .

ε( )

5 n

| |

+1 | | 1 1 4

f f ' ' '

(t) (η)

F( t) F F( x x− x−

Per Lagrange, , con :

| | | |

ε ≤max ⋅ = (x) ⋅ )=( )( )(x− )

| |

max 4 9 9

3 !

(n+1)!

t ∈I x 3 1 1

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

poiché non conosco e , approssimo il valore di ,

( ⋅ (η)≃f ( )

η 8 9

2 √

x x

1

x= max f ' ' '( x

poiché per ho il valore massimo di .

| |

)

9 x∈ I x

19 1

| |

F f ' ' '(

Vale quindi: | |

ϵ ≤max (x )

⋅ )

⋅

| |

max 3 !

F F F '( x

Ma , e la derivata prima di F vale:

| | | |

(x) =max (x) ⇒ )=0 √ 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

19 1 91.125

| |

F( x f ' ' '

| |

ε ≤max )

⋅ ( )

⋅ =0.0023197⋅ =0.0352285

| |

max 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

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 .

[ ( )− ]

n i i d P y

Si analizza la quantità , diversa

[ (x )− ]

n i i

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

diversi a seconda del metodo che si utilizza.

Metodo dei Minimi Quadrati

, y

Dati n punti , si vuole valutare

(x ) n

∑ 2

P d , con d= y .

(x)∣d=min [P (x )− ]

n n i i

i=1

Si può applicare il metodo considerando solo x esatto, oppure considerando solo y 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

Risolvere il sistema equivale a risolvere l'equazione matriciale:

( ) ( )

n n

∑ ∑

n x y

( )

i i

a

i=1 0 i=1

=

n n n

a

2 1

∑ ∑ ∑

x x x y

i i i i

i=1 i=1 i=1

A , A , A

Definiamo le matrici :

1 2

( ) ( ) ( )

n n n n

∑ ∑ ∑ ∑

n x y x n y

i i i i

i=1 i=1 i=1 i=1

A= A A

= =

1 2

n n n n n n

∑ ∑ ∑ ∑ ∑ ∑

2 2

x x x y x x x y

i i i i i i i i

i=1 i=1 i=1 i=1 i=1 i=1

Per la Regola di Cramer, vale quindi: detA detA

1 2

a a

= =

0 1

detA detA

detA detA

1 2

Il polinomio approssimatore diventa quindi: P x= x

(x)=a +a +

1 0 1 detA detA

Nel caso si pong