Sistemi lineari: generalità - Home | Dipartimento di Scienze di...
Transcript of Sistemi lineari: generalità - Home | Dipartimento di Scienze di...
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Cρ
ρV
19
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
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