Treffer: 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 \Gamma 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 n(ffl; d) needed to compute an "-approximation to the solution of V = \Gamma(V ) at any finite number of points in its domain is bounded by C" \Gammap 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 .