c19-6 (779621)
Текст из файла
19.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.872Chapter 19.Partial Differential EquationsFrom One-Grid, through Two-Grid, to MultigridThe key idea of the multigrid method can be understood by considering thesimplest case of a two-grid method. Suppose we are trying to solve the linearelliptic problemLu = 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 linearalgebraic equations asLh uh = fh(19.6.2)Let ueh denote some approximate solution to equation (19.6.2). We will use thesymbol uh to denote the exact solution to the difference equations (19.6.2). Thenthe error in ueh or the correction isvh = uh − ueh(19.6.3)dh = Lh ueh − fh(19.6.4)The residual or defect is(Beware: some authors define residual as minus the defect, and there is not universalagreement about which of these two quantities 19.6.4 defines.) Since Lh is linear,the error satisfiesLh vh = −dh(19.6.5)Sample 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).introduction to the subject here. In particular, we will give two sample multigridroutines, one linear and one nonlinear. By following these prototypes and byperusing the references [1-4] , you should be able to develop routines to solve yourown 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 convergenceof a traditional relaxation method, as defined by you on a grid of pre-specifiedfineness. 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 astemporary 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 finitedifference equations). In this approach, the method obtains successive solutions onfiner and finer grids. You can stop the solution either at a pre-specified fineness, oryou can monitor the truncation error due to the discretization, quitting only whenit is tolerably small.In this section we will first discuss the “multigrid method,” then use the conceptsdeveloped to introduce the FMG method.
The latter algorithm is the one that weimplement in the accompanying programs.19.6 Multigrid Methods for Boundary Value Problems873At this point we need to make an approximation to Lh in order to find vh . Theclassical iteration methods, such as Jacobi or Gauss-Seidel, do this by finding, ateach stage, an approximate solution of the equationLbh vbh = −dh(19.6.6)=ueh + bvhuenewh(19.6.7)Now consider, as an alternative, a completely different type of approximationfor Lh , one in which we “coarsify” rather than “simplify.” That is, we form someappropriate approximation LH of Lh on a coarser grid with mesh size H (we willalways take H = 2h, but other choices are possible). The residual equation (19.6.5)is now approximated byLH 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 operatorR 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 injectionoperator.
Once we have a solution veH to equation (19.6.8), we need a prolongationoperator P that prolongates or interpolates the correction to the fine grid:vh = P veHe(19.6.10)The prolongation operator is also called the coarse-to-fine operator or the interpolation operator. Both R and P are chosen to be linear operators. Finally theapproximation ueh can be updated:uenew=ueh + evhhOne 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.11)Sample 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).where Lbh is a “simpler” operator than Lh . For example, Lbh is the diagonal part ofLh for Jacobi iteration, or the lower triangle for Gauss-Seidel iteration. The nextapproximation is generated by874Chapter 19.Partial Differential EquationsSmoothing, Restriction, and Prolongation OperatorsThe most popular smoothing method, and the one you should try first, isGauss-Seidel, since it usually leads to a good convergence rate.
If we order the meshpoints from 1 to N , then the Gauss-Seidel scheme isN 1XLij uj − fiui = −Liij=1j6=ii = 1, . . . , N(19.6.12)Sample 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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
