Presentazione Multigrid

Formattazione del testo

A=P-NA=P-NA= P=L+DP=L+DN=-UN=-UGauss-SeidelPertanto: �+1 �−1 − 1� � � �=−(�+�) +(�+�)�+1 �−1 − 1Quindi, in termini di componenti, la successione è costruita come segue:Si noti che questa espressione si può scrivere in forma più compatta,come: �+1 �+1 �−1� � � �=− (� +� −�)�+1 �+1 �−1 con k ≥ 0Gauss-Seidel - AnalisiConsiderato il fatto che, per calcolare la componente i-esima del nuovo vettore dellasuccessione si utilizzano le j<i componenti già calcolate, si osserva che un’iterazione delmetodo di Gauss-Seidel equivale a due iterazioni del metodo di Jacobi (che utilizzasoltanto le componenti del vecchio vettore ).Nel metodo di Gauss-Seidel si eseguono meno iterazioni e quindi converge piùvelocemente .Tuttavia, la complessità computazionale non varia ed entrambi i metodihanno una complessità computazionale:2� (� )Jacobi

L'ipotesi converge alla soluzione del problema con una data precisione. L'ipotesi da soddisfare affinché la convergenza sia assicurata è:

Applicando il metodo Multigrid il fattore di convergenza rispetta la legge: < 1 - h•

Applicando il metodo di Gauss-Seidel il fattore di convergenza rispetta la legge: < 1 - h•

I metodi iterativi in generale hanno un fattore di convergenza dipendente dal passo di discretizzazione, portando a una complessità dell'ordine di

I metodi basati su Multigrid hanno un fattore di convergenza indipendente dal passo di discretizzazione, portando a una complessità dell'ordine di

Analisi

Multigrid

• La metodologia Multigrid ha alla base la risoluzione di un problema mediante una trasformazione del problema stesso.
• Dimostreremo come il susseguirsi di tali operazioni porteranno ad una significativa riduzione dell'errore.
• Metodologie Multigrid presentano, a differenza dei metodi iterativi, vantaggiosi tempi di convergenza lineari con la dimensione del problema.

Analisi Multigrid

Gli elementi fondamentali in una metodologia Multigrid sono:

• Griglia: per griglia si intende essenzialmente il numero di variabili che partecipano al problema. In genere viene classificata la griglia per il suo passo di campionamento, che è definito come h = 1/n
• Griglia fine: con questa espressione si intende una griglia relativamente fitta, ossia costituita da un alto numero di variabili.
• Griglia coarse: è una griglia relativamente sfoltita, ossia costituita da un numero di variabili inferiore a quello del problema di partenza.
• Restrizione: la

La restrizione riguarda il passaggio da una griglia fine a una griglia più coarse. Dunque, da una griglia di partenza, si può applicare una restrizione per avere una griglia sfoltita.

• Interpolazione: il duale della restrizione, questa operazione ci consente di passare da una griglia coarse a una griglia fine.
• Problema fine: viene indicato problema fine il problema definito sulla griglia fine.
• Problema coarse: viene indicato con problema coarse il problema definito su griglia coarse.

Analisi Multigrid: Step del metodo

1. Applicazione di un metodo iterativo (Jacobi, Gauss-Seidel) sul problema fine: allo scopo di trovare una certa soluzione con un certo errore ε e un certo residuo ρ.
2. Effettuare il calcolo del residuo applicando un termine di restrizione consente di trasformare la griglia da R'fine (ossia accurata) a 'coarse' (ossia rozza):

Risolvere il seguente sistema:

Analisi Multigrid: Step del metodo

4. Interpolare il termine per trovare

L'effettivo termine correttivo sulla griglia fine, ossia 5. Sommare il termine correttivo a : = + , e successivamente applicare nuovamente un metodo iterativo al problema fine:

Nel processo appena descritto mancano alcune componenti, che sono:

• La matrice interpolante I;
• La matrice restrittiva R;
• La matrice . Analisi Multigrid:

Matrice Interpolante

L'interpolazione ci consente di passare da una griglia coarse a una griglia fine.

Come si evince dalla figura passiamo da una griglia sfitta ad una molto folta: i nuovi punti presi in considerazione stanno a metà tra i punti adiacenti.

Analisi Multigrid: Matrice Interpolante

Data una griglia coarse, definita su più punti v ,v ..v1 2, k1 2, ka partire dagli estremi, si vuole ottenere una griglia fine definita su m punti u ,…u1 m1 m

La matrice I così ottenuta sarà di dimensioni mxk; il prodotto tra il vettore di punti su griglia coarse ed I restituirà il

vettore su griglia fine ricercatoIv = u• v ϵ• u ϵ

Analisi Multigrid:

Matrice Restrittiva

La matrice restrittiva R è l’operatore responsabile per il passaggio da un fine problema definito ad uno definito coarse. Mentre potrebbe essere intuitivo invertire la matrice I per ottenere la matrice R ciò non è possibile : I non è una matrice a rango pieno. La soluzione è infatti da ricercare nella trasposizione, e nella riscalatura della matrice I. La matrice R così ottenuta sarà kxm

Analisi Multigrid:

Matrice

A valle del procedimento di restrizione, la matrice A verrà definita sulla griglia più coarse. Osservazione : vogliamo analizzare qualitativamente la matrice. Si può dimostrare infatti che la matrice più fine post-moltiplicata per un qualsiasi vettore interpolato, dà come risultato un vettore con campioni dispari nulli. Quindi per ottenerne i campioni basta prendere solo i campioni pari, che equivale a R.

Analisi

Possiamo concludere allora che: la costruzione di equazioni corrette per griglie grossolane richiedeinformazioni dalla griglia fine.Tuttavia, non possiamo farlo senza spendere un notevole sforzo computazionale, il chevanificherebbe lo scopo dell’approccio Multigrid, che mira alla rapida convergenzaverso la soluzione.Dobbiamo allora fare i conti con il fatto che le griglie grossolane sono utili per rappresentarefunzioni regolari.

Analisi Multigrid: Errore

Analizziamo come viene manipolato l’errore stesso nel percorrere gli step del Multigrid.Partiamo dalla considerazione che:

e = u -u r =A eh h hh h h

Dal calcolo del residuo,

Possiamo facilmente notare, che a partire dalla restrizione di esso si ottiene la seguente espressione:

A → RA eh hh h

Dall'equazione A E = r, il termine di residuo viene moltiplicato

2h 2h 2h

per l'inverso della matrice A; perveniamo così alla seguente espressione

E RA e-1 = A -1

2h 2h h

2h h

Analisi Multigrid: Errore

E' possibile ricostruire il termine di correzione E tramite interpolazione

dell'espressione precedente: A RA e → IA RA e = -1 -1

-1 -1

2h h 2h h

2h h 2h h

Ehh

Rinominata la matrice IA RA = S, è possibile

esprimere il termine correttivo in relazione all'errore:

E = Sehh

La matrice S gode di una proprietà

S = I(RA I) RA I (RA I) RA = IA RA =

2 -1 -1 -1

2h h h h 2h h

h h h h 2h h

S essa è uguale al suo quadrato

Analisi Multigrid: Errore

E

Nell'ipotesi in cui il vettore errore sia un autovettore per la matrice S, Se = λe.

Vale la relazione Ne consegue quindi la seguente proprietà:

S e = S Se =

λSe = λ e² 22 2SData quindi l’uguaglianza della matrice con il suo quadrato,