c19-5 (779620), страница 3
Текст из файла (страница 3)
To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).∂u= ∇2 u − ρ∂t19.6 Multigrid Methods for Boundary Value Problems871CITED 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 ValueProblemsPractical multigrid methods were first introduced in the 1970s by Brandt.
Thesemethods 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 ellipticequations in O(N log N ) operations. The numerical coefficients in these estimatesare such that multigrid methods are comparable to the rapid methods in executionspeed. Unlike the rapid methods, however, the multigrid methods can solve generalelliptic 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 ellipticproblems.
Rather there is a multigrid technique that provides the framework forsolving these problems. You have to adjust the various components of the algorithmwithin this framework to solve your specific problem. We can only give a briefSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).standard tridiagonal algorithm.
Given un , one solves (19.5.36) for un+1/2 , substituteson the right-hand side of (19.5.37), and then solves for un+1 . The key questionis how to choose the iteration parameter r, the analog of a choice of timestep foran 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 theoptimal 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 thanin SOR, so the ADI method would appear to be inferior. This is in fact true if wechoose the same parameter r for every iteration step. However, it is possible tochoose a different r for each step. If this is done optimally, then ADI is generallymore 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.
Ouradvice is to use SOR for trivial problems (e.g., 20 × 20), or for solving a largerproblem once only, where ease of programming outweighs expense of computertime. Occasionally, the sparse matrix methods of §2.7 are useful for solving a setof difference equations directly. For production solution of large elliptic problems,however, multigrid is now almost always the method of choice..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
