6.3. 规范方法的收敛速度

从上面的讨论我们已经知道, 若 $\mu =1-\lambda$ 是 $T=I-U^{\prime }$ 的一个单特征值, 则当 $n$ 足够大时, ${\mu }_n=1-{\lambda }_n$ 也是 $T_n^{\prime }=I-U_n^{\prime }$ 的一个单特征值, 从而关于 ${\mu }_n$ 的谱投影算子 ${\text{Pr}}_n$ 的像即为由其特征函数 $f_n$ 张成的一维线性空间. 设 $\Vert f_n\Vert =1$, 则它们的 “极限函数”$f$ 也有 $\Vert f\Vert =1.$

我们的目标是估计 $\Vert a_n{f}_n-f\Vert$: 为此令 ${\text{Pr}}_{n}f=c_n{f}_n$, 则有 $a_n=\text{sgn}{c}_n$, 即 $c_n=a_n|c_n|$, 从而$$\begin{array}{rl}\Vert a_n{f}_n-f\Vert & \le \Vert a_n{f}_n-c_n{f}_n\Vert +\Vert {\text{Pr}}_{n}f-f\Vert \\ & =|1-|c_n||+\Vert {\text{Pr}}_{n}f-f\Vert \\ & =|\Vert f\Vert -\Vert c_n{f}_n\Vert |+\Vert {\text{Pr}}_{n}f-f\Vert \\ & \le \Vert f-c_n{f}_n\Vert +\Vert {\text{Pr}}_{n}f-f\Vert =2\Vert f-{\text{Pr}}_{n}f\Vert .\end{array}$$于是问题转化为估计 $\Vert f-{\text{Pr}}_{n}f\Vert$, 而这可以利用如下定理得到:

定理 6.3.0.1. 设 $(E,\Vert \cdot \Vert )$ 是 Banach 空间, $T_n^{\prime }$ 和 $T$ 是其上的紧算子, 并且 $T_n^{\prime }\stackrel{cc}{\to }T.$ 取 $\mu \in \sigma (T)\backslash \{0\}$ 的逼近序列 ${\mu }_n\in \sigma (T_n^{\prime })\backslash \{0\}$, 它们相应的谱投影算子为 ${\text{Pr}}_n.$ 则存在只依赖于 $\mu$ 和 $\sigma (T)$ 的常数 $C>0$ 使得$$\Vert f-{\text{Pr}}_{n}f\Vert \le C(\Vert (T_n^{\prime }-T)f\Vert +\Vert f\Vert \cdot \Vert (T-T_n^{\prime })T_n^{\prime }\Vert )$$对 $\mu$ 的任意特征向量 $f\in E$ 成立.

(详见文章 The Numerical Solution of the Eigenvalue Problem for Compact Integral Operators 中的定理 3)

根据这个定理, 我们只需要估计 $\Vert (T_n^{\prime }-T)f\Vert$ 和 $\Vert (T-T_n^{\prime })T_n^{\prime }\Vert$ 两项:

•

第一项的估计已由上一节的命题证明过程给出: $$\begin{array}{rl}\Vert T_n^{\prime }f-Tf\Vert \le & \underset{x\in \mathcal{X}}{\sup }\left|{\int }_{\mathcal{X}}h(x,y)f(y)d{P}_n(y)-{\int }_{\mathcal{X}}h(x,y)f(y)dP(y)\right|\\ & +\frac{\Vert s{\Vert }^2}{l^3}\underset{x\in \mathcal{X}}{\sup }\left|{\int }_{\mathcal{X}}s(x,y)d{P}_n(y)-{\int }_{\mathcal{X}}s(x,y)dP(y)\right|\\ \le & \left(1+\frac{\Vert s{\Vert }^2}{l^3}\right)\underset{g\in (f\cdot \mathcal{H})\cup \mathcal{S}}{\sup }\left|{\int }_{\mathcal{X}}g(y)d{P}_n(y)-{\int }_{\mathcal{X}}g(y)dP(y)\right|.\end{array}$$

•

对于第二项, 我们将其拆解进行估计: $$\begin{array}{rl}\Vert (T-T_n^{\prime })T_n^{\prime }\Vert & \le \Vert (T-T_n)T_n^{\prime }\Vert +\Vert (T_n-T_n^{\prime })T_n^{\prime }\Vert \\ & \le \Vert T(T_n^{\prime }-T_n)\Vert +\Vert (T-T_n)T_n\Vert +\Vert T_n(T_n-T_n^{\prime })\Vert +\Vert (T_n-T_n^{\prime })T_n^{\prime }\Vert \\ & \le \Vert T_n^{\prime }-T_n\Vert (\Vert T\Vert +\Vert T_n\Vert +\Vert T_n^{\prime }\Vert )+\Vert (T-T_n)T_n\Vert .\end{array}$$根据上一节的命题证明, 易见前一项有估计$$\begin{array}{rl}\Vert T_n^{\prime }-T_n\Vert (\Vert T\Vert +\Vert T_n\Vert +\Vert T_n^{\prime }\Vert )& \le \frac{\Vert s{\Vert }^2}{l^3}\underset{x\in \mathcal{X}}{\sup }\left|{\int }_{\mathcal{X}}s(x,y)d{P}_n(y)-{\int }_{\mathcal{X}}s(x,y)dP(y)\right|\cdot \frac{3\Vert s\Vert }{l}\\ & =\frac{3\Vert s{\Vert }^3}{l^4}\underset{g\in \mathcal{S}}{\sup }\left|{\int }_{\mathcal{X}}g(y)d{P}_n(y)-{\int }_{\mathcal{X}}g(y)dP(y)\right|,\end{array}$$故只需再估计后一项: 从范数和算子的定义出发, 我们有$$\begin{array}{rl}& \Vert (T-T_n)T_n\Vert =\underset{\Vert g\Vert =1}{\sup }\underset{x\in \mathcal{X}}{\sup }|(T-T_n)T_{n}g(x)|\\ & =\underset{\Vert g\Vert =1}{\sup }\underset{x\in \mathcal{X}}{\sup }\left|{\int }_{\mathcal{X}}h(x,z){\int }_{\mathcal{X}}h(z,y)g(y)d{P}_n(y)dP(z)-{\int }_{\mathcal{X}}h(x,z){\int }_{\mathcal{X}}h(z,y)g(y)d{P}_n(y)d{P}_n(z)\right|\\ & =\underset{\Vert g\Vert =1}{\sup }\underset{x\in \mathcal{X}}{\sup }\left|{\int }_{\mathcal{X}}g(y){\int }_{\mathcal{X}}h(x,z)h(z,y)dP(z)d{P}_n(y)-{\int }_{\mathcal{X}}g(y){\int }_{\mathcal{X}}h(x,z)h(z,y)d{P}_n(z)d{P}_n(y)\right|\\ & \le \underset{x,y\in \mathcal{X}}{\sup }\left|{\int }_{\mathcal{X}}h(x,z)h(y,z)dP(z)-{\int }_{\mathcal{X}}h(x,z)h(y,z)d{P}_n(z)\right|\\ & =\underset{g\in \mathcal{H}\cdot \mathcal{H}}{\sup }\left|{\int }_{\mathcal{X}}g(z)dP(z)-{\int }_{\mathcal{X}}g(z)d{P}_n(z)\right|,\end{array}$$其中最后的函数类定义为$$\mathcal{H}\cdot \mathcal{H}:=\{h(x,\cdot )h(y,\cdot ):x,y\in \mathcal{X}\}.$$综合起来我们得到$$\Vert (T-T_n^{\prime })T_n^{\prime }\Vert \le \left(1+\frac{3\Vert s{\Vert }^3}{l^4}\right)\underset{g\in (\mathcal{H}\cdot \mathcal{H})\cup \mathcal{S}}{\sup }\left|{\int }_{\mathcal{X}}g(y)d{P}_n(y)-{\int }_{\mathcal{X}}g(y)dP(y)\right|.$$

综上, 我们可以得到最终结果:

定理 6.3.0.2. 在上述假设和记号下, 则存在只依赖于 $\mu ,\sigma (T)$ 和相似度函数 $s$ 的常数 $C’>0$, 以及一列 $\{a_n\}\subset \{-1,1\}$, 使得$$\Vert a_n{f}_n-f\Vert \le C^{\prime }\underset{g\in \mathcal{G}}{\sup }\left|{\int }_{\mathcal{X}}g(y)d{P}_n(y)-{\int }_{\mathcal{X}}g(y)dP(y)\right|$$其中函数类 $\mathcal{G}=\mathcal{S}\cup (f\cdot \mathcal{H})\cup (\mathcal{H}\cdot \mathcal{H}).$

由此可见, 特征函数的收敛速度被经验分布的收敛速度 (由函数类 $\mathcal{G}$ 刻画) 所控制, 而后者可由经验过程理论得到估计 (参考书 Weak Convergence and Empirical Processes 中第 2 章) .

例如, 对于 Gauss 相似度函数 $s(x,y)=\exp (-\Vert x-y{\Vert }^2/{\sigma }^2)$, 我们可以用覆盖数方法得到特征函数的收敛速度为 $O(1/n).$ (详见文章中的 Section 6.3)