Corso di Laurea in Matematica Analisi Numerica · 2016. 1. 22. · Analisi Numerica 1° mod. a.a....

1

Corso di Laurea in Matematica

Analisi Numerica (1° mod., 6 crediti, 48 ore, a.a. 2014-2015, lez.5)

Docente: Marco Gaviano

(e-mail:[email protected])

2

Schema di un problema numerico

Tx=y

y x relazioni

input output

Analisi Numerica 1° mod. a.a. 2014-2015, Lezione n.5

3

Classificazione di problemi numerici

1. Problemi diretti

y x relazioni

si assegna si determina assegnate


4

Schema di un problema numerico

Tx=y

y x relazioni

input output


5


2. Problemi di identificazione

y x relazioni

assegnato assegnato si determina


6


3. Problemi inversi

y x relazioni

si determina si assegna assegnate


7

Analisi degli errori

Notazione

a >> b significa a ‘molto più grande’ di b

a b significa a ‘approssimativamente uguale’ a b

a-b indica ‘l’errore assoluto’ tra i valori a e b

(a-b)/a indica ‘l’errore relativo’ tra i valori a e b


8

Analisi degli errori

Tipi di errore

1. Errori nel modello

2. Errori nei dati

3. Errori di arrotondamento e nei calcoli

4. Errori di troncamento

Analisi Numerica


9

Rappresentazione dei numeri nel Calcolatore

Notazione posizionale

8754 (nel sistema decimale) è un modo compatto

di scrivere

8103 + 7102 + 5101 + 4100

In generale in base 10 si ha

N=dndn-1…d0 = dn10n + dn-110n-1 +…+ d0100

cifre


10

Possono utilizzarsi altre basi:

• binaria (2 simboli: 0, 1)

• ottale (8 simboli: 0,1, 2, 3, 4, 5, 6, 7)

• esadecimale (16 simboli: 0,1, 2, 3, 4, 5, 6, 7, 8, 9, A,

B, C,D, E, F )

Esistono algoritmi che operano la conversione da una

base ad un’altra


11

In una generica base >1 si ha per un numero

N= (dndn-1,…,d1d0)

(dndn-1,…,d1d0) = dnn + dn-1

n-1 +…+ d11+ d0

0

cifre in base , comprese tra 0 e -1


12

Osservazione

Conversione da binario ad esadecimale

(0000)2= (0)16, (0001)2= (1)16

(0010)2= (2)16, (0011)2= (3)16 ….

(1100)2= (C)16, (1101)2= (D)16

(1110)2= (E)16, (1111)2= (F)16

F

1111

1

0001

1

1

binario

esadecimale

conversione


13

Esempio di rappresentazioni di un numero in basi

differenti

base rappres. numero

2 100011111

4 10133

8 437

10 287

12 1BB

16 11F


14

Teorema

Dato un numero reale x0 esso può esprimersi

univocamente come

con

1. sign(x) = 1 (x>0) oppure sign(x)= -1 (x<0)

2. p numero intero

3. 0di-1

4. d10 e le di non tutte uguali a -1 a partire da un

indice in poi

esponenteparte

p

mantissam

dddxsignx

...)()( 3

3

2

2

1

1


15

Esempi

2345 =+(210-1+ 310-2+ 410-3+ 510-4)104

=+(.2345)104

0.0045 =+(410-1+ 510-2)10-2

=+(.45)10-2

0.00004 =+(410-1)10-4

=+(.4)10-4


16

Osservazione 1

d1 è 0 perché in tal modo nel rappresentare il

numero non si scrivono gli zeri per esempio

0.000000004 =+(410-1)1010-8

=+(.4)10 10-8


17

Osservazione 2

La condizione 4 serve per avere una rappresentazione

univoca. Altrimenti le 2 espressioni

(.99999999….)10 100 e (1)101

rappresenterebbero lo stesso numero

9 ripetuto infinite volte


18

Osservazione 3

La mantissa m soddisfa la relazione

In conclusione un numero reale x con x 0 si può

scrivere nella forma

x=(.d1 d2 d3…)p

e si parla di ‘rappresentazione normalizzata’

11

m

le cifre potrebbero essere infinite


19

Numeri macchina o sistema floating point

L’insieme dei numeri reali è infinito e vi sono dei

numeri con un numero infinito di cifre (numeri

irrazionali).

In un calcolatore che ha un numero finito di celle di

memoria può rappresentarsi un sottoinsieme finito

dei numeri reali. Inoltre i numeri reali con un

numero di cifre ‘grande’ o infinito saranno

rappresentati mediante approssimazioni.


20

Ogni calcolatore può avere il suo modo di

rappresentare i numeri. Si individua comunque uno

schema generale comune, chiamato

sistema floating point

o

sistema in virgola mobile

o

insieme dei numeri macchina


21

(definizione)

Un insieme di numeri macchina con t cifre

significative, base e range (L,U) è l’insieme dei

numeri dato da

con

• t, interi > 0 e 2

• 0 di -1, i=2,3,…

• d1 0, L p U, U>0, L<0

t

i

i

i

p dxsignRxULtF1

)(0),,,(


22

Un numero reale x ha la forma

Un numero macchina x ha la forma

p

tdddx 21.

numero di cifre finito e uguale a t

le cifre potrebbero essere infinite

pdddx 321.

p è limitato

p non è limitato


23

Esempi di sistemi floating point in doppia precisione

Dec 11/780 Vax 2 56 256

IBM /370 16 14 128

Cray 2 96 32768

Honeywell DPS8 2 63

Sperry 1100 2 60 2048

IEEE standard chip 2 52 2048

Hewlett Packard 3000 2 54 512

calcolatore t U+|L|+1


24

Il numero (cardinalità) dei numeri in un sistema

floting point è

infatti

1)1)(1||(21 tLU

t

i

i

i

p dxsignRxULtF1

)(0),,,(


25

Esempio di sistema floating point con

=2, t=3, L= 1, U=2

Il generico numero ha la forma

pdd 21.0 21

3 cifre per la

mantissa

parte esponente con

-1p2 1a cifra 0


26

La cardinalità di tale sistema è 1+2(2+1+1)(1)(2)2

I numeri sono: lo zero e

± 0.100·2-1 ± 0.101·2-1 ± 0.110·2-1 ± 0.111·2-1

± 0.100·20 ± 0.101·20 ± 0.110·20 ± 0.111·20

± 0.100·21 ± 0.101·21 ± 0.110·21 ± 0.111·21

± 0.100·22 ± 0.101·22 ± 0.110·22 ± 0.111·22

)21.0(0)2,1,3,2( 21

pddF


27

I valori positivi nella retta reale sono rappresentati da

0 2-2 2-1 20 21 22

I numeri si distribuiscono uniformemente tra successive

potenze di 2 ovvero tra

[2-2 , 2-1], [2-1 , 20], [20 , 21], [21 , 22]

underflow overflow


28

Un sistema floating point più realistico è dato da

=2, t=24, U+|L|+1=256

In tal caso si potrebbe avere la rappresentazione su un

calcolatore utilizzando 4 bytes (precisione semplice)

caratteristica mantissa

8 bits 23 bits

segno


29

Come rappresentiamo un numero reale x, x>0,

su un calcolatore con sistema floating point F(,t,L,U)?

1. x è tale che L p U e di =0 per i > t; allora x è un

numero macchina rappresentabile esattamente

pdddx ...)(. 321

rappresentazione normalizzata di x


30

2. L’esponente p della rappresentazione di x non

appartiene all’intervallo [L,U]. X non può essere

rappresentato esattamente nel sistema floating

point.

Se p < L si parla di underflow ed x viene

approssimato con lo zero

Se p > U si parla di overflow ed x non può essere

rappresentato in nessun modo


31

3. L’esponente p della rappresentazione di x

appartiene all’intervallo [L,U] ma le cifre di ,

per i > t non sono tutte nulle. Allora x viene

approssimato da un numero del sistema

floating F del calcolatore


32

Approssimazione ad un numero floating point

Sia x un numero reale > 0 della forma

con p[L,U] allora il numero macchina che lo approssima

si indica con fl(x) con fl(x) dato da

pdddx ...)(. 321

t

i

i

i

p dxtroncxfl1

)()(

)2

1()(

1

1

tt

i

i

i

p dtroncxfl

troncamento, chopping

arrotondamento, rounding


33

Esempio

Sia dato il numero x=165.286 in base 10.

x=(.165286)103 (in forma normalizzata )

In caso di troncamento con t=4 si approssima con

In caso di arrotondamento con t=4 si approssima con

310)1652(.)()( xtroncxfl

34 10)]102

116528(.[)( troncxfl

33 10)1653(.10)]00005.016528(.[ tronc


34

Osservazione

Se dt+1< /2 troncamento ed approssimazione coincidono;

per esempio con t=4 in entrambi i casi si ha

x=856.428 (.8564)103

Se dt+1 /2 troncamento ed approssimazione differiscono

(in valore assoluto) di p-t; per esempio con t=4

x = 856.468 (.8564)103 (troncamento)

x = 856.468 (.8565)103 (arrotondamento)

differenza = 103-4 = 0.1


35

Proposizione

Sia x un numero reale in base , ovvero

Allora (se non si verifica overflow) si ha la valutazione

dell’errore

con k=1 nel caso del troncamento e

con k=0.5 nel caso dell’arrotondamento

].,[,01

1

ULpddxi

i

i

p

tkx

xxfl 1)(


36

Dimostrazione nel caso dell’arrotondamento

Si ha

Poiché d1 0 e m –1, si ha

ptxxfl 2

1)(

t

t

p

pt

mmx

xxfl

1

2

1

||

2

1

||

2

1)(


37

La quantità

si chiama precisione macchina del sistema floating

point.

(proprietà) eps è il più piccolo numero macchina

positivo tale che

tkeps 1

1)1( epsfl


38

Come conoscere il valore eps di un sistema floating

point?

Algoritmo(precisione macchina) in pseudo-codice

eps=1.

eps1=eps+1;

while eps1> 1,

eps=0.5*eps;

eps1=eps+1

end

stampa ‘la precisione macchina è: 2*eps


39

Algoritmo in FORTRAN(descritto nel libro di testo)

EPS=1.

1 EPS=0.5*EPS

EPS1=EPS+1

IF(EPS1.GT.1) GOTO 1

EPS=2.*EPS


40

Corso di Laurea in Matematica

Analisi Numerica (1° mod., 6 crediti, 48 ore, a.a. 2014-2015, lez.6)

Docente: Marco Gaviano

(e-mail:[email protected])

41

Osservazione

Quando si eseguono calcoli su un calcolatore è

importante conoscere i parametri del suo sistema

floating point, F(, t, L, U). In particolare si deve

conoscere la precisione macchina

In Matlab il valore eps è predefinito e vale

eps = 2.220446049250313e-016

tkeps 1


42

1. eps dà la distanza tra 1 ed il successivo numero

macchina più grande

2. eps è il più piccolo numero macchina positivo tale che

1)1( epsfl

1 eps

non ci sono numeri macchina

gli altri numeri macchina numero macchina successivo ad 1


43

Perché la somma di due numeri macchina a e b con

a>> b può dare a? ovvero: a+b=a

Esempio con =10 (sistema decimale) e t=4

a=24,56 = (.2456)·102

b=0,00001234 = (.1234)·10-4

.2456 102

.0000001234 102

.2456 102

riduzione alla stessa parte esponenziale

quella del numero maggiore

somma e perdita delle cifre di b


44

La relazione

Può riscriversi come

epskx

xxfl t 1)(

epsconxxfl ||)1()(

perturbazione


45

Le operazioni aritmetiche sul calcolatore

(aritmetica floating point)

Dato x e y numeri macchina di un sistema floating point

F(, t, L, U). Si ha

x+y xy = fl(x+y)

x-y xy = fl(x-y)

y*y xy = fl(x*y)

x/y xy = fl(x/y)

operazioni (esatte) definite in matematica

operazioni eseguite dal calcolatore


46

Osservazione

Le operazione aritmetiche eseguite in un calcolatore

sono approssimazioni delle operazioni definite in

Matematica.

Nell’eseguire un’operazione quale la somma tra due

numeri reali a e b può aversi e un errore di

rappresentazione di a e b; inoltre ad esso deve

aggiungersi l’errore introdotto nel fare la somma.


47

Possiamo scrivere per x e y numeri macchina

xy = (xy)(1+ ) con | | eps

Nel caso della somma

xy = float(x+y) = (x+y)(1+ )

qualsiasi operazione aritmetica

eseguita dal calcolatore operazione aritmetica

corrispondente esatta


48

ed anche

x y = float(x+y) = (x + y)(1+ )= x(1+ ) + y(1+ )

a cui può darsi la seguente interpretazione la somma

data dal calcolatore è la somma esatta di

x(1+ ) e y(1+ )

cioè il calcolatore dà la somma esatta non di x e y ma di

due valori modificati (perturbazioni di x e y)

somma nel calcolatore somma esatta


49

Questo modo di operare viene usato per studiare gli

errori che si commettono quando un algoritmo è

implementato su di un calcolatore; viene chiamata

analisi all’indietro dell’errore o backward analysis.

Cioè a partire dai dati x, il calcolatore, applicando un

certo algoritmo, produce il risultato y affetto da errore.

Il risultato y è interpretato come risultato esatto

ottenuto a partire da x+ (dati perturbati)


50

In pratica avviene questo

Noi con l’analisi all’indietro lo interpretiamo come

y x algoritmo

y x+ algoritmo

affetto da errore opera in aritmetica finita

non affetto da errore opera esattamente dati perturbati


51

Conclusione

L’aritmetica (finita) del calcolatore non coincide con

l’aritmetica (infinita) definita in Matematica

Proprietà valide in Matematica possono non essere

valide


52

Esempi

Dati i numeri a, b, c si deve calcolare a+b+c

a= 0.2337125810-4

b= 0.33678429102

c= -0.33677811102

Si può operare in 2 modi differenti

(algorit.1) (a b) c = 0.33678452102 0.33677811102

=0.6410000010-3

(algorit.2) a (b c) = 0.2337125810-4 0.618000010-3

=0.64137126 10-3

risultato esatto

a+b+c= 0.64137125810-3


53

(esercitazione)

La funzione

y1= x6-6x5+15x4-20x3 +15x2-6x+1

può essere scritta anche nella forma

y2=(x-1)6

Fare il grafico della funzione utilizzando le 2

rappresentazioni. Ovvero nella stessa figura fare il

grafico di y1 e y2 nell’intervallo [0.994, 1.006].


54

Come operano i programmi che tracciano il

grafico di una funzione di una variabile ?

A partire da una tabulazione (xi, yi), i=1,…,n

uniscono con una curva i punti riportati in un

sistema di assi cartesiani


55

I punti sono pochi: il grafico non è soddisfacente

-8 -6 -4 -2 0 2 4 6 8-1

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1


56

I punti sono sufficienti: il grafico è accettabile

-8 -6 -4 -2 0 2 4 6 8-1

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1


57

I grafici di

y1= x6-6x5+15x4-20x3 +15x2-6x+1 e y2=(x-1)6

0.994 0.996 0.998 1 1.002 1.004 1.006 1.008 1.01-1

0

1

2

3

4

5x 10

-14


58

I grafici di

y1= x6-6x5+15x4-20x3 +15x2-6x+1 e y2=(x-1)6

0.994 0.996 0.998 1 1.002 1.004 1.006 1.008 1.01-1

0

1

2

3

4

5x 10

-14


59

I grafici di

y1= x6-6x5+15x4-20x3 +15x2-6x+1 e y2=(x-1)6

0.994 0.996 0.998 1 1.002 1.004 1.006 1.008 1.01-1

0

1

2

3

4

5x 10

-14


60

Problema ben posto (definizione)

Un problema si dice ben posto (Hadamard) quando

ammette una ed una sola soluzione e questa dipende con

continuità dai dati


61

Problema ben posto

y x relazioni

dati del problema soluzione del problema

ad ogni x corrisponde

uno ed un solo y

dipende con continuità

al variare di x


62

Condizionamento di un problema

Consideriamo un problema in cui si abbia

x(dati input) f(x) (soluzione esatta), x, f(x)R

Si debba operare a partire dai dati x ma per errori dovuti alla

raccolta dei dati si operi a partire da x+

La soluzione esatta sarà ora f(x+) (al posto di f(x)).

L’errore assoluto sarà f(x)-f(x+) e quello relativo

Il termine è chiamato errore inerente dovuto all’errore sui dati

in input

0)(,)(

)()(

xf

xf

xfxff

f


63

L’errore inerente viene posto in relazione con l’errore

relativo in input

In tal modo si può analizzare il problema in termini

generali e valutare, come al variare dei dati in input

varia la soluzione esatta.

0,

xx

x


64

La quantità

è detta numero di condizionamento del problema nel punto x.

Si ha per qualsiasi incremento ||

Se C è piccolo, allora il problema è ben condizionato

0,||

)(

)()(supsup

|||

x

xf

xfxfC

x

f

xf C


65

Esempio

Si debba calcolare

Posto si ha

Trascurando i termini di ordine superiore al primo (si assume

|<<1|), si ottiene

)1()21(

)1()1(ˆˆ)ˆ(

22

222

xxx

xx

xx

xxxxxf

x

xxf

x

x

xx

xxxx

xf

xfxf

1

12

)(

)()1()21(

)(

)()ˆ(2

22

xxxf 2)(

)1(ˆxxxx


66

Poiché , il problema di valutare

è mal condizionato per valori in

input in intorni del punto –1.

Altro esempio:

Con calcoli analoghi si ottiene

In tal caso il problema

è ben condizionato.

1

12lim

1 x

x

x

xxxf 2)(

3)( xxf

xfxf

xfxf 3

)(

)()ˆ(


67

Problema ben condizionato (definizione)

Un problema si dice ben condizionato quando è ben posto

e la sua soluzione non varia di molto al variare dei dati

y x relazioni

non varia di molto

al variare dei dati dati del problema

soluzione del problema


68

Algoritmo

Insieme di operazioni che permettono di risolvere un

problema numerico

y x algoritmo


69

Il problema dello studio dell’attendibilità delle soluzioni

date da un algoritmo è di grande importanza in Analisi

Numerica. Tale studio è difficile e solo in casi particolari

si riesce a dare delle indicazioni utili; esistono varie

tecniche: le principali sono

• Analisi in avanti (forward analysis)

• Analisi all’indietro (backward analysis)

• Aritmetica dell’intervallo

• Analisi statistica


70

Analisi in avanti dell’errore algoritmico

Con l’analisi in avanti, si valuta ad ogni operazione

eseguita dall’algoritmo l’errore commesso,

ricordando che per ogni operazione al calcolatore si

ha

xy=(xy)(1+ ) con | | eps .


71

Esempio

Si debba valutare l’errore algoritmico che si ottiene

eseguendo al calcolatore

Si assume che i valori in input siano numeri macchina

xxxf 5)( 2


72

Le operazioni dell’algoritmo nel calcolare x2-5x sono

si ottiene

Ricordando la relazione fondamentale dei calcoli in

aritmetica di macchina, ed effettuando i calcoli in

prima approssimazione, ossia trascurando gli ordini

superiori al primo, si ottiene:

.;5; 2132

2

1 zzzxzxz

).();5();( 2132

2

1 zzflzxflzxflz


73

Tramite questo sviluppo al prim’ordine siamo in grado

di valutare l’errore algoritmico

33

2

21

22

321

22

321

2

21

2

2

3

555

)1)(55(

)1))(1(5)1((

))1(5)1((

))5()((

xxxxxx

xxxx

xx

xxfl

xflxflflz


74

L’algoritmo è instabile poichè per x tendente a 5, l’errore

algoritmico cresce in maniera non limitata.

32132212

2

2

2

33

2

21

22

2

5

5

55

5

5

5

5555

)(

)())5()((

)(

)())((

xx

x

xx

x

xx

x

xx

xxxxxxxx

xf

xfxflxflfl

xf

xfxfflALG


75

Consideriamo, per la stessa funzione f(x) l’algoritmo

seguente

Consideriamo ogni passo dell’algoritmo:

Al calcolatore si ottiene

)5()( xxxf

.;5 121 zxzxz

).();5( 121 zxflzxflz


76

L’errore algoritmico risulta essere

L’algoritmo è stabile.

2121

)5(

)5()1)(5(

)(

)())5((

)(

)())((

xx

xxxx

xf

xfxflxfl

xf

xfxfflALG

)1)(5(

)1))(1)(5(())5((

21

212

xx

xxxflxflz


77

Analisi all’indietro dell’errore algoritmico

Insieme di problemi da risolvere

ottenuti perturbando i dati

Pb

P

x

y

soluzione esatta

soluzione calcolata

dall’algoritmo problema la cui soluzione

esatta è y


78

Algoritmo stabile (definizione qualitativa)

Un algoritmo si dice stabile quando nella sua applicazione

gli errori di arrotondamento non vengono

amplificati eccessivamente


79

Possiamo avere

•Un problema può essere ben condizionato per certi

dati ma non per altri

•Un problema può essere ben condizionato ma se lo

risolviamo con un algoritmo non stabile le soluzioni

ottenute possono non essere attendibili

•In Analisi Numerica in generale si riesce a trovare la

soluzione di problemi ben condizionati se si dispone di

algoritmi stabili


Corso di Laurea in Matematica Analisi Numerica · 2016. 1. 22. · Analisi Numerica 1° mod. a.a....

Documents

Transcript of Corso di Laurea in Matematica Analisi Numerica · 2016. 1. 22. · Analisi Numerica 1° mod. a.a....