19.6 Multigrid Methods for Boundary Value Problems 877 If you are confronted with a new problem and you are not sure what P and R choices are likely to work well,here is a safe rule:Suppose mp is the order of the interpolation P(ie.,it interpolates polynomials of degree mp-1 exactly).Suppose mr is the order of R,and that R is the adjoint of some P(not necessarily the P you intend to use).Then if m is the order of the differential operator Ch,you should satisfy the inequality mp+m>m.For example,bilinear interpolation and its adjoint,full weighting,for Poisson's equation satisfy mp+mr=4>m =2. Of course the p and R operators should enforce the boundary conditions for your problem.The easiest way to do this is to rewrite the difference equation to have homogeneous boundary conditions by modifying the source term if necessary 81 (cf.$19.4).Enforcing homogeneous boundary conditions simply requires the P operator to produce zeros at the appropriate boundary points.The corresponding R is then found by R=Pt Full Multigrid Algorithm So far we have described multigrid as an iterative scheme,where one starts with some initial guess on the finest grid and carries out enough cycles(V-cycles, 9 W-cycles,...)to achieve convergence.This is the simplest way to use multigrid: Simply apply enough cycles until some appropriate convergence criterion is met However,efficiency can be improved by using the Full Multigrid Algorithm(FMG), also known as nested iteration. Instead of starting with an arbitrary approximation on the finest grid (e.g., uh=0),the first approximation is obtained by interpolating from a coarse-grid 、屋多5 solution: uh =PuH (19.6.20) 61 The coarse-grid solution itself is found by a similar FMG process from even coarser grids.At the coarsest level,you start with the exact solution.Rather than proceed as in Figure 19.6.1,then,FMG gets to its solution by a series of increasingly tall "N's," each taller one probing a finer grid(see Figure 19.6.2). Numerica 10621 Note that P in(19.6.20)need not be the same P used in the multigrid cycles. It should be at least of the same order as the discretization Ch,but sometimes a 431 higher-order operator leads to greater efficiency. Recipes It turns out that you usually need one or at most two multigrid cycles at each level before proceeding down to the next finer grid.While there is theoretical (outside 腿 guidance on the required number of cycles(e.g.,[21),you can easily determine it North empirically.Fix the finest level and study the solution values as you increase the number of cycles per level.The asymptotic value of the solution is the exact solution of the difference equations.The difference between this exact solution and the solution for a small number of cycles is the iteration error.Now fix the number of cycles to be large,and vary the number oflevels,i.e.,the smallest value of h used.In this way you can estimate the truncation error for a given h.In your final production code,there is no point in using more cycles than you need to get the iteration error down to the size of the truncation error. The simple multigrid iteration (cycle)needs the right-hand side f only at the finest level.FMG needs f at all levels.If the boundary conditions are homogeneous,19.6 Multigrid Methods for Boundary Value Problems 877 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). If you are confronted with a new problem and you are not sure what P and R choices are likely to work well, here is a safe rule: Suppose mp is the order of the interpolation P (i.e., it interpolates polynomials of degree mp − 1 exactly). Suppose mr is the order of R, and that R is the adjoint of some P (not necessarily the P you intend to use). Then if m is the order of the differential operator Lh, you should satisfy the inequality mp + mr > m. For example, bilinear interpolation and its adjoint, full weighting, for Poisson’s equation satisfy mp + mr = 4 > m = 2. Of course the P and R operators should enforce the boundary conditions for your problem. The easiest way to do this is to rewrite the difference equation to have homogeneous boundary conditions by modifying the source term if necessary (cf. §19.4). Enforcing homogeneous boundary conditions simply requires the P operator to produce zeros at the appropriate boundary points. The corresponding R is then found by R = P†. Full Multigrid Algorithm So far we have described multigrid as an iterative scheme, where one starts with some initial guess on the finest grid and carries out enough cycles (V-cycles, W-cycles,...) to achieve convergence. This is the simplest way to use multigrid: Simply apply enough cycles until some appropriate convergence criterion is met. However, efficiency can be improved by using the Full Multigrid Algorithm (FMG), also known as nested iteration. Instead of starting with an arbitrary approximation on the finest grid (e.g., uh = 0), the first approximation is obtained by interpolating from a coarse-grid solution: uh = PuH (19.6.20) The coarse-grid solution itself is found by a similar FMG process from even coarser grids. At the coarsest level, you start with the exact solution. Rather than proceed as in Figure 19.6.1, then, FMG gets to its solution by a series of increasingly tall “N’s,” each taller one probing a finer grid (see Figure 19.6.2). Note that P in (19.6.20) need not be the same P used in the multigrid cycles. It should be at least of the same order as the discretization Lh, but sometimes a higher-order operator leads to greater efficiency. It turns out that you usually need one or at most two multigrid cycles at each level before proceeding down to the next finer grid. While there is theoretical guidance on the required number of cycles (e.g., [2]), you can easily determine it empirically. Fix the finest level and study the solution values as you increase the number of cycles per level. The asymptotic value of the solution is the exact solution of the difference equations. The difference between this exact solution and the solution for a small number of cycles is the iteration error. Now fix the number of cycles to be large, and vary the number of levels, i.e., the smallest value of h used. In this way you can estimate the truncation error for a given h. In your final production code, there is no point in using more cycles than you need to get the iteration error down to the size of the truncation error. The simple multigrid iteration (cycle) needs the right-hand side f only at the finest level. FMG needs f at all levels. If the boundary conditions are homogeneous