1995 Reports

What Is the Complexity of Solution-Restricted Operator Equations?

Werschulz, Arthur G.

We study the worst case complexity of operator equations Lu = f , where L : G → X is a bounded linear injection, G is a Hilbert space, and X is a normed linear space. Past work on the complexity of such problems has generally assumed that the class F of problem elements f to be the unit ball of X. However, there are many problems for which this choice of F yields unsatisfactory results. Mixed elliptic-hyperbolic problems are one example, the difficulty being that our technical tools are not strong enough to give good complexity bounds. Ill-posed problems are another example, because we know that the complexity of computing finite-error approximations is infinite if F is a ball in X. In this paper, we pursue another idea. Rather than directly restrict the class F of problem elements f, we will consider problems that are solution-restricted, i.e., we restrict the class U of solution elements u. In particular, we assume that U is the unit ball of a Hilbert space W continuously embedded in G. The main idea is that our problem can be reduced to the standard approximation problem of approximating the embedding of W into G. This allows us to characterize optimal information and algorithms for our problem. Then, we consider specific applications. The first application we consider is any problem for which G and W are standard Sobolev Hilbert spaces we call this the standard problem, since it includes many problems of practical interest. We show that finite element information and generalized Galerkin methods are nearly optimal for standard problems. We then look at elliptic boundary-value problems, Fredholm integral equations of the second kind, the Tricomi problem (a mixed hyperbolic-elliptic problem arising in the study of transonic flow), the inverse finite Laplace transform, and the backwards heat equation. (Note that with the exception of the backwards heat equation, all of these are standard problems. Moreover, the inverse finite Laplace transform and the backwards heat equation are ill-posed problems.) We determine the problem complexity and derive nearly optimal algorithms for all these problems.