The optimal accuracy of difference schemes
Authors:
Arieh Iserles and Gilbert Strang
Journal:
Trans. Amer. Math. Soc. 277 (1983), 779803
MSC:
Primary 65M10; Secondary 41A21
MathSciNet review:
694388
Fulltext PDF Free Access
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]
George
A. Baker Jr., Essentials of Padé approximants, Academic
Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New
YorkLondon, 1975. MR 0454459
(56 #12710)
 [2]
Germund
G. Dahlquist, A special stability problem for linear multistep
methods, Nordisk Tidskr. InformationsBehandling 3
(1963), 27–43. MR 0170477
(30 #715)
 [3]
Germund
Dahlquist, Convergence and stability in the numerical integration
of ordinary differential equations, Math. Scand. 4
(1956), 33–53. MR 0080998
(18,338d)
 [4]
James
W. Daniel and Ramon
E. Moore, Computation and theory in ordinary differential
equations, W. H. Freeman and Co., San Francisco, Calif., 1970
(German). MR
0267765 (42 #2667)
 [5]
Byron
L. Ehle, 𝐴stable methods and Padé approximations to
the exponential, SIAM J. Math. Anal. 4 (1973),
671–680. MR 0331787
(48 #10119)
 [6]
Björn
Engquist and Stanley
Osher, Onesided difference approximations
for nonlinear conservation laws, Math.
Comp. 36 (1981), no. 154, 321–351. MR 606500
(82c:65056), http://dx.doi.org/10.1090/S0025571819810606500X
 [7]
A. Erdelyi, et al., Higher transcendental functions. I, McGrawHill, 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), no. 3, 241–251. MR 641308
(83a:65015), http://dx.doi.org/10.1093/imanum/1.3.241
 [9]
Arieh
Iserles, Order stars and a saturation theorem for firstorder
hyperbolics, IMA J. Numer. Anal. 2 (1982),
no. 1, 49–61. MR 654266
(83d:65253), http://dx.doi.org/10.1093/imanum/2.1.49
 [10]
Arieh
Iserles, A note on Padé approximations and generalized
hypergeometric functions, BIT 19 (1979), no. 4,
543–545. MR
559965 (81a:41028), http://dx.doi.org/10.1007/BF01931272
 [11]
Arieh
Iserles, On the generalized Padé approximations to the
exponential function, SIAM J. Numer. Anal. 16 (1979),
no. 4, 631–636. MR 537277
(80i:41013), http://dx.doi.org/10.1137/0716048
 [12]
Peter
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]
Earl
D. Rainville, Special functions, The Macmillan Co., New York,
1960. MR
0107725 (21 #6447)
 [14]
G. Strang, Trigonometric polynomials and difference methods of maximum accuracy, J. Math. Phys. 41 (1962), 147154.
 [15]
Gilbert
Strang, Accurate partial difference methods. II. Nonlinear
problems, Numer. Math. 6 (1964), 37–46. MR 0166942
(29 #4215)
 [16]
Gilbert
Strang, WienerHopf difference equations, J. Math. Mech.
13 (1964), 85–96. MR 0160335
(28 #3548)
 [17]
Gilbert
Strang, Implicit difference methods for initialboundary 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.
Wanner, E.
Hairer, and S.
P. Nørsett, Order stars and stability theorems, BIT
18 (1978), no. 4, 475–489. MR 520756
(81b:65070), http://dx.doi.org/10.1007/BF01932026
 [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)
 [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), 2743. MR 0170477 (30:715)
 [3]
 , Convergence and stability in the numerical integration of ordinary differential equations, Math. Scand. 4 (1956), 3353. 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), 571580. MR 0331787 (48:10119)
 [6]
 B. Engquist and S. Osher, Onesided difference approximations for nonlinear conservation laws, Math. Comp. 36 (1981), 321352. MR 606500 (82c:65056)
 [7]
 A. Erdelyi, et al., Higher transcendental functions. I, McGrawHill, 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), 241251. 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), 543545. MR 559965 (81a:41028)
 [11]
 , On the generalized Padé approximations to the exponential function, Siam J. Numer. Anal. 16 (1979), 631636. 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), 497520. 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), 147154.
 [15]
 , Accurate partial difference methods. II. Nonlinear problems, Numer. Math. 6 (1964), 3746. MR 0166942 (29:4215)
 [16]
 , WienerHopf difference equations, J. Math. Mech. 13 (1964), 3746. MR 0160335 (28:3548)
 [17]
 , Implicit difference methods for initialboundary value problems, J. Math. Anal. Appl. 16 (1966), 188198. 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), 475489. MR 520756 (81b:65070)
 [20]
 O. B. Widlund, On Lax's theorem on Friedrichs type finite difference schemes, Comm. Pure Appl. Math. 24 (1971), 117123. 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:
http://dx.doi.org/10.1090/S00029947198306943889
PII:
S 00029947(1983)06943889
Article copyright:
© Copyright 1983
American Mathematical Society
