求解带扰动的线性方程组的贪婪随机Kaczmarz方法

摘要

当相容的线性代数方程组的右端向量发生扰动时，给出了由贪婪随机Kaczmarz方法所产生的迭代解与原线性代数方程组的最小范数解之间的期望误差的上界，并说明了随着迭代步数的增长，该期望解误差以线性速率下降至一个给定阈值。数值实验表明，该阈值能够很好地估计贪婪随机Kaczmarz方法的迭代解误差所能达到的最小值。

关键词

Kaczmarz方法; 线性方程组; 扰动; 随机迭代; 收敛性质

对于系数矩阵为$\mathit{A}\in {\mathbf{C}}^{m\times n}$且右端向量为$\mathit{b}\in {\mathbf{C}}^m$的大规模相容线性代数方程组

$$\mathit{A}\mathit{x}=\mathit{b}$$

（1）

的求解，Kaczmarz方法^［1］是经典的行处理迭代方法，在信号与图像处理领域有着广泛的应用。其每步迭代只需按照给定的循环顺序选取系数矩阵的某一行，并将当前迭代向量正交投影至由该行所形成的超平面上。Strohmer等^［2］提出按照与系数矩阵每一行的欧氏范数平方成比例的概率准则随机选取系数矩阵的行，得到了收敛更为快速的随机Kaczmarz方法。若用${\left(\cdot \right)}^{\mathrm{*}}$表示相应矩阵或向量的共轭转置，则当初始迭代向量在${\mathit{A}}^{\mathrm{*}}$的列空间中时，随机Kaczmarz方法期望线性收敛^［2-5］到线性代数方程组（1）的最小欧氏范数解${\mathit{x}}_{\star }={\mathit{A}}^{†}\mathit{b}$，其中${\mathit{A}}^{†}$表示系数矩阵$\mathit{A}$的Moore-Penrose伪逆。当线性代数方程组（1）的右端向量发生扰动时，Needell^［6］给出了随机Kaczmarz方法的期望解误差的上界，并说明了随着迭代步数的增长，随机Kaczmarz方法的期望解误差会以线性速率下降至一个误差阈值。之后，Zouzias等^［7］对Needell所提出的期望解误差的上界进行了改进。

影响随机Kaczmarz方法收敛速率的关键在于其中所蕴含的用于选取每步迭代所需调用的系数矩阵行的概率准则。为了提高随机Kaczmarz方法的收敛速率，Bai等 ^［8-9］提出了一个可以获取每步迭代中残向量的模较大分量的概率准则，并基于该概率准则构造出了贪婪随机Kaczmarz方法。当初始迭代向量在${\mathit{A}}^{\mathrm{*}}$的列空间时，贪婪随机Kaczmarz方法所产生的迭代序列${\left\{{\mathit{x}}_k\right\}}_{k=\mathrm{0}}^{\mathrm{\infty }}$收敛到线性代数方程组（1）的最小范数解${\mathit{x}}_{\star }={\mathit{A}}^{†}\mathit{b}$且具有期望线性收敛速率

$$E{‖{\mathit{x}}_k-{\mathit{x}}_{\star }‖}_{\mathrm{2}}\le {\left[\mathrm{1}-\frac{\mathrm{1}}{\mathrm{2}}\left(\frac{\mathrm{1}}{\gamma }{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}+\mathrm{1}\right)\frac{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{*}}\mathit{A}\right)}{{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\right]}^{\frac{k-\mathrm{1}}{\mathrm{2}}}{\left(\mathrm{1}-\frac{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{*}}\mathit{A}\right)}{{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\right)}^{\frac{\mathrm{1}}{\mathrm{2}}}{‖{\mathit{x}}_{\mathrm{0}}-{\mathit{x}}_{\star }‖}_{\mathrm{2}}$$

其中$\gamma ={‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}-\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}$，且${‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}$、${‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}$和${\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{*}}\mathit{A}\right)$分别表示矩阵$\mathit{A}$第$i$行的欧氏范数平方、矩阵$\mathit{A}$的Frobenius范数平方和矩阵${\mathit{A}}^{\mathrm{*}}\mathit{A}$的最小非零特征值。

当线性代数方程组（1）的右端向量$\mathit{b}$被加上一个不为零的扰动向量$\mathit{r}\in {\mathbf{C}}^m$时，实际求解的线性代数方程组问题将变为

$$\mathit{A}\mathit{x}=\mathit{y}$$

（2）

其中，$\mathit{y}=\mathit{b}+\mathit{r}$。若对任意矩阵$\mathit{G}\in {\mathbf{C}}^{m\times n}$和任意向量$\mathit{u}\in {\mathbf{C}}^m$，用${\mathit{G}}^{\left(i\right)}$和${\mathit{u}}^{\left(i\right)}$分别表示矩阵$\mathit{G}$的第$i$行和向量$\mathit{u}$的第$i$个分量，由于贪婪随机Kaczmarz方法的第$k$步迭代将当前迭代向量${\mathit{x}}_k$投影至超平面${\mathit{A}}^{\left(i_k\right)}\mathit{x}={\mathit{y}}^{\left(i_k\right)}$上，而线性代数方程组（1）的最小范数解${\mathit{x}}_{\star }={\mathit{A}}^{†}\mathit{b}$满足$\mathit{A}{\mathit{x}}_{\star }=\mathit{y}-\mathit{r}$，故其并不能收敛到${\mathit{x}}_{\star }$。在这种情况下，本文对贪婪随机Kaczmarz方法的期望解误差进行分析，得到了其上界，证明了随着迭代步数的增长，由贪婪随机Kaczmarz方法所产生的迭代解与原线性代数方程组（1）的最小范数解${\mathit{x}}_{\star }$之间的误差以线性速率下降至一个给定阈值。数值实验表明本文所给出的阈值能够很好地估计贪婪随机Kaczmarz方法的迭代解误差所能达到的最小值。

1 贪婪随机Kaczmarz方法

不失一般性，在本文的讨论中，总是假设系数矩阵$\mathit{A}$不存在零行，即${\mathit{A}}^{(i)}\ne \mathrm{0}$，$i=\mathrm{1,2},\dots ,m$。当线性代数方程组（1）的右端向量发生扰动时，求解线性代数方程组（2）的贪婪随机Kaczmarz方法^［8］如下：

输入：$\mathit{A}$，$\mathit{y}$，$\mathrm{𝓁}$与${\mathit{x}}_{\mathrm{0}}$

输出：${\mathit{x}}_{\mathrm{𝓁}}$

1： for $k=\mathrm{0,1},\dots ,\mathrm{𝓁}-\mathrm{1}$ do

2： 计算

$${\epsilon }_k=\frac{\mathrm{1}}{\mathrm{2}}\left(\frac{\mathrm{1}}{{‖\mathit{y}-\mathit{A}{\mathit{x}}_k‖}_{\mathrm{2}}^{\mathrm{2}}}\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{\frac{{\left|{\mathit{y}}^{(i)}-{\mathit{A}}^{(i)}{\mathit{x}}_k\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}\right\}+\frac{\mathrm{1}}{{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\right)$$

3： 确定正整数指标集

$$U_k=\left\{i|{\left|{\mathit{y}}^{(i)}-{\mathit{A}}^{(i)}{\mathit{x}}_k\right|}^{\mathrm{2}}\ge {\epsilon }_k{‖\mathit{y}-\mathit{A}{\mathit{x}}_k‖}_{\mathrm{2}}^{\mathrm{2}}{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}\right\}$$

4： 计算向量${\tilde{\mathit{r}}}_k\in {\mathbf{C}}^m$的第$i$个分量

$${{\tilde{\mathit{r}}}_k}^{(i)}=\left\{\begin{array}{ll}{\mathit{y}}^{(i)}-{\mathit{A}}^{(i)}{\mathit{x}}_k,& \hspace{1em}\mathrm{如}\mathrm{果}\mathrm{i}\in U_k\\ \mathrm{0},& \hspace{1em}\mathrm{否}\mathrm{则}\end{array}\right.$$

5： 按照概率$P_{\mathrm{r}}(\mathrm{r}\mathrm{o}\mathrm{w}=i_k)=\frac{{\left|{{\tilde{\mathit{r}}}_k}^{(i_k)}\right|}^{\mathrm{2}}}{{‖{\tilde{\mathit{r}}}_k‖}_{\mathrm{2}}^{\mathrm{2}}}$选取$i_k\in U_k$

6： 令${\mathit{x}}_{k+\mathrm{1}}={\mathit{x}}_k+\frac{\left({\mathit{y}}^{(i_k)}-{\mathit{A}}^{(i_k)}{\mathit{x}}_k\right)}{{‖{\mathit{A}}^{(i_k)}‖}_{\mathrm{2}}^{\mathrm{2}}}{\left({\mathit{A}}^{(i_k)}\right)}^{\mathrm{*}}$

7： endfor

令$R\left(\mathit{A}\right)$和$R{\left(\mathit{A}\right)}^{\perp }$分别为系数矩阵$\mathit{A}$的像空间和其像空间的正交补子空间，则有$\mathit{r}={\mathit{r}}_{R(\mathit{A})}+{\mathit{r}}_{R{(\mathit{A})}^{\perp }}$，其中${\mathit{r}}_{R(\mathit{A})}$和${\mathit{r}}_{R{(\mathit{A})}^{\perp }}$分别表示向量$\mathit{r}$在$R\left(\mathit{A}\right)$和$R{\left(\mathit{A}\right)}^{\perp }$上的正交投影。若线性代数方程组（1）右端向量的扰动$\mathit{r}$在系数矩阵$\mathit{A}$的像空间$R\left(\mathit{A}\right)$中，则线性代数方程组（2）等价于线性代数方程组

$$\mathit{A}\mathit{x}=\mathit{b}+{\mathit{r}}_{R(\mathit{A})}$$

（3）

易知线性代数方程组（3）是相容的且其最小范数解为${\tilde{\mathit{x}}}_{\star }={\mathit{A}}^{†}\left(\mathit{b}+{\mathit{r}}_{R(\mathit{A})}\right)$。此时，若初始迭代向量在${\mathit{A}}^{\mathrm{*}}$的列空间中，则求解线性代数方程组（2）的贪婪随机Kaczmarz方法所产生的迭代序列${\left\{{\mathit{x}}_k\right\}}_{k=\mathrm{0}}^{\mathrm{\infty }}$期望线性收敛到${\tilde{\mathit{x}}}_{\star }$。

2 误差分析

与求解原线性代数方程组（1）的贪婪随机Kaczmarz方法的分析^［8］类似，根据求解线性代数方程组（2）的贪婪随机Kaczmarz方法中${\epsilon }_k$的定义可知，对于$k=\mathrm{1,2},\dots$，由于

$${\mathit{y}}^{\left(i_{k-\mathrm{1}}\right)}-{\mathit{A}}^{\left(i_{k-\mathrm{1}}\right)}{\mathit{x}}_k={\mathit{y}}^{\left(i_{k-\mathrm{1}}\right)}-{\mathit{A}}^{\left(i_{k-\mathrm{1}}\right)}\left({\mathit{x}}_{k-\mathrm{1}}+\frac{\left({\mathit{y}}^{\left(i_{k-\mathrm{1}}\right)}-{\mathit{A}}^{\left(i_{k-\mathrm{1}}\right)}{\mathit{x}}_{k-\mathrm{1}}\right)}{{‖{\mathit{A}}^{\left(i_{k-\mathrm{1}}\right)}‖}_{\mathrm{2}}^{\mathrm{2}}}{\left({\mathit{A}}^{\left(i_{k-\mathrm{1}}\right)}\right)}^{\mathrm{*}}\right)=\mathrm{0}$$

有${\epsilon }_k{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}=\frac{\mathrm{1}}{\mathrm{2}}\frac{\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\frac{{\left|{\mathit{y}}^{(i)}-{\mathit{A}}^{(i)}{\mathit{x}}_k\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}\right)}{{\displaystyle \sum _{i=\mathrm{1}}^m}\frac{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}{{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\frac{{\left|{\mathit{y}}^{(i)}-{\mathit{A}}^{(i)}{\mathit{x}}_k\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}}+\frac{\mathrm{1}}{\mathrm{2}}=$$\frac{\mathrm{1}}{\mathrm{2}}\frac{\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\frac{{\left|{\mathit{y}}^{(i)}-{\mathit{A}}^{(i)}{\mathit{x}}_k\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}\right)}{{\displaystyle \sum _{\underset{i\ne i_{k-\mathrm{1}}}{i=\mathrm{1}}}^m}\frac{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}{{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\frac{{\left|{\mathit{y}}^{(i)}-{\mathit{A}}^{(i)}{\mathit{x}}_k\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}}+\frac{\mathrm{1}}{\mathrm{2}}\ge$

$$\frac{\mathrm{1}}{\mathrm{2}}\left(\frac{{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}{{\displaystyle \sum _{\underset{i\ne i_{k-\mathrm{1}}}{i=\mathrm{1}}}^m}{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}+\mathrm{1}\right)$$

而对于$k=\mathrm{0}$，有

$${\epsilon }_{\mathrm{0}}{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}=\frac{\mathrm{1}}{\mathrm{2}}\frac{\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\frac{{\left|{\mathit{y}}^{(i)}-{\mathit{A}}^{(i)}{\mathit{x}}_{\mathrm{0}}\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}\right)}{{\displaystyle \sum _{i=\mathrm{1}}^m}\frac{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}{{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\frac{{\left|{\mathit{y}}^{(i)}-{\mathit{A}}^{(i)}{\mathit{x}}_{\mathrm{0}}\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}}+\frac{\mathrm{1}}{\mathrm{2}}\ge \mathrm{1}$$

因此，可得引理1。

引理 1  　求解系数矩阵为$\mathit{A}\in {\mathbf{C}}^{m\times n}$且右端向量为$\mathit{y}\in {\mathbf{C}}^m$的线性代数方程组（2）的贪婪随机Kaczmarz方法的概率准则中的量${\epsilon }_k$，$k=\mathrm{0,1},\mathrm{2},\dots$，满足

$${\epsilon }_{\mathrm{0}}\ge \frac{\mathrm{1}}{{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}$$

和

$${\epsilon }_k\ge \frac{\mathrm{1}}{\mathrm{2}}\left(\frac{\mathrm{1}}{\gamma }+\frac{\mathrm{1}}{{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\right)$$，$$k=\mathrm{1,2},\dots$$

其中$\gamma ={‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}-\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}$。

当线性代数方程组（1）右端向量的扰动$\mathit{r}$在$R\left(\mathit{A}\right)$中时，若初始迭代向量在${\mathit{A}}^{\mathrm{*}}$的列空间中，则求解线性代数方程组（2）的贪婪随机Kaczmarz方法所产生的迭代向量期望线性收敛到线性代数方程组（3）的最小范数解${\tilde{\mathit{x}}}_{\star }$。对于一般的扰动情形，求解线性代数方程组（2）的贪婪随机Kaczmarz方法所产生的迭代向量与${\tilde{\mathit{x}}}_{\star }$之间的期望误差的上界可以由引理2给出。

引理 2  　如果初始迭代向量${\mathit{x}}_{\mathrm{0}}\in {\mathbf{C}}^n$在${\mathit{A}}^{\mathrm{*}}$的列空间中，则贪婪随机Kaczmarz方法求解扰动后的线性代数方程组（2）所产生的迭代序列${\left\{{\mathit{x}}_k\right\}}_{k=\mathrm{0}}^{\mathrm{\infty }}$与线性代数方程组（3）的最小范数解${\tilde{\mathit{x}}}_{\star }$之间的期望误差满足

$$E{‖{\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}\le \sqrt[]{{\alpha }^{k-\mathrm{1}}{\alpha }_{\mathrm{0}}}{‖{\mathit{x}}_{\mathrm{0}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}+\sqrt[]{\frac{\beta }{\mathrm{1}-\alpha }}$$

其中

$$\begin{array}{l}\alpha =\mathrm{1}-\frac{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{*}}\mathit{A}\right)}{\mathrm{4}}\left(\frac{\mathrm{1}}{\gamma }+\frac{\mathrm{1}}{{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\right),\\ {\alpha }_{\mathrm{0}}=\mathrm{1}-\frac{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{*}}\mathit{A}\right)}{\mathrm{2}{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}},\end{array}$$

$$\begin{array}{cc}\begin{array}{l}\beta =\mathrm{2}\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\frac{{\left|{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i)}\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}\right)-\frac{{‖{\mathit{r}}_{R{(\mathit{A})}^{\perp }}‖}_{\mathrm{2}}^{\mathrm{2}}}{\mathrm{2}{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}},\\ \gamma ={‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}-\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}\end{array}& \end{array}$$

（4）

证明：　由求解线性代数方程组（2）的贪婪随机Kaczmarz方法的定义和$\mathit{A}{\tilde{\mathit{x}}}_{\star }=\mathit{b}+{\mathit{r}}_{R(\mathit{A})}$可知

$$\begin{array}{l}{\mathit{x}}_{k+\mathrm{1}}-{\tilde{\mathit{x}}}_{\star }={\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }+\frac{{\mathit{y}}^{(i_k)}-{\mathit{A}}^{(i_k)}{\mathit{x}}_k}{{‖{\mathit{A}}^{(i_k)}‖}_{\mathrm{2}}^{\mathrm{2}}}{\left({\mathit{A}}^{(i_k)}\right)}^{\mathrm{*}}=\\ {\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }+\frac{{\mathit{b}}^{(i_k)}+{\mathit{r}}_{R(\mathit{A})}^{(i_k)}-{\mathit{A}}^{(i_k)}{\mathit{x}}_k+{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i_k)}}{{‖{\mathit{A}}^{(i_k)}‖}_{\mathrm{2}}^{\mathrm{2}}}{\left({\mathit{A}}^{(i_k)}\right)}^{\mathrm{*}}=\\ \left(\mathit{I}-\frac{{\left({\mathit{A}}^{(i_k)}\right)}^{\mathrm{*}}{\mathit{A}}^{(i_k)}}{{‖{\mathit{A}}^{(i_k)}‖}_{\mathrm{2}}^{\mathrm{2}}}\right)\left({\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }\right)+\frac{{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i_k)}}{{‖{\mathit{A}}^{(i_k)}‖}_{\mathrm{2}}^{\mathrm{2}}}{\left({\mathit{A}}^{(i_k)}\right)}^{\mathrm{*}}\end{array}$$

其中$\mathit{I}$表示具有合适阶数的单位矩阵，则有

$${‖{\mathit{x}}_{k+\mathrm{1}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}={‖\left(\mathit{I}-\frac{{\left({\mathit{A}}^{(i_k)}\right)}^{\mathrm{*}}{\mathit{A}}^{(i_k)}}{{‖{\mathit{A}}^{(i_k)}‖}_{\mathrm{2}}^{\mathrm{2}}}\right)\left({\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }\right)‖}_{\mathrm{2}}^{\mathrm{2}}+\frac{{\left|{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i_k)}\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i_k)}‖}_{\mathrm{2}}^{\mathrm{2}}}$$

（5）

用$E_k$表示固定前$k$步迭代的条件期望，即$E_k\left[\cdot \right]=E\left[\cdot |i_{\mathrm{0}},i_{\mathrm{1}},\dots ,i_{k-\mathrm{1}}\right]$，其中$i_l(l=\mathrm{0,1},\dots ,k-\mathrm{1})$为第$l$步迭代所选取的行指标，则对等式（5）两边取条件期望可得

$$\begin{array}{l}{E}_k{‖{\mathit{x}}_{k+\mathrm{1}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}={‖{\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}-\\ \sum _{i_k\in U_k}\frac{{\left|{\mathit{y}}^{\left(i_k\right)}-{\mathit{A}}^{\left(i_k\right)}{\mathit{x}}_k\right|}^{\mathrm{2}}}{\sum _{i\in U_k}{\left|{\mathit{y}}^{\left(i\right)}-{\mathit{A}}^{\left(i\right)}{\mathit{x}}_k\right|}^{\mathrm{2}}}\frac{{\left|{\mathit{b}}^{\left(i_k\right)}+{\mathit{r}}_{R(\mathit{A})}^{(i_k)}-{\mathit{A}}^{\left(i_k\right)}{\mathit{x}}_k\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i_k)}‖}_{\mathrm{2}}^{\mathrm{2}}}+\\ \sum _{i_k\in U_k}\frac{{\left|{\mathit{y}}^{\left(i_k\right)}-{\mathit{A}}^{\left(i_k\right)}{\mathit{x}}_k\right|}^{\mathrm{2}}}{\sum _{i\in U_k}{\left|{\mathit{y}}^{\left(i\right)}-{\mathit{A}}^{\left(i\right)}{\mathit{x}}_k\right|}^{\mathrm{2}}}\frac{{\left|{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i_k)}\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i_k)}‖}_{\mathrm{2}}^{\mathrm{2}}}\end{array}$$

由于

$$\begin{array}{l}{\left|{\mathit{y}}^{\left(i_k\right)}-{\mathit{A}}^{\left(i_k\right)}{\mathit{x}}_k\right|}^{\mathrm{2}}={\left|{\mathit{b}}^{\left(i_k\right)}+{\mathit{r}}_{R(\mathit{A})}^{(i_k)}+{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i_k)}-{\mathit{A}}^{\left(i_k\right)}{\mathit{x}}_k\right|}^{\mathrm{2}}\le \\ {\left(\left|{\mathit{b}}^{\left(i_k\right)}+{\mathit{r}}_{R(\mathit{A})}^{(i_k)}-{\mathit{A}}^{\left(i_k\right)}{\mathit{x}}_k\right|+\left|{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i_k)}\right|\right)}^{\mathrm{2}}\le \\ \mathrm{2}{\left|{\mathit{b}}^{\left(i_k\right)}+{\mathit{r}}_{R(\mathit{A})}^{(i_k)}-{\mathit{A}}^{\left(i_k\right)}{\mathit{x}}_k\right|}^{\mathrm{2}}+\mathrm{2}{\left|{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i_k)}\right|}^{\mathrm{2}}\end{array}$$

可知

$${\left|{\mathit{b}}^{\left(i_k\right)}+{\mathit{r}}_{R(\mathit{A})}^{(i_k)}-{\mathit{A}}^{\left(i_k\right)}{\mathit{x}}_k\right|}^{\mathrm{2}}\ge \frac{\mathrm{1}}{\mathrm{2}}{\left|{\mathit{y}}^{\left(i_k\right)}-{\mathit{A}}^{\left(i_k\right)}{\mathit{x}}_k\right|}^{\mathrm{2}}-{\left|{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i_k)}\right|}^{\mathrm{2}}$$

则根据正整数指标集${\mathrm{U}}_k$的定义可得

$$\begin{array}{l}{E}_k{‖{\mathit{x}}_{k+\mathrm{1}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}\le {‖{\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}-\\ \frac{\mathrm{1}}{\mathrm{2}}\sum _{i_k\in U_k}\frac{{\left|{\mathit{y}}^{\left(i_k\right)}-{\mathit{A}}^{\left(i_k\right)}{\mathit{x}}_k\right|}^{\mathrm{2}}}{\sum _{i\in U_k}{\left|{\mathit{y}}^{\left(i\right)}-{\mathit{A}}^{\left(i\right)}{\mathit{x}}_k\right|}^{\mathrm{2}}}\frac{{\left|{\mathit{y}}^{\left(i_k\right)}-{\mathit{A}}^{\left(i_k\right)}{\mathit{x}}_k\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i_k)}‖}_{\mathrm{2}}^{\mathrm{2}}}+\\ \mathrm{2}\sum _{i_k\in U_k}\frac{{\left|{\mathit{y}}^{\left(i_k\right)}-{\mathit{A}}^{\left(i_k\right)}{\mathit{x}}_k\right|}^{\mathrm{2}}}{\sum _{i\in U_k}{\left|{\mathit{y}}^{\left(i\right)}-{\mathit{A}}^{\left(i\right)}{\mathit{x}}_k\right|}^{\mathrm{2}}}\frac{{\left|{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i_k)}\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i_k)}‖}_{\mathrm{2}}^{\mathrm{2}}}\le \\ {‖{\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}-\frac{\mathrm{1}}{\mathrm{2}}{\epsilon }_k{‖\mathit{y}-\mathit{A}{\mathit{x}}_k‖}_{\mathrm{2}}^{\mathrm{2}}+\\ \mathrm{2}\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\frac{{\left|{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i)}\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}\right)\end{array}$$

对于在矩阵${\mathit{A}}^{\mathrm{*}}$的像空间$R({\mathit{A}}^{\mathrm{*}})$中的任意向量$\mathit{u}$，有不等式

$${‖\mathit{A}\mathit{u}‖}_{\mathrm{2}}^{\mathrm{2}}\ge {\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{*}}\mathit{A}\right){‖\mathit{u}‖}_{\mathrm{2}}^{\mathrm{2}}$$

（6）

成立。利用该不等式，通过引理1、向量$\mathit{b}+{\mathit{r}}_{R(\mathit{A})}-\mathit{A}{\mathit{x}}_k=\mathit{A}\left({\tilde{\mathit{x}}}_{\star }-{\mathit{x}}_k\right)\in R(\mathit{A})$和向量${\mathit{r}}_{R{(\mathit{A})}^{\perp }}$的正交性、${\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }\in R({\mathit{A}}^{\mathrm{*}})$以及$\gamma \le {‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}$可知，对于$k=\mathrm{1,2},\dots$，有

$$\begin{array}{l}{E}_k{‖{\mathit{x}}_{k+\mathrm{1}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}\le {‖{\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}-\frac{\mathrm{1}}{\mathrm{4}}\left(\frac{\mathrm{1}}{\gamma }+\frac{\mathrm{1}}{{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\right){‖\mathit{y}-\mathit{A}{\mathit{x}}_k‖}_{\mathrm{2}}^{\mathrm{2}}+\mathrm{2}\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\frac{{\left|{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i)}\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}\right)=\\ {‖{\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}-\frac{\mathrm{1}}{\mathrm{4}}\left(\frac{\mathrm{1}}{\gamma }+\frac{\mathrm{1}}{{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\right)\left({‖\mathit{b}+{\mathit{r}}_{R(\mathit{A})}-\mathit{A}{\mathit{x}}_k‖}_{\mathrm{2}}^{\mathrm{2}}+{‖{\mathit{r}}_{R{(\mathit{A})}^{\perp }}‖}_{\mathrm{2}}^{\mathrm{2}}\right)+\mathrm{2}\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\frac{{\left|{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i)}\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}\right)\le \\ \left[\mathrm{1}-\frac{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{*}}\mathit{A}\right)}{\mathrm{4}}\left(\frac{\mathrm{1}}{\gamma }+\frac{\mathrm{1}}{{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\right)\right]{‖{\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}+\\ \mathrm{2}\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\frac{{\left|{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i)}\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}\right)-\frac{\mathrm{1}}{\mathrm{4}}\left(\frac{\mathrm{1}}{\gamma }+\frac{\mathrm{1}}{{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\right){‖{\mathit{r}}_{R{(\mathit{A})}^{\perp }}‖}_{\mathrm{2}}^{\mathrm{2}}\le \\ \left[\mathrm{1}-\frac{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{*}}\mathit{A}\right)}{\mathrm{4}}\left(\frac{\mathrm{1}}{\gamma }+\frac{\mathrm{1}}{{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\right)\right]{‖{\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}+\\ \mathrm{2}\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\frac{{\left|{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i)}\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}\right)-\frac{{‖{\mathit{r}}_{R{(\mathit{A})}^{\perp }}‖}_{\mathrm{2}}^{\mathrm{2}}}{\mathrm{2}{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\end{array}$$

而对于$k=\mathrm{0}$，有

$$\begin{array}{l}E{‖{\mathit{x}}_{\mathrm{1}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}\le {‖{\mathit{x}}_{\mathrm{0}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}-\frac{\mathrm{1}}{\mathrm{2}{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}{‖\mathit{y}-\mathit{A}{\mathit{x}}_{\mathrm{0}}‖}_{\mathrm{2}}^{\mathrm{2}}+\\ \mathrm{2}\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\frac{{\left|{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i)}\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}\right)=\\ {‖{\mathit{x}}_{\mathrm{0}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}-\frac{\mathrm{1}}{\mathrm{2}{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\left({‖\mathit{b}+{\mathit{r}}_{R(\mathit{A})}-\mathit{A}{\mathit{x}}_{\mathrm{0}}‖}_{\mathrm{2}}^{\mathrm{2}}+{‖{\mathit{r}}_{R{(\mathit{A})}^{\perp }}‖}_{\mathrm{2}}^{\mathrm{2}}\right)+\mathrm{2}\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\frac{{\left|{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i)}\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}\right)\le \\ \left[\mathrm{1}-\frac{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{*}}\mathit{A}\right)}{\mathrm{2}{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\right]{‖{\mathit{x}}_{\mathrm{0}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}+\\ \mathrm{2}\underset{\mathrm{1}\le i\le m}{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\frac{{\left|{\mathit{r}}_{R{(\mathit{A})}^{\perp }}^{(i)}\right|}^{\mathrm{2}}}{{‖{\mathit{A}}^{(i)}‖}_{\mathrm{2}}^{\mathrm{2}}}\right)-\frac{{‖{\mathit{r}}_{R{(\mathit{A})}^{\perp }}‖}_{\mathrm{2}}^{\mathrm{2}}}{\mathrm{2}{‖\mathit{A}‖}_{\mathrm{F}}^{\mathrm{2}}}\end{array}$$

对不等式两边取期望可得对于$k=\mathrm{1,2},\dots$，有

$$E{‖{\mathit{x}}_{k+\mathrm{1}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}\le \alpha E{‖{\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}+\beta$$

而对于$k=\mathrm{0}$，有

$$E{‖{\mathit{x}}_{\mathrm{1}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}\le {\alpha }_{\mathrm{0}}{‖{\mathit{x}}_{\mathrm{0}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}+\beta$$

因此，由于$\mathrm{0}<\alpha <\mathrm{1}$，$\beta \ge \mathrm{0}$，对于$k=\mathrm{1,2},\dots$，有

$$\begin{array}{l}E{‖{\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}\le \alpha E{‖{\mathit{x}}_{k-\mathrm{1}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}+\beta \le \\ {\alpha }^{\mathrm{2}}E{‖{\mathit{x}}_{k-\mathrm{2}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}+\alpha \beta +\beta \le \cdots \le \\ {\alpha }^{k-\mathrm{1}}E{‖{\mathit{x}}_{\mathrm{1}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}+\left({\displaystyle \sum _{i=\mathrm{0}}^{k-\mathrm{2}}}{\alpha }^i\right)\beta \le \\ {\alpha }^{k-\mathrm{1}}{\alpha }_{\mathrm{0}}{‖{\mathit{x}}_{\mathrm{0}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}+\left({\displaystyle \sum _{i=\mathrm{0}}^{k-\mathrm{1}}}{\alpha }^i\right)\beta \le \\ {\alpha }^{k-\mathrm{1}}{\alpha }_{\mathrm{0}}{‖{\mathit{x}}_{\mathrm{0}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}+\frac{\beta }{\mathrm{1}-\alpha }\end{array}$$

由Jensen不等式可知

$$E{‖{\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}\le {\left(E{‖{\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}\right)}^{\frac{\mathrm{1}}{\mathrm{2}}}\le {\left({\alpha }^{k-\mathrm{1}}{\alpha }_{\mathrm{0}}{‖{\mathit{x}}_{\mathrm{0}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}^{\mathrm{2}}+\frac{\beta }{\mathrm{1}-\alpha }\right)}^{\frac{\mathrm{1}}{\mathrm{2}}}\le \sqrt[]{{\alpha }^{k-\mathrm{1}}{\alpha }_{\mathrm{0}}}{‖{\mathit{x}}_{\mathrm{0}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}+\sqrt[]{\frac{\beta }{\mathrm{1}-\alpha }}$$

基于引理2，关于求解扰动后的线性代数方程组（2）的贪婪随机Kaczmarz方法所产生的迭代近似解与原线性代数方程组（1）的最小范数解${\mathit{x}}_{\star }$之间的期望误差的上界，可以给出如下定理。

定理 1  　如果初始迭代向量${\mathit{x}}_{\mathrm{0}}\in {\mathbf{C}}^n$在${\mathit{A}}^{\mathrm{*}}$的列空间中且${\tilde{\mathit{x}}}_{\star }$为线性代数方程组（3）的最小范数解，则贪婪随机Kaczmarz方法求解扰动后的线性代数方程组（2）所产生的迭代序列${\left\{{\mathit{x}}_k\right\}}_{k=\mathrm{0}}^{\mathrm{\infty }}$与原线性代数方程组（1）的最小范数解${\mathit{x}}_{\star }={\mathit{A}}^{†}\mathit{b}$之间的期望误差满足

$$E{‖{\mathit{x}}_k-{\mathit{x}}_{\star }‖}_{\mathrm{2}}\le \sqrt[]{{\alpha }^{k-\mathrm{1}}{\alpha }_{\mathrm{0}}}{‖{\mathit{x}}_{\mathrm{0}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}+\sqrt[]{\frac{\beta }{\mathrm{1}-\alpha }}+\frac{{‖{\mathit{r}}_{R(\mathit{A})}‖}_{\mathrm{2}}}{\sqrt[]{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{*}}\mathit{A}\right)}}$$

其中，$\alpha$、${\alpha }_{\mathrm{0}}$和$\beta$如（4）式中定义。

证明：　因为${\tilde{\mathit{x}}}_{\star }-{\mathit{x}}_{\star }\in R({\mathit{A}}^{\mathrm{*}})$，则通过不等式（6）可知

$${‖{\mathit{r}}_{R(\mathit{A})}‖}_{\mathrm{2}}={‖\mathit{A}\left({\tilde{\mathit{x}}}_{\star }-{\mathit{x}}_{\star }\right)‖}_{\mathrm{2}}\ge \sqrt[]{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{*}}\mathit{A}\right)}{‖{\tilde{\mathit{x}}}_{\star }-{\mathit{x}}_{\star }‖}_{\mathrm{2}}$$

又因为有

$${‖{\mathit{x}}_k-{\mathit{x}}_{\star }‖}_{\mathrm{2}}={‖{\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }+{\tilde{\mathit{x}}}_{\star }-{\mathit{x}}_{\star }‖}_{\mathrm{2}}\le {‖{\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}+{‖{\tilde{\mathit{x}}}_{\star }-{\mathit{x}}_{\star }‖}_{\mathrm{2}}$$

成立，则由引理2可得

$$E{‖{\mathit{x}}_k-{\mathit{x}}_{\star }‖}_{\mathrm{2}}\le E{‖{\mathit{x}}_k-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}+{‖{\tilde{\mathit{x}}}_{\star }-{\mathit{x}}_{\star }‖}_{\mathrm{2}}\le \sqrt[]{{\alpha }^{k-\mathrm{1}}{\alpha }_{\mathrm{0}}}{‖{\mathit{x}}_{\mathrm{0}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}+\sqrt[]{\frac{\beta }{\mathrm{1}-\alpha }}+\frac{{‖{\mathit{r}}_{R(\mathit{A})}‖}_{\mathrm{2}}}{\sqrt[]{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{*}}\mathit{A}\right)}}$$

定理1说明了当迭代步数$k$趋于无穷时，贪婪随机Kaczmarz方法求解扰动后的线性代数方程组（2）所产生的迭代序列${\left\{{\mathit{x}}_k\right\}}_{k=\mathrm{0}}^{\mathrm{\infty }}$的期望相对解误差$E{‖{\mathit{x}}_k-{\mathit{x}}_{\star }‖}_{\mathrm{2}}/{‖{\mathit{x}}_{\star }‖}_{\mathrm{2}}$以$\sqrt[]{\alpha }$的线性速率下降至某个阈值，并给出了该阈值的估计

$$\tau =\frac{\mathrm{1}}{{‖{\mathit{x}}_{\star }‖}_{\mathrm{2}}}\left(\sqrt[]{\frac{\beta }{\mathrm{1}-\alpha }}+\frac{{‖{\mathit{r}}_{R(\mathit{A})}‖}_{\mathrm{2}}}{\sqrt[]{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{*}}\mathit{A}\right)}}\right)$$

若${\mathit{r}}_{R{(\mathit{A})}^{\perp }}$为零，则扰动后的线性代数方程组（2）即为相容的线性代数方程组（3）。因此，求解线性代数方程组（2）的贪婪随机Kaczmarz方法的迭代序列${\left\{{\mathit{x}}_k\right\}}_{k=\mathrm{0}}^{\mathrm{\infty }}$收敛到线性代数方程组（3）的最小范数解${\tilde{\mathit{x}}}_{\star }$，且其与原线性代数方程组（1）的最小范数解${\mathit{x}}_{\star }$的差趋于${\tilde{\mathit{x}}}_{\star }-{\mathit{x}}_{\star }$。此时，如果初始迭代向量在${\mathit{A}}^{\mathrm{*}}$的列空间中，则求解线性代数方程组（2）的贪婪随机Kaczmarz方法所产生的迭代序列${\left\{{\mathit{x}}_k\right\}}_{k=\mathrm{0}}^{\mathrm{\infty }}$满足$\frac{E{‖{\mathit{x}}_k-{\mathit{x}}_{\star }‖}_{\mathrm{2}}}{{‖{\mathit{x}}_{\star }‖}_{\mathrm{2}}}\le \sqrt[]{{\alpha }^{k-\mathrm{1}}{\alpha }_{\mathrm{0}}}\frac{{‖{\mathit{x}}_{\mathrm{0}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}}{{‖{\mathit{x}}_{\star }‖}_{\mathrm{2}}}+$ $\frac{{‖{\tilde{\mathit{x}}}_{\star }-{\mathit{x}}_{\star }‖}_{\mathrm{2}}}{{‖{\mathit{x}}_{\star }‖}_{\mathrm{2}}}\le \sqrt[]{{\alpha }^{k-\mathrm{1}}{\alpha }_{\mathrm{0}}}\frac{{‖{\mathit{x}}_{\mathrm{0}}-{\tilde{\mathit{x}}}_{\star }‖}_{\mathrm{2}}}{{‖{\mathit{x}}_{\star }‖}_{\mathrm{2}}}+\frac{{‖{\mathit{r}}_{R(\mathit{A})}‖}_{\mathrm{2}}}{{‖{\mathit{x}}_{\star }‖}_{\mathrm{2}}\sqrt[]{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{*}}\mathit{A}\right)}}$

若${\mathit{r}}_{R(\mathit{A})}$为零，则线性代数方程组（3）即为线性代数方程组（1），且线性代数方程组（3）的最小范数解${\tilde{\mathit{x}}}_{\star }$即为${\mathit{x}}_{\star }={\mathit{A}}^{†}\mathit{b}$。此时，如果初始迭代向量在${\mathit{A}}^{\mathrm{*}}$的列空间中，则求解线性代数方程组（2）的贪婪随机Kaczmarz方法所产生的迭代序列${\left\{{\mathit{x}}_k\right\}}_{k=\mathrm{0}}^{\mathrm{\infty }}$满足

$$\frac{E{‖{\mathit{x}}_k-{\mathit{x}}_{\star }‖}_{\mathrm{2}}}{{‖{\mathit{x}}_{\star }‖}_{\mathrm{2}}}\le \sqrt[]{{\alpha }^{k-\mathrm{1}}{\alpha }_{\mathrm{0}}}\frac{{‖{\mathit{x}}_{\mathrm{0}}-{\mathit{x}}_{\star }‖}_{\mathrm{2}}}{{‖{\mathit{x}}_{\star }‖}_{\mathrm{2}}}+\frac{\mathrm{1}}{{‖{\mathit{x}}_{\star }‖}_{\mathrm{2}}}\sqrt[]{\frac{\beta }{\mathrm{1}-\alpha }}$$

3 数值实验

通过数值实验测试贪婪随机Kaczmarz方法求解带右端项扰动的线性代数方程组（2）时的数值表现，并将所估计的阈值与贪婪随机Kaczmarz方法所产生的真实迭代解误差进行比较。

所测试的系数矩阵$\mathit{A}$分为两类：一类为利用MATLAB函数randn随机产生的元素服从标准正态分布的矩阵，矩阵维数分别为$\mathrm{200}\times \mathrm{100}\mathrm{000}$和$\mathrm{100}\mathrm{000}\times \mathrm{200}$；另一类为取自稀疏矩阵库^［10］的稀疏矩阵bibd_16_8和ash958，矩阵维数分别为$\mathrm{120}\times \mathrm{12}\mathrm{870}$和$\mathrm{958}\times \mathrm{292}$。

线性代数方程组（1）的右端向量$\mathit{b}$取为$\mathit{A}{\mathit{x}}_{\mathrm{*}}$，其中${\mathit{x}}_{\mathrm{*}}\in {\mathbf{R}}^n$是利用MATLAB函数randn随机产生的。线性代数方程组（1）的右端项的扰动向量$\mathit{r}$分为三类：一类为随机扰动，一类为在系数矩阵的像空间中的扰动，另一类为在系数矩阵的像空间的正交补空间中的扰动。这三类扰动均由MATLAB函数randn生成，并且其欧氏范数为原始右端向量$\mathit{b}$的欧氏范数的0.0005倍。由于$\mathrm{200}\times \mathrm{100}\mathrm{000}$的随机矩阵和稀疏矩阵bibd_16_8为行满秩矩阵，故其所对应的右端项扰动$\mathit{r}$一定在其像空间中。所有计算均从初始向量${\mathit{x}}_{\mathrm{0}}=\mathrm{0}$开始。

图1描绘了当线性代数方程组（1）的系数矩阵为随机产生的矩阵且右端项扰动$\mathit{r}$为随机扰动时，贪婪随机Kaczmarz方法重复运行50次所产生的相对解误差$E_{\mathrm{R}\mathrm{S}}$的中值和阈值$\tau$分别取以10为底的对数之后相对于迭代步数的曲线，其中

$$E_{\mathrm{R}\mathrm{S}}=\frac{{‖{\mathit{x}}_k-{\mathit{x}}_{\star }‖}_{\mathrm{2}}}{{‖{\mathit{x}}_{\star }‖}_{\mathrm{2}}}$$

图1 当$\mathit{m}=\mathrm{200},\mathit{n}=\mathrm{100}\mathrm{000}$和$\mathit{m}=\mathrm{100}\mathrm{000},\mathit{n}=\mathrm{200}$时，lg E_RS和lg τ相对于迭代步数的曲线

Fig.1 Pictures of lg E_RS and lg τ versus the iteration step when $\mathit{m}=\mathrm{200},\mathit{n}=\mathrm{100}\mathrm{000}$ and $\mathit{m}=\mathrm{100}\mathrm{000},\mathit{n}=\mathrm{200}$

从图1可以看出，贪婪随机Kaczmarz方法所产生的相对解误差下降至${\mathrm{10}}^{-\mathrm{3}}$左右之后不再减小，且阈值$\tau$能够很好地给出该最小值的估计。特别地，当系数矩阵为$\mathrm{200}\times \mathrm{100}\mathrm{000}$的随机矩阵时，$\tau$与真实相对解误差所能达到的最小值非常接近。

图2描绘了对于$\mathrm{100}\mathrm{000}\times \mathrm{200}$的随机产生的系数矩阵，当线性代数方程组（1）的右端项扰动$\mathit{r}$分别在系数矩阵的像空间和系数矩阵的像空间的正交补空间中时，贪婪随机Kaczmarz方法重复运行50次所产生的相对解误差的中值和阈值$\tau$分别取以10为底的对数之后相对于迭代步数的曲线。从图2可以看出，贪婪随机Kaczmarz方法所产生的相对解误差下降至${\mathrm{10}}^{-\mathrm{3}}$左右之后不再减小，且阈值$\tau$能够很好地给出该最小值的估计，特别当扰动向量$\mathit{r}$在系数矩阵的像空间中时。

图2 当$\mathit{m}=\mathrm{100}\mathrm{000},\mathit{n}=\mathrm{200}$且$\mathit{r}\in \mathit{R}\left(\mathit{A}\right)$和$\mathit{r}\in \mathit{R}{\left(\mathit{A}\right)}^{\perp }$时，lg E_RS和lg τ相对于迭代步数的曲线

Fig.2 Pictures of lg E_RS and lg τ versus the iteration step when$\mathit{m}=\mathrm{100}\mathrm{000},\mathit{n}=\mathrm{200}$,and $\mathit{r}\in \mathit{R}\left(\mathit{A}\right)$ and $\mathit{r}\in \mathit{R}{\left(\mathit{A}\right)}^{\perp }$

当线性代数方程组（1）的系数矩阵为稀疏矩阵bibd_16_8和ash958时，图3描绘了右端项扰动$\mathit{r}$为随机扰动时，贪婪随机Kaczmarz方法重复运行50次所产生的相对解误差的中值和阈值$\tau$分别取以10为底的对数之后相对于迭代步数的曲线；图4描绘了右端项扰动$\mathit{r}$分别在系数矩阵的像空间和系数矩阵的像空间的正交补空间中时的相应曲线。类似地，从图3和图4可以看出，贪婪随机Kaczmarz方法所产生的相对解误差下降至${\mathrm{10}}^{-\mathrm{3}}$左右之后不再减小，且阈值$\tau$能够很好地给出该最小值的估计，特别当系数矩阵为bibd_16_8和当系数矩阵为ash958且扰动向量$\mathit{r}$在系数矩阵的像空间中时。

图3 当矩阵为bibd_16_8 和ash958 时，lg E_RS和lg τ相对于迭代步数的曲线

Fig.3 Pictures of lg E_RS and lg τ versus the iteration step when the matrices are bibd_16_8 and ash958

图4 当矩阵为ash958且$\mathit{r}\in \mathit{R}\left(\mathit{A}\right)$和$\mathit{r}\in \mathit{R}{\left(\mathit{A}\right)}^{\perp }$时，lg E_RS与lg τ相对于迭代步数的曲线

Fig.4 Pictures of lg E_RS and lg τ versus the iteration step when the matrix is ash958, and $\mathit{r}\in \mathit{R}\left(\mathit{A}\right)$ and$\mathit{r}\in \mathit{R}{\left(\mathit{A}\right)}^{\perp }$

4 结论

当线性代数方程组的右端向量发生扰动时，证明了贪婪随机Kaczmarz方法的期望解误差以线性速率下降至一个给定阈值。数值实验表明该阈值能够很好地估计贪婪随机Kaczmarz方法的迭代解误差所能达到的最小值。可以发现当扰动不是很大且对解的精度要求不是很高时，贪婪随机Kaczmarz方法仍然能够很好地给出原线性代数方程组最小范数解的近似。