Sistemi lineari: generalità - Home | Dipartimento di Scienze di...

21
Sistemi lineari: generalità Problema: risolvere un sistema lineare di grandi dimensioni N = + + + = + + + n n n n b x a x a x a b x a x a x a L L 2 2 2 22 1 21 1 1 2 12 1 11 n i b x a i j ij , 1 1 = = = + + + n n b x a x a x a L M M M M 2 2 1 1 2 2 2 22 1 21 In forma compatta: + + + n n nn n n b x a x a x a 2 2 1 1 In forma compatta: A = [ a ij ]nxn vettore dei coefficienti B AX = B = [ b i ]n vettore dei termini noti X = [x i ]n vettore delle incognite X [ x i ]vettore delle incognite 1

Transcript of Sistemi lineari: generalità - Home | Dipartimento di Scienze di...

Page 1: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Sistemi lineari: generalità

Problema: risolvere un sistema lineare di grandi dimensioni

N

∑⎪⎪⎨

⎧=+++=+++

nn

nn

bxaxaxabxaxaxa

L

L

22222121

11212111

nibxa ijij ,11

==∑⎪⎪⎩

⎪⎨

=+++

nn

bxaxaxa

bxaxaxa

L

MMMM

2211

22222121 ⇔

In forma compatta:

⎩ +++ nnnnnn bxaxaxa 2211

In forma compatta:

A = [ aij ]∈ ℜnxn vettore dei coefficienti

BAX = B = [ bi ]∈ ℜn vettore dei termini noti

X = [ xi ]∈ ℜn vettore delle incogniteX [ xi ]∈ ℜ vettore delle incognite1

Page 2: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Sistemi lineari: soluzione

Teorema (Rouché-Capelli): il sistema lineare AX=Bammette soluzione se e solo se r(A|B)=r(A) ovvero seammette soluzione se e solo se r(A|B) r(A), ovvero see solo se B appartiene allo spazio lineare generato dallecolonne di A.

Metodo di Cramer: se la matrice è quadrata e non sin-

i 11 DA

qgolare la soluzione è esprimibile nella forma:

nix ii ,1

)det(1 ==⇔= −

ADBAX

è il d i d ll i iDove Di è il determinante della matrice ottenuta sosti-tuendo alla i-esima colonna della matrice A, il vettore deitermini noti B.termini noti B.

2

Page 3: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Metodo di Cramer: costo• Costo computazionale: stima del numero di operazioni pe-

santi (moltiplicazioni e divisioni) per ottenere la soluzione.( p ) p• Algoritmo di Cramer:

– n+1 determinanti nix ii ,1

)det(==

AD

– n! prodotti per determinante– n-1 moltiplicazioni per ciascun prodotto

)det(A

– n divisioni

• Costo computazionale (calcolatore 1 Giga-Flops):

( ) ( ) ( ) flops!11!1514

2 −≈+−+=c nnnnnnC

anni101.3sec107.9flops107.902ngiorni5.3sec109.2flops109.215n

41120

514

≈⇒≈⇒=≈⇒≈⇒=

c

c

CC

3

Page 4: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Sistemi lineari: metodi

• L’uso del metodo di Cramer è valido solo per sistemi di dimensione estremamente contenute (ad es 10x10)dimensione estremamente contenute (ad es. 10x10).

• Metodi diretti:– soluzione esatta in un numero finito di passi (operazioni sulla matrice);– elevata occupazione della memoria;– problemi “densi” o matrici particolari (tridiagonali,…);

efficienti per “piccoli” problemi (100x100)– efficienti per piccoli problemi (100x100).

• Metodi iterativi:– la soluzione ottenuta tramite approssimazioni successive (punto unito);la soluzione ottenuta tramite approssimazioni successive (punto unito);– soluzione esatta in un numero infinito di passi (errore di troncamento);– bassa occupazione di memoria;– problemi “sparsi” e/o di elevate dimensioni.

4

Page 5: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Sistemi lineari: condizionamento• Condizionamento: stima della “sensibilità” del

problema ad una variazione sui dati “di input”.p p• Indipendente dal metodo numerico adottato, però ne

influenza la scelta e la precisione dei calcoli.• Analisi: si perturbano i dati di ingresso e si valuta la

corrispondente variazione della soluzione.• Un problema si dice malcondizionato se ad una

“piccola” variazione sui dati “di ingresso” corrisponde “ d ” i i d ll l iuna “grande” variazione della soluzione.

• Nel caso di A non affetta da “errori”, e con δB errore sui dati (sul termine noto B):sui dati (sul termine noto B):

BAA

X δδ 1−≤B

AAX

≤5

Page 6: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Sistemi lineari: condizionamento

• Detti ||δA|| e ||δB|| l’errore sui coefficienti e sul termine noto, e con ||δX|| l’errore sulla soluzione, si ha:

⎟⎞

⎜⎛ ABAX δδδ )(K

⎟⎟⎠

⎞⎜⎜⎝

⎛+

−≤

AA

BB

AA

A

AXX δδ

δδ

)(1

)(

K

K

A

• Dove K(A)=||A||·||A-1|| è il numero di condizionamentoDove K(A) ||A|| ||A || è il numero di condizionamentodi A, con 1 ≤ K(A)≤ ∞; nel caso di norma spettrale e per matrici simmetriche e definite positive:

minmax2 /)( λλ=AK

6

Page 7: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Condizionamento: esempio

⎨⎧ =+ 121 109 bxx

Esempio 4.3.1:⎩⎨ =+ 221 98 bxx

se p o .3. :

%101.010.000.0

90.000.1

1

1

2

1

2

1 =≈

⎪⎪⎪⎫

⎥⎦

⎤⎢⎣

⎡++

=⎥⎦

⎤⎢⎣

⎡⇒⎥

⎤⎢⎣

⎡=⎥

⎤⎢⎣

⎡BBδ

xx

bb

%3606319.001.1

1

1

11

22

==

⎪⎪

⎪⎪⎬

⎥⎤

⎢⎡+

=⎥⎤

⎢⎡

⇒⎥⎤

⎢⎡

=⎥⎤

⎢⎡

⎦⎣⎦⎣⎦⎣⎦⎣

Xδxb%3606.3

07.089.0122

==⎪⎪⎭

⎥⎦

⎢⎣−

=⎥⎦

⎢⎣

⇒⎥⎦

⎢⎣

=⎥⎦

⎢⎣ Xxb

361)(1

111 == −AAAKNumero di condizionamento:

• Esercizi consigliati [GL] 2 3 2 5 7 52• Esercizi consigliati [GL] 2.3, 2.5, 7.527

Page 8: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Metodi iterativi: generalità• Sono basati su una trasformazione del problema in uno

equivalente dalla struttura più semplice tramite una d i i d ll t i d i ffi i ti ( litti )decomposizione della matrice dei coefficienti (splitting).

• Il problema equivalente è risolto per mezzo di una procedura iterativa di approssimazioni successiveprocedura iterativa di approssimazioni successive.

• Sono applicati a problemi “grandi” e/o “sparsi”.

( ) ( )

( ) ( )⎪

⎪⎨⎧

+∑=

+=⇔+=⇔= +

+

+n kk

kk

qxcx 1

1 QCXXQCXXBAX

NMA 31⎪⎩

+∑==

=−=

+=

−i

jjiji qxcx

1BMQNMC

NMA

1

143421

C è detta matrice di iterazione.

8

Page 9: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Metodi iterativi: convergenzaUn metodo iterativo fornisce la soluzione esatta (in assenza di errori di arrotondamento) in un numero infinito di passi; ) p ;si definisce errore di troncamento, la quantità:

( ) ( )kk XXE −=Un metodo iterativo è detto convergente se:

XXE =

( )k( ) 0E =∞→

k

klim

Teorema: condizione sufficiente affinché il metodoTeorema: condizione sufficiente affinché il metodo iterativo sia convergente qualunque sia il vettore iniziale X(0) è che sia ||C||<1.|| ||

Teorema: il metodo iterativo converge, qualunque sia il vettore iniziale X(0), se e solo se ρ(C)<1.vettore iniziale X , se e solo se ρ(C) 1.

9

Page 10: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Metodi iterativi: definizioni

Per un metodo iterativo convergente sotto la condizione||C||< 1 fissata una certa tolleranza ε la procedura iterativa||C||< 1, fissata una certa tolleranza ε, la procedura iterativa può essere arrestata quando l’indice di iterazione k è tale che:

( ) ( )+ kk XX 1 i i di( ) ( ) ε≤−+ kk XX 1 Criterio di arresto

In tal caso, per l’errore commesso rispetto alla soluzione , p pesatta, si hanno le seguenti stime:

( ) ( ) ( )kkk XXC

E ≤ ++ 11 Sti t i i( ) ( ) ( )XXC

E −−

≤1 Stima a posteriori

( ) ( ) ( )011

1 C ++

kk( ) ( ) ( )011

1XX

CC

E −−

≤+k Stima a priori

E i i i li t [GL] 7 41• Esercizio consigliato [GL] 7.4110

Page 11: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Metodi iterativi: decomposizione di A

I metodi iterativi sono basati su uno “splitting” della i d i ffi i i dmatrice dei coefficienti: A=L+D+U, dove:

⎥⎤

⎢⎡ 0000 L

⎥⎥⎥⎥⎥

⎢⎢⎢⎢⎢

=⎩⎨⎧

≤>

= 00000

0 3231

21

LLLLLLL

ijij aa

a

jijial L

Triangolare inferiore

=⎩⎨⎧

≠==

⎥⎦⎢⎣ −

),,,(0

0

2211

121

L

L

nnii

ij

nnnn

aaadiagjijiad

aaa

D Diagonale

⎥⎥⎤

⎢⎢⎡

⎨⎧ <

⎩ ≠

000

0

222

11312LL

n

n

ijaaaaa

jia

ji

U

g

Triangolare

⎥⎥⎥⎥

⎦⎢⎢⎢⎢

=⎩⎨⎧

≥<

=−

00000000

1LL

LLLLL

nn

ijij

ajijiau U

go esuperiore

11

Page 12: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Metodi iterativi: Jacobi

Posto M=D e N=L+U, si ha: X=-D-1(L+U)X+D-1B=CJX+QJ

⎥⎥⎤

⎢⎢⎡ −−0

11

1

11

12 L n

aa

aa

i di i i

⎥⎥⎥⎥⎥

⎢⎢⎢⎢⎢

−−= 022

2

22

21

J

LOLL

L n

aa

aa

CMatrice di iterazione

di Jacobi

⎥⎥⎥

⎦⎢⎢⎢

⎣−− 021 L

nn

n

nn

n

aa

aa

Quindi, l’algoritmo di Jacobi fornisce la successione:⎞⎛

0,11

1

)()1(J

)(J

)1(

≥=

⎟⎟⎟

⎜⎜⎜

⎛+−=⇔+= ∑

≠=

++

knibxa

ax

n

ijj

ik

jijii

ki

kk QXCX

⎠⎝ ≠ij

12

Page 13: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Metodi iterativi: Gauss-Seidel

Il metodo di Gauss-Seidel fa uso dei valori già calcolati:

0,11

1

)(1

1

)1()1(

≥=

⎟⎟⎠

⎞⎜⎜⎝

⎛+−−= ∑∑

+=

=

++

kni

bxaxaa

x i

n

ij

kjij

i

j

kjij

ii

ki

In forma compatta, posto:p , p

UNLDM =+=

( ) ( ) 11 QXCBLDUXLDX +=+++−= −−

Ottenendosi:

( ) ( ) GSGS QXCBLDUXLDX +=+++=

13

Page 14: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Jacobi & Gauss-Seidel: convergenzaTeorema: se A è diagonalmente dominante, per righe o per

colonne, i metodi di Jacobi e di Gauss-Seidel sono ,convergenti per qualunque valore del vettore X(0).

Corollario: il metodo di Jacobi (Gauss-Seide) converge se eCorollario: il metodo di Jacobi (Gauss-Seide) converge se e solo se ρ(CJ )<1 (ρ(CGS )<1), qualunque sia X(0).

T A è i t i d fi it iti il t d diTeorema: se A è simmetrica e definita positiva, il metodo di Gauss-Seidel è convergente per qualunque valore di X(0).

Criterio di Sylvester: condizione necessaria e sufficiente affinché una matrice quadrata e simmetrica sia definita positi a è che:positiva è che:

( ) nkk ,,2,10det K=>A

14

Page 15: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Jacobi & Gauss-Seidel: esempio

E i 4 5 1 ifi l d i t di diEsempio 4.5.1: verificare la convergenza dei metodi di Jacobi e di Gauss-Seidel per i seguenti problemi:problemi:

⎤⎡ 211 ⎤⎡ 101

⎥⎥⎤

⎢⎢⎡ −

= 212211

A ⎥⎥⎤

⎢⎢⎡

= 011101

A⎥⎥⎦⎢

⎢⎣ 122 ⎥

⎥⎦⎢

⎢⎣ 111

• Esercizi consigliati [GL] 2.20, 2.21, 7.16

15

Page 16: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Metodi iterativi: S.O.R.

Il metodo S.O.R. (successive over relaxation) si ottiene dal rilassamento della soluzione fornita dal metodo GS:rilassamento della soluzione fornita dal metodo GS:

⎪⎪⎧

⎟⎟⎠

⎞⎜⎜⎝

⎛+−−=

−++ ∑∑1~ )(

1)1()1( bxaxa

ax i

nk

jij

ik

jijk

i

( )⎪⎪⎩

⎪⎨ ≥=

−+=

⎟⎠

⎜⎝

++

+== 0,1

1~ )()1()1(

11 kni

xxx

a

kj

ki

ki

ijjii

ωω ( )⎩ jii

Con ω∈ℜ+ parametro di rilassamento, posto:

( ) ωωω /1/ −−=+= DUNLDM

si ottiene:

( ) ( )[ ] ( ) ωωωωωωω QXCBLDXDULDX +=++−−+−= −− 11 1

si ottiene:

16

Page 17: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Metodo S.O.R.: convergenza

Si dimostra che ρ(Cω )≥|1-ω|, da cui:

Lemma: condizione necessaria affinché il metodo di rilassamento converga è che ω∈(0,2).

Teorema: se A è simmetrica e definita positiva, la condizione 0<ω<2 è necessaria e sufficiente per lacondizione 0<ω<2, è necessaria e sufficiente per la convergenza del metodo S.O.R., qualunque sia X(0).

Teorema: se A è tridiagonale e definita positiva, la convergenza del metodo S.O.R. è massima per:

( )GS112

Cρω

−+= • Esercizi consigliati [GL] 2.29, 2.30( )GS11 Cρ+

17

Page 18: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Metodi iterativi: esempio

E i [GL] 2 30 C l l l l ità i t ti diEsempio [GL] 2.30: Calcolare la velocità asintotica di convergenza dei metodi di Jacobi, Gauss-Seidel e S.O.R. con parametro ottimo, applicati alla soluzioneS.O.R. con parametro ottimo, applicati alla soluzione del sistema algebrico avente come matrice dei coefficienti la matrice:

⎤⎡ − 022

⎥⎥⎥⎤

⎢⎢⎢⎡

−−= 132022

A⎥⎦⎢⎣ − 410

18

Page 19: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Metodi iterativi: esempio

⎥⎥⎤

⎢⎢⎡

−−

+⎥⎥⎤

⎢⎢⎡

+⎥⎥⎤

⎢⎢⎡−=++= 100

020030002

002000

UDLA⎥⎥⎦⎢

⎢⎣⎥

⎥⎦⎢

⎢⎣⎥

⎥⎦⎢

⎢⎣ − 000400010

( ) ⎥⎤

⎢⎡

− 3/103/2010

1 ULDC

Jacobi

( ) ⎥⎤

⎢⎡

+ − 3/13/20010

1ULDC

Gauss-Seidel

( )⎥⎥⎥

⎦⎢⎢⎢

=+−=04/103/103/21

J ULDC

01⎪⎧ =λ

( )⎥⎥⎥

⎦⎢⎢⎢

=+−=12/16/103/13/20GS ULDC

0⎧ =λ

2/32/3

3

2

1

⎪⎩

⎪⎨

−=+=

λλλ

4/300

3

2

1

⎪⎩

⎪⎨

===

λλλ

( )( )[ ] 06247.0Log

8660.02/3

JJ

J

≈−=≈=

CC

ρρV

( )( )[ ] 1249.0Log

75.04/3

GSGS

GS

≈−===C

ρV

19

Page 20: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Metodi iterativi: esempio

Succesive Over Relaxation

( ) 342

0 ==ω

Succesive Over Relaxation

( ) 311 GS0 −+ Cρ

⎥⎤

⎢⎡ − 03/43/1

( ) ( )[ ]⎥⎥⎥

⎢⎢⎢

−−−=−−+−= −

27/581/2381/89/427/2327/81 00

10OPT DULDC ωωω

( ) 3333.03/13/1

OPT1 ≈=⎪

⎧ −=Cρ

λ ( )( )[ ] 4771.0Log

3333.03/1

3/13/1

OPTOPT

OPT

3

2 ≈−=≈

⎪⎩

⎪⎨

−=+=

CC

ρρ

λλ

V

20

Page 21: Sistemi lineari: generalità - Home | Dipartimento di Scienze di …riccardo.broglia/Didattica/PMN2009... · 2011. 6. 2. · Sistemi lineari: metodi •L’uso del metodo di Cramer

Metodi iterativi: esempio

100

100

Residuo in norma L2

10-2

ω=1.1ω=1.2ω=4/3ω=1.4ω 1 5

10-2

10JacobiGauss-SeidelSOR Ottimo

10-6

10-4

ω=1.5

10-6

10-4

10-8

10-8

10-12

10-10

10-12

10-10

0 10 20 30 40 50 60 70 8010

-14

0 20 40 60 80 100 120 140 160 180 20010

-14

It i iIt i i IterazioniIterazioni

21