168 Chapter 5.Evaluation of Functions wksp[j+1]=0.5*(wksp[j]+tmp); tmp=dum; wksp [nterm+1]=0.5*(wksp [nterm]+tmp); if (fabs(wksp[nterm+1])<=fabs(wksp[nterm])) Favorable to increase p, *sum +(0.5*wksp[++nterm]); and the table becomes longer. else Favorable to increase n, *sum +wksp[nterm+1]; the table doesn't become longer The powerful Euler technique is not directly applicable to a series of positive terms.Occasionally it is useful to converta series of positive terms into an alternating series,just so that the Euler transformation can be used!Van Wijngaarden has given a transformation for accomplishing this [1]: -1)r-1w (5.1.7 3 where RECIPES wr三Ur+22x+4U4r+8U8r+··· (5.1.8) 2 Equations(5.1.7)and(5.1.8)replace a simple sum by a two-dimensional sum,each term in(5.1.7)being itself an infinite sum(5.1.8).This may seem a strange way to 3 Press. ART save on work!Since,however,the indices in(5.1.8)increase tremendously rapidly, as powers of 2,it often requires only a few terms to converge(5.1.8)to extraordinary Progra accuracy.You do,however,need to be able to compute the v,'s efficiently for “random”values r.The standard“updating”tricks for sequential r's,mentioned OF SCIENTIFIC( above following equation(5.1.1),can't be used. Actually,Euler's transformation is a special case of a more general transforma- 6 tion of power series.Suppose that some known function g(z)has the series ga)=∑6n2n (5.1.9) 1920 COMPUTING (ISBN n=0 and that you want to sum the new,unknown,series Numerical 10521 Recipes 43108 (5.1.10) (outside Then it is not hard to show(see [2))that equation(5.1.10)can be written as North Software. fe)=∑ae90 n! (5.1.11) n=0 which often converges much more rapidly.Here A(m)co is the nth finite-difference operator (equation 5.1.6),with A(0)coco,and g(m)is the nth derivative of g(z) The usual Euler transformation (equation 5.1.5 with n=0)can be obtained,for example,by substituting g(2)=1+z 1 =1-z+z2-z3+… (5.1.12)168 Chapter 5. Evaluation of Functions 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). wksp[j+1]=0.5*(wksp[j]+tmp); tmp=dum; } wksp[nterm+1]=0.5*(wksp[nterm]+tmp); if (fabs(wksp[nterm+1]) <= fabs(wksp[nterm])) Favorable to increase p, *sum += (0.5*wksp[++nterm]); and the table becomes longer. else Favorable to increase n, *sum += wksp[nterm+1]; the table doesn’t become longer. } } The powerful Euler technique is not directly applicable to a series of positive terms. Occasionally it is useful to convert a series of positive terms into an alternating series, just so that the Euler transformation can be used! Van Wijngaarden has given a transformation for accomplishing this [1]:
∞ r=1 vr =
∞ r=1 (−1)r−1wr (5.1.7) where wr ≡ vr + 2v2r + 4v4r + 8v8r + ··· (5.1.8) Equations (5.1.7) and (5.1.8) replace a simple sum by a two-dimensional sum, each term in (5.1.7) being itself an infinite sum (5.1.8). This may seem a strange way to save on work! Since, however, the indices in (5.1.8) increase tremendously rapidly, as powers of 2, it often requires only a few terms to converge (5.1.8) to extraordinary accuracy. You do, however, need to be able to compute the v r’s efficiently for “random” values r. The standard “updating” tricks for sequential r’s, mentioned above following equation (5.1.1), can’t be used. Actually, Euler’s transformation is a special case of a more general transforma￾tion of power series. Suppose that some known function g(z) has the series g(z) =
∞ n=0 bnzn (5.1.9) and that you want to sum the new, unknown, series f(z) =
∞ n=0 cnbnzn (5.1.10) Then it is not hard to show (see [2]) that equation (5.1.10) can be written as f(z) =
∞ n=0 [∆(n) c0] g(n) n! zn (5.1.11) which often converges much more rapidly. Here ∆(n)c0 is the nth finite-difference operator (equation 5.1.6), with ∆(0)c0 ≡ c0, and g(n) is the nth derivative of g(z). The usual Euler transformation (equation 5.1.5 with n = 0) can be obtained, for example, by substituting g(z) = 1 1 + z = 1 − z + z2 − z3 + ··· (5.1.12)