Summary
In this paper we analyze the condition number of the stiffness matrices arising in the discretization of selfadjoint and positive definite plane elliptic boundary value problems of second order by finite element methods when using hierarchical bases of the finite element spaces instead of the usual nodal bases. We show that the condition number of such a stiffness matrix behaves like O((log κ)2) where κ is the condition number of the stiffness matrix with respect to a nodal basis. In the case of a triangulation with uniform mesh sizeh this means that the stiffness matrix with respect to a hierarchical basis of the finite element space has a condition number behaving like\(O\left( {\left( {\log \frac{1}{h}} \right)^2 } \right)\) instead of\(O\left( {\left( {\frac{1}{h}} \right)^2 } \right)\) for a nodal basis. The proofs of our theorems do not need any regularity properties of neither the continuous problem nor its discretization. Especially we do not need the quasiuniformity of the employed triangulations. As the representation of a finite element function with respect to a hierarchical basis can be converted very easily and quickly to its representation with respect to a nodal basis, our results mean that the method of conjugate gradients needs onlyO(log n) steps andO(n log n) computer operations to reduce the energy norm of the error by a given factor if one uses hierarchical bases or related preconditioning procedures. Heren denotes the dimension of the finite element space and of the discrete linear problem to be solved.
Similar content being viewed by others
References
Axelsson, O., Barker, V.A.: Finite element solution of boundary value problems: Theory and computation. New York: Academic Press 1984
Axelsson, O., Gustafsson, I.: Preconditioning and two-level multigrid methods of arbitrary degree of approximation. Math. Comput.40, 219–242 (1983)
Bank, R.E.: PLTMG user's guide, Edition 4.0, Technical Report, Department of Mathematics, University of California at San Diego 1985
Bank, R.E., Dupont, T.: An optimal order process for solving finite element equation. Math. Comput.36, 35–51 (1981)
Bank, R.E., Dupont, T.: Analysis of a two-level scheme for solving finite element equations. Report CNA-159, Center for Numerical Analysis, University of Texas at Austin 1980
Braess, D.: The contraction number of a multigrid method for solving the Poisson equation. Numer. Math.37, 387–404 (1981)
Hackbusch, W.: On the convergence of multi-grid iterations. Beiträge Numer. Math.9, 213–329 (1981)
Hackbusch, W.: Multi-grid convergence theory. In: Multigrid methods. (W. Hackbusch and U. Trottenberg eds.).
Hackbusch, W., Trottenberg, U.: Multigrid methods. Proceedings, Köln 1981, Lect. Notes Math. 960. Berlin, Heidelberg, New York: Springer 1982
Oganesjan, L.A., Ruhovec, L.A.: Variational difference methods for the solution of elliptic differential equations (in Russian) Erevan 1979
Thomée, V.: Galerkin finite element methods for parabolic problems. Lect. Notes Math. 1054. Berlin, Heidelberg, New York: Springer 1984
Wendland, W.L.: Elliptic systems in the plane. London, San Francisco, Melbourne: Pitman 1979
Yserentant, H.: The convergence of multi-level methods for solving finite element equations in the presence of singularities (To appear in Math. Comput.)
Yserentant, H.: On the convergence of multi-level methods for strongly nonuniform families of grids and any number of smoothing steps per level. Computing30, 305–313 (1983)
Yserentant, H.: Über die Maximumnormkonvergenz der Methode der finiten Elemente bei geringsten Regularitätsvoraussetzungen. Z. Angew. Math. Mech.65, 91–100 (1985)
Zienciewicz, O.C., Kelly, D.W., Gago, J., Babuška, I.: Hierarchical finite element approaches, error estimates and adaptive refinement. In: The mathematics of finite elements and applications IV. (J.R. Whiteman ed.) London: Academic Press 1982
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Yserentant, H. On the multi-level splitting of finite element spaces. Numer. Math. 49, 379–412 (1986). https://doi.org/10.1007/BF01389538
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01389538