Incomplete iterations in multistep backward difference methods for parabolic problems with smooth and nonsmooth data
Authors:
James H. Bramble, Joseph E. Pasciak, Peter H. Sammon and Vidar Thomée
Journal:
Math. Comp. 52 (1989), 339367
MSC:
Primary 65N10; Secondary 65N20
MathSciNet review:
962207
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Backward difference methods for the discretization of parabolic boundary value problems are considered in this paper. In particular, we analyze the case when the backward difference equations are only solved 'approximately' by a preconditioned iteration. We provide an analysis which shows that these methods remain stable and accurate if a suitable number of iterations (often independent of the spatial discretization and time step size) are used. Results are provided for the smooth as well as nonsmooth initial data cases. Finally, the results of numerical experiments illustrating the algorithms' performance on model problems are given.
 [1]
Garth
A. Baker, James
H. Bramble, and Vidar
Thomée, Single step Galerkin approximations
for parabolic problems, Math. Comp.
31 (1977), no. 140, 818–847. MR 0448947
(56 #7252), http://dx.doi.org/10.1090/S0025571819770448947X
 [2]
James
H. Bramble, Discrete methods for parabolic equations with
timedependent coefficients, Numerical methods for partial
differential equations (Proc. Adv. Sem., Math. Res. Center, Univ.
Wisconsin, Madison, Wis., 1978) Publ. Math. Res. Center Univ. Wisconsin,
vol. 42, Academic Press, New YorkLondon, 1979, pp. 41–52.
MR 558215
(80m:65063)
 [3]
J. H. Bramble, R. E. Ewing, J. E. Pasciak & A. H. Schatz, "A preconditioning technique for the efficient solution of problems with local grid refinement," Comput. Methods Appl. Mech. Engrg., v. 67, 1988, pp. 149159.
 [4]
James
H. Bramble and Joseph
E. Pasciak, New convergence estimates for
multigrid algorithms, Math. Comp.
49 (1987), no. 180, 311–329. MR 906174
(89b:65234), http://dx.doi.org/10.1090/S0025571819870906174X
 [5]
J.
H. Bramble, J.
E. Pasciak, and A.
H. Schatz, An iterative method for elliptic
problems on regions partitioned into substructures, Math. Comp. 46 (1986), no. 174, 361–369. MR 829613
(88a:65123), http://dx.doi.org/10.1090/S00255718198608296130
 [6]
J.
H. Bramble, J.
E. Pasciak, and A.
H. Schatz, The construction of preconditioners
for elliptic problems by substructuring. I, Math. Comp. 47 (1986), no. 175, 103–134. MR 842125
(87m:65174), http://dx.doi.org/10.1090/S00255718198608421253
 [7]
J.
H. Bramble, J.
E. Pasciak, and A.
H. Schatz, The construction of preconditioners
for elliptic problems by substructuring. II, Math. Comp. 49 (1987), no. 179, 1–16. MR 890250
(88j:65248), http://dx.doi.org/10.1090/S00255718198708902504
 [8]
James
H. Bramble, Joseph
E. Pasciak, and Alfred
H. Schatz, The construction of preconditioners
for elliptic problems by substructuring. III, Math. Comp. 51 (1988), no. 184, 415–430. MR 935071
(89e:65118), http://dx.doi.org/10.1090/S0025571819880935071X
 [9]
James
H. Bramble, Joseph
E. Pasciak, and Alfred
H. Schatz, The construction of preconditioners
for elliptic problems by substructuring. IV, Math. Comp. 53 (1989), no. 187, 1–24. MR 970699
(89m:65098), http://dx.doi.org/10.1090/S00255718198909706993
 [10]
James
H. Bramble and Peter
H. Sammon, Efficient higher order single step
methods for parabolic problems. I, Math.
Comp. 35 (1980), no. 151, 655–677. MR 572848
(81h:65110), http://dx.doi.org/10.1090/S0025571819800572848X
 [11]
J.
H. Bramble, A.
H. Schatz, V.
Thomée, and L.
B. Wahlbin, Some convergence estimates for semidiscrete Galerkin
type approximations for parabolic equations, SIAM J. Numer. Anal.
14 (1977), no. 2, 218–241. MR 0448926
(56 #7231)
 [12]
James
H. Bramble and Vidar
Thomée, Discrete time Galerkin methods for a parabolic
boundary value problem, Ann. Mat. Pura Appl. (4) 101
(1974), 115–152. MR 0388805
(52 #9639)
 [13]
R. Chandra, Conjugate Gradient Methods for Partial Differential Equations, Yale University, Dept. of Comp. Sci. Rep. No. 129, 1978.
 [14]
M.
Crouzeix and P.A.
Raviart, Approximation d’équations
d’évolution linéaires par des méthodes
multipas, Étude numérique des grands systèmes
(Proc. Sympos., Novosibirsk, 1976), Méthodes Math. Inform.,
vol. 7, Dunod, Paris, 1978, pp. 133–150 (French). MR 517853
(80d:65063)
 [15]
Colin
W. Cryer, On the instability of high order backwarddifference
multistep methods, Nordisk Tidskr. Informations behandling (BIT)
12 (1972), 17–25. MR 0311112
(46 #10208)
 [16]
Jim
Douglas Jr., Todd
Dupont, and Richard
E. Ewing, Incomplete iteration for timestepping a Galerkin method
for a quasilinear parabolic problem, SIAM J. Numer. Anal.
16 (1979), no. 3, 503–522. MR 530483
(80f:65117), http://dx.doi.org/10.1137/0716039
 [17]
Todd
Dupont, Richard
P. Kendall, and H.
H. Rachford Jr., An approximate factorization procedure for solving
selfadjoint elliptic difference equations, SIAM J. Numer. Anal.
5 (1968), 559–573. MR 0235748
(38 #4051)
 [18]
C.
William Gear, Numerical initial value problems in ordinary
differential equations, PrenticeHall, Inc., Englewood Cliffs, N.J.,
1971. MR
0315898 (47 #4447)
 [19]
F.
B. Hildebrand, Introduction to numerical analysis, McGrawHill
Book Company, Inc., New YorkTorontoLondon, 1956. MR 0075670
(17,788d)
 [20]
Stephen
L. Keeling, Galerkin/RungeKutta discretizations
for parabolic equations with timedependent coefficients, Math. Comp. 52 (1989), no. 186, 561–586. MR 958873
(90a:65239), http://dx.doi.org/10.1090/S00255718198909588733
 [21]
MarieNoëlle
Le Roux, Semidiscretization in time for
parabolic problems, Math. Comp.
33 (1979), no. 147, 919–931. MR 528047
(80f:65101), http://dx.doi.org/10.1090/S00255718197905280472
 [22]
J. L. Lions & E. Magenes, Problèmes aux Limites non Homogènes et Applications, Dunod, Paris, 1968.
 [23]
W. M. Patterson, 3rd, Iterative Methods for the Solution of a Linear Operator Equation in Hilbert SpaceA Survey, Lecture Notes in Math., vol. 394, SpringerVerlag, New York, 1974.
 [24]
V. Thomée, Galerkin Finite Element Methods for Parabolic Problems, Lecture Notes in Math., vol. 1054, SpringerVerlag, New York, 1984.
 [25]
Harry
Yserentant, On the multilevel splitting of finite element
spaces, Numer. Math. 49 (1986), no. 4,
379–412. MR
853662 (88d:65068a), http://dx.doi.org/10.1007/BF01389538
 [26]
Miloš
Zlámal, Finite element multistep
discretizations of parabolic boundary value problems, Math. Comp. 29 (1975), 350–359. MR 0371105
(51 #7326), http://dx.doi.org/10.1090/S00255718197503711052
 [1]
 G. A. Baker, J. H. Bramble & V. Thomée, "Single step Galerkin approximations for parabolic problems," Math. Comp., v. 31, 1977, pp. 818847. MR 0448947 (56:7252)
 [2]
 J. H. Bramble, "Discrete methods for parabolic equations with timedependent coefficients," in Numerical Methods for PDE's, Academic Press, New York, 1979, pp. 4152. MR 558215 (80m:65063)
 [3]
 J. H. Bramble, R. E. Ewing, J. E. Pasciak & A. H. Schatz, "A preconditioning technique for the efficient solution of problems with local grid refinement," Comput. Methods Appl. Mech. Engrg., v. 67, 1988, pp. 149159.
 [4]
 J. H. Bramble & J. E. Pasciak, "New convergence estimates for multigrid algorithms," Math. Comp., v. 49, 1987, pp. 311329. MR 906174 (89b:65234)
 [5]
 J. H. Bramble, J. E. Pasciak & A. H. Schatz, "An iterative method for elliptic problems on regions partitioned into substructures," Math. Comp., v. 46, 1986, pp. 361369. MR 829613 (88a:65123)
 [6]
 J. H. Bramble, J. E. Pasciak & A. H. Schatz, "The construction of preconditioners for elliptic problems by substructuring, I," Math. Comp., v. 47, 1986, pp. 103134. MR 842125 (87m:65174)
 [7]
 J. H. Bramble, J. E. Pasciak & A. H. Schatz, "The construction of preconditioners for elliptic problems by substructuring, II," Math. Comp., v. 49, 1987, pp. 116. MR 890250 (88j:65248)
 [8]
 J. H. Bramble, J. E. Pasciak & A. H. Schatz, "The construction of preconditioners for elliptic problems by substructuring, III," Math. Comp., v. 51, 1988, pp. 415430. MR 935071 (89e:65118)
 [9]
 J. H. Bramble, J. E. Pasciak & A. H. Schatz, "The construction of preconditioners for elliptic problems by substructuring, IV," Math. Comp. (To appear.) MR 970699 (89m:65098)
 [10]
 J. H. Bramble & P. H. Sammon, "Efficient higher order single step methods for parabolic problems: Part I," Math. Comp., v. 35, 1980, pp. 655677. MR 572848 (81h:65110)
 [11]
 J. H. Bramble, A. H. Schatz, V. Thomée & L. B. Wahlbin, "Some convergence estimates for Galerkin type approximation for parabolic equations," SIAM J. Numer. Anal., v. 14, 1977, pp. 218241. MR 0448926 (56:7231)
 [12]
 J. H. Bramble & V. Thomée, "Discrete time Galerkin methods for a parabolic boundary value problem," Ann. Mat. Pura Appl., v. 101, 1974, pp. 115152. MR 0388805 (52:9639)
 [13]
 R. Chandra, Conjugate Gradient Methods for Partial Differential Equations, Yale University, Dept. of Comp. Sci. Rep. No. 129, 1978.
 [14]
 M. Crouzeix & P. A. Raviart, "Approximation d'équations d'évolution linéaires par des méthodes multipas," in Étude Numérique des Grands Systèmes, Proc. Sympos. Novosibirsk, Dunod, Paris, 1978, pp. 133150. MR 517853 (80d:65063)
 [15]
 C. W. Cryer, "On the instability of high order backwarddifference multistep methods," BIT, v. 12, 1972, pp. 1725. MR 0311112 (46:10208)
 [16]
 J. Douglas, Jr., T. Dupont & R. Ewing, "Incomplete iterations for timestepping a Galerkin method for a quasilinear parabolic problem," SIAM J. Numer. Anal., v. 16, 1979, pp. 503522. MR 530483 (80f:65117)
 [17]
 T. Dupont, R. P. Kendall & H. H. Rachford, "An approximate factorization procedure for solving selfadjoint elliptic difference equations," SIAM J. Numer. Anal., v. 5, 1968, pp. 559573. MR 0235748 (38:4051)
 [18]
 C. W. Gear, Numerical Initial Value Problems in Ordinary Differential Equations, PrenticeHall, Englewood Cliffs, N. J., 1971. MR 0315898 (47:4447)
 [19]
 F. B. Hildebrand, Introduction to Numerical Analysis, McGrawHill, New York, 1956. MR 0075670 (17:788d)
 [20]
 S. L. Keeling, "Galerkin/RungeKutta discretizations for parabolic equations with time dependent coefficients," Preprint, 1987. MR 958873 (90a:65239)
 [21]
 M.N. Le Roux, "Semidiscretization in time for parabolic problems," Math. Comp., v. 33, 1979, pp. 919931. MR 528047 (80f:65101)
 [22]
 J. L. Lions & E. Magenes, Problèmes aux Limites non Homogènes et Applications, Dunod, Paris, 1968.
 [23]
 W. M. Patterson, 3rd, Iterative Methods for the Solution of a Linear Operator Equation in Hilbert SpaceA Survey, Lecture Notes in Math., vol. 394, SpringerVerlag, New York, 1974.
 [24]
 V. Thomée, Galerkin Finite Element Methods for Parabolic Problems, Lecture Notes in Math., vol. 1054, SpringerVerlag, New York, 1984.
 [25]
 H. Yserentant, "On the multilevel splitting of finite element spaces," Numer. Math., v. 49, 1986, pp. 379412. MR 853662 (88d:65068a)
 [26]
 M. Zlámal, "Finite element multistep discretizations of parabolic boundary value problems," Math. Comp., v. 29, 1975, pp. 350359. MR 0371105 (51:7326)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65N10,
65N20
Retrieve articles in all journals
with MSC:
65N10,
65N20
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198909622078
PII:
S 00255718(1989)09622078
Article copyright:
© Copyright 1989
American Mathematical Society
