19.4 Fourier and Cyclic Reduction Methods 857 For example,a combined advective-diffusion equation,such as Ou oi=-v 02u +D (19.3.21) Ox 0x2 might profitably use an explicit scheme for the advective term combined with a Crank-Nicolson or other implicit scheme for the diffusion term. The alternating-direction implicit (ADI)method,equation(19.3.16),is an example of operator splitting with a slightly different twist.Let us reinterpret (19.3.19)to have a different meaning:Let i now denote an updating method that 8 includes algebraically all the pieces of the total operator C,but which is desirably stable only for the Ci piece;likewise U2,...Um.Then a method of getting from un to un+1 is B un+1/m=h(u”,△t/m) ICAL un+2/m =U(un+1/m,At/m) (19.3.22) un+1=Um(un+(m-1)/m,At/m) 8 9 The timestep for each fractional step in(19.3.22)is now only 1/m ofthe full timestep, because each partial operation acts with all the terms of the original operator. Equation(19.3.22)is usually,though not always,stable as a differencing scheme 》 9 for the operator C.In fact,as a rule of thumb,it is often sufficient to have stable i's only for the operator pieces having the highest number of spatial derivatives-the other i's can be unstable-to make the overall scheme stable! 6 It is at this point that we turn our attention from initial value problems to boundary value problems.These will occupy us for the remainder of the chapter. CITED REFERENCES AND FURTHER READING: Ames,W.F.1977,Numerical Methods for Partial Differential Equations,2nd ed.(New York: Academic Press). 3四三a Numerica 10.621 4312 (outside Recipes 19.4 Fourier and Cyclic Reduction Methods for North Boundary Value Problems As discussed in $19.0,most boundary value problems(elliptic equations,for example)reduce to solving large sparse linear systems of the form A·u=b (19.4.1) either once,for boundary value equations that are linear,or iteratively,for boundary value equations that are nonlinear.19.4 Fourier and Cyclic Reduction Methods 857 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). For example, a combined advective-diffusion equation, such as ∂u ∂t = −v ∂u ∂x + D ∂2u ∂x2 (19.3.21) might profitably use an explicit scheme for the advective term combined with a Crank-Nicolson or other implicit scheme for the diffusion term. The alternating-direction implicit (ADI) method, equation (19.3.16), is an example of operator splitting with a slightly different twist. Let us reinterpret (19.3.19) to have a different meaning: Let U1 now denote an updating method that includes algebraically all the pieces of the total operator L, but which is desirably stable only for the L1 piece; likewise U2,... Um. Then a method of getting from un to un+1 is un+1/m = U1(un, ∆t/m) un+2/m = U2(un+1/m, ∆t/m) ··· un+1 = Um(un+(m−1)/m, ∆t/m) (19.3.22) The timestep for each fractional step in (19.3.22) is now only 1/m of the full timestep, because each partial operation acts with all the terms of the original operator. Equation (19.3.22) is usually, though not always, stable as a differencing scheme for the operator L. In fact, as a rule of thumb, it is often sufficient to have stable U i’s only for the operator pieces having the highest number of spatial derivatives — the other Ui’s can be unstable — to make the overall scheme stable! It is at this point that we turn our attention from initial value problems to boundary value problems. These will occupy us for the remainder of the chapter. CITED REFERENCES AND FURTHER READING: Ames, W.F. 1977, Numerical Methods for Partial Differential Equations, 2nd ed. (New York: Academic Press). 19.4 Fourier and Cyclic Reduction Methods for Boundary Value Problems As discussed in §19.0, most boundary value problems (elliptic equations, for example) reduce to solving large sparse linear systems of the form A · u = b (19.4.1) either once, for boundary value equations that are linear, or iteratively, for boundary value equations that are nonlinear