19.6 Multigrid Methods for Boundary Value Problems 873 At this point we need to make an approximation to Ch in order to find uh.The classical iteration methods,such as Jacobi or Gauss-Seidel,do this by finding,at each stage,an approximate solution of the equation Chin =-dh (19.6.6) where Ch is a"simpler"operator than Ch.For example,Ch is the diagonal part of Ch for Jacobi iteration,or the lower triangle for Gauss-Seidel iteration.The next approximation is generated by 好w=h+th (19.6.7) 菲 Now consider,as an alternative,a completely different type of approximation ICAL for Ch,one in which we“coarsify”rather than“simplify.”That is,.we form some 3 appropriate approximation Ci of Ch on a coarser grid with mesh size H(we will always take H=2h,but other choices are possible).The residual equation (19.6.5) RECIPES is now approximated by 令 CHUH =-dH (19.6.8) Since C has smaller dimension,this equation will be easier to solve than equation 9」 (19.6.5).To define the defect d on the coarse grid,we need a restriction operator R that restricts dh to the coarse grid: dH Rdh (19.6.9) The restriction operator is also called the fine-to-coarse operator or the injection operator.Once we have a solution n to equation (19.6.8),we need a prolongation operator P that prolongates or interpolates the correction to the fine grid: 三 Uh =PUH (19.6.10) Numerica 10621 431 The prolongation operator is also called the coarse-to-fine operator or the inter- Recipes polation operator.Both R and P are chosen to be linear operators.Finally the approximation un can be updated: 裙ew=h十th (19.6.11) One step of this coarse-grid correction scheme is thus: Coarse-Grid Correction Compute the defect on the fine grid from (19.6.4). .Restrict the defect by (19.6.9). .Solve (19.6.8)exactly on the coarse grid for the correction .Interpolate the correction to the fine grid by (19.6.10).19.6 Multigrid Methods for Boundary Value Problems 873 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). At this point we need to make an approximation to Lh in order to find vh. The classical iteration methods, such as Jacobi or Gauss-Seidel, do this by finding, at each stage, an approximate solution of the equation Lhvh = −dh (19.6.6) where Lh is a “simpler” operator than Lh. For example, Lh is the diagonal part of Lh for Jacobi iteration, or the lower triangle for Gauss-Seidel iteration. The next approximation is generated by u
new h = u
h + vh (19.6.7) Now consider, as an alternative, a completely different type of approximation for Lh, one in which we “coarsify” rather than “simplify.” That is, we form some appropriate approximation LH of Lh on a coarser grid with mesh size H (we will always take H = 2h, but other choices are possible). The residual equation (19.6.5) is now approximated by LH vH = −dH (19.6.8) Since LH has smaller dimension, this equation will be easier to solve than equation (19.6.5). To define the defect dH on the coarse grid, we need a restriction operator R that restricts dh to the coarse grid: dH = Rdh (19.6.9) The restriction operator is also called the fine-to-coarse operator or the injection operator. Once we have a solution v
H to equation (19.6.8), we need a prolongation operator P that prolongates or interpolates the correction to the fine grid: v
h = Pv
H (19.6.10) The prolongation operator is also called the coarse-to-fine operator or the inter￾polation operator. Both R and P are chosen to be linear operators. Finally the approximation u
h can be updated: u
new h = u
h +
vh (19.6.11) One step of this coarse-grid correction scheme is thus: Coarse-Grid Correction • Compute the defect on the fine grid from (19.6.4). • Restrict the defect by (19.6.9). • Solve (19.6.8) exactly on the coarse grid for the correction. • Interpolate the correction to the fine grid by (19.6.10).