Generalized tractability for multivariate problems. I: Linear tensor product problems and linear information (Q883336): Difference between revisions

The main subject of the present paper is studying generalized tractability for multivariate problems defined as a linear tensor product of problems. The tractability is the study of the difficulty of approximating operators defined on spaces of \(d\)-variate functions with the emphasis on the large dimension \(d.\) Here \(n(\varepsilon, d)\) denotes the minimal number of information evaluations needed to reduce the initial error by a factor of \(\varepsilon \in (0,1].\) The essence of the tractability study is to find necessary and sufficient conditions on spaces of functions and operators for which \(n(\varepsilon, d)\) does not depend exponentially on \(\varepsilon^{-1}\) and on \(d.\) In the introduction a broad survey of papers concerning tractability is given. The notion a tractability function is defined. In section 2 some preliminary notions and statements are given. The concept of the multivariate problem is given. An algorithm \(A_{n,d}\) that uses finitely many information evaluations is proposed. The notion of the worst-case error of the algorithm \(A_{n,d}\) is defined. The notions generalized tractability, \((T, \Omega)\)-tractability, strong \((T, \Omega)\)-tractability and the corresponding parameters exponent \(t^{\text{tra}}\) and \(t^{\text{str}}\) are defined. Different cases of the tractability functions are considered. In section 3 the elements of the multivariate linear tensor product problems are given. The main topic here is the choice of the eigenvalues. Eigenvalues with exponential, polynomial and logarithmic rates of convergence are considered. In section 4 necessary and sufficient conditions for restricted tractability are provided. In Theorem 4.1 where \(d^{*} = 0\) and Theorem 4.2 where \(d^{*} \geq 1,\) necessary and sufficient conditions for multivariate problems \(S\) to be \((T, \Omega^{\text{res}})\)-tractable and strongly \((T, \Omega^{\text{res}})\)-tractable in the class of linear information are presented. The values of the exponents of restricted tractability and strong restricted tractability are given. In the next Theorems 4.3, 4.4 and 4.5 again the necessary and sufficient conditions for multivariate problems \(S\) to be \((T, \Omega^{\text{res}})\)-tractable and strongly \((T, \Omega^{\text{res}})\)-tractable, with additional conditions on the exponential rate, the polynomial rate and logarithmic rate of convergence of eigenvalues are proposed. Theorems 4.7 and 4.8 combine the results of the previous theorems and present statements on the tractability of \(S\) for \(\Omega^{\text{res}}(\varepsilon_{0}, d^{*}).\) In these theorems the strong tractability of \(S\) means that \(S\) is strongly \((T, \Omega^{\text{res}}(\varepsilon_{0}, d^{*}))\)-tractable in the class of linear information, and the tractability of \(S\) means that \(S\) is \((T, \Omega^{\text{res}}(\varepsilon_{0}, d^{*}))\)-tractable in the class of linear information.