李婉婷

（成都理工大学 数理学院，四川 成都 610059)

经典的kaczmarz算法[1]是用来求解大型相容线性方程组的算法，给定一个实矩阵和一个实向量，求相容线性系统的解：

Kaczmarz算法根据选择方法的不同，可以分为随机性和确定性两大类。在随机化的Kaczmarz算法中，行索引由根据某种概率分布随机选择，2009年Strohmer与Vershynin提出了指数收敛速度的随机Kaczmarz算法[2]，使kaczmarz算法得到了改进和扩展。在确定性Kaczmarz算法中，行索引ki是在循环搜索或基于贪婪策略中选择的。2020年，Yu-Qi Niu和Bing Zheng在贪婪的kaczmarz算法中加入了分块的思想，提出了贪婪块kaczmarz算法[3]。

1．贪婪块kaczmarz算法

算法1：贪婪块kaczmarz算法（GBK)输入：A， b，0x和参数 (0,1]η∈ ；对 0,1k= …运行以下步骤，直到满足终止准则；计算：2()1 2■■ε η ≤≤-max i ik ■k im■b Ax A=■■■■■■()2 i确定行索引集：{2 L= - ≥: k k k k k i k k i i b A x Aε()()i 2 2}；更新：†x x A b Ax= + -k k k-1-1( )( )L L L k k k

在上述算法中， ()iA表示矩阵A的第i行，()ib表示向量b的第i行，kx表示向量x的第k次迭代得到的迭代解。

2．正则化贪婪块kaczmarz算法

求解（1）可以转换成求解以下问题：

本文采用正则化，可以通过求解问题（3）得到问题（2）的近似解[4]：

由算法1和（3），得到以下算法2。

算法2.正则化贪婪块kaczmarz算法输入 0,, ,,, and parameter (0,1]AbxLωα η∈A=b ■■■ ■=■■■ ■AL ω,b 0;■ ■ ■■对 0,1k=…images/BZ_160_1554_1702_1696_1752.png运行以下步骤，直到满足终止准则；■计算：■-max i ik ε η ≤≤■2 k()1 2=■■■■■■im■b Ax A；()2 i确定行索引值:I=-≥ ;{: k k k k k i k k i i b 2 A x Aε()()i 2 2}选出kI中小于m+1的行，得到行索引kJ，计算 α T k k k i x-1-1= - - ;( )( )x x A A x b A k k J,J 2 J,k J F k ,选出kI中大于m的行，令i=i-m k k ，计算ω x x b x x k k k i i i m k k i i- -= +- -+1 1 1( )()-1 2 k k k +k k ω ω x x b x x k k k i i i m k k i i- -= -- -+1 1 1( )()2 1 1 2 k k k ++-k+1 k ω

3.数值实例

实例1 假设A的维数为m×n，x*的维数为n×1，aij为矩阵A的第(,)ij个元素，ijx为向量x的第(,)ij个元素，ija和ijx都从正态分布中得出的，，对be加高斯噪声得到b，再分别用GBK和GBK-Tik来求解线性方程 xbA= ，并重复实验一百次，求得每次迭代后的平均相对误差和迭代次数的关系图。

图（1）

图（2）

实例2 矩阵A来自于正则化工具箱测试问题shaw[5]，，精确解xe=sin(0.01:0.01:π)，，η为噪声水平，我们分别取η的值为0.01%，0.1%，0.2%，0.5%，两种算法得到的相对误差如下表所示。……