Lezioni di Analisi Numericariccardo.broglia/Didattica/AN2003...Err. computazionale: è la somma...

Analisi Numerica(R. BROGLIA)

Ingegneria MeccanicaAnno Accademico 2003-04

2

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 BrogliaTel: [email protected]

Calcolo numerico:nozioni introduttive

4

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.

5

Calcolo numerico: erroriProblema Fisico

Ipotesi semplificative(errori inerenti)

Modello Matematico⇓

Know out, fantasia e arte(errori di troncamento)⇓

Modello NumericoAlgoritmo (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

6

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*xx −=ε

( )

=⋅−==

%100// ***

rr

r xxxxεε

εεErrore relativo

7

Errore di arrotondamento: propagazione),...,,( 11 nxxxfY =Calcolo di una funzione:

Nel caso di funzione di una variabile:

)()( ** xfxfYY −=−

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

( ) *2** )()()()( xxxOxxxfxfxfx

x −=∆+−+≈−=∆

εε321

Sostituendo:

)()()()( 2* xfxfxOxxfYY xxx εε =≤∆+∆=−

8

Errore di arrotondamento: propagazione

Formula generale di propagazione degli errori:

)(xfY xε≤∆

Nel caso di funzione di più variabili:

),...,(),...,( 111 1 nxnnx xxfxxfY nεε ++≤∆ L

*iii xx −=ε Errore sul dato i-esimo

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

9

Propagazione: esempio

Esempio 1.4.1:

422

411

105.01233.0

105.01234.0−

−

⋅≤=

⋅≤=

ε

ε

x

x

0001.),( 2121 =−= xxxxf

%10011010

4

4

21

21 =⇒==−+

≤∆

−

−

rxxYY ε

εε

• Esercizio consigliato [G] 1.4.2

10


Esempio:

( )17213535217)(

1)(234567

2

71

−+−+−+−=

−=

xxxxxxxxfxxf

Le due funzioni sono identiche in senso algebrico; calcolo di f1(x) e di f2(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)

11


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

f1(x) f2(x)

( )71 1)( −= xxf

12

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:

)()(

)(xfxf

xYY

xfxY′

∆≤∆

⇒′∆≤∆

xxC

xfxfx

xx

YY

p∆

=′∆

≤∆

)()(

Cp: numero di condizionamento del problema

13

Propagazione: condizionamento

)()(

xfxfxCp

′=

xxC

YY

p∆

≤∆

Se Cp è “grande” il problema è mal condizionato, ossia a piccole perturbazione dei dati iniziali si hanno grandi varia-zioni dei risultati. Viceversa se Cp è “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.

14

Condizionamento: esempio

Esempio 1.5.1:

−−==−==

⇒

=+=+

≠ )1/()()1/(1)(

01

2

2

)1( 2 ααααα

αα

α gzfy

zyzy

2

2

11

)()(

αα

ααα

−+

=′

=ggCz2

2

12

)()(

αα

ααα

−=

′=

ffCy

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

15

Condizionamento: esempio

1.01.01.0 10-4-2499.752500.250.9998-4999.755000.250.9999

3.4 10-41.6 10-41.8 10-4-0.8031456701.4460671050.5554

1.446299444y

-0.803419341z |∆y/y|

0.5555|∆z/z||∆α/α|α

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

16

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.

17

Stabilità di un algoritmo: esempio

0lim,0d11

0=>=

∞→∫ nnnxn

n IIxexeIEsempio 1.6.1:

Integrando per parti:

0

1

1

32

1

1

0

1

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

))2(1)(1(1))1(1(1

1d1

Inknnn

InnnnInn

nIxexnee

I

nn

k

k

nn

nxn

n

−++−−−+=

=−−−+−=−−−=

=−=

−=

∑

∫

−

=

−−

−−

L

L

Algoritmo

11 −−= nn nII

.....28566321205588.0)1(1d11

0=−== ∫ eexeeI

xoCon:

18


)!!!(!10436.3

0

28652072766470.0!3233157122642411176.0!221

71443678794411.0128566321205588.0

1026

25

03

02

01

0

⋅−=

=

=−⋅+−==+−=

=−==

II

IIII

III

M

M

0 0.25 0.5 0.75 10

0.2

0.4

0.6

0.8

1

n=0

n=1 n=2n=4

n=26

14 cifre significative

xnn exe

xy 1)( =

19


Propagazione dell’errore iniziale ε0=I0-I0* nel calcolo di In? L’algoritmo è lineare, quindi:

0*00

*00

* !)1()(!)1()()( εε nIInIfIfII nnnnn −=−−=−=−=

[ ][ ] *011*0

01

10

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

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

InknnnIf

InknnnIfnn

kk

nn

kk

−++−−−+=

−++−−−+=

∑∑

−

=

−

=

L

L

Il termine (-1)nn!, 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.

20


L’algoritmo può essere così modificato:

nIInII nnnn

−=⇒−= −−

11 11

Sapendo che: e posto IN=0 per N fissato:0lim =∞→ nn I

K,1,10 1 −=−

== − NNkkIII kkN

21


Propagazione dell’errore:

)1(11

11

1*

112

***

111

−=

−−=

−−

=

−=−

=−

−−

=−=

−−−−

−−−

NNNNII

NNII

NI

NIII

NNNNN

NNNNNNNN

εεε

εε

L’errore si riduce l’algoritmo è stabile.

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

Analisi Numerica(R. BROGLIA) Ingegneria MeccanicaAnno Accademico 2003-04Calcolo numerico:nozioni introduttiveCalcolo numerico: generalitàCalcolo numerico: erroriErrore computazionale: definizioniErrore di arrotondamento: propagazioneErrore di arrotondamento: propagazionePropagazione: esempioPropagazione: esempioPropagazione: esempioPropagazione: condizionamentoPropagazione: condizionamentoCondizionamento: esempioCondizionamento: esempioAlgoritmo: definizioneStabilità di un algoritmo: esempioStabilità di un algoritmo: esempioStabilità di un algoritmo: esempioStabilità di un algoritmo: esempioStabilità di un algoritmo: esempio

Lezioni di Analisi Numericariccardo.broglia/Didattica/AN2003...Err. computazionale: è la somma...

Documents

Transcript of Lezioni di Analisi Numericariccardo.broglia/Didattica/AN2003...Err. computazionale: è la somma...