貪婪的分塊正則化kaczmarz

李婉婷

（成都理工大學 數理學院，四川 成都 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%，兩種算法得到的相對誤差如下表所示。

images/BZ_161_242_2336_307_2376.png0．01 0．1 0．2 0．5 GBK 6．6255e+16 2．4486e+18 2．7127e+17 2．0541e+20 GBK-Tik 6．3794e-04 3．9487e-03 6．9821e-02 2．7452e-01

4．結論

本文提出了一種貪婪的分塊正則化kaczmarz(GBK-Tik）算法，并通過數值實例證明，該算法優越于貪婪的分塊kaczmarz算法，在處理實例1中的適定問題時候，GBK-Tik算法的收斂速度比GBK算法快，且相對誤差比GBK算法小，在處理實例2中的不適定問題時，GBK-Tik算法所得相對誤差比GBK算法小很多。