Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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 $ {u_{t}} = {u_x}$ which compute each new value $ U(x,t + \Delta t)$ as a combination of the known values $ U(x - r\Delta x,t),\ldots,U(x + s\Delta x,\Delta t)$. For such schemes we find the optimal order of accuracy: stability is possible for small $ \Delta t/\Delta x$ if and only if $ p \leqslant \min \{ {r + s,2r + 2,2s} \}$. A similar bound is established for implicit methods. In this case the most accurate schemes are based on Padé approximations $ P(z)/Q(z)$ to $ {z^\lambda }$ near $ z = 1$, and we find an expression for the difference $ \vert Q{\vert^2} - \vert P{\vert^2}$; this allows us to test the von Neumann condition $ \vert P/Q\vert \leqslant 1$. We also determine the number of zeros of $ Q$ in the unit circle, which decides whether the implicit part is uniformly invertible.


References [Enhancements On Off] (What's this?)

  • [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, $ A$-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 $ A$-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)

Similar Articles

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

American Mathematical Society