Basic Properties of Multigrid Methods

Abstract

Multigrid methods are among the most effective iterative methods for the numerical solution of partial differential equations (PDEs). In the thesis, we consider Poisson's equation as the model problem and present its discretization by the finite difference method. Discretization of PDEs gives typically large algebraic systems of linear equations. Various iterative methods can struggle to find an enough accurate approximation within the allocated time. In particular, relaxation methods such as Jacobi or Gauss-Seidel effectively reduce oscillating parts of the error but are inefficient in reducing smooth error components. Multigrid methods combine relaxation methods with correction on a coarser grid to overcome this deficiency. The problem discretized on a coarser grid is smaller and easier to solve. Typically, a recursive error correction is considered using a hierarchy of grids until the coarsest problem is small enough to get a solution quickly by a direct solver. The purpose of this thesis is to discuss the main principles and thoughts behind the multigrid methods, alongside some practical examples and numerical experiments.

Víceúrovňové metody patří mezi nejefektivnější iterační metody pro numerické ře- šení parciálních diferenciálních rovnic (PDR). V práci uvažujeme jako modelový problém Poissonovu rovnici a její diskretizaci metodou konečných diferencí. Obecně diskretizace PDR vede na velké soustavy lineárních rovnic. Různé iterační metody mohou mít potíže s nalezením dostatečně přesné aproximace v daném čase. Zejména relaxační metody, jako je Jacobi nebo Gauss-Seidel, účinně redukují oscilující části chyby, ale jsou neefektivní v redukci hladkých chybových složek. Multigridní metody kombinují relaxační metody s korekcí na hrubší síti, aby překonaly tento nedostatek. Problém diskretizovaný na hrubší síti je menší a snáze řešitelný. Oprava na hrubší síti se obvykle realizuje rekurzivně pomocí hierarchie sítí, dokud nejhrubší problém není dostatečně malý na to, aby jej bylo možné řešit přímým řešičem. Cílem této práce je diskutovat hlavní principy a myšlenky, které stojí za multigridními metodami, spolu s některými praktickými příklady a numerickými experimenty.