28-29Gennaio2009 [email protected] MassimilianoMartinelli SoluzioniAnaliticheeNumericheApplicateall’IngegneriaAmbientale

(1)

Metodi numerici per la risoluzione di sistemi lineari

Soluzioni Analitiche e Numeriche Applicate all’Ingegneria Ambientale

Massimiliano Martinelli

[email protected]

Università Politecnica delle Marche, Ancona Facoltà di Ingegneria

28-29 Gennaio 2009

(2)

Outline

1 Introduzione

2 Metodi numerici per la risoluzione di sistemi lineari Metodi diretti

Metodi iterativi

(3)

Outline

1 Introduzione

2 Metodi numerici per la risoluzione di sistemi lineari Metodi diretti

Metodi iterativi

(4)

Metodi iterativi

La matrice del sistema non viene modificata⇒ migliore sfruttamento della sparsità

Soluzione come limite di una successione⇒ si pone il problema della convergenza (e anche della velocità di convergenza)

Per matrici piene O(n²) operazioni ogni iterazione ⇒ metodi iterativi meno costosi dei metodi diretti se si ottiene la convergenza in un numero di iterazioni che dipende da n in modo sublineare

Possibilità di utilizzare approcci matrix-free

I metodi iterativi si possono applicare anche alla risoluzione di sistemi non-lineari

(5)

Principio dei metodi iterativi

Data una stima iniziale x⁽⁰⁾della soluzione del problema, si costruisce una successione di vettori x^(k)che verifica la proprietà di convergenza

k→∞limx^(k)= x

(6)

k→∞limx^(k)= x

Il metodo iterativo può essere scritto nella forma

x^(k+1)=ϕϕϕ_k+1(x^(k), x^(k−1), . . . , x^(k−m), A, b) per k≥ m doveϕϕϕ_k^{e x}⁽⁰⁾, . . . , x^(m)sono rispettivamente funzioni e vettori dati.

(7)

k→∞limx^(k)= x

Il metodo iterativo può essere scritto nella forma

x^(k+1)=ϕϕϕ_k+1(x^(k), x^(k−1), . . . , x^(k−m), A, b) per k≥ m doveϕϕϕ_k^{e x}⁽⁰⁾, . . . , x^(m)sono rispettivamente funzioni e vettori dati.

m è chiamato ordine del metodo

se le funzioniϕϕϕknon dipendono dal passo k, il metodo è detto stazionario, altrimenti non-stazionario

se le funzioniϕϕϕ_kdipendono linearmente dai vettori x⁽⁰⁾, . . . , x^(m)il metodo è chiamato lineare, altrimenti non-lineare

(8)

Metodi iterativi lineari

Consistenza con il sistema lineare

Sia B∈ R^n×n(matrice di iterazione). Il metodo iterativo lineare x^(k+1)= Bx^(k)+ f

è detto essere consistente con il sistema lineare Ax= b se x= Bx + f

o, equivalentemente

f= (I − B)A⁻¹b

(9)

o, equivalentemente

f= (I − B)A⁻¹b

La sola consistenza non è sufficiente per la convergenza

(10)

o, equivalentemente

f= (I − B)A⁻¹b

La sola consistenza non è sufficiente per la convergenza Convergenza di un metodo iterativo consistente

(11)

Tecnica dello splitting

Scegliere due matrici P e N tali che A= P − N

(12)

P (matrice di precondizionamento) deve essere non singolare e “facilmente”

invertibile

(13)

invertibile

Dato x⁽⁰⁾, un metodo iterativo lineare e consistente si scrive come Px^(k+1)= Nx^(k)+ b k≥ 0

(14)

invertibile

ovvero, introducendo il residuo al passo k r^(k)= b − Ax^(k) si ottiene

x^(k+1)= x^(k)+ P⁻¹r^(k)

(15)

invertibile

ovvero, introducendo il residuo al passo k r^(k)= b − Ax^(k) si ottiene

x^(k+1)= x^(k)+ P⁻¹r^(k)

La matrice di iterazione è B= P⁻¹N f= P⁻¹b

(16)

Scriviamo A= D − E − F

D è la matrice diagonale uguale agli elementi diagonali di A, e sia D invertibile (ovvero d_ii= aii6= 0 per i = 1, . . . , n)

E è la matrice di elementi e_ij= −aijse i> j, eij= 0 se i ≤ j F è la matrice di elementi f_ij= −aijse j> i, fij= 0 se j ≤ i

(17)

Scriviamo A= D − E − F

D è la matrice diagonale uguale agli elementi diagonali di A, e sia D invertibile (ovvero d_ii= aii6= 0 per i = 1, . . . , n)

E è la matrice di elementi e_ij= −aijse i> j, eij= 0 se i ≤ j F è la matrice di elementi f_ij= −aijse j> i, fij= 0 se j ≤ i







a₁₁ a₁₂ . . . a_1n a₂₁ a₂₂ . . . a_2n ... ... ... a_n1 a_n2 . . . a_nn







| {z }

A

=







a₁₁ 0

a₂₂ . ..

0 a_nn







| {z }

D

+







0 0

a₂₁ 0 ... . .. . .. a_n1 . . . a_n,n−1 0







| {z }

−E

+







0 a₁₂ . . . a_1n 0 . .. ...

. .. a_1,n−1

0 ⁰







| {z }

−F

(18)

Px^(k+1)= Nx^(k)+ b dove A= P − N Metodo di Jacobi: P= D e N = E + F

Dx^(k+1)= (E + F)x^(k)+ b ovvero x^(k+1)= x^(k)+ D⁻¹r^(k)

(19)

Px^(k+1)= Nx^(k)+ b dove A= P − N Metodo di Jacobi: P= D e N = E + F

Dx^(k+1)= (E + F)x^(k)+ b ovvero x^(k+1)= x^(k)+ D⁻¹r^(k)

(D⁻¹)ii=_d¹

ii

B_J= D⁻¹(E + F) = I − D⁻¹A Equivale a

x^(k+1)_i = 1 a_ii

bi−

i−1∑

j=1

aijx^(k)_j −

∑n j=i+1

aijx^(k)_j

con i= 1, . . . , n

(20)

Px^(k+1)= Nx^(k)+ b dove A= P − N Metodo di Gauss-Seidel: P= D − E e N = F

(D − E)x^(k+1)= Fx^(k)+ b ovvero x^(k+1)= x^(k)+ (D − E)⁻¹r^(k)

(21)

Px^(k+1)= Nx^(k)+ b dove A= P − N Metodo di Gauss-Seidel: P= D − E e N = F

(D − E)x^(k+1)= Fx^(k)+ b ovvero x^(k+1)= x^(k)+ (D − E)⁻¹r^(k)

(D − E) è la parte triangolare inferiore di A (invertibile perché gli elementi diagonali non sono nulli)

B_GS= (D − E)⁻¹F Equivale a

x^(k+1)_i = 1 a_ii

b_i−

i−1∑

j=1

a_ijx^(k+1)_j −

∑n j=i+1

a_ijx^(k)_j

con i= 1, . . . , n

(22)

Tecniche di accelerazione della convergenza

Metodo di rilassamento

Si introduce nei metodi precedenti il parametro di rilassamentoωda scegliere opportunamente

Metodo di Jacobi

x^(k+1)= x^(k)+ D⁻¹r^(k)

BJ= I − D⁻¹A Equivale a

x^(k+1)_i = 1 a_ii

bi−

i−1∑

j=1

aijx^(k)_j −

∑n j=i+1

aijx^(k)_j

con i= 1, . . . , n

(23)

Metodo di rilassamento

Si introduce nei metodi precedenti il parametro di rilassamentoωda scegliere opportunamente

Metodo di Jacobi con rilassamento (JOR)

x^(k+1)= x^(k)+ω^D⁻¹^r^(k)

BJ_ω =ω^BJ+(1 −ω)I= I −ω^D⁻¹^A Equivale a

x^(k+1)_i = ω a_ii

bi−

i−1∑

j=1

aijx^(k)_j −

∑n j=i+1

aijx^(k)_j

+ (1 −ω)x^(k)_i con i= 1, . . . , n

Consistente per ogniω6= 0 (ω= 1 metodo di Jacobi)

(24)

Metodo di Gauss-Seidel

x^(k+1)= x^(k)+ ( D − E)⁻¹r^(k)

B_GS= (D − E)⁻¹F Equivale a

x^(k+1)_i = 1 aii

b_i−

i−1∑

j=1

a_ijx^(k+1)_j −

∑n j=i+1

a_ijx^(k)_j

con i= 1, . . . , n

(25)

Metodo di Gauss-Seidel con rilassamento (SOR) x^(k+1)= x^(k)+ (1

ω^D^{− E)}⁻¹^r^(k)

B_GS_ω = (_ω¹D− E)⁻¹

(_ω¹− 1)D +F Equivale a

x^(k+1)_i = ω aii

b_i−

i−1∑

j=1

a_ijx^(k+1)_j −

∑n j=i+1

a_ijx^(k)_j

+ (1 −ω)x^(k)_i con i= 1, . . . , n

Consistente per ogniω6= 0 (ω= 1 metodo di Gauss-Seidel)

(26)

Alcuni risultati di convergenza

Se A è strettamente diagonale dominante per righe, i metodi di Jacobi e Gauss-Seidel sono convergenti

Se A è simmetrica e definita positiva, il metodo JOR è convergente con 0<ω< 2/ρ(D⁻¹A)

Se il metodo di Jacobi è convergente, allora il metodo JOR converge per 0<ω≤ 1

Per ogniω∈ R si haρ(BGS_ω) ≥ |ω− 1|; perciò il metodo SOR non converge seω≤ 0 oω≥ 2

(Teorema di Ostrowski) Se A è simmetrica e definita positiva, allora il metodo SOR converge se e solo se 0<ω< 2. Inoltre, la sua convergenza è monotona rispetto ad||·||A(ovvero||x^(k+1)− x||A< ||x^(k)− x||A)

(27)

Metodi di Richardson

Il metodo iterativo x^(k+1)= x^(k)+ P⁻¹r^kpuò essere generalizzato da x^(k+1)= x^(k)+αkP⁻¹r^k con αk∈ R

(28)

La matrice di iterazione è R(αk) = I −αkP⁻¹A

(29)

La matrice di iterazione è R(αk) = I −αkP⁻¹A Seαk=α⇒ metodo di Richardson stazionario

I metodi di Jacobi e Gauss-Seidel sono metodi di Richardson stazionari

(30)

I metodi di Jacobi e Gauss-Seidel sono metodi di Richardson stazionari Algoritmo per il metodo di Richardson

1 x^(k)soluzione approssimata al passo k

2 Calcolo del residuo: r^(k)= b − Ax^(k)

3 Soluzione del sistema lineare Pz^(k)= r^(k) α

(31)

I metodi di Jacobi e Gauss-Seidel sono metodi di Richardson stazionari Algoritmo per il metodo di Richardson

1 x^(k)soluzione approssimata al passo k

2 Calcolo del residuo: r^(k)= b − Ax^(k)

3 Soluzione del sistema lineare Pz^(k)= r^(k)

4 Calcolo del parametro di accelerazioneαk

5 Aggionamento della soluzione al passo k+ 1: x^(k+1)= x^(k)+αkz^(k)

(32)

Metodo di Richardson: analisi di convergenza

Per ogni matrice invertibile P, il metodo di Richardson stazionario è convergente se e solo se

2 Reλi

α|λi|² > 1 ∀i = 1, . . . , n doveλi∈ C sono gli autovalori di P⁻¹A.

(33)

Metodo di Richardson: analisi di convergenza

Per ogni matrice invertibile P, il metodo di Richardson stazionario è convergente se e solo se

2 Reλi

α|λi|² > 1 ∀i = 1, . . . , n doveλi∈ C sono gli autovalori di P⁻¹A.

Se P⁻¹A ha autovalori reali e positivi, allora il metodo di Richardson stazionario è convergente se e solo se

0<α< 2 λmax

inoltre, il raggio spettrale della matrice di iterazione I−α^P⁻¹A è minimo per αopt= 2

λmin+λmax

(34)

Scelta della matrice di precondizionamento P

Il metodo di Richardson non specifica come scegliere P e, in generaleαk

Mancanza di risultati teorici riguardo alla scelta ottimale di P

(35)

Scegliendo P= A si ha convergenza in una iterazione (ma l’obiettivo è proprio risolvere Ax= b)

(36)

In pratica, si cercano matrici di precondizionamento P tali che P⁻¹A≈ I dove P è facilmente invertibile

(37)

Diverse strategie per la scelta (e il calcolo) di P:

Matrice di precondizionamento diagonale (analoga a quella usata nel metodo di Jacobi)

Fattorizzazione LU Incompleta (ILU)

Precondizionatori polinomiali (polinomiale di Neumann, “minimi quadrati”,. . . )

(38)

Diverse strategie per la scelta (e il calcolo) di P:

Matrice di precondizionamento diagonale (analoga a quella usata nel metodo di Jacobi)

Fattorizzazione LU Incompleta (ILU)

Precondizionatori polinomiali (polinomiale di Neumann, “minimi quadrati”,. . . )

(39)

Fattorizzazione ILU(p)

ILU(0)

Sia A una matrice tale che la fattorizzazione LU non richiede il pivoting Si costruiscono due matrici ˜L triangolare inferiore e ˜U triangolare superiore tali che:

L e ˜˜ U abbiano la stessa struttura di sparsità di D− E e D − F ( ˜L ˜U)ij= aijse aij6= 0

⇒ Stessa quantità di memoria necessaria per A (nessun fill-in)

(40)

ILU(0)

⇒ Stessa quantità di memoria necessaria per A (nessun fill-in) Permettendo il fill-in si ha una fattorizzazione di A più accurata

Per esempio si può considerare la fattorizzazione ILU(0) della matrice ˜L ˜U⇒ ILU(1) e cosi via⇒ ILU(p)

(41)

ILU(0)

L’esistenza della fattorizzazione ILU non è garantita per tutte le matrici invertibili⇒ Esistenza per matrici a diagonale dominante, M-matrici, . . .

(42)

ILU(0)

L’esistenza della fattorizzazione ILU non è garantita per tutte le matrici invertibili⇒ Esistenza per matrici a diagonale dominante, M-matrici, . . . Esistono varianti per la riduzione del fill-in (ILUT, MILU,. . . )

(43)

Sia A simmetrica e definita positiva e siaΦ(y) =1

2y^TAy− y^Tb x è soluzione di Ax= b ⇔Φ(x) = min

y∈RⁿΦ(y)

(44)

y∈RⁿΦ(y) Domanda

Come determinare x∈ Rⁿche minimizzaΦ(y), partendo da un punto x⁽⁰⁾?

(45)

y∈RⁿΦ(y)

Domanda

Come determinare x∈ Rⁿche minimizzaΦ(y), partendo da un punto x⁽⁰⁾? Metodo del gradiente (o Steepest Descent)

(46)

y∈RⁿΦ(y)

Domanda

Si calcola la direzione di massima pendenza (locale):

∇Φ(x^(k)) = Ax^(k)− b = −r^(k)

(47)

y∈RⁿΦ(y)

Domanda

Si calcola la direzione di massima pendenza (locale):

∇Φ(x^(k)) = Ax^(k)− b = −r^(k)

Si cerca un minimo diΦlungo la direzione x^(k)+αkr^(k)⇒ differenziando Φ(x^(k+1)) =Φ(x^(k)+αkr^(k)) rispetto adαked uguagliando a zero si ha:

αk= hr^(k), r^(k)i hr^(k), Ar^(k)i

(48)

Metodo del gradiente: algoritmo Dato x⁽⁰⁾∈ Rⁿ, per k= 0, 1, . . .

1 r^(k)= b − Ax^(k)

2 αk= hr^(k), r^(k)i

hr^(k), Ar^(k)i

3 x^(k+1)= x^(k)+αkr^(k)

(49)

1 r^(k)= b − Ax^(k)

2 αk= hr^(k), r^(k)i

hr^(k), Ar^(k)i

3 x^(k+1)= x^(k)+αkr^(k)

Metodo del gradiente: convergenza

Sia A una matrice simmetrica e definita positiva. Allora il metodo del gradiente è convergente per ogni scelta del dato iniziale x⁽⁰⁾e

||e^(k+1)||A≤K₂(A) − 1 K₂(A) + 1||e^(k)||A

(50)

1 r^(k)= b − Ax^(k)

2 αk= hr^(k), r^(k)i

hr^(k), Ar^(k)i

3 x^(k+1)= x^(k)+αkr^(k)

Metodo del gradiente: convergenza

Sia A una matrice simmetrica e definita positiva. Allora il metodo del gradiente è convergente per ogni scelta del dato iniziale x⁽⁰⁾e

||e^(k+1)||A≤K₂(A) − 1 K₂(A) + 1||e^(k)||A

λ

(51)

Metodo del gradiente⇒ Scelta di una direzione di discesa (∇Φ(x^(k)) = −r^(k)) + minimizzazione lungo quella direzione

(52)

Possibili altre scelte per la direzione di discesa

(53)

Ottimalità rispetto ad una direzione

Una direzione x^(k)è detta essere ottimale rispetto ad una direzione p6= 0 se Φ(x^(k)) ≤Φ(x^(k)+λp) ∀λ∈ R

(54)

Se x^(k)è ottimale rispetto a p alloraΦammette un minimo locale lungo p per λ= 0, e quindi

0=∂Φ

∂λ^(x^(k)⁺λp) _λ₌₀=h

hp, (Ax^(k)− b)i +λhp, Apii

λ=0

= −hp, r^(k)i

(55)

Se x^(k)è ottimale rispetto a p alloraΦammette un minimo locale lungo p per λ= 0, e quindi

0=∂Φ

∂λ^(x^(k)⁺λp) _λ₌₀=h

hp, (Ax^(k)− b)i +λhp, Apii

λ=0

= −hp, r^(k)i

x^(k)è ottimale rispetto a p⇔ p è ortogonale al residuo r^(k)

(56)

Nel metodo del gradiente x^(k+1)è ottimale rispetto a r^(k)(ovvero r^(k+1)⊥ r^(k) ), infatti

hr^(k+1), r^(k)i = hb − Ax^(k+1), r^(k)i

= hb − A

x^(k)+ hr^(k), r^(k)i hr^(k), Ar^(k)ir^(k)

, r^(k)i

= hr^(k), r^(k)i − hr^(k), r^(k)i

hr^(k), Ar^(k)ihAr^(k), r^(k)i

= hr^(k), r^(k)i − hr^(k), r^(k)i

= 0

(57)

hr^(k+1), r^(k)i = hb − Ax^(k+1), r^(k)i

= hb − A

, r^(k)i

= hr^(k), r^(k)i − hr^(k), r^(k)i

hr^(k), Ar^(k)ihAr^(k), r^(k)i

= hr^(k), r^(k)i − hr^(k), r^(k)i

= 0

La iterata successiva x^(k+2)non è più ottimale rispetto a r^(k)

(58)

hr^(k+1), r^(k)i = hb − Ax^(k+1), r^(k)i

= hb − A

, r^(k)i

= hr^(k), r^(k)i − hr^(k), r^(k)i

hr^(k), Ar^(k)ihAr^(k), r^(k)i

= hr^(k), r^(k)i − hr^(k), r^(k)i

= 0

La iterata successiva x^(k+2)non è più ottimale rispetto a r^(k)

Domanda