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

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

MathSciNet review:
694388

Full-text PDF

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]**G. A. Baker,*Essentials of Padé approximants*, Academic Press, New York, 1975. MR**0454459 (56:12710)****[2]**G. Dahlquist,*A special stability problem for linear multistep methods*, BIT**3**(1963), 27-43. MR**0170477 (30:715)****[3]**-,*Convergence and stability in the numerical integration of ordinary differential equations*, Math. Scand.**4**(1956), 33-53. MR**0080998 (18:338d)****[4]**J. W. Daniel and R. E. Moore,*Computation and theory in ordinary differential equations*, Freeman, San Francisco, 1970. MR**0267765 (42:2667)****[5]**B. L. Ehle, -*stable methods and Padé approximations to the exponential*, Siam J. Numer. Anal.**4**(1973), 571-580. MR**0331787 (48:10119)****[6]**B. Engquist and S. Osher,*One-sided difference approximations for non-linear conservation laws*, Math. Comp.**36**(1981), 321-352. MR**606500 (82c:65056)****[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), 241-251. MR**641308 (83a:65015)****[9]**A. Iserles,*Order stars and a saturation theorem for first order hyperbolics*, IMA J. Numer. Anal. (to appear). MR**654266 (83d:65253)****[10]**-,*A note on Padé approximations and generalized hypergeometric functions*, BIT**19**(1979), 543-545. MR**559965 (81a:41028)****[11]**-,*On the generalized Padé approximations to the exponential function*, Siam J. Numer. Anal.**16**(1979), 631-636. MR**537277 (80i:41013)****[12]**P. 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 (26:3215)****[13]**E. D. Rainville,*Special functions*, Macmillan, New York, 1967. MR**0107725 (21:6447)****[14]**G. Strang,*Trigonometric polynomials and difference methods of maximum accuracy*, J. Math. Phys.**41**(1962), 147-154.**[15]**-,*Accurate partial difference methods*. II.*Non-linear problems*, Numer. Math.**6**(1964), 37-46. MR**0166942 (29:4215)****[16]**-,*Wiener-Hopf difference equations*, J. Math. Mech.**13**(1964), 37-46. MR**0160335 (28:3548)****[17]**-,*Implicit difference methods for initial-boundary value problems*, J. Math. Anal. Appl.**16**(1966), 188-198. MR**0205496 (34:5323)****[18]**G. Szegö,*Orthogonal polynomials*, Amer. Math. Soc. Colloq. Publ., vol. 23, Amer. Math. Soc., Providence, R.I., 1939.**[19]**G. E. Wanner, E. Hairer and S. P. Nørsett,*Order stars and stability theorems*, BIT**18**(1978), 475-489. MR**520756 (81b:65070)****[20]**O. B. Widlund,*On Lax's theorem on Friedrichs type finite difference schemes*, Comm. Pure Appl. Math.**24**(1971), 117-123. MR**0275693 (43:1446)**

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