Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

3) DETERMINARE N , N > 0 MEDIANTE UN PROCED-

IMENTO ITERATIVO

1. Individuare m, n > 0 tali che

2 2

m < N < n

m + n

2. Calcolare c = 2 √

2

3. Se c = N =⇒ c = N −→ Stop

2

4. Se c < N =⇒ Sostituire c a m e tornare a 2.

2

5. Se c > N =⇒ Sostituire c a n e tornare a 2.

2 2

m N n m N n

N.B.

IL PROCEDIMENTO PUÒ NON FINIRE (ES. N = 2)

=⇒ NON E’ UN ALGORITMO 4

CRITERIO DI ARRESTO

DECIDIAMO DI FERMARCI SE

2

|c − N | ≤ ε, ε > 0 È UNA TOLLERANZA

=⇒ c E’ UN’APPROSSIMAZIONE DI N NEI LIMITI DEL

CRITERIO DI ARRESTO SCELTO E DELLA TOLLERAN-

ZA SCELTA ε

ALGORITMO

1. Leggi: N, m, n, ε

2. Calcola c = (m + n)/2

2

3. Se |c − N | ≤ ε =⇒ Vai a 5.

2

4. Se c < N poni m = c e vai a 2.

Altrimenti poni n = c e vai a 2.

5. Scrivi c

6. Stop

N.B. RISCHIO: [M, N ] GRANDE E/O ε PICCOLO POTREB-

BERO IMPLICARE TROPPO TEMPO DI CALCOLO

=⇒ PUO’ ESSERE UNA BUONA IDEA FISSARE UN NU-

MERO MASSIMO DI ITERAZIONI 5

4) CALCOLO DEL VALORE DI UN POLINOMIO IN UN

PUNTO α n

X i 2 n

P (x) = a x = a + a x + a x + · · · + a x

n i 0 1 2 n

i=0

n

X i 2 n

P (α) = a α = a + a α + a α + · · · + a α

n i 0 1 2 n

i=0

ALGORITMO(1)

1. Leggi: n, a , a , . . . , a ; α

0 1 n

2. Poni p = 1

3. Poni s = a 0

4. Per i = 1, 2, . . . , n

1. Poni p = α · p

2. Poni s = s + a · p

i

5. Scrivi s

6. Stop

OPERAZIONI: 2n MOLTIPLICAZIONI

n ADDIZIONI 6

FORMULAZIONE DI HORNER

n n−1 2

P (x) = a x + a x + · · · + a x + a x + a

n n n−1 2 1 0

n−1 n−2

P (x) = x(a x + a x + · · · + a x + a ) + a

n n n−1 2 1 0

n−2 n−3

= x(x(a x + a x + · · · + a ) + a ) + a

n n−1 2 1 0

...

= (· · · ((a x + a )x + a )x + · · · + a )x + a

n n−1 n−2 1 0

ALGORITMO(2)

1. Leggi: n, a , a , . . . , a ; α

0 1 n

2. Poni s = a n

Per i = n − 1, n − 2, . . . , 0

3. 1. Poni s = s · α + a

i

4. Scrivi s

5. Stop

OPERAZIONI: n MOLTIPLICAZIONI

n ADDIZIONI 7

RAPPRESENTAZIONE DEI NUMERI

SISTEMI DI NUMERAZIONE

BINARIO: CIFRE 0,1

OTTALE: CIFRE 0, 1, 2, 3, 4, 5, 6, 7

...

DECIMALE: CIFRE 0 , 1, 2, 3, 4, 5, 6, 7, 8, 9

• NOTAZIONE POSIZIONALE

2 1 0

ES. (123) = 1 × 10 + 2 × 10 + 3 × 10

10 2 1 0

(123) = 1 × 8 + 2 × 8 + 3 × 8

8 1 0

(10) = 1 × 10 + 0 × 10

10 1 0

(10) = 1 × 2 + 0 × 2

2

IN UN ELABORATORE I NUMERI SONO RAPPRESEN-

• TATI IN UNA BASE DIVERSA DA β = 10 ⇒

IN GENERALE SONO NECESSARI ALGORITMI DI CON-

VERSIONE

RAPPRESENTAZIONE ESTERNA ¿ RAPP. INTERNA

β = 10 ¿ β =2 8

RAPPRESENTAZIONE DEI NUMERI

NUMERI INTERI

(a a . . . a a ) , con a , i = 1, . . . , m CIFRE DEL

m m−1 1 0 β i

SISTEMA DI NUMERAZIONE 0 ≤ a < β.

i

NUMERI REALI

UN NUMERO REALE x SI RAPPRESENTA NELLA FORMA

VIRGOLA MOBILE NORMALIZZATA (V.M.N.)

b

±0.a a . . . a β a 6 = 0

1 2 m 1

m ≤∞

a , a , . . . , a CIFRE DEL SISTEMA DI NUMERAZIONE

1 2 m

b UN NUMERO INTERO IN BASE β

a a . . . a E’ DETTA MANTISSA

1 2 m

b E’ DETTA CARATTERISTICA

ES. 0

0.1471 −→ 0.1471 10

2 3

37.1 −→ 0.371 10 0.0371 10

−2

0.003 −→ 0.3 10

NOTA:

x = 0 HA PER CONVENZIONE MANTISSA = 0

CARATTERISTICA = 0 9

RAPPRESENTAZIONE IN MACCHINA DEI

NUMERI INTERI

UN ELABORATORE DISPONE DI UN CERTO NUMERO DI

BITS PER RAPPRESNTARE I NUMERI (INTERI E REALI).

NUMERI INTERI

LOCAZIONI DI 16/32 BITS (PIÙ COMUNI)

½ 0 ⇒ N > 0

0

1 BIT PER IL SEGNO 1 ⇒ N < 0

AVENDO A DISPOSIZIONE t BITS ⇒ SOLO t−1 BITS SONO

PER LA RAPPRESENTAZIONE VERA E PROPRIA

QUALE E’ IL MASSIMO NUMERO N RAPPRESENTABILE

max

CON t BITS?

ES: β = 10; N = 947584

t =7 ⇒ 0 9 4 7 5 8 4

| {z }

t = 5 ⇒ OVERFLOW

t−2 t−3 1 0 t−1

N = 9×10 +9×10 +· · ·+9×10 +9×10 = 10 − 1

max 10

RAPPRESENTAZIONE IN MACCHINA DI

NUMERI REALI

SEGNO CARATTERISTICA MANTISSA

NUMERI REALI DI MACCHINA :

NUMERI CON MANTISSE E CARATTERISTICHE RAPPRE-

SENTABILI ESATTAMENTE CON I BITS A DISPOSIZIONE

IL LIMITE SULLA CARATTERISTICA DELIMITA L’OR-

• DINE DI GRANDEZZA DEI DATI

OVERFLOW

=⇒ UNDERFLOW

IL LIMITE SULLA MANTISSA CARATTERIZZA LA

• PRECISIONE 11

PRECISIONE

IL NUMERO DI CIFRE CHE L’ELABORATORE RISERVA

ALLA MANTISSA DEI NUMERI REALI (m) DETERMINA

LA PRECISIONE CON LA QUALE L’ELABORATORE LA-

VORA

SIA x 6 = 0 UN NUMERO REALE TALE CHE LA SUA RAPPRE-

SENTAZIONE IN v.m.n. RICHIEDE PIÙ DI m CIFRE DI

MANTISSA b

x = ±0.a a . . . a a . . . a . . . β

1 2 m m+1 m+i

%

a 6 = 0

1

IN QUESTO CASO x VIENE APPROSSIMATO CIOE’ VIENE

SOSTITUITO DA UN NUMERO REALE AD ESSO VICINO

CHE E’ CHIAMATO fl(x) (FLOATING DI x)

LA DETERMINAZIONE DI fl(x) PU0̀ AVVENIRE MEDIANTE

b

TRONCAMENTO ⇒ fl(x) = ±0.a a . . . a β

1 2 m

ARROTONDAMENTO ⇒

½ b

±0.a a . . . a β a < β/2

1 2 m m+1

fl(x) = b

±0.a a . . . (a + 1)β a ≥ β/2

1 2 m m+1

ESEMPIO

β = 10, m = 5

3

x =0.9345781 10 3

TRONC −→ fl(x) = 0.93457 10 3

ARR. −→ fl(x) = 0.93458 10 12

ERRORI NELLA RAPPRESENTAZIONE

SI DEFINISCE

ERRORE ASSOLUTO e = |x − fl(x)|

A x − fl(x)

| |

ERRORE RELATIVO e =

R |x|

ESEMPIO

β = 10, m = 4 TRONC/ARR

5 5

1) x = 0. 5895 4 10 fl(x) = 0.5895 10

|{z} 5 −4 5 1

e = |x − fl(x)| = 0.00004 10 = (0.4 10 )10 = 0.4 10

A |x − fl(x)| 1

e 0.4 10 −4

A

e = = = = c 10

R 5

|x| |x| 0.58954 10

−2 −2

2) y = 0. 5895 4 10 fl(y) = 0.5895 10

|{z} −2 −4 −2 −6

e = |y − fl(y)| = 0.0000410 = (0.4 10 )10 = 0.4 10

A |y − fl(y)| −6

e 0.4 10 −4

A

e = = = = c 10

R −2

|y| |y| 0.58954 10

• VIENE FATTO LO STESSO TIPO DI OPERAZIONE SU

x E y CON LO STESSO RISULTATO

• L’ERRORE RELATIVO E’ LO STESSO

• L’ERRORE ASSOLUTO NON E’ LO STESSO 13

L’ERRORE ASSOLUTO E’ INFLUENZATO DALL’ORDINE

DI GRANDEZZA DEL DATO

L’ERRORE RELATIVO NON E’ INFLUENZATO DALL’OR-

DINE DI GRANDEZZA DEL DATO

L’ERRORE RELATIVO DA’ INDICAZIONI SULL’ APPROSSI-

MAZIONE OPERATA SULLA MANTISSA DEL DATO

OVVERO

SULLA ACCURATEZZA (O PRECISIONE) CON CUI IL DA-

TO E’ APPROSSIMATO.

L’ERRORE RELATIVO NON DIPENDE DALLA CARAT-

• TERISTICA MA

DIPENDE DALLA MANTISSA

SE VOGLIAMO UNA MISURA DELLA PRECISIONE CON

CUI L’ELABORATORE APPROSSIMA UN QUALUNQUE NU-

MERO REALE DOBBIAMO SVINCOLARCI DA QUESTA

DIPENDENZA COME?

CONSIDERANDO UNA LIMITAZIONE SUPERIORE DEGLI

ERRORI DI ARARROTONDAMENTO/TRONCAMENTO

RELATIVI 14

PRECISIONE DI MACCHINA

LIMITAZIONE SUPERIORE DEGLI ERRORI RELATIVI SE

SI OPERA PER TRONCAMENTO ⇒

x − fl(x) 1−m

| | ≤ β ∀x 6 = 0

x

SE SI OPERA PER ARROTONDAMENTO ⇒

x − fl(x) 1 1−m

| | ≤ β ∀x 6 = 0

x 2

1

1−m 1−m

LA QUANTITÀ β O β E’ DETTA PRECISIONE DI

2

MACCHINA E VIENE DI SOLITO INDICATA CON IL SIM-

BOLO ε .

m

PIU’ AVANTI VEDREMO UN ALGORITMO PER DETER-

MINARLA. 15

ARITMETICA FINITA

DATI E RISULTATI SONO MEMORIZZATI CON UN NU-

MERO FINITO DI CIFRE (m) DI MANTISSA E

QUALUNQUE OPERAZIONE VIENE EFFETTUATA CON

UN NUMERO FINITO DI CIFRE (m) DI MANTISSA

NOTA: RISULTATI TEMPORANEI DELLE OPERAZIONI SONO

MEMORIZZATI IN APPOSITE LOCAZIONI CON PIÙ

CIFRE DI MANTISSA MA IN OGNI CASO IL NUMERO

E’ FINITO (SI EFFETTUA UN TRONC./ARR.)

LE 4 OPERAZIONI EFFETTUATE SU NUMERI DI MACCHI-

NA NON PRODUCONO NECESSARIAMENTE UN NUMERO

DI MACCHINA ⇒ IL RISULTATO DEVE ESSERE TRASFOR-

MATO NEL SUO f loating.

QUINDI

x + y si scrive x ¢ y e’ f l(f l(x) + f l(y))

x − y si scrive x ¯ y e’ f l(f l(x) − f l(y))

x × y si scrive x £ y e’ f l(f l(x) × f l(y))

x/y si scrive x £ y e’ f l(f l(x)/f l(y)) 16

OPERAZIONI IN MACCHINA

SOMMA ALGEBRICA DI DUE NUMERI REALI:

1 SI TRASFORMA IL NUMERO CON CARATTERISTICA

MINORE IN MODO CHE I DUE NUMERI ABBIANO LA

STESSA CARATTERISTICA (uno dei due perde la forma v.m.n.);

2 SI SOMMANO LE MANTISSE (lasciando invariate le carat-

teristiche);

3 SI RICAVA IL FLOATING DEL RISULTATO (si rinormalizza

il numero troncando o arrotondando se necessario)

PRODOTTO/DIVISIONE DI DUE NUMERI REALI:

1 SI PRODUCONO/DIVIDONO LE MANTISSE E SI SOM-

MANO/SOTTRAGGONO LE CARATTERISTICHE

3 SI FA IL FLOATING DEL RISULTATO (si rinormalizza il

numero troncando o arrotondando se necessario)

−1

β = 10, m = 4, b = 2, tronc. x = 10 , y = −0.00054

0 −3

f l(x) = 0.1000 10 , f l(y) = −0.5400 10

0 0 0 −1

x ¢ y = 0.1000 10 ¯ 0.0005 10 = 0.0995 10 = 0.9950 10

0 0 0 −3 −4

x £ y = 0.1000 10 £ (−0.0005) 10 = −0.0000510 10 = −0.5 10

17

ALCUNE CONSEGUENZE DELLA PRECISIONE

FINITA

PER LE OPERAZIONI DI MACCHINA VALGONO ANCORA

LE PROPRIETÀ DELLE QUATTRO OPERAZIONI

ARITMETICHE? SPESSO NO

• NON VALE LA PROPRIETA’ ASSOCIATIVA

• NON VALE LA PROPRIETA’ DISTRIBUTIVA

• VALE LA PROPRIETA’ COMMUTATIVA

FORMULE O ALGORITMI MATEMATICAMENTE EQUI-

VALENTI (CHE PORTANO ALLO STESSO RISULTATO SE

APPLICATI IN ARITMETICA ESATTA) POSSONO PRO-

DURRE RISULTATI DIVERSI IN ARITMETICA FINITA

LO STUDIO DEGLI ERRORI DI ARROTONDAMENTO E

DELLA LORO PROPOGAZIONE ATTRAVERSO GLI AL-

GORITMI E’ DI FONDAMENTALE IMPORTANZA PER

POTER INTERPRETARE E VALUTARE I RISULTATI DI

UN QUALUNQUE ALGORITMO CHE OPERI CON NUMERI

REALI 18

ESEMPIO: β = 10 m = 4 fl(x) per TRONCAMENTO

−3 1−m

ε = 10 ←− ε = β

m m

a = 2000 b = 2.5 c = 7.8

4 1 1

(a ¢ b) ¢ c = (0.2000 10 ¢ 0.2500 10 ) ¢ 0.7800 10 =

4 4 1

= (0.2000 10 ¢ 0.0002(5) 10 ) ¢ 0.7800 10 =

4 1

= 0.2002 10 ¢ 0.7800 10 =

4 4 4

0.2009 10

= 0.2002 10 ¢ 0.0007(8) 10 =

4 1 1

a ¢ (b ¢ c) = 0.2000 10 ¢ (0.2500 10 ¢ 0.7800 10 ) =

4 2

= 0.2000 10 ¢ 0.1030 10 =

4 4 4

= 0.2000 10 ¢ 0.0010(3) 10 = 0.2010 10

(a + b) + c = a + (b + c) = 2010.3

(a ¢ b) ¢ c 6 = a ¢ (b ¢ c) ½ 2010.3 − 2009 = 1.3

ERRORI ASSOLUTI 2010.3 − 2010 = 0.3

½ −3

1.3/2010.3 ' 10

ERRORI RELATIVI −4

0.3/2010.3 ' 10

NOTA: RISULTATI DIVERSI MA ACCETTABILI NEI LIMI-

TI DELLA PRECISIONE USATA 19

1−m −2

ESEMPIO: β = 10 m = 3 ε = β = 10

m

a = 0.651 b = 0.653

(a+b)

c = 2 0.651 0.652 0.653

0 0

(0.651 10 ¢ 0.653 10 )¤

: 2=

1 0

= 0.130 10 ¤

: 2 = 0.650 10 6∈ [a, b]

(b−a)

c = a + 2

0 0 0

0.651 10 ¢ (0.653 10 ¯ 0.651 10 )¤

: 2=

0 −2

= 0.651 10 ¢ (0.200 10 )¤

: 2=

0 −2 0 0

= 0.651 10 ¢ 0.100 10 = 0.651 10 ¢ 0.0010 10 =

0

= 0.652 10

FORMULE MATEMATICAMENTE EQUIVALENTI NON LO

SONO PIÙ QUANDO SI OPERA IN ARITMETICA FINITA

20

IMPORTANTE

IL CONCETTO DI UGUAGLIANZA VA MODIFICATO QUAN-

DO SI LAVORA SUI NUMERI REALI IN PRECISIONE FINI-

TA

RISULTATI DIVERSI POSSONO ESSERE CONSIDERATI UGUALI

NEI LIMITI DELLA PRECISIONE USATA

DUE NUMERI SONO UGUALI QUANDO HANNO UGUALE

CARATTERISTICA E UGUALE MANTISSA

MA

DUE NUMERI SONO DA CONSIDERARSI UGUALI QUAN-

DO LA LORO DIFFERENZA E’ PICCOLA RISPETTO ALLA

PRECISIONE DI MACCHINA

OVVERO

DUE NUMERI a, b IN PRECISIONE FINITA SONO DA CON-

SIDERARSI UGUALI QUANDO

|a − b| ≤ ε

DOVE ε E’ UN NUMERO, DETTO TOLLERANZA, IL CUI

VALORE DIPENDE DALLA PRECISIONE DI MACCHINA

21

QUINDI

NELL’ESEMPIO DEL PUNTO MEDIO I DUE NUMERI

• a = 0.651 b = 0.653

POTEVANO ESSERE CONSIDERATI UGUALI

INFATTI −3 −2

|b − a| = 2 10 ε = 10

m

N.B. GLI STESSI NUMERI NON POTREBBERO ESSERE

−8

CONSIDERATI UGUALI SE FOSSE ε = 10

m

• SE IL RISULTATO DI UN ALGORITMO IN PRECISIONE

INFINITA E’ ZERO E L’ALGORITMO REALIZZATO IN

PRECISIONE FINITA DÀ UN RISULTATO DIVERSO DA

ZERO MA PICCOLO, NON POSSIAMO CONCLUDERE

CHE L’ELABORATORE ABBIA SBAGLIATO

SE UN ALGORITMO PREVEDE UN CONTROLLO SULLA

• UGUAGLIANZA TRA DUE REALI DOBBIAMO FARE MOL-

TA ATTENZIONE NEL REALIZZARLO IN UN PROGRAM-

MA a = b ⇒ |a − b| ≤ ε

IL VALORE ε DEVE ESSERE SCELTO TENENDO CON-

TO DELLA PRECISIONE DI MACCHINA E, IN GENERALE,

DA CONSIDERAZIONI INDOTTE DAL CONTESTO 22

ALGORITMO PER IL CALCOLO DI ε

m

LA CONOSCENZA DI ε E’ FONDAMENTALE PER

m

• VALUTARE I RISULTATI

• SCEGLIERE LE TOLLERANZE

⇒ SERVE UN ALGORITMO PER CALCOLARLA

IDEA SU CUI PUÒ ESSERE BASATO L’ALGORITMO

−7 1−m

β = 10, m = 8 TRONCAMENTO ⇒ ε = 10 = β

m

−6 −7 −8

CALCOLIAMO fl(1 + 10 ), fl(1 + 10 ), fl(1 + 10 )

−6 1 −5

fl(1 + 10 ) = 0.10000000 10 ¢ 0.10000000 10 =

1 1 1

= 0.10000000 10 ¢ 0.00000010 10 = 0.10000010 10

−7 1 −6

fl(1 + 10 ) = 0.10000000 10 ¢ 0.10000000 10 =

1 1 1

= 0.10000000 10 ¢ 0.00000001 10 = 0.10000001 10

−8 1 −7

fl(1 + 10 ) = 0.10000000 10 ¢ 0.10000000 10 =

1 1 1

= 0.10000000 10 ¢ 0.000000001 10 = 0.100000001 10

⇒ ε E’ LA PIÙ PICCOLA POTENZA DELLA BASE β = 10

m

CHE VIENE SENTITA IN MACCHINA SE SOMMATA A 1 23

ALGORITMO PER DETERMINARE

ε IN BASE β

m

−p

fl(1 + β ) 6 = fl(1) −p

⇒ ε = β

m

−p−1

fl(1 + β ) = fl(1)

1. Poni ε = 1

m −1

2. Poni ε = β ∗ ε

m m

Poni a = 1 + ε

3. m

4. Se a > 1 vai a 2.

Altrimenti vai a 5.

5. Poni ε = β ∗ ε

m m

Stampa ε

6. m 24

CONSIDERAZIONI SULLE QUATTRO

OPERAZIONI ARITMETICHE

SUPPONIAMO DI EFFETTUARE OPERAZIONI ESATTE

PRODOTTO

fl(x ) fl(x )

1 2

z z

}| { }| {

x x − x (1 + ε ) · x (1 + ε ) x x − (x + x ε )(x + x ε )

1 2 1 1 2 2 1 2 1 1 1 2 2 2

= =

x x x x

1 2 1 2

x x − x x − x x ε − x x ε − x x ε ε ∼

1 2 1 2 1 2 2 1 2 1 1 2 1 2 −ε − ε

= =

x x 2 1

1 2

DIVISIONE ε , ε ≤ ε

1 2 m

x (1 + ε )

x 1 1

1 −

x 1 + ε 1 + ε − 1 − ε

x (1 + ε )

2 1 2 1

2 2 = 1 − = =

x 1 + ε 1 + ε

1 2 2

x

2 ε − ε

2 1

= ' ε − ε

2 1

1 + ε 2

SOMMA ALGEBRICA

(x + x ) − x (1 + ε ) − x (1 + ε )

1 2 1 1 2 2 =

x + x

1 2

x + x − x − x ε − x − x ε

1 2 1 1 1 2 2 2

= =

x + x

1 2

−x x

1 2

= ε − ε

x + x x + x

1 2

1 2 1 2 25

ESAMINANDO GLI ERRORI RELATIVI SI PUÒ AFFER-

MARE CHE LA SOMMA DI DUE NUMERI DI SEGNO OP-

POSTO PUÒ CAUSARE UN’AMPLIFICAZIONE DEGLI ER-

RORI NEI DUE OPERANDI QUANDO x + x ≈ 0

1 2

IL RISULTATO E’ ANALOGO ANCHE QUANDO SI SOSTI-

TUISCE L’OPERAZIONE ARITMETICA ESATTA CON QUEL-

LA DI MACCHINA 26

CANCELLAZIONE NUMERICA

PERDITA DI CIFRE SIGNIFICATIVE DOVUTA A SOTTRAZIONE

TRA OPERANDI QUASI UGUALI

ES:

β = 10 m = 6 ARROTONDAMENTO

a = 0.147554326 ā = 0.147554

b = 0.147251742 b̄ = 0.147252 −3

(a − b) = 0.000302584 = 0.302584 10 −3

(ā ¯ b̄) = 0.000302 = 0.302000 10

LA PERDITA DI CIFRE SIGNIFICATIVE HA LA SUA ORIG-

INE NEGLI ERRORI SUI DATI 27

ESEMPIO:

PERDITA DI PRECISIONE E FORMULAZIONE ALTERNA-

TIVA 2

x − 2bx + c = 0

p p

2 2

x = b + b − c x = b − b − c

1 2

SE |c| ¿ b p 2

b − c

b − sgn(b)

COMPORTA LA DIFFERENZA TRA NUMERI QUASI UGUALI

FORMULA ALTERNATIVA

p c

2

x = b + sgn(b) b − c, x =

1 2 x

1 28

RIASSUMENDO

SI COMMETTONO ERRORI NELLA RAPPRESENTAZIONE

1) DI NUMERI REALI

2) SI COMMETTONO ERRORI NELL’ESECUZIONE DELLE

OPERAZIONI ARITMETICHE

IDEA (TRANQUILLIZZANTE MA SBAGLIATA):

POICHÈ GLI ERRORI SONO PICCOLI ANCHE I RISULTATI

SONO AFFETTI DA ERRORI PICCOLI

POICHE’ NON POSSIAMO BASARCI SU TALE RASSICU-

RANTE IDEA, E’ IMPORTANTE OCCUPARSI DELLE SEGUEN-

TI QUESTIONI:

PROBLEMA −→ SOLUZIONE

SE SI ALTERANO I DATI DEL PROBLEMA, COME SI AL-

TERA LA SOLUZIONE? (ANALISI DEL CONDIZIONAMEN-

TO DEL PROBLEMA)

PROBLEMA −→ ALGORITMO −→ SOLUZIONE

COME SI PROPAGANO GLI ERRORI DELLE OPERAZIONI

NELL’ALGORITMO? (ANALISI DELLA STABILITA’ DELL’

ALGORITMO) 29

CONDIZIONAMENTO DI UN SISTEMA

LINEARE

PROBLEMA −→ SOLUZIONE

SI CONSIDERI IL SISTEMA LINEARE

½ · ¸

x − x = 1 100001

1 2 LA SOLUZIONE E’

x − 1.00001x = 0 100000

1 2

CONSIDERIAMO IL NUOVO SISTEMA ·

½ ¸

x − x = 1 −99999

1 2 LA SOLUZIONE E’

x − 0.99999x = 0 −100000

1 2

UN CAMBIAMENTO (IN VALORE ASSOLUTO) DI

−5

0.00002 = 2 · 10

IN UN ELEMENTO DELLA MATRICE HA PROVOCATO UN

CAMBIAMENTO (IN VALORE ASSOLUTO) DI

5

200000 = 2 · 10

NELLE COMPONENTI DELLA SOLUZIONE

µ ¶

ORDINE DI GRANDEZZA 5

CAMBIAMENTO RISULTATI 10 10

' = 10

µ ¶ −5

10

ORDINE DI GRANDEZZA

CAMBIAMENTO DATI 30

STABILITA’ DI UN ALGORITMO

PROBLEMA −→ ALGORITMO −→ SOLUZIONE

STUDIAMO LA PROPAGAZIONE GLI ERRORI DOVUTI ALLE

OPERAZIONI EFFETTUATE NEL CORSO DELL’ ALGO

RITMO

UN ALGORITMO SI DICE STABILE SE L’INFLUSSO DEGLI

ERRORI RIMANE LIMITATO

A B

L’ALGORITMO E’ PIÙ STABILE DELL’ ALGORITMO

SE L’INFLUENZA DEGLI ERRORI E’ MINORE

2 3 4

x x x

x

ESEMPIO: e = 1 + x + + + + · · ·

2! 3! 4!

−13

SI VUOLE STIMARE e 3 4

2 13 13

13

−13 − + + · · ·

METODO 1: e = 1 − 13 + 2! 3! 4!

%

la sottrazione e’ pericolosa!!!

2

1 13

−13

METODO 2: e = = 1/(1 + 13 + + · · ·)

2!

13

e

n M M

1 2

−5 −6

30 2.93783393 10 2.26036459 10

−5 −6

40 9.37448635 10 2.26032941 10

−5 −6

50 −1.32982788 10 2.26032941 10

−5

58 −1.32986125 10 31

NORME DI VETTORI E DI MATRICI

IL CONCETTO DI NORMA E’ UNA GENERALIZZAZIONE

DEL CONCETTO DI LUNGHEZZA DI UN VETTORE x ∈

n n×n

R O DI UNA MATRICE A ∈ R n

DEFINIZIONE:UNA FUNZIONE DA IR IN IR

x → kxk

TALE CHE

1) kxk ≥ 0 E kxk = 0 ⇐⇒ x = 0

2) kαxk = |α| · kxk ∀ α ∈ IR n

3) kx + yk ≤ kxk + kyk ∀ x, y ∈ IR

È UNA NORMA VETTORIALE

ESEMPI

v

u n

X √

u

t 2 T

x = x x NORMA 2

kxk =

2 i

i=1

n

X

kxk = |x | NORMA 1

1 i

i=1

kxk = max |x | NORMA ∞

∞ i

i=1,...,n 32

NORME MATRICIALI

n×n

DEFINIZIONE: UNA FUNZIONE DA IR → IR

n×n

A → kAk A ∈ IR

TALE CHE

kAk ≥ 0 E kAk = 0 ⇐⇒ A = 0

1)

2) kαAk = |α| · kAk ∀ α ∈ IR n×n

3) kA + Bk ≤ kAk + kBk ∀ A, B ∈ IR

4) kA · Bk ≤ kAk · kBk

È DETTA NORMA MATRICIALE

ESEMPI

s X 2

kAk = a NORMA DI FROBOENIUS

F ij

i,j=1,...,n

r T

kAk = max |λ (A A)| NORMA 2

2 i

i=1,...,n T

- MSSIMO AUTOVALORI IN MODULO DI A A

n

X

kAk = max |a | NORMA 1

1 ij

j=1,...,n i=1

n

X

kAk = max |a | NORMA ∞

∞ ij

i=1,...,n j=1 33

PROPRIETÀ DI NORME MATRICIALI

INDOTTE

AD OGNI NORMA VETTORIALE E’ POSSIBILE ASSOCIA-

RE UNA CORRISPONDENTE NORMA MATRICIALE

kAxk

kAk = sup kxk

n

x∈R

LA k • k , LA k • k E LA k • k SONO NORME MATRICIALI

2 1 ∞

INDOTTE DALLE CORRISPONDENTI NORME VETTORI-

ALI. LE NORME MATRICIALI INDOTTE SODDISFANO IN-

OLTRE: n×n n

kAxk ≤ kAk · kxk A ∈ IR , x ∈ IR

• n

• kIk = 1 I ∈ R matrice identità

• ρ(A) ≤ kAk DOVE IL RAGGIO SPETTRALE DI A E’

ρ(A) = max |λ | ≤ kAk

i

i=1,...,n

( ρ(A) e’ cioe’ il massimo autovalore di A in

modulo) 34

CONDIZIONAMENTO DI A

(per la risoluzione di Ax = b)

n×n n −1

SIA A ∈ R , b ∈ R ; Ax = b ; det(A) 6 = 0 → ∃ A

COME SI RIPERCUOTONO SUI RISULTATI LE VARIAZIONI

SUI DATI?

CASO SEMPLICE: PERTURBAZIONE SOLO SU b.

SE δb E’ IL VETTORE PERTURBAZIONE Ax = b DIVENTA

A(x + δx) = b + δb

A(x + δx) = b + δb ⇒ Ax + Aδx = b + δb ⇒ Aδx = δb

Ax = b ⇒ kbk = kAxk ≤ kAk · kxk

kbk

⇒ kxk ≥ kAk

−1 −1

Aδx = δb ⇒ δx = A δb ⇒ kδxk ≤ kA k · kδbk

kδxk kδbk −1

≤ · kA k · kAk

| {z }

kxk kbk

| {z } | {z }

ERRORE

RELATIVO K(A)

SUI INDICE DI CONDIZIONAMENTO

RISULTATI ERRORE RELATIVO SUI DATI 35

CASO GENERALE

GENERALIZZIAMO AL CASO DI UNA PERTURBAZIONE

ANCHE SU A.

SIA δA LA PERTURBAZIONE

kδxk kδbk kδAk

−1

≤ kA k · kAk · ( + )

kxk kbk kAk

kδxk kδbk kδAk

≤ K(A) · ( + )

| {z }

kxk kbk kAk

| {z } | {z }

ERRORE RELATIVO SUI DATI

INDICE DI CONDIZIONAMENTO

ERRORE RELATIVO SUI RISULTATI 36

ESEMPIO

MATRICE DI HILBERT

 

1 1 1

1 ···

2 3 n

 

 

1 1 1 1

···

 

2 3 4 n+1

H =  

. ...

n ...

..

 

 

1 1 1

··· ···

n n+1 2n−1

n K (H )

2 n

1

2 1.2 10 2

3 1.9 10 3

4 6.5 10 5

5 1.8 10 6

6 4.4 10 8

7 1.3 10 37

ESEMPIO ½ x − 0.99999x = 1

1 2

x − x = 0

1 2

SOTTRAENDO LE DUE RIGHE IN PRECISIONE INFINITA

ABBIAMO −5 5

(1 − 0.99999)x = 1 ⇒ 10 x = 1 ⇒ x = 10

2 2 2 5

x = x = 10

1 2

CONSIDERANDO IL SISTEMA PERTURBATO

½ x − 1.00001x = 1

1 2

x − x = 0

1 2

SEMPRE IN PRECISIONE INFINITA ABBIAMO

5 5

(1 − 1.00001)x = 1 ⇒ 10 x = 1 ⇒ x = −10

2 2 2 5

x = −10

1

CALCOLIAMO LE VARIAZIONI SUI DATI E QUELLE SUI

RISULTATI

µ ¶ µ ¶

1 −0.99999 1 −1.00001

A = A + δA =

1 −1 1 −1

µ ¶ −5

−5 kδAk 2 · 10

0 2 · 10 ∞ −5

δA = A − Ã = ⇒ = = 10

0 0 kAk 2

∞ 38

µ ¶ µ ¶ µ ¶

5 5 5

10 −10 2 · 10

x = x̃ = δx = x − x̃ = ⇒

5 5 5

10 −10 2 · 10

5

kδxk 2 · 10

∞ =2

= 5

kxk 10

∞ −1

CALCOLIAMO K(A) = kAk · kA k. RISULTA kAk = 2

~

CALCOLIAMO QUINDI L’INVERSA DI A .

µ ¶

1 −1 0.99999

−1 −1 5

A = · ⇒ kA k = 10 · 2

−1 1

−5

−10 5 5

IN CONCLUSIONE RISULTA K(A) = 2 · 2 · 10 = 4 · 10

kδxk kδAk 5 −5

≤ K(A) · ; (2 ≤ 4 · 10 · 10 )

kxk kAk ¶

µ ¶

µ

1

a a a −a

11 12 22 12

−1

; A =

~ A = a a −a a

det(A)

21 22 21 11

da usare solo nel caso di matrici 2 × 2. 39

OSSERVAZIONI SU K(A)

−1 −1

• K(A) = kAk · kA k ≥ kA · A k = kIk = 1

• NON CI SONO RELAZIONI TRA ORDINE DEL SISTEMA

n E K(A)

• NON CI SONO RELAZIONI TRA det(A) E K(A)

ES.  

1 −1 −1 · · · · · · −1

 

0 1 −1 · · · · · · −1

 

 

0 0 1 −1 · · · −1

  kAk = n

A =  

.. ...

... ∞

.

 

 

.. ...

...

 

.

0 ··· ··· ··· ··· 1

 

n−2

1 1 2 4 ··· ··· 2

 

n−3

0 1 1 2 4 · · · 2

 

 

n−4

0 0 1 1 2 ··· 2

  −1 n−1

−1 kA k = 2

A =  

.. .

. .. .. ∞

.

 

 

.. ...

. . .

 

.

0 ··· ··· ··· ··· ··· 1 P

n−2 i n−1

(1 + 2 = 1 + (2 − 1))

i=0

n−1

K (A) = n · 2 SE n E’ GRANDE A E’

MALCONDIZIONATA MA PER OGNI n RISULTA det(A) = 1

40

ES.  

1 0 ··· 0

10

  1 1 1

A = diag( , , . . . , )

1

0 · · · 0

  10 10 10

10

A =  

... ...

...

  1

kAk =

∞ 10

1

0 ··· ··· 10

 

10 0 · · · 0

  −1

A = diag(10, 10, . . . , 10)

0 10 · · · 0

 

−1

A =  

.. ...

. . .

.

  −1

kA k = 10

0 · · · · · · 10 1

−1

K(A) = kAk · kA k = · 10 = 1

∞ ∞ ∞ 10

−n

det(A) = 10 (n GRANDE DETERMINANTE PICCOLO)

• IN PRATICA E’ MOLTO COSTOSO CALCOLARE K(A)

−1

(IL CALCOLO DI A RICHIEDE LA RISOLUZIONE DI

n SISTEMI LINEARI)

• SI PUÒ STIMARE K(A) PERTURBANDO I DATI E CON-

TROLLANDO LA SOLUZIONE 41

SISTEMI LINEARI

n×n n

SIANO A ∈ IR , b, x ∈ IR : IL PROBLEMA È DETER-

MINARE LA SOLUZIONE, SE ESISTE, DI

Ax = b .

LA SOLUZIONE ESISTE ED È UNICA SE E SOLO SE LA

MATRICE A È NON SINGOLARE (det(A) 6 = 0)

METODO NOTO: REGOLA DI CRAMER ⇒

det(A )

i

x = , i = 1, . . . , n

i det(A)

DOVE A È LA MATRICE OTTENUTA DA A SOSTITUEN-

i

DO ALLA i-ESIMA COLONNA IL VETTORE b.

I DETERMINANTI COINVOLTI POTREBBERO ESSERE CAL-

COLATI CON LA REGOLA DI LAPLACE,

n

X j+1

det(A) = (−1) a det(A )

1j 1j

j=1

DOVE A RAPPRESENTA LA MATRICE DI ORDINE n − 1

1j

OTTENUTA DA A ELIMINANDO LA PRIMA RIGA E LA

j-ESIMA COLONNA.

PROBLEMA: IL NUMERO DI OPERAZIONI ARITMETICHE

∼ ∼

6

COINVOLTE SUPERA (n + 1)! (10! 3.6 × 10 , 20! 2.4 ×

= =

18 64

10 , 50! 3 × 10 )

= 42

METODI NUMERICI PER LA RISOLUZIONE DI

SISTEMI LINEARI

METODI DIRETTI: COSTRUISCONO LA SOLUZIONE ESATTA,

IN ASSENZA DI ERRORI DI

ARROTONDAMENTO, IN UN NUMERO

FINITO DI PASSI

(PER MATRICI DENSE E DI ORDINE NON

ELEVATO)

METODI ITERATIVI: COSTRUISCONO UNA SUCCESSIONE

DI VETTORI, CONVERGENTE SOTTO

OPPORTUNE CONDIZIONI,

ALLA SOLUZIONE

⇒ NECESSITANO DI CRITERI

DI ARRESTO

(PER MATRICI SPARSE E DI

ORDINE ELEVATO) 43

CASI FACILMENTE RISOLUBILI

A DIAGONALE

1) x = b /a , i = 1, . . . , n (det(A)) 6 = 0 ⇐⇒ a 6 = 0 ∀ i

i i ii ii

2) A TRIANGOLARE ⇒ ALGORITMO BASATO SU

SOSTITUZIONI IN AVANTI (TRIANG. SUP.)

O ALL’INDIETRO (TRIANG. INF.)

ESEMPIO 

 a 11 

 a a 

 21 22 

A = a a a 

 31 32 33 

 ..

. 

 a a . . . . . . a

n1 n2 nn

x = b /a

1 1 11

x = (b − a x )/a

2 2 21 1 22

... i−1

X

x = (b − a x )/a , i = 3, . . . , n

i i ik k ii

k=1

(det(A) 6 = 0 ⇐⇒ a 6 = 0 ∀ i)

ii

N.B.

1) COSTO COMPUTAZIONALE: n

n

X 2

n(n + 1) n

2) COSTO COMPUT. : i = = O( )

2 2

i=1 44

INFATTI PER CALCOLARE x OCCORRONO (i−1) MOLTI-

i

PLICAZIONI E 1 DIVISIONE ⇒ i OPERAZIONI (TRASCU-

n

X i

RANDO LE SOMME) QUINDI OTTENIAMO i=1

ALGORITMO

1. Leggi

2. Calcola x = b /a

1 1 11

3. Calcola x = (b − a x )/a

2 2 21 1 22

4. Per i = 3, . . . , n i−1

X

4.1 Calcola x = (b − a x )/a

i i ik k ii

k=1

Stampa x

5.

6. Stop 45

CALCOLO DELL’INVERSA DI UNA MATRICE

n×n −1 −1

A ∈ R (AA = A A = I)

n =2 µ µ ¶

¶ 1 a −a

a a 22 12

11 12 −1

A = A = −a a

a a det(A) 21 11

21 22

ES. n = 3  

 

    

x

a a a x x 1 0 0

   

11

11 12 13 12 13

 

 

 =

x

a a a 0

x x 1 0

   

21

21 22 23 22 23

   

x

a a a x x 0 0 1

   

31

31 32 33 32 33

|{z} |{z} |{z} |{z} |{z} |{z}

x x x e e e

1 2 3 1 2 3

 a x + a x + a x = 1

 11 11 12 21 13 31 ⇒ Ax = e

a x + a x + a x = 0 1 1

21 11 22 21 23 31

 a x + a x + a x = 0

31 11 32 21 33 31

ANALOGO SISTEMA CON LA ⇒ Ax = e

2 2

SECONDA COLONNA

ANALOGO SISTEMA CON LA ⇒ Ax = e

3 3

TERZA COLONNA

QUESTO METODO VALE ANCHE PER n > 3 46

METODO DI GAUSS

DATO IL SISTEMA Ax = b

 a x + a x + · · · + a x = b

 11 1 12 2 1n n 1

 a x + a x + · · · + a x = b

21 1 22 2 2n n 2

...

 a x + a x + ··· + a x = b

n1 1 n2 2 nn n n

SE L’ELEMENTO PIVOT a 6 = 0 RICAVIAMO

11 n

X

1

x = (b − a x )

1 1 1k k

a 11 k=2

SOSTITUENDO NELLA SECONDA EQUAZIONE

n

X

1

a · (b − a x ) + a x + · · · + a x = b

21 1 1k k 22 2 2n n 2

a 11 k=2 a a

a 21 21

21 a )x + (a − a )x + · · · = b − b

(a − 12 2 23 13 3 2 1

22 a a a

11 11 11

SOSTITUENDO NELLA i-ESIMA EQUAZIONE

a a a

i1 i1 i1

(a − a )x + (a − a )x + · · · = b − b

i2 12 2 i3 13 3 i 1

a a a

11 11 11 47

QUINDI PERVENIAMO AL SISTEMA

 (2) (2) (2) (2)

 a x + a x + · · · + a x = b

 1 2 n

11 12 1n 1

 (2) (2) (2)

0 a x + · · · + a x = b

2 n

22 2n 2

...

 (2) (2) (2)

0 a x + · · · + a x = b

nn n

2 n

n2

a a a − a a

21 22 11 21 12

(2)

SE a 6 = 0 ⇐⇒ (a − a ) 6 = 0 ⇐⇒ 6 = 0

22 12

22 a a

11 11

(2)

(a elemento pivot) RICAVIAMO x , SOSTITUIAMO ED OT-

2

22

TENIAMO

 (3) (3) (3) (3)

a x + a x + · · · + a x = b

 1 2 n

11 12 1n 1

 (3) (3) (3)

 0 + a x + ··· + a x = b

 2 n

22 2n 2

(3) (3) (3)

0 0 a x + · · · + a x = b

3 n

 33 3n 3

 ... ...

 (3)

(3) (3) x = b

0 0 a x + · · · + a n

nn n

3

n3

(n)

SE a 6 = 0, k = 1, . . . , n − 1 DOPO (n − 1) PASSI

kk (n)

OTTENIAMO (a elemento pivot)

kk

 (n) (n) (n) (n)

a x + a x + ··· + a x = b

 1 2 n

11 12 1n 1

 (n) (n) (n)

 a x + ··· + a x = b

 2 n

22 2n 2

(n) (n) (n)

a x + · · · + a x = b

3 n

 33 3n 3

 ...

 (n) (n)

a x = b

nn n

n 48


ACQUISTATO

2 volte

PAGINE

100

PESO

259.00 KB

AUTORE

Sara F

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica
SSD:
Università: Firenze - Unifi
A.A.: 2013-2014

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Sara F di informazioni apprese con la frequenza delle lezioni di Calcolo Numerico e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Firenze - Unifi o del prof Fantechi Alessandro.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Calcolo numerico

Calcolo Numerico – Determinante
Appunto
Calcolo numerico – Programma
Dispensa
Fondamenti di Informatica I – Manuale Linguaggio C
Dispensa
Appunti Analisi 1
Appunto