Calcolo numerico: generalità

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, III^a edizione Springer, 2006

• M.L. Lo Cascio: Fondamenti di Analisi Numerica, McGraw-Hill, 2008

Sito internet:

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

( , , )

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

Contatti:

Contatti:

Riccardo Broglia Tel: 06.50299297 r broglia@insean it r.broglia@insean.it

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, III^a edizione Springer, 2006

• M.L. Lo Cascio: Fondamenti di Analisi Numerica, McGraw-Hill, 2008

Sito internet:

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

( , , )

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

Contatti:

Contatti:

Claudio TESTA Tel: 06.50299251 c testa@insean it c.testa@insean.it

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: modellizzazione ed errori

Problema Fisico

Astrazione ed ipotesi semplificative

( i i ti)

⇓

Modello Matematico

⇓

Know How, fantasia e arte (errori di troncamento)

Modello Matematico

⇓⇓

Modello Numerico

Algoritmo (stabilità) e computer 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 degli errori di cui è certamente affetta

Errore computazionale: definizioni

• Errore troncamento: è dovuto alla discretizzazione di un di un problema matematico (passaggio dal continuo al

discreto).

• Errore arrotondamento: è dovuto alla precisione finita dei

l l i ì l i

calcolatori, così come la sua propagazione.

• Errore computazionale: è la somma degli errori di

troncamento e di arrotondamento argomenti di interesse troncamento e di arrotondamento, argomenti di interesse fondamentale dell’analisi numerica.

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

Detta x la soluzione approssimata e x quella esatta:

x

x −

ε = x x Errore assoluto

ε ( )

⎬ ⎫

−

=

= /

/

r

ε x x x x

ε

Errore assoluto Errore relativo

⎭ ⎬

=

⋅ 100

%

r

ε

ε Errore relativo

Errore di arrotondamento: propagazione

Calcolo di una funzione: Y = f ( x

, x

, ... , x

) Nel caso di funzione di una variabile:

*

*

( ) (

)

*

f x f x

Y

Y − = −

S il d i i l f(

) ll’i t di

(

)

*

) ( ) ( ) ( )

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

f ≈ + − + Δ ε = −

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 − = Δ

+ Δ ≤ ε

= ε

Sostituendo:

Errore di arrotondamento: propagazione

Formula generale di propagazione degli errori:

) (x f

Y ≤ ε

Δ

Nel caso di funzione di più variabili:

) ,

...

, ( )

, ...

,

(

1

f

x x

f

x x

Y ≤ ε + + ε

Δ L

*

Errore sul dato i-esimo

* i i

i

= x − x ε

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

rapporto tra due valori rapporto tra due valori.

Propagazione: esempio

Esempio 1.4.1:

4 4 1

1 = 0.1234

ε

4 2

2 = 0.1233

ε

0001 .

) ,

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

% 100 10 1

10

4 4 2

1

+ = = ⇒ =

Δ ≤

−

−

x

x Y

Y ε ε ε

2

10

1

− x x

Y

Propagazione: esempio

Esempio 1.4.2: determinare le radici di x²-2ax+b=0 con a>0

2 b ≈ a a 0 a

a x

Se a>>b allora: x₂ = a − a − b ≈ a − a = 0 Se a>>b allora:

Esempio: a=103.25 e b=1.021 eseguendo i calcoli con sette if i ifi i

cifre significative:

005 .

0 021

. 1 ) 25 ( 56 . 10660 25

.

2 =103 − − =

x

Verifica: x₂² − 2ax₂ +b ≈ −0.11510⁻¹ Come ovviare?

00494443 021 0

. 1

2 2

1 = ⇒ = b = ≈

x b

x x

Verifica: x² − 2ax + b ≈ −0 2710⁻⁴

00494443 .

245 0 . 103 25

. 103

2 2 2

1 ≈

= +

−

= +

⇒

=

b a

a x

b x

x

Verifica: x₂ − 2ax₂ + b ≈ −0.2710

Propagazione: esempio

Esempio:

( )

1 7

21 35

35 21

7 )

(

1 )

(

2 3

4 5

6 7

7

1 = −

f

x x

f

1 7

21 35

35 21

7 )

( ^{7 6 5 4 3 2}

2 x = x − x + x − x + x − x + x −

f

Le due funzioni sono identiche in senso algebrico;

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)

>> l t( f2)

>> plot(x,f2)

Propagazione: esempio

1.5x 10^-26

1.5x 10^-14

f

(x) f

(x)

0.5 1

0.5

1

f

( )

0 0

-1 -0.5

-1 -0.5

0.9998 0.9999 1 1.0001 1.0002

-1.5 -1.50.9998 0.9999 1 1.0001 1.0002

( )

1

( x ) = x − 1

f

Propagazione: condizionamento

Consideriamo il calcolo di una funzione y=f(x); e

l i l l ff l i l fi l di

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

Δ ≤ Δ

⇒ Δ

≤

Δ Y f (x )

f

Y Δ Δ

Δ ( )

x C x

x f

x xf

x x Y

Y

p

x

= Δ

≤ Δ Δ

) (

) (

C

: numero di condizionamento del problema p

Propagazione: condizionamento

C x

Y ≤ Δ

Δ xf ( x )

C

C x Y ≤

) (

) (

x f C

= f

Se C_p è “grande” il problema è mal condizionato, ossia a piccole perturbazione dei dati iniziali si hanno grandi varia-

p p g

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 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

⎩ = = − −

⎩ α y + z = 0

_{z g} ( α ) α /( 1 α )

2 2

1 2 )

(

)

( α α

α ^′ ₌

= f

C

f

2

1 1 )

(

) (

α α α

α

α ′ = +

= g C

g

1

)

( α − α

y

f

1 )

( α − α

g

Il problema del calcolo di y e z è mal condizionato

per valori di α prossimi ad 1.

Condizionamento: esempio

α y z |Δα/α| |Δy/y| |Δz/z|

0.5555 1.446299444 -0.803419341 0.5555 1.446299444 0.803419341

1.8 10^-4 1.6 10^-4 3.4 10^-4 0.5554 1.446067105 -0.803145670

0.9998 2500.25 -2499.75

1.0 10^-44 1.0 1.0 0.9999 5000.25 -4999.75

Esercizio: stimare il condizionamento del problema del 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 aritmetiche finita e una successione di operazioni logiche e aritmetiche finita e non ambigua, che consente di ottenere il risultato numerico a partire dai dati di input.

partire dai dati di input.

Oltre alla tendenza del problema a propagare gli errori sui dati bisogna tenere conto che l’uso di un algoritmo di calcolo dati, bisogna tenere conto che l’uso di un algoritmo di calcolo comporta un errore di approssimazione (troncamento dei dati numerici), fornendo un dato finale approssimato f_a(X):

numerici), fornendo un dato finale approssimato f_a(X):

l’errore totale è esprimibile come:

E E

X f X

f X

f X

f X

f X

f

E_f = f_a(X)− f (X^*) = f_a(X)− f (X) + f (X) − f (X^*) = E_a + E_d E = ( )− ( ) = ( )− ( ) + ( ) − ( ) = +

Errore algoritmico

) ( )

(X f X f

E_a = _a −

*) Errore di propagazione sui dati

( )

(X f X ^* f

E_d = −

Stabilità degli algoritmi: definizione

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

Esempio 1.6.1:

0 > =

=

∫

x n

n x e x I I

I e

e

Integrando per parti:

1 1

0

1 d 1

1 e n x e x nI

I_n e ^{n x} ⎟ = − _n =

⎠⎞

⎜⎝

= ⎛ −

∫

1

3 2

! ) 1 ( ) 1 (

) 1 (

) 1 ( 1

) )

2 (

1 )(

1 (

1 )

) 1 (

1 ( 1

I n k

n n

n

I n

n n n

I n

n

n n

k

n n

+ +

+

=

−

−

− +

−

=

−

−

−

=

∑

−

− L

Al it

0 1

! ) 1 ( ) 1 (

) 1 (

) 1 (

1 n n n k n I

k

− + +

−

−

− +

=

∑

= L ^Algoritmo

...

2856 6321205588

. 0 )

1 1 (

1 ¹ d

0 = − =

= _e

∫

I_o ^x

Con:

Stabilità di un algoritmo: esempio

7144 3678794411

1 0

2856 6321205588

.

0 = 0 I I

I 14 cifre significative

5712 2642411176

.

! 0 2 2

1

7144 3678794411

. 1 0

2 0 1 0

= +

= −

− =

= I I I I

2865 2072766470

. 0

! 3 2 3 3

1 ₀

3 = − + ⋅ − I =

I

M ¹

1

25 = 0 I

M

0 6 0.8

x n

n x e

x e

y 1

) ( =

)

!

!

! (!

10 436

.

3 ¹⁰

26 25

⋅

−

=

I _0.4

0.6

n=0

0 0 25 0 5 0 75 1

0

0.2 n=1 n=2 n=4

n=26

0 0.25 0.5 0.75 1

Stabilità di un algoritmo: esempio

Propagazione dell’errore iniziale ε₀=I₀-I₀^* nel calcolo di I_n?

l i li i di

L’algoritmo è lineare, quindi:

*

*

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

ε

ε

ε

ε

[ ]

1

0) 1 1 ( 1) ( 1) ( 1) ( 1) !

(I n n n k n I

f ^{n n}

k

k − − + + −

− +

=

∑

[

]

[ ]

1 1

* 0

1 0 0

! ) 1 ( )

1 (

) 1 (

) 1 ( 1

) (

) ( )

( )

( ) ( )

(

I n k

n n

n I

f f

n n k

k k

− + +

−

−

− +

=

∑

∑

−

=

=

L

Il termine (-1)ⁿn!, rapporto tra l’errore al “passo” n e quello al “passo” 0 è detto coefficiente di amplificazione dell’er- 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:

− I 1

n I I

nI

I_n = − _n− ⇒ _n− = 1 ⁿ

1 _{1 1}

Sapendo che: e posto I

=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 − = −

− =

− −

=

−

= _{− −}

− N N

I I

N I N

I I

I_{N N} ^{N N N N N}

N

ε ε

) 1 (

1 1

1

* 1 1

2 = −

− −

− =

= ⁻ − ^{− −}

− N N N N

I

I_{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.