Supra-convergent schemes on irregular grids
HTML articles powered by AMS MathViewer
- by H.-O. Kreiss, T. A. Manteuffel, B. Swartz, B. Wendroff and A. B. White PDF
- Math. Comp. 47 (1986), 537-554 Request permission
Abstract:
As Tikhonov and Samarskiĭ showed for $k = 2$, it is not essential that kth-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 kth difference quotient is set equal to the value of the kth derivative at the middle point of the stencil; the proof is particularly transparent for $k = 2$. For any k, in fact, there is a $\left \lfloor {k/2} \right \rfloor$-parameter family of symmetric averages of the values of the kth 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 ${D^2}y = f$ 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.References
- Eusebius J. Doedel, The construction of finite difference approximations to ordinary differential equations, SIAM J. Numer. Anal. 15 (1978), no. 3, 450–465. MR 483481, DOI 10.1137/0715029
- Eusebius J. Doedel, Some stability theorems for finite difference collocation methods on nonuniform meshes, BIT 20 (1980), no. 1, 58–66. MR 569977, DOI 10.1007/BF01933586
- 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 D. Grigorieff [1983], "Some stability inequalities for compact finite difference schemes," typescript, 17 pp.
- 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, DOI 10.1016/0021-9991(85)90070-1
- Peter D. Lax, Periodic solutions of the KdV equation, Comm. Pure Appl. Math. 28 (1975), 141–188. MR 369963, DOI 10.1002/cpa.3160280105 Levermore [1982], Lawrence Livermore National Laboratory, personal communication.
- 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, DOI 10.1090/S0025-5718-1980-0559190-8 A. Manteuffel & A. B. White [1985], "A calculus of difference operators." (In preparation.)
- 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, DOI 10.1090/S0025-5718-1986-0856700-3
- L. M. Milne-Thomson, The Calculus of Finite Differences, Macmillan & Co., Ltd., London, 1951. MR 0043339
- M. R. Osborne, Minimising truncation error in finite difference approximations to ordinary differential equations, Math. Comp. 21 (1967), 133–145. MR 223107, DOI 10.1090/S0025-5718-1967-0223107-X
- 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 162366 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. Samarskiĭ, Vvedenie v teoriyu raznostnykh skhem, Izdat. “Nauka”, Moscow, 1971 (Russian). MR 0347102
- Larry L. Schumaker, Spline functions: basic theory, Pure and Applied Mathematics, John Wiley & Sons, Inc., New York, 1981. MR 606200
- Marc Nico Spijker, Stability and convergence of finite-difference methods, Rijksuniversiteit te Leiden, Leiden, 1968 (English, with Dutch summary). Doctoral dissertation, University of Leiden, 1968. MR 0239761
- Hans J. Stetter, Analysis of discretization methods for ordinary differential equations, Springer Tracts in Natural Philosophy, Vol. 23, Springer-Verlag, New York-Heidelberg, 1973. MR 0426438 F. Steffensen [1927], Interpolation, Williams & Wilkins, Baltimore, Md.
- Carl de Boor (ed.), Mathematical aspects of finite elements in partial differential equations, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1974. Publication No. 33 of the Mathematics Research Center, The University of Wisconsin-Madison. MR 0349031
- 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 362953, DOI 10.1137/0711077
- Blair Swartz, Compact, implicit difference schemes for a differential equation’s side conditions, Math. Comp. 35 (1980), no. 151, 733–746. MR 572851, DOI 10.1090/S0025-5718-1980-0572851-X
- 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 371088, DOI 10.1137/0711081
- 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 168128
- 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, DOI 10.1137/0725025 Wheeler [1983], Dept. of Math. Sci., Rice University, personal communication.
Additional Information
- © Copyright 1986 American Mathematical Society
- 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