發(fā)布時(shí)間：2020-12-04 23:34

　　Kaczmarz方法是求解大規(guī)模線性方程組的一種常用迭代方法.該方法在信號(hào)處理,圖像處理等領(lǐng)域得到了廣泛的應(yīng)用.經(jīng)典的Kaczmarz方法通過(guò)循環(huán)遍歷系數(shù)矩陣的行,在每次迭代時(shí)將當(dāng)前點(diǎn)投影到由工作行形成的超平面上.但是,由于遍歷矩陣的行的工作量很大,Kaczmarz方法在實(shí)際中往往運(yùn)行很慢.隨機(jī)Kaczmarz方法的出現(xiàn)大大提高了Kaczmarz方法效率.隨機(jī)Kaczmarz方法的一個(gè)明顯的缺點(diǎn)是它選擇系數(shù)矩陣中工作行的概率準(zhǔn)則存在失效的情況.最近Bai和Wu提出了一個(gè)新的概率準(zhǔn)則,該準(zhǔn)則在每個(gè)迭代步驟中盡可能地捕獲殘差向量較大分量對(duì)應(yīng)的行,并由此提出了一種貪婪隨機(jī)Kaczmarz方法（GRK）.然而,貪婪隨機(jī)Kaczmarz方法在矩陣規(guī)模較大時(shí),工作量非常大,不適于大數(shù)據(jù)問(wèn)題的求解.本文的主要貢獻(xiàn)如下:第一、我們從概率顯著性的角度出發(fā),提出了一種部分隨機(jī)Kaczmarz方法,它可以降低貪婪隨機(jī)Kaczmarz方法所需的計(jì)算成本,并建立了收斂性結(jié)果.第二、基于Chebyshev大數(shù)定律和Z-檢驗(yàn),我們將簡(jiǎn)單隨機(jī)抽樣方法應(yīng)用于部分隨機(jī)Kaczmarz方法,提出了新算法,并證明了其收斂性.... 

【文章來(lái)源】：中國(guó)礦業(yè)大學(xué)江蘇省 211工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：51 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

–1算法3的收斂曲線

碩士學(xué)位論文(a)t=2(b)t=4(c)t=8(d)t=16圖2–2算法3中工作行的概率Figure2–2ProbabilitiesoftheworkingrowsinAlgorithm3圖2–2為算法3(第一次迭代)各行的概率在t=2,4,8,16時(shí)的情況.系數(shù)矩陣與圖2–1是同一矩陣.在圖2–1中,我們繪制算法3的收斂曲線.可以看出,算法在較大t時(shí)收斂更快.我們?cè)趫D2–2中繪制了算法3(第一次迭代)對(duì)于不同參數(shù)t=2,4,8,16時(shí)的工作行的對(duì)應(yīng)概率.可以看出,隨著t的增加,具有較大概率的行變得更容易被選取到.因此,自然的想法是在算法3中設(shè)置t→∞.根據(jù)(2.19),選擇第ik行的概率可以表示為如下形式:|r(ik)|‖A(ik)‖2=b(ik)A(ik)xkA(ik)2=max1≤j≤mb(jk)A(jk)xkA(jk)2(2.20)顯然,此時(shí)選擇到工作行的概率(幾乎)為1.因此,我們有了以下算法:12

碩士學(xué)位論文=‖xkx‖221±εkm1‖rk‖221±εkm1∑mjk=1,jk=jk1‖Ajk‖22≤‖xkx‖22(1εk)λmin(AHA)(1+εk)γ‖xkx‖22=1(1εk)‖A‖2F(1+εk)γκ(A)2‖xkx‖22.(2.37)由(2.27),類似的,存在0≤εk1,εk11,并滿足下式Ek1‖xkx‖22=‖xk1x‖221±εk1m1r2(ik1)1±εk1m1∑mjk1=1,jk1=jk2‖A‖2FA(jk1)22≤‖xk1x‖22(1εk1)λmin(AHA)(1+εk1)ξ‖xk1x‖22=1(1εk1)‖A‖2F(1+εk1)ξκ(A)2‖xk1x‖22.(2.38)從式(2.37)和(2.38),我們得到以下關(guān)于算法收斂性的定理5.定理2.10.根據(jù)以上假設(shè)和符號(hào),算法5收斂到x的收斂率期望為:E‖xk+1x‖22≤1(1εk)‖A‖2F(1+εk)γκ(A)21(1εk1)‖A‖2F(1+εk1)ξκ(A)2‖xk1x‖22.由定理2.10和定理2.7可以看出算法5的收斂速度可能稍慢于算法4,即前者可能比后者的迭代次數(shù)更多.這是因?yàn)樗惴?每次只選取到矩陣的的少數(shù)行進(jìn)行計(jì)算.我們對(duì)算法5賦予不同的采樣率與貪婪方法以及算法4進(jìn)行了數(shù)值實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如下圖:圖2–3算法5(選擇不的同參數(shù)η)與GRK算法的收斂曲線Figure2–3ConvergencecurvesofAlgorithm5(withdifferentη)andGRK18


本文編號(hào)：2898438