No Curse of Dimensionality for Contraction Fixed Points Even in the Worst Case

We consider the problem of computing approximations to fixed points of quasilinear contraction mappings defined on the space of continuous functions of $d$ variables. Our main emphasis is on large d. Examples of such mappings include the Bellman operator from the theory of dynamic programming. This paper proves that there exist deterministic algorithms for computing approximations to fixed points for some classes of quasilinear contraction mappings which are strongly tractable, i.e., in the worst case the number of function evaluations needed to compute an e-approximation to the solution at any finite number of points in its domain is bounded by C/e^p where both C and p are independent of d. This is done by using relations between the quasilinear contraction problem and the conditional expectation and approximation problems. The conditional expectation problem is equivalent to weighted multivariate integration. This allows us to apply recent proof technique and results on the strong tractability of weighted multivariate integration and approximation to establish strong tractability for the quasilinear fixed point problem. In particular, this holds when the fixed points belong to a Sobolev space for a specific weighted norm.