共軛梯度法中預條件子的優(yōu)化

共軛梯度法中預條件子的優(yōu)化郭存柱【摘要】為了降低方程組求解中共扼梯度法系數(shù)矩陣的條件數(shù)，提高收斂速度，常用預處理方法將原方程進行等價轉化,同時預條件子既要接近原系數(shù)矩陣，又要容易求其逆矩陣。本文從尋求對角預條件子出發(fā)，用矩陣的特征值分解方法解出了預處理后系數(shù)矩陣特征值矩陣的顯式表達，得到對角預條件子矩陣的最優(yōu)選擇,并予以證明。給出了三個p-范數(shù)預條件子，將之與常用的預條件子進行對比，實例檢驗表明三個p-范數(shù)預條件子的作用更優(yōu)越，且使算法收斂更快。【期刊名稱】《應用數(shù)學進展》【年(卷)，期】2017(006)004【總頁數(shù)】8頁(P651-658)【關鍵詞】預條件子;條件數(shù);特征值分解;<i>p</i>-范數(shù)預條件子【作者】郭存柱【作者單位】［1］隴南師專數(shù)信學院，甘肅隴南【正文語種】中文【中圖分類】O24使用求解方程組Ax=b(其中A為n階對稱正定矩陣，x為nxl未知向量，b為nxl已知向量)，理論上可以在n步之內得到精確解。但由于機器的舍入誤差，可能需迭代超過n步才能達到所需精度的解。尤其當A的條件數(shù)很大時，迭代求解過程總體收斂會很慢，因之這一優(yōu)越的方法在一段時間曾被擱置。直到引入預條件處理方法(用P-1乘以原方程組，得到同解方程組P-1Ax=P-1b),來降低系數(shù)矩陣的條件數(shù)(cond(P-1A)lt;lt;cond(A))，提高了迭代速度和穩(wěn)定性，才使共扼梯度法在工程、微分方程數(shù)值求解和最優(yōu)化等領域得到廣泛應用。預條件子(亦稱條件預優(yōu)矩陣)P的選取應接近A，且容易求逆，正對角陣為首選。此前共扼梯度法常用的預條件子有以下三種。取P=D，其中D為A的對角陣。取P=(D+3L)D-1(D+3U),其中A被分解為A=D+L+U,D、L、U為對角陣、下三角陣、上三角陣，3頃0,2)。當3=1時即為Gauss-Seidel預條件子。由MeijerinkJ.A.和VandervorstA.1977年提出［3］。將A分解成A=LLT+R,其中L為下三角陣，且與A有一樣的稀疏性(當Aij=0時，有Lij=0)。取P=LTL,或？=1。已知矩陣A，求矩陣P，使得P-1A的條件數(shù)最小，即設正定矩陣A的特征值分別為入i>0,n=12...,n,則A的譜條件數(shù)為設n階矩陣A的特征值分別為入1,入2,...,入n,相應的特征向量為丫"=12..小為標準正交向量組，即記A=diag(入1,入2,...,入n),「=(Y1，Y2,...，Yn),其中/139(入1,入2,...,入捫表示對角元素分別為入1,入2,...An的對角矩陣，則A可分解為設P-1A的特征值分別為pi>0,相應的特征向量為湖=1,2,...,n為標準正交向量組,即fiM=diag(p1,p2,./pn),A=(81/82/.,8n),由矩陣的譜分解定理首先想到的是P=A，因cond(P-1A)=cond(A-1A)=cond(I)=1，條件數(shù)最小。但求A-1和解方程組是同一問題，當A的條件數(shù)很大時誤差會很大，且其時間復雜度為O(n3).將(1)兩邊乘以P-1得由cond(AB)<cond(A)cond(B)，且AB與BA有相同的非零特征值[4],為最小°cond(P-1「A「T)趨向于最小值1。因此，對角預條件子P的最優(yōu)選擇是A的特征值矩陣A,此時，在數(shù)值計算中，當A的特征值非常接近于0時，由于機器的舍入誤差容限，計算機將其按0對待，導致無法求逆。因而，尋找可逆矩陣P近似替代人取由A的各列的p-范數(shù)為對角元素的矩陣作為預條件子P，即其中，表示A的第j列的p-范數(shù)，分別取p=1,2e，可得以下三種不同列范數(shù)預條件子。取當A為正定對角矩陣時，三個p-范數(shù)預條件子都等于A。使用Matlab的預條件子共扼梯度函數(shù)pcg和雙線性共扼梯度函數(shù)bicg。實例1.當A為13階Hilbert矩陣，x=ones(n)(n個1);b=A*x;cond(A)=8.3042x1019，用1-范數(shù)預條件子1-步達精確值、8-范數(shù)預條件子13步相對誤差小于10-16、2-范數(shù)預條件子17步相對誤差小于10-16，其次是Jacobi、Gauss-Seidel預條件子和不用預條件子，用不完全Cholesky預條件子表現(xiàn)最差。如圖1。實例2.當n=1000;A=diag((1:n).人2)+diag((1:n-20).人(1/2),20)+diag((1:n-20).人(1/2),-20);x,b同例1(下同)；cond(A)=1.0023x106,用1-范數(shù)預條件子2步達精確值、Gauss-Seidel預條件子6步相對誤差小于10-16,2-范數(shù)、8-范數(shù)、Jacobi預條件子17步相對誤差小于10-16，其次是不完全Cholesky預條件子，不用預條件子收斂非常慢，如圖2。實例3.當n=33;A=log([5:n+4]')*([1:n].人2);cond(A)=1.2857x1020，用1-范數(shù)、8-范數(shù)預條件子迭代1步達精確值，2-范數(shù)預條件子迭代1步相對誤差小于10-16,無法進行Cholesky分解，如圖3。實例4.當n=3000;A=diag(1./(3:n+2))+diag(1./(n-1:1),1)+diag(1./(n-1：1),-1)；cond(A)=1.0007x103，全部預條件子表現(xiàn)都優(yōu)越，且用1-范數(shù)、2-范數(shù)、8-范數(shù)預條件子表現(xiàn)最好，1步達到精確值，如圖4。實例5.當n=2000;A=magic(n);A非正定,cond(A)=8.5285x1020,其它方法無法進行，用1-范數(shù)1步迭代達精確值，不用預條件子迭代10步相對誤差小于10-15,如圖5。實例6.當n=1000;A=diag((1:n))+diag(sin(1:n-3),3)+diag(sin(1:n-3),-3)+diag(sin(1:n-20),20)+diag(sin(1:n-20),-20)+diag(cos(1:n-100),100)+diag(cos(1:n-100),-100);cond(A)=1.3568x103,Gauss-Seidel預條件子表現(xiàn)優(yōu)越，迭代16步誤差即小于10-18，其次是不完全2-范數(shù)、8-范數(shù)、Jacobi、1-范數(shù)、Cholesky預條件子，不用預條件子收斂非常慢，如圖6。共扼梯度法的算法復雜度取決于矩陣與向量乘積的次數(shù)，如恰當設計程序使每步迭代只有一次矩陣與向量的乘法，在矩陣稀疏時，時間復雜度為。而使用預條件子的共扼梯度法大大降低了復雜度，節(jié)省了計算的時間成本，提高了運算速度和精度。其中用列范數(shù)預條件子方法迭代次數(shù)遠遠小于矩陣階數(shù)n?？紤]到兩矩陣乘積、矩陣與向量乘積的復雜度，對稀疏矩陣而言，列Euclid范數(shù)、Gauss-Seidel范數(shù)、不完全Cholesky分解預條件子的復雜度都是O(n2)，而列最大模、絕對和預條件子復雜度為【相關文獻】SauerTimothy.數(shù)值分析[M].裴玉茹，馬賡宇，譯.北京:機械工業(yè)出版社,2015.林成森.數(shù)值計算方法[M].第2版.北京:科學出版社,2005.Meijerink,J.V.andVanderVorst,H.A.(1977)AnIterativeSolutionMethodforLinearSystemsofWhichtheCoefficientM