Supra-convergent schemes on irregular grids

Authors:
H.-O. Kreiss, T. A. Manteuffel, B. Swartz, B. Wendroff and A. B. White

Journal:
Math. Comp. **47** (1986), 537-554

MSC:
Primary 65L05; Secondary 40A30, 65D25, 65L10

DOI:
https://doi.org/10.1090/S0025-5718-1986-0856701-5

MathSciNet review:
856701

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: As Tikhonov and Samarskiĭ showed for , it is not essential that *k*th-order compact difference schemes be centered at the arithmetic mean of the stencil's points to yield second-order convergence (although it does suffice). For stable schemes and even *k*, the main point is seen when the *k*th difference quotient is set equal to the value of the *k*th derivative at the middle point of the stencil; the proof is particularly transparent for . For any *k*, in fact, there is a -parameter family of symmetric averages of the values of the *k*th derivative at the points of the stencil which, when similarly used, yield second-order convergence. The result extends to stable compact schemes for equations with lower-order terms under general boundary conditions. Although the extension of Numerov's tridiagonal scheme (approximating with third-order truncation error) yields fourth-order convergence on meshes consisting of a bounded number of pieces in which the mesh size changes monotonically, it yields only third-order convergence to quintic polynomials on any three-periodic mesh with unequal adjacent mesh sizes and fixed adjacent mesh ratios. A result of some independent interest is appended (and applied): it characterizes, simply, those functions of *k* variables which possess the property that their average value, as one translates over one period of an arbitrary periodic sequence of arguments, is zero; i.e., those bounded functions whose average value, as one translates over arbitrary finite sequences of arguments, goes to zero as the length of the sequences increases.

**[E]**Eusebius J. Doedel,*The construction of finite difference approximations to ordinary differential equations*, SIAM J. Numer. Anal.**15**(1978), no. 3, 450–465. MR**0483481**, https://doi.org/10.1137/0715029**[E]**Eusebius J. Doedel,*Some stability theorems for finite difference collocation methods on nonuniform meshes*, BIT**20**(1980), no. 1, 58–66. MR**569977**, https://doi.org/10.1007/BF01933586**[V]**Y. Alavi, G. Chartrand, D. R. Lick, and C. E. Wall (eds.),*Graph theory with applications to algorithms and computer science*, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1985. MR**812651****[R]**D. Grigorieff [1983], "Some stability inequalities for compact finite difference schemes," typescript, 17 pp.**[E]**E. W. Larsen, C. D. Levermore, G. C. Pomraning, and J. G. Sanderson,*Discretization methods for one-dimensional Fokker-Planck operators*, J. Comput. Phys.**61**(1985), no. 3, 359–390. MR**816660**, https://doi.org/10.1016/0021-9991(85)90070-1**[P]**Peter D. Lax,*Periodic solutions of the KdV equation*, Comm. Pure Appl. Math.**28**(1975), 141–188. MR**0369963**, https://doi.org/10.1002/cpa.3160280105**[D]**Levermore [1982], Lawrence Livermore National Laboratory, personal communication.**[R]**Robert E. Lynch and John R. Rice,*A high-order difference method for differential equations*, Math. Comp.**34**(1980), no. 150, 333–372. MR**559190**, https://doi.org/10.1090/S0025-5718-1980-0559190-8**[T]**A. Manteuffel & A. B. White [1985], "A calculus of difference operators." (In preparation.)**[T]**Thomas A. Manteuffel and Andrew B. White Jr.,*The numerical solution of second-order boundary value problems on nonuniform meshes*, Math. Comp.**47**(1986), no. 176, 511–535, S53–S55. MR**856700**, https://doi.org/10.1090/S0025-5718-1986-0856700-3**[L]**L. M. Milne-Thomson,*The Calculus of Finite Differences*, Macmillan and Co., Ltd., London, 1951. MR**0043339****[M]**M. R. Osborne,*Minimising truncation error in finite difference approximations to ordinary differential equations*, Math. Comp.**21**(1967), 133–145. MR**0223107**, https://doi.org/10.1090/S0025-5718-1967-0223107-X**[A]**A. A. Samarskiĭ,*Homogeneous difference schemes on non-uniform grids for equations of parabolic type*, Ž. Vyčisl. Mat. i Mat. Fiz.**3**(1963), 266–298 (Russian). MR**0162366****[A]**A. Samarskiĭ [1963b], "Local one dimensional difference schemes on non-uniform nets,"*Zh. Vychisl. Mat. i Mat. Fiz.*, v. 3, pp. 431-466; English transl. in*U.S.S.R. Comput. Math. and Math. Phys.*, v. 3, pp. 572-619.**[A]**A. A. Samarskiĭ,*\cyr Vvedenie v teoriyu raznostnykh skhem*, Izdat. “Nauka”, Moscow, 1971 (Russian). MR**0347102****[L]**Larry L. Schumaker,*Spline functions: basic theory*, John Wiley & Sons, Inc., New York, 1981. Pure and Applied Mathematics; A Wiley-Interscience Publication. MR**606200****[M]**Marc Nico Spijker,*Stability and convergence of finite-difference methods*, Doctoral dissertation, University of Leiden, vol. 1968, Rijksuniversiteit te Leiden, Leiden, 1968 (English, with Dutch summary). MR**0239761****[H]**Hans J. Stetter,*Analysis of discretization methods for ordinary differential equations*, Springer-Verlag, New York-Heidelberg, 1973. Springer Tracts in Natural Philosophy, Vol. 23. MR**0426438****[J]**F. Steffensen [1927],*Interpolation*, Williams & Wilkins, Baltimore, Md.**[B]**Carl de Boor (ed.),*Mathematical aspects of finite elements in partial differential equations*, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1974. Publication No. 33 of the Mathematics Research Center, The University of Wisconsin-Madison. MR**0349031****[B]**Blair Swartz and Burton Wendroff,*The relation between the Galerkin and collocation methods using smooth splines*, SIAM J. Numer. Anal.**11**(1974), 994–996. MR**0362953**, https://doi.org/10.1137/0711077**[B]**Blair Swartz,*Compact, implicit difference schemes for a differential equation’s side conditions*, Math. Comp.**35**(1980), no. 151, 733–746. MR**572851**, https://doi.org/10.1090/S0025-5718-1980-0572851-X**[V]**Vidar Thomée and Burton Wendroff,*Convergence estimates for Galerkin methods for variable coefficient initial value problems*, SIAM J. Numer. Anal.**11**(1974), 1059–1068. MR**0371088**, https://doi.org/10.1137/0711081**[A]**A. N. Tihonov and A. A. Samarskiĭ,*Homogeneous difference schemes on irregular meshes*, Ž. Vyčisl. Mat. i Mat. Fiz.**2**(1962), 812–832 (Russian). MR**0168128****[A]**Alan Weiser and Mary Fanett Wheeler,*On convergence of block-centered finite differences for elliptic problems*, SIAM J. Numer. Anal.**25**(1988), no. 2, 351–375. MR**933730**, https://doi.org/10.1137/0725025**[M]**Wheeler [1983], Dept. of Math. Sci., Rice University, personal communication.

Retrieve articles in *Mathematics of Computation*
with MSC:
65L05,
40A30,
65D25,
65L10

Retrieve articles in all journals with MSC: 65L05, 40A30, 65D25, 65L10

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1986-0856701-5

Keywords:
Initial value problems,
boundary value problems,
compact difference schemes,
irregular grids,
nonuniform mesh,
difference quotients,
divided differences,
truncation error,
supra-convergence,
superconvergence

Article copyright:
© Copyright 1986
American Mathematical Society