The Computational Complexity of Differential and Integral Equations: An Information-based ApproachComplexity theory has become an increasingly important theme in mathematical research. This book deals with an approximate solution of differential or integral equations by algorithms using incomplete information. This situation often arises for equations of the form Lu = f where f is some function defined on a domain and L is a differential operator. We do not have complete information about f. For instance, we might only know its value at a finite number of points in the domain, or the values of its inner products with a finite set of known functions. Consequently the best that can be hoped for is to solve the equation to within a given accuracy at minimal cost or complexity. In this book, the theory of the complexity of the solution to differential and integral equations is developed. The relationship between the worst case setting and other (sometimes more tractable) related settings, such as the average case, probabilistic, asymptotic, and randomized settings, is also discussed. The author determines the inherent complexity of the problem and finds optimal algorithms (in the sense of having minimal cost). Furthermore, he studies to what extent standard algorithms (such as finite element methods for elliptic problems) are optimal. This approach is discussed in depth in the context of two-point boundary value problems, linear elliptic partial differential equations, integral equations, ordinary differential equations, and ill-posed problems. As a result, this volume should appeal to mathematicians and numerical analysts working on the approximate solution of differential and integral equations, as well as to complexity theorists addressing related questions in this area. |
Contents
a twopoint boundary value problem | 2 |
Elliptic partial differential equations in the worst case setting | 5 |
Complexity in the asymptotic and randomized settings | 293 |
Copyright | |
3 other sections not shown
Common terms and phrases
absolute error criterion adaptive information approximation arbitrary linear information Astd average case setting Banach space bilinear form boundary value problem Chapter comp(ɛ define denote e-approximation elliptic systems exists ɛ-complexity F₁ FEM of degree FEMQ finite element method follows Fredholm problem Galerkin method Gaussian measure H¹(I H¹(N Hence Hilbert space ill-posed problems inequality information of cardinality information-based complexity L₂ L₂(n Lemma linear functional linear problems lower bound minimal error algorithm n,k n,k n₁ Na,k nonadaptive information norm Notes and Remarks nth minimal error nth minimal radius nth optimal information optimal complexity algorithm optimal error algorithm orthonormal basis pavg(n Poisson problem positive constant problem elements quadrature residual error criterion seminormed Sn,k Sobolev spaces solution operator spline algorithm standard information subspace Suppose worst case setting