The optimal accuracy of difference schemes

Authors:
Arieh Iserles and Gilbert Strang

Journal:
Trans. Amer. Math. Soc. **277** (1983), 779-803

MSC:
Primary 65M10; Secondary 41A21

MathSciNet review:
694388

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We consider difference approximations to the model hyperbolic equation which compute each new value as a combination of the known values . For such schemes we find the optimal order of accuracy: stability is possible for small if and only if . A similar bound is established for implicit methods. In this case the most accurate schemes are based on Padé approximations to near , and we find an expression for the difference ; this allows us to test the von Neumann condition . We also determine the number of zeros of in the unit circle, which decides whether the implicit part is uniformly invertible.

**[1]**George A. Baker Jr.,*Essentials of Padé approximants*, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1975. MR**0454459****[2]**Germund G. Dahlquist,*A special stability problem for linear multistep methods*, Nordisk Tidskr. Informations-Behandling**3**(1963), 27–43. MR**0170477****[3]**Germund Dahlquist,*Convergence and stability in the numerical integration of ordinary differential equations*, Math. Scand.**4**(1956), 33–53. MR**0080998****[4]**James W. Daniel and Ramon E. Moore,*Computation and theory in ordinary differential equations*, W. H. Freeman and Co., San Francisco, Calif., 1970 (German). MR**0267765****[5]**Byron L. Ehle,*𝐴-stable methods and Padé approximations to the exponential*, SIAM J. Math. Anal.**4**(1973), 671–680. MR**0331787****[6]**Björn Engquist and Stanley Osher,*One-sided difference approximations for nonlinear conservation laws*, Math. Comp.**36**(1981), no. 154, 321–351. MR**606500**, 10.1090/S0025-5718-1981-0606500-X**[7]**A. Erdelyi, et al.,*Higher transcendental functions*. I, McGraw-Hill, New York, 1953.**[8]**A. Iserles and M. J. D. Powell,*On the 𝐴-acceptability of rational approximations that interpolate the exponential function*, IMA J. Numer. Anal.**1**(1981), no. 3, 241–251. MR**641308**, 10.1093/imanum/1.3.241**[9]**Arieh Iserles,*Order stars and a saturation theorem for first-order hyperbolics*, IMA J. Numer. Anal.**2**(1982), no. 1, 49–61. MR**654266**, 10.1093/imanum/2.1.49**[10]**Arieh Iserles,*A note on Padé approximations and generalized hypergeometric functions*, BIT**19**(1979), no. 4, 543–545. MR**559965**, 10.1007/BF01931272**[11]**Arieh Iserles,*On the generalized Padé approximations to the exponential function*, SIAM J. Numer. Anal.**16**(1979), no. 4, 631–636. MR**537277**, 10.1137/0716048**[12]**Peter D. Lax,*On the stability of difference approximations to solutions of hyperbolic equations with variable coefficients*, Comm. Pure Appl. Math.**14**(1961), 497–520. MR**0145686****[13]**Earl D. Rainville,*Special functions*, The Macmillan Co., New York, 1960. MR**0107725****[14]**G. Strang,*Trigonometric polynomials and difference methods of maximum accuracy*, J. Math. Phys.**41**(1962), 147-154.**[15]**Gilbert Strang,*Accurate partial difference methods. II. Non-linear problems*, Numer. Math.**6**(1964), 37–46. MR**0166942****[16]**Gilbert Strang,*Wiener-Hopf difference equations*, J. Math. Mech.**13**(1964), 85–96. MR**0160335****[17]**Gilbert Strang,*Implicit difference methods for initial-boundary value problems*, J. Math. Anal. Appl.**16**(1966), 188–198. MR**0205496****[18]**G. Szegö,*Orthogonal polynomials*, Amer. Math. Soc. Colloq. Publ., vol. 23, Amer. Math. Soc., Providence, R.I., 1939.**[19]**G. Wanner, E. Hairer, and S. P. Nørsett,*Order stars and stability theorems*, BIT**18**(1978), no. 4, 475–489. MR**520756**, 10.1007/BF01932026**[20]**O. B. Widlund,*On Lax’s theorem on Friedrichs type finite difference schemes*, Comm. Pure Appl. Math.**24**(1971), 117–123. MR**0275693**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
65M10,
41A21

Retrieve articles in all journals with MSC: 65M10, 41A21

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1983-0694388-9

Article copyright:
© Copyright 1983
American Mathematical Society