Presentazione Multigrid

Metodi

Multigrid

e analisi di metodi iterativi

(Jacobi e Gauss-Seidel)

Margherita Maria M63001118

Martina Russo M63001128

Michelle Pepe M63001196

Indice

• Generalità

Metodi Iterativi • Teorema della convergenza

• Jacobi e Gauss-Seidel: confronto

• Errore e residuo

• Elementi Multigrid

• Multigrid ed errore

Analisi Multigrid • Aliasing

• Applicazioni del metodo Multigrid

• Modi di Fourier

• Primo schema

Schemi Multigrid • Secondo schema

• Terzo schema

• Full grid

Metodi Iterativi

• Un metodo iterativo si distingue da metodi esatti, in quanto non

• Un metodo iterativo si distingue da metodi esatti, in quanto non

arriva a risolvere perfettamente un problema, ma si basa sulla

arriva a risolvere perfettamente un problema, ma si basa sulla

convergenza verso la soluzione di quest’ultimo

convergenza verso la soluzione di quest’ultimo

Metodi Iterativi

Solitamente un problema lineare si presenta nella seguente forma:

Ax=b

Ax=b

Da questa, possiamo ricavare la soluzione come :

x=(I-A)x+b

x=(I-A)x+b

Attraverso l’utilizzo dei metodi iterativi, è possibile esprimere la

soluzione dello stesso problema in relazione al passo di iterazione k-

b

esimo: x =(I-A)x +b

x =(I-A)x +b

k+1 k

k+1 k

Metodi Iterativi

Ovviamente in una situazione del genere nulla si può dire sulla convergenza

del metodo!

Tuttavia sappiamo che per ogni successiva iterazione, una nuova configurazione x viene

k+1

calcolata a partire da x

k

Consideriamo il problema scritto a questo punto sotto questa forma :

Px =(P - A)x +

k+1 k

k+1 k

b

b

La matrice P introdotta risulta essere molto utile in un metodo iterativo e prende il nome

precondizionamento.

di matrice di

Tra le possibili scelte, abbiamo: Matrice di Gauss

Matrice di Jacobi Siedel

Metodi Iterativi diminuisce

Un metodo iterativo converge se l’errore passo dopo passo

e = x -x

k k

k k

pre-condizionamento,

Sfruttando la matrice di introdotta in precedenza,

possiamo descrivere l’errore al passo successivo come segue:

Pe = Px – Px = (P-A)x + b – (P-A)x -b=

k+1 k+1 k

k+1 k+1 k

(P-A)e

k

k

Moltiplicando ambo i membri per la matrice P otteniamo:

-1

e = (I – P -

-

k+1

k+1 A)e

1

1 k

k

Tale matrice la definiamo matrice M : l’obiettivo è far annullare la matrice per abbattere

l’errore. e = Me

k+1 k

k+1 k

Metodo Iterativo:

Teorema della convergenza dell’errore

Per poter annullare l’errore, faremo riferimento agli autovalori di M.

Qualora l’errore e fosse un autovettore dello spazio definito da M,

k

varrebbe la relazione: Me = λe

k k

k k

Altrimenti l’errore potrebbe essere comunque scritto come combinazione

lineare degli autovettori di M che costituiscono una base dello spazio di M.

Me = c λ v + c λ v + … + c λ v

k 1 1 1 2 2 2 n n n

k 1 1 1 2 2 2 n n n

Possiamo notare come l’abbattimento dell’errore dipenda dal valore degli autovalori

di M. Nell’ipotesi in cui valga il teorema della convergenza tale per cui |λ (M)|< 1 per

j

ogni j, la velocità di convergenza è tanto più rapida, tanto minore è il più grande

raggio spettrale

degli autovalori di M; tale valore prende il nome di

ρ(M) = max {|

j

j

λ (M)|}

j

j

Metodi iterativi

Tra i metodi iterativi vogliamo porre attenzione sui metodi di Jacobi e

Gauss-Seidel.

Jacobi e Gauss-Seidel generano una successione di valori che converge

alla soluzione del sistema: =

=

Metodi iterativi

Partiamo dal sistema lineare Ax=b con P non singolare

A=P-N

A=P-N

Ax=b Px=Nx+b

Ax=b Px=Nx+b

In generale, con un metodo iterativo, abbiamo che:

�+1 � �

−1 −1

� � � �=��

=� +� +� con k ≥ 0

b

Jacobi A=L+D+U

A=L+D+U

P=D

P=D

A= N=-(L+U)=D-A

N=-(L+U)=D-A

con k ≥ 0

Jacobi

−1 −1 − 1

( )=� ( )=�

� �+� �− � �

=−� −�

−1 −1 − 1

�

�

Con matrice diagonale con elementi 1/

�+1 � −1

� � �

=� +�

�+1 � −1

�

�

In forma scalare

Jacobi - Analisi

Il metodo di Jacobi richiede di tenere in memoria almeno due vettori (2n), ma i

calcoli possono essere svolti in parallelo sulle componenti.

Per ogni iterazione il calcolo di ognuna delle n componenti richiede n-1

moltiplicazioni e n-1 somme.

Di conseguenza ricaviamo una complessità computazionale:

2

� (� )

Esempio

Presentiamo un esempio relativo alla risoluzione con metodo iterativo di un

sistema del tipo Ax=b, con matrice A tridiagonale

• Questa matrice presenta autovalori del tipo:

λ (A) = 2 – 2cos().

j

j

• Siamo tuttavia interessati agli autovalori della

matrice : M = (I-P A)

-1

-1

• P matrice di Jacobi : P = diag(A) = 2I

Possiamo quindi calcolare gli autovalori di M, come: λ (M) = 1 – λ (A) = cos().

j j

Dove con j = 1 otteniamo il raggio spettrale, cioè il più grande tra gli autovalori.

Esempio

L’autovettore associato a j = 1 `e una funzione trigonometrica la cui frequenza `e molto

bassa. Tale funzione trigonometrica `e: sin( kπ N + 1 ) k = 1, 2, . . . , N.

Dunque all’autovalore dal valore più alto è associato un autovettore derivato dal

campionamento di un segnale a bassa frequenza

Dato che l’autovalore nell’esempio appena presentato, è associato ad un angolo prossimo a zero, vale la

approssimazione di Taylor: cos() () 2

Questo risultato non deve sorprendere; i metodi iterativi riescono con

buona efficienza ad eliminare componenti in alta frequenza, ma non quelle

in bassa frequenza. Esempio

Nel seguente codice Matlab è stato implementato l’esempio appena descritto per

mostrare

come avviene la convergenza verso la soluzione del sistema lineare attraverso Jacobi:

cos() () 2

Esempio