求解大型线性最小二乘问题的贪婪Gauss-Seidel方法

摘要

基于一种选择系数矩阵$\mathit{A}$的工作列的策略，提出了求解大型线性最小二乘问题的一种不同的贪婪Gauss-Seidel方法，并对该方法进行了收敛性分析。数值实验表明，在相同的精度下，所提方法在计算时间上优于文献提出的贪婪随机坐标下降方法。

关键词

贪婪Gauss-Seidel方法; 贪婪随机坐标下降方法; 随机的Gauss-Seidel方法; 大型线性最小二乘问题

线性最小二乘问题是数值代数与科学计算中一个经典问题，经常出现于参数估计、反演与预测等问题之中。常见的直接法包括带旋转的QR分解法和奇异值分解法^［1-2］等。然而， 当矩阵规模较大时， 此类方法通常需要很大的存储量并且计算成本较高。因此，迭代法成为求解大型线性最小二乘问题的重要选择，如著名的Gauss-Seidel方法^［3］。

众所周知， Gauss-Seidel方法与Kaczmarz方法密切相关， 如它们均可视为坐标下降法对应于特殊半正定线性系统的变形。具体地，对于线性系统$\mathit{A}\mathit{x}=\mathit{b}$， Kaczmarz方法的迭代格式与坐标下降法应用于半正定系统$\mathit{A}{\mathit{A}}^{\mathrm{T}}\mathit{u}=\mathit{b}$，并结合标准的原始-对偶映射$\mathit{x}={\mathit{A}}^{\mathrm{T}}\mathit{u}$的迭代格式一致， Gauss-Seidel方法$\mathrm{的}\mathrm{迭}\mathrm{代}\mathrm{格}\mathrm{式}\mathrm{则}$等同于坐标下降法应用于半正定系统${\mathit{A}}^{\mathrm{T}}\mathit{A}\mathit{x}={\mathit{A}}^{\mathrm{T}}\mathit{b}$的迭代格式^［4］。2009年， Strohmer和Vershynin^［5］首次证明了随机Kaczmarz方法具有线性收敛性。随后， Leventhal和Lewis^［6］证明了随机Gauss-Seidel（RGS）方法也具有类似的结果， 该方法也称为随机坐标下降方法。它是根据适当的概率分布随机投影于矩阵A的列， 达到最小化$‖\mathit{b}-\mathit{A}\mathit{x}{‖}_{\mathrm{2}}^{\mathrm{2}}$的目的， 因而具有很好的性能， 从而引起了广泛的关注，可参见文献［7-14］及其参考文献。

Bai和Wu^［15］提出了贪婪随机坐标下降（GRCD）方法， 该方法引入了一种贪婪的概率准则， 避免了RGS方法的一些缺点， 从而使得其在迭代次数和计算时间上都优于RGS方法。文献［15］提出的贪婪思想具有广泛的应用， 参见文献［16-24］及其参考文献。

本文提出一种求解大型线性最小二乘问题的贪婪Gauss-Seidel（GGS）方法， 与GRCD方法相比，它采用了完全不同的方式来确定矩阵$\mathit{A}$的工作列， 使得其每次迭代所需的计算时间更少。从理论上证明GGS方法的收敛性；在数值实验中，利用文献［15］中的例子比较了GGS和GRCD这2种方法的性能。

1 预备知识

对于向量$\mathit{z}\mathrm{ϵ}{\mathbf{R}}^n$，${\mathit{z}}^{(j)}$表示它的第$j$个分量。对于矩阵$\mathit{G}=\left(g_{ij}\right)\mathrm{ϵ}{\mathbf{R}}^{m\times n}$，${\mathit{G}}_{(j)}$、$||\mathit{G}|{|}_{\mathrm{2}}$以及$||\mathit{G}|{|}_F$分别表示它的第$j$列、谱范数以及F范数。此外，如果$\mathit{G}\mathrm{ϵ}{\mathbf{R}}^{n\times n}$是一个正定矩阵，那么任意一个向量$\mathit{x}\mathrm{ϵ}{\mathbf{R}}^n$的能量范数定义为$||\mathit{x}|{|}_{\mathit{G}}=\sqrt[]{{\mathit{x}}^{\mathrm{T}}\mathit{G}\mathit{x}}$，其中${(·)}^{\mathrm{T}}$表示一个向量或者一个矩阵的转置。另外，用$\mathit{I}$表示单位矩阵， 用${\mathit{e}}_j$表示它的第$j$列，用${\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}({\mathit{G}}^{\mathrm{T}}\mathit{G})$表示${\mathit{G}}^{\mathrm{T}}\mathit{G}$的最小正特征值，用$|W|$表示集合W的元素个数。

类似文献［15］，本文以${\mathit{x}}_{*}={\mathit{A}}^{†}\mathit{b}$，其中${\mathit{A}}^{†}=({\mathit{A}}^{\mathrm{T}}{\mathit{A})}^{-\mathrm{1}}{\mathit{A}}^{\mathrm{T}}$表示A的Moore-Penrose广义逆，表示如下线性最小二乘问题的唯一最小范数最小二乘解：

$$\underset{\mathit{x}\mathrm{ϵ}{\mathrm{ℛ}}^n}{\mathrm{m}\mathrm{i}\mathrm{n}}‖\mathit{b}-\mathit{A}\mathit{x}{‖}_{\mathrm{2}}^{\mathrm{2}}$$

（1）

其中矩阵$\mathit{A}\mathrm{ϵ}{\mathbf{R}}^{m\times n}$列满秩，向量$\mathit{b}\mathrm{ϵ}{\mathbf{R}}^m$. 众所周知， ${\mathit{x}}_{\mathit{*}}≔\mathrm{a}\mathrm{r}\mathrm{g}\underset{\mathit{x}\mathrm{ϵ}{\mathrm{R}}^n}{\mathrm{m}\mathrm{i}\mathrm{n}}‖\mathit{b}-\mathit{A}\mathit{x}{‖}_{\mathrm{2}}^{\mathrm{2}}$是关于式（1）的如下正规方程组^［25］的解：

$${\mathit{A}}^{\mathrm{T}}\mathit{A}\mathit{x}={\mathit{A}}^{\mathrm{T}}\mathit{b}$$

（2）

基于正规方程组（2），文献［15］提出了如下贪婪随机坐标下降方法，即算法1，其中${\mathit{r}}_k=\mathit{b}-\mathit{A}{\mathit{x}}_k$表示残差向量。

算法1  　贪婪随机坐标下降方法。 ①置$k:=\mathrm{0}$。 计算${\delta }_k=\frac{\mathrm{1}}{\mathrm{2}}(\frac{\mathrm{1}}{||{\mathit{A}}^{\mathrm{T}}{\mathit{r}}_k|{|}_{\mathrm{2}}^{\mathrm{2}}}\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{\frac{{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}\right\}+\frac{\mathrm{1}}{||\mathit{A}|{|}_F^{\mathrm{2}}})$ 。 ②定义正整数指标集$v_k=\left\{j\right.\left|\right.{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}\ge {\delta }_k||{\mathit{A}}^{\mathrm{T}}{\mathit{r}}_k|{|}_{\mathrm{2}}^{\mathrm{2}}‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}\}$。③令${\mathit{s}}_k={\mathit{A}}^{\mathrm{T}}{\mathit{r}}_k$， 计算${\widetilde{{\mathit{s}}_k}}^{(j)}=\left\{\begin{array}{c}{{\mathit{s}}_k}^{(j)},\mathrm{如}\mathrm{果}j\in v_k,\\ \mathrm{0},\mathrm{其}\mathrm{他}\mathrm{情}\mathrm{形}\mathrm{。}\end{array}\right.$④根据概率$\mathrm{P}\mathrm{r}\left(c=j_k\right)=\frac{|{\widetilde{{\mathit{s}}_k}}^{(j_k)}{|}^{\mathrm{2}}}{||\widetilde{{\mathit{s}}_k}|{|}_{\mathrm{2}}^{\mathrm{2}}}$选取指标$j_k\in v_k\mathrm{。}$ ⑤计算${\mathit{x}}_{k+\mathrm{1}}={\mathit{x}}_k+\frac{{{\mathit{s}}_k}^{(j_k)}}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}{\mathit{e}}_{j_k}$。 ⑥置$k=k+\mathrm{1}$， 转步骤①。

由贪婪随机坐标下降方法中${\delta }_k$和$v_k$的定义可知， 如果$l\in v_k$， 那么

$$\frac{{\left|{\mathit{A}}_{\left(l\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(l\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}\ge \frac{\mathrm{1}}{\mathrm{2}}(\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{\frac{{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}\right\}+\frac{‖{\mathit{A}}^{\mathrm{T}}{\mathit{r}}_k{‖}_{\mathrm{2}}^{\mathrm{2}}}{||\mathit{A}|{|}_F^{\mathrm{2}}})$$

注意到

$$\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{\frac{{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}\right\}\ge \stackrel{}{{\displaystyle \sum _{j=\mathrm{1}}^n}}\frac{‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}{||\mathit{A}|{|}_F^{\mathrm{2}}}\frac{{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}=\frac{‖{\mathit{A}}^{\mathrm{T}}{\mathit{r}}_k{‖}_{\mathrm{2}}^{\mathrm{2}}}{||\mathit{A}|{|}_F^{\mathrm{2}}}$$

因此，不能得到如下结论：如果$l\in v_k$，那么$\frac{{\left|{\mathit{A}}_{\left(l\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(l\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}\ge \underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{\frac{{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}\right\}$， 也即

$$\frac{{\left|{\mathit{A}}_{\left(l\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(l\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}=\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{\frac{{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}\right\}$$

由此可知，可能存在一些$l\in v_k$使得

$$\frac{{\left|{\mathit{A}}_{\left(l\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(l\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}<\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{\frac{{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}\right\}$$

（3）

与此同时， 对于任意的$j_k\in v_k$， 由迭代格式可以得到

$$||\mathit{A}{\mathit{x}}_{k+\mathrm{1}}-\mathit{A}{\mathit{x}}_k|{|}_{\mathrm{2}}^{\mathrm{2}}=\frac{{\left|{\mathit{A}}_{\left(j_k\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}$$

（4）

结合式（3）和式（4）可以发现，在更新得到${\mathit{x}}_{k+\mathrm{1}}$的时候， 指标集合$v_k$中的列指标并不能保证$\mathit{A}{\mathit{x}}_{k+\mathrm{1}}\mathrm{与}\mathit{A}{\mathit{x}}_k$之间的距离最大。此外，在计算${\delta }_k$的时候需要计算矩阵$\mathit{A}$的所有列范数。

2 基于残差-距离的贪婪Gauss-Seidel方法

考虑到贪婪随机坐标下降方法里指标集合$v_k$中的列指标并不能保证$\mathit{A}{\mathit{x}}_{k+\mathrm{1}}\mathrm{与}\mathit{A}{\mathit{x}}_k$之间的距离最大， 并且计算${\delta }_k$的时候需要计算矩阵$\mathit{A}$的所有列范数； 同时，考虑到最近很多工作按照最大残差^［26-30］策略选择迭代指标，提出了基于残差-距离的贪婪Gauss-Seidel方法，即算法2。

算法2  　贪婪Gauss-Seidel方法。①置$k:=\mathrm{0}$。 确定正整数指标集

$$R_k=\left\{\right.\widetilde{j_k}\left|\right.\widetilde{j_k}=\mathrm{a}\mathrm{r}\mathrm{g}\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|\}$$

②计算

$$j_k=\mathrm{a}\mathrm{r}\mathrm{g}\underset{\widetilde{j_k}\in {\mathrm{R}}_k}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{\frac{{\left|{\mathit{A}}_{\left(\widetilde{j_k}\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(\widetilde{j_k}\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}\right\}$$

③计算

$${\mathit{x}}_{k+\mathrm{1}}={\mathit{x}}_k+\frac{{\mathit{A}}_{\left(j_k\right)}^{\mathrm{T}}{\mathit{r}}_k}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}{\mathit{e}}_{j_k}$$

④置$k=k+\mathrm{1}$， 转步骤①。

贪婪Gauss-Seidel方法主要包括2步：①通过正规方程组（2）的残差向量${\mathit{s}}_k$的最大元素确定指标集合$R_k$。②按照$\mathit{A}{\mathit{x}}_{k+\mathrm{1}}\mathrm{与}\mathit{A}{\mathit{x}}_k$之间的距离最大准则从集合$R_k$中选择迭代所需列指标。粗略看来，该方法似乎改变了贪婪随机坐标下降方法的2个主要步骤的顺序。然而，与贪婪随机坐标下降方法相比，贪婪Gauss-Seidel方法除了在求${\mathit{x}}_{k+\mathrm{1}}$时使得$\mathit{A}{\mathit{x}}_{k+\mathrm{1}}\mathrm{与}\mathit{A}{\mathit{x}}_k$之间的距离最大之外，也不再需要计算矩阵$\mathit{A}$每一列的范数。此外，由于$R_k$是由向量${\mathit{s}}_k$的最大项决定的，还可以发现集合$R_k$中的元素个数可能小于集合$v_k$中的元素个数，即$|R_k|<|v_k|$。因此，该方法可以减少每次迭代的计算成本，从而可期待在计算时间上会有更好的表现，这一点将在第3节中的数值实验中进行验证。

注1  　如果$\left|{\mathit{A}}_{\left(j_k\right)}^{\mathrm{T}}{\mathit{r}}_k\right|$=$\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|$，则$j_k\in R_k\mathrm{。}$由此可知贪婪Gauss-Seidel方法中的集合$R_k$非空。

注2  　类似于贪婪随机坐标下降方法，贪婪Gauss-Seidel方法可利用$\frac{{\left|{\mathit{A}}_{\left(\widetilde{j_k}\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(\widetilde{j_k}\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}$，其中$\widetilde{j_k}\in R_k,$作为概率选择标准得到相应的随机算法。在这种情况下，它的收敛因子可能比贪婪Gauss-Seidel方法稍差，因为贪婪Gauss-Seidel方法是根据$\frac{{\left|{\mathit{A}}_{\left(\widetilde{j_k}\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(\widetilde{j_k}\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}$最大的值来选择指标的，其使得$\mathit{A}{\mathit{x}}_{k+\mathrm{1}}\mathrm{与}\mathit{A}{\mathit{x}}_k$之间的距离最大。

注3  　在贪婪Gauss-Seidel方法中确定了指标集合$R_k$之后， 类似文献［31-34］中的思想，可以得到关于贪婪Gauss-Seidel方法的分块算法。

接下来， 给出贪婪Gauss-Seidel方法的收敛性分析。

定理1  　由贪婪Gauss-Seidel方法生成的迭代序列$\{{\mathit{x}}_k{\}}_{k=\mathrm{0}}^{\mathrm{\infty }}$，从初始向量${\mathit{x}}_{\mathrm{0}}\mathrm{ϵ}{\mathbf{R}}^n$开始，线性收敛于唯一的最小范数最小二乘解${\mathit{x}}_{*}={\mathit{A}}^{†}\mathit{b}$，并且

$$‖{\mathit{x}}_{\mathrm{1}}-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^T\mathit{A}}^{\mathrm{2}}\le (\mathrm{1}-\frac{\mathrm{1}}{|R_{\mathrm{0}}|}·\sum _{j_{\mathrm{0}}\in R_{\mathrm{0}}}\frac{\mathrm{1}}{‖{\mathit{A}}_{\left(j_{\mathrm{0}}\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}·\frac{\mathrm{1}}{n}·{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}({\mathit{A}}^{\mathrm{T}}\mathit{A}))‖{\mathit{x}}_{\mathrm{0}}-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}$$

（5）

对于$k=\mathrm{1},\mathrm{2},\cdots$，有

$$‖{\mathit{x}}_{\mathrm{k}+\mathrm{1}}-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}\le \left(\mathrm{1}-\frac{\mathrm{1}}{\left|R_k\right|}·\sum _{j_k\in R_k}\frac{\mathrm{1}}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}·\frac{\mathrm{1}}{n-\mathrm{1}}·{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{T}}\mathit{A}\right)\right)‖{\mathit{x}}_k-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}$$

（6）

此外， 令$\beta =\mathrm{m}\mathrm{i}\mathrm{n}\{\frac{\mathrm{1}}{\left|R_k\right|}·\sum _{j_k\in R_k}\frac{\mathrm{1}}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}\}$， $k=\mathrm{1},\mathrm{2},\cdots ,$ 则对于$k=\mathrm{1},\mathrm{2},\cdots$，有

$$‖{\mathit{x}}_k-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}\le {\left(\mathrm{1}-\frac{\beta ·{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{T}}\mathit{A}\right)}{n-\mathrm{1}}\right)}^{k-\mathrm{1}}(\mathrm{1}-\sum _{j_{\mathrm{0}}\in R_{\mathrm{0}}}\frac{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}(A^{\mathrm{T}}A)}{|R_{\mathrm{0}}|·‖{\mathit{A}}_{\left(j_{\mathrm{0}}\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}·n})·‖{\mathit{x}}_{\mathrm{0}}-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}$$

（7）

证明  　由贪婪Gauss-Seidel方法的迭代格式可知

$$\mathit{A}\left({\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_k\right)=\frac{{\mathit{A}}_{\left(j_k\right)}^{\mathrm{T}}{\mathit{r}}_k}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}{\mathit{A}}_{(j_k)}$$

这意味着$\mathit{A}\left({\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_k\right)$平行于${\mathit{A}}_{(j_k)}$。与此同时

$$\mathit{A}\left({\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_{*}\right)=\mathit{A}\left({\mathit{x}}_k-{\mathit{x}}_{*}+\frac{{\mathit{A}}_{\left(j_k\right)}^{\mathrm{T}}{\mathit{r}}_k}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}{\mathit{e}}_{j_k}\right)=\mathit{A}({\mathit{x}}_k-{\mathit{x}}_{*})+\frac{{\mathit{A}}_{\left(j_k\right)}^{\mathrm{T}}{\mathit{r}}_k}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}{\mathit{A}}_{(j_k)}$$

结合${\mathit{A}}^{\mathrm{T}}\mathit{A}{\mathit{x}}_{*}={\mathit{A}}^{\mathrm{T}}\mathit{b}$可以得到

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

则

$$\begin{array}{l}{\mathit{A}}_{\left(j_k\right)}^{\mathrm{T}}\mathit{A}\left({\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_{*}\right)=\\ {\mathit{A}}_{\left(j_k\right)}^{\mathrm{T}}\left(\mathit{I}-\frac{{\mathit{A}}_{(j_k)}{\mathit{A}}_{\left(j_k\right)}^{\mathrm{T}}}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}\right)\mathit{A}\left({\mathit{x}}_k-{\mathit{x}}_{*}\right)=\mathrm{0}\end{array}$$

故$\mathit{A}\left({\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_{*}\right)$垂直于${\mathit{A}}_{(j_k)}$。因此， 向量$\mathit{A}\left({\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_k\right)$垂直于向量$\mathit{A}\left({\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_{*}\right)$. 由勾股定理可得

$$\begin{array}{l}‖\mathit{A}\left({\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_{*}\right){‖}_{\mathrm{2}}^{\mathrm{2}}=\\ ‖\mathit{A}\left({\mathit{x}}_k-{\mathit{x}}_{*}\right){‖}_{\mathrm{2}}^{\mathrm{2}}-‖\mathit{A}\left({\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_k\right){‖}_{\mathrm{2}}^{\mathrm{2}}\end{array}$$

其等价形式为

$$\begin{array}{l}‖{\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}=\\ ‖{\mathit{x}}_k-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}-‖{\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_k{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}\end{array}$$

（8）

另一方面， 由贪婪Gauss-Seidel方法可知

$$|{\mathit{A}}_{\left(j_k\right)}^{\mathrm{T}}{\mathit{r}}_k|=\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|$$

并且

$$\frac{|{\mathit{A}}_{\left(j_k\right)}^{\mathrm{T}}{\mathit{r}}_k{|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}=\underset{j\in R_k}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{\frac{{\left|{\mathit{A}}_{(j)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}\right\}$$

则

$$‖{\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_k{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}=‖\mathit{A}\left({\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_k\right){‖}_{\mathrm{2}}^{\mathrm{2}}=$$

$$\frac{{\left|{\mathit{A}}_{\left(j_k\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}\ge$$$$\sum _{j_k\in R_k}\frac{\frac{|{\mathit{A}}_{\left(j_k\right)}^{\mathrm{T}}{\mathit{r}}_k{|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}}{\sum _{j\in R_k}\frac{{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}}·\frac{|{\mathit{A}}_{\left(j_k\right)}^{\mathrm{T}}{\mathit{r}}_k{|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}$$$$\ge$$

$$\sum _{j_k\in R_k}\frac{\mathrm{1}}{|R_k|}·\frac{|{\mathit{A}}_{\left(j_k\right)}^{\mathrm{T}}{\mathit{r}}_k{|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}$$=$$\sum _{j_k\in R_k}\frac{\mathrm{1}}{|R_k|}·\frac{\underset{\mathrm{1}\le \mathrm{j}\le \mathrm{n}}{\mathrm{m}\mathrm{a}\mathrm{x}}|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k{|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}$$

（9）

因此， 将式（9）代入式（8）可得

$$‖{\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}\le ‖{\mathit{x}}_k-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}-\sum _{j_k\in R_k}\frac{\mathrm{1}}{\left|R_k\right|}·\frac{\underset{\mathrm{1}\le \mathrm{j}\le \mathrm{n}}{\mathrm{m}\mathrm{a}\mathrm{x}}|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k{|}^{\mathrm{2}}}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}$$

（10）

当$k=\mathrm{0}$时，有

$$\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_{\mathrm{0}}\right|}^{\mathrm{2}}=\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_{\mathrm{0}}\right|}^{\mathrm{2}}·\frac{‖{\mathit{A}}^{\mathrm{T}}{\mathit{r}}_{\mathrm{0}}{‖}_{\mathrm{2}}^{\mathrm{2}}}{{\sum }_{j=\mathrm{1}}^n{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_{\mathrm{0}}\right|}^{\mathrm{2}}}\ge \frac{\mathrm{1}}{n}·‖{\mathit{A}}^{\mathrm{T}}{\mathit{r}}_{\mathrm{0}}{‖}_{\mathrm{2}}^{\mathrm{2}}$$

结合文献［16］中的结果：

$$‖{\mathit{A}}^{\mathrm{T}}\mathit{x}{‖}_{\mathrm{2}}^{\mathrm{2}}\ge {\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}({\mathit{A}}^{\mathrm{T}}\mathit{A})‖\mathit{x}{‖}_{\mathrm{2}}^{\mathrm{2}}$$

（11）

其中向量x属于A的列空间，可得到

$$\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_{\mathrm{0}}\right|}^{\mathrm{2}}\ge \frac{\mathrm{1}}{n}·{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}({\mathit{A}}^{\mathrm{T}}\mathit{A})·‖\mathit{A}{\mathit{x}}_{*}-\mathit{A}{\mathit{x}}_{\mathrm{0}}{‖}_{\mathrm{2}}^{\mathrm{2}}=\frac{\mathrm{1}}{n}·{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}({\mathit{A}}^{\mathrm{T}}\mathit{A})·‖{\mathit{x}}_{\mathrm{0}}-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}$$

（12）

因此， 将式（12）代入式（10）可得

$$‖{\mathit{x}}_{\mathrm{1}}-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}\le ‖{\mathit{x}}_{\mathrm{0}}-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}-$$$$\sum _{j_{\mathrm{0}}\in R_{\mathrm{0}}}\frac{\mathrm{1}}{|R_{\mathrm{0}}|}·\frac{\mathrm{1}}{‖{\mathit{A}}_{\left(j_{\mathrm{0}}\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}·\frac{\mathrm{1}}{n}·{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{T}}\mathit{A}\right)·‖{\mathit{x}}_{\mathrm{0}}-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}=(\mathrm{1}-\frac{\mathrm{1}}{|R_{\mathrm{0}}|}·$$$$\sum _{j_{\mathrm{0}}\in R_{\mathrm{0}}}\frac{\mathrm{1}}{‖{\mathit{A}}_{\left(j_{\mathrm{0}}\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}·\frac{\mathrm{1}}{n}·{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}({\mathit{A}}^{\mathrm{T}}\mathit{A}))‖{\mathit{x}}_{\mathrm{0}}-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}$$

这即是式（5）。

当$k\ge \mathrm{1}$时，有

$$\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}=\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}·\frac{‖{\mathit{A}}^{\mathrm{T}}{\mathit{r}}_k{‖}_{\mathrm{2}}^{\mathrm{2}}}{{\sum }_{j=\mathrm{1}}^n{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}$$

根据贪婪Gauss-Seidel方法的迭代格式， 立刻可得

$${\mathit{A}}_{\left(j_{k-\mathrm{1}}\right)}^{\mathrm{T}}{\mathit{r}}_k={\mathit{A}}_{\left(j_{k-\mathrm{1}}\right)}^{\mathrm{T}}({\mathit{r}}_{k-\mathrm{1}}-\frac{{\mathit{A}}_{\left(j_{k-\mathrm{1}}\right)}^{\mathrm{T}}{\mathit{r}}_{k-\mathrm{1}}}{‖{\mathit{A}}_{\left(j_{k-\mathrm{1}}\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}{\mathit{A}}_{(j_{k-\mathrm{1}})})={\mathit{A}}_{\left(j_{k-\mathrm{1}}\right)}^{\mathrm{T}}{\mathit{r}}_{k-\mathrm{1}}-{\mathit{A}}_{\left(j_{k-\mathrm{1}}\right)}^{\mathrm{T}}{\mathit{r}}_{k-\mathrm{1}}=\mathrm{0}$$

则

$$\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}=\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}{\left|{\mathit{A}}_{\left(j\right)}^T{\mathit{r}}_k\right|}^{\mathrm{2}}·\frac{‖{\mathit{A}}^{\mathrm{T}}{\mathit{r}}_k{‖}_{\mathrm{2}}^{\mathrm{2}}}{{\displaystyle \sum _{\begin{array}{c}j=\mathrm{1}\\ j\ne j_{k-\mathrm{1}}\end{array}}^n}{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}}\ge \frac{\mathrm{1}}{n-\mathrm{1}}·‖{\mathit{A}}^{\mathrm{T}}{\mathit{r}}_k{‖}_{\mathrm{2}}^{\mathrm{2}}$$

结合式（11）得到

$$\begin{array}{l}\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}{\left|{\mathit{A}}_{\left(j\right)}^{\mathrm{T}}{\mathit{r}}_k\right|}^{\mathrm{2}}\ge \\ \frac{\mathrm{1}}{n-\mathrm{1}}·{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}({\mathit{A}}^{\mathrm{T}}\mathit{A})‖\mathit{A}{\mathit{x}}_{*}-\mathit{A}{\mathit{x}}_k{‖}_{\mathrm{2}}^{\mathrm{2}}\\ =\frac{\mathrm{1}}{n-\mathrm{1}}·{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}({\mathit{A}}^{\mathrm{T}}\mathit{A})‖{\mathit{x}}_k-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}\end{array}$$

（13）

因此， 将式（13）代入式（10）可得

$$‖{\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}\le ‖{\mathit{x}}_k-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}-\sum _{j_k\in R_k}\frac{\mathrm{1}}{\left|R_k\right|}·\frac{\mathrm{1}}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}·\frac{\mathrm{1}}{n-\mathrm{1}}·{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{T}}\mathit{A}\right)‖{\mathit{x}}_k-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}=\left(\mathrm{1}-\frac{\mathrm{1}}{\left|R_k\right|}·\sum _{j_k\in R_k}\frac{\mathrm{1}}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}·\frac{\mathrm{1}}{n-\mathrm{1}}·{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{T}}\mathit{A}\right)\right)‖{\mathit{x}}_k-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}$$

这即是式（6）。关于迭代指标$k$递归可得到式（7）。

注4  　运用下面不等式

$$\mathrm{1}-\frac{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{T}}\mathit{A}\right)}{‖\mathit{A}{‖}_F^{\mathrm{2}}-\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{i}\mathrm{n}}‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}<\mathrm{1}-\frac{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{T}}\mathit{A}\right)}{‖\mathit{A}{‖}_F^{\mathrm{2}}}<\mathrm{1}$$

可以得到

$$\mathrm{0}<\frac{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{T}}\mathit{A}\right)}{\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}·(n-\mathrm{1})}\le \frac{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{T}}\mathit{A}\right)}{‖\mathit{A}{‖}_F^{\mathrm{2}}-\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{i}\mathrm{n}}‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}<\mathrm{1}$$

再结合

$$\frac{\mathrm{1}}{\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}\le \beta \le \frac{\mathrm{1}}{n}·{\displaystyle \sum _{j_k=\mathrm{1}}^n}\frac{\mathrm{1}}{‖{\mathit{A}}_{\left(j_k\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}$$

可得到

$$\mathrm{1}-\frac{\beta ·{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{T}}\mathit{A}\right)}{n-\mathrm{1}}\le \mathrm{1}-\frac{{\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{T}}\mathit{A}\right)}{\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{a}\mathrm{x}}‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}·(n-\mathrm{1})}<\mathrm{1}$$

因此， 贪婪Gauss-Seidel方法的收敛因子确实是小于1的。

注5  　贪婪随机坐标下降方法^［15］的误差估计如下：

$${{\rm E}}_k[‖{\mathit{x}}_{k+\mathrm{1}}-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}]\le \left(\mathrm{1}-\frac{\mathrm{1}}{\mathrm{2}}\left(\frac{\mathrm{1}}{‖\mathit{A}{‖}_F^{\mathrm{2}}-\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{i}\mathrm{n}}‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}+\frac{\mathrm{1}}{‖\mathit{A}{‖}_F^{\mathrm{2}}}\right){\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{T}}\mathit{A}\right)\right)‖{\mathit{x}}_k-{\mathit{x}}_{*}{‖}_{{\mathit{A}}^{\mathrm{T}}\mathit{A}}^{\mathrm{2}}$$

其中$k=\mathrm{1},\mathrm{2},\cdots \mathrm{。}$由此可知贪婪随机坐标下降方法的收敛因子为

$$\mathrm{1}-\frac{\mathrm{1}}{\mathrm{2}}\left(\frac{\mathrm{1}}{‖\mathit{A}{‖}_F^{\mathrm{2}}-\underset{\mathrm{1}\le j\le n}{\mathrm{m}\mathrm{i}\mathrm{n}}‖{\mathit{A}}_{\left(j\right)}{‖}_{\mathrm{2}}^{\mathrm{2}}}+\frac{\mathrm{1}}{‖\mathit{A}{‖}_F^{\mathrm{2}}}\right){\lambda }_{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\mathit{A}}^{\mathrm{T}}\mathit{A}\right)$$

由于直接比较贪婪Gauss-Seidel（GGS）和贪婪随机坐标下降（GRCD）2种方法的收敛因子并不容易， 所以采用2个数值例子进行比较。此外， 还绘制了2种方法的实际收敛速率， 其定义^［17］如下：

$${\rho }_k={(\frac{{\rm E}[‖{\mathit{x}}_k-{\mathit{x}}_{*}{‖}_{\mathrm{2}}^{\mathrm{2}}]}{‖{\mathit{x}}_{\mathrm{0}}-{\mathit{x}}_{*}{‖}_{\mathrm{2}}^{\mathrm{2}}})}^{\raisebox{1ex}{$\mathrm{1}$}\!\left/ \!\raisebox{-1ex}{$k$}\right.},k\ge \mathrm{1}$$

图1表明， 贪婪Gauss-Seidel方法和贪婪随机坐标下降方法的收敛因子基本相同，但前者的实际收敛速率略好于后者。

图1 GGS和GRCD方法的收敛因子与实际收敛速率

Fig. 1 Convergence factors and rates of the GGS and GRCD methods

3 数值实验

通过数值实验比较贪婪Gauss-Seidel （GGS）方法和贪婪随机坐标下降（GRCD）方法在求解线性最小二乘问题上的表现，其中矩阵$\mathit{A}$来自2类集合，一类是由Matlab函数randn随机生成，一类是来自不同应用的稀疏矩阵^［35］。为了公正直接地比较GGS和GRCD方法，采用的例子都来自文献［15］。

主要依据迭代次数（IT）和CPU计算时间比较这2种方法。数值结果中的迭代次数和计算时间表示的是50次重复运行相应方法的平均值。此外，为了直观地比较2种方法，给出了GGS方法相对于GRCD方法的迭代次数加速比（$\mathrm{I}\mathrm{T}\mathrm{s}\mathrm{p}\mathrm{e}\mathrm{e}\mathrm{d}$-up），其定义为GRCD方法所需的迭代次数除以GGS方法所需的迭代次数，同时给出了GGS方法相对于GRCD方法的计算时间加速比（$\mathrm{C}\mathrm{P}\mathrm{U}\mathrm{s}\mathrm{p}\mathrm{e}\mathrm{e}\mathrm{d}$-up），其定义为GRCD方法所需的计算时间除以GGS方法所需的计算时间。对于来自文献［35］的稀疏矩阵， 其稠密度定义为矩阵非零元素个数除以矩阵元素个数。

在数值实验中，解向量${\mathit{x}}_{*}$由Matlab函数randn随机生成。对于相容的系统， 令右边$\mathit{b}=\mathit{A}{\mathit{x}}_{*}\mathrm{。}$对于不相容的系统， 取$\mathit{b}=\mathit{A}{\mathit{x}}_{*}+{\mathit{r}}_{\mathrm{0}}$，其中${\mathit{r}}_{\mathrm{0}}$是属于${\mathit{A}}^{\mathrm{T}}$的零空间的一个非零向量， 由Matlab函数null生成。本节所有的数值实验， 均取初始向量${\mathit{x}}_{\mathrm{0}}=\mathrm{0}$， 停机准则为近似解的相对误差$\frac{‖{\mathit{x}}_k-{\mathit{x}}_{*}{‖}_{\mathrm{2}}^{\mathrm{2}}}{‖{\mathit{x}}_{*}{‖}_{\mathrm{2}}^{\mathrm{2}}}<{\mathrm{10}}^{-\mathrm{6}},$或者迭代次数超过20万步。

对于第一类随机生成的矩阵， 线性系统相容时， 2类迭代法的迭代次数和计算时间的数值结果如表1所示； 当线性系统不相容时， 其数值结果如表2所示。从表1和表2可以看出， GGS方法的迭代次数与GRCD方法几乎相同， 但在计算时间上， GGS方法的效率更高，计算时间加速比至少可达到1.626。

表1 GGS和GRCD 2种方法在随机数据矩阵时求解相容系统的数值结果

Tab. 1 Numerical results of solving consistent systems with random data matrices by using the GGS and the GRCD methods

$\mathrm{阶}\mathrm{数}$	IT			CPU计算时间
	GGS	GRCD	IT speed-up	GGS	GRCD	CPU speed-up
1 000×50	126.000 0	128.240 0	1.017 8	0.013 8	0.063 1	4.590 9
1 000×100	374.000 0	361.500 0	0.966 6	0.046 6	0.170 3	3.657 7
1 000×150	603.000 0	600.560 0	0.996 0	0.104 4	0.319 4	3.059 9
2 000×50	108.000 0	106.260 0	0.983 9	0.012 5	0.052 5	4.200 0
2 000×100	246.000 0	245.720 0	0.998 9	0.046 6	0.131 3	2.818 8
2 000×150	439.000 0	445.680 0	1.015 2	0.109 4	0.269 1	2.460 0
3 000×50	105.000 0	104.960 0	0.999 6	0.017 2	0.055 6	3.236 4
3 000×100	231.000 0	236.880 0	1.025 5	0.061 9	0.144 4	2.333 3
3 000×150	409.000 0	409.040 0	1.000 1	0.140 0	0.283 4	2.024 6
4 000×50	96.000 0	99.740 0	1.039 0	0.019 4	0.057 2	2.951 6
4 000×100	205.000 0	209.120 0	1.020 1	0.067 8	0.138 8	2.046 1
4 000×150	337.000 0	343.660 0	1.019 8	0.163 8	0.266 2	1.626 0
5 000×50	96.000 0	95.380 0	0.993 5	0.025 0	0.060 0	2.400 0
5 000×100	195.000 0	203.080 0	1.041 4	0.072 8	0.156 9	2.154 5
5 000×150	340.000 0	337.020 0	0.991 2	0.181 9	0.297 8	1.637 5

表2 GGS和GRCD 2种方法在随机数据矩阵时求解不相容系统的数值结果

Tab. 2 Numerical results of solving inconsistent systems with random data matrices by using the GGS and the GRCD methods

$\mathrm{阶}\mathrm{数}$	IT			CPU计算时间
	GGS	GRCD	IT speed-up	GGS	GRCD	CPU speed-up
1 000×50	120.000 0	124.860 0	1.040 5	0.012 5	0.059 1	4.725 0
1 000×100	329.000 0	321.380 0	0.976 8	0.040 0	0.159 1	3.976 6
1 000×150	589.000 0	579.560 0	0.984 0	0.099 4	0.300 9	3.028 3
2 000×50	113.000 0	110.200 0	0.975 2	0.011 9	0.056 6	4.763 2
2 000×100	245.000 0	250.060 0	1.020 7	0.053 1	0.132 2	2.488 2
2 000×150	434.000 0	444.720 0	1.024 7	0.111 3	0.266 6	2.396 1
3 000×50	107.000 0	105.080 0	0.982 1	0.019 4	0.055 3	2.854 8
3 000×100	235.000 0	232.360 0	0.988 8	0.060 9	0.141 2	2.317 9
3 000×150	399.000 0	401.460 0	1.006 2	0.140 3	0.276 9	1.973 3
4 000×50	95.000 0	97.480 0	1.026 1	0.019 4	0.053 7	2.774 2
4 000×100	220.000 0	216.740 0	0.985 2	0.069 4	0.144 4	2.081 1
4 000×150	348.000 0	356.800 0	1.025 3	0.152 5	0.277 2	1.817 6
5 000×50	87.000 0	91.940 0	1.056 8	0.018 7	0.055 9	2.983 3
5 000×100	212.000 0	215.960 0	1.018 7	0.086 2	0.156 6	1.815 2
5 000×150	336.000 0	339.260 0	1.009 7	0.164 1	0.305 0	1.859 0

对于第二类矩阵， 即文献［35］中的稀疏列满秩矩阵， 线性系统相容时， 2类迭代方法的迭代次数和计算时间的数值结果如表3所示； 当线性系统不相容时， 其数值结果如表4所示。从这2个表中可见， 除了非常病态的矩阵Trefethen_300外，GGS方法和GRCD方法的迭代次数几乎相同。但对于所有矩阵， GGS方法的计算时间都小于GRCD方法， 计算时间加速比至少可达到1.531 5。

表3 GGS和GRCD 2种方法在真实数据矩阵时求解相容系统的数值结果

Tab. 3 Numerical results of solving consistent systems with real‑world data matrices by using the GGS and the GRCD methods

矩阵名称	$\mathrm{阶}\mathrm{数}$	稠密度/%	$\mathrm{条}\mathrm{件}\mathrm{数}$	IT			CPU计算时间
				GGS	GRCD	IT speed-up	GGS	GRCD	CPU speed-up
abtaha1	14 596×209	1.68	12.23	14 888	13 966	0.938 0	8.255 0	12.642 8	1.531 5
Cities	55×46	53.04	207.15	29 181	40 937	1.402 9	0.174 7	1.849 7	10.588 6
divorce	50×9	50.00	19.39	634	647	1.020 0	0.002 8	0.031 6	11.222 2
WorldCities	315×100	23.87	66.00	5 011	5 011	1.000 0	0.077 2	0.291 6	3.777 3
Trefethen_300	300×300	5.20	1 772.69	3 210	1 374	0.428 0	0.041 6	0.073 4	1.766 9
cage5	37×37	17.02	15.42	1 477	1 624.4	1.099 8	0.006 6	0.070 0	10.666 7

表4 GGS和GRCD 2种方法在真实数据矩阵时求解不相容系统的数值结果

Tab. 4 Numerical results of solving inconsistent systems with real‑world data matrices by using the GGS and the GRCD methods

矩阵名称	$\mathrm{阶}\mathrm{数}$	稠密度/%	$\mathrm{条}\mathrm{件}\mathrm{数}$	IT			CPU计算时间
				GGS	GRCD	IT speed-up	GGS	GRCD	CPU speed-up
abtaha1	14 596×209	1.68	12.23	11 264	12 571	1.116 0	6.275 0	11.303 4	1.801 3
Cities	55×46	53.04	207.15	28 449	39 752	1.397 3	0.171 6	1.827 8	10.653 9
divorce	50×9	50.00	19.39	552	497	0.899 8	0.002 8	0.021 3	7.555 6
WorldCities	315×100	23.87	66.00	3 532	3 576	1.012 5	0.055 0	0.205 0	3.727 3

因此，数值实验显示GGS方法的迭代次数与GRCD方法几乎相同， 但在所有情形中， 贪婪Gauss-Seidel方法在计算时间上总是优于贪婪随机坐标下降方法。

4 结论与展望

针对大型线性最小二乘问题， 提出了一类新的贪婪Gauss-Seidel方法，理论分析了新方法的收敛性。数值实验表明，本文方法虽然与贪婪随机坐标下降方法的迭代次数几乎相同， 但所需计算时间更少。主要原因在于本文方法不仅避免了矩阵$\mathit{A}$所有列范数的计算， 而且指标集合的元素个数更少， 从而减少了每次迭代的计算时间。

众所周知， 对于Gauss-Seidel方法而言， 工作列的选取准则在整个迭代过程都有着十分重要的影响。如何设计一个随机的列选取准则改进贪婪Gauss-Seidel方法需要进行进一步的研究。

作者贡献声明

李寒宇：主要负责本文的指导和修订工作，包括文章框架结构、方法分析和验证等。

张彦钧：主要负责本文的初稿撰写工作，包括算法推导、理论证明与数值实现。