Metodi classici
I metodi iterativi per la soluzione dei sistemi lineari vengono usati in alternativa ai metodi diretti (eliminazione Gaussiana) quando il numero di equazioni/incognite `e elevato e la matrice dei coefficienti `e sparsa. In tal caso, i metodi iterativi sono pi`u veloci e richiedono meno memorizzazione dei metodi diretti. Un metodo iterativo per risolvere un sistema lineare A x= b
parte, in generale, da una stima iniziale x(0) e costruisce una successione di vettori{x(k)}che converge alla soluzione. Vedremo tre metodi classici: quello di Jacobi, quello di Gauss-Seidele quello di Gauss-Seidel con rilassamento.
Metodi iterativi
Il metodo di Jacobi
Consideriamo il sistemaA x= be scriviamo esplicitamente le equazioni:
a11x1+ a12x2+ ... + a1nxn= b1
a21x1+ a22x2+ ... + a2nxn= b2
...
an1x1+ an2x2+ ... + annxn = bn
Risolviamo ora lai−esima equazione per l’incognita diagonalexi, sotto l’ipotesi cheaii6= 0 per ognii = 1, 2, ..., n:
Metodi iterativi
Il metodo di Jacobi
x1= [b1− (a12x2+ ... + a1nxn)] /a11 x2= [b2− (a21x1+ ... + a2nxn)] /a22 ... xn= [bn− (an1x1+ an2x2+ ...)] /ann ovvero x1= 0 @b1−X j6=1 a1jxj 1 A/a11 x2= 0 @b2−X j6=2 a2jxj 1 A/a22 ... xn= 0 @bn−X j6=n anjxj 1 A/ann
Metodi iterativi
Il metodo di Jacobi
Supponiamo ora di aver ottenuto il vettore{x(k)} dellak−esima iterazione. L’iterazione successiva viene allora data da
x(k+1)1 = b1−X j6=1 a1jx(k)j /a11 x(k+1)2 = b2−X j6=2 a2jx(k)j /a22 ... x(k+1)n = bn−X j6=n anjx(k)j /ann
L’ipotesi aii6= 0per ognii`e una condizione necessaria (ma non sufficiente !!) per la convergenza del metodo.
Metodi iterativi
Il metodo di Jacobi - Esempio
7 x1+ 3 x2+ x3= 18 2 x1− 9 x2+ 4 x3= 12 x1− 4 x2+ 12 x3= 6
Risolvendo per le ingognite diagonali otteniamo lo schema iterativo:
x(k+1)1 = (18 − 3 x(k)2 − x(k)3 )/7 x(k+1)2 = (2 x(k)1 + 4 x(k)3 − 12)/9 x(k+1)3 = (6 − x(k)1 + 4 x(k)2 )/12
Metodi iterativi
Il metodo di Gauss-Seidel
Riprendiamo lo schema iterativo di Jacobi:
x(k+1)1 = 0 @b1−X j6=1 a1jx(k)j 1 A/a11 x(k+1)2 = 0 @b2−X j6=2 a2jx(k)j 1 A/a22 ... x(k+1)n = 0 @bn−X j6=n anjx(k)j 1 A/ann `
E chiaro che, una volta determinatox(k+1)1 dalla prima equazione, possiamo utilizzare il nuovo valore nelle equazioni successive, al posto dix(k)1 . Lo stesso dicasi perx(k+1)2 nelle equazioni dalla terza in poi, e cos`ı via per le altre incognite.
Metodi iterativi
Il metodo di Gauss-Seidel
Lo schema iterativo che si ottiene in tal guisa `e detto metodo di Gauss-Seidel: x(k+1)1 = b1−X j6=1 a1jx(k)j /a11 x(k+1)2 = b2− a21x(k+1)1 −X j≥3 a2jx(k)j /a22 x(k+1)3 = b3− a31x(k+1)1 − a32x(k+1)2 −X j≥4 a3jx(k)j /a33 ... x(k+1)n = bn−X j<n anjx(k+1)j /ann
Metodi iterativi
ovvero x(k+1)i = bi− i−1 X j=1 aijx(k+1)j − n X j=i+1 aijx(k)j /aiiMetodi iterativi
Versioni matriciali: Jacobi
Il metodo di Jacobi `e equivalente a scrivere la matrice dei coefficienti,A, come somma della sua parte diagonale e di quella non diagonale,A= D + R, dove
D= a11 0 0 ... 0 0 a22 0 ... 0 0 0 ... ... 0 0 0 0 ... ann R= 0 a12 a13 ... a1n a21 0 a23 ... a2n ... ... ... ... ... an1 an2 an3 ... 0
Il sistemaA x= bsi pu`o scrivere allora: (D + R) x = b, ovvero
D x= b − R x. Quindix= D−1(b − R x)e l’algoritmo iterativo di Jacobi si pu`o scrivere come
x(k+1) = D−1(b − R x(k)) = T x(k)+ c.
Metodi iterativi
Versioni matriciali: Gauss-Seidel
Per il metodo di Gauss-Seidel scriviamo ancora A= D + R, ma poniamo inoltreR= −L − U, dove
L = − 0 0 0 ... 0 a21 0 0 ... 0 a31 a32 0 ... 0 ... ... ... ... ... an1 an2 an3 ... 0 U = − 0 a12 a13 ... a1n 0 0 a23 ... a2n ... ... ... ... ... 0 0 0 ... an−1,n 0 0 0 ... 0
Metodi iterativi
Il sistemaA x= bsi pu`o scrivere allora: (D − L − U) x = b, ovvero
(D − L) x = U x + b. Quindix= (D − L)−1(U x + b) e l’algoritmo iterativo di Gauss-Seidel si pu`o scrivere come
x(k+1)= (D − L)−1(U x(k)+ b) = T x(k)+ c.
doveT≡ (D − L)−1Uec= (D − L)−1b.
Forme matriciali
Le forme matriciali per il metodo di Jacobi e di Gauss-Seidel torneranno utili per l’analisi di convergenza dei metodi.
Metodi iterativi
Convergenza dei metodi iterativi
Abbiamo visto che i metodi di Jacobi e di Gauss-Seidel in forma matriciale si scrivono x(k+1)= T x(k)+ c, doveT≡ −D−1Rper Jacobi e T≡ (D − L)−1Uper Gauss-Seidel. Il teorema principale sulla convergenza dice che
Theorem
Per ogni vettorex(0) ∈ Rn, la successione{x(k)} definita da
x(k+1)= T x(k)+ c,
converge all’unica soluzione del problema x= T x + cse e solo se
ρ(T) < 1.
Per la dimostrazione del teorema, abbiamo bisogno di un lemma preparatorio.
Metodi iterativi
Lemma
SiaT una matricen × n e siaρ(T)il suo raggio spettrale. Se
ρ(T) < 1 allora la matriceI− T`e invertibile e
(I − T)−1 = I + T + T2+ ... = ∞ X n=0 Tn Dimostrazione
Cominciamo con l’osservare che, se T x= λ x(cio`e seλ`e un autovalore di T) allora1 − λ`e un autovalore dtI− T, infatti(I − T) x = (1 − λ) x. Ma, per ipotesi,ρ(T) < 1e quindi|λ| < 1per ogni autovalore. Di conseguenza, la matriceI− Tnon ha autovalori nulli ed `e invertibile. Sia ora
Sm= I + T + T2+ ... + Tm=Pm
n=0Tn. Allora
Metodi iterativi
Ora, dall’ipotesiρ(T) < 1segue cheT`e convergente, e quindi
lim m→∞(I − T) Sm= lim m→∞(I − Tm+1) = I da cui (I − T)−1= lim m→∞Sm= ∞ X n=0 Tn
Dimostrazione del teorema
Dimostriamo prima che seρ(T) < 1la successione converge. Consideriamo la successione x(k) = T x(k−1)+ c = T(T x(k−2)+ c) + c = T2x(k−2)+ (T + I) c ... = Tkx(0)+ (Tk−1+ Tk−2+ ... + I) c
Metodi iterativi
Riassumendo,
x(k)= Tkx(0)+ (Tk−1+ Tk−2+ ... + I) c
Ma ρ(T) < 1, quindi T`e convergente e quindi
lim
k→∞ Tkx(0) = 0
e quindi, per il lemma precedente,
lim k→∞x(k)= ∞ X n=0 Tn ! c= (I − T)−1c
La successione{x(k)}converge pertanto al vettorex= (I − T)−1c, ed abbiamox= T x + c.
Metodi iterativi
Supponiamo ora che la successione {x(k)}converga alla soluzione (unica) dix= T x + ce dimostriamo che deve essereρ(T) < 1. Dimostreremo in realt`a l’affermazione equivalente cheT`e
convergente. Sia alloraz∈ Rn arbitrario e siaxla soluzione (unica) di x= T x + c. Poniamox(0)= x − ze costruiamo la successione
x(k)= T x(k−1)+ c; per ipotesi,{x(k)} converge adx e
x− x(k) = (T x + c) − (T x(k−1)+ c) = T (x − x(k−1)) = T2(x − x(k−2)) = ... = Tk(x − x(0)) = Tkz E pertanto lim k→∞Tkz= lim k→∞(x − x(k)) = 0
Metodi iterativi
Alcuni fatti importanti
Elenchiamo di seguito alcuni teoremi sulla convergenza dei metodi iterativi senza dimostrarli; comunque essi seguono dai teoremi visti in precedenza.
Sia||T|| < 1in qualunque norma naturale e sia c∈ Rn un vettore dato. Allora la successione{x(k)}data da
x(k+1) = T x(k)+ cconverge, per ognix(0)∈ Rn ad un vettore
x∈ Rn e valgono le seguenti limitazioni sull’errore:
1 ||x − x(k)|| ≤ ||T||k
||x(0)− x||;
2 ||x − x(k)|| ≤ 1−||T||||T||k ||x(1)− x(0)||;
SeA`e a dominanza diagonale stretta, allora i metodi di Jacobi e di Gauss-Seidel convergono per qualunque scelta della stima inizialex(0);
il raggio spettrale d`a una misura della rapidit`a della convergenza del metodo iterativo,||x(k)− x|| ≈ ρ(T)k||x(0)− x||.
Metodi iterativi
Alcuni fatti importanti: teorema di Stein-Rosenberg
Indichiamo conTJ eTG le matriciTrispettivamente del metodo di Jacobi e di Gauss-Seidel e siaAla matrice dei coefficienti del sistema. Allora, seaii > 0per ogniieaij ≤ 0per ognii 6= j, una e solo una delle seguenti affermazioni `e vera:
0 ≤ ρ(TG) < ρ(TJ) < 1;
1 < ρ(TJ) < ρ(TG);
ρ(TJ) = ρ(TG) = 0 ρ(TJ) = ρ(TG) = 1.
Vediamo che, sotto le ipotesi particolari enunciate nel teorema, quando uno dei due metodi converge allora convergono entrambi, Gauss-Seidel facendolo con maggior rapidit`a (vedi prima
affermazione) e che quando un metodo diverge allora divergono entrambi (seconda affermazione).
Metodi iterativi
Il Successive Over Relaxation Method, SOR
Dalle considerazioni precedenti, `e chiaro che un metodo iterativo converge tanto pi`u rapidamente quanto pi`u piccolo `e il raggio spettrale della matrice che lo caratterizza. `E pertanto vantaggioso scegliere un metodo iterativo che abbia raggio spettrale il pi`u piccolo possibile. Questo sogno si pu`o realizzare con il metodo del sovrarilassamento (Successive Over
Relaxation Method, SOR).
Riprendiamo la formula iterativa esplicita (non matriciale) del metodo di Gauss-seidel e riportiamola subito sotto in forma matriciale: x(k+1)i = bi− i−1 X j=1 aijx(k+1)j − n X j=i+1 aijx(k)j /aii x(k+1)= D−1(b + L x(k+1)+ U x(k))
Metodi iterativi
Il Successive Over Relaxation Method, SOR
Il metodo SOR consiste in una variante del metodo di
Gauss-Seidel, in cui il valorex(k+1) viene ottenuto mediante una media pesata tra il valore fornito dall’iterazione di Gauss-Seidel (che riportiamo qui sotto per completezza) ed il valorex(k)
dell’iterazione precedente:
x(k+1) = D−1(b + L x(k+1)+ U x(k))
x(k+1) = ω D−1(b + L x(k+1)+ U x(k)) + (1 − ω)x(k)
doveω > 0`e un parametro reale, per ora arbitario. Moltiplicando l’ultima equazione da sinistra perD,
Metodi iterativi
Riprendiamo: D x(k+1)= ω (b + L x(k+1)+ U x(k)) + (1 − ω) D x(k) da cui (D − ωL)x(k+1)= (ω U + (1 − ω) D) x(k)+ ω b x(k+1)= (D − ωL)−1(ω U + (1 − ω) D) x(k) +ω (D − ωL)−1bLo schema iterativo SOR pu`o dunque essere scritto nella usuale forma matricialex(k+1)= T x(k)+ c, dove
T= Tω≡ (D − ωL)−1(ω U + (1 − ω) D)e
Metodi iterativi
Le propriet`a di convergenza del metodo dipendono dunque dalla matriceTω. Nella pratica, per`o, la versione matriciale `e usata solo per l’analisi di convergenza; per la stesura degli algoritmi si preferisce la forma esplicita scalare
x(k+1)i = ω aii bi− i−1 X j=1 aijx(k+1)j − n X j=i+1 aijx(k)j + (1 − ω) x(k)i per i = 1, 2, ..., n. Convergenza di SOR
Al problema di determinare il valore ottimale diωper un dato sistema
A x= b non si pu`o dare una risposta a priori, e molto si deve lasciare all’esperienza. Esistono comunque dei risultati parziali, che valgono in alcune circostanze. Ne citiamo tre dimostrando solo il primo.
Metodi iterativi
Theorem (Teorema di Kahan)
SiaA x= b il sistema lineare da risolvere. Seaii6= 0 per ognii, allora ρ(Tω) ≥ |ω − 1|. Pertanto, il metodo iterativo SOR converge solo se0 < ω < 2.
Dimostrazione
Ricordiamo cheTω= (D − ωL)−1(ω U + (1 − ω) D). SiccomeD− ωL`e una matrice triangolare inferiore i cui elementi diagonali sono gli elementi diagonali diD, abbiamo cheDet((D − ωL)) = Det(D)e
Det((D − ωL)−1) = Det(D−1)e, con ragionamento analogo,
Det(ω U + (1 − ω) D) = Det((1 − ω) D) = (1 − ω)nDet(D). Ne segue che Det(Tω) = (1 − ω)ne quindiQn
j=1|λj| = |1 − ω|n, conλj,j = 1, 2, ..., ngli autovalori diTω. Quindi, se|1 − ω| > 1esiste almeno un autovaloreλcon |λ| > 1e quindiρ(Tω) > 1. Allora, non pu`o essere che il massimo, in valore assoluto, degli autovalori sia minore di|1 − ω| > 1(altrimenti il prodotto di nnumeri tutti minori di|1 − ω| > 1non potrebbe dare|1 − ω| > 1come risultato) e ne segue la tesi.
Metodi iterativi
Theorem (Teorema di Ostrowski-Reich)
SiaA x= b il sistema lineare da risolvere e siaA definita positiva. Allora SOR converge per qualunque scelta iniziale x(0) se e solo se
0 < ω < 2.
Theorem
SiaA x= b il sistema lineare da risolvere e siaA definita positiva e tridiagonale. Allora ρ(TG) = [ρ(TJ)]2< 1 e la scelta ottimale per il parametro ω di SOR `e data da
ω = 2
Metodi iterativi
Esercizi
Esercizio 7.3.12: SeA`e a dominanza diagonale stretta, allora ||TJ||∞< 1.
Esercizio 7.3.14: Un oggetto si trova in uno qualunque dei punti equispaziati{x0, x1, ..., xn}. Quando si trova inxi, pu`o saltare inxi+1 o inxi−1con la stessa probabilit`a. Ora, indichiamo conPila
probabilit`a che l’oggetto, partendo dalla posizionexi, raggiunga l’estremo x0 prima dixn. Ovviamente,P0= 1ePn= 0. Siccome l’oggetto pu`o giungere inxi solo daxi+1 o daxi−1 e con la stessa probabilit`a, ne segue che
Pi=Pi−1+ Pi+1 2
Dimostrare che le probabilit`ap= (P1, P2, ..., Pn−1)obbediscono ad un sistema lineareA p= b, e determinareAeb. Risolvere il sistema per n = 10,n = 50edn = 100. Cambiare quindi le probabilit`a di salto in αed1 − α.