Hilbert空间中增量型不精确拟牛顿算法的局部收敛性分析

Local Convergence Analysis of Incremental Inexact Quasi-Newton Algorithm in Hilbert Space

摘要: 在图像处理，机器学习和工程学等应用领域中，通常需要处理一些定义在Hilbert空间中的大规模算子方程。为求解这类算子方程及最值问题，构造了一类增量型不精确Broyden方法并证明了该算法的线性收敛和局部超线性收敛性。该算法降低了在处理大规模问题中所产生的储存成本，并通过应用证明了该算法的有效性。

Abstract: In application fields such as image processing, machine learning, and engineering, it is often necessary to solve large-scale operator equations defined in Hilbert spaces. To address such operator equations and optimization problems, a class of incremental inexact Broyden methods has been developed, and the linear convergence as well as local superlinear convergence of this algorithm has been proven. This algorithm reduces the storage costs associated with handling large-scale problems, and its effectiveness has been demonstrated through practical applications.

1. 引言

随着大数据时代的到来，其深刻改变着人类的生活和工作方式。数据量的急剧增长是大数据时代最直观的表现。从GB到TB，再到PB、EB，数据量的爆炸式增长对存储和处理能力提出了前所未有的挑战，处理速度的快慢直接关系到大数据的时效性。因此，在大数据时代需要不断创新数据处理和分析技术，才能更好地挖掘和利用大数据的潜力，推动社会进步和经济发展。

在图像处理[1]-[3]，机器学习[4] [5]和工程学[6] [7]等应用领域中通常是将实际问题转换为算子方程进行求解，考虑抽象空间中算子方程的一般形式为

$F\left(x\right)=\frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(x\right)}=0$ (1)

其中$f_i\left(x\right):X\to Y$ 是非线性算子，$X,Y$ 是Hilbert空间。

关于求解非线性方程组的研究已经有很长的历史。在有限维空间中，当F是个非线性算子时，牛顿法较为经典，其具有二阶的收敛速度，但需要精确计算导算子，使得牛顿法在实际的应用受到限制，特别在大规模问题及其不适用。为了解决上述问题，[8]提出了一种新的迭代算法——Broyden迭代算法，其核心优势在于避免了传统导算子的复杂计算过程，并保持了优于常规算法的收敛效率。该算法在非线性最小范数问题和非光滑优化等应用领域中表现出较为明显的优势。然而，当涉及需要离散化处理的无穷维空间问题时，经典Broyden方法受限于有限维近似带来的误差积累，其收敛速率明显降低。为解决该问题，[9]通过构建Hilbert空间的理论框架，将Broyden方法扩展至无穷维情形下的非线性算子方程求解，并证明了算法的线性收敛性和超线性收敛，使得Broyden方法更具一般性。

在无限维空间中，关于求解非线性方程组和无约束优问题的不精确牛顿类方法的研究很多。针对Banach空间中半光滑算子方程的求解问题，[10]提出了两种不精确牛顿法，并分别证明了两种方法的全局收敛性。[11]通过对非线性最小二乘问题的高斯牛顿法展开理论分析，基于Hölder连续性的假设框架，并在仿射不变条件下建立了不精确高斯牛顿法的局部收敛理论，证明了算法在临界点邻域内具有确定的收敛半径和1 + p阶超线性收敛速率。为求解无约束极大极小问题，[12]通过引入光滑凝聚函数对非光滑极大值函数进行可微逼近，将原问题转化为光滑无约束优化形式，再使用不精确牛顿法进行求解，并证明了算法的全局收敛性。值得注意的是，[13]基于[9]的理论基础上，进一步研究了Hilbert空间上算子方程的不精确拟牛顿法，成功将有限维不精确拟牛顿法拓展至Hilbert空间中用于解决算子方程求解问题，并证明了其线性收敛性和超线性收敛性。

在Hilbert空间中，关于增量型不精确拟牛顿法的研究很少。当面对大规模问题时，面对大量的数据时，现有的计算机只能存储有限个数据和做有限次运算，所以如何降低存储成本和提高收敛速度是有必要研究的。[14]对有限维空间中的增量拟牛顿法(IQN)的收敛性和存储成本进行了研究，为将不精确拟牛顿法与增量思想相结合，并推广至无限维空间中作了准备。

本文在[13]的基础上，将Hilbert空间中的不精确拟牛顿法与增量思想相结合，构造了增量型不精确拟牛顿方法用于解决大规模的抽象算子方程问题中出现的存储成本高昂的问题，并证明了该方法的局部收敛性。

2. 预备知识

本研究建立的理论框架基于以下基本假设：

假设1 (解的存在性)：非线性算子$f_i\left(x\right):X\to Y$ ，存在最优解$x^{\ast }\in X$ ，使得$F^{\prime }\left(x^{\ast }\right)=\frac{1}{n}{\displaystyle \sum _{i=1}^n{f^{\prime }}_i\left(x^{\ast }\right)}=0$ 。

假设2：非线性算子$f_i$ 在解邻域$B_{\delta }\left(x^{\ast }\right)$ 内Fréchet可微，且在解邻域内${f^{\prime }}_i$ 是局部Lipschitz连续的。

假设3：${f^{\prime }}_i\left(x^{\ast }\right)$ 是非奇异的或存在$\gamma >0$ ，使得对任意的$x\in X$ 有$\Vert {f^{\prime }}_i\left(x^{\ast }\right)\left(x\right)\Vert \ge \gamma \Vert x\Vert$ 。

为证明超线性收敛，需要下面的定义及引理：

定义2.1 [9]：设$X,Y$ 是Hilbert空间。算子$D\in B\left(X,Y\right)$ 称为Hilbert-Schmidt算子，若存X的某个标准正交基$\left\{a_{\alpha }:\alpha \in A\right\}$ 使得${{\displaystyle \sum _{\alpha \in A}\Vert D{a}_{\alpha }\Vert }}_Y^2<\infty$ 。

引理2.1 [9]：设$X,Y$ 是Hilbert空间，$x_i\in X$ ，$y_i\in Y$ ，$i=1,2$ ，$T\in B\left(X,Y\right)$ 则以下性质成立，其中$T^{\ast }$ 表示伴随算子：

(i) ${\left(y_1\otimes x_1\right)}^{\ast }=x_1\otimes y_1\in B\left(Y,X\right)$ ，

(ii) $\left(y_1\otimes x_1\right)\left(x_2\otimes y_2\right)=\langle x_1,x_2\rangle \left(y_1\otimes y_2\right)\in B\left(Y,Y\right)$ ，

(iii) $T\left(x_1\otimes y_1\right)=T{x}_1\otimes y_1\in B\left(Y,Y\right)$ ，

(iv) $\left(y_1\otimes x_1\right)T^{\ast }=y_1\otimes T{x}_1\in B\left(Y,Y\right)$ ，

(v) $\Vert y_1\otimes x_1\Vert =\Vert y_1\Vert \Vert x_1\Vert$ 。

引理2.2 [9]：设$X,Y$ 是Hilbert空间，$x_1,x_2\in X$ ，$D_1$ 是Hilbert-Schmidt算子。则对于定义2.1中的标准正交基$\left\{a_{\alpha }:\alpha \in A\right\}$ ，对每个算子$T\in B\left(X,X\right)$ 进行定义

$trT={\displaystyle \sum _{\alpha \in A}\langle a_{\alpha },T{a}_{\alpha }\rangle }$

只要和是有限的，则以下结论成立：

(i) 对于$i=1,2$ 有$tr{T}_i<\infty$ ，则$tr\left(T_1+T_2\right)=tr{T}_1+tr{T}_2$ ，

(ii) $tr{x}_1\otimes x_2=\langle x_1,x_2\rangle$ 。

3. 增量型不精确拟牛顿型的收敛性分析

为本节主要构造了增量型不精确拟牛顿算法，并对其收敛性进行了分析和证明，为证明第四节Hilbert空间增量型不精确拟牛顿算法的收敛性做好准备。

增量型不精确拟牛顿算法

为解决大规模抽象算子问题，根据不精确拟牛顿算法和[14]中所提出的以循环方式选择进行更新的增量拟牛顿方法，构造的增量型不精确拟牛顿算法框架如下：

算法3.1增量型不精确拟牛顿算法

步0：设$x^0$ ，${\left\{B_i^0\right\}}_{i=1}^n$ 分别为初始迭代点和初始迭代算子；

步1：设$z_1^0=z_2^0=\cdots =z_n^0=x^0$ ；

步2：设$g^0=\frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(x^0\right)}$ ，$\left({\tilde{B}}^0\right)=\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^0}$ ；

步3：对于$k=0,1,\cdots$ 做循环更新：

3.1设$i_k=\left(k\mathrm{mod}n\right)+1$ ，是对于所有k做循环选择需要满足的重要索引，

3.2计算$x^{k+1}=x^k+\Delta x^k$ ，其中$\Delta x^k$ 为非精确求解得到并满足

$r^k={\tilde{B}}^k\Delta x^k+g^k$ ，$\frac{\Vert r^k\Vert }{\Vert g^k\Vert }\le {\eta }^k$ ，${\eta }^k\in \left[0,1\right)$

3.3当$i=i_k$ 时，计算$s_{i_k}^{k+1},y_{i_k}^{k+1}$ 和其中根据$B_i^k\in B\left(X,Y\right)$ 的迭代方法计算$B_{i_k}^{k+1}$ ，

$s_i^k=z_i^{k+1}-z_i^k$ ，$y_i^k=f_i\left(z_i^{k+1}\right)-f_i\left(z_i^k\right)$

3.4更新${\tilde{B}}^{k+1}$ 和有关函数信息表，其中

$\{\begin{array}{l}{z}_{i_k}^{k+1}=x^{k+1}i=i_k\\ z_i^{k+1}=z_i^{k}i\ne i_k\end{array}$ $\{\begin{array}{l}{f}_{i_k}\left(z_i^{k+1}\right)=f_{i_k}\left(x^{k+1}\right)i=i_k\\ f_i\left(z_i^{k+1}\right)=f_i\left(z_i^k\right)i\ne i_k\end{array}$ $\{\begin{array}{l}{\tilde{B}}^{k+1}={\tilde{B}}^k+\frac{1}{n}\left(B_{i_k}^{k+1}-B_{i_k}^k\right)i=i_k\\ g^{k+1}=g^k+\frac{1}{n}\left(f_{i_k}\left(z_{i_k}^{k+1}\right)-f_{i_k}\left(z_{i_k}^k\right)\right)i=i_k\\ B_i^{k+1}=B_i^{k}i\ne i_k\end{array}$

基于该算法，有如下的线性收敛性定理：

定理3.1：设$X,Y$ 是Hilbert空间，$f_i:X\to Y$ 是非线性算子，假设在假设均成立的情况下，算法3.1产生的迭代序列$\left\{x^k\right\}$ ，存在$\epsilon >0$ 和$\eta >0$ 满足$\epsilon <\frac{1}{\Vert {f^{\prime }}_i{\left(x^{\ast }\right)}^{-1}\Vert }$ 和$\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \left(\frac{L\left(\eta +1\right)}{2}\epsilon +\eta \Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert +\epsilon \right)<1$ ，其中${\eta }^k\in \left[0,\eta \right)$ 且$0<\eta <1$ ，L为Lipschitz常数，当首次迭代点$x^0$ 与$B_i^k$ 对任意$\forall k\in N$ ，$i=1,2,\cdots ,n$ 满足$\Vert x^0-x^{\ast }\Vert \le \epsilon$ 且$\Vert B_i^k-{f^{\prime }}_i\left(x^{\ast }\right)\Vert \le \epsilon$ ，则序列$\left\{x^k\right\}$ 满足

$\Vert x^k-x^{\ast }\Vert \le r^{\left[\frac{k-1}{n}\right]+1}\Vert x^0-x^{\ast }\Vert$ 。(2)

证明：由算法3.1可知

$\begin{array}{c}{x}^{k+1}-x^{\ast }=x^k+\Delta x^k-x^{\ast }\\ =z_i^k+\left(r^k-g^k\right){\left({\tilde{B}}^k\right)}^{-1}-x^{\ast }\\ =z_i^k+\left(r^k-\frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(z_i^k\right)}\right){\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}-x^{\ast }\\ ={\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\left[\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k{z}_i^k}+r^k-\frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(z_i^k\right)}-\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k{x}^{\ast }}\right]\\ ={\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}{r}^k-{\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\left[\frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(z_i^k\right)}-\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k\left(z_i^k-x^{\ast }\right)}\right]\end{array}$ (3)

对式(3)同时加上并减去$\frac{1}{n}{\displaystyle \sum _{i=1}^n{f^{\prime }}_i\left(x^{\ast }\right)\left(z_i^k-x^{\ast }\right)}$ ，并重新排列项得到

$\begin{array}{l}\Vert x^{k+1}-x^{\ast }\Vert \\ =\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}{r}^k-{\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}[\frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(z_i^k\right)}-\frac{1}{n}{\displaystyle \sum _{i=1}^n{f^{\prime }}_i\left(x^{\ast }\right)\left(z_i^k-x^{\ast }\right)}\\ +\frac{1}{n}{\displaystyle \sum _{i=1}^n{f^{\prime }}_i\left(x^{\ast }\right)\left(z_i^k-x^{\ast }\right)}-\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k\left(z_i^k-x^{\ast }\right)}]\Vert \\ =\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}{r}^k-{\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\left[\frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(z_i^k\right)}-\frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i{}^{\prime }\left(x^{\ast }\right)\left(z_i^k-x^{\ast }\right)}+\frac{1}{n}{\displaystyle \sum _{i=1}^n\left({f^{\prime }}_i\left(x^{\ast }\right)-B_i^k\right)\left(z_i^k-x^{\ast }\right)}\right]\Vert \\ \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}{r}^k\Vert +\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\left[\frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(z_i^k\right)}-\frac{1}{n}{\displaystyle \sum _{i=1}^n{f^{\prime }}_i\left(x^{\ast }\right)\left(z_i^k-x^{\ast }\right)}+\frac{1}{n}{\displaystyle \sum _{i=1}^n\left({f^{\prime }}_i\left(x^{\ast }\right)-B_i^k\right)\left(z_i^k-x^{\ast }\right)}\right]\Vert \end{array}$

由于$r^k={\tilde{B}}^k\Delta x^k+g^k$ 且满足$\frac{\Vert r^k\Vert }{\Vert g^k\Vert }\le {\eta }^k$ ，${\eta }^k\in \left[0,\eta \right)$ ，则有

$\begin{array}{l}\Vert x^{k+1}-x^{\ast }\Vert \\ \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}{r}^k\Vert +\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\left[\frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(z_i^k\right)}-\frac{1}{n}{\displaystyle \sum _{i=1}^n{f^{\prime }}_i\left(x^{\ast }\right)\left(z_i^k-x^{\ast }\right)}+\frac{1}{n}{\displaystyle \sum _{i=1}^n\left({f^{\prime }}_i\left(x^{\ast }\right)-B_i^k\right)\left(z_i^k-x^{\ast }\right)}\right]\Vert \\ \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \eta \Vert g^k\Vert +\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \Vert \frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(z_i^k\right)}-\frac{1}{n}{\displaystyle \sum _{i=1}^n{f^{\prime }}_i\left(x^{\ast }\right)\left(z_i^k-x^{\ast }\right)}+\frac{1}{n}{\displaystyle \sum _{i=1}^n\left({f^{\prime }}_i\left(x^{\ast }\right)-B_i^k\right)\left(z_i^k-x^{\ast }\right)}\Vert \end{array}$

由$f_i{}^{\prime }\left(z_i^k\right)$ 在$x^{\ast }$ 处的泰勒展开得到

$\begin{array}{l}\Vert x^{k+1}-x^{\ast }\Vert \\ \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}{r}^k\Vert +\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}[\frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(z_i^k\right)}-\frac{1}{n}{\displaystyle \sum _{i=1}^n{f^{\prime }}_i\left(x^{\ast }\right)\left(z_i^k-x^{\ast }\right)}\\ +\frac{1}{n}{\displaystyle \sum _{i=1}^n\left({f^{\prime }}_i\left(x^{\ast }\right)-B_i^k\right)\left(z_i^k-x^{\ast }\right)}]\Vert \\ \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \eta \Vert g^k\Vert +\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \Vert \frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(z_i^k\right)}-\frac{1}{n}{\displaystyle \sum _{i=1}^n{f^{\prime }}_i\left(x^{\ast }\right)\left(z_i^k-x^{\ast }\right)}\\ +\frac{1}{n}{\displaystyle \sum _{i=1}^n\left({f^{\prime }}_i\left(x^{\ast }\right)-B_i^k\right)\left(z_i^k-x^{\ast }\right)}\Vert \\ \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \eta \Vert \frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(z_i^k\right)}\Vert +\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \left(\frac{L}{2n}{\displaystyle \sum _{i=1}^n{\Vert z_i^k-x^{\ast }\Vert }^2}+\frac{1}{n}{\displaystyle \sum _{i=1}^n\Vert {f^{\prime }}_i\left(x^{\ast }\right)-B_i^k\Vert \Vert z_i^k-x^{\ast }\Vert }\right)\end{array}$

又因$\Vert B_i^k-{f^{\prime }}_i\left(x^{\ast }\right)\Vert \le \epsilon$ ，最后得到

$\begin{array}{c}\Vert x^{k+1}-x^{\ast }\Vert \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \eta \left(\frac{L}{2n}{\displaystyle \sum _{i=1}^n{\Vert z_i^k-x^{\ast }\Vert }^2}+\frac{1}{n}{\displaystyle \sum _{i=1}^n\Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert \Vert z_i^k-x^{\ast }\Vert }\right)\\ +\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \left(\frac{L}{2n}{\displaystyle \sum _{i=1}^n{\Vert z_i^k-x^{\ast }\Vert }^2}+\frac{1}{n}{\displaystyle \sum _{i=1}^n\Vert {f^{\prime }}_i\left(x^{\ast }\right)-B_i^k\Vert \Vert z_i^k-x^{\ast }\Vert }\right)\\ \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \frac{L\left(\eta +1\right)}{2n}\Vert z_i^k-x^{\ast }\Vert {\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }\end{array}$ (4)

$\begin{array}{c}+\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \left(+\frac{\eta }{n}\Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert +\frac{1}{n}\Vert {f^{\prime }}_i\left(x^{\ast }\right)-B_i^k\Vert \right){\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }\\ \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \left(\frac{L\left(\eta +1\right)}{2n}\epsilon +\frac{\eta }{n}\Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert +\frac{\epsilon }{n}\right){\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }\end{array}$

由式(4)，可得到首次迭代

$\begin{array}{c}\Vert x^1-x^{\ast }\Vert \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^0}\right)}^{-1}\Vert \left(\frac{L\left(\eta +1\right)}{2n}\epsilon +\frac{\eta }{n}\Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert +\frac{\epsilon }{n}\right){\displaystyle \sum _{i=1}^n\Vert z_i^0-x^{\ast }\Vert }\\ \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^0}\right)}^{-1}\Vert \left(\frac{L\left(\eta +1\right)}{2}\epsilon +\eta \Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert +\epsilon \right)\Vert x^0-x^{\ast }\Vert \end{array}$

由于$r=\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \left(\frac{L\left(\eta +1\right)}{2}\epsilon +\eta \Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert +\epsilon \right)<1$ ，则

$\Vert x^1-x^{\ast }\Vert \le r\Vert x^0-x^{\ast }\Vert <\epsilon$

继续进行下一次迭代，有不等式

$\begin{array}{c}\Vert x^2-x^{\ast }\Vert \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^1}\right)}^{-1}\Vert \left(\frac{L\left(\eta +1\right)}{2n}\epsilon +\frac{\eta }{n}\Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert +\frac{\epsilon }{n}\right){\displaystyle \sum _{i=1}^n\Vert z_i^1-x^{\ast }\Vert }\\ =\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^1}\right)}^{-1}\Vert \left(\frac{L\left(\eta +1\right)}{2}\epsilon +\eta \Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert +\epsilon \right)\left(\frac{n-1}{n}\Vert x^0-x^{\ast }\Vert +\frac{1}{n}\Vert x^1-x^{\ast }\Vert \right)\\ \le r\left(\frac{n-1}{n}\Vert x^0-x^{\ast }\Vert +\frac{1}{n}\Vert x^1-x^{\ast }\Vert \right)\\ \le r\Vert x^0-x^{\ast }\Vert \end{array}$

同理可证，对于所有的迭代$k=1,\dots n$ ，有$\Vert x^k-x^{\ast }\Vert \le \epsilon$ 。此外，当$k=1,\cdots ,n$ 时，有$\Vert x^k-x^{\ast }\Vert \le r\Vert x^0-x^{\ast }\Vert$ 。

现在使用迭代$k=1,\cdots ,n$ 作为归纳论证的基础。为了更精确，假设对于迭代$k=jn+1,jn+2,\cdots ,jn+n$ ，残差的上界为$\Vert x^k-x^{\ast }\Vert \le r^{j+1}\Vert x^0-x^{\ast }\Vert$ 。

下面证明，对于迭代序列$k=\left(j+1\right)n+1,\left(j+1\right)n+2,\cdots ,\left(j+1\right)n+n$ ，不等式$\Vert x^k-x^{\ast }\Vert \le r^{j+2}\Vert x^0-x^{\ast }\Vert$ 成立。

基于不等式$\Vert B_i^k-{f^{\prime }}_i\left(x^{\ast }\right)\Vert \le \epsilon$ 且$\Vert {f^{\prime }}_i{\left(x^{\ast }\right)}^{-1}\Vert$ 有界，可以证明，对于所有的$k=jn+1,jn+2,\cdots ,jn+n$ ，有$\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert$ 是一致有界的。对于迭代$k=\left(j+1\right)n+1$ ，有

$\begin{array}{c}\Vert x^{\left(j+1\right)n+1}-x^{\ast }\Vert \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^{\left(j+1\right)n}}\right)}^{-1}\Vert \left(\frac{L\left(\eta +1\right)}{2n}\epsilon +\frac{\eta }{n}\Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert +\frac{\epsilon }{n}\right){\displaystyle \sum _{i=1}^n\Vert z_i^{\left(j+1\right)n}-x^{\ast }\Vert }\\ \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^{\left(j+1\right)n}}\right)}^{-1}\Vert \left(\frac{L\left(\eta +1\right)}{2n}\epsilon +\frac{\eta }{n}\Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert +\frac{\epsilon }{n}\right){\displaystyle \sum _{i=1}^n\Vert z_i^{\left(j+1\right)n}-x^{\ast }\Vert }\end{array}$ (5)

由于变量以循环方式更新，因此变量集合${\left\{z_i^{\left(j+1\right)n}\right\}}_{i=1}^{i=n}$ 等于集合${\left\{x^{\left(j+1\right)n-i}\right\}}_{i=0}^{i=n-1}$ 且对于所有的$j=1,\cdots ,n$ 满足$\Vert x^{jn+i}-x^{\ast }\Vert \le \epsilon$ ，因此可以将式(5)的右侧简化为

$\begin{array}{c}\Vert x^{\left(j+1\right)n+1}-x^{\ast }\Vert \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^{\left(j+1\right)n}}\right)}^{-1}\Vert \left(\frac{L\left(\eta +1\right)}{2}\epsilon +\eta \Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert +\epsilon \right)\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n\Vert x^{jn+i}-x^{\ast }\Vert }\right)\\ \le r\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n\Vert x^{jn+i}-x^{\ast }\Vert }\right)\end{array}$ (6)

并假设对迭代序列$k=jn+1,jn+2,\cdots ,jn+n$ ，有$\Vert x^k-x^{\ast }\Vert \le r^{j+1}\Vert x^0-x^{\ast }\Vert$ ，则有

$\Vert x^{\left(j+1\right)n+1}-x^{\ast }\Vert \le r^{j+2}\Vert x^0-x^{\ast }\Vert$ (7)

即证得式(2)。

因此，算法3.1具有Q线性收敛性，其线性收敛因子$r<1$ 随参数$\epsilon$ 和$\eta$ 的选择而变化，可获得多样的收敛性因子值。

定理3.2：设$X,Y$ 是Hilbert空间，$f_i:X\to Y$ 是非线性算子，在假设条件均成立的情况下，$\left\{{\tilde{B}}^k\right\}$ 可逆。假设由算法3.1产生的迭代序列$\left\{x^k\right\}$ 收敛到$x^{\ast }$ ，若${\eta }^k=o\left(1\right)$ ，即$\Vert r_i^k\Vert =o\left(\Vert f_i\left(z_i^{k+1}\right)\Vert \right)$ ，则残差序列$\Vert x^k-x^{\ast }\Vert$ 满足：

$\underset{k\to \infty }{\lim }\frac{\Vert x^k-x^{\ast }\Vert }{\frac{1}{n}\left(\Vert x^{k-1}-x^{\ast }\Vert +\cdots +\Vert x^{k-n}-x^{\ast }\Vert \right)}=0$ (8)

的充要条件是对于所有的$i=1,2,\dots ,n$ 有

$\Vert \left(B_i^k-{f^{\prime }}_i\left(x^{\ast }\right)\right)\left(z_i^k-x^{\ast }\right)\Vert =o\left(\Vert z_i^k-x^{\ast }\Vert \right)$ 。

证明：当$f_i$ 满足假设条件(a)~(c)时，对任意向量$x,\widehat{x},x^{\ast }\in X$ 有

$\Vert f_i\left(\widehat{x}\right)-f_i\left(x\right)-{f^{\prime }}_i\left(x^{\ast }\right)\left(\widehat{x}-x\right)\Vert \le L\max \left\{\Vert \widehat{x}-x^{\ast }\Vert ,\Vert x-x^{\ast }\Vert \right\}\Vert \widehat{x}-x\Vert$ (9)

其中L是Lipschitz常数。故

$\left(B_i^k-{f^{\prime }}_i\left(x^{\ast }\right)\right)\left(z_i^{k+1}-z_i^k\right)=f_i\left(z_i^{k+1}\right)-f_i\left(z_i^k\right)-{f^{\prime }}_i\left(x^{\ast }\right)\left(z_i^{k+1}-z_i^k\right)+r_i^k-f_i\left(z_i^{k+1}\right)$ (10)

结合式(9)与式(10)得到

$\begin{array}{l}\frac{\Vert r_i^k-f_i\left(z_i^{k+1}\right)\Vert }{\Vert z_i^{k+1}-z_i^k\Vert }-L\max \left\{\Vert z_i^k-x^{\ast }\Vert ,\Vert z_i^{k+1}-x^{\ast }\Vert \right\}\\ \le \frac{\Vert \left(B_i^k-{f^{\prime }}_i\left(x^{\ast }\right)\right)\left(z_i^{k+1}-z_i^k\right)\Vert }{\Vert z_i^{k+1}-z_i^k\Vert }\\ \le L\max \left\{\Vert z_i^k-x^{\ast }\Vert ，\Vert z_i^{k+1}-x^{\ast }\Vert \right\}+\frac{\Vert r_i^k-f_i\left(z_i^{k+1}\right)\Vert }{\Vert z_i^{k+1}-z_i^k\Vert }\end{array}$

从而

$\underset{k\to \infty }{\lim }\frac{\Vert \left(B_i^k-{f^{\prime }}_i\left(x^{\ast }\right)\right)\left(z_i^{k+1}-z_i^k\right)\Vert }{\Vert z_i^{k+1}-z_i^k\Vert }=0$ (11)

式(11)成立的充要条件为

$\underset{k\to \infty }{\lim }\frac{\Vert r_i^k-f_i\left(z_i^{k+1}\right)\Vert }{\Vert z_i^{k+1}-z_i^k\Vert }=0$ (12)

下面证明式(12)为式(8)成立的充要条件：

假设$\underset{k\to \infty }{\lim }\frac{\Vert x^k-x^{\ast }\Vert }{\frac{1}{n}\left(\Vert x^{k-1}-x^{\ast }\Vert +\cdots +\Vert x^{k-n}-x^{\ast }\Vert \right)}=0$ 成立且${\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }={\displaystyle \sum _{i=0}^{n-1}\Vert x^{k-i}-x^{\ast }\Vert }$ ，则有

$\underset{k\to \infty }{\lim }\frac{\Vert x^{k+1}-x^{\ast }\Vert }{\frac{1}{n}{\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }}=0$

表明算法3.1生成的迭代序列具有平均超线性收敛速度。更准确地说，它表明在步骤k捕获误差的比值除以最后n个误差的平均值收敛于零。

由式(9)可知

$\Vert f_i\left(z_i^{k+1}\right)-f_i\left(x^{\ast }\right)-{f^{\prime }}_i\left(x^{\ast }\right)\left(z_i^{k+1}-x^{\ast }\right)\Vert \le L{\Vert z_i^{k+1}-x^{\ast }\Vert }^2$

可立即得到

$\begin{array}{c}\Vert f_i\left(z_i^{k+1}\right)\Vert \le \Vert f_i\left(x^{\ast }\right)+{f^{\prime }}_i\left(x^{\ast }\right)\left(z_i^{k+1}-x^{\ast }\right)\Vert +L{\Vert z_i^{k+1}-x^{\ast }\Vert }^2\\ ={\rm O}\left(\Vert z_i^{k+1}-x^{\ast }\Vert \right)=o\left(\Vert z_i^k-x^{\ast }\Vert \right)\end{array}$

同理可得$\Vert f_i\left(z_i^k\right)\Vert =o\left(\Vert z_i^k-x^{\ast }\Vert \right)$ 。

又因为$\Vert r_i^k\Vert \le {\eta }^k\Vert g_i^k\Vert ={\eta }^k\Vert f_i\left(z_i^k\right)\Vert$ ，其中${\eta }^k\to 0$ ，从而有

$\Vert r_i^k\Vert =o\left(\Vert z_i^k-x^{\ast }\Vert \right)$

故

$\Vert r_i^k-f_i\left(z_i^{k+1}\right)\Vert =o\left(\Vert z_i^k-x^{\ast }\Vert \right)=o\left(\Vert z_i^{k+1}-z_i^k\Vert \right)$

反之若

$\underset{k\to \infty }{\lim }\frac{\Vert r_i^k-f_i\left(z_i^{k+1}\right)\Vert }{\Vert z_i^{k+1}-z_i^k\Vert }=0$

则式(11)成立。

下证$\underset{k\to \infty }{\lim }\frac{\Vert x^k-x^{\ast }\Vert }{\frac{1}{n}\left(\Vert x^{k-1}-x^{\ast }\Vert +\cdots +\Vert x^{k-n}-x^{\ast }\Vert \right)}=0$ ，由定理3.1中的式(4)可得

$\begin{array}{c}\Vert x^{k+1}-x^{\ast }\Vert \le \Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \eta \left(\frac{L}{2n}{\displaystyle \sum _{i=1}^n{\Vert z_i^k-x^{\ast }\Vert }^2}+\frac{1}{n}{\displaystyle \sum _{i=1}^n\Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert \Vert z_i^k-x^{\ast }\Vert }\right)\\ +\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \left(\frac{L}{2n}{\displaystyle \sum _{i=1}^n{\Vert z_i^k-x^{\ast }\Vert }^2}+\frac{1}{n}{\displaystyle \sum _{i=1}^n\Vert {f^{\prime }}_i\left(x^{\ast }\right)-B_i^k\Vert \Vert z_i^k-x^{\ast }\Vert }\right)\end{array}$ (13)

将式(13)的两边同时除以$\frac{1}{n}{\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }$ 得到

$\begin{array}{c}\frac{\Vert x^{k+1}-x^{\ast }\Vert }{\frac{1}{n}{\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }}\le \frac{\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \left(\frac{\eta L}{2}{\displaystyle \sum _{i=1}^n{\Vert z_i^k-x^{\ast }\Vert }^2}+\eta {\displaystyle \sum _{i=1}^n\Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert \Vert z_i^k-x^{\ast }\Vert }\right)}{{\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }}\\ +\frac{\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \left(\frac{L}{2}{\displaystyle \sum _{i=1}^n{\Vert z_i^k-x^{\ast }\Vert }^2}+{\displaystyle \sum _{i=1}^n\Vert \left({f^{\prime }}_i\left(x^{\ast }\right)-B_i^k\right)\left(z_i^k-x^{\ast }\right)\Vert }\right)}{{\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }}\end{array}$

由于误差$\Vert z_i^k-x^{\ast }\Vert$ 是误差${\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }$ 的和的下界，因此将${\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }$ 替换为$\Vert z_i^k-x^{\ast }\Vert$ ，则有

$\begin{array}{c}\frac{\Vert x^{k+1}-x^{\ast }\Vert }{\frac{1}{n}{\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }}\le \frac{\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert L\left(1+\eta \right)}{2}{\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }+\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \eta {\displaystyle \sum _{i=1}^n\Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert }\\ +\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert {\displaystyle \sum _{i=1}^n\frac{\Vert \left({f^{\prime }}_i\left(x^{\ast }\right)-B_i^k\right)\left(z_i^k-x^{\ast }\right)\Vert }{\Vert z_i^k-x^{\ast }\Vert }}\end{array}$ (14)

由于$\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert$ 有上界，对式(14)求极限得到：

$\underset{k\to \infty }{\lim }\frac{\Vert x^{k+1}-x^{\ast }\Vert }{\frac{1}{n}{\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }}=0$ 。

定理3.2的结果并不等价于经典的Q-超线性收敛的拟牛顿法，即$\underset{k\to \infty }{\lim }\Vert x^{k+1}-x^{\ast }\Vert /\Vert x^k-x^{\ast }\Vert =0$ 。虽然残差$\Vert x^k-x^{\ast }\Vert$ 的Q-超线性收敛性是不可证明的，但可以证明序列$\Vert x^k-x^{\ast }\Vert$ 存在一个超线性收敛于零的子序列且该子序列为$\Vert x^k-x^{\ast }\Vert$ 的上界。

定理3.3：假设定理3.1和定理3.2中的条件成立，迭代序列由算法3.1产生，存在$\Vert x^k-x^{\ast }\Vert$ 一个子序列并超线性收敛到零。即存在一个序列${\varsigma }^k$ ，对于所有$k\ge 0$ 满足$\Vert x^k-x^{\ast }\Vert \le {\xi }^k$ ，且序列${\xi }^k$ 以超线性速率收敛到零，即有

$\underset{k\to \infty }{\lim }\frac{{\varsigma }^{k+1}}{{\varsigma }^k}=0$

证明：见文[14]。

4. Broyden修正不精确增量拟牛顿法的收敛性分析

本节基于第三节的内容，进一步证明了Hilbert空间中增量型不精确拟牛顿算法的局部收敛性。

增量型不精确Broyden算法

若$B_i^k$ 的迭代公式由Broyden修正给出，得到算法4.1：

算法4.1增量型不精确Broyden算法

步0：给出初始迭代点$x^0\in X$ 和初始迭代算子${\left\{B_i^0\right\}}_{i=1}^n$ ，其中$x^0$ 与$x^{\ast }$ 充分接近，算子${\left\{B_i^0\right\}}_{i=1}^n$ 与${\left\{{f^{\prime }}_i\left(x^0\right)\right\}}_{i=1}^n$ 也充分接近，并给出合理的容差范围；

步1：设$z_1^0=z_2^0=\cdots =z_n^0=x^0$ ；

步2：设$g^0=\frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(x^0\right)}$ ，$\left({\tilde{B}}^0\right)=\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^0}$ ；

步3：对于$k=0,1,\cdots$ 做循环更新直到$\left\{x^k\right\}$ 收敛；

3.1设$i_k=\left(k\mathrm{mod}n\right)+1$ ，是对于所有k做循环选择需要满足的重要索引，

3.2计算$x^{k+1}=x^k+\Delta x^k$ ，其中$\Delta x^k$ 为非精确求解得到并满足

$r^k={\tilde{B}}^k\Delta x^k+g^k$ ，$\frac{\Vert r^k\Vert }{\Vert g^k\Vert }\le {\eta }^k$ ，${\eta }^k\in \left[0,1\right)$

3.3当$i=i_k$ 时，计算$s_{i_k}^{k+1},y_{i_k}^{k+1},B_{i_k}^{k+1}$ ，其中

$s_i^k=z_i^{k+1}-z_i^k$ ，$y_i^k=f_i\left(z_i^{k+1}\right)-f_i\left(z_i^k\right)$ ，$B_i^{k+1}=B_i^k+\frac{\left(y_i^k-B_i^k{s}_i^k\right)\otimes s_i^k}{\langle s_i^k,s_i^k\rangle }$

3.4更新${\tilde{B}}^{k+1}$ 和有关函数信息表，其中

$\{\begin{array}{l}{z}_{i_k}^{k+1}=x^{k+1}i=i_k\\ z_i^{k+1}=z_i^{k}i\ne i_k\end{array}$ $\{\begin{array}{l}{f}_{i_k}\left(z_i^{k+1}\right)=f_{i_k}\left(x^{k+1}\right)i=i_k\\ f_i\left(z_i^{k+1}\right)=f_i\left(z_i^k\right)i\ne i_k\end{array}$ $\{\begin{array}{l}{\tilde{B}}^{k+1}={\tilde{B}}^k+\frac{1}{n}\left(B_{i_k}^{k+1}-B_{i_k}^k\right)i=i_k\\ g^{k+1}=g^k+\frac{1}{n}\left(f_{i_k}\left(z_{i_k}^{k+1}\right)-f_{i_k}\left(z_{i_k}^k\right)\right)i=i_k\\ B_i^{k+1}=B_i^{k}i\ne i_k\end{array}$

由第三节内容可证得算法4.1的线性收敛定理如下：

定理4.1：$X,Y$ 是Hilbert空间，$f_i:X\to Y$ 是非线性算子，在满足所有假设条件下且$\left\{{\tilde{B}}^k\right\}$ 可逆。L为Lipschitz常数。控制序列$\left\{{\eta }^k\right\}$ 满足${\eta }^k\in \left[0,\eta \right)$ ，$0<\eta <1$ ，存在$\epsilon >0$ 和$\eta >0$ ，当

$\epsilon <\frac{1}{\Vert {f^{\prime }}_i{\left(x^{\ast }\right)}^{-1}\Vert }$

且

$\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \left(\frac{L\left(\eta +1\right)}{2}\epsilon +\eta \Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert +\epsilon \right)<1$

时，若$x^0\in X$ 与$B_i^0$ 满足$\Vert x^0-x^{\ast }\Vert \le \epsilon$ 且$\Vert B_i^0-{f^{\prime }}_i\left(x^{\ast }\right)\Vert \le \epsilon$ ，则由算法4.1产生的迭代点列$\left\{x^k\right\}$ 至少Q-线性收敛于$x^{\ast }$ 。

证明：由定理3.1证明可知，存在${\epsilon }^1>0$ 和${\eta }^1>0$ ，使得$\Vert x^0-x^{\ast }\Vert \le {\epsilon }^1$ ，$\Vert B_i^k-{f^{\prime }}_i\left(x^{\ast }\right)\Vert \le {\epsilon }^1$ ，对任意$k\in N$ 有$\Vert x^{k+1}-x^{\ast }\Vert \le r^1\Vert x^k-x^{\ast }\Vert$ ，其中$r^1\in \left(0,1\right)$ 。若初始迭代点$x^0$ 满足$\Vert x^0-x^{\ast }\Vert \le \epsilon <{\epsilon }^1$ 且初始迭代算子$B_i^0$ 满足$\Vert B_i^0-{f^{\prime }}_i\left(x^{\ast }\right)\Vert \le \epsilon <{\epsilon }^1$ ，则式子$\Vert x^t-x^{\ast }\Vert \le {\epsilon }^1$ ，$\Vert B_i^t-{f^{\prime }}_i\left(x^{\ast }\right)\Vert \le {\epsilon }^1$ ，对于$t=0$ 是成立的。接下来，将采用归纳法，证明上述两个式子对任意情况的t均成立。假设对于$t=0,1,\cdots ,k\in N$ 时，有$\Vert x^t-x^{\ast }\Vert \le {\epsilon }^1$ ，$\Vert B_i^t-{f^{\prime }}_i\left(x^{\ast }\right)\Vert \le {\epsilon }^1$ 成立，又

$\begin{array}{c}\Vert B_i^{t+1}-{f^{\prime }}_i\left(x^{\ast }\right)\Vert =\Vert B_i^t+\frac{\left(y_i^t-B_i^t{s}_i^t\right)\otimes s_i^t}{\langle s_i^t,s_i^t\rangle }-{f^{\prime }}_i\left(x^{\ast }\right)\Vert \\ =\Vert \left(B_i^t-{f^{\prime }}_i\left(x^{\ast }\right)\right)\left(I-\frac{s_i^t\otimes s_i^t}{\langle s_i^t,s_i^t\rangle }\right)+\frac{\left(y_i^t-{f^{\prime }}_i\left(x^{\ast }\right)s_i^t\right)\otimes s_i^t}{\langle s_i^t,s_i^t\rangle }\Vert \\ \le \Vert B_i^t-{f^{\prime }}_i\left(x^{\ast }\right)\Vert \Vert I-\frac{s_i^t\otimes s_i^t}{\langle s_i^t,s_i^t\rangle }\Vert +\frac{\Vert \left(y_i^t-{f^{\prime }}_i\left(x^{\ast }\right)s_i^t\right)\otimes s_i^t\Vert }{\langle s_i^t,s_i^t\rangle }\end{array}$ (15)

由X的内积的定义，有

$\Vert I-\frac{s_i^t\otimes s_i^t}{\langle s_i^t,s_i^t\rangle }\Vert =1$

利用归纳假设并由定理3.1的证明过程可知

$\Vert x^{t+1}-x^{\ast }\Vert \le r^1\Vert x^t-x^{\ast }\Vert ,t=0,1,\cdots ,k$ (16)

由上式(16)以及${f^{\prime }}_i\left(x^{\ast }\right)$ 的局部Lipschitz连续性有对于$t=0,1,\cdots ,k$ ，

$\begin{array}{c}\Vert \left(y_i^t-{f^{\prime }}_i\left(x^{\ast }\right)s_i^t\right)\otimes s_i^t\Vert \le \Vert s_i^t\Vert \Vert y_i^t-{f^{\prime }}_i\left(x^{\ast }\right)s_i^t\Vert \\ \le \Vert {f^{\prime }}_i\left(x^t+{\tau }_i^t{s}_i^t\right)-{f^{\prime }}_i\left(x^{\ast }\right)\Vert {\Vert s_i^t\Vert }^2\\ \le L\left({\tau }_i^t\Vert x^{t+1}-x^{\ast }\Vert +\left(1-{\tau }_i^t\right)\Vert x^t-x^{\ast }\Vert \right){\Vert s_i^t\Vert }^2\\ \le L\Vert x^t-x^{\ast }\Vert {\Vert s_i^t\Vert }^2\end{array}$

由${f^{\prime }}_i\left(x^{\ast }\right)$ 的连续性和中值定理可得${\tau }_i^t\in \left[0,1\right]$ ，L为Lipschiz常数。

令

$\epsilon ={\epsilon }^1{\left(1+2L+2L\left(n-1\right)r^1+2L{\left(r^1\right)}^2\right)}^{-1}$

显然$\epsilon <{\epsilon }^1$ ，对于$t=0,1,\cdots ,k$ 有

$\Vert x^{t+1}-x^{\ast }\Vert \le r^1\Vert x^t-x^{\ast }\Vert \le \cdots \le {\left(r^1\right)}^{\left[\frac{t}{n}\right]+1}\Vert x^0-x^{\ast }\Vert \le {\left(r^1\right)}^{\left[\frac{t}{n}\right]+1}\epsilon$

故

$\Vert B_i^{t+1}-{f^{\prime }}_i\left(x^{\ast }\right)\Vert \le \Vert B_i^t-{f^{\prime }}_i\left(x^{\ast }\right)\Vert +L\Vert x^t-x^{\ast }\Vert \le \Vert B_i^t-{f^{\prime }}_i\left(x^{\ast }\right)\Vert +2L\Vert x^t-x^{\ast }\Vert$ (17)

对式(17)两边进行求和可得

$\begin{array}{c}\Vert B_i^{k+1}-{f^{\prime }}_i\left(x^{\ast }\right)\Vert \le \Vert B_i^0-{f^{\prime }}_i\left(x^{\ast }\right)\Vert +{\displaystyle \sum _{t=0}^{k}2L\Vert x^t-x^{\ast }\Vert }\\ \le \Vert B_i^0-{f^{\prime }}_i\left(x^{\ast }\right)\Vert +{\displaystyle \sum _{t=0}^{k}2L{\left(r^1\right)}^{\left[\frac{t-1}{n}\right]+1}\epsilon }\\ \le \epsilon +2L\epsilon \left(1+\left(n-1\right)r^1+{\left(r^1\right)}^2\right)\\ =\epsilon \left(1+2L+2L\left(n-1\right)r^1+2L{\left(r^1\right)}^2\right)={\epsilon }^1\end{array}$

这说明$\Vert x^t-x^{\ast }\Vert \le {\epsilon }^1$ ，$\Vert B_i^t-{f^{\prime }}_i\left(x^{\ast }\right)\Vert \le {\epsilon }^1$ 对于所有的k都成立，结合定理3.1有

$\Vert x^{k+1}-x^{\ast }\Vert \le {\left(r^1\right)}^{\left[\frac{k}{n}\right]+1}\Vert x^0-x^{\ast }\Vert <{\epsilon }^1$

该算法的线性收敛得到证明。

定理4.2：在定理4.1的假设条件下，初始迭代算子$B_i^0$ 满足$B_i^0-{f^{\prime }}_i\left(x^{\ast }\right)$ 是Hilbert-Schmidt算子且$\Vert r_i^k\Vert =o\left(\Vert f_i\left(z_i^{k+1}\right)\Vert \right)$ 。则存在$\epsilon >0$ 使得当$x^0$ 和$B_i^0$ 满足$\Vert x^0-x^{\ast }\Vert \le \epsilon$ 和$\Vert B_i^0-{f^{\prime }}_i\left(x^{\ast }\right)\Vert \le \epsilon$ 时，算法4.1产生的残差序列$\Vert x^k-x^{\ast }\Vert$ 满足：

$\underset{k\to \infty }{\lim }\frac{\Vert x^k-x^{\ast }\Vert }{\frac{1}{n}\left(\Vert x^{k-1}-x^{\ast }\Vert +\cdots +\Vert x^{k-n}-x^{\ast }\Vert \right)}=0$

证明：由式(15)有

$\begin{array}{c}{B}_i^{k+1}-{f^{\prime }}_i\left(x^{\ast }\right)=B_i^k-{f^{\prime }}_i\left(x^{\ast }\right)+\frac{\left(y_i^t-B_i^t{s}_i^t\right)\otimes s_i^t}{\langle s_i^t,s_i^t\rangle }\\ =\left(B_i^k-{f^{\prime }}_i\left(x^{\ast }\right)\right)\left(I-\frac{s_i^k\otimes s_i^k}{\langle s_i^k,s_i^k\rangle }\right)+\frac{\left(y_i^k-{f^{\prime }}_i\left(x^{\ast }\right)s_i^k\right)\otimes s_i^k}{\langle s_i^k,s_i^k\rangle }\end{array}$ (18)

令$D_k=B_i^k-{f^{\prime }}_i\left(x^{\ast }\right)\in B\left(X,Y\right)$ ，$e_k=\frac{s_i^k}{\Vert s_i^k\Vert }\in X$ ，$d_k=\frac{y_i^k-{f^{\prime }}_i\left(x^{\ast }\right)s_i^k}{\Vert s_i^k\Vert }\in Y$ ，则式(18)可简化为

$D_{k+1}=D_k\left(I-e_k\otimes e_k\right)+d_k\otimes e_k$

由引理2.1中的性质(i)~(iv)和$\Vert e_k\Vert =1$ ，可以简化$D_{k+1}{}^{\ast }{D}_{k+1}\in B\left(Y,Y\right)$ 如下：

$\begin{array}{c}{D}_{k+1}^{\ast }{D}_{k+1}=\left(\left(I-e_k\otimes e_k\right)D_k^{\ast }+e_k\otimes d_k\right)\left(D_k\left(I-e_k\otimes e_k\right)+d_k\otimes e_k\right)\\ =\left(I-e_k\otimes e_k\right)D_k^{\ast }{D}_k\left(I-e_k\otimes e_k\right)+\left(e_k\otimes d_k\right)\left(D_k-D_k{e}_k\otimes e_k\right)\\ +\left(I-e_k\otimes e_k\right)D_k^{\ast }{d}_k\otimes e_k+{\Vert d_k\Vert }^2{e}_k\otimes e_k\\ =D_k{}^{\ast }{D}_k-\left(e_k\otimes D_k^{\ast }{D}_k{e}_k+D_k^{\ast }{D}_k{e}_k\otimes e_k\right)+{\Vert D_k{e}_k\Vert }^2{e}_k\otimes e_k\\ +e_k\otimes D_k^{\ast }{d}_k+D_k^{\ast }{d}_k\otimes e_k+\left({\Vert d_k\Vert }^2-2\langle d_k,D_k{e}_k\rangle e_k\otimes e_k\right)\end{array}$ (19)

通过假设，$D_1$ 是一个Hilbert-Schmidt算子，即对于$X$ 存在${\left\{e_i\right\}}_{i\in I}$ 的标准正交基使得

${\displaystyle \sum _{i\in I}\langle e_i,D_1{}^{\ast }{D}_1{e}_i\rangle }<\infty$

在式(19)中从$D_k^{\ast }{D}_k$ 到$D_{k+1}^{\ast }{D}_{k+1}$ 的每一个修正都由秩为1的算子的有限和给出。因此，根据引理2.2知所有算子$D_k^{\ast }{D}_k$ ，$k\in N$ ，的迹$tr\left(D_k^{\ast }{D}_k\right)$ 是有限的。通过$tr$ 和$tr\left(x_1\otimes x_2\right)=\langle x_1,x_2\rangle$ 的线性性质，对式(19)在两侧取迹进行化简得到：

$tr\left(D_{k+1}^{\ast }{D}_{k+1}\right)=tr\left(D_k^{\ast }{D}_k\right)-{\Vert D_k{e}_k\Vert }^2+{\Vert d_k\Vert }^2$ (20)

连续使用式(20)可得

$tr\left(D_{k+1}^{\ast }{D}_{k+1}\right)=tr\left(D_1^{\ast }{D}_1\right)+{\displaystyle \sum _{i=1}^k\left({\Vert d_i\Vert }^2-{\Vert D_i{e}_i\Vert }^2\right)}$ (21)

根据定义$tr\left(D_{k+1}^{\ast }{D}_{k+1}\right)$ 是范数之和是非负的，则有：

${\displaystyle \sum _{i=1}^k{\Vert D_i{e}_i\Vert }^2}\le tr\left(D_1^{\ast }{D}_1\right)+{\displaystyle \sum _{i=1}^k{\Vert d_i\Vert }^2}$ (22)

在$f_i$ 可微的情况下，可以使用Lipschitz常数$L>0$ 和[15]中的中值定理知对$\Vert d_k\Vert$ 进行估计

$\begin{array}{c}\Vert d_k\Vert =\Vert f_i\left(x^{k+1}\right)-f_i\left(x^k\right)-{f^{\prime }}_{i{x}^{\ast }}\left(x^{k+1}-x^k\right)\Vert {\Vert x^{k+1}-x^k\Vert }^{-1}\\ \le L\Vert x^k-x^{\ast }\Vert \end{array}$

利用线性收敛速度，得到对于某个$\kappa \in \left(0,1\right)$ ，对所有的$k\in N$ 有

$\begin{array}{c}{\displaystyle \sum _{i=0}^k{\Vert d_i\Vert }^2}\le {\displaystyle \sum _{i=0}^k{L}^2{\Vert x^i-x^{\ast }\Vert }^2}\le L^2{\Vert x^0-x^{\ast }\Vert }^2{\displaystyle \sum _{i=0}^{k-1}{\left({\kappa }^2\right)}^i}\\ \le L^2\Vert x^0-x^{\ast }\Vert {\left(1-{\kappa }^2\right)}^{-1}\end{array}$

因此，式(22)中左侧不等式的和也是有限的，即

${\displaystyle \sum _{i=1}^k{\Vert D_i{e}_i\Vert }^2}<\infty$

并且得到

$\underset{k\to \infty }{\lim }\Vert D_k{e}_k\Vert =\underset{k\to \infty }{\lim }\frac{\Vert \left(B_i^k-{f^{\prime }}_i\left(x^{\ast }\right)\right)s_i^k\Vert }{\Vert s_i^k\Vert }=0$ (23)

式(23)为Dennis-More条件[16]。已知其在有限维情况下是超线性收敛的。为了达到在无限维情况下的目的有，

$\gamma \frac{\Vert x^{k+1}-x^{\ast }\Vert }{\frac{1}{n}{\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }}\le \frac{\Vert {f^{\prime }}_i\left(x^{\ast }\right)\left(x^{k+1}-x^{\ast }\right)\Vert }{\frac{1}{n}{\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }}\le n\frac{\Vert {f^{\prime }}_i\left(x^{\ast }\right)\left(x^{k+1}-x^{\ast }\right)\Vert }{\Vert z_i^k-x^{\ast }\Vert }\le 2n\frac{\Vert \left(B_i^k-{f^{\prime }}_i\left(x^{\ast }\right)\right)s_i^k\Vert }{\Vert s_i^k\Vert }+L{\Vert z_i^k-x^{\ast }\Vert }^2$ (24)

其中第一个不等式由假设3得到，第二个不等式由误差$\Vert z_i^k-x^{\ast }\Vert$ 是误差${\displaystyle \sum _{i=1}^n\Vert z_i^k-x^{\ast }\Vert }$ 的和的下界得到，第三个不等式由文[9]中定理3.1的证明可知，并结合式(23)，当$k\to \infty$ 时，有

$\underset{k\to \infty }{\lim }\frac{\Vert x^k-x^{\ast }\Vert }{\frac{1}{n}\left(\Vert x^{k-1}-x^{\ast }\Vert +\cdots +\Vert x^{k-n}-x^{\ast }\Vert \right)}=0$ 。

5. 应用

针对非线性算子方程的高效求解问题，考虑采用具有增量型不精确Broyden方法。参见[17]知可将非线性积分方程如下表示：

X为Hilbert空间，Y为Banach空间，$G:X\to Y$ 是非线性算子，$V:Y\to X$ 是线性算子。对于给定$h\in Y$ ，有最优解$x^{\ast }$ 满足

$x^{\ast }-VG{x}^{\ast }=h$ (25)

定理5.1：设$X,Y$ 分别是Hilbert空间和Banach空间，在$B_{\delta }\left(x^{\ast }\right)$ 内，$G:X\to Y$ 是Fréchet可微的且导数${G^{\prime }}_{x^{\ast }}$ 满足Lipschitz连续性，$V\in B\left(Y,X\right)$ ，且对任意的$x\in X$ ，$V\circ {G^{\prime }}_{x^{\ast }}:X\to X$ 是Hilbert-Schmidt算子，且$V\circ {G^{\prime }}_{x^{\ast }}$ 的特征值不是1，$\Vert r_i^k\Vert =o\left(\Vert f_i\left(z_i^{k+1}\right)\Vert \right)$ 。则存在$\epsilon >0$ 和$\eta >0$ ，当

$\epsilon <\frac{1}{\Vert {f^{\prime }}_i{\left(x^{\ast }\right)}^{-1}\Vert }$ 且$\Vert {\left(\frac{1}{n}{\displaystyle \sum _{i=1}^n{B}_i^k}\right)}^{-1}\Vert \left(\frac{L\left(\eta +1\right)}{2}\epsilon +\eta \Vert {f^{\prime }}_i\left(x^{\ast }\right)\Vert +\epsilon \right)<1$ ，

若初始迭代点$x^0\in X$ 满足$\Vert x^0-x^{\ast }\Vert \le \epsilon$ ，初始迭代算子$B_i^0\in B\left(X,X\right)$ 且$B_i^0=I-v_i{g^{\prime }}_i\left(x^0\right)$ 时，算法4.1产生的迭代点列超线性收敛到$x^{\ast }$ 。

证明：定义$F\left(x\right)=\frac{1}{n}{\displaystyle \sum _{i=1}^n{f}_i\left(x\right)}$ 且$f_i\left(x\right):X\to X$ 为

$f_i\left(x\right)=x-v_i{g}_{i}x-h$

并假设$f_i$ 是$f_i$ -可微的，则

${f^{\prime }}_i\left(x\right)=I-v_i{g^{\prime }}_i\left(x\right)$

在满足定理5.1的条件下，存在$m>0$ 对于所有的$u\in U$ 有

$\Vert {f^{\prime }}_i\left(x^{\ast }\right)\left(u\right)\Vert =\Vert \left(I-v_i{g^{\prime }}_i\left(x^{\ast }\right)\right)u\Vert \ge m\Vert u\Vert$ 。

由$B_i^0=I-v_i{g^{\prime }}_i\left(x^0\right)$ 有

$B_i^0-{f^{\prime }}_i\left(x^{\ast }\right)=I-v_i{g^{\prime }}_i\left(x^0\right)-I+v_i{g^{\prime }}_i\left(x^{\ast }\right)=v_i\left({g^{\prime }}_i\left(x^{\ast }\right)-{g^{\prime }}_i\left(x^0\right)\right)$ (26)

和对于某些常数$\kappa >0$ 有

$\Vert B_i^0-{f^{\prime }}_i\left(x^{\ast }\right)\Vert \le \Vert v_i\Vert \Vert {g^{\prime }}_i\left(x^{\ast }\right)-{g^{\prime }}_i\left(x^0\right)\Vert \le \Vert v_i\Vert \kappa \Vert x^{\ast }-x^0\Vert$ ，

因此，若$\Vert x^{\ast }-x^0\Vert$ 很小，则$B_i^0-{f^{\prime }}_i\left(x^{\ast }\right)$ 也很小。此外，由假设与Hilbert-Schmidt算子的可加性，证明式(26)是Hilbert-Schmidt算子。因此，由定理4.2可得到超线性收敛速度结果。

基金项目

这项研究由黑龙江省科研业务费一般项目(项目编号：1452MSYYB007)资助。

NOTES

^*通讯作者。