An optimal order process for solving finite element equations

Authors:
Randolph E. Bank and Todd Dupont

Journal:
Math. Comp. **36** (1981), 35-51

MSC:
Primary 65N30; Secondary 65F10

DOI:
https://doi.org/10.1090/S0025-5718-1981-0595040-2

MathSciNet review:
595040

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A *k*-level iterative procedure for solving the algebraic equations which arise from the finite element approximation of elliptic boundary value problems is presented and analyzed. The work estimate for this procedure is proportional to the number of unknowns, an optimal order result. General geometry is permitted for the underlying domain, but the shape plays a role in the rate of convergence through elliptic regularity. Finally, a short discussion of the use of this method for parabolic problems is presented.

**[1]**N. S. Bakhvalov, "On the convergence of a relaxation method with natural constraints on the elliptic operator,"*Ž. Vyčisl. Mat.i Mat. Fiz.*, v. 6, 1966, pp. 861-885.**[2]**R. E. Bank & Todd Dupont, "Analysis of a two-level scheme for solving finite element equations,"*Numer. Math.*(Submitted.)**[3]**J. H. Bramble, "Discrete methods for parabolic equations with time-dependent coefficients,"*Numerical Methods for PDEs*, Academic Press, New York, 1979, pp. 41-52. MR**558215 (80m:65063)****[4]**J. H. Bramble & S. R. Hilbert, "Bounds for a class of linear functionals with applications to Hermite interpolation,"*Numer. Math.*, v. 16, 1971, pp. 362-369. MR**0290524 (44:7704)****[5]**J. H. Bramble & M. Zlamal, "Triangular elements in the finite element method,"*Math. Comp.*, v. 24, 1970, pp. 809-821. MR**0282540 (43:8250)****[6]**A. Brandt, "Multi-level adaptive solutions to boundary value problems,"*Math. Comp.*, v. 31, 1977, pp. 333-390. MR**0431719 (55:4714)****[7]**Jim Douglas, Jr., Todd Dupont & R. E. Ewing, "Incomplete iteration for time-stepping a Galerkin method for a quasi-linear parabolic problem,"*SIAM J. Numer. Anal.*, v. 16, 1979, pp. 503-522. MR**530483 (80f:65117)****[8]**Jim Douglas, Jr. & Todd Dupont, "Galerkin methods for parabolic equations,"*SIAM J. Numer. Anal.*, v. 7, 1970, pp. 575-626. MR**0277126 (43:2863)****[9]**Jim Douglas, Jr., "Effective time-stepping methods for the numerical solution of nonlinear parabolic problems,"*The Mathematics of Finite Elements and Applications*III, MAFELAP 1978 (J. R. Whiteman, Ed.), Academic Press, New York, 1979, pp. 289-304. MR**559305 (81j:65116)****[10]**Todd Dupont & Ridgway Scott, "Polynomial approximation of functions in Sobolev spaces,"*Math Comp.*, v. 34, 1980, pp. 441-463. MR**559195 (81h:65014)****[11]**R. P. Fedorenko, "A relaxation method for solving elliptic difference equations,"*Ž. Vyčisl. Mat. i Mat. Fiz.*, v. 1, 1961, pp. 922-927. MR**0137314 (25:766)****[12]**R. P. Fedorenko, "The speed of convergence of one iterative process,"*Ž. Vyčisl. Mat. i Mat. Fiz.*, v. 4, 1964, pp. 559-564. MR**0182163 (31:6386)****[13]**P. Grisvard, "Behavior of the solutions of an elliptic boundary value problem in a polygon or polyhedral domain,"*Numerical Solution of Partial Differential Equations*-III (B. Hubbard, Ed.), Academic Press, New York, 1975, pp. 207-274. MR**0466912 (57:6786)****[14]**W. Hackbusch,*On the Convergence of a Multi-Grid Iteration Applied to Finite Element Equations*, Report 77-8, Universität zu Köln, July 1977.**[15]**W. Hackbusch,*On the Computation of Approximate Eigenvalues and Eigenfunctions of Elliptic Operators by Means of a Multi-Grid Method*, Report 77-10, Universität zu Köln, August 1977.**[16]**P. Jamet, "Estimations d'erreur pour des éléments finis droits presque dégénérés,"*Rev. Française Automat. Informat. Recherche Operationelle, Ser. Rouge*, v. 10, 1976, pp. 43-61. MR**0455282 (56:13521)****[17]**R. A. Nicolaides, "On multiple grid and related techniques for solving discrete elliptic systems,"*J. Comput. Phys.*, v. 19, 1975, pp. 418-431. MR**0413541 (54:1655)****[18]**R. A. Nicolaides, "On the convergence of an algorithm for solving finite element equations,"*Math. Comp.*, v. 31, 1977, pp. 892-906. MR**0488722 (58:8239)****[19]**D. J. Rose & G. F. Whitten, "A recursive analysis of dissection strategies,"*Sparse Matrix Computations*(J. R. Bunch and D. J. Rose, Eds.), Academic Press, New York, 1976, pp. 59-83. MR**0521077 (58:25119)****[20]**Ridgway Scott, "Interpolated boundary conditions on the finite element method,"*SIAM J. Numer. Anal.*, v. 12, 1975, pp. 404-427. MR**0386304 (52:7162)****[21]**G. Strang & G. Fix,*An Analysis of the Finite Element Method*, Prentice-Hall, Englewood Cliffs, N. J., 1973. MR**0443377 (56:1747)****[22]**V. Thomée, "Negative norm estimates and super convergence in Galerkin methods for parabolic problems,"*Math. Comp.*, v. 34, 1980, pp. 93-113. MR**551292 (81a:65092)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65N30,
65F10

Retrieve articles in all journals with MSC: 65N30, 65F10

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1981-0595040-2

Article copyright:
© Copyright 1981
American Mathematical Society