c5-5 (779489)
Текст из файла
178Chapter 5.Evaluation of FunctionsThen the answer is√0 w=0dw+iw=6 0, c ≥ 02wc + id =w 6= 0, c < 0, d ≥ 0(5.4.7)w 6= 0, c < 0, d < 0Routines implementing these algorithms are listed in Appendix C.CITED REFERENCES AND FURTHER READING:Midy, P., and Yakovlev, Y. 1991, Mathematics and Computers in Simulation, vol. 33, pp. 33–49.Knuth, D.E. 1981, Seminumerical Algorithms, 2nd ed., vol. 2 of The Art of Computer Programming(Reading, MA: Addison-Wesley) [see solutions to exercises 4.2.1.16 and 4.6.4.41].5.5 Recurrence Relations and Clenshaw’sRecurrence FormulaMany useful functions satisfy recurrence relations, e.g.,(n + 1)Pn+1 (x) = (2n + 1)xPn (x) − nPn−1 (x)Jn+1 (x) =2nJn (x) − Jn−1 (x)x(5.5.1)(5.5.2)nEn+1 (x) = e−x − xEn (x)(5.5.3)cos nθ = 2 cos θ cos(n − 1)θ − cos(n − 2)θ(5.5.4)sin nθ = 2 cos θ sin(n − 1)θ − sin(n − 2)θ(5.5.5)where the first three functions are Legendre polynomials, Bessel functions of the firstkind, and exponential integrals, respectively.
(For notation see [1].) These relationsare useful for extending computational methods from two successive values of n toother values, either larger or smaller.Equations (5.5.4) and (5.5.5) motivate us to say a few words about trigonometricfunctions. If your program’s running time is dominated by evaluating trigonometricfunctions, you are probably doing something wrong. Trig functions whose argumentsform a linear sequence θ = θ0 + nδ, n = 0, 1, 2, .
. ., are efficiently calculated bythe following recurrence,cos(θ + δ) = cos θ − [α cos θ + β sin θ]sin(θ + δ) = sin θ − [α sin θ − β cos θ](5.5.6)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).|d|+ iw 2w |d| − iw2w5.5 Recurrence Relations and Clenshaw’s Recurrence Formulawhere α and β are the precomputed coefficients δβ ≡ sin δα ≡ 2 sin22179(5.5.7)t ≡ tan θ2cos θ =1 − t21 + t2sin θ =2t1 + t2(5.5.8)The cost of getting both sin and cos, if you need them, is thus the cost of tan plus2 multiplies, 2 divides, and 2 adds.
On machines with slow trig functions, this canbe a savings. However, note that special treatment is required if θ → ±π. And alsonote that many modern machines have very fast trig functions; so you should notassume that equation (5.5.8) is faster without testing.Stability of RecurrencesYou need to be aware that recurrence relations are not necessarily stableagainst roundoff error in the direction that you propose to go (either increasing n ordecreasing n).
A three-term linear recurrence relationyn+1 + an yn + bn yn−1 = 0,n = 1, 2, . . .(5.5.9)has two linearly independent solutions, fn and gn say. Only one of these correspondsto the sequence of functions fn that you are trying to generate.
The other one gnmay be exponentially growing in the direction that you want to go, or exponentiallydamped, or exponentially neutral (growing or dying as some power law, for example).If it is exponentially growing, then the recurrence relation is of little or no practicaluse in that direction. This is the case, e.g., for (5.5.2) in the direction of increasingn, when x < n. You cannot generate Bessel functions of high n by forwardrecurrence on (5.5.2).To state things a bit more formally, iffn /gn → 0asn→∞(5.5.10)then fn is called the minimal solution of the recurrence relation (5.5.9).
Nonminimalsolutions like gn are called dominant solutions. The minimal solution is unique, if itexists, but dominant solutions are not — you can add an arbitrary multiple of fn toa given gn . You can evaluate any dominant solution by forward recurrence, but notthe minimal solution. (Unfortunately it is sometimes the one you want.)Abramowitz and Stegun (in their Introduction) [1] give a list of recurrences thatare stable in the increasing or decreasing directions. That list does not contain allSample 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).The reason for doing things this way, rather than with the standard (and equivalent)identities for sums of angles, is that here α and β do not lose significance if theincremental δ is small. Likewise, the adds in equation (5.5.6) should be done inthe order indicated by square brackets. We will use (5.5.6) repeatedly in Chapter12, when we deal with Fourier transforms.Another trick, occasionally useful, is to note that both sin θ and cos θ can becalculated via a single call to tan:180Chapter 5.Evaluation of Functionsyn+1 − 2γyn + yn−1 = 0(5.5.11)where γ ≡ n/x is treated as a constant.
You solve such recurrence relationsby trying solutions of the form yn = an . Substituting into the above recurrence givespora = γ ± γ2 − 1(5.5.12)a2 − 2γa + 1 = 0The recurrence is stable if |a| ≤ 1 for all solutions a. This holds (as you can verify)if |γ| ≤ 1 or n ≤ x. The recurrence (5.5.2) thus cannot be used, starting with J0 (x)and J1 (x), to compute Jn (x) for large n.Possibly you would at this point like the security of some real theorems onthis subject (although we ourselves always follow one of the heuristic procedures).Here are two theorems, due to Perron [2]:Theorem A. If in (5.5.9) an ∼ anα , bn ∼ bnβ as n → ∞, and β < 2α, thengn+1 /gn ∼ −anα ,fn+1 /fn ∼ −(b/a)nβ−α(5.5.13)and fn is the minimal solution to (5.5.9).Theorem B.
Under the same conditions as Theorem A, but with β = 2α,consider the characteristic polynomialt2 + at + b = 0(5.5.14)If the roots t1 and t2 of (5.5.14) have distinct moduli, |t1 | > |t2 | say, thengn+1 /gn ∼ t1 nα ,fn+1 /fn ∼ t2 nα(5.5.15)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).possible formulas, of course. Given a recurrence relation for some function fn (x)you can test it yourself with about five minutes of (human) labor: For a fixed xin your range of interest, start the recurrence not with true values of fj (x) andfj+1 (x), but (first) with the values 1 and 0, respectively, and then (second) with0 and 1, respectively.
Generate 10 or 20 terms of the recursive sequences in thedirection that you want to go (increasing or decreasing from j), for each of the twostarting conditions. Look at the difference between the corresponding members ofthe two sequences. If the differences stay of order unity (absolute value less than10, say), then the recurrence is stable. If they increase slowly, then the recurrencemay be mildly unstable but quite tolerably so. If they increase catastrophically,then there is an exponentially growing solution of the recurrence. If you knowthat the function that you want actually corresponds to the growing solution, thenyou can keep the recurrence formula anyway e.g., the case of the Bessel functionYn (x) for increasing n, see §6.5; if you don’t know which solution your functioncorresponds to, you must at this point reject the recurrence formula.
Notice thatyou can do this test before you go to the trouble of finding a numerical method forcomputing the two starting functions fj (x) and fj+1 (x): stability is a property ofthe recurrence, not of the starting values.An alternative heuristic procedure for testing stability is to replace the recurrence relation by a similar one that is linear with constant coefficients.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
