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

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

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

【文章頁數】：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時的情況.系數矩陣與圖2–1是同一矩陣.在圖2–1中,我們繪制算法3的收斂曲線.可以看出,算法在較大t時收斂更快.我們在圖2–2中繪制了算法3(第一次迭代)對于不同參數t=2,4,8,16時的工作行的對應概率.可以看出,隨著t的增加,具有較大概率的行變得更容易被選取到.因此,自然的想法是在算法3中設置t→∞.根據(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),我們得到以下關于算法收斂性的定理5.定理2.10.根據以上假設和符號,算法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,即前者可能比后者的迭代次數更多.這是因為算法5每次只選取到矩陣的的少數行進行計算.我們對算法5賦予不同的采樣率與貪婪方法以及算法4進行了數值實驗,實驗結果如下圖:圖2–3算法5(選擇不的同參數η)與GRK算法的收斂曲線Figure2–3ConvergencecurvesofAlgorithm5(withdifferentη)andGRK18


本文編號：2898438