李婉婷

（成都理工大學(xué) 數(shù)理學(xué)院，四川 成都 610059)

經(jīng)典的kaczmarz算法[1]是用來求解大型相容線性方程組的算法，給定一個(gè)實(shí)矩陣和一個(gè)實(shí)向量，求相容線性系統(tǒng)的解：

Kaczmarz算法根據(jù)選擇方法的不同，可以分為隨機(jī)性和確定性兩大類。在隨機(jī)化的Kaczmarz算法中，行索引由根據(jù)某種概率分布隨機(jī)選擇，2009年Strohmer與Vershynin提出了指數(shù)收斂速度的隨機(jī)Kaczmarz算法[2]，使kaczmarz算法得到了改進(jìn)和擴(kuò)展。在確定性Kaczmarz算法中，行索引ki是在循環(huán)搜索或基于貪婪策略中選擇的。2020年，Yu-Qi Niu和Bing Zheng在貪婪的kaczmarz算法中加入了分塊的思想，提出了貪婪塊kaczmarz算法[3]。

1．貪婪塊kaczmarz算法

算法1：貪婪塊kaczmarz算法（GBK)輸入：A， b，0x和參數(shù) (0,1]η∈ ；對 0,1k= …運(yùn)行以下步驟，直到滿足終止準(zhǔn)則；計(jì)算：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）可以轉(zhuǎn)換成求解以下問題：

本文采用正則化，可以通過求解問題（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運(yùn)行以下步驟，直到滿足終止準(zhǔn)則；■計(jì)算：■-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，計(jì)算 α 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 ，計(jì)算ω 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.數(shù)值實(shí)例

實(shí)例1 假設(shè)A的維數(shù)為m×n，x*的維數(shù)為n×1，aij為矩陣A的第(,)ij個(gè)元素，ijx為向量x的第(,)ij個(gè)元素，ija和ijx都從正態(tài)分布中得出的，，對be加高斯噪聲得到b，再分別用GBK和GBK-Tik來求解線性方程 xbA= ，并重復(fù)實(shí)驗(yàn)一百次，求得每次迭代后的平均相對誤差和迭代次數(shù)的關(guān)系圖。

圖（1）

圖（2）

實(shí)例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．結(jié)論

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