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

transcript

Corso di Laurea in Matematica

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

Docente: Marco Gaviano

(e-mail:gaviano@unica.it)

Schema di un problema numerico

y x relazioni

input output

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

Classificazione di problemi numerici

1. Problemi diretti

y x relazioni

si assegna si determina assegnate

Schema di un problema numerico

y x relazioni

input output

2. Problemi di identificazione

y x relazioni

assegnato assegnato si determina

3. Problemi inversi

y x relazioni

si determina si assegna assegnate

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

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

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

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

In una generica base >1 si ha per un numero

N= (dndn-1,…,d1d0)

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

n-1 +…+ d11+ d0

cifre in base , comprese tra 0 e -1

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

binario

esadecimale

conversione

Esempio di rappresentazioni di un numero in basi

differenti

base rappres. numero

2 100011111

4 10133

10 287

12 1BB

16 11F

Teorema

Dato un numero reale x0 esso può esprimersi

univocamente come

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

mantissam

dddxsignx

...)()( 3

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

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

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

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’

le cifre potrebbero essere infinite

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.

Ogni calcolatore può avere il suo modo di

rappresentare i numeri. Si individua comunque uno

schema generale comune, chiamato

sistema floating point

sistema in virgola mobile

insieme dei numeri macchina

(definizione)

Un insieme di numeri macchina con t cifre

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

numeri dato da

• t, interi > 0 e 2

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

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

p dxsignRxULtF1

)(0),,,(

Un numero reale x ha la forma

Un numero macchina x ha la forma

tdddx 21.

numero di cifre finito e uguale a t

le cifre potrebbero essere infinite

pdddx 321.

p è limitato

p non è limitato

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

Il numero (cardinalità) dei numeri in un sistema

floting point è

infatti

1)1)(1||(21 tLU

p dxsignRxULtF1

)(0),,,(

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

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

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

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

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

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

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

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

p dxtroncxfl1

p dtroncxfl

troncamento, chopping

arrotondamento, rounding

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

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

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

ULpddxi

xxfl 1)(

Dimostrazione nel caso dell’arrotondamento

Poiché d1 0 e m –1, si ha

ptxxfl 2

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

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

stampa ‘la precisione macchina è: 2*eps

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

Corso di Laurea in Matematica

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

Docente: Marco Gaviano

(e-mail:gaviano@unica.it)

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

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

non ci sono numeri macchina

gli altri numeri macchina numero macchina successivo ad 1

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

La relazione

Può riscriversi come

xxfl t 1)(

epsconxxfl ||)1()(

perturbazione

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

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.

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

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

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)

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

Conclusione

L’aritmetica (finita) del calcolatore non coincide con

l’aritmetica (infinita) definita in Matematica

Proprietà valide in Matematica possono non essere

valide

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

(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].

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

I punti sono pochi: il grafico non è soddisfacente

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

I punti sono sufficienti: il grafico è accettabile

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

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

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

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

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

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

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

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.

La quantità

è detta numero di condizionamento del problema nel punto x.

Si ha per qualsiasi incremento ||

Se C è piccolo, allora il problema è ben condizionato

)()(supsup

Esempio

Si debba calcolare

Posto si ha

Trascurando i termini di ordine superiore al primo (si assume

|<<1|), si ottiene

)1()21(

)1()1(ˆˆ)ˆ(

xxxxxf

)()1()21(

)()ˆ(2

xxxf 2)(

)1(ˆxxxx

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.

xxxf 2)(

3)( xxf

xfxf 3

)()ˆ(

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

Algoritmo

Insieme di operazioni che permettono di risolvere un

problema numerico

y x algoritmo

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

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

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

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

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

1 zzzxzxz

).();5();( 2132

1 zzflzxflzxflz

Tramite questo sviluppo al prim’ordine siamo in grado

di valutare l’errore algoritmico

)1)(55(

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

))1(5)1((

))5()((

xxxxxx

xflxflflz

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

algoritmico cresce in maniera non limitata.

32132212

)())5()((

)())((

xxxxxxxx

xfxflxflfl

xfxfflALG

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

L’errore algoritmico risulta essere

L’algoritmo è stabile.

)5()1)(5(

)())5((

)())((

xfxflxfl

xfxfflALG

)1)(5(

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

xxxflxflz

Analisi all’indietro dell’errore algoritmico

Insieme di problemi da risolvere

ottenuti perturbando i dati

soluzione esatta

soluzione calcolata

dall’algoritmo problema la cui soluzione

esatta è y

Algoritmo stabile (definizione qualitativa)

Un algoritmo si dice stabile quando nella sua applicazione

gli errori di arrotondamento non vengono

amplificati eccessivamente

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