求矩陣特征值特征向量的進化策略算法

1、.：.；- PAGE 7 -求解矩陣特征值及特征向量的進化戰(zhàn)略新方法夏慧明 周永權(quán)廣西民族大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，南寧，530006摘 要：提出了一種基于進化戰(zhàn)略求解矩陣特征值及特征向量的新方法。該方法可用于求解恣意實矩陣的特征值及特征向量。 實驗結(jié)果闡明，這種基于進化戰(zhàn)略求解矩陣特征值及特征向量的方法，相比傳統(tǒng)方法，收斂速度較快，并且求解精度提高了10倍。該算法可以快速有效地獲得恣意矩陣對應(yīng)的特征值及特征向量。關(guān)鍵詞：實矩陣；特征值；特征向量；進化戰(zhàn)略中圖法分類號：TP183A New Evolution Strategy Method for Solving Matrix Eigenva

2、lues and EigenvectorsXia huiming Zhou Yongquan(College of math and computer science, Guangxi University for Nationalities, Nanning 530006)Abstract: In this paper, a new Evolution Strategy method for solving matrix eigenvalues and eigenvectors was proposed. Any real matrixs eigenvalues and eigenvecto

3、rs can be solved by this method. Several experimental results show that the proposed Evolution Strategy method is more efficient and feasible in solving the matrixs eigenvalues and eigenvectors of arbitrary matrix than the tradition method. It was found that the accuracy is ten times higher than the

4、 old method and the speed convergent quickly.Keywords: real matrix; eigenvalues; eigenvectors; evolution strategy1 引 言在科學(xué)和工程計算中，求解矩陣的特征值及特征向量，是最普遍的問題之一。在許多運用領(lǐng)域，經(jīng)常運用矩陣的特征值及特征向量，如主成分分析、因子分析等都必需計算相關(guān)矩陣的特征值和特征向量。 目前，關(guān)于特征值、特征向量問題的數(shù)值解法有兩種：變換法和迭代法。其中，變換法是直接對矩陣進展處置，經(jīng)過變換，使之變成較容易求解特征值、特征向量的新矩陣，但是變換方法經(jīng)常存貯量較大，計算

5、速度較慢；迭代法基金工程：國家自然科學(xué)基金( 60461001);廣西自然科學(xué)基金(0542048);廣西民族大學(xué)艱苦工程資助課題。作者簡介：夏慧明(1981-),男,碩士,主要從事于進化計算及運用方面研討。周永權(quán)(1962- ),男, 博士,教授,主要研討方向為神經(jīng)網(wǎng)絡(luò),計算智能及運用。是經(jīng)過一系列矩陣向量乘積而求得特征值和特征向量，常用的方法有：Lanczos法、Davidson法等。雖然這些方法在求解時都獲得了宏大的勝利，但是普遍存在著計算精度低、收斂速度慢及泛化才干弱等缺陷。進化戰(zhàn)略Evolution Strategies, ES是由I.Rechenberg 和H.P.Schweful

6、為研討風(fēng)洞中的流膂力子問題而提出的。它是一種基于生物界自然選擇和自然遺傳機制的計算方法，利用生物變異的思想來隨機改動參數(shù)值，并獲得了較好的結(jié)果。文中基于進化戰(zhàn)略的特點，提出一種基于進化戰(zhàn)略求解矩陣特征值及特征向量的新方法。該方法可用于求解恣意實矩陣的特征值及特征向量。實驗結(jié)果闡明，這種新的方法，相比傳統(tǒng)方法，具有求解精度高、收斂速度快等特點，可以快速有效地求得恣意矩陣的特征值及特征向量，該方法在科學(xué)與工程計算中有著廣泛的運用。2 特征值與特征向量設(shè) 是一個方陣，是一個維向量，乘積可以看成是維空間內(nèi)的線性變換。假設(shè)能找到一個標量，使得存在一個非零向量，滿足，那么可以以為線性變換將映射為，此時稱是

7、對應(yīng)于特征值的特征向量。通常標量和向量可以是復(fù)數(shù)。為了簡單起見，本文特征值思索在復(fù)數(shù)范圍內(nèi)，特征向量思索在實數(shù)范圍內(nèi)。定義 2。1 假設(shè)是一個實矩陣，那么它存在個特征值，其中為實數(shù)或復(fù)數(shù)。定義 2。2 假設(shè)是的特征值并且非零向量具有如下特性：，那么稱為矩陣對應(yīng)于特征值的特征向量。3 進化戰(zhàn)略算法算法實現(xiàn)過程如下：1) 確定問題的表達方式。表達方式中個體由目的變量和規(guī)范差兩部分組成，每部分又可以有個分量，即：和之間的關(guān)系是：式中：父代個體的第個分量；子代新個體的第個分量；服從規(guī)范正態(tài)分布的隨機數(shù)；針對第個分量重新產(chǎn)生一次符合規(guī)范正態(tài)分布的隨機數(shù)； 全局系數(shù)；部分系數(shù)。上式闡明，新個體是在舊個體根

8、底上隨機變化而來。2) 隨機生成初始群體：進化戰(zhàn)略中初始群體由個個體組成。初始個體是隨機生成的，也可以從某個初始點出發(fā)，經(jīng)過多次突變產(chǎn)生個初始個體，該初始點可從可行域中用隨機方法選取。初始個體的規(guī)范差。3) 進化戰(zhàn)略的突變是在舊個體根底上添加一個隨機量，生成新個體，突變過程為：式中 ,， 是個體中所含分量的數(shù)目。通常，及取為1。4基于進化戰(zhàn)略求矩陣特征值及特征向量的步驟步驟1：求特征值1) 確定矩陣特征值個體的表達方式：表達式中個體由目的變量和規(guī)范差兩部分組成，由于是在復(fù)數(shù)范圍內(nèi)求特征值，所以每個個體有2個分量，分別代表特征值的實部和虛部，即。2) 隨機生成特征值初始群體：初始群體由個個體組成

9、，初始個體是隨機生成的，設(shè)初始個體的規(guī)范差。3) 計算順應(yīng)度：特征值是在滿足將特征值代入特征多項式后，即多項式的值越小時，那么特征值的近似程度越好。取順應(yīng)度函數(shù)為：，順應(yīng)度值越接近1，特征值越優(yōu)良，其中：，終止條件選擇一個很接近1的值，當順應(yīng)度值大于時終止。4) 假設(shè)滿足條件，那么終止，選出最優(yōu)解。否那么，繼續(xù)向下進展。5) 根據(jù)進化戰(zhàn)略，采用5.1)-5.4)產(chǎn)生新群體：5.1) 重組：從父代個體中隨機取出兩個個體，交換目的變量和隨機因子，產(chǎn)生新個體。目的變量與隨機因子均采用黃金分割重組。5.2) 突變：對重組后的個體添加隨機變量，按照式與產(chǎn)生新個體。其中及取為1，。5.3) 計算個體順應(yīng)度

10、。5.4) 選擇：采用選擇戰(zhàn)略，挑選優(yōu)良的個體作為進化的結(jié)果。6) 反復(fù)執(zhí)行第5)步，直到滿足終止條件，選擇最正確的個體作為進化戰(zhàn)略的結(jié)果，即所求的最優(yōu)特征值。步驟2: 求特征向量7) 對步驟1中所求的特征值進展整理，設(shè)誤差限，假設(shè)特征值的虛部的絕對值小于時，那么記該特征值為實數(shù)。從步驟1中找出一切的實特征值，務(wù)虛特征值相應(yīng)的特征向量。8) 隨機生成個初始群體，每一個個體包含個分量為矩陣的階數(shù)。即，其中為特征向量個體。初始個體的規(guī)范差取。9) 計算順應(yīng)度：取順應(yīng)度函數(shù)為，為將特征向量代入線性方程組：，經(jīng)整理可寫成：然后，令，假設(shè)順應(yīng)度值越接近1，那么表示特征向量越優(yōu)，終止條件選擇一個很接近1的

11、值，當順應(yīng)度值大于時終止。10) 假設(shè)滿足條件，那么終止，選出最優(yōu)解。否那么，繼續(xù)向下執(zhí)行。11) 根據(jù)進化戰(zhàn)略，采用11.1)-11.4) 產(chǎn)生新群體：11.1) 重組：從父代個體中隨機取出兩個個體，交換目的變量和隨機因子，產(chǎn)生新個體。目的變量與隨機因子均采用黃金分割重組。11.2)突變：對重組后的個體添加隨機變量，按照式與產(chǎn)生新個體。其中及取為1，。11.3) 計算個體順應(yīng)度。11.4) 選擇：采用選擇戰(zhàn)略，挑選優(yōu)良的個體作為進化的結(jié)果。12) 反復(fù)執(zhí)行第11)步，直到滿足終止條件，選擇最正確的個體作為進化戰(zhàn)略的結(jié)果，即為與實特征值相對應(yīng)的最優(yōu)特征向量。5 仿真實例為了驗證本文算法在求解矩

12、陣特征值與特征向量時的正確性，順應(yīng)度函數(shù)分別取為： = 1 * GB3 求特征值時取，其中； = 2 * GB3 求特征向量時取，其中。根據(jù)上節(jié)算法的思想，當與的值越接近1 時，表示特征值、特征向量與準確解間的誤差越??； = 3 * GB3 以下算例，均采用選擇戰(zhàn)略，其中， ，終止條件均??； = 4 * GB3 準確解由Maple軟件求得。例1 求矩陣的特征值及與實特征值相對應(yīng)的特征向量。由本文算法，可求出矩陣的特征值及與實特征值相對應(yīng)的特征向量，結(jié)果見表1。表1 復(fù)數(shù)域內(nèi)特征值與實特征值相對應(yīng)的特征向量準確解Matlab所求解3同步求解法4本文算法特征值特征向量此例中含有一個二重特征值-2，

13、從表1中可以看出本文算法求解的特征值與Matlab所求解相比最大誤差為10，與文獻4中的同步求解法所得解及準確解間的最大誤差為10，優(yōu)于Matlab法；求特征向量時，與Matlab所求解相比本文最大誤差為10，與文獻4中的同步求解法所求解及準確解間的最大誤差為10。由此例可看出利用本文算法在求解含重特征值時依然是有效的。圖1、2給出了所求特征值及與實特征值相對應(yīng)的特征向量的順應(yīng)度函數(shù)值隨迭代次數(shù)變化的曲線，從圖中可以看出所求近似解的變化趨勢及收斂速度。30200.650.70.750.80.850.90.951510152535404550迭代次數(shù)特征值1特征值2特征值3順應(yīng)度值 10.60.

14、70.90.80.5302520151050.40.10.20.3迭代次數(shù)50404535特征向量1特征向量2特征向量3順應(yīng)度值 圖1 特征值對應(yīng)的順應(yīng)度函數(shù)變化曲線 圖2 特征向量對應(yīng)的順應(yīng)度函數(shù)變化曲線例2 求矩陣的特征值及與實特征值相對應(yīng)的特征向量。利用上節(jié)算法，所求特征值及與實特征值相對應(yīng)的特征向量如表2。表2 復(fù)數(shù)域內(nèi)特征值與實特征值相對應(yīng)的特征向量準確解Languerre迭代分治算法5牛頓迭代分治算法5本文算法特征值特征向量由表2可以看出牛頓迭代法只得到矩陣的兩個實特征值，一對復(fù)特征值被脫漏，Languerre迭代法雖然求出了矩陣的四個特征值，但精度較低，并且與準確解間的誤差大于本

15、文算法與準確解間的誤差；所求的特征向量與準確解間的誤差為10，精度非常高。圖3、4分別為特征值及與實特征值相對應(yīng)的特征向量的順應(yīng)度函數(shù)值隨迭代次數(shù)變化的曲線，從圖中可以看出所求解的精度高，收斂速度快。0.21特征值1特征值2特征值30.40.310300.8特征值40.10.90.70.60.5515202535404550迭代次數(shù)迭代次數(shù)順應(yīng)度值特征值1特征值2特征值3特征值4 特征向量2迭代次數(shù)特征向量1504535403025200.10.20.30.40.50.70.60.80.9115105順應(yīng)度值 圖3 特征值對應(yīng)的順應(yīng)度函數(shù)變化曲線 圖4 特征向量對應(yīng)的順應(yīng)度函數(shù)變化曲線6 結(jié)

16、論 文中給出的進化戰(zhàn)略算法可用于求恣意實矩陣的特征值、特征向量，由算例可以看出該算法所求得的解，精度高、收斂速度快。對于含虛特征值的情形，由于Newton迭代法不收斂，故求不出矩陣的虛特征值，而本文算法能將階矩陣在復(fù)數(shù)域內(nèi)的一切特征值求出，求解精度高于Languerre迭代法及其它一些算法；對于含重特征值的情形，該算法也是行之有效的。參考文獻1 Back T, Schwefel H P. Evolution Strategies I: Variants and Their Computational Implementation. In: Genetic Algorithms in Engineering and Computer ScienceM, Winter G(ed), Wiley, 1995, 111-126.2 Schwefel H P, Back T. Evolution Strategies = 2 * ROMAN II: Theoretical Aspects. In: Genetic Algorithms in Engineering and Computer Science M, Winter G