Abstract Generated abstract
The paper studies error estimates for approximating integrals over the infinite-dimensional unit cube by finite averages at prescribed nodes. Using Haar series expansions, it refines finite-dimensional discrepancy estimates and extends them to function classes defined by bounds on Haar coefficients or Lipschitz-type mixed differences. A general theorem is proved for grids whose projected discrepancies admit multiplicative bounds, yielding error estimates for infinite-dimensional integration when the defining constants of the function class decrease sufficiently fast. The results are applied to generalized Halton sequences and to a newly constructed generalized LP_tau sequence, with the latter giving the optimal order \(N^{-1/p}\) on the classes \(S_p\) and near-optimal estimates for the classes \(H_\alpha\).
Full Text
UDC 518.12+517.392
MATHEMATICS
I. M. SOBOL’
APPLICATION OF HAAR SERIES TO ERROR ESTIMATION IN THE COMPUTATION OF INFINITE-DIMENSIONAL INTEGRALS
(Presented by Academician A. N. Tikhonov on 24 IX 1966)
We estimate the error of the approximation
\[ \int_{K_\infty} f(X)\,dX \approx \frac{1}{N}\sum_{\nu=1}^{N} f(X_\nu), \tag{*} \]
where \(K_\infty\) is the infinite-dimensional unit cube; \(X=(x_1,x_2,\ldots,x_n,\ldots)\) is a point of this cube. The measure on \(K_\infty\) is defined by means of the infinite product of Lebesgue measures \((dX=dx_1dx_2\ldots dx_n\ldots)\).
In (1) a sequence of points \(\{X_\nu^*\}\) was constructed, called a generalized Halton sequence, whose points can be used as nodes in \((*)\), and an error estimate for such an approximation was obtained for certain classes of functions.
In § 2 of the present paper the error of the approximation \((*)\) is estimated for broader classes of functions \(S_p\) and \(\bar H_\alpha\) (the classes \(H_\alpha\) are analogues of the Lipschitz classes \(\operatorname{Lip}\alpha\), \(0<\alpha\le 1\)). A new sequence of points \(\{X_\nu^{**}\}\), called a generalized \(ЛП_\tau\)-sequence, is constructed, for which estimates are obtained that are somewhat better than for \(\{X_\nu^*\}\). On the classes \(S_p\) the order of these estimates turns out to be the best possible. The concept of a grid \(\{X_1,\ldots,X_N\}\) with a multiplicative estimate of nonuniformity is introduced. For such grids an estimate of the approximation \((*)\) is obtained in general form.
The paper uses the method of Haar series, which made it possible to obtain error estimates on the classes \(S_p\) and \(H_\alpha\) in the \(n\)-dimensional case \((^{2-4})\). However, in order to be able to pass to the limit as \(n\to\infty\), it was necessary to improve these estimates somewhat. This is done in § 1.
In what follows, the symbol \(K_{i_1\ldots i_s}\) denotes the \(s\)-dimensional face of the cube \(K_\infty\) on which \(x_{i_1},\ldots,x_{i_s}\) range from 0 to 1, while all the remaining \(x_i\equiv 1\).
§ 1. The case of \(n\) variables.
1.1. Expansion of a function in “different-dimensional” terms.
Consider a function \(f(P)\), where \(P=(x_1,\ldots,x_n)\), defined in the \(n\)-dimensional unit cube \(K\equiv K_{12\ldots n}\). Write its expansion in the Fourier–Haar series, explicitly separating the first function of the Haar system \(\chi_1(x)\equiv 1\). Let
\[ C_{k_1\ldots k_s}^{i_1\ldots i_s} = \int_K f(P)\chi_{k_1}(x_{i_1})\cdots \chi_{k_s}(x_{i_s})\,dP, \]
\[
(dP=dx_1\cdots dx_n),
\]
where \(1\le i_1<i_2<\cdots<i_s\le n,\ 1\le s\le n\). Then
\[ f(P)=c_0+\sum_{k_1,\ldots,k_s}^{\wedge}\sum C_{k_1\ldots k_s}^{i_1\ldots i_s} \chi_{k_1}(x_{i_1})\cdots \chi_{k_s}(x_{i_s}), \tag{1} \]
where the symbol \(\hat{\sum}\) denotes summation over all different \(s\)-index quantities for \(s=1,2,\ldots,n\):
\[ \hat{\sum} T_{i_1\ldots i_s} = \sum_{i_1=1}^{n} T_{i_1} + \sum_{1\leq i_1<i_2\leq n}\sum T_{i_1 i_2} +\cdots+ T_{12\ldots n}. \]
In (1), as throughout what follows, the indices \(k_\sigma\) vary from \(2\) to \(\infty\). Each of the sums following the sign \(\hat{\sum}\) depends only on the \(s\) variables \(x_{i_1},\ldots,x_{i_s}\).
1.2. Estimation of the integration error. Choose an integration net \(\Sigma\), consisting of arbitrary points \(P_1,\ldots,P_N\) of the cube \(K\), and estimate the error
\[ \delta(f;\Sigma)=\frac{1}{N}\sum_{\nu=1}^{N} f(P_\nu)-\int_K f(P)\,dP . \tag{2} \]
Suppose that the series (1) converges uniformly, and substitute it into (2). After transformations entirely analogous to the transformations of Sec. 1 from \((^3)\), we obtain the estimate
\[ |\delta(f;\Sigma)| \leq \frac{1}{N}\hat{\sum} A_p^{i_1\ldots i_s}(f)\,\Phi_q^{i_1\ldots i_s}(\Sigma), \tag{3} \]
in which \(1/p+1/q=1\);
\[ A_p^{i_1\ldots i_s}(f) = \sum_m 2^{(m_1-1)/2+\cdots+(m_s-1)/2} \left\{\sum_j |C_k^i|^p\right\}^{1/p}, \]
and \(\Phi_q^{i_1\ldots i_s}(\Sigma)\) is the \(s\)-dimensional discrepancy of the projections of the points \(P_1,\ldots,P_N\) onto \(K_{i_1\ldots i_s}\) \((^3)\). Here
\(i=(i_1,\ldots,i_s)\), \(k=(k_1,\ldots,k_s)\), \(m=(m_1,\ldots,m_s)\),
\(j=(j_1,\ldots,j_s)\);
\(1\leq m_\sigma<\infty\), \(1\leq j_\sigma\leq 2^{m_\sigma-1}\).
In \((^3)\) the norm \(\|f\|_p=\hat{\sum} A_p^{i_1\ldots i_s}(f)\) was used. Therefore the estimate (3) was coarsened and written in the form
\[ |\delta(f;\Sigma)| \leq N^{-1}\|f\|_p\,\varphi_q(\Sigma), \quad \text{where } \varphi_q(\Sigma)=\max \Phi_q^{i_1\ldots i_s}(\Sigma). \]
Below only the simplest quantities \(\Phi_\infty^{i_1\ldots i_s}(\Sigma)\) are used; we shall call them the discrepancies of the net \(\Sigma\). It is easy to prove that for any net
\[ \Phi_q^{i_1\ldots i_s}(\Sigma) \leq N^{1/q}\Phi_\infty^{i_1\ldots i_s}(\Sigma). \tag{4} \]
1.3. Classes of functions \(S_p\) and \(H_\alpha\).
Definition. A function \(f(x_1,\ldots,x_n)\) belongs to the class \(S_p(L_{i_1\ldots i_s})\), \(1\leq p<\infty\), if for any \(1\leq i_1<i_2<\cdots<i_s\leq n\) and \(1\leq s\leq n\)
\[ A_p^{i_1\ldots i_s}(f) \leq L_{i_1\ldots i_s}. \tag{5} \]
The constants \(\{L_{i_1\ldots i_s}\}\) are called the defining constants of the class.
As in \((^2,^3)\), it is proved that if \(f\in S_p\), then the series (1) converges uniformly in \(K\), and estimate (3) with \(L_{i_1\ldots i_s}\) in place of \(A_p^{i_1\ldots i_s}(f)\) is an exact estimate on \(S_p\) (for any prescribed net \(\Sigma\)).
Definition. A function \(f(x_1,\ldots,x_n)\) belongs to the class \(H_\alpha(L_{i_1\ldots i_s})\), \(0<\alpha\leq 1\), if for any \(1\leq i_1<i_2<\cdots<i_s\leq n\) and \(1\leq\)
\(\leqslant s \leqslant n\) in the cube \(K\)
\[ \left|\Delta_{\xi_{i_1}}\cdots \Delta_{\xi_{i_s}} f(P)\right| \leqslant L_{i_1\ldots i_s}\left(\frac{\alpha+1}{2}\right)^s \left|\xi_{i_1}\cdots \xi_{i_s}\right|^\alpha . \tag{6} \]
Just as in \((^2)\), it is proved that if \(f \in H_\alpha(L_{i_1\ldots i_s})\) and \(\alpha p>1\), then
\[ A_p^{i_1\ldots i_s}(f) \leqslant L_{i_1\ldots i_s}\left(2^{1+\alpha}-2^{1+1/p}\right)^{-s}. \tag{7} \]
From (3), (4), and (7) one can obtain an estimate of \(|\delta(f;\Sigma)|\) on the classes \(H_\alpha\), quite analogous to estimate (8) from \((^3)\).
§ 2. The case of infinitely many variables
2.1. Classes of functions
The classes \(S_p(L_{i_1\ldots i_s})\) and \(H_\alpha(L_{i_1\ldots i_s})\) are defined in the same way as in the \(n\)-dimensional case: the corresponding inequalities (5) or (6) must be satisfied in \(K_\infty\) for arbitrary \(1\leqslant i_1<i_2<\cdots<i_s\), \(1\leqslant s<\infty\). In addition, it is assumed that at each point
\(f(X)=\lim_{n\to\infty} f(x_1,\ldots,x_n,1,1,1,\ldots)\), and passage to the limit is possible:
\[ \int_{K_\infty} f(X)\,dX = \lim_{n\to\infty}\int_K f(x_1,\ldots,x_n,1,1,\ldots)\,dP . \]
2.2. Estimate of the error of integration
Choose a grid consisting of points \(X_1,\ldots,X_N\) in \(K_\infty\). The projections of these points onto \(K_{i_1\ldots i_s}\) form an \(s\)-dimensional grid, whose discrepancy shall be denoted by \(\Phi_\infty^{i_1,\ldots,i_s}\).
Suppose that there exist constants \(B\) and \(\{h_i\}\), \(1\leqslant i<\infty\), such that for any \(i_1<\cdots<i_s\)
\[ \Phi_\infty^{i_1\ldots i_s}\leqslant Bh_{i_1}\cdots h_{i_s}. \tag{8} \]
In this case we shall say that the grid admits a multiplicative estimate of discrepancies.
Theorem. For a grid \(X_1,\ldots,X_N\) admitting the multiplicative estimate of discrepancies (8), on classes of functions \(S_p\) and \(H_\alpha\) whose defining constants decrease uniformly with respect to \(\{h_i\}\), the estimate holds
\[ \left| \frac{1}{N}\sum_{\nu=1}^{N} f(X_\nu) - \int_{K_\infty} f(X)\,dX \right| \leqslant ABN^{-1/p}\exp\sum_{i=1}^{\infty} v_i, \tag{9} \]
where \(v_i=\varepsilon_i h_i\) in the case of the class \(S_p\), while in the case of the class \(H_\alpha\) the parameter \(p>1/\alpha\) and
\[
v_i=\varepsilon_i h_i(2^{1+\alpha}-2^{1+1/p})^{-1}.
\]
Proof scheme. Use inequality (3) for the function \(f(x_1,\ldots,x_n,1,1,\ldots)\), then inequalities (5) or (7), (4), and (8). The right-hand side is estimated by means of Lemma 2 from \((^1)\). Then pass to the limit as \(n\to\infty\).
2.3. Use of the generalized Halton sequence
As the grid \(X_1,\ldots,X_N\) we choose the points \(X_1^*,\ldots,X_N^*\). Since the projections of the points \(\{X_\nu^*\}\) onto \(K_{i_1\ldots i_s}\) form an \(s\)-dimensional Halton sequence, it is easy to show (cf. \((^1,^4)\)) that estimate (8) will be satisfied with \(B=1\), \(h_i=\bar{\beta}_i\ln N+\bar{\gamma}_i\). The asymptotics of the coefficients as \(i\to\infty\) is known: \(\bar{\beta}_i\sim 4i\), \(\bar{\gamma}_i\sim 8i\ln i\). Hence, for the applicability of the preceding theorem it is sufficient to require that the defining constants of the class decrease uniformly with respect to \(\{i\ln i\}\).
Choose an arbitrary \(\varepsilon>0\). One can choose \(A\) and \(\{\varepsilon_i\}\) so that \(\sum \varepsilon_i\bar{\beta}_i=\varepsilon\); then the order of estimate (9) on the classes \(S_p\) will be \(N^{-1/p+\varepsilon}\).
\[ \text{* According to }(^1),\ \text{this means that }\ L_{i_1\ldots i_s}\leqslant A\varepsilon_{i_1}\cdots\varepsilon_{i_s} \ \text{and, in addition, the series }\ \sum_{1}^{\infty}\varepsilon_i h_i \ \text{converges.} \]
If \(p\) is fixed so that \(0<\alpha-1/p<\varepsilon\), and then \(A\) and \(\{\varepsilon_i\}\) are chosen so that
\(\sum \varepsilon_i\beta_i=(2^{1+\alpha}-2^{1+1/p})(\varepsilon-\alpha+1/p)\), then the order of the estimate (9) on the classes \(H_\alpha\) will be \(N^{-\alpha+\varepsilon}\).
We note that the orders of the estimates on the classes \(S_p\) and \(H_\alpha\), even in the \(n\)-dimensional case, cannot be better than \(N^{-1/p}\) and, respectively, \(N^{-\alpha}\).
2.4. Use of a generalized \(\mathrm{LP}_\tau\)-sequence
Definition. By a generalized \(\mathrm{LP}_\tau\)-sequence we shall mean a sequence of points \(\{X_\nu^{**}\}\) with coordinates
\[ X_{\nu+1}^{**}=\bigl(p^{(1)}(\nu),\ p^{(2)}(\nu),\ldots,\ p^{(n)}(\nu),\ldots\bigr), \]
where \(\{p^{(n)}(\nu)\}\) is a sequence of type \(DR\) corresponding to the \(n\)-th monocyclic operator (5) (the operators are numbered so that their orders \(\bar m_n\) do not decrease).
As the grid \(X_1,\ldots,X_N\) we choose the points \(X_1^{**},\ldots,X_N^{**}\). Since the projections of the points \(\{X_\nu^{**}\}\) onto \(K_{i_1,\ldots,i_s}\) form an \(s\)-dimensional \(\mathrm{LP}_\tau\)-sequence, it follows from (5) that estimate (8) holds with \(B=1/2\), \(h_i=2^{\bar m_i}\), and also the asymptotic estimate for \(\bar m_i\) as \(i\to\infty\),
\[ \bar m_i \leq \log_2 i+\log_2\bigl(\log_2 i\,\log_2\log_2 i\bigr)+O(1). \tag{10} \]
Thus, \(h_i\leq C i\ln i\ln\ln i\), and for the applicability of our theorem it is sufficient to require that the defining constants of the class decrease uniformly with respect to \(\{i\ln i\ln\ln i\}\).
The order of the estimate (9) on the classes \(S_p\) turns out to be \(N^{-1/p}\). This is the best possible order.
Let us now consider the classes \(H_\alpha\). Let \(0<\varkappa<\varepsilon\). Fix \(1/p=\alpha-\varkappa/\sqrt{\ln N}\). After a suitable choice of \(A\) and \(\{\varepsilon_i\}\), the order of the estimate (9) will be equal to \(N^{-\alpha+\varepsilon/\sqrt{\ln N}}\).
Remark. In this subsection we had to require a more rapid decrease of the defining constants in comparison with Sec. 2.3. Apparently this is caused by the crudeness of estimate (10).
Received
20 IX 1966
References
- I. M. Sobol’, Zhurn. vychislit. matem. i matem. fiz., 1, No. 5, 917 (1961).
- I. M. Sobol’, DAN, 132, No. 4, 773 (1960).
- I. M. Sobol’, DAN, 132, No. 5, 1041 (1960).
- I. M. Sobol’, DAN, 139, No. 4, 821 (1961).
- I. M. Sobol’, UMN, 21, No. 5, 271 (1966).