多元连续问题易处理性的研究始于 1994 年^[20,21],历经近三十年的发展, 越来越多的学者对该问题产生兴趣,现在已经变成非常热门的研究领域^[11⇓-13].对于给定的正整数 $d$, 多元连续问题通常指的是一系列解算子 $S=\{S_{d}:F_d\rightarrow G_{d}\}_{d\in\mathbb{N}}$,其中 $F_{d}$ 是由 $d$ 元函数组成的函数类, $G_{d}$ 是一个 Banach 空间. 事实上,多元逼近和多元积分^[3,6,16,25]是其中两个最重要且被广泛研究的多元连续问题. 通常使用包含所有函数值的标准信息类 $\Lambda^{\text{std}}$ 或者包含所有连续线性泛函的线性信息类 $\Lambda^{\text{all}}$去逼近这些算子.

本文使用的算法其质量通过最坏框架下的逼近误差进行测度, 即函数空间单位球上的最大误差.由于维数 $d$ 通常很大(成百上千), 研究算法的误差时不仅要考虑如何依赖于信息算子的数量,而且要考虑怎样依赖于维数 $d$. 在逼近 $S_{d}$ 时,误差不超过一个常数的 $\varepsilon$ 倍的算法中所需要信息算子的最小数量称为信息复杂度,并记作 $n^{\Lambda}(\varepsilon,d)$, 其中 $\Lambda\in\{\Lambda^{\text{all}},\Lambda^{\text{std}}\}$.如果该常数等于 1, 此时称为绝对误差标准. 如果该常数等于初始误差(没有使用任何信息的误差), 此时称为归一化误差标准.关于信息复杂度的基础知识可以参见文献[18].

根据多项式收敛和指数收敛, 易处理性被分成两种类型.对于代数易处理性^[4,14,15],它刻画的是信息复杂度如何依赖于 $d$ 和 $\varepsilon^{-1}$. 而对于指数收敛易处理性,它刻画的是信息复杂度怎样依赖于 $d$ 和 $(1+\ln\varepsilon^{-1})$.近些年, 指数收敛易处理性已变成多元问题易处理性中最热门的研究领域之一,参见文献[1⇓-3,5⇓⇓-8,10,17,19,22,24,26].

然而, 大多数关于指数收敛易处理性的文献过去主要研究定义在 Hilbert 空间上的多元连续问题,参见文献[1⇓-3,5,10,17,19,24,26].本文我们讨论定义在加权 Korobov 空间中多元 $\mathbb{L}_{\infty}$-逼近问题的指数收敛易处理性.Kritzer等^[7]首次研究了该问题, 得到了 $\Lambda\in\{\Lambda^{\text{all}},\Lambda^{\text{std}}\}$以及绝对和归一化误差标准下的一些指数收敛易处理性结果,包括指数收敛-(强)多项式易处理性, 指数收敛-弱易处理性和指数收敛-$(s,t)$-弱易处理性 ($s=1$, $t>1$).2020 年, 许贵桥^[22]讨论了多元 $\mathbb{L}_{p}$-逼近问题 ($1\leq p\leq \infty$),并得到了一些指数收敛易处理性概念的充分必要条件.

本文继续对上述问题进行讨论,研究之前文献中没有解决的多元 $\mathbb{L}_{\infty}$-逼近问题的指数收敛-拟多项式易处理性和指数收敛-一致弱易处理性.更确切地说, 我们得到了 $\Lambda\in\{\Lambda^{\text{all}},\Lambda^{\text{std}}\}$及绝对误差标准下指数收敛-拟多项式易处理性和 $\Lambda^{\text{std}}$及绝对和归一化误差标准下指数收敛-一致弱易处理性的充分必要条件.

本文主要讨论 $\mathbb{L}_{\infty}$ 范数下具有指数权的 Korobov 空间中多元函数逼近问题,简称为多元 $\mathbb{L}_{\infty}$-逼近.下面首先给出已被大量文献研究过的加权 Korobov 空间的定义,参见文献[2,5,7,22,24].

设 $\textbf{a}=\{a_{k}\}_{k\geq 1}$ 和 $\textbf{b}=\{b_{k}\}_{k\geq 1}$ 为两个正实数权序列.通常假定它们满足

对一个固定正实数 $\omega\in(0,1)$, ${\rm i}=\sqrt{-1}, a, b>0$, 假设解析的 Korobov 核$K_{d,\textbf{a},\textbf{b}}$ 具有如下的乘积形式

其中 $K_{1,a,b}$ 为单变量解析的 Korobov 核,

因此

这里$\omega_{\textbf{h}}=\omega^{\sum_{k=1}^{d}a_{k}|h_{k}|^{b_{k}}},$$\textbf{h}=(h_{1},h_{2},\cdots,h_{d})$, $\textbf{x}=(x_{1},x_{2},\cdots,x_{d})$, $\textbf{y}=(y_{1},y_{2},\cdots,y_{d})$ 且

经常用 $H(K_{d,\textbf{a},\textbf{b}})$ 来表示解析的 Korobov 空间,它是一个具有核(2.3)式的再生核 Hilbert 空间^[2,5].

现在考虑多元 $\mathbb{L}_{\infty}$-逼近问题, 它通过如下的嵌入算子定义

即解算子是 $H(K_{d,\textbf{a},\textbf{b}})$ 到 $L_{\infty}([0,1]^{d})$ 的嵌入映射. 由文献[7]可知这个嵌入是连续的, 而且

通常利用线性非自适应算法^[11,18]来逼近 $\text{APP}_{d,\infty}$,该算法使用的信息算子为线性信息或标准信息. 即函数 $f\in H(K_{d,\textbf{a},\textbf{b}})$ 通过如下的算法

进行逼近, 其中 $L_{k}\in\Lambda^{\text{all}}=H^{*}(K_{d,\textbf{a},\textbf{b}})$ ($H(K_{d,\textbf{a},\textbf{b}})$ 的对偶空间) 或$L_{k}\in\Lambda^{\text{std}} =\{L|L(g)=g(\textbf{x}),\ \forall\ g\in H(K_{d,\textbf{a},\textbf{b}}),\textbf{x}\in[0,1]^{d}\}$, $1\leq k \leq n$, $\alpha_{k}$ 为 $L_{\infty}([0,1]^{d})$ 中的元素. 因为 $H(K_{d,\textbf{a},\textbf{b}})$ 是一个再生核 Hilbert 空间, 所以函数值也是连续线性泛函, 因此 $\Lambda^{\text{std}}\subseteq \Lambda^{\text{all}}$.

由 (2.4) 式的算法 $A_{n,d}$ 进行逼近的最坏框架下的误差定义为

其中 $\|\cdot\|_{H(K_{d,\textbf{a},\textbf{b}})}$ 表示 $H(K_{d,\textbf{a},\textbf{b}})$ 的范数, $\|\cdot\|_{L_{\infty}([0,1]^{d})}$ 表示本性上确界. $n$ 阶最小最坏框架下的误差定义为

这里的下确界选自所有 (2.4) 式的算法. 当 $n=0$ 时, 用 0 逼近函数 $f$, 此时的初始误差为

显然 $d$ 非常大时初始误差可能任意大, 这意味着多元$\mathbb{L}_{\infty}$-逼近问题可能不是规范化的.

对于 $\varepsilon\in(0,1)$, $d\in \mathbb{N}$, $\Lambda\in\{\Lambda^{\text{all}},\Lambda^{\text{std}}\}$, 用 $n^{L_\infty,\Lambda}_{\text{abs}}(\varepsilon,d)$ 表示绝对误差标准下的信息复杂度, 它被定义成使得误差不大于预先给定的精度 $\varepsilon$ 的算法需要的信息算子的最小数量, 即

类似地, 归一化误差标准下的信息复杂度定义为

由于 $e^{L_\infty,\Lambda^{\text{all}}}(n,d)\leq e^{L_\infty,\Lambda^{\text{std}}}(n,d),$ 从而

其中 $X\in\{\text{abs},\text{nor}\}$. 又因为 $e^{L_\infty,\Lambda}(0,d)>1$, 故对任意$\Lambda\in\{\Lambda^{\text{all}},\Lambda^{\text{std}}\}$ 有

下面给出指数收敛易处理性的概念. 对于 $\Lambda\in\{\Lambda^{\text{all}},\Lambda^{\text{std}}\}$ 和$X\in\{\text{abs},\text{nor} \}$, 称多元 $\mathbb{L}_{\infty}$-逼近问题$\text{APP}_{d,\infty}$

·指数收敛-强多项式易处理性 (EC-SPT)当且仅当存在非负实数 $C$ 和 $p$ 使得

对所有 $d\in\mathbb{N},\varepsilon\in(0,1)$ 成立.将满足 (2.7) 式中 $p$ 的下确界称为 EC-SPT 的指数, 记作 $p^{*}$.

·指数收敛-多项式易处理性 (EC-PT)当且仅当存在非负实数 $C$, $p$ 和 $q$ 使得

对所有 $d\in\mathbb{N},\varepsilon\in(0,1)$ 成立.

·指数收敛-拟多项式易处理性 (EC-QPT)当且仅当存在非负实数 $C$ 和 $t$ 使得

对所有 $d\in\mathbb{N},\varepsilon\in(0,1)$ 成立.将满足(2.8)式中 $t$ 的下确界称为 EC-QPT 的指数, 记作 $t^{*}$.

·指数收敛-一致弱易处理性 (EC-UWT) 当且仅当

对所有 $s, t>0$ 成立.

·指数收敛-弱易处理性 (EC-WT) 当且仅当

·指数收敛-$(s,t)$-弱易处理性 (EC-$(s,t)$-WT, $s,t>0$) 当且仅当

容易验证上述指数收敛易处理性概念具有如下的关系:

如果把上述指数收敛易处理性定义中的 $(1+\ln\varepsilon^{-1})$ 或 $\ln\varepsilon^{-1}$换成 $\varepsilon^{-1}$, 相应地得到强多项式易处理性 (SPT)、多项式易处理性 (PT)、 拟多项式易处理性 (QPT)、一致弱易处理性 (UWT)、 弱易处理性 (WT) 和 $(s,t)$-弱易处理性 ($(s,t)$-WT).在本文中, 我们主要研究指数收敛易处理性.

加权 Korobov 空间 $H(K_{d,\textbf{a},\textbf{b}})$ 中的多元 $\mathbb{L}_{2}$-逼近问题已经被广泛研究,参见文献 [2, 5, 19, 24, 26]. 该问题

是由 $H(K_{d,\textbf{a},\textbf{b}})$ 到 $L_{2}([0,1]^{d})$ 的嵌入逼近.对于多元 $\mathbb{L}_{2}$-逼近问题, 我们仍然只需使用线性算法

其中 $L_{k}\in\Lambda^{\text{all}}=H^{*}(K_{d,\textbf{a},\textbf{b}})$ 或$L_{k}\in\Lambda^{\text{std}}=\{L|L(g)=g(\textbf{x}), \forall \ g\in H(K_{d,\textbf{a},\textbf{b}}),\textbf{x}\in[0,1]^{d}\}$,$1\leq k \leq n$, $\alpha_{k}$ 为 $L_{2}([0,1]^{d})$ 中的元素.

同 $\mathbb{L}_{\infty}$ 情形类似, 算法 $A_{n,d}$ 在最坏框架下的误差定义为

且 $n$ 阶最小最坏框架误差定义为

这里的下确界选自所有线性算法 $A_{n,d}$. 当 $n=0$ 时, 文献[2] 已得到初始误差

因此, 多元 $\mathbb{L}_{2}$-逼近问题的绝对误差和归一化误差标准没有区别.

对于 $\varepsilon\in(0,1)$, $d\in \mathbb{N}$, $\Lambda\in\{\Lambda^{\text{all}},\Lambda^{\text{std}}\}$,多元 $\mathbb{L}_{2}$-逼近的信息复杂度在绝对和归一化误差标准下的定义为

由文献[7]知绝对误差标准下多元 $\mathbb{L}_{2}$-逼近的难度不比多元$\mathbb{L}_{\infty}$-逼近难, 即对于$\Lambda\in\{\Lambda^{\text{all}},\Lambda^{\text{std}}\}$ 有

多元 $\mathbb{L}_{2}$-逼近问题的指数收敛易处理性概念 EC-SPT, EC-PT, EC-QPT, EC-UWT, EC-WT 和 EC-$(s,t)$-WT与多元 $\mathbb{L}_{\infty}$-逼近的类似, 只需要把定义中的 $n^{L_\infty,\Lambda}_{X}(\varepsilon,d)$ 替换成$n^{L_2,\Lambda}(\varepsilon,d)$ 即可. 关于 $H(K_{d,\textbf{a},\textbf{b}})$ 中的多元$\mathbb{L}_{2}$-逼近指数收敛易处理性结果已在文献 [2,5,19,24] 中得到研究.

注意到对于线性信息类 $\Lambda^{\text{all}}$, 其多元 $\mathbb{L}_{2}$-逼近和$\mathbb{L}_{\infty}$-逼近问题可以通过算子 $W_{d}$ 的特征值得到很好地刻画, 其中$W_{d}=\text{APP}_{d,2}^{*} \text{APP}_{d,2}:H(K_{d,\textbf{a},\textbf{b}})\longrightarrow H(K_{d,\textbf{a},\textbf{b}})$,

多元 $\mathbb{L}_{2}$-逼近的刻画结果参见文献[11,18],多元 $\mathbb{L}_{\infty}$-逼近的刻画结果已在文献[9] 中得到讨论.

事实上, 对于 $\textbf{h}\in \mathbb{Z} ^{d}$, 函数 $e_{\textbf{h}}$ 定义为

此时, $\{e_{\textbf{h}}\}_{\textbf{h}\in \mathbb{Z} ^{d}}$ 就是 Korobov 空间$H(K_{d,\textbf{a},\textbf{b}})$ 的完备正交基. 容易证明算子 $W_{d}$ 的特征对为$(\omega_{\textbf{h}},e_{\textbf{h}})$, 即

算子 $W_d$ 非增重排后的特征值记为 $\{\lambda_{d,k}\}_{k\in \mathbb{N} }$, 即

显然, $\{\lambda_{d,k}\}_{k\in \mathbb{N} }=\{\omega_{\textbf{h}}\}_{\textbf{h}\in \mathbb{Z} ^{d}}$ 且 $\lambda_{d,1}=1$.从而

设

则 $X\in\{\text{abs},\text{nor} \}$ 时,

另外, 对于多元 $\mathbb{L}_{2}$-逼近和 $\mathbb{L}_{\infty}$-逼近, 其 $n$ 阶最小误差都由同一个算法

获得, 这里 $\eta_{d,k}$ 表示相应于特征值 $\lambda_{d,k}$ 的特征函数^[9].

对于 $\Lambda\in\{\Lambda^{\text{all}},\Lambda^{\text{std}}\}$ 及绝对和归一化误差标准,文献[7] 最早开始研究最坏框架下定义在 $H(K_{d,\textbf{a},\textbf{b}})$中的多元 $\mathbb{L}_{\infty}$-逼近问题的指数收敛易处理性. 该文献主要研究EC-SPT, EC-PT 和 EC-$(1,t)$-WT($t\geq 1$), 最终通过权参数得到匹配的充分必要条件.最近, 文献[22] 进一步研究了多元 $\mathbb{L}_{p}$-逼近问题的指数收敛易处理性,其中 $1\leq p\leq \infty$. 对于线性信息类 $\Lambda^{\text{all}}$ 及绝对和归一化误差标准,他们得到了 EC-SPT, EC-PT, EC-UWT 和 EC-WT 成立的条件. 下面给出多元$\mathbb{L}_{\infty}$-逼近问题的一些指数收敛易处理性结果.

对于 $\Lambda\in\{\Lambda^{\text{all}},\Lambda^{\text{std}}\}$及绝对和归一化误差标准^[7],

·EC-SPT 成立当且仅当 EC-PT 成立当且仅当

·EC-$(1,t)$-WT($t\geq 1$) 成立当且仅当

对于 $\Lambda^{\text{all}}$及绝对和归一化误差标准^[22]

·EC-UWT 成立当且仅当

对于 EC-SPT, EC-PT 和 EC-$(1,t)$-WT($t\geq 1$),容易发现它们的结果在 $\Lambda^{\text{all}}$ 和$\Lambda^{\text{std}}$ 之间以及绝对误差和归一化误差标准之间并没有什么区别.但对于 EC-UWT, 并不知道其在 $\Lambda^{\text{all}}$ 和 $\Lambda^{\text{std}}$下的条件是否一致. 本文中, 我们对该公开的问题给出肯定的回答. 另外, 本文也研究EC-QPT 并得到 $\Lambda\in\{\Lambda^{\text{all}},\Lambda^{\text{std}}\}$和绝对误差标准下的充分必要条件, 该条件是否也对归一化误差标准成立仍然没有得到解决.我们采用类似文献[7] 中的构造性算法和方法得到 EC-QPT 和 EC-UWT的充分必要条件, 算法使用的采样点是具有不同网格尺寸的正则网格.这些正则网格之前在文献 [2,3] 中被用来解决多元逼近和积分问题.

定理4.1 考虑定义在 Korobov 空间 $H(K_{d,\textbf{a},\textbf{b}})$ 中的多元$\mathbb{L}_{\infty}$-逼近问题, 其中序列 $\textbf{a}$ 和 $\textbf{b}$满足 (2.1) 式.对于 $\Lambda\in\{\Lambda^{\text{all}},\Lambda^{\text{std}}\}$ 和绝对误差标准, EC-QPT 成立当且仅当

如果上式成立, 则 EC-QPT 的指数满足

其中 $C$ 为大于零的常数. 特别地, 若 $\alpha_{*}=\infty$ 则 $t^{*}=B^{*}$.

定理4.2 考虑定义在 Korobov 空间 $H(K_{d,\textbf{a},\textbf{b}})$ 中的多元$\mathbb{L}_{\infty}$-逼近问题, 其中序列 $\textbf{a}$ 和 $\textbf{b}$满足(2.1) 式.对于 $\Lambda^{\text{std}}$ 和绝对误差或归一化误差标准, EC-UWT 成立当且仅当

对于固定的 $\omega\in(0,1)$, $K_{d,\textbf{a},\textbf{b}}$ 为 (2.3)式定义的解析 Korobov 核, 且 $\textbf{a},\textbf{b}$ 满足 (2.1) 式.由 (2.2) 式知再生核 Hilbert 空间 $H(K_{d,\textbf{a},\textbf{b}})$为单变量再生核 Hilbert 空间 $H(K_{1,a_{j},b_{j}})$ 的张量积, 其中 $K_{1,a_{j},b_{j}}$, $j=1,\cdots,d$为其再生核, 即

在证明我们的结果之前, 首先介绍关于标准信息类 $\Lambda^{\text{std}}$ 的一些预备知识.文献 [23] 提供了一种基于函数值的特殊线性逼近算法, 利用该算法可得到误差界.对于给定的点集 $P=\{\textbf{x}_{1}, \cdots,\textbf{x}_{n} \}$ 和函数值$\{f(\textbf{x}_{1}), \cdots,f(\textbf{x}_{n}) \}$, 样条 $\sigma$ 定义为

于是可以利用样条 $\sigma(f;P)$ 在 $\mathbb{L}_\infty$ 范数下逼近 $f\in H(K_{d,\textbf{a},\textbf{b}})$.而且, 该逼近算法使用的是 $d$ 维网格 $g_{n,d}$,此种正则网格在文献 [2,3,6,7] 中已被广泛讨论和研究.下面给出它们的定义.

给定 $d\in \mathbb{N}$, 具有网格尺寸 $m_{1},\cdots,m_{d}\in \mathbb{N}$ 的正则网格 $g_{n,d}$ 定义为如下的点集

其中 $n=\prod_{j=1}^{d} m_{j}$ 为 $g_{n,d}$ 的基数. 用 $g_{n,d}^{\bot}$ 表示 $g_{n,d}$ 的对偶集合, 即

对于正则网格 $g_{n,d}$, 集合 $\mathbb{Z} ^{d}$ 可以表示成 $g_{n,d}^{\bot}$ 和集合

的直和, 即

给定取自 $g_{n,d}$ 的点 $\textbf{x}_{1}, \cdots,\textbf{x}_{n}$,由文献 [23] 知样条 $\sigma(f;P)$ 可以由基函数$\phi_{k}, k=1,2,\cdots,n$ 表示, 这里 $\phi_{k}$ 为$K_{d,\textbf{a},\textbf{b}}(\cdot,\textbf{x}_{r})$ 的线性组合. 更精确地说

其中 $\{\xi_{r,k}\}$ 是通过由 Kronecker delta 函数 $\delta$ 表示的一个条件给出, 即

按照文献 [23,3.1 节] 类似的步骤, 文献 [7] 利用上面的正则网格最终得到如下估计

对于指数易处理性概念 EC-QPT, 容易验证当 $d\in \mathbb{N}$, $\varepsilon\in(0,1)$ 时,

$$\begin{aligned} \exp\left(t(1+\ln d)(1+\ln(1+\ln\varepsilon^{-1}))\right)=(ed)^{t(1+\ln(1+\ln\varepsilon^{-1}))} =(e(1+\ln\varepsilon^{-1}))^{t(1+\ln d)}, \end{aligned}$$

其中 $e=\exp{(1)}$. 在下面的证明过程中将会用到上面的等价式子.

证 首先证明由 EC-QPT 成立得到条件 (4.1).由关系式 (2.5) 和 (3.1) 知只需考虑多元$\mathbb{L}_{2}$-逼近问题和线性信息类 $\Lambda^{\text{all}}$.因此由文献 [5] 得 (4.1) 式成立且 EC-QPT 的指数 $t^{*}$满足

下面证明条件 (4.1) 可以推出绝对误差标准下多元$\mathbb{L}_{\infty}$-逼近问题的 EC-QPT 成立.由关系式 (2.5) 知只需考虑标准信息类 $\Lambda^{\text{std}}$. 为了得到想要的结果,需要使用 (5.1) 式给出的算法 $\sigma(\cdot; g_{n,d})$, 其中采样点 $\{\textbf{x}_{k}\}_{k=1}^{n}$来自于正则网格 $g_{n,d}$. 而且, $g_{n,d}$ 的网格尺寸 $m_{1}, m_{2},\cdots,m_{d}$ 为

这里 $M>1$, $\beta\in(0,1)$,

由 (6.1) 式知 $m_{j}\geq1$ 且 $m_{j}$ 总为奇数. 另外, 容易证得如果 $a_{j}\geq(x(M))^{1/\beta}$, 则 $m_{j}=1$. 因为 $\alpha_{*}>0$, 这意味着对于每个 $\tau\in (0,\alpha_{*})$, 总存在正整数 $N^{*}_{\tau}$ 使得 $j\geq N^{*}_{\tau}$ 时,

对于 $\ln x(M)\geq\beta\tau$, 即 $M\geq \omega^{-e^{\beta\tau}}$, 由 (6.2) 式知, 若

则 $m_{j}=1$, 其中 $J(M)$ 为非线性方程

的解. 因为 $y\geq 1$ 时 $y/(1+\ln y)$ 是递增的, 故该方程的解是唯一的.而且由文献 [5]可知 $M\rightarrow\infty$ 时,

由 (5.2) 式知

类似文献 [命题 1]的证明, 最终得到

其中$A_{1}:=\sum_{l=1}^{\infty}\omega^{a_{1}(l^{b^{*}}-1)}<\infty.$

首先估计不等式 (6.3) 中右边的因式. 利用 $x\geq 0$ 时 $\ln (1+x)\leq x$可得

由 (6.1) 式 $m_{j}$ 的定义得$a_{j}[(m_{j}+1)/2]^{b_{j}}\geq a_{j}^{1-\beta}x(M)= a_{j}^{1-\beta}(\ln M)/\ln\omega^{-1}$.因此

不失一般性, 假设 $M\geq 2$. 因为 $j\leq N_{\tau}^{*}-1$, $a_{j}\geq a_{1}$,$j\geq N_{\tau}^{*}$ 时 $a_{j}\geq\exp\left(\frac{\tau j}{1+\ln j}\right)$, 从而

其中

由 (6.4) 式容易验证当 $M\geq C_{\beta,\tau}^{1/\min(a_{1}^{1-\beta},1)}$ 时 $\gamma\leq 1$.而且, 利用函数的凸性可以证得对所有 $\gamma\in[0,1]$, $-1+\exp(\gamma)\leq (e-1)\gamma$.因此, 当 $M\geq C_{\beta,\tau}^{1/\min(a_{1}^{1-\beta},1)}$ 时,

从而

下面估计使用算法 $\sigma(\cdot; g_{n,d})$ 时所需要的函数值数量 $n$.当 $x(M)\geq a_{1}^{\beta}$, 即 $M\geq \omega^{-a_{1}^{\beta}}$ 时,

因为 $N^{*}_{\beta,\tau, M}\leq N_{\tau}^{*}+J(M)$, 从而由 (6.6) 式得

当 $M\geq\max(2,C_{\beta,\tau}^{1/\min(a_{1}^{1-\beta},1)},\omega^{-e^{\tau}},\omega^{-a_{1}^{\beta}})$ 时, 结合 (6.5) 和 (6.7) 式得

其中

因为 $y\rightarrow\infty$ 时$J(y)=\frac{1+o(1)}{\beta\tau}[\ln\ln y]\ln\ln\ln y,$由此可以得到 $D_{\beta,\tau}<+\infty$. 现在设

从而

另外, 由 (6.8) 式知 $\varepsilon\rightarrow 0$ 时 $\ln M=\mathcal{O}(\ln\varepsilon^{-1})$.因此, 对于足够小的 $\varepsilon$ 存在 $C_{1}>1$ 使得

由信息复杂度的定义和 (6.9) 式可知, 对于足够小的 $\varepsilon$

其中

由 (6.2) 式知 $\lim a_{j}=\infty$, 这意味着 $C_{d,M}$ 中仅有有限个项大于 1.从而

而且, 由假设条件 $B^{*}<\infty$ 得

现在结合 (6.11) 与 (6.12) 式, 可将 (6.10) 式变为

事实上, 我们可以使用类似文献 [5] 的方法去分析 (6.13) 式中的因式$\rho:=3^{\min(d,N_{\beta,\tau,M}^{*})}$ 并最终得到

上式可等价地写成

因为对于足够小的 $\varepsilon$ 存在 $C_{1}>1$ 使得 $\ln M\leq C_{1}\ln\varepsilon^{-1}$,故由 (6.14) 式得

其中 $C_{3}:=1+\ln C_{1}$.

由 (6.13) 和 (6.15) 式知 EC-QPT 成立, 且$t\leq B^{*}+C_{3}(\beta\tau)^{-1}(1+2\eta)\ln 3.$由于 $\tau$ 可任意趋于 $\alpha_{*}$, $\eta$ 可任意小,且 $\beta$ 可任意趋于 1, 故得 EC-QPT 的指数满足$t^{*}\leq B^{*}+\frac{C_{3}\ln 3}{\alpha_{*}}.$

证 首先证明由 EC-UWT 成立得到条件 (4.2).由 (2.5) 式可知只需考虑多元$\mathbb{L}_{\infty}$-逼近问题和线性信息类 $\Lambda^{\text{all}}$.因此, 由文献[22]可知条件 (4.2) 成立.

下面证明当使用标准信息类 $\Lambda^{\text{std}}$ 时,条件 (4.2) 可以推出多元 $\mathbb{L}_{\infty}$-逼近问题的 EC-UWT 成立.由关系式 (2.6) 知, 只需证明绝对误差标准下的 EC-UWT 成立.需要强调的是我们使用的算法和正则网格与定理 4.1 的证明过程中一样.由于 $A=\infty$, 故对任意 $\delta>0$ 存在正整数 $N_{\delta}^{*}$, 使得 $j\geq N_{\delta}^{*}$ 时,

注意到 $a_{j}\geq(x(M))^{1/\beta}$ 时 $m_{j}=1$, 因此由 (7.1) 式可得当

时, $m_{j}=1$.

类似于定理 4.1 的证明方法, 得到

其中

不失一般性, 假设 $M\geq 2$. 因为 $j\leq N_{\delta}^{*}-1$ 时 $a_{j}\geq a_{1}$,$j\geq N_{\delta}^{*}$ 时 $a_{j}>j^{\delta}$, 因此由 (7.3) 式得

其中

由于 $M\geq C_{\beta,\delta}^{1/\min(a_{1}^{1-\beta},1)}$ 时 $\gamma\leq 1$,故结合 (7.2) 和 (7.4) 式可得

这里第一个不等式利用了 $\gamma\in[0,1]$ 时 $-1+\exp(\gamma)\leq (e-1)\gamma$ 的结论.

现在估计使用算法 $\sigma(\cdot; g_{n,d})$ 时所需要的函数值数量 $n$.因为 $N_{\beta,\delta,M}^{*}\leq N_{\delta}^{*}+(x(M))^{\frac{1}{\beta\delta}}$,故由 (6.6) 式得

因此, 当 $M\geq\max(2,C_{\beta,\delta}^{1/\min(a_{1}^{1-\beta},1)},\omega^{-a_{1}^{\beta}})$ 时,结合 (7.5) 和 (7.6) 式得

其中

且 $\delta>1/\beta$.若取

则

由 (7.7) 式知 $\varepsilon\rightarrow 0$ 时 $\ln M=\mathcal{O}(\ln\varepsilon^{-1})$.从而根据信息复杂度的定义和 (7.6) 式知

其中 $\mathcal{O}$ 仅依赖于 $\beta$ 和 $\delta$.因此,

对任意的 $s,t\in(0,\infty)$, 如果选取 $\delta>\max(1/\beta,1/(\beta t))$, 则

上面式子意味着 EC-UWT 成立.