Supraconvergent schemes on irregular grids
Authors:
H.O. Kreiss, T. A. Manteuffel, B. Swartz, B. Wendroff and A. B. White
Journal:
Math. Comp. 47 (1986), 537554
MSC:
Primary 65L05; Secondary 40A30, 65D25, 65L10
MathSciNet review:
856701
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: As Tikhonov and Samarskiĭ showed for , it is not essential that kthorder compact difference schemes be centered at the arithmetic mean of the stencil's points to yield secondorder 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 . For any k, in fact, there is a parameter family of symmetric averages of the values of the kth derivative at the points of the stencil which, when similarly used, yield secondorder convergence. The result extends to stable compact schemes for equations with lowerorder terms under general boundary conditions. Although the extension of Numerov's tridiagonal scheme (approximating with thirdorder truncation error) yields fourthorder convergence on meshes consisting of a bounded number of pieces in which the mesh size changes monotonically, it yields only thirdorder convergence to quintic polynomials on any threeperiodic 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
(58 #3482)
 [E]
Eusebius
J. Doedel, Some stability theorems for finite difference
collocation methods on nonuniform meshes, BIT 20
(1980), no. 1, 58–66. MR 569977
(81j:65090), http://dx.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 WileyInterscience Publication, John Wiley &
Sons Inc., New York, 1985. MR 812651
(86g:05026)
 [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 onedimensional
FokkerPlanck operators, J. Comput. Phys. 61 (1985),
no. 3, 359–390. MR 816660
(87j:82007), http://dx.doi.org/10.1016/00219991(85)900701
 [P]
Peter
D. Lax, Periodic solutions of the KdV equation, Comm. Pure
Appl. Math. 28 (1975), 141–188. MR 0369963
(51 #6192)
 [D]
Levermore [1982], Lawrence Livermore National Laboratory, personal communication.
 [R]
Robert
E. Lynch and John
R. Rice, A highorder difference method for
differential equations, Math. Comp.
34 (1980), no. 150, 333–372. MR 559190
(82b:65070), http://dx.doi.org/10.1090/S00255718198005591908
 [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 secondorder
boundary value problems on nonuniform meshes, Math. Comp. 47 (1986), no. 176, 511–535, S53–S55. MR 856700
(87m:65116), http://dx.doi.org/10.1090/S00255718198608567003
 [L]
L.
M. MilneThomson, The Calculus of Finite Differences,
Macmillan and Co., Ltd., London, 1951. MR 0043339
(13,245c)
 [M]
M.
R. Osborne, Minimising truncation error in finite
difference approximations to ordinary differential equations, Math. Comp. 21 (1967), 133–145. MR 0223107
(36 #6156), http://dx.doi.org/10.1090/S0025571819670223107X
 [A]
A.
A. Samarskiĭ, Homogeneous difference schemes on nonuniform
grids for equations of parabolic type, Ž. Vyčisl. Mat. i
Mat. Fiz. 3 (1963), 266–298 (Russian). MR 0162366
(28 #5565)
 [A]
A. Samarskiĭ [1963b], "Local one dimensional difference schemes on nonuniform nets," Zh. Vychisl. Mat. i Mat. Fiz., v. 3, pp. 431466; English transl. in U.S.S.R. Comput. Math. and Math. Phys., v. 3, pp. 572619.
 [A]
A.
A. \cyr{S}amarskiĭ, Vvedenie v teoriyu raznostnykh
skhem, Izdat. “Nauka”, Moscow, 1971 (Russian). MR 0347102
(49 #11822)
 [L]
Larry
L. Schumaker, Spline functions: basic theory, John Wiley &
Sons Inc., New York, 1981. Pure and Applied Mathematics; A
WileyInterscience Publication. MR 606200
(82j:41001)
 [M]
Marc
Nico Spijker, Stability and convergence of finitedifference
methods, Doctoral dissertation, University of Leiden, vol. 1968,
Rijksuniversiteit te Leiden, Leiden, 1968 (English, with Dutch summary). MR 0239761
(39 #1118)
 [H]
Hans
J. Stetter, Analysis of discretization methods for ordinary
differential equations, SpringerVerlag, New York, 1973. Springer
Tracts in Natural Philosophy, Vol. 23. MR 0426438
(54 #14381)
 [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 YorkLondon, 1974. Publication No. 33 of the
Mathematics Research Center, The University of WisconsinMadison. MR 0349031
(50 #1525)
 [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
(50 #15391)
 [B]
Blair
Swartz, Compact, implicit difference schemes
for a differential equation’s side conditions, Math. Comp. 35 (1980), no. 151, 733–746. MR 572851
(81f:65063), http://dx.doi.org/10.1090/S0025571819800572851X
 [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
(51 #7309)
 [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
(29 #5392)
 [A]
Alan
Weiser and Mary
Fanett Wheeler, On convergence of blockcentered finite differences
for elliptic problems, SIAM J. Numer. Anal. 25
(1988), no. 2, 351–375. MR 933730
(89m:65094), http://dx.doi.org/10.1137/0725025
 [M]
Wheeler [1983], Dept. of Math. Sci., Rice University, personal communication.
 [E]
 J. Doedel [1978], "The construction of finite difference approximations to ordinary differential equations," SIAM J. Numer. Anal., v. 15, pp. 450465. MR 0483481 (58:3482)
 [E]
 J. Doedel [1980], "Some stability theorems for finite difference collocation methods on nonuniform meshes," BIT, v. 20, pp. 5866. MR 569977 (81j:65090)
 [V]
 Faber & A. B. White [1985], "Supraconvergence and functions that sum to zero on cycles," in Graph Theory with Applications to Algorithms and Computer Science (Y. Alavi, G. Chartrand, L. Lesniak, D. R. Lick, and C. E. Wall, eds.), Wiley, New York. MR 812651 (86g:05026)
 [R]
 D. Grigorieff [1983], "Some stability inequalities for compact finite difference schemes," typescript, 17 pp.
 [E]
 W. Larsen, C. D. Levermore, G. C. Pomaraning & J. G. Sanderson [1985], "Discretization methods for FokkerPlanck operators," J. Comput. Phys., v. 61, pp. 359390. MR 816660 (87j:82007)
 [P]
 Lax [1975], "Periodic solutions of the KdV equation," Comm. Pure Appl. Math., v. 28, pp. 141188. MR 0369963 (51:6192)
 [D]
 Levermore [1982], Lawrence Livermore National Laboratory, personal communication.
 [R]
 E. Lynch & J. R. Rice [1980], "A highorder difference method for differential equations," Math. Comp., v. 34, pp. 333372. MR 559190 (82b:65070)
 [T]
 A. Manteuffel & A. B. White [1985], "A calculus of difference operators." (In preparation.)
 [T]
 A. Manteuffel & A. B. White [1986], "The numerical solution of secondorder boundary value problems on nonuniform meshes," Math. Comp., v. 47, pp. 511535. MR 856700 (87m:65116)
 [L]
 M. MilneThomson [1933], The Calculus of Finite Differences, Macmillan, London. MR 0043339 (13:245c)
 [M]
 R. Osborne [1967], "Minimizing truncation error in finite difference approximations to ordinary differential equations," Math. Comp., v. 21, pp. 133145. MR 0223107 (36:6156)
 [A]
 A. Samarskiĭ [1963a], "Homogeneous difference schemes on nonuniform nets for equations of parabolic type," Zh. Vychisl. Mat. i Mat. Fiz., v. 3, pp. 266298; English transl. in U.S.S.R. Comput. Math. and Math. Phys., v. 2, pp. 351393. MR 0162366 (28:5565)
 [A]
 A. Samarskiĭ [1963b], "Local one dimensional difference schemes on nonuniform nets," Zh. Vychisl. Mat. i Mat. Fiz., v. 3, pp. 431466; English transl. in U.S.S.R. Comput. Math. and Math. Phys., v. 3, pp. 572619.
 [A]
 A. Samarskiĭ [1971], Introduction to the Theory of Difference Schemes, "Nauka", Moscow. (Russian) MR 0347102 (49:11822)
 [L]
 L. Schumaker [1981], Spline Functions: Basic Theory, Wiley, New York. MR 606200 (82j:41001)
 [M]
 N. Spijker [1968], Stability and Convergence of Finite Difference Schemes, Thesis, University of Leiden. MR 0239761 (39:1118)
 [H]
 J. Stetter [1973], Analysis of Discretization Methods for Ordinary Differential Equations, SpringerVerlag, New York. MR 0426438 (54:14381)
 [J]
 F. Steffensen [1927], Interpolation, Williams & Wilkins, Baltimore, Md.
 [B]
 K. Swartz [1974], "The construction and comparison of finite difference analogs of some finite element schemes," in Mathematical Aspects of Finite Elements in Partial Differential Equations (C. de Boor, ed.), Academic Press, New York, pp. 279312. MR 0349031 (50:1525)
 [B]
 Swartz & B. Wendroff [1974], "The relation between the Galerkin and collocation methods using smooth splines," SIAM J. Numer. Anal., v. 11, pp. 994996. MR 0362953 (50:15391)
 [B]
 Swartz [1980], "Compact, implicit difference schemes for a differential equation's side conditions," Math. Comp., v. 35, pp. 733746. MR 572851 (81f:65063)
 [V]
 Thomée & B. Wendroff [1974], "Convergence estimates for Galerkin methods for variable coefficient initial value problems," SIAM J. Numer. Anal., v. 11, pp. 10591068. MR 0371088 (51:7309)
 [A]
 N. Tikhonov & A. A. Samarskiĭ [1962], "Homogeneous difference schemes on nonuniform nets," Zh. Vychisl. Mat. i Mat. Fiz., v. 2, pp. 812832; English transl. in U.S.S.R. Comput. Math. and Math. Phys., v. 2, pp. 927953. MR 0168128 (29:5392)
 [A]
 Weisert & M. F. Wheeler [1984], "On convergence of blockcentered finite differences for elliptic problems," submitted to SIAM J. Numer. Anal. MR 933730 (89m:65094)
 [M]
 Wheeler [1983], Dept. of Math. Sci., Rice University, personal communication.
Similar Articles
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:
http://dx.doi.org/10.1090/S00255718198608567015
PII:
S 00255718(1986)08567015
Keywords:
Initial value problems,
boundary value problems,
compact difference schemes,
irregular grids,
nonuniform mesh,
difference quotients,
divided differences,
truncation error,
supraconvergence,
superconvergence
Article copyright:
© Copyright 1986 American Mathematical Society
