Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)


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 | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 68Q25, 65D05

Retrieve articles in all journals with MSC: 68Q25, 65D05

Additional Information

PII: S 0025-5718(1984)0725985-4
Article copyright: © Copyright 1984 American Mathematical Society