Mètode multigrid
En anàlisi numèrica, un mètode multigrid (amb acrònim anglès mètode MG) és un algorisme per resoldre equacions diferencials utilitzant una jerarquia de discretitzacions. Són un exemple d'una classe de tècniques anomenades mètodes multiresolució, molt útils en problemes que presenten múltiples escales de comportament. Per exemple, molts mètodes bàsics de relaxació presenten diferents taxes de convergència per a components de longitud d'ona curta i llarga, cosa que suggereix que aquestes escales diferents es tracten de manera diferent, com en un enfocament d'anàlisi de Fourier a multigrid.[1] Els mètodes MG es poden utilitzar com a solucionadors i també com a precondicionadors.
La idea principal de la multigrid és accelerar la convergència d'un mètode iteratiu bàsic (conegut com a relaxació, que generalment redueix l'error de longitud d'ona curta) mitjançant una correcció global de l'aproximació de la solució de la graella fina de tant en tant, aconseguida resolent un problema gruixut. El problema gruixut, tot i que és més barat de resoldre, és similar al problema de la graella fina, ja que també té errors de longitud d'ona curta i llarga. També es pot resoldre mitjançant una combinació de relaxació i atractiu a quadrícules encara més gruixudes. Aquest procés recursiu es repeteix fins que s'arriba a una graella on el cost de la solució directa és insignificant en comparació amb el cost d'un escombrat de relaxació de graella fina. Aquest cicle multigrid normalment redueix tots els components d'error en una quantitat fixa limitada molt per sota d'un, independentment de la mida de la malla de la graella fina. L'aplicació típica de multigrid és la solució numèrica d'equacions diferencials parcials el·líptiques en dues o més dimensions.[2]
Els mètodes multigrid es poden aplicar en combinació amb qualsevol de les tècniques de discretització habituals. Per exemple, el mètode d'elements finits es pot refondre com un mètode multigrid.[3] En aquests casos, els mètodes multigrid es troben entre les tècniques de solució més ràpides que es coneixen actualment. A diferència d'altres mètodes, els mètodes multigrid són generals perquè poden tractar regions i condicions de límit arbitràries. No depenen de la separabilitat de les equacions o d'altres propietats especials de l'equació. També s'han utilitzat àmpliament per a sistemes d'equacions no simètrics i no lineals més complicats, com les equacions d'elasticitat de Lamé o les equacions de Navier-Stokes.[4]
Hi ha moltes variacions d'algorismes multigrid, però les característiques comunes són que es considera una jerarquia de discretitzacions (grids). Els passos importants són: [5][6]
- Suavització: reducció d'errors d'alta freqüència, per exemple utilitzant algunes iteracions del mètode Gauss-Seidel.
- Càlcul residual: calcula l'error residual després de les operacions de suavització.
- Restricció: mostreig inferior a l'error residual a una graella més gruixuda.
- Interpolació o prolongació: interpolació d'una correcció calculada en una graella més gruixuda en una graella més fina.
- Correcció: afegir una solució de graella més gruixuda prolongada a la graella més fina.
Referències modifica
- ↑ Roman Wienands. Practical Fourier analysis for multigrid methods (en anglès). CRC Press, 2005, p. 17. ISBN 978-1-58488-492-7.
- ↑ U. Trottenberg. Multigrid (en anglès). Academic Press, 2001. ISBN 978-0-12-701070-0.
- ↑ Yu Zhu. Multigrid finite element methods for electromagnetic field modeling (en anglès). Wiley, 2006, p. 132 ff. ISBN 978-0-471-74110-7.
- ↑ Analysis of the multigrid method (tesi) (en anglès).
- ↑ M. T. Heath. «Section 11.5.7 Multigrid Methods». A: Scientific Computing: An Introductory Survey (en anglès). McGraw-Hill Higher Education, 2002, p. 478 ff. ISBN 978-0-07-112229-0.
- ↑ P. Wesseling. An Introduction to Multigrid Methods (en anglès). Wiley, 1992. ISBN 978-0-471-93083-9.