19.6 Multigrid Methods for Boundary Value Problems 871 standard tridiagonal algorithm.Given u",one solves(19.5.36)for u+1/2,substitutes on the right-hand side of(19.5.37),and then solves for u+.The key question is how to choose the iteration parameter r,the analog of a choice of timestep for an initial value problem. As usual,the goal is to minimize the spectral radius of the iteration matrix. Although it is beyond our scope to go into details here,it turns out that,for the optimal choice of r,the ADI method has the same rate of convergence as SOR. The individual iteration steps in the ADI method are much more complicated than in SOR,so the ADI method would appear to be inferior.This is in fact true if we choose the same parameter r for every iteration step.However,it is possible to 81 choose a different r for each step.If this is done optimally,then ADI is generally more efficient than SOR.We refer you to the literature [1-4]for details. Our reason for not fully implementing ADI here is that,in most applications, it has been superseded by the multigrid methods described in the next section.Our advice is to use SOR for trivial problems (e.g.,20 x 20),or for solving a larger problem once only,where ease of programming outweighs expense of computer time.Occasionally,the sparse matrix methods of 82.7 are useful for solving a set of difference equations directly.For production solution of large elliptic problems, however,multigrid is now almost always the method of choice. 9 CITED REFERENCES AND FURTHER READING: Hockney,R.W.,and Eastwood,J.W.1981,Computer Simulation Using Particles (New York: McGraw-Hill),Chapter 6. 85总6 Young,D.M.1971,Iterative Solution of Large Linear Systems (New York:Academic Press).[1] Stoer,J.,and Bulirsch,R.1980,Introduction to Numerical Analysis(New York:Springer-Verlag). 558.3-8.6.2] Varga,R.S.1962,Matrix /terative Analysis (Englewood Cliffs,NJ:Prentice-Hall).[3] Spanier,J.1967,in Mathematical Methods for Digital Computers,Volume 2(New York:Wiley). Chapter 11.[4] 19.6 Multigrid Methods for Boundary Value Problems 、之花 61 Numerical 10.621 43108 Recipes Practical multigrid methods were first introduced in the 1970s by Brandt.These (outside methods can solve elliptic PDEs discretized on N grid points in O(N)operations North The "rapid"direct elliptic solvers discussed in $19.4 solve special kinds of elliptic equations in O(N log N)operations.The numerical coefficients in these estimates are such that multigrid methods are comparable to the rapid methods in execution speed.Unlike the rapid methods,however,the multigrid methods can solve general elliptic equations with nonconstant coefficients with hardly any loss in efficiency. Even nonlinear equations can be solved with comparable speed. Unfortunately there is not a single multigrid algorithm that solves all elliptic problems.Rather there is a multigrid technique that provides the framework for solving these problems.You have to adjust the various components of the algorithm within this framework to solve your specific problem.We can only give a brief19.6 Multigrid Methods for Boundary Value Problems 871 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). standard tridiagonal algorithm. Given un, one solves (19.5.36) for un+1/2, substitutes on the right-hand side of (19.5.37), and then solves for u n+1. The key question is how to choose the iteration parameter r, the analog of a choice of timestep for an initial value problem. As usual, the goal is to minimize the spectral radius of the iteration matrix. Although it is beyond our scope to go into details here, it turns out that, for the optimal choice of r, the ADI method has the same rate of convergence as SOR. The individual iteration steps in the ADI method are much more complicated than in SOR, so the ADI method would appear to be inferior. This is in fact true if we choose the same parameter r for every iteration step. However, it is possible to choose a different r for each step. If this is done optimally, then ADI is generally more efficient than SOR. We refer you to the literature [1-4] for details. Our reason for not fully implementing ADI here is that, in most applications, it has been superseded by the multigrid methods described in the next section. Our advice is to use SOR for trivial problems (e.g., 20 × 20), or for solving a larger problem once only, where ease of programming outweighs expense of computer time. Occasionally, the sparse matrix methods of §2.7 are useful for solving a set of difference equations directly. For production solution of large elliptic problems, however, multigrid is now almost always the method of choice. CITED REFERENCES AND FURTHER READING: Hockney, R.W., and Eastwood, J.W. 1981, Computer Simulation Using Particles (New York: McGraw-Hill), Chapter 6. Young, D.M. 1971, Iterative Solution of Large Linear Systems (New York: Academic Press). [1] Stoer, J., and Bulirsch, R. 1980, Introduction to Numerical Analysis (New York: Springer-Verlag), §§8.3–8.6. [2] Varga, R.S. 1962, Matrix Iterative Analysis (Englewood Cliffs, NJ: Prentice-Hall). [3] Spanier, J. 1967, in Mathematical Methods for Digital Computers, Volume 2 (New York: Wiley), Chapter 11. [4] 19.6 Multigrid Methods for Boundary Value Problems Practical multigrid methods were first introduced in the 1970s by Brandt. These methods can solve elliptic PDEs discretized on N grid points in O(N) operations. The “rapid” direct elliptic solvers discussed in §19.4 solve special kinds of elliptic equations in O(N log N) operations. The numerical coefficients in these estimates are such that multigrid methods are comparable to the rapid methods in execution speed. Unlike the rapid methods, however, the multigrid methods can solve general elliptic equations with nonconstant coefficients with hardly any loss in efficiency. Even nonlinear equations can be solved with comparable speed. Unfortunately there is not a single multigrid algorithm that solves all elliptic problems. Rather there is a multigrid technique that provides the framework for solving these problems. You have to adjust the various components of the algorithm within this framework to solve your specific problem. We can only give a brief