Metodo di Gauss-Seidel

Avviso

I contenuti di queste slide non sono esaustivi ai fini del buon esito dell’esame. Fare riferimento anche alle lezioni tenute in aula ed ai testi consigliati:

G. Monegato, Fondamenti di Calcolo Numerico. Ed.

CLUT

A. Quarteroni, F. Saleri, ’Calcolo Scienifico, esercizi e problemi risolti con matlab e octave’ Springer.

M. Annunziato, DMI Universit `a di Salerno - documento provvisorio – p. 1/63

Metodo di Gauss-Seidel

La matrice_M è parte triangolare inferiore di_A. Sia_{M = L} (non confondere con la decomposizione_LU), compresa la diagonale principale.

Abbiamo una formula interessante dal punto di vista algoritmico:

x⁽ⁿ⁺¹⁾ = (I − L⁻¹A)x⁽ⁿ⁾+ L⁻¹b ⇒ Lx⁽ⁿ⁺¹⁾ = (L − A)x⁽ⁿ⁾+ b ⇒ (D + L0)x⁽ⁿ⁺¹⁾ = −U0x⁽ⁿ⁾+ b ⇒ x⁽ⁿ⁺¹⁾ = D⁻¹(b − L0x⁽ⁿ⁺¹⁾− U0x⁽ⁿ⁾) x⁽ⁿ⁺¹⁾ = (I − L⁻¹A)x⁽ⁿ⁾+ L⁻¹b ⇒ Lx⁽ⁿ⁺¹⁾ = (L − A)x⁽ⁿ⁾+ b ⇒ (D + L0)x⁽ⁿ⁺¹⁾ = −U0x⁽ⁿ⁾+ b ⇒ x⁽ⁿ⁺¹⁾ = D⁻¹(b − L0x⁽ⁿ⁺¹⁾− U0x⁽ⁿ⁾) x⁽ⁿ⁺¹⁾ = (I − L⁻¹A)x⁽ⁿ⁾+ L⁻¹b ⇒ Lx⁽ⁿ⁺¹⁾ = (L − A)x⁽ⁿ⁾+ b ⇒ (D + L0)x⁽ⁿ⁺¹⁾ = −U0x⁽ⁿ⁾+ b ⇒ x⁽ⁿ⁺¹⁾ = D⁻¹(b − L0x⁽ⁿ⁺¹⁾− U0x⁽ⁿ⁾) dove_D è la parte diagonale di_A,_L0 e_U0 la parte triangolare inferiore e superiore esclusa della parte diagonale.

M. Annunziato, DMI Universit `a di Salerno - documento provvisorio – p. 50/63

Metodo di Gauss-Seidel

Grazie alla struttura particolare di_L0 ed_U0, sviluppando esplicitamente le sommatorie si trova chele componenti del vettore_xxx^{(n+1)(n+1)(n+1)} che moltiplica _L0, possono essere

immediatamente sostituite durante il calcolo:

x^(k+1)_i = b_i−P

j<ia_ijx^(k+1)_j −P

j>ia_ijx^(k)_j

aii .

x^(k+1)_i = bi−P

j<iaijx^(k+1)_j −P

j>iaijx^(k)_j

a_ii .

x^(k+1)_i = b_i−P

j<ia_ijx^(k+1)_j −P

j>ia_ijx^(k)_j

aii .

x^(k+1)₁ = _a¹₁₁(b1− (a12x^(k)₂ + a13x^(k)₃ + · · · + a1nx^(k)n )) x^(k+1)₂ = _a¹₂₂(b2− (a21x^(k+1)₁ + a23x^(k)₃ + · · · + a2nx^(k)n ))

· · ·

x^(k+1)n = _a¹_nn(bn− (an1x^(k+1)₁ + an2x^(k+1)₂ + · · · + ann−1x^(k+1)_n−1 )) x^(k+1)₁ = _a¹₁₁(b₁− (a₁₂x^(k)₂ + a₁₃x^(k)₃ + · · · + a_1nx^(k)n ))

x^(k+1)₂ = _a¹₂₂(b2− (a21x^(k+1)₁ + a23x^(k)₃ + · · · + a2nx^(k)n ))

· · ·

x^(k+1)n = _a¹_nn(b_n− (a_n1x^(k+1)₁ + a_n2x^(k+1)₂ + · · · + a_nn−1x^(k+1)_n−1 )) x^(k+1)₁ = _a¹₁₁(b1− (a12x^(k)₂ + a13x^(k)₃ + · · · + a1nx^(k)n ))

x^(k+1)₂ = _a¹₂₂(b2− (a21x^(k+1)₁ + a23x^(k)₃ + · · · + a2nx^(k)n ))

· · ·

x^(k+1)n = _a¹_nn(bn− (an1x^(k+1)₁ + an2x^(k+1)₂ + · · · + ann−1x^(k+1)_n−1 ))

M. Annunziato, DMI Universit `a di Salerno - documento provvisorio – p. 51/63

Metodo di Gauss-Seidel

Il metodo di Gauss-Seidel è untentativo di accelerazione di Jacobi.

Le componenti_xxx^(k+1)_i^(k+1)_i^(k+1)_i dell’iterazione successiva in fase di calcolo, sono immediatamente utilizzate per il calcolo delle rimanenti componenti. Significa tentare di

accelerare la convergenza (ma non è sempre così) e si risparmia l’uso di due vettori _x.

M. Annunziato, DMI Universit `a di Salerno - documento provvisorio – p. 52/63

Convergenza

Bisogna predire se il metodo iterativo convergeo non converge. Dato _{Ax = b}abbiamo il metodo iterativo

xxx^{(k+1)(k+1)(k+1)}= Bx= Bx= Bx^(k)(k)(k)+ M+ M+ M⁻¹⁻¹⁻¹bbb

sia _¯x la soluzione esatta. Sull’errore assoluto_eee^(k)(k)(k)_{= ¯x − x= ¯x − x= ¯x − x}^(k)(k)(k) possiamo scrivere:

Be^(k) = B(¯x − x^(k)) = ¯x − M⁻¹b − (x^(k+1)− M⁻¹b) = BeBe^(k)(k) = B(¯x − x= B(¯x − x^(k)(k)) = ¯x − M) = ¯x − M⁻¹⁻¹b − (xb − (x^(k+1)(k+1)− M− M⁻¹⁻¹b) =b) =

= e= e= e^{(k+1)(k+1)(k+1)} ⇒ e⇒ e⇒ e^(k)(k)(k)= B= B= B^kkkeee^(0)(0)(0) Si desidera che_{limlimlimk→∞k→∞k→∞eee}^(k)(k)(k)_{= 0= 0= 0}.

M. Annunziato, DMI Universit `a di Salerno - documento provvisorio – p. 53/63

Autovalori e autovettori di una matrice

Data la matrice_{A ∈ RA ∈ RA ∈ R}^n×nn×nn×n,_{∃v 6= 0∃v 6= 0∃v 6= 0}tale che: _{Av = λvAv = λvAv = λv} dove_λλλ è uno scalare detto autovalore, e_vvvè un vettore detto autovettore.

gli autovalori si trovano dalla soluzione dell’equazione det(A − λI) = 0

det(A − λI) = 0

det(A − λI) = 0, la quale è un equazione algebrica di grado _nin_λ.

l’insieme di tuttli gli autovalori viene chiamato spettro della matrice: _σ(A)σ(A)σ(A).

il raggio spettrale è l’autovalore di modulo massimo:

ρ(A) = max_λ∈σ(A)|λ|

ρ(A) = max_λ∈σ(A)|λ|

ρ(A) = max_λ∈σ(A)|λ|.

per le norme compatibili con quelle di vettore:

ρ(A) ≤ kAk ρ(A) ≤ kAk ρ(A) ≤ kAk.

M. Annunziato, DMI Universit `a di Salerno - documento provvisorio – p. 54/63

Convergenza

Lemma:

k→∞limlim B^k = 0 ⇐⇒ ρ(B) < 1

k→∞lim B^k = 0 ⇐⇒ ρ(B) < 1

k→∞B^k = 0 ⇐⇒ ρ(B) < 1 ρ(B)ρ(B)ρ(B) è il raggio spettrale di_BBB.

Teorema: _∀x∀x∀x^(0)(0)(0) _{∈ R∈ R∈ R}ⁿⁿⁿ la successione_xxx^(0)(0)(0)_{, x, x, x}^(1)(1)(1)_{, . . ., . . ., . . .} definita da:

xxx^{(k+1)(k+1)(k+1)} = Bx= Bx= Bx^(k)(k)(k)+ c+ c+ c ∀k ≥ 0, c 6= 0∀k ≥ 0, c 6= 0∀k ≥ 0, c 6= 0

converge all’unica soluzione di_{x = Bx + c}x = Bx + cx = Bx + c se e solo se ρ(B) < 1

ρ(B) < 1ρ(B) < 1

Corollario (sufficiente): Se_{kBk < 1kBk < 1kBk < 1}per una norma di matrice, allora la successione delle_xxx^(k)(k)(k) converge alla soluzione.

M. Annunziato, DMI Universit `a di Salerno - documento provvisorio – p. 55/63

Convergenza (metodo pratico)

Può essere difficile calcolare il raggio spettrale di una matrice. Si utilizzano le altre norme indotte, più semplici da calcolare.

In Jacobi e Gauss-Seidel la matrice_MMM contiene la parte diagonale. Per questi due metodi una condizione solo sufficiente di convergenza è assicurata da:

kI − M⁻¹Ak∞ ≤ max

1≤i≤n

X

j6=i

aij

aii

 < 1 kI − M⁻¹Ak_∞ ≤ max

1≤i≤n

X

j6=i

aij

aii

 < 1 kI − M⁻¹Ak∞ ≤ max

1≤i≤n

X

j6=i

aij

aii

 < 1

vale a dire se la matrice_AAAè diagonalmente dominante per righe.

M. Annunziato, DMI Universit `a di Salerno - documento provvisorio – p. 56/63

Convergenza (metodo pratico)

Se _Aè tridiagonale, in caso di convergenza,

Gauss-Seidel converge più velocemente di Jacobi.

Se _Aè simmetrica e definita positiva Gauss-Seidel converge. Se anche_{2D − A} è definita positiva Jacobi converge.

Per matrici_Ageneriche, Jacobi o Gauss-Seidel

possono convergere o meno,indipendentemente l’uno dall’altro.

M. Annunziato, DMI Universit `a di Salerno - documento provvisorio – p. 57/63

Ordinamento e convergenza

E’ dato il sistema:

( x − 2y = −2

2x + y = 2 ρ(B_J) = 2, ρ(B_GS) = 4 ( x − 2y = −2

2x + y = 2 ρ(BJ) = 2, ρ(BGS) = 4 ( x − 2y = −2

2x + y = 2 ρ(B_J) = 2, ρ(B_GS) = 4 Jacobi e Gauss-Seidel non convergono.

Scambio di righe

( 2x + y = 2 x − 2y = −2 ( 2x + y = 2

x − 2y = −2 ( 2x + y = 2

x − 2y = −2 A

AAè diagonale dominante per righe, Jacobi e Gauss-Seidel convergono.

M. Annunziato, DMI Universit `a di Salerno - documento provvisorio – p. 58/63

Test di arresto (metodo accurato)

Quando fermare un metodo iterativo ?

TEST DI ARRESTO: ^{kb − Ax}

(k)k

kbk = kr^(k)k kbk ≤ ǫ TEST DI ARRESTO: ^{kb − Ax}

(k)k

kbk = kr^(k)k kbk ≤ ǫ TEST DI ARRESTO: ^{kb − Ax}

(k)k

kbk = kr^(k)k kbk ≤ ǫ il residuo deve essere piccolo rispetto al termine noto.

(residuo e termine noto li conosciamo)

M. Annunziato, DMI Universit `a di Salerno - documento provvisorio – p. 59/63

Test di arresto (metodo accurato)

Quanto deve essere piccolo_ǫǫǫ affinché l’errore relativo rispetto alla soluzione vera sia piccolo?

kekeke^(k)(k)(k)k = kAk = kAk = kA⁻¹⁻¹⁻¹rrr^(k)(k)(k)k ≤ kAk ≤ kAk ≤ kA⁻¹⁻¹⁻¹kkrkkrkkr^(k)(k)(k)k ≤k ≤k ≤

≤ kA≤ kA≤ kA⁻¹⁻¹⁻¹kkbkǫ ≤ ǫK(A)kxkkbkǫ ≤ ǫK(A)kxkkbkǫ ≤ ǫK(A)kxveraveraverakkk

dove_{xxxveraveravera} è il risultato vero e_K(A)K(A)K(A)il condizionamento di_AAA. Per cui:

ke^(k)k

kxkevera^(k)kk ≤ ǫK(A) = ¯ǫ ⇒ ǫ = ¯ǫ/K(A) kxkevera^(k)kk ≤ ǫK(A) = ¯ǫ ⇒ ǫ = ¯ǫ/K(A) kxverak ≤ ǫK(A) = ¯ǫ ⇒ ǫ = ¯ǫ/K(A)

fissato_¯ǫ¯ǫ¯ǫsi può stimare_ǫǫǫ e quindi usare il test di arresto. (la stima dell’errore relativo non dipende dal risultato).

M. Annunziato, DMI Universit `a di Salerno - documento provvisorio – p. 60/63

Rapidità di convergenza

Criterio affinché l’errore_eee^(k)(k)(k) si riduca di un fattore_ααα rispetto a_eee^(0)(0)(0) in_k passi.

e^(k) = B^ke⁽⁰⁾ ⇒ ke^(k)k

ke⁽⁰⁾k ≤ kB^kk ≤ kBk^k e^(k) = B^ke⁽⁰⁾ ⇒ ke^(k)k

ke⁽⁰⁾k ≤ kB^kk ≤ kBk^k e^(k) = B^ke⁽⁰⁾ ⇒ ke^(k)k

ke⁽⁰⁾k ≤ kB^kk ≤ kBk^k ossia l’errore si riduce se_{kBk < 1kBk < 1kBk < 1}.

Si vuole avere ^ke_ke^ke_ke^ke_ke^(k)₍₀₎^(k)(0)^(k)(0)^k_kk^kkk _{≤ α}≤ α≤ α, si sceglie_kBkkBkkBk^kkk _{≤ α}≤ α≤ α. k ln(kBk) ≤ ln(α) ⇒ k ≥ ln(α)/ ln(kBk) k ln(kBk) ≤ ln(α) ⇒ k ≥ ln(α)/ ln(kBk)k ln(kBk) ≤ ln(α) ⇒ k ≥ ln(α)/ ln(kBk)

M. Annunziato, DMI Universit `a di Salerno - documento provvisorio – p. 61/63

Rapidità di convergenza

Velocità di convergenza asintotica:

R(B) = − ln ρ(B)R(B) = − ln ρ(B)R(B) = − ln ρ(B)

Numero_KKK_ααα di iterazioni per ridurre l’errore di un fattore_ααα: Kα ≥ − ln α

Kα ≥ − ln αR(B) Kα ≥ − ln αR(B) R(B)

α = quantità della quale si vuole ridurre l’errore sulla stima iniziale della soluzione.

ρ(B) = ρ(B) =

ρ(B) =raggio spettrale della matrice di iterazione.

Kα = Kα =

Kα = iterazioni necessarie per ridurre l’errore di_ααα.

M. Annunziato, DMI Universit `a di Salerno - documento provvisorio – p. 62/63

Complessità computazionale

Nei metodi iterativi la complessità computazionale, per una matrice di dimensione_n, è:_KnKnKn²²²; sono eseguiti circa_{n × n} prodotti e somme per ogni iterazione;_K è il numero di iterazioni necessarie per raggiungere la precisione desiderata.

Se la matrice è sparsa e contiene_pelementi diversi da zero, omettendo di calcolare i prodotti per zero, la complessità diventa:_KpKpKp

Il metodo iterativo è competitivo con quello di eliminazione di Gauss quando:

Kp < n³

3 =⇒ K < n³ Kp < n³ 3p

3 =⇒ K < n³ Kp < n³ 3p

3 =⇒ K < n³ 3p

M. Annunziato, DMI Universit `a di Salerno - documento provvisorio – p. 63/63