隨機(jī)數(shù)值方法及其在隨機(jī)Kaczmarz算法中的應(yīng)用.pdf

1、Kaczmarz算法是一種求解超定線性系統(tǒng)Ax=b的有效方法。Kaczmarz算法在諸如圖像重構(gòu)，數(shù)字信號(hào)處理等信息科學(xué)領(lǐng)域都有廣泛的應(yīng)用。與傳統(tǒng)的Kaczmarz算法比較，在經(jīng)典Kaczmarz算法基礎(chǔ)上建立起來的隨機(jī)化的Kaczmarz算法(RK算法)，其算法效率更加高效，收斂速度可以達(dá)到指數(shù)收斂。對(duì)于一定條件下的超定線性系統(tǒng)，數(shù)值模擬以及理論分析表明，RK算法比包括著名的共軛梯度算法在內(nèi)的傳統(tǒng)算法更加高效。本文進(jìn)一步研究了隨機(jī)化R

2、K算法的設(shè)計(jì)，主要?jiǎng)?chuàng)新性工作包括：
　　1.基于矩陣低秩近似的隨機(jī)RK算法設(shè)計(jì)
　　通過設(shè)計(jì)一種具有正交結(jié)構(gòu)的低秩預(yù)條件矩陣，得到了求解線性方程組Ax=b的預(yù)條件RK算法，從理論上證明了本文算法提高了隨機(jī)RK算法的收斂性，而當(dāng)mn時(shí)，數(shù)值實(shí)驗(yàn)驗(yàn)證了本文算法比傳統(tǒng)的隨機(jī)RK算法具有更快的收斂速度與計(jì)算效率。
　　2.基于Nesterov加速迭代格式的含噪RK迭代算法
　　基于隨機(jī)近似投影(Randomized Ap

3、proximate Orthogonal Projection)思想，本文將RK算法(REK)拓廣到求解含噪聲的超定線性系統(tǒng)，算法主要思想是將b正交投影到A的列向量形成的空間上，從而可以盡可能的減少噪聲的影響，并通過Nesterov加速迭代格式對(duì)改進(jìn)REK算法進(jìn)行加速，從而建立了一種加速迭代算法(AREK:Accelerated Randomized Extended Kaczmarz)。數(shù)值實(shí)驗(yàn)表明，當(dāng)矩陣A是稠密矩陣且A的最小的奇異

4、值很小時(shí)，AREK算法相對(duì)于REK算法有更好的收斂性。
　　3.基于隨機(jī)行選取與最小二乘法的分塊RK迭代算法
　　Needell和Tropp給出了分塊隨機(jī)分塊Kaczmarz算法，該算法的主要思想是將當(dāng)前迭代量投影到A的子矩陣的解空間。本文基于隨機(jī)行選取與最小二乘法相結(jié)合，建立了一種新的分塊RK迭代法，其基本步驟是：以子矩陣條件數(shù)作為約束條件，選取矩陣A中若干行，分割得到若干子塊矩陣，然后實(shí)現(xiàn)分塊RK迭代，數(shù)值實(shí)驗(yàn)表明了算法