秩虧最小二乘問題的預條件AOR迭代法

沈海龍, 張麗紅

(東北大學 理學院, 沈陽 110819)

?

秩虧最小二乘問題的預條件AOR迭代法

沈海龍, 張麗紅

(東北大學 理學院, 沈陽 110819)

秩虧最小二乘問題來源于統計學問題、最優化問題等科學與工程計算領域。由于實際問題所對應的線性方程組的系數矩陣的階數比較大,且秩虧,換句話說,矩陣A是不可逆的,使其求解變得更為復雜,因此,研究求解秩虧最小二乘問題的高效方法就變得尤為重要。為了求解秩虧最小二乘問題,在預處理基礎上提出了二分塊的AOR迭代法;研究了新建立的AOR迭代法的收斂性和最優參數的選取,得到了一些相關的定理。數值例子驗證了所給方法的可行性。數值實驗和理論都表明:新的AOR方法的計算格式更加簡單、收斂速度快、并具有廣泛的適用性,同時行滿秩矩陣A1的選取要比文獻[8]中可逆方陣A11的選取更方便。

秩虧損; 最小二乘; SOR方法; AOR方法; BSOR方法

0 引 言

在解決許多應用問題時,往往會遇到如下定義的秩虧最小二問題

‖

其中:A∈Rm×n(m≥n):rank(A)=k

對于最小二乘問題的深入研究,從20世紀60年代才真正開始,而且隨著計算機技術和計算機速度的飛速進步,以及科學計算問題的實際需要而有了長足的發展,各種廣義的和修正的最小二乘問題的研究方興未艾。近年來,諸多學者考慮用迭代法來求解秩虧問題。利用迭代法解秩虧最小二乘問題有節省存儲空間、減少計算開銷等優點,在工程計算中有很重要的應用。因此,尋找秩虧損最小二乘問題的新解法, 即構造更優的迭代格式,使其精確度更高、誤差更小、收斂速度加快,更好地應用于實際生產、生活中就具有重要的現實意義。一些學者研究出了適用于系統(1)的迭代方法,具有代表性的如文獻[7]通過預處理技術將系數矩陣A分成2塊,寫成3×3塊的增廣矩陣。然后用三分塊SOR迭代法和二分塊SOR迭代法來解決生成的3×3塊增廣線性方程組,文獻[8]沿著文獻[7]的思路,研究了用AOR迭代法找系統(1)的解,并且給出了AOR迭代法收斂的一個充分條件。

本文建立了預處理條件的二分塊AOR迭代法;研究了預處理條件下的二分塊AOR迭代法的收斂性和最優參數的選取,得到了一些相關的定理;然后給出了利用新的AOR迭代法找A+b的定理和推論。數值算例驗證了所給方法的可行性和有效性。數值實驗和理論都表明:新的AOR迭代法迭代速度快、計算格式簡單,并具有廣泛的適用性,同時本文中行滿秩矩陣A1的選取要比文獻[7]中可逆方陣A11的選取更方便。

1 二分塊AOR迭代法的格式及收斂性

考慮如下方程

定理1 矩陣Js的特征值在如下區間I:[-βi,0],這里β=‖BC‖2。

定理2Hγ,ω半收斂當且僅當參數γ,ω滿足條件

證明 由于Hγ,ω半收斂當且僅當如下3個條件成立:

1) (1-ω)I半收斂;

2)Tγ,ω半收斂;

3) [I-(I-(1-ω)I)(I-(1-ω)I)-1]Rγ,ω[I-(I-Tγ,ω)(I-Tγ,ω)-1]=0。

2 用AOR迭代法找A+b

因為z(x0)是增廣系統(3)的解,z(x0)可以寫成

3 數值算例

本節給出數值例子證明上面的結論和幾個相關的問題,在計算中迭代中止的條件為‖Xk+1-Xk‖2<10-4,所有的計算均是在INTELPENTIUM1.8GHZ(256MRAM),Windows7系統下使用Matlab7.0獲得的。

例 針對如下方程組,分別用二分塊、四分塊AOR迭代法求A+b。

方法1 將系數矩陣A分解成二分塊,設

由定理4,計算可得ω0=1.4142。

表1 第k步的迭代值Tab.1 The kthstep of iteration value

方法2 將系數矩陣A分解成四分塊,設

‖B‖2=1,

4 結 論

在終止條件‖Xk+1-Xk‖2<10-4下,當γ=0.8時,二分塊AOR迭代法在經過有限次迭代后逼近最小二乘解,但是四分塊AOR迭代法在300次迭代內是不逼近最小二乘解的。理論跟數值算例都說明將線性方程組的系數矩陣分成二分塊要比四分塊迭代速度更快、更具普遍性、更方便。

[1]VARGARS.MatrixIterativeAnalysis[M].Prentice-Hall:EnglewoodCliffs, 1962:105-113.

[2]YOUNGDM.IterativeSolutionofLargeLinearSystems[M].NewYork:AcademicPress, 1971:150-160.

[3]VARGARS,NIETHAMMERW,CAIDY.P-cyclicmatricesandthesymmetricsuccessiveoverrelaxationmethod[J].LinearAlgebraandItsApplications, 1984,58:425-439.

[4]MARKHAMTL,PLEMMONSRJ,NEUMANNM.Convergenceofadirect-iterativemethodforlarge-caleleastsquaresproblems[J].LinearAlgebraandItsApplications, 1985,69:155-167.

[5]SANTOSCH,SILVABPB,YUANJY.BlockSORmethodsforrank-deficientleastsquaresproblems[J].JournalofComputationalandAppliedMathematics, 1998,100:1-9.

[6]MILLERVA,NEUMANNM.Successiveoverrelaxationmethodsforsolvingtherankdeficientleastsquaresproblem[J].LinearAlgebraandItsApplications, 1987,88/89:533-557.

[7]TIANH.Accelerateoverrelaxationmethodsforrankdeficientlinearsystems[J].AppliedMathematicsandComputation, 2003,140:485-499.

[8]ZHENGB,WANGK.Symmetricsuccessiveoverrelaxationmethodforsolvingtherankdeficientlinearleastsquaresproblem[J].AppliedMathematicsandComputation, 2005,169:1305-1323.

[9]魏木生. 廣義最小二乘問題的理論和計算[M]. 北京:科學出版社, 2006:30-45.

Study of 2-block AOR iterative method for rank deficient least squares problems

SHEN Hailong, ZHANG Lihong

(College of Science, Northeastern University, Shenyang 110819, China)

Rank-deficient least squares problems arise from many scientific and engineering computations such as statistics, optimal problem and so on. In the practical problems, since the order number of corresponding coefficient matrix of linear equations is larger, and the rank of matrix is a deficit. In other words, matrixAis irreversible. Then solving process is become more complex. So it is very important to study of the suitable iterative methods for rank-deficient least squares problems. For solving the least square problems with rank-deficient, the 2-block AOR method by preconditioning technique was given. The convergence analysis of the new AOR method and the choice of optimal relaxation parameters were studied. The corresponding theorems were gotten. Numerical examples showed the effectiveness of new method. It suggests that the new iterative AOR method is simpler, faster in convergence speed, more extensive applicability than the method in [8]. Meanwhile, matrixA1is full row rank, it is more convenient than the requirement ofA11in [18].

rank deficient; least squares; SOR method; AOR method; BSOR method

2016-01-03。

國家自然科學基金資助項目(11071033); 中央高校基本業務費資助項目(090405013)。

沈海龍(1971-),男(朝鮮族),吉林延邊人,東北大學講師,博士。

1673-5862(2016)03-0333-05

O241.2

A

10.3969/ j.issn.1673-5862.2016.03.017