872 Chapter 19.Partial Differential Equations introduction to the subject here.In particular,we will give two sample multigrid routines,one linear and one nonlinear.By following these prototypes and by perusing the references [1-41,you should be able to develop routines to solve your own problems. There are two related,but distinct,approaches to the use ofmultigrid techniques. The first,termed"the multigrid method,"is a means for speeding up the convergence of a traditional relaxation method,as defined by you on a grid of pre-specified fineness.In this case,you need define your problem(e.g.,evaluate its source terms) only on this grid.Other,coarser,grids defined by the method can be viewed as temporary computational adjuncts. The second approach,termed(perhaps confusingly)"the full multigrid(FMG) method,"requires you to be able to define your problem on grids of various sizes (generally by discretizing the same underlying PDE into different-sized sets of finite- difference equations).In this approach,the method obtains successive solutions on 不 finer and finer grids.You can stop the solution either at a pre-specified fineness,or you can monitor the truncation error due to the discretization,quitting only when it is tolerably small. RECIPESI In this section we will first discuss the"multigrid method,"then use the concepts 器3d 2 developed to introduce the FMG method.The latter algorithm is the one that we implement in the accompanying programs. From One-Grid,through Two-Grid,to Multigrid The key idea of the multigrid method can be understood by considering the simplest case of a two-grid method.Suppose we are trying to solve the linear elliptic problem 6 Cu=f (19.6.1) where C is some linear elliptic operator and f is the source term.Discretize equation (19.6.1)on a uniform grid with mesh size h.Write the resulting set of linear algebraic equations as Chuh fh (19.6.2) 多，aoao Numerica 10.621 43106 Let ih denote some approximate solution to equation(19.6.2).We will use the symbol uh to denote the exact solution to the difference equations(19.6.2).Then the error in uh or the correction is Uh th uh (19.6.3 The residual or defect is dh=Chuh-fh (19.6.4) (Beware:some authors define residual as minus the defect,and there is not universal agreement about which of these two quantities 19.6.4 defines.)Since Ch is linear, the error satisfies ChUh =-dh (19.6.5)872 Chapter 19. Partial Differential Equations 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). introduction to the subject here. In particular, we will give two sample multigrid routines, one linear and one nonlinear. By following these prototypes and by perusing the references [1-4], you should be able to develop routines to solve your own problems. There are two related, but distinct, approaches to the use of multigrid techniques. The first, termed “the multigrid method,” is a means for speeding up the convergence of a traditional relaxation method, as defined by you on a grid of pre-specified fineness. In this case, you need define your problem (e.g., evaluate its source terms) only on this grid. Other, coarser, grids defined by the method can be viewed as temporary computational adjuncts. The second approach, termed (perhaps confusingly) “the full multigrid (FMG) method,” requires you to be able to define your problem on grids of various sizes (generally by discretizing the same underlying PDE into different-sized sets of finite￾difference equations). In this approach, the method obtains successive solutions on finer and finer grids. You can stop the solution either at a pre-specified fineness, or you can monitor the truncation error due to the discretization, quitting only when it is tolerably small. In this section we will first discuss the “multigrid method,” then use the concepts developed to introduce the FMG method. The latter algorithm is the one that we implement in the accompanying programs. From One-Grid, through Two-Grid, to Multigrid The key idea of the multigrid method can be understood by considering the simplest case of a two-grid method. Suppose we are trying to solve the linear elliptic problem Lu = f (19.6.1) where L is some linear elliptic operator and f is the source term. Discretize equation (19.6.1) on a uniform grid with mesh size h. Write the resulting set of linear algebraic equations as Lhuh = fh (19.6.2) Let u
h denote some approximate solution to equation (19.6.2). We will use the symbol uh to denote the exact solution to the difference equations (19.6.2). Then the error in u
h or the correction is vh = uh − u
h (19.6.3) The residual or defect is dh = Lhu
h − fh (19.6.4) (Beware: some authors define residual as minus the defect, and there is not universal agreement about which of these two quantities 19.6.4 defines.) Since Lh is linear, the error satisfies Lhvh = −dh (19.6.5)