2005 Reports

Tractability of Quasilinear Problems. I: General Results

Werschulz, Arthur G.; Wozniakowski, Henryk

The tractability of multivariate problems has usually been studied only for the approximation of linear operators. In this paper we study the tractability of quasilinear multivariate problems. That is, we wish to approximate nonlinear operators Sd (·, ·) that depend linearly on the first argument and satisfy a Lipschitz condition with respect to both arguments. Here, both arguments are functions of d variables. Many computational problems of practical importance have this form. Examples include the solution of specific Dirichlet, Neumann, and Schrödinger problems. We show, under appropriate assumptions, ¨ that quasilinear problems, whose domain spaces are equipped with product or finite-order weights, are tractable or strongly tractable in the worst case setting. This paper is the first part in a series of papers. Here, we present tractability results for quasilinear problems under general assumptions on quasilinear operators and weights. In future papers, we shall verify these assumptions for quasilinear problems such as the solution of specific Dirichlet, Neumann, and Schrödinger problems.