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

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

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

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

【學位級別】：碩士

【部分圖文】：

–1算法3的收斂曲線

碩士學位論文(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ù)矩陣與圖2–1是同一矩陣.在圖2–1中,我們繪制算法3的收斂曲線.可以看出,算法在較大t時收斂更快.我們在圖2–2中繪制了算法3(第一次迭代)對于不同參數(shù)t=2,4,8,16時的工作行的對應(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)顯然,此時選擇到工作行的概率(幾乎)為1.因此,我們有了以下算法:12

碩士學位論文=‖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è)和符號,算法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ù)更多.這是因為算法5每次只選取到矩陣的的少數(shù)行進行計算.我們對算法5賦予不同的采樣率與貪婪方法以及算法4進行了數(shù)值實驗,實驗結(jié)果如下圖:圖2–3算法5(選擇不的同參數(shù)η)與GRK算法的收斂曲線Figure2–3ConvergencecurvesofAlgorithm5(withdifferentη)andGRK18


本文編號：2898438