求矩阵特征值特征向量的进化策略算法

-1-求解矩阵特征值及特征向量的进化策略新方法夏慧明周永权（广西民族大学数学与计算机科学学院，南宁，530006）摘要：提出了一种基于进化策略求解矩阵特征值及特征向量的新方法。该方法可用于求解任意实矩阵的特征值及特征向量。实验结果表明，这种基于进化策略求解矩阵特征值及特征向量的方法，相比传统方法，收敛速度较快，并且求解精度提高了10倍。该算法能够快速有效地获得任意矩阵对应的特征值及特征向量。关键词：实矩阵；特征值；特征向量；进化策略中图法分类号：TP183ANewEvolutionStrategyMethodforSolvingMatrixEigenvaluesandEigenvectorsXiahuimingZhouYongquan(Collegeofmathandcomputerscience,GuangxiUniversityforNationalities,Nanning530006)Abstract:Inthispaper,anewEvolutionStrategymethodforsolvingmatrixeigenvaluesandeigenvectorswasproposed.Anyrealmatrix’seigenvaluesandeigenvectorscanbesolvedbythismethod.SeveralexperimentalresultsshowthattheproposedEvolutionStrategymethodismoreefficientandfeasibleinsolvingthematrix’seigenvaluesandeigenvectorsofarbitrarymatrixthanthetraditionmethod.Itwasfoundthattheaccuracyistentimeshigherthantheoldmethodandthespeedconvergentquickly.Keywords:realmatrix;eigenvalues;eigenvectors;evolutionstrategy1引言在科学和工程计算中，求解矩阵的特征值及特征向量，是最普遍的问题之一。在许多应用领域，经常使用矩阵的特征值及特征向量，如主成分分析、因子分析等都必须计算相关矩阵的特征值和特征向量。目前，关于特征值、特征向量问题的数值解法有两种：变换法和迭代法。其中，变换法是直接对矩阵进行处理，通过变换，使之变成较容易求解特征值、特征向量的新矩阵，但是变换方法常常存贮量较大，计算速度较慢；迭代法基金项目：国家自然科学基金(60461001);广西自然科学基金(0542048);广西民族大学重大项目资助课题。作者简介：夏慧明(1981-),男,硕士,主要从事于进化计算及应用方面研究。周永权(1962-),男,博士,教授,主要研究方向为神经网络,计算智能及应用。-2-是通过一系列矩阵向量乘积而求得特征值和特征向量，常用的方法有：Lanczos法、Davidson法等。虽然这些方法在求解时都取得了巨大的成功，但是普遍存在着计算精度低、收敛速度慢及泛化能力弱等缺陷。进化策略（EvolutionStrategies,ES）]21[是由I.Rechenberg和H.P.Schweful为研究风洞中的流体力子问题而提出的。它是一种基于生物界自然选择和自然遗传机制的计算方法，利用生物变异的思想来随机改变参数值，并获得了较好的结果。文中基于进化策略的特点，提出一种基于进化策略求解矩阵特征值及特征向量的新方法。该方法可用于求解任意实矩阵A的特征值及特征向量。实验结果表明，这种新的方法，相比传统方法，具有求解精度高、收敛速度快等特点，能够快速有效地求得任意矩阵的特征值及特征向量，该方法在科学与工程计算中有着广泛的应用。2特征值与特征向量]3[设A是一个nn方阵，X是一个n维向量，乘积AXY可以看成是n维空间内的线性变换。若能找到一个标量，使得存在一个非零向量X，满足XAX，则可以认为线性变换AXXT)(将X映射为X，此时称X是对应于特征值的特征向量X。通常标量和向量X可以是复数。为了简单起见，本文特征值考虑在复数范围内，特征向量考虑在实数范围内。定义2。1如果A是一个nn实矩阵，则它存在n个特征值n,,,21，其中),,2,1(nii为实数或复数。定义2。2如果是A的特征值并且非零向量V具有如下特性：VAV，则V称为矩阵A对应于特征值的特征向量。3进化策略算法算法实现过程如下：1)确定问题的表达方式。表达方式中个体由目标变量X和标准差两部分组成，每部分又可以有n个分量，即：)),,,,,(),,,,,,((),(2121ninixxxxXX和之间的关系是：)1,0())1,0()1,0(exp('''iiiiiiiNxxNrNr式中：),(iix——父代个体的第i个分量；),(''iix——子代新个体的第i个分量；)1,0(N——服从标准正态分布的随机数；)1,0(iN——针对第i个分量重新产生一次符合标准正态分布的随机数；'r——全局系数；r——局部系数。上式表明，新个体是在旧-3-个体基础上随机变化而来。2)随机生成初始群体：进化策略中初始群体由个个体组成。初始个体是随机生成的，也可以从某个初始点))0(),0((X出发，通过多次突变产生个初始个体，该初始点可从可行域中用随机方法选取。初始个体的标准差0.3)0(。3)进化策略的突变是在旧个体基础上添加一个随机量，生成新个体，突变过程为：)1,0())1,0()1,0(exp('''iiiiiiiNxxNrNr式中1)2(nr,1')2(nr，n是个体中所含分量的数目。通常，r及'r取为1。4基于进化策略求矩阵特征值及特征向量的步骤步骤1：求特征值1)确定矩阵特征值个体的表达方式：表达式中个体由目标变量X和标准差两部分组成，因为是在复数范围内求特征值，所以每个个体有2个分量，分别代表特征值的实部和虚部，即)),(),,((),(2121xxX。2)随机生成特征值初始群体：初始群体由个个体组成，初始个体是随机生成的，设初始个体的标准差0.3)0(。3)计算适应度：特征值是在满足将特征值代入特征多项式后，即多项式)det(AIe的值越小时，则特征值的近似程度越好。取适应度函数为：)1/(12ef，适应度值越接近1，特征值越优良，其中：10f，终止条件选择一个很接近1的值，当适应度值大于时终止。4)若满足条件，则终止，选出最优解。否则，继续向下进行。5)根据进化策略，采用5.1)-5.4)产生新群体：5.1)重组：从父代个体中随机取出两个个体，交换目标变量和随机因子，产生新个体。目标变量与随机因子均采用黄金分割重组。5.2)突变：对重组后的个体添加随机变量，按照式))1,0()1,0(exp(''iiiNrNr与)1,0('iiiiNxx产生新个体。其中r及'r取为1，2,1i。5.3)计算个体适应度f。5.4)选择：采用),(选择策略，挑选优良的个体作为进化的结果。-4-6)反复执行第5)步，直到满足终止条件，选择最佳的个体作为进化策略的结果，即所求的最优特征值。步骤2:求特征向量7)对步骤1中所求的特征值进行整理，设误差限0000000001.0，若特征值的虚部的绝对值小于时，则记该特征值为实数。从步骤1中找出所有的实特征值，求实特征值相应的特征向量。8)随机生成个初始群体，每一个个体),(X包含n个分量（n为矩阵A的阶数）。即)),,,,,(),,,,,,((),(2121ninixxxxX，其中),,,,,(21nixxxx为特征向量个体。初始个体的标准差取0.3)0(。9)计算适应度：取适应度函数为)1/(1dg，d为将特征向量X代入线性方程组：XAX，经整理可写成：0)(0)(0)(21XfXfXfn然后，令niiXfd12)(，若适应度值越接近1，则表示特征向量越优，10g，终止条件选择一个很接近1的值，当适应度值大于时终止。10)若满足条件，则终止，选出最优解。否则，继续向下执行。11)根据进化策略，采用11.1)-11.4)产生新群体：11.1)重组：从父代个体中随机取出两个个体，交换目标变量和随机因子，产生新个体。目标变量与随机因子均采用黄金分割重组。11.2)突变：对重组后的个体添加随机变量，按照式))1,0()1,0(exp(''iiiNrNr与)1,0('iiiiNxx产生新个体。其中r及'r取为1，ni,...,2,1。11.3)计算个体适应度g。11.4)选择：采用),(选择策略，挑选优良的个体作为进化的结果。12)反复执行第11)步，直到满足终止条件，选择最佳的个体作为进化策略的结果，即为与实特征值相对应的最优特征向量。5仿真实例-5-为了验证本文算法在求解矩阵特征值与特征向量时的正确性，适应度函数分别取为：①求特征值时取)1/(12ef，其中)det(AIe；②求特征向量时取)1/(1dg，其中niiXfd12)(。根据上节算法的思想，当f与g的值越接近1时，表示特征值、特征向量与精确解间的误差越小；③以下算例，均采用),(选择策略，其中20，1407，终止条件均取9999999999.0；④精确解由Maple软件求得。例1求矩阵266157113A的特征值及与实特征值相对应的特征向量。由本文算法，可求出矩阵的特征值及与实特征值相对应的特征向量，结果见表1。表1复数域内特征值与实特征值相对应的特征向量精确解Matlab所求解[3]同步求解法[4]本文算法特征值400000000000000.44i00000000000000.000000000000000.4256910000000528.22i0000140.000000000000822.00000000-2430919999999471.12i0000140.00000000-9999181.99999999-特征向量1101101100000011.000000008533480.999999991258250.000000000112856910.000000050000001.000000000000001.000000000117036480.000000050168251.000000000000001.000000000112856910.00000005-0000001.000000000000001.000000000110157550.00000006-0000001.000000000341411.00000000此例中含有一个二重特征值-2，从表1中可以看出本文算法求解的特征值与Matlab所求解相比最大误差为108，与文献[4]中的同步求解法所得解及精确解间的最大误差为1013，优于Matlab法；求特征向量时，与Matlab所求解相比本文最大误差为109，与文献[4]中的同步求解法所求解及精确解间的最大误差为108。由此例可看出利用本文算法在求解含重特征值时仍然是有效的。图1、2给出了所求特征值及与实特征值相对应的特征向量的适应度函数值随迭代次数变化的曲线，从图中可以看出所求近似解的变化趋势及收敛速度。-6-图1特征值对应的适应度函数变化曲线图2特征向量对应的适应度函数