Calcolo numerico:

Analisi Numerica

(R. BROGLIA)

Ingegneria Meccanica

Anno Accademico 2003-04

Libri di Testo:

• L. Gori: Calcolo Numerico, (IV Ed.) Ed. Kappa, 1999

• L. Gori, M.L. Lo Cascio: Esercizi di Calcolo Numerico, (II Ed.) Ed. Kappa, 1999

• A. Quarteroni, F. Saleri: Introduzione al Calcolo Scientifico, Springer, 2002

Sito internet:

• Dipartimento MeMoMa: http://www.dmmm.uniroma1.it (corsi, laurea triennale,….)

• Home page: http://www.dmmm.uniroma1.it/~broglia

Contatti:

Riccardo Broglia Tel: 06.50299297

[email protected]

Calcolo numerico:

nozioni introduttive

Calcolo numerico: generalità

Cosa si intende per calcolo numerico?

Per calcolo numerico si intende quella branca della matematica che studia e sviluppa modelli e metodi al fine di risolvere tramite algoritmi numerici imple-

mentati in un calcolatore, problemi matematici.

Calcolo numerico: errori

Problema Fisico

Ipotesi semplificative (errori inerenti)

Modello Matematico

⇓

Know out, fantasia e arte (errori di troncamento)

⇓

Modello Numerico

Algoritmo (stabilità) e computer (errori di arrotondamento)

⇓

Soluzione Numerica

(errore computazionale)

La soluzione numerica può essere accettata se e solo se si ha una stima degli errori di cui è certamente affetta

Errore computazionale: definizioni

Err. computazionale: è la somma degli errori di troncamento e di arrotondamento, argomenti di interesse fondamentale dell’analisi numerica.

Err. troncamento: è dovuto al passaggio dal continuo al discreto.

Err. arrotondamento: è dovuto dalla precisione finita dei calcolatori, così come la sua propagazione.

Detta x la soluzione approssimata e x^* quella esatta:

Errore assoluto x*

x − ε =

( )





=

⋅

−

=

=

% 100

/

/ ^{* * *}

r r

r x x x x

ε ε

ε

ε

Errore di arrotondamento: propagazione

) ,

...

, ,

(x₁ x₁ x_n f

Y = Calcolo di una funzione:

Nel caso di funzione di una variabile:

) (

)

( ^*

* f x f x

Y

Y − = −

Sviluppando in serie la f(x^*) nell’intorno di x:

(

)

*) ( ) ( ) ( )

(x f x f x x x O x x x

f

x

x − + ∆ = −

+

≈

−

=

∆

ε 3ε

2 1 Sostituendo:

) ( )

( )

( )

( ²

* xf x O x f x f x

Y

Y − = ∆ _x + ∆ ≤ ε _x = ε _x

Errore di arrotondamento: propagazione

Formula generale di propagazione degli errori:

) (x f

Y ≤ ε _x

∆

Nel caso di funzione di più variabili:

) ,

...

, ( )

, ...

,

( _{1 1}

1 fx₁ x xn n fx x xn

Y ≤ ε + + ε n

∆ L

* i i

i = x − x

ε Errore sul dato i-esimo

Esercizio: esprimere l’errore commesso per le operazioni di somma algebrica (cancellazione numerica), prodotto e

rapporto tra due valori.

Propagazione: esempio

Esempio 1.4.1:

4 2

2

4 1

1

10 5

. 0 1233

. 0

10 5

. 0 1234

. 0

−

−

⋅

≤

=

⋅

≤

=

ε ε

x x

0001 .

) ,

(x₁ x₂ = x₁ − x₂ = f

% 100 10 1

10

4 4

2 1

2

1 = = ⇒ =

−

≤ +

∆

−

−

x r

x Y

Y ε ε ε

• Esercizio consigliato [G] 1.4.2

Propagazione: esempio

Esempio:

( )

1 7

21 35

35 21

7 )

(

1 )

(

2 3

4 5

6 7

2

7 1

− +

− +

− +

−

=

−

=

x x

x x

x x

x x

f

x x

f

Le due funzioni sono identiche in senso algebrico;

calcolo di f₁(x) e di f₂(x) per x∈[0.9998,1.0002]:

>>x=linspace(0.9998,1.0002,100)

>> f1=(x-1).^7;

>> f2=x.^7-7*x.^6+21*x.^5-35*x.^4+35*x.^3-21*x.^2+7*x-1;

>> plot(x,f1)

>> plot(x,f2)

Propagazione: esempio

0.9998 0.9999 1 1.0001 1.0002

-1.5 -1 -0.5 0 0.5 1

1.5x 10^-26

0.9998 0.9999 1 1.0001 1.0002

-1.5 -1 -0.5 0 0.5 1

1.5x 10^-14

f

(x) f

(x)

( )

1

( x ) = x − 1

f

Propagazione: condizionamento

Consideriamo il calcolo di una funzione y=f(x); e valutiamo quale è l’effetto sul risultato finale di una perturbazione ∆x=x-x^* del dato di input:

) (

) ) (

( f x

x x f

Y x Y

f x

Y ′

∆

∆ ≤

′ ⇒

∆

≤

∆

x C x

x f

x f

x x

x Y

Y

p

= ∆

∆ ′

∆ ≤

) (

) (

C_p: numero di condizionamento del problema

Propagazione: condizionamento

) (

) (

x f

x f

C_p x ′ x =

C x Y

Y

p

≤ ∆

∆

Se C_p è “grande” il problema è mal condizionato, ossia a piccole perturbazione dei dati iniziali si hanno grandi varia- zioni dei risultati. Viceversa se C_p è “piccolo”, il problema è ben condizionato.

Il condizionamento non dipende dall’algoritmo usato, dipen- de dal problema (f(x)) e dipende dai dati di ingresso (x). Un problema può essere ben condizionato per certi valori di input e mal condizionato per altri.

Condizionamento: esempio

Esempio 1.5.1:





−

−

=

=

−

=

⇒ =





= +

= +

≠ ( ) /(1 )

) 1

/(

1 )

( 0

1

2 2

) 1

( ² α α α

α α

α

α

α z g

f y

z y

z y

2 2

1 1 )

(

) (

α α α

α α

−

= +

= ′

g C_z g

2 2

1 2 )

(

) (

α α α

α α

= −

= ′

f C_y f

Il problema del calcolo di y e z è mal condizionato per valori di α prossimi ad 1.

Condizionamento: esempio

1.0 1.0

1.0 10^-4 -2499.75

2500.25 0.9998

-4999.75 5000.25

0.9999

3.4 10^-4 1.6 10^-4

1.8 10^-4 -0.803145670

1.446067105 0.5554

1.446299444 y

-0.803419341

z |∆y/y|

0.5555

|∆z/z|

|∆α/α|

α

Esercizio: stimare il condizionamento del problema del calcolo della y e della z nei due casi.

Algoritmo: definizione

Il problema numerico è risolto tramite un algoritmo:

ossia una successione di operazioni logiche e aritme- tiche finita e non ambigua, che consente di ottenere il risultato numerico a partire dai dati di input.

Stabilità numerica: sensibilità di un algoritmo alla perturbazione dei dati di input. Un algoritmo è detto stabile se gli errori assoluti sui dati non sono ampli- ficati durante l’elaborazione. Viceversa, l’algoritmo è detto instabile.

Stabilità di un algoritmo: esempio

0 lim

, 0 1 ¹ d

0 > =

=

∫

x n

n x e x I I

I e

Esempio 1.6.1:

Integrando per parti:

0 1

1

3 2

1 1

0

1

! ) 1 ( ) 1 (

) 1 (

) 1 ( 1

) )

2 (

1 )(

1 (

1 )

) 1 (

1 ( 1

1 1 d

I n k

n n

n

I n

n n n

I n

n

nI x

e x

n e e

I

n n

k

k

n n

n x

n n

− + +

−

−

− +

=

=

−

−

− +

−

=

−

−

−

=

=

−

 =





=  −

∑

∫

−

=

−

−

− −

L

L Algoritmo

1− ₋1

= _n

n nI

I

...

2856 6321205588

. 0 )

1 1 (

1 ¹ d

0 = − =

= _e

∫

I_o ^x

Con:

Stabilità di un algoritmo: esempio

)

!

!

! (!

10 436

. 3 0

2865 2072766470

. 0

! 3 2 3 3 1

5712 2642411176

.

! 0 2 2

1

7144 3678794411

. 1 0

2856 6321205588

. 0

10 26

25 3 0 2 0 1 0 0

⋅

−

=

=

=

−

⋅ +

−

=

= +

= −

− =

=

=

I I I I I I I I I

M M

0 0.25 0.5 0.75 1

0 0.2 0.4 0.6 0.8 1

n=0

n=1 n=2 n=4

n=26

14 cifre significative

x n

n x e

x e

y 1

) ( =

Stabilità di un algoritmo: esempio

Propagazione dell’errore iniziale ε₀=I₀-I₀^* nel calcolo di I_n? L’algoritmo è lineare, quindi:

0

* 0 0

* 0 0

* ( ) ( ) ( 1) !( ) ( 1) !ε

ε_n = I_n − I_n = f I − f I = − ⁿn I − I = − ⁿn

[ ]

[ ]

1 1

* 0

0 1

0 1

! ) 1 ( )

1 (

) 1 (

) 1 ( 1

) (

! ) 1 ( )

1 (

) 1 (

) 1 ( 1

) (

I n k

n n

n I

f

I n k

n n

n I

f

n n k

k n n

k

k

− + +

−

−

− +

=

− + +

−

−

− +

=

∑

∑

−

=

−

=

L L

Il termine (-1)ⁿn!, rapporto tra l’errore al “passo” n e quello al “passo” 0, è detto coefficiente di amplificazione dell’er- rore iniziale. L’errore cresce con n, l’algoritmo è instabile.

Stabilità di un algoritmo: esempio

L’algoritmo può essere così modificato:

n I I

nI

I_n = − _n− ⇒ _n− = 1− ⁿ

1 _{1 1}

Sapendo che: e posto I^lim_→∞ n ^{= 0} _N=0 per N fissato:

n I

K , 1 1 ,

0 ₁ = − = −

= ₋ k N N

k I I

I_{N k} ^k

Stabilità di un algoritmo: esempio

Propagazione dell’errore:

) 1 (

1 1

1 1

1

* 1 1

2

*

*

* 1 1

1

= −

− −

− =

= −

−

− =

− =

− −

=

−

=

−

−

− −

−

−

−

N N N

N I I

N N

I I

N I N

I I I

N N

N N

N

N N

N N

N N

N N

ε ε ε

ε ε

L’errore si riduce l’algoritmo è stabile.

Esercizio: valutare il valore approssimato di I₀ con N=10 e N=15, stimare l’errore commesso; usare tale algoritmo per valutare I₇. calcolare I₇ a partire da un valore di I₀ accurato alla quarta cifra decimale con il metodo instabile.