Polynomial-time algorithms for multivariate linear problems with finite-order weights: worst case setting (Q2505651)

The approximation of linear multivariate problems defined over weighted tensor product Hilbert spaces finite-order weights is considered in the article. The problem of representation function of \((d)\) variables by sums of functions of at most \((q*)\) variables is investigated. Here, \((q*)\) is fixed (and presumably small) and \((d)\) may be arbitrary large. A construction of polynomial-time algorithms \((A_{d,\varepsilon })\) for general \((d)\)-variate problem with the number of evaluations bounded roughly by \((\varepsilon^{-p} d^{q*})\) to achieve an error \((\varepsilon)\) in the worst case setting are proved. The bibliography contains 44 sources.