基于貪婪隨機Kaczmarz方法的算法研究

張選靜 何清龍 陳敏 范芷萍 劉麗霞

【摘要】貪婪隨機Kaczmarz算法（GRKM）是一種求解大型稀疏矩陣方程組的有效方法.基于GRKM方法和Nesterov加速策略，本文給出了一種求解線性方程組的快速AGREK迭代方法.AGREK算法的主要思想是在每步迭代中依據更有效的概率準則進行隨機正交投影并采用Nesterov技術進行加速.為了驗證AGREK算法的有效性，針對隨機矩陣線性方程組進行數值實驗，數值實驗表明本文給出的AGREK方法是可行和高效的.

【關鍵詞】線性方程組;Kaczmarz方法;AGREK方法

【基金項目】貴州大學大學生創新創業訓練計劃項目資助，項目編號：2018520067.

一、引?言

在理論研究和實際工程問題中，Kaczmarz方法是一種有效的迭代方法，該方法每次迭代將當前點投影到選取行所形成的超平面上.經過多次迭代，從而達到逐漸接近線性方程組的真實解的目的.若初始估計量為x0，則求解線性方程組Ax=b的Kaczmarz方法迭代過程為：

xk+1=xk+（b（i）-A（i）xk）‖A（i）‖22（A（i））T，

其中，i=kmodm+1，A（i）表示系數矩陣A的第i行，b（i）表示右端項b的第i個元素，（·）T表示轉置，‖·‖2表示歐幾里得范數.

基于Kaczmarz方法的研究一直是數值代數理論研究的熱點.Strohmer和Vershynin提出具有指數收斂速度的隨機化Kaczmarz方法，使用隨機選取系數矩陣A的行進行投影，大大提高Kaczmarz方法的收斂速度[1].Zhong基于更加有效的隨機選取行的準則，建立了貪婪隨機Kaczmarz方法（Greedy Randomized Kaczmarz Method，GRKM）[2].向徐提出了基于Nesterov加速技術的AREK算法[3].本文基于GRKM算法中提出的引入指標集的概率選擇準則和Nesterov加速的AREK算法，給出了一種快速高效的AGREK算法并給出數值試驗以驗證方法的有效性.

二、AGREK算法

輸入：m×n系數矩陣A，向量b，迭代次數l，初始化v0=x0=0，z0=b，w-1=0.

輸出：xl

for k=0，1，…，l-1 do

STEP 1.求解方程w2k=w2k+w2k-1λ-1mwk-w2k-1=0，令wk的值為方程組的較大根.

計算βk=m-wkλwk（m2-λ），tk=1-wkλm.

STEP 2.選擇jk∈{1，2，…，n}列的概率為：

pr（jk）=‖A（j）‖22‖A‖2F.

STEP 3.隨機正交投影：zk+1=zk-（A（jk）T，zk）‖A（jk）‖22A（jk）.

STEP 4.計算

εk=121‖b-Axk‖22max1≤ik≤m|b（ik）-A（ik）xk|2‖A（ik）‖22+1‖A‖2F.

STEP 5.定義正整數指標集uk={ik||b（ik）-A（ik）xk|2≥εk‖b-Axk‖22‖A（ik）‖22}.

STEP 6.根據

r（i）k=b（i）-A（i）xk，if?i∈uk，0，otherwise，

計算向量rk中的第i個分量r（i）k.

STEP 7.選擇ik∈uk行的概率為：pr（ik）=|r（ik）k|2‖rk‖22.

STEP 8.Nesterov加速過程

yk=βkvk+（1-βk）xk，

xk+1=yk-（A（ik）T（A（ik）yk-（b（ik）-z（ik）k）））‖A（ik）‖22，

vk+1=tkvk+（1-tk）yk-wk（A（ik）T（A（ik）yk-（b（ik）-z（ik）k）））‖A（ik）‖22

end for.

三、數值實驗

（一）適定方程組

本節中的數值實驗均以零向量為初始值，即x0=（0，0，…，0），使用隨機生成的矩陣A∈Rm×n（m=n）和向量x∈Rn 進行數值實驗，右端項b=Ax，程序每運行100次對應1次迭代次數.對當前迭代xk，若滿足相對誤差RSE<10-6或已經達到最大運行次數，算法停止運行，將其視為一次數值實驗.為了避免隨機性結果，求解同一個線性方程組的數值實驗重復進行5次，最終實驗結果取5次數值實驗的均值.實驗結果如下.

由表1、圖1、圖2顯示的實驗結果可以看出，求解適定方程組時，當達到最大迭代次數時，GRKM方法仍不能得到滿足相對誤差條件的有效解，AREK方法、AGREK方法均收斂得比GRKM方法快，AGREK方法比AREK方法收斂得更快.

（二）超定方程組

求解超定線性方程組Ax=b，A∈Rm×n（m>n）.我們利用該方程的最小二乘解作為該方程的廣義解，于是廣義解等價于求解線性方程組ATAx=ATb.程序每運行1次對應1次迭代次數.對當前迭代xk，仍為了避免隨機性結果，求解同一個線性方程組的數值實驗每次進行5次，實驗結果取5次數值實驗的均值.實驗結果如表2所示.

由表2可知，當求解超定方程組時，三種方法隨著方程數目的增加，求解隨機矩陣所需的迭代時間和迭代次數呈現減小的趨勢.當求解超定矩陣時，GRKM方法收斂得比AREK和AGREK方法快，AGREK方法收斂得比AREK方法快.

四、結?語

針對求解線性方程組問題，本文基于GRKM方法和AREK方法，提出了一種更加快速有效的AGREK方法.AGREK方法兼具GRKM方法的概率準則優點和Nesterov加速特性，因此，能夠快速求解線性方程組.數值試驗表明，當求解線性方程組時，AGREK方法的收斂速度優于AREK方法和GRKM方法，驗證了AGREK算法的高效性.

【參考文獻】

[1]T.Strohmer and R.Vershynin.A randomized Kaczmarz algorithm with exponential convergence[J].Journal of Fourier Analysisand Applications，2008（15）：262.

[2]Zhong Zhi Bai，Wen Ting Wu.On greedy randomized Kaczmarz method for solving large sparse linear systems[J]，SIAM J.Sci.Comput.，2018（40）：A592-A606.