張亞蕾，楊少靜

1.仰恩大學數(shù)學系，福建 泉州 362014；2.河北科技學院公共課部，河北 保定 071000

0 引言

現(xiàn)代社會當中許多科學和工程技術(shù)等實際問題都可以轉(zhuǎn)換歸納成為非對稱線性方程組的特征值和特征向量求解問題，也被稱為非對稱性方程組求解問題，例如醫(yī)學上的數(shù)據(jù)分析問題、圖像以及信號等問題的處理、化學反應問題等，最后都歸結(jié)為解決矩陣的特征問題，通過求解大規(guī)模的非對稱線性方程組

Rm×n(Cm×n)αi=λiαi

(1)

來解決實際問題.其中，Rn(Cn) 表示n維實(復)向量空間，Rm×n(Cm×n)表示m×n實(復)矩陣的全體，(λi,αi)i=1,2,...,n為Rm×n(Cm×n)的特征對( ‖αi‖=1).因此研究非對稱線性方程組的特征求解問題的數(shù)值方法具有非常重要的作用，關(guān)于探討算法設計的好壞，開發(fā)出更有效的算法也成為一個非常重要的問題.

為了求出更優(yōu)，精度更高的特征對，需要對算法的精度和實用性進行反復地研究.一個好的算法不僅需要具備數(shù)值收斂、占用的存儲空間小、運算量少，還需要易于計算機實現(xiàn).傳統(tǒng)方式解決此類問題應用Lanczos 算法，當原始矩陣規(guī)模龐大時，利用這種方法就存在著計算復雜，存儲量過大，實際問題中我們產(chǎn)生的矩陣都是上萬階，甚至于幾十萬階，因此它的速度和內(nèi)存問題就會格外突出.Lanczos 算法在求解時采用的是正交投影方法[1]，雖然只需要存儲4個向量，但是其特征值的精度不夠高.除此之外，隨著算法生成的Krylov子空間維度的增大，向量會逐漸失去正交性，直接導致算法的收斂速度和收斂性降低.為了解決這一系列的問題，對原始的Lanczos 算法進行改進和精化，使得求解出的特征對精度更高，速度更快.改變算法的解題方式，從正交投影的方式轉(zhuǎn)變成為雙正交的方式，由于矩陣空間維度擴大會影響向量的雙正交性，所以借助壓縮技術(shù)，在得到高精度特征值的同時維持其雙正交性，且能減少硬件的內(nèi)存消耗[2].

1 精細化對比

1.1 構(gòu)造三角矩陣

首先對非線性方程組進行初始化處理，將方程組轉(zhuǎn)換成等價的三角矩陣.非線性方程組的矩陣形式為

(2)

其中，大寫字母V,W,Y表示矩陣，小寫字母v,w表示向量.在三角化中，首先設定u為啟動向量，對于i=1,2,...,n,計算式(3)：

Wk+1(β1e1)=bAWk=Wk+1Yk+1(∶,k+1)

(3)

其中，β1是非負的且滿足Wk+1∈Rk+1,k+1，Wk+1為非對稱三角矩陣，Yk+1(∶k+1)表示的是將Wk+1的最后一列去除掉.通常情況下，要是想找到矩陣A的奇異三元組，則必須對Wk進行奇異值分解，接著用Wk的奇異值近似A的奇異值，將Wk的奇異值向量與Lanczos向量相結(jié)合并對A的奇異值向量進行逼近，則可進行三角化處理，設A為非對稱線性方程的等價矩陣表現(xiàn)形式，且A∈Rm×n(Cm×n)，b表示正向量且b∈Rm×n，k為整數(shù).執(zhí)行循環(huán)算法：

y=norm(b);v=b/y;g=A*v;x=v*g;g=g-x*v;T(1,1)=x;
fori=2:k;Y(i,i-1)=Y(i-1,i)=y;end

1.2 精化向量子空間的Ritz值

(4)

由多項式的連續(xù)性可以得出，位移點對于不需要奇異值的近似程度更好.用每一次計算出的那些不需要的Ritz值作為位移，即為準確位移.取那些不需要的近似奇異值(Ritz值)作為位移，由此得到重新啟動方法.

1.3 精細化投影

(5)

(6)

通過算法計算出近似值與真實值進行對比，對比兩種算法計算出的近似值與真實值之間的誤差，從而得出精化度對比結(jié)果.誤差估計以子空間迭代法為標準進行對比，計算是在IBM-PC機上進行的.兩種算法都是采用的多個初始向量進行迭代計算，精化Lanczos算法對所有初始向量采用了平行迭代格式，且借助了逐個加入初始向量的迭代格式.從而在取相同截斷值的情況下，精化Lanczos算法的初始向量實際參加迭代的次數(shù)更少.迭代次數(shù)越多則收斂越快，計算結(jié)果精度也就越高.針對誤差值的對比分析進行數(shù)據(jù)統(tǒng)計并繪制對比曲線如圖1所示.

圖1 精細度對比曲線Fig.1 The curve of precision contrastion

結(jié)合圖中曲線分析，受收斂作用的影響，兩種算法的精度隨著求解數(shù)量的增加而呈上升趨勢.數(shù)量較少時精化Lanczos算法的精度較低，比Lanczos算法的精度低102，待數(shù)量增多后精化Lanczos算法的誤差急劇上升，最后維持在102以上.

2 收斂效果對比

表1 Lanczos算法與精化Lanczos算法的收斂效果Tab.1 The convergence effect of Lanczos algorithm and refined Lanczos algorithm

從表1中可知，兩種算法在運行過程中得到的收斂結(jié)果相似，但由于在算法運行當中的收斂效果主要體現(xiàn)在算法的運行速度上，由于精化算法自身具備收斂檢驗和重啟操作，所以精化Lanczos算法計算相對更加簡單快速.

3 時間消耗對比

時間消耗是檢測一個算法質(zhì)量和效率的重要參考依據(jù)，在保證準確率的情況下，算法計算的運行時間越短，該算法的質(zhì)量也就越高，性能也就越強.由于精化Lanczos算法有收斂檢驗的功能，所以可以自身控制收斂速度，進而影響了計算的時間.針對Lanczos算法和精化Lanczos算法都可以順利地進行大規(guī)模非對稱線性方程組的求解，并得到一定誤差范圍內(nèi)的準確結(jié)果，可以確保此兩種算法為可運行的算法，即可進行計算時間的探究與分析，可以統(tǒng)計出兩種算法計算方程組消耗的時間并整理成對比圖，如圖2所示.

從圖2中結(jié)果來看，對于大規(guī)模非對稱線性方程組的求解算例，兩種Lanczos算法計算得到的參數(shù)估值均值出入不大，而從觀測數(shù)據(jù)上可以看出，精化Lanczos算法的計算時間在每次計算時均小于Lanczos算法30秒的時間.從圖中可以看出隨著數(shù)據(jù)量的增加，利用Lanczos算法計算時所涉及系數(shù)矩陣的協(xié)因數(shù)陣的維度擴大，分解出的向量構(gòu)造也逐漸復雜，而精化Lanczos算法提取了系數(shù)矩陣中重復出現(xiàn)的隨機元素，進行收斂操作和檢驗，此時兩種Lanczos算法的計算時間差會迅速增大，精化的Lanczos算法大大節(jié)省了時間消耗.因此，實驗同樣證明了對大量數(shù)據(jù)進行求解處理時，采用精化Lanczos算法可以明顯地提高計算效率，減少計算時間.

圖2 兩種算法時間消耗對比圖Fig.2 The comparison of time consumption between two algorithms

4 占用內(nèi)存空間對比

在精化Lanczos算法當中引用了隱式壓縮重啟技術(shù)[10]，其操作分為兩個步驟，一個是隱式壓縮，該技術(shù)的特點是選擇若干個位移，對Lanczos過程產(chǎn)生的低階上矩陣進行分解，使得計算量和存儲量大大減少了，從而加快了Lanczos算法的收斂速度.隱式壓縮重啟技術(shù)已廣泛應用于特征值問題，例如隱式重啟Lanczos算法、Lanczos壓縮重啟算法、循環(huán)收縮Lanczos算法、隱式重啟塊Lanczos算法、隱式重啟全局Lanczos算法[10]等.該技術(shù)在全局的應用中首先令k為要求特征值的個數(shù)，i=k+p，考慮i=k+p步全局Lanczos算法過程，有

(7)

其中,e為單位向量，Is為最小奇異值的奇異向量.x為位移，對Wk+p做帶位移的QR分解，有

Wk+p-xI=QR

(8)

其中，Q是正交矩陣，R是三角矩陣.經(jīng)過p步帶位移隱式重啟之后，可以得出結(jié)果：

(9)

5 計算結(jié)果對比

計算結(jié)果分為計算結(jié)果的準確性和殘量值[5].設定CPU表示計算時間單位為秒，Iter表示重啟次數(shù)，m為投影了空間的維數(shù)，允許誤差界tol=10-5，全局算法的殘量范數(shù)取res，初始矩陣或向量均為隨機選取.調(diào)用Matlab R2010a中的eig命令求得矩陣A的4個最大特征值為

?1=7.992 413 314 948 18
?2=7.981 047 676 817 97
?3=7.981 047 676 817 96
?4=7.699 682 038 687 75

用精化Lanczos算法計算初始矩陣的4個最大特征值，使用兩種解題算法進行計算得出計算結(jié)果如表2所示.

表2 兩種算法計算結(jié)果Tab.2 The results of two methods

從計算結(jié)果中可以看出 Lanczos算法得出的結(jié)果為小數(shù)點后兩位，而精化 Lanczos算法特征值為小數(shù)點后五位，與設定的最大特征值對比兩種算法的計算結(jié)果均在準確范圍之內(nèi)，但精化的算法在結(jié)果的體現(xiàn)上更加準確，即精化 Lanczos算法的準確性更高.至于殘量值根據(jù)殘量定理：當精化向量收斂到原矩陣的特征值當中，則精化向量的殘量收斂值為零.利用Ipsen引理可以得出精化向量和特征向量的殘量值.

(10)

圖3 殘量對比結(jié)果圖Fig.3 The figure of residual comparison

6 結(jié)束語

相對非對稱線性方程組求解算法及應用而言，非對稱線性方程組求解初始化策略的研究相對較少，通過提出精化Lanczos算法并與Lanczos算法的各項性能進行對比，可以充分地驗證出精化算法的優(yōu)勢，從理論上說明精化Lanczos方法比Lanczos方法更優(yōu)越，可以在實際問題的解決中得到廣泛應用.