The Computational Complexity of Differential and Integral Equations: An Information-Based Approach

Erscheinungsjahr 1991
ISBN: 978-0-19-853589-8
Verlag: OXFORD UNIV PR

Buch, Englisch, 342 Seiten, Format (B × H): 165 mm x 241 mm, Gewicht: 703 g

Reihe: Oxford Mathematical Monographs

This book is concerned with a central question in numerical analysis: the 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. The function f may not be given exactly - we might only know its value at a finite number of points in the domain. Consequently the best that can be
hoped for is to solve the equation to within a given accuracy at minimal cost or complexity.

The author develops the theory of the complexity of the solutions to differential and integral equations and discusses the relationship between the worst-case setting and other (sometimes more tractable) related settings such as the average case, probabilistic, asymptotic, and randomized settings. 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.

Autoren/Hrsg.

Werschulz, Arthur G.

Inhaltsverzeichnis

Introduction; EXAMPLE: A TWO-POINT BOUNDARY VALUE PROBLEM: Introduction; Error, cost, and complexity; A minimal error algorithm; Complexity bounds; Comparison with the finite element method; Standard information; Final remarks; GENERAL FORMULATION: Introduction; Problem formulation; Information; Model of computation; Algorithms, their errors, and their costs; Complexity; Randomized setting; Asymptotic setting; THE WORST CASE SETTING: GENERAL RESULTS: Introduction;
Radius and diameter; Complexity; Linear problems; The residual error criterion; ELLIPTIC PARTIAL DIFFERENTIAL EQUATIONS IN THE WORST CASE SETTING; Introduction; Variational elliptic boundary value problems; Problem formulation; The normed case with arbitrary linear information; The normed case with
standard information; The seminormed case; Can adaption ever help?; OTHER PROBLEMS IN THE WORST CASE SETTING: Introduction; Linear elliptic systems; Fredholm problems of the second kind; Ill-posed problems; Ordinary differential equations; THE AVERAGE CASE SETTING: Introduction; Some basic measure theory; General results for the average case setting; Complexity of shift-invariant problems; Ill-posed problems; The probabilistic setting; COMPLEXITY IN THE ASYMPTOTIC AND RANDOMIZED SETTINGS:

Introduction; Asymptotic setting; Randomized setting; Appendices; Bibliography.