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

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]**James H. Bramble,*Discrete methods for parabolic equations with time-dependent 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 York-London, 1979, pp. 41–52. MR**558215****[4]**J. H. Bramble and S. R. Hilbert,*Bounds for a class of linear functionals with applications to Hermite interpolation*, Numer. Math.**16**(1970/1971), 362–369. MR**0290524****[5]**James H. Bramble and Miloš Zlámal,*Triangular elements in the finite element method*, Math. Comp.**24**(1970), 809–820. MR**0282540**, 10.1090/S0025-5718-1970-0282540-0**[6]**Achi Brandt,*Multi-level adaptive solutions to boundary-value problems*, Math. Comp.**31**(1977), no. 138, 333–390. MR**0431719**, 10.1090/S0025-5718-1977-0431719-X**[7]**Jim Douglas Jr., Todd Dupont, and Richard E. Ewing,*Incomplete iteration for time-stepping a Galerkin method for a quasilinear parabolic problem*, SIAM J. Numer. Anal.**16**(1979), no. 3, 503–522. MR**530483**, 10.1137/0716039**[8]**Jim Douglas Jr. and Todd Dupont,*Galerkin methods for parabolic equations*, SIAM J. Numer. Anal.**7**(1970), 575–626. MR**0277126****[9]**Jim Douglas Jr.,*Effective time-stepping methods for the numerical solution of nonlinear parabolic problems*, Mathematics of finite elements and applications, III (Proc. Third MAFELAP Conf., Brunel Univ., Uxbridge, 1978) Academic Press, London-New York, 1979, pp. 289–304. MR**559305****[10]**Todd Dupont and Ridgway Scott,*Polynomial approximation of functions in Sobolev spaces*, Math. Comp.**34**(1980), no. 150, 441–463. MR**559195**, 10.1090/S0025-5718-1980-0559195-7**[11]**R. P. Fedorenko,*A relaxation method of solution of elliptic difference equations*, Ž. Vyčisl. Mat. i Mat. Fiz.**1**(1961), 922–927 (Russian). MR**0137314****[12]**R. P. Fedorenko,*On the speed of convergence of an iteration process*, Ž. Vyčisl. Mat. i Mat. Fiz.**4**(1964), 559–564 (Russian). MR**0182163****[13]**Pierre Grisvard,*Behavior of the solutions of an elliptic boundary value problem in a polygonal or polyhedral domain*, Numerical solution of partial differential equations, III (Proc. Third Sympos. (SYNSPADE), Univ. Maryland, College Park, Md., 1975) Academic Press, New York, 1976, pp. 207–274. MR**0466912****[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]**Pierre Jamet,*Estimations d’erreur pour des éléments finis droits presque dégénérés*, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. \jname RAIRO Analyse Numérique**10**(1976), no. R-1, 43–60 (French, with Loose English summary). MR**0455282****[17]**R. A. Nicolaides,*On multiple grid and related techniques for solving discrete elliptic systems*, J. Computational Phys.**19**(1975), no. 4, 418–431. MR**0413541****[18]**R. A. Nicolaides,*On the 𝑙² convergence of an algorithm for solving finite element equations*, Math. Comp.**31**(1977), no. 140, 892–906. MR**0488722**, 10.1090/S0025-5718-1977-0488722-3**[19]**Donald J. Rose and Gregory F. Whitten,*A recursive analysis of dissection strategies*, Sparse matrix computations (Proc. Sympos., Argonne Nat. Lab., Lemont, Ill., 1975) Academic Press, New York, 1976, pp. 59–83. MR**0521077****[20]**Ridgway Scott,*Interpolated boundary conditions in the finite element method*, SIAM J. Numer. Anal.**12**(1975), 404–427. MR**0386304****[21]**Gilbert Strang and George J. Fix,*An analysis of the finite element method*, Prentice-Hall, Inc., Englewood Cliffs, N. J., 1973. Prentice-Hall Series in Automatic Computation. MR**0443377****[22]**Vidar Thomée,*Negative norm estimates and superconvergence in Galerkin methods for parabolic problems*, Math. Comp.**34**(1980), no. 149, 93–113. MR**551292**, 10.1090/S0025-5718-1980-0551292-5

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