Topic 2: Elliptic Partial Differential Equ ations Lectu re 2-4: Poisson’s Equation: Multigrid Methods Wednesday , Febru ary 3, 2010 Contents 1 Mu ltigrid Methods 2 Multigrid method for Poisson’s equation in 2-D 3 Simple V − cycle algorithm 4 Restricting the Residu al to a Coarser Lattice 1 2 3 5 7 1 MULTIGRID METHODS 5 Prolongation of the Correction to the Finer Lattice 6 Cell-centered and Vertex-centered Grids and Coarsenings 7 Boundary points 8 Restriction and Prolongation Operators 9 Improvements and More Complicated Multigrid Algorithms 8 8 11 11 15 1 Multigrid Methods The multigrid method provides algorithms which can be used to accelerate the rate of convergence of iterative methods, such as Jacobi or Gauss-Seidel, for solving elliptic partial differential equations. Iterative methods start with an approximate guess for the solution to the differential equation. In each iteration, the difference between the approximate solution and the exact solution is made smaller. One can analyze this difference or error into components of different wavelengths, for example by using Fourier analysis. In general the error will have components of many different wavelengths: there will be 2 2 MULTIGRID METHOD FOR POISSON’S EQUATION IN 2-D short wavelength error components and long wavelength error components. Algorithms like Jacobi or Gauss-Seidel are local because the new value for the solution at any lattice site depends only on the value of the previous iterate at neighboring points. Such local algorithms are generally more efficient in reducing short wavelength error components. The basic idea behind multigrid methods is to reduce long wavelength error components by updating blocks of grid points. This s...