Does increased regularity lower complexity?
Author: Arthur G. Werschulz
Journal: Math. Comp. 42 (1984), 69-93
MSC: Primary 68Q25; Secondary 65D05
MathSciNet review: 725985
Full-text PDF Free Access
Abstract: Intuitively, the more regular a problem, the easier it should be to solve. Examples drawn from ordinary and partial differential equations, as well as from approximation, support the intuition. Traub and Woźniakowski conjectured that this is always the case. In this paper, we study linear problems. We prove a weak form of the conjecture, and show that this weak form cannot be strengthened. To do this, we consider what happens to the optimal error when regularity is increased. If regularity is measured by a Sobolev norm, increasing the regularity improves the optimal error, which allows us to establish the conjecture in the normed case. On the other hand, if regularity is measured by a Sobolev seminorm, it is no longer true that increasing the regularity improves the optimal error. However, a "shifted" version of this statement holds, which enables us to establish the conjecture in the seminormed case.
-  Ivo Babuška and A. K. Aziz, Survey lectures on the mathematical foundations of the finite element method, The mathematical foundations of the finite element method with applications to partial differential equations (Proc. Sympos., Univ. Maryland, Baltimore, Md., 1972) Academic Press, New York, 1972, pp. 1–359. With the collaboration of G. Fix and R. B. Kellogg. MR 0421106
-  Philippe G. Ciarlet, The finite element method for elliptic problems, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. Studies in Mathematics and its Applications, Vol. 4. MR 0520174
-  Avner Friedman, Foundations of modern analysis, Holt, Rinehart and Winston, Inc., New York-Montreal, Que.-London, 1970. MR 0275100
-  J. Nečas, Les Méthodes Directes en Théorie des Equations Elliptiques, Masson, Paris, 1967.
-  Martin Schechter, Principles of functional analysis, Academic Press, New York-London, 1971. MR 0445263
-  Joe Fred Traub and H. Woźniakowsi, A general theory of optimal algorithms, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. ACM Monograph Series. MR 584446
-  Arthur G. Werschulz, Optimal error properties of finite element methods for second order elliptic Dirichlet problems, Math. Comp. 38 (1982), no. 158, 401–413. MR 645658, https://doi.org/10.1090/S0025-5718-1982-0645658-4
- I. Babuška & A. K. Aziz, "Survey lectures on the mathematical foundations of the finite element method," in The Mathematical Foundations of Finite Element Method with Applications to Partial Differential Equations (A. K. Aziz, ed.), Academic Press, New York, 1972, pp. 3-359. MR 0421106 (54:9111)
- P. G. Ciarlet, The Finite Element Method for Elliptic Problems, Studies in Mathematics and Its Applications, Vol. 4 (J. L. Lions et al., eds.), North-Holland, Amsterdam, 1978. MR 0520174 (58:25001)
- A. Friedman, Foundations of Modern Analysis, Holt, Rinehart, and Winston, New York, 1970. MR 0275100 (43:858)
- J. Nečas, Les Méthodes Directes en Théorie des Equations Elliptiques, Masson, Paris, 1967.
- M. Schechter, Principles of Functional Analysis, Academic Press, New York, 1971. MR 0445263 (56:3607)
- J. F. Traub & H. Woźniakowski, A General Theory of Optimal Algorithms, Academic Press, New York, 1980. MR 584446 (84m:68041)
- A. G. Werschulz, "Optimal-error properties of finite-element methods for second-order elliptic Dirichlet problems," Math. Comp., v. 38, 1982, pp. 401-413. MR 645658 (83d:65300)