Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

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

ALGORITMO DI GAUSS

1. Per k = 1, . . . , n − 1

1.2 Se a = 0 stop

kk

1.2.1 m = a /a

ik ik kk

1.2.2 Per j = k + 1, . . . , n

1.2.2.1 a = a − m a

ij ij ik kj

1.2.3 b = b − m b

i i ik k

1.2.4 a = 0

ik

(risoluzione del sistema triangolare)

2. Se a = 0 stop

nn

3. x = b /a

n n nn

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

n

X

1 (b −

4.1 x = a x )

i

i ik k

a ii k=i+1

 

. .. ...

 

INVARIATO

 

...

 

0

 

 

...

 

 

(k) . . . ... k

. . . . . . . . . . . . a

 

(k) kk

A =  

. ... k +1

 

0

 

.

... ..

 

 

...

 

0 0

 

...

...

 

...

0

k k +1 49

ESEMPIO 

   9

11 4 −6 

 

 b =

A = 19

−7 17 9 1

−1 −4 6

RISOLUZIONE CON IL METODO DI GAUSS DI Ax = b

 11 4 −6 9

 

(1) (1)

[A | b ] = −7 17 9 19

−1 −4 6 1

(1)

0

1 PASSO a = 11 6 = 0

11

k =1 i =2 −7

m = a /a =

21 21 11 11

j =2 −7 215

a = a − m a = 17 − ( )4 =

22 22 21 12 11 11

j =3 −7 57

a = a − m a = 9 − ( )(−6) =

23 23 21 13 11 11

−7 272

b = b − m b = 19 − ( )9 =

2 2 21 1 11 11

 

11 −6 9

4

 

 

(2) (2) 57 272

215

[A | b ] = 0

 

11 11 11

40 60 20

0 11 11 11 50

215

(2)

0

2 PASSO a = 6 = 0

22 11 ⇓

 

4 −6 9

11

 

 

(3) (3) 215 57 272

[A | b ] = 0

 

11 11 11

276 276

0 0 43 43

SI PROCEDE POI ALLA RISOLUZIONE DEL SISTEMA

276

276 / =1

x = b /a =

3 3 33 43 43

i =2 3

X

1 1

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

a x ) =

2 2 2 23 3

2k k

a a

22 22

k=3

215 272 57 11 215

= 1/ · ( − · 1) = · ( )=1

11 11 11 215 11

i =1 3

X

1 1

x = (b − a x ) = (b − a x − a x )

1 1 1k k 1 12 2 13 3

a a

11 11

k=2

1 1

= (9 − 4 + 6) = · 11 = 1

11 11 

 1 

LA SOLUZIONE DEL SISTEMA È x = 1

1 51

(1) 0

SE a 6 = 0 =⇒ 1 PASSO DI GAUSS

11

det(A ) 6 = 0 A MINORE PRINCIPALE DI A

1 1

DI ORDINE 1

(2) 0

SE a 6 = 0 =⇒ 2 PASSO DI GAUSS

22

det(A ) 6 = 0 A MINORE PRINCIPALE DI A

2 2

DI ORDINE 2

... esimo

(k)

SE a 6 = 0 =⇒ k PASSO DI GAUSS

kk

det(A ) 6 = 0 A MINORE PRINCIPALE DI A

k k

DI ORDINE k ···

GAUSS PUÒ ESSERE APPLICATO SE TUTTI I MINORI

PRINCIPALI DI A FINO ALL’ORDINE n − 1 HANNO DE-

TERMINANTE 6 = 0. VALE IL SEGUENTE

n×n

TEOREMA SIA A ∈ IR TALE CHE det(A ) 6 = 0 k =

k

1, . . . , n − 1 (A MINORE PRINCIPALE DI ORDINE k)

k

ALLORA IL METODO DI GAUSS E’ APPLICABILE.

Q (k)

n

INOLTRE det(A) = a .

k=1 kk 52

IL METODO DI GAUSS CON PERMUTAZIONE

 x + x = 1

 2 3 (1)

det(A) = 6 6 = 0 MA a = 0

x − x + x = 3

1 2 3 11

 2x + x − x = 0

1 2 3

=⇒ SCAMBIO LA SECONDA E LA PRIMA RIGA

 x − x + x = 3

 1 2 3

x + x = 1

2 3

 2x + x − x = 0

1 2 3

ED APPLICO GAUSS SENZA PROBLEMI

 

1 3

−1 1

 

(1) (1)

[A | b ] = → m = 0, m = 2

0 1

1 1 21 31

2 0

1 −1 

 3

1 −1 1 

(2) (2) → m = 3

[A | b ] = 1

0 1 1 32

−6

0 3 −3

 

3

1 −1 1

 

(3) (3)

[A | b ] = 1

0 1 1 −9

0 0 −6 53

GAUSS IN PRECISIONE FINITA

SIA IL SISTEMA Ax = b

· ¸ · ¸

ε 1 1+ ε

A = b = ε > 0 “PICCOLO”

1 0 1 ¸

· 1

⇒ LA SOLUZIONE DEL SISTEMA E’ x = 1

IL PROBLEMA È BEN CONDIZIONATO. INFATTI

· ¸ −1

0 1 kA k = 1 + ε

−1 2

A = ; ⇒ K(A) = (1 + ε)

1 −ε kAk = 1 + ε

K(A) È DI POCO SUPERIORE AD 1 PER ε PICCOLO

−3

SUPPONIAMO ε = 0.3 10 , β = 10, m = 3 ARROT.

(1) (1)

A PARTIRE DA [A | b ] = [A | f ] DOPO UN PASSO OT-

TENIAMO ¸

· −3

−3 1 + 0.3 10

0.3 10 1

(2) (2)

[A | b ] = 4 4

−0.333 10

0 −0.333 10 54

DA · ¸

−3

0.3 10 1 1

(2) (2)

[A | b ] = 4 4

0 −0.333 10 −0.333 10

E PER SOSTITUZIONE ALL’INDIETRO OTTENIAMO

 

1 1

0.1000 10 − 0.100 10 · ¸

  0

−3

0.3 10

 

x̃ = =

 

4

−0.333 10 1

4

−0.333 10

L’ERRORE DI CUI È AFFETTA LA SOLUZIONE NON DIPENDE

DAL MAL CONDIZIONAMENTO DEL PROBLEMA

MA

ALL’INSTABILITÀ DEL METODO DI GAUSS

RIMEDIO: SCAMBIARE LE RIGHE (per aumentare l’elemen-

to pivot) ¸

· 1

1 0

(1) (1)

[A | b ] = 1+ ε

ε 1

· ¸ · ¸

1 0 1 1 0 1

(2) (2)

[A | b ] = =

0 1 1+ ε − ε 0 1 1

¸

· 1 RIOTTENIAMO LA SOLUZIONE ESATTA

⇒ x̃ = 1 55

STRATEGIA DEL MASSIMO PIVOT

UNA STRATEGIA PER IL METODO DI GAUSS CHE CON-

SENTE DI CONTENERE GLI ERRORI È EVITARE LA SCELTA

DI UN DIVISORE PICCOLO NELLA COSTRUZIONE DEI

MOLTIPLICATORI.

AL PASSO k-ESIMO SI SCAMBIA LA RIGA k-ESIMA CON

LA RIGA i-ESIMA (i ≥ k) TALE CHE

(k) (k)

|a | = max |a |

ik jk

j=k,...,n

TALE TECNICA SI CHIAMA PIVOTING PARZIALE (NON

RICHIEDE IL RIORDINAMENTO DELLE INCOGNITE)

UNA VARIANTE CONSISTE NELLO SCAMBIO OPPORTUNO

DI RIGHE E COLONNE CIOÈ

AL PASSO k-ESIMO SI SCAMBIA LA RIGA k-ESIMA CON

LA RIGA i-ESIMA (i ≥ k) E LA COLONNA k-ESIMA CON

LA COLONNA j-ESIMA (j ≥ k) TALE CHE

(k)

(k) | = max |a |

|a j,t

ij j,t=k,...,n

TALE TECNICA SI CHIAMA PIVOTING TOTALE (RICHIEDE

IL RIORDINAMENTO DELLE INCOGNITE) 56

ESEMPIO

MATRICE DI HANKEL A DI ORDINE n I CUI ELEMENTI

n

SONO ½ k

2 k> 0

(n)

a = , i = 1, . . . , n, k = i+1−n, . . . , n

1/(2−k)

i,n+k−i 2 k ≤ 0

n =4  

√ √ √

4 3

2 2 2 2

√ √

 

3 2

2 2 2 2

 

A =  

2 3

2 2 2 2

 

2 3 4

2 2 2 2

SI COSTRUISCE IL VETTORE f IN MODO CHE IL SIS-

TEMA Ax = f ABBIA COME SOLUZIONE x = [1, 1, . . . , 1]

kδxk −6

TABELLA DEGLI ERRORI AL VARIARE DI ε ' 10

n

kxk

n GAUSS PIVOT PARZIALE PIVOT TOTALE

−5 −5 −6

4 1.61 10 1.30 10 1.60 10

−6 −5 −5

6 7.84 10 1.83 10 2.09 10

−4 −4 −5

8 4.96 10 3.54 10 1.93 10

−2 −4 −5

10 1.38 10 3.05 10 7.52 10

−3 −3 −4

12 7.84 10 3.08 10 1.07 10

−1 −3 −4

14 7.48 10 3.01 10 8.75 10

−1 −2 −4

16 2.26 10 2.49 10 9.15 10 57

METODI ITERATIVI PER SISTEMI LINEARI

DATO UN SISTEMA LINEARE Ax = b L’IDEA E’ DI COSTRU-

(k)

IRE UNA SUCCESSIONE DI VETTORI {x } CHE CON-

(k)

VERGA ALLA SOLUZIONE ⇒ lim x = x

k→∞

COME E’ POSSIBILE REALIZZARE CIO’ ?

ESEMPIO: n = 3

 a x + a x + a x = b

 11 1 12 2 13 3 1

a x + a x + a x = b

21 1 22 2 23 3 2

 a x + a x + a x = b

31 1 32 2 33 3 3

SUPPONENDO a 6 = 0, a 6 = 0, a 6 = 0 POSSIAMO SCRI-

11 22 33

VERE  b −a x −a x

 x = 1 12 2 13 3

 1 a

11

b −a x −a x

x = 2 21 1 23 3

2 a

 22

 b −a x −a x

x = 3 31 1 32 2

3 a

33 (0)

QUINDI, PARTENDO DA UN VETTORE ARBITRARIO x ∈

3 (k)

R POSSIAMO GENERARE LA SUCCESSIONE {x }

 (k) (k)

(k+1) 1 (b − a x − a x )

x =

 1 12 13

2 3

1 a 11

(k+1) (k) (k)

1 (b )

x = − a x − a x

2 21 23

2 1 3

a

 22

 (k+1) (k) (k)

1

x = (b − a x − a x )

3 31 32

3 1 2

a 33 58

I METODI DI JACOBI E DI GAUSS SEIDEL

IN GENERALE, PER UNA MATRICE DI DIMENSIONE n

POSSIAMO SCRIVERE n

X

1

(k+1) (k)

x = (b − a x ), i = 1, . . . , n

i ij

i j

a

ii j=1,j6 =

i

O ANCHE i−1 n

X X

1 (k) (k)

(k+1) (b − a x − a x ), i = 1, . . . , n .

x = i ij ij

j j

i a

ii j=1 j=i+1

QUESTO E’ IL METODO DI JACOBI.

SE AD OGNI PASSO UTILIZZIAMO LE COMPONENTI DEL

(k+1)

VETTORE x GIA’ AGGIORNATE (presumibilmente piu’

precise) OTTENIAMO IL METODO DI GAUSS-SEIDEL

i−1 n

X X

1 (k)

(k+1) (k+1)

x = (b − a x − a x ), i = 1, . . . , n .

i ij ij j

i j

a ii j=1 j=i+1 59

FORMULAZIONE MATRICIALE DI J. E G. S.

DI UNA MATRICE A DI DIMENSIONE n CONSIDERIAMO

UNO SPLITTING DEL TIPO

A = L + D + U

DOVE L ED U SONO IL TRIANGOLO INFERIORE E SU-

PERIORE DI A E DOVE D E’ LA SUA DIAGONALE

     

0 0 ... 0 0 a . . . a a 0 . . . 0

12 1n 11

     

a 0 . . . 0 0 0 . . . a 0 a . . . 0

 

   

21 3n 22

, , .

     

... ... ...

     

a a . . . 0 0 0 ... 0 0 0 ... a

n1 n2 nn

SE RISCRIVIAMO LE FORMULE DI JACOBI

n

i−1 X

X (k)

(k)

(k+1) +b ,

x

− a

x

= − a

a x i

ij

ij

ii

|{z} j

j

i |{z}

|{z} j=i+1

j=1

elementi di D elementi di U

elementi di L

ARRIVIAMO A JACOBI IN FORMA MATRICIALE

(k+1) (k) (k+1) −1 (k) −1

Dx = −(L+U )x +b ⇒ x = −D (L+U )x +D b .

NEL CASO DI GAUSS SEIDEL A PARTIRE DA

i−1 n

X X

(k+1) (k+1) (k)

a x = − a x − a x +b ,

ii ij ij i

|{z} i j j

|{z} |{z}

j=1 j=i+1

elementi di D elementi di L elementi di U

ARRIVIAMO A

(k+1) (k+1) (k) (k+1) (k)

Dx = −Lx −U x +b ⇒ (D+L)x = −U x +b

(k+1) −1 (k) −1

OVVERO x = −(D + L) U x + (D + L) b. 60

FORMULAZIONE MATRICIALE:

CASO GENERALE

DI UNA MATRICE A DI DIMENSIONE n CONSIDERIAMO

UNO SPLITTING DEL TIPO A = M − N . RISULTA

Ax = b ⇒ (M − N )x = b

⇒ Mx = Nx + b

−1 −1

⇒ x = M N x + M b

DA CUI SI OTTIENE IL METODO ITERATIVO

½ (k+1) −1 (k) −1

x = M N x + M b

(0) n

x ∈ R arbitrario

(k)

TEOREMA LA SUCCESSIONE {x } CONVERGE ALLA

SOLUZIONE SE E SOLO SE LA MATRICE DI ITERAZIONE

−1

M N E’ CONVERGENTE E CIOE’, INDICATA CON 0 LA

MATRICE NULLA, RISULTA

−1 k

lim (M N ) = 0 .

k→∞

(k) (k) (k)

DIM: SIA e = x − x. OVVIAMENTE x → x SE E

(k) (0) (0)

SOLO SE e → 0. POSTO e = x − x RISULTA:

(k) (k) −1 (k−1) −1 −1 −1

e = x − x = M N x + M b − M N x − M b

−1 k (0)

−1 (k−1) −1 2 (k−2) e

= M N e = (M N ) e = · · · (M N )

| {z }

tende a 0

E QUINDI POSSIAMO CONCLUDERE CHE

(k) −1 k .

x → x ⇔ (M N ) → 0

|{z}

matricenulla 61

CONDIZIONI PER LA CONVERGENZA

DI SEGUITO SONO ELENCATE ALCUNE FRA LE

CONDIZIONI NECESSARIE e/o SUFFICIENTI

PER LA CONVERGENZA DI UN METODO ITERATIVO

BASATO SULLO SPLITTING A = M − N .

−1

• (M N ) e’ una matrice convergente (NEC. E SUFF.)

−1 −1

• ρ(M N ) = max |λ (M N )| < 1 (NEC. E SUFF.)

i=1,...,n i

−1

• k(M N )k < 1 (SUFF.)

• A e’ una matrice diagonale dominante in senso forte

P nj=1,i6

|a | > |a | (SUFF.)

ii ij

=

j

Solo per Gauss-Seidel: A e’ una matrice simmetrica e definita

• positiva (SUFF.)

IN GENERALE NON SI PUO’ AFFERMARE CHE IL METO-

DO DI GAUSS SEIDEL CONVERGA PIU’ VELOCEMENTE

DEL METODO DI JACOBI (O VICEVERSA). TUTTAVIA,

NEL CASO DI MATRICI TRIDIGONALI IL METODO DI

GAUSS SEIDEL CONVERGE SE E SOLO SE CONVERGE

IL METODO DI JACOBI E, ASINTOTICAMENTE, SONO

NECESSARIE META’ITERAZIONI DI GAUSS SEIDEL PER

OTTENERE LA STESSA PRECISIONE DI JACOBI. 62

CRITERI DI ARRESTO (k)

QUANDO COSTRUIAMO UNA SUCCESSIONE {x } TALE

(k)

CHE x → x NELLA PRATICA DOBBIAMO FERMARCI

DOPO UN NUMERO FINITO DI PASSI CIOE’ SCEGLIERE

DEI CRITERI DI ARRESTO.

I PIU’ USATI SONO:

(k+1) (k)

• kx − x k ≤ ²

(k+1) (k)

kx −x k ≤ ²

• (k+1)

kx k

(k) (k)

• kr k = kAx − bk ≤ ²

(k) (k)

IL VETTORE r = Ax − b E’ DETTO VETTORE RESI-

(k)

DUO ED E’ NULLO SE E SOLO SE x E’ LA SOLUZIONE

ESATTA.

E’ IMPORTANTE OSSERVARE CHE UN RESIDUO PICCO-

LO NON NECESSARIAMENTE IMPLICA VICINANZA AL-

LA SOLUZIONE (DIPENDE DAL CONDIZIONAMENTO DEL-

LA MATRICE A) 63

EQUAZIONI NON LINEARI

IL PROBLEMA È DETERMINARE LE SOLUZIONI DI

UN’EQUAZIONE NON LINEARE

f (x) = 0 f : IR → IR

IN GENERALE NON SONO DISPONIBILI FORMULE

ESPLICITE PER CALCOLARE LE SOLUZIONI DI f (x) = 0.

=⇒

SI RICORRE A TECNICHE CHE CONSENTANO DI AP-

PROSSIMARE LE SOLUZIONI CON UN PRESTABILITO GRA-

DO DI PRECISIONE

N.B. UN CASO PARTICOLARE DI f (x) = 0 SONO LE EQUAZIONI

ALGEBRICHE n

X k

P (x) = a x = 0

n k

k=0

ALCUNI ESEMPI DI EQUAZIONI NON LINEARI

x 2

x + 4 sin(x) = 0, e − x = 0, x − log(x) = 3 64


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