Universitatea “Ovidius” din Constanta

Facultatea de Matematica si Informatica

Studii masterat: Modelare si tehnologii informatice

Disciplina: Tehnici de programare pentru calcule stiintifice

Proiect de curs

Multigrid

2012

I. Descrierea problemei

Acest proiect isi propune sa studieze introducerea in metode de tip multigrid. Metodele de tip multigrid au fost dezvoltate pentru a rezolva eficient sisteme liniare. Metoda multigrid se bazeaza pe faptul ca exista metode iterative care poseda proprietatea de netezire: metode care descresc rapid componentele oscilatorii mari ale erorii.

Se poate proiecta eroarea solutiei pe o grila mai rara si se poate rezolva o versiune mai rara pentru ecuatia erorii. Prin aplicarea metodei 2-grid de mai multe ori se obţine metoda multigrid. Sistemul liniar generat in acest studiu este generat folosind metode de tip diferente finite pentru aproximarea derivatelor de ordin 1 sau 2.

II. Problema

Se da problema:

cu α = 3, β = 0.25, p = 0, q = 0, avand solutia exacta data de:

Pentru solutia exacta enuntata mai sus se va calcula termenul liber corespunzator.

Discretizarea si numarul aferent de puncte pe un iterval, va tine cont de urmatoarea formula:

unde A si B reprezinta capetele intervalului iar N numarul de puncte din discretizare.

Se va aplica o dubla derivare pentru afisarea termenului liber, iar pasii anteriori vor fi ilustrati in urmatoarea imagine:

Matricea obtinuta in urma discretizarii, pentru grila fina ese data de:

Se formeaza grila rara prin racirea punctelor de pe grila fina din 2 in 2.

Numarul de puncte interioare pe grila va fi de .

Matricea obtinuta pentru grila rara este :

Trecerea de la nivelul fin la nivelul rar se face prin operatorul (restrictie)

iar invers prin operatorul (interpolare) .

Forma acestui operator este data de :

unde:

Codul sursa matlab:

III Algoritmul 2, 3 si 4 grid

Folosindu-ne de punctele anterioare implementam algoritmul 2-grid.

Algoritmul 3-grid

Algoritmul 4-grid

IV Metodele Gauss-Seidel si Richardson

Metoda Gauss-Seidel a fost implementata dupa formula:

avand urmatorul cod implementat in matlab:

unde, A reprezinta matricea, b este termenul liber, x0 initial, steps reprezinta numarul de iteratii iar omega este parametrul de relaxare.

Metoda Richardson implementata dupa formula:

avand urmatorul cod implementat in matlab:

unde B reprezinta valoarea parantezei din formula iar x rezultatul final.

V Rezultate si concluzii

Tabela 2-grid + grafic

Tabela 3-grid + grafic

Tabela 4-grid + grafic

Concluzie:

Se observa ca metoda Gauss - Seidel este mai eficienta decat metoda Richardson deoarece punctele sunt mai apropiate de graficul functiei exacte.