EC-(s, t)-weaktractability of multivariate linear problems in the average case setting

摘要

We study EC-(s, t)-weak tractability of multivariate linear problems in the average case setting. This paper extends earlier work in the worst case setting. The parameters s >= 0 and t >= 0 allow us to study the information complexity n(epsilon, d) of a d-variate problem with respect to different powers of In epsilon(-1), corresponding to the bits of accuracy, and d. We consider the absolute and normalized error criteria. In particular, a multivariate problem is EC-(s, t)-weakly tractable if lim(d+epsilon)-1(->infinity)In n(epsilon, d)/[d(t) + In-s epsilon(-1)] = 0. We deal with general linear problems and linear tensor product problems. We show necessary and sufficient conditions for EC-(s, t)-weak tractability. In the case of general linear problem these conditions are matching. For linear tensor product problems, we also show matching conditions with the exception of some cases where s > 1, in general. (C) 2019 Elsevier Inc. All rights reserved.