沈海龍, 張麗紅

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

?

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

沈海龍, 張麗紅

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

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

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

0 引 言

在解決許多應(yīng)用問題時(shí),往往會(huì)遇到如下定義的秩虧最小二問題

‖

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

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

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

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

考慮如下方程

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

定理2Hγ,ω半收斂當(dāng)且僅當(dāng)參數(shù)γ,ω滿足條件

證明 由于Hγ,ω半收斂當(dāng)且僅當(dāng)如下3個(gè)條件成立:

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

因?yàn)閦(x0)是增廣系統(tǒng)(3)的解,z(x0)可以寫成

3 數(shù)值算例

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

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

方法1 將系數(shù)矩陣A分解成二分塊,設(shè)

由定理4,計(jì)算可得ω0=1.4142。

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

方法2 將系數(shù)矩陣A分解成四分塊,設(shè)

‖B‖2=1,

4 結(jié) 論

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

[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]魏木生. 廣義最小二乘問題的理論和計(jì)算[M]. 北京:科學(xué)出版社, 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。

國家自然科學(xué)基金資助項(xiàng)目(11071033); 中央高校基本業(yè)務(wù)費(fèi)資助項(xiàng)目(090405013)。

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

1673-5862(2016)03-0333-05

O241.2

A

10.3969/ j.issn.1673-5862.2016.03.017