SISTEMI LINEARI

(1)

SISTEMI LINEARI

PARTE II

Metodi Iterativi

(2)

Metodi iterativi

Metodi iterativi

1

Metodi iterativi

Quando `e conveniente usarli?

2

Metodi iterativi stazionari Il metodo di Jacobi

Il metodo di Gauss-Seidel Condizioni per la convergenza

3

Metodi del Gradiente

Metodo della pi `u ripida discesa

Metodo del gradiente coniugato

(3)

Metodi iterativi

1

Metodi iterativi

Quando `e conveniente usarli?

2

Metodi iterativi stazionari Il metodo di Jacobi

Il metodo di Gauss-Seidel Condizioni per la convergenza

3

Metodi del Gradiente

Metodo della pi `u ripida discesa

Metodo del gradiente coniugato

(4)

Metodi iterativi

Metodi iterativi

1

Metodi iterativi

Quando `e conveniente usarli?

2

Metodi iterativi stazionari Il metodo di Jacobi

Il metodo di Gauss-Seidel Condizioni per la convergenza

3

Metodi del Gradiente

Metodo della pi `u ripida discesa

Metodo del gradiente coniugato

(5)

Outline

1

Metodi iterativi

Quando `e conveniente usarli?

2

Metodi iterativi stazionari Il metodo di Jacobi

Il metodo di Gauss-Seidel Condizioni per la convergenza

3

Metodi del Gradiente

Metodo della pi `u ripida discesa

Metodo del gradiente coniugato

(6)

Metodi iterativi Stazionari Gradiente

Quando

Ax = b, A ∈ R

^n×n

, b ∈ R

ⁿ

Convenienti quando:

La matrice A `e sparsa e senza una particolare struttura

la dimensione n `e grande

(7)

Metodi iterativi stazionari

Idea di base

Ax = b V x = Bx + c

parto da un vettore iniziale x

⁽⁰⁾

e genero la successione

x

⁽¹⁾

= Bx

⁽⁰⁾

+ c, x

⁽²⁾

= Bx

⁽¹⁾

+ c, . . . , x

^{(k )}

= Bx

^{(k −1)}

+ c . . . ...

Teorema

La successione {x

^{(k )}

} al tendere di k all’infinito, converge alla

soluzione x del sistema se e solo se il raggio spettrale di B `e

minore di uno

(8)

Jacobi Gauss-Seidel Convergenza

Criterio di arresto

E necessario stabilire quando terminano le iterazioni. ` Il procedimento termina quando

||x^{(k +1)}−x^{(k )}||

||x^{(k +1)}||

≤ TOL

dove TOL `e una tolleranza prefissata

si supera il numero massimo di iterazioni NMAX stabilito a

priori

(9)

Algortimo e costo computazionale

Algoritmo

Input A, b, TOL, NMAX. Output x0

1

x 0 = 0

2

pongo l’errore iniziale e = 1 e k = 0 (contatore iterazioni)

3

calcolo la matrice B e il termine noto c

4

Fino a quando e > TOL & k ≤ NMAX x = B ∗ x 0 + c

e = kx − x 0k/kx k k = k + 1

x 0 = x

5

Se k > NMAX il metodo non converge, altrimenti x 0 `e la

soluzione.

(10)

Costo computazionale

Ad ogni iterazione, il costo `e dato dal costo del prodotto matrice per vettore

B ∗ x .

Quindi `e dell’ordine del numero di elementi non nulli della matrice:

Se A `e sparsa

O(s) dove s n

²

, in genere s < n

Se A `e piena

O(n

²

)

(11)

Outline

1

Metodi iterativi

Quando `e conveniente usarli?

2

Metodi iterativi stazionari Il metodo di Jacobi

Il metodo di Gauss-Seidel Condizioni per la convergenza

3

Metodi del Gradiente

Metodo della pi `u ripida discesa

Metodo del gradiente coniugato

(12)

Il metodo di Jacobi

A = D + L + U a

_ii

6= 0, i = 1 . . . , n

D =







• 0 0 0 0 • 0 0 0 0 • 0 0 0 0 •





 U =







0 • • • 0 0 • • 0 0 0 • 0 0 0 0





 L =







0 0 0 0

• 0 0 0

• • 0 0

• • • 0







La matrice di iterazione `e

B = −D

⁻¹

(L + U) e

c = D

⁻¹

b

(13)

Il metodo di Jacobi

Implementare l’algoritmo in forma vettoriale Comandi utili

>>tril(A)

Estrae la matrice triangolare inferiore inclusa la diagonale

>>triu(A)

Estrae la matrice triangolare superiore inclusa la diagonale

>>d=diag(A)

estrae la diagonale di A (d `e un vettore)

>>D=diag(d)

matrice diagonale con elementi uguali agli elementi di d

>>eig(A)

restituisce tutti gli autovalori della matrice A

(14)

Outline

1

Metodi iterativi

Quando `e conveniente usarli?

2

Metodi iterativi stazionari Il metodo di Jacobi

Il metodo di Gauss-Seidel Condizioni per la convergenza

3

Metodi del Gradiente

Metodo della pi `u ripida discesa

Metodo del gradiente coniugato

(15)

Il metodo di Gauss-Seidel

Se penso al metodo di Jacobi in forma scalare, si ha che la k + 1−esima iterazione `e definita da

x

_i^{(k +1)}

= b

_i

− P

n

j=1,j6=i

a

_ij

x

_j^{(k )}

a

_ii

, i = 1, . . . , n

Il metodo di Gauss-Seidel sfrutta le componenti dell’iterata k + 1− esima gi `a calcolate

x

_i^{(k +1)}

= b

_i

− P

i−1

j=1

a

_ij

x

_j^{(k +1)}

− P

n

j=i+1

a

_ij

x

_j^{(k )}

a

_ii

, i = 1, . . . , n In questo caso la matrice di iterazione `e

B = −(L + D)

⁻¹

U

(16)

Il metodo di Gauss-Seidel: esempio di function

function [x,iter]=gseidel(a,b,x0,nmax,toll) [n,n]=size(a); iter = 0; err=1; x = x0;

while (err> toll) & (iter <= nmax) iter = iter + 1;

x(1)=(b(1)-a(1,2:n)*x(2:n))/a(1,1);

for i=2:n-1

x(i)=(b(i)-a(i,1:i-1)x(1:i-1)- a(i,i+1:n)x(i+1:n))/a(i,i);

end

x(n)=(b(n)-a(n,1:n-1)*x(1:n-1))/a(n,n);

err = norm (x-x0) / norm(x);

x0 = x;

(17)

Outline

1

Metodi iterativi

Quando `e conveniente usarli?

2

Metodi iterativi stazionari Il metodo di Jacobi

Il metodo di Gauss-Seidel Condizioni per la convergenza

3

Metodi del Gradiente

Metodo della pi `u ripida discesa

Metodo del gradiente coniugato

(18)

Condizioni sufficienti per la convergenza

Jacobi

Se la matrice A `e a diagonale dominante V il metodo converge

Gauss-Seidel

Se la matrice A `e a diagonale dominante V il metodo converge

Se A e simmetrica definita positiva V il metodo converge

Quando entrambi convergono, il metodo di Gauss-Seidel

converge pi `u rapidamente alla soluzione. Ci `o significa che il

numero di iterazioni necessarie per raggiungere la tolleranza

(19)

Metodi del gradiente

Ax = b

A simmetrica e definita positiva

Trovare la soluzione x del sistema equivale a minimizzare la forma quadratica

f (x ) = 1

2 x

^T

Ax − x

^T

b

parto da un vettore tentativo x

⁽⁰⁾

e genero la successione x

^{(k +1)}

= x

^{(k )}

+ α

_k

p

^{(k )}

p

^{(k )}

`e la direzione lungo la quale mi sposto

α

_k

in generale `e scelto in modo che f (x

^{(k )}

+ α

_k

p

^{(k )}

) sia

minima lungo la direzione scelta

(20)

ripida discesa Gradiente coniugato

Outline

1

Metodi iterativi

Quando `e conveniente usarli?

2

Metodi iterativi stazionari Il metodo di Jacobi

Il metodo di Gauss-Seidel Condizioni per la convergenza

3

Metodi del Gradiente

Metodo della pi `u ripida discesa

Metodo del gradiente coniugato

(21)

Metodo della pi `u ripida discesa

Si sceglie

p

^{(k )}

= r

^{(k )}

= −∇f (x

^{(k )}

), dove

r

^{(k )}

= b − Ax

^{(k )}

α

_k

=

_(r^(r(k )^{(k )})⁾^T^TAr^r^{(k )}^{(k )}

Con queste scelte si ha che le direzioni p

^{(k )}

e p

^{(k +1)}

sono ortogonali. Ovvero

(r

^{(k +1)}

, r

^{(k )}

) = 0.

(22)

Metodo della pi `u ripida discesa

Convergenza

La successione x

^{(k )}

converge a x per k → ∞ La velocit `a di convergenza dipende dall’autovalore massimo λ

_M

e dall’ autovalore minimo λ

_m

. Ad ogni iterazione l’errore si riduce del fattore

λ

_M

− λ

_m

λ

_M

+ λ

m

.

Quando λ

_M

e λ

m

sono vicini la velocit `a di convergenza pu `o

essere molto lenta.

(23)

Algoritmo ...

Fino a quando e > TOL & k ≤ NMAX r = b − Ax 0

α =

_r^rT^TAr^r

x = x 0 + αr k = k + 1

e = kx − x 0k/kx k x 0 = x

....

(24)

Outline

1

Metodi iterativi

Quando `e conveniente usarli?

2

Metodi iterativi stazionari Il metodo di Jacobi

Il metodo di Gauss-Seidel Condizioni per la convergenza

3

Metodi del Gradiente

Metodo della pi `u ripida discesa

Metodo del gradiente coniugato

(25)

Metodo del gradiente coniugato

Per evitare problemi legati alla lentezza del metodo della pi `u ripida discesa, si possono scegliere le direzioni p

^{(k )}

in modo diverso.

Gradiente coniugato

Si costruiscono dei vettori A-coniugati, cio `e tali che (Ap

⁽ⁱ⁾

, p

^(j)

) = 0

Se non ci fossero gli errori di calcolo, dopo n iterazioni avrei la soluzione esatta.

>>x=pcg(A,b,toll,nmax)

fornisce la soluzione del sistema Ax = b mediante il metodo

del gradiente coniugato.

(26)