Metodo multigriglia (o multigrid)

metodo multigriglia (o multigrid)

Metodo per la risoluzione numerica efficiente di sistemi lineari associati alla discretizzazione di problemi differenziali, sia ordinari che alle derivate parziali. Questo metodo sfrutta la possibilità di discretizzare il medesimo problema differenziale su due o più griglie di finezza diversa. Talvolta le griglie hanno struttura gerarchica, ossia una griglia è ottenuta da un sottoinsieme di nodi di una griglia preesistente più fine. A titolo di esempio, consideriamo il sistema lineare A_ηx_η=f_η associato alla discretizzazione, mediante un metodo agli elementi finiti o alle differenze finite, di un problema differenziale e h denoti l’ampiezza della griglia utilizzata per calcolare la soluzione numerica. Indichiamo con N_η il numero di righe (e colonne) di A_η. Allo scopo di accelerare la convergenza di un metodo iterativo applicato al sistema A_ηx_η=f_ηA_ηx_η=f_η, si può ricorrere a un problema numerico ausiliario, diciamo A_Ηw_Η=g_Η, ottenuto dalla discretizzazione dello stesso problema differenziale, ma su una griglia più rada di ampiezza caratteristica H>>h. La nuova matrice A_Η avrà ;N_Η〈〈N_η righe e colonne. Si effettuano dapprima alcune iterazioni, diciamo k, sulla griglia fine (per es., di Jacobi, di Richardson o del gradiente coniugato) ottenendo una soluzione di tentativo x_η^(κ). Si calcola il residuo associato r_Η^(κ)=f_η−A_ηx_η^(κ) e lo si restringe alla griglia rada, ottenendo r_Η^(κ)=R_η^Ηr_η^(κ), essendo R_η^Η una matrice rettangolare di dimensione N_Η×N_η. A questo punto si risolve il sistema ridotto A_Ηw_Η=r_Η^(κ) e infine si corregge sulla griglia fine il vettore tentativo x_η^(κ), ovvero x_η^(κ+1)=x_η^(κ)+R_η^Ηw_Η. Questa volta R_η^Η è una matrice rettangolare di dimensione N_η×N_Η che estende un vettore della griglia rada a quella fine. In genere R_Η^η è la matrice trasposta di R_η^Η. Il metodo può essere implementato anche su più di due griglie.

→ Computazionali, metodi