c16-7 (779599)
Текст из файла
16.7 Multistep, Multivalue, and Predictor-Corrector Methods747free_vector(ysav,1,nv);free_vector(yerr,1,nv);free_vector(x,1,KMAXX);free_vector(err,1,KMAXX);free_matrix(dfdy,1,nv,1,nv);free_vector(dfdx,1,nv);free_matrix(d,1,nv,1,KMAXX);The routine stifbs is an excellent routine for all stiff problems, competitive withthe best Gear-type routines. stiff is comparable in execution time for moderate N and−4−8<∼ 10 . By the time ∼ 10 , stifbs is roughly an order of magnitude faster. Thereare further improvements that could be applied to stifbs to make it even more robust. Forexample, very occasionally ludcmp in simpr will encounter a singular matrix.
You couldarrange for the stepsize to be reduced, say by a factor of the current nseq[k]. There arealso certain stability restrictions on the stepsize that come into play on some problems. Fora discussion of how to implement these automatically, see [6].CITED REFERENCES AND FURTHER READING:Gear, C.W. 1971, Numerical Initial Value Problems in Ordinary Differential Equations (EnglewoodCliffs, NJ: Prentice-Hall).
[1]Kaps, P., and Rentrop, P. 1979, Numerische Mathematik, vol. 33, pp. 55–68. [2]Shampine, L.F. 1982, ACM Transactions on Mathematical Software, vol. 8, pp. 93–113. [3]Enright, W.H., and Pryce, J.D. 1987, ACM Transactions on Mathematical Software, vol. 13,pp. 1–27. [4]Bader, G., and Deuflhard, P. 1983, Numerische Mathematik, vol. 41, pp. 373–398.
[5]Deuflhard, P. 1983, Numerische Mathematik, vol. 41, pp. 399–422.Deuflhard, P. 1985, SIAM Review, vol. 27, pp. 505–535.Deuflhard, P. 1987, “Uniqueness Theorems for Stiff ODE Initial Value Problems,” Preprint SC87-3 (Berlin: Konrad Zuse Zentrum für Informationstechnik). [6]Enright, W.H., Hull, T.E., and Lindberg, B. 1975, BIT, vol. 15, pp. 10–48.Wanner, G. 1988, in Numerical Analysis 1987, Pitman Research Notes in Mathematics, vol. 170,D.F. Griffiths and G.A.
Watson, eds. (Harlow, Essex, U.K.: Longman Scientific and Technical).Stoer, J., and Bulirsch, R. 1980, Introduction to Numerical Analysis (New York: Springer-Verlag).16.7 Multistep, Multivalue, andPredictor-Corrector MethodsThe terms multistep and multivalue describe two different ways of implementingessentially the same integration technique for ODEs. Predictor-corrector is a particular subcategrory of these methods — in fact, the most widely used.
Accordingly,the name predictor-corrector is often loosely used to denote all these methods.We suspect that predictor-corrector integrators have had their day, and that theyare no longer the method of choice for most problems in ODEs. For high-precisionapplications, or applications where evaluations of the right-hand sides are expensive,Bulirsch-Stoer dominates. For convenience, or for low precision, adaptive-stepsizeRunge-Kutta dominates. Predictor-corrector methods have been, we think, squeezedSample 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).}748Chapter 16.Integration of Ordinary Differential EquationsxnIn a single-step method like Runge-Kutta or Bulirsch-Stoer, the value yn+1 at xn+1depends only on yn .
In a multistep method, we approximate f(x, y) by a polynomialpassing through several previous points xn , xn−1 , . . . and possibly also throughxn+1 . The result of evaluating the integral (16.7.1) at x = xn+1 is then of the form000yn+1 = yn + h(β0 yn+1+ β1 yn0 + β2 yn−1+ β3 yn−2+ · · ·)(16.7.2)where yn0 denotes f(xn , yn ), and so on. If β0 = 0, the method is explicit; otherwiseit is implicit. The order of the method depends on how many previous steps weuse to get each new value of y.Consider how we might solve an implicit formula of the form (16.7.2) for yn+1 .Two methods suggest themselves: functional iteration and Newton’s method.
Infunctional iteration, we take some initial guess for yn+1 , insert it into the right-handside of (16.7.2) to get an updated value of yn+1 , insert this updated value back intothe right-hand side, and continue iterating. But how are we to get an initial guess foryn+1 ? Easy! Just use some explicit formula of the same form as (16.7.2).
This iscalled the predictor step. In the predictor step we are essentially extrapolating thepolynomial fit to the derivative from the previous points to the new point xn+1 andthen doing the integral (16.7.1) in a Simpson-like manner from xn to xn+1 . Thesubsequent Simpson-like integration, using the prediction step’s value of yn+1 tointerpolate the derivative, is called the corrector step. The difference between thepredicted and corrected function values supplies information on the local truncationerror that can be used to control accuracy and to adjust stepsize.If one corrector step is good, aren’t many better? Why not use each correctoras an improved predictor and iterate to convergence on each step? Answer: Even ifyou had a perfect predictor, the step would still be accurate only to the finite orderof the corrector.
This incurable error term is on the same order as that which youriteration is supposed to cure, so you are at best changing only the coefficient in frontSample 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).out in the middle. There is possibly only one exceptional case: high-precisionsolution of very smooth equations with very complicated right-hand sides, as wewill describe later.Nevertheless, these methods have had a long historical run. Textbooks arefull of information on them, and there are a lot of standard ODE programs aroundthat are based on predictor-corrector methods.
Many capable researchers have alot of experience with predictor-corrector routines, and they see no reason to makea precipitous change of habit. It is not a bad idea for you to be familiar with theprinciples involved, and even with the sorts of bookkeeping details that are the baneof these methods. Otherwise there will be a big surprise in store when you first haveto fix a problem in a predictor-corrector routine.Let us first consider the multistep approach.
Think about how integrating anODE is different from finding the integral of a function: For a function, the integrandhas a known dependence on the independent variable x, and can be evaluated atwill. For an ODE, the “integrand” is the right-hand side, which depends both onx and on the dependent variables y. Thus to advance the solution of y0 = f(x, y)from xn to x, we haveZ xf(x0 , y) dx0(16.7.1)y(x) = yn +16.7 Multistep, Multivalue, and Predictor-Corrector Methods749predictor:yn+1 = yn +h00(23yn0 − 16yn−1+ 5yn−2) + O(h4 )12(16.7.3)Here information at the current point xn , together with the two previous points xn−1and xn−2 (assumed equally spaced), is used to predict the value yn+1 at the nextpoint, xn+1 .
The Adams-Moulton part is the corrector. The third-order case iscorrector:yn+1 = yn +h0(5y0+ 8yn0 − yn−1) + O(h4 )12 n+1(16.7.4)Without the trial value of yn+1 from the predictor step to insert on the right-handside, the corrector would be a nasty implicit equation for yn+1 .There are actually three separate processes occurring in a predictor-corrector0method: the predictor step, which we call P, the evaluation of the derivative yn+1from the latest value of y, which we call E, and the corrector step, which we callC.
In this notation, iterating m times with the corrector (a practice we inveighedagainst earlier) would be written P(EC)m . One also has the choice of finishing witha C or an E step. The lore is that a final E is superior, so the strategy usuallyrecommended is PECE.Notice that a PC method with a fixed number of iterations (say, one) is anexplicit method! When we fix the number of iterations in advance, then the finalvalue of yn+1 can be written as some complicated function of known quantities. Thusfixed iteration PC methods lose the strong stability properties of implicit methodsand should only be used for nonstiff problems.For stiff problems we must use an implicit method if we want to avoid havingtiny stepsizes.
(Not all implicit methods are good for stiff problems, but fortunatelysome good ones such as the Gear formulas are known.) We then appear to have twochoices for solving the implicit equations: functional iteration to convergence, orNewton iteration.
However, it turns out that for stiff problems functional iterationwill not even converge unless we use tiny stepsizes, no matter how close ourprediction is! Thus Newton iteration is usually an essential part of a multistepstiff solver. For convergence, Newton’s method doesn’t particularly care what thestepsize is, as long as the prediction is accurate enough.Multistep methods, as we have described them so far, suffer from two seriousdifficulties when one tries to implement them:• Since the formulas require results from equally spaced steps, adjustingthe stepsize is difficult.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).of the error term by a fractional amount. So dubious an improvement is certainly notworth the effort. Your extra effort would be better spent in taking a smaller stepsize.As described so far, you might think it desirable or necessary to predict severalintervals ahead at each step, then to use all these intervals, with various weights, ina Simpson-like corrector step. That is not a good idea.
Extrapolation is the leaststable part of the procedure, and it is desirable to minimize its effect. Therefore, theintegration steps of a predictor-corrector method are overlapping, each one involvingseveral stepsize intervals h, but extending just one such interval farther than theprevious ones. Only that one extended interval is extrapolated by each predictor step.The most popular predictor-corrector methods are probably the AdamsBashforth-Moulton schemes, which have good stability properties. The AdamsBashforth part is the predictor. For example, the third-order case is750Chapter 16.Integration of Ordinary Differential EquationsFor multivalue methods the basic data available to the integrator are the firstfew terms of the Taylor series expansion of the solution at the current point xn .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
