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

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

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

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

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