求矩陣特征值特征向量的進(jìn)化策略算法

1、.：.；- PAGE 7 -求解矩陣特征值及特征向量的進(jìn)化戰(zhàn)略新方法夏慧明 周永權(quán)廣西民族大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，南寧，530006摘 要：提出了一種基于進(jìn)化戰(zhàn)略求解矩陣特征值及特征向量的新方法。該方法可用于求解恣意實(shí)矩陣的特征值及特征向量。 實(shí)驗(yàn)結(jié)果闡明，這種基于進(jìn)化戰(zhàn)略求解矩陣特征值及特征向量的方法，相比傳統(tǒng)方法，收斂速度較快，并且求解精度提高了10倍。該算法可以快速有效地獲得恣意矩陣對應(yīng)的特征值及特征向量。關(guān)鍵詞：實(shí)矩陣；特征值；特征向量；進(jì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é)和工程計(jì)算中，求解矩陣的特征值及特征向量，是最普遍的問題之一。在許多運(yùn)用領(lǐng)域，經(jīng)常運(yùn)用矩陣的特征值及特征向量，如主成分分析、因子分析等都必需計(jì)算相關(guān)矩陣的特征值和特征向量。 目前，關(guān)于特征值、特征向量問題的數(shù)值解法有兩種：變換法和迭代法。其中，變換法是直接對矩陣進(jìn)展處置，經(jīng)過變換，使之變成較容易求解特征值、特征向量的新矩陣，但是變換方法經(jīng)常存貯量較大，計(jì)算

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

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

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

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

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

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

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

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

13、從表1中可以看出本文算法求解的特征值與Matlab所求解相比最大誤差為10，與文獻(xiàn)4中的同步求解法所得解及準(zhǔn)確解間的最大誤差為10，優(yōu)于Matlab法；求特征向量時(shí)，與Matlab所求解相比本文最大誤差為10，與文獻(xiàn)4中的同步求解法所求解及準(zhǔn)確解間的最大誤差為10。由此例可看出利用本文算法在求解含重特征值時(shí)依然是有效的。圖1、2給出了所求特征值及與實(shí)特征值相對應(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 求矩陣的特征值及與實(shí)特征值相對應(yīng)的特征向量。利用上節(jié)算法，所求特征值及與實(shí)特征值相對應(yīng)的特征向量如表2。表2 復(fù)數(shù)域內(nèi)特征值與實(shí)特征值相對應(yīng)的特征向量準(zhǔn)確解Languerre迭代分治算法5牛頓迭代分治算法5本文算法特征值特征向量由表2可以看出牛頓迭代法只得到矩陣的兩個(gè)實(shí)特征值，一對復(fù)特征值被脫漏，Languerre迭代法雖然求出了矩陣的四個(gè)特征值，但精度較低，并且與準(zhǔn)確解間的誤差大于本

15、文算法與準(zhǔn)確解間的誤差；所求的特征向量與準(zhǔn)確解間的誤差為10，精度非常高。圖3、4分別為特征值及與實(shí)特征值相對應(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、論 文中給出的進(jìn)化戰(zhàn)略算法可用于求恣意實(shí)矩陣的特征值、特征向量，由算例可以看出該算法所求得的解，精度高、收斂速度快。對于含虛特征值的情形，由于Newton迭代法不收斂，故求不出矩陣的虛特征值，而本文算法能將階矩陣在復(fù)數(shù)域內(nèi)的一切特征值求出，求解精度高于Languerre迭代法及其它一些算法；對于含重特征值的情形，該算法也是行之有效的。參考文獻(xiàn)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