一种基于Householder变换的RRGMRES算法

丁伯伦，凌婷婷，耿红梅

(1.扬州工业职业技术学院，江苏 扬州 225000；2.安徽信息工程学院，安徽 芜湖 241000)

0 引言

在科学技术与工程实践中，如优化控制理论、电路仿真、流体力学等领域，常常需要求解如下的大型稀疏线性方程组问题：

Ax=b

这里A∈Rn×n为稀疏的非奇异矩阵.

1 HGMRES算法和RRGMRES算法

GMRES算法首先是运用Arnoldi正交化过程在Krylov子空间上生成一组标准正交基v1，v2，…，vk，此时Krylov子空间可表示为：

κk(A，r0)=span{v1，v2，…，vk}=span{r0，Ar0，A2r0，…，Ak-1r0}

HGMRES是基于GMRES的一种优化算法，在第一步中不选择利用Arnoldi正交化过程，转而选择Householder变换来生成一组正交基.HGMRES算法满足：

其中Vk=(v1，v2，…，vk)是Krylov子空间的一组标准正交基，而正交基里的元素是由(k+1)个Householder矩阵乘积得到，即：vj+1=P1P2…Pj+1ej+1.

这种方法避免采用Arnoldi正交化过程，转而由Householder变换生成正交基，优点是后续迭代数值稳定性好，计算结果精确度高.

RRGMRES也是基于GMRES的一种改进算法，前面仍利用Arnoldi正交化过程生成一组正交基，但在最后构造残量表达式上做出了改变：

需求解一个新的最小二乘问题即可.该算法的优点是更能有效地减少存储空间和运算量.所以本文将这两种算法结合在一起，提出了一种新的算法，通过后面的数值实验证实，这种新的算法在解的收敛性和精确度上均具有较好的效果.

2 基于Householder变换的RRGMRES算法

首先利用Householder变换生成一组标准正交基，这里的vk+1可表示为具有k+1列的k+1个Householder矩阵的乘积[4]，即：

齐海峰也从一个小工人，一步步混到了厂办主任。官职升了，脾气还是没见长。妻管严就妻管严吧，半辈子不都吵过来了。

再进行下一个过程：基于算法中第k步残量表达式‖rk‖=‖r0-AVky‖，这里选择对其变型，改变残量表达式的形式[3].

这也是一个最小二乘问题，可求解得出y，进而得出第k步近似解：xk=x0+Vky.最后根据残量rk=b-Axk的结果来判定迭代算法是否终止[6].具体算法如下：

3)根据Householder变换递推得到一组标准正交基Vk=(v1，v2，…，vk).

5)形成近似解xk=x0+Vkyk，得到残量rk=b-Axk.

6)根据残量rk设置的要求判定迭代是否终止.

3 数值实验

下面列出一个大型稀疏矩阵，利用本文的算法求解，并使用Matlab软件进行数值模拟，通过观察图像来对比本文算法和RRGMRES算法的收敛效果.

例选取的矩阵A是一个1 024阶的分块方阵[7].

设置初始值x=(1，1，…，1)T，应用Matlab模拟出本文算法与RRGMRES算法的迭代步数与残量范数的关系图.

图1中实线表示本文算法，而虚线表示RRGMRES算法，横坐标表示迭代步数，纵坐标表示相对残量的对数.当残量rk设置为1.092e-08时，本文算法在142步就达到要求，而RRGMRES算法则需要194步才能达到要求.可见本文算法的收敛速度要更快些.

图1 两种算法对比图