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

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

【關(guān)鍵詞】線性方程組;Kaczmarz方法;AGREK方法

【基金項(xiàng)目】貴州大學(xué)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目資助，項(xiàng)目編號(hào)：2018520067.

一、引?言

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

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

其中，i=kmodm+1，A（i）表示系數(shù)矩陣A的第i行，b（i）表示右端項(xiàng)b的第i個(gè)元素，（·）T表示轉(zhuǎn)置，‖·‖2表示歐幾里得范數(shù).

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

二、AGREK算法

輸入：m×n系數(shù)矩陣A，向量b，迭代次數(shù)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的值為方程組的較大根.

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

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

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

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

STEP 4.計(jì)算

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

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

STEP 6.根據(jù)

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

計(jì)算向量rk中的第i個(gè)分量r（i）k.

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

STEP 8.Nesterov加速過(guò)程

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.

三、數(shù)值實(shí)驗(yàn)

（一）適定方程組

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

由表1、圖1、圖2顯示的實(shí)驗(yàn)結(jié)果可以看出，求解適定方程組時(shí)，當(dāng)達(dá)到最大迭代次數(shù)時(shí)，GRKM方法仍不能得到滿足相對(duì)誤差條件的有效解，AREK方法、AGREK方法均收斂得比GRKM方法快，AGREK方法比AREK方法收斂得更快.

（二）超定方程組

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

由表2可知，當(dāng)求解超定方程組時(shí)，三種方法隨著方程數(shù)目的增加，求解隨機(jī)矩陣所需的迭代時(shí)間和迭代次數(shù)呈現(xiàn)減小的趨勢(shì).當(dāng)求解超定矩陣時(shí)，GRKM方法收斂得比AREK和AGREK方法快，AGREK方法收斂得比AREK方法快.

四、結(jié)?語(yǔ)

針對(duì)求解線性方程組問(wèn)題，本文基于GRKM方法和AREK方法，提出了一種更加快速有效的AGREK方法.AGREK方法兼具GRKM方法的概率準(zhǔn)則優(yōu)點(diǎn)和Nesterov加速特性，因此，能夠快速求解線性方程組.數(shù)值試驗(yàn)表明，當(dāng)求解線性方程組時(shí)，AGREK方法的收斂速度優(yōu)于AREK方法和GRKM方法，驗(yàn)證了AGREK算法的高效性.

【參考文獻(xiàn)】

[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.