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

求解矩阵特征值及特征向量的进化策略新方法夏慧明 周永权（广西民族大学数学与计算机科学学院，南宁，530006）摘 要：提出了一种基于进化策略求解矩阵特征值及特征向量的新方法。该方法可用于求解任意实矩阵的特征值及特征向量。 实验结果表明，这种基于进化策略求解矩阵特征值及特征向量的方法，相比传统方法，收敛速度较快，并且求解精度提高了10倍。该算法能够快速有效地获得任意矩阵对应的特征值及特征向量。关键词：实矩阵；特征值；特征向量；进化策略中图法分类号：TP183A New Evolution Strategy Method for Solving Matrix Eigenvalues 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 eigenvectors 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 old method and the speed convergent quickly.Keywords: real matrix; eigenvalues; eigenvectors; evolution strategy1 引 言在科学和工程计算中，求解矩阵的特征值及特征向量，是最普遍的问题之一。在许多应用领域，经常使用矩阵的特征值及特征向量，如主成分分析、因子分析等都必须计算相关矩阵的特征值和特征向量。 目前，关于特征值、特征向量问题的数值解法有两种：变换法和迭代法。其中，变换法是直接对矩阵进行处理，通过变换，使之变成较容易求解特征值、特征向量的新矩阵，但是变换方法常常存贮量较大，计算速度较慢；迭代法基金项目：国家自然科学基金( 60461001);广西自然科学基金(0542048);广西民族大学重大项目资助课题。作者简介：夏慧明(1981-),男,硕士,主要从事于进化计算及应用方面研究。周永权(1962- ),男, 博士,教授,主要研究方向为神经网络,计算智能及应用。是通过一系列矩阵向量乘积而求得特征值和特征向量，常用的方法有：Lanczos法、Davidson法等。虽然这些方法在求解时都取得了巨大的成功，但是普遍存在着计算精度低、收敛速度慢及泛化能力弱等缺陷。进化策略（Evolution Strategies, ES）是由I.Rechenberg 和H.P.Schweful为研究风洞中的流体力子问题而提出的。它是一种基于生物界自然选择和自然遗传机制的计算方法，利用生物变异的思想来随机改变参数值，并获得了较好的结果。文中基于进化策略的特点，提出一种基于进化策略求解矩阵特征值及特征向量的新方法。该方法可用于求解任意实矩阵的特征值及特征向量。实验结果表明，这种新的方法，相比传统方法，具有求解精度高、收敛速度快等特点，能够快速有效地求得任意矩阵的特征值及特征向量，该方法在科学与工程计算中有着广泛的应用。2 特征值与特征向量设 是一个方阵，是一个维向量，乘积可以看成是维空间内的线性变换。若能找到一个标量，使得存在一个非零向量，满足，则可以认为线性变换将映射为，此时称是对应于特征值的特征向量。通常标量和向量可以是复数。为了简单起见，本文特征值考虑在复数范围内，特征向量考虑在实数范围内。定义 2。1 如果是一个实矩阵，则它存在个特征值，其中为实数或复数。定义 2。2 如果是的特征值并且非零向量具有如下特性：，则称为矩阵对应于特征值的特征向量。3 进化策略算法算法实现过程如下：1) 确定问题的表达方式。表达方式中个体由目标变量和标准差两部分组成，每部分又可以有个分量，即：和之间的关系是：式中：父代个体的第个分量；子代新个体的第个分量；服从标准正态分布的随机数；针对第个分量重新产生一次符合标准正态分布的随机数； 全局系数；局部系数。上式表明，新个体是在旧个体基础上随机变化而来。2) 随机生成初始群体：进化策略中初始群体由个个体组成。初始个体是随机生成的，也可以从某个初始点出发，通过多次突变产生个初始个体，该初始点可从可行域中用随机方法选取。初始个体的标准差。3) 进化策略的突变是在旧个体基础上添加一个随机量，生成新个体，突变过程为：式中 ,， 是个体中所含分量的数目。通常，及取为1。4基于进化策略求矩阵特征值及特征向量的步骤步骤1：求特征值1) 确定矩阵特征值个体的表达方式：表达式中个体由目标变量和标准差两部分组成，因为是在复数范围内求特征值，所以每个个体有2个分量，分别代表特征值的实部和虚部，即。2) 随机生成特征值初始群体：初始群体由个个体组成，初始个体是随机生成的，设初始个体的标准差。3) 计算适应度：特征值是在满足将特征值代入特征多项式后，即多项式的值越小时，则特征值的近似程度越好。取适应度函数为：，适应度值越接近1，特征值越优良，其中：，终止条件选择一个很接近1的值，当适应度值大于时终止。4) 若满足条件，则终止，选出最优解。否则，继续向下进行。5) 根据进化策略，采用5.1)-5.4)产生新群体：5.1) 重组：从父代个体中随机取出两个个体，交换目标变量和随机因子，产生新个体。目标变量与随机因子均采用黄金分割重组。5.2) 突变：对重组后的个体添加随机变量，按照式与产生新个体。其中及取为1，。5.3) 计算个体适应度。5.4) 选择：采用选择策略，挑选优良的个体作为进化的结果。6) 反复执行第5)步，直到满足终止条件，选择最佳的个体作为进化策略的结果，即所求的最优特征值。步骤2: 求特征向量7) 对步骤1中所求的特征值进行整理，设误差限，若特征值的虚部的绝对值小于时，则记该特征值为实数。从步骤1中找出所有的实特征值，求实特征值相应的特征向量。8) 随机生成个初始群体，每一个个体包含个分量（为矩阵的阶数）。即，其中为特征向量个体。初始个体的标准差取。9) 计算适应度：取适应度函数为，为将特征向量代入线性方程组：，经整理可写成：然后，令，若适应度值越接近1，则表示特征向量越优，终止条件选择一个很接近1的值，当适应度值大于时终止。10) 若满足条件，则终止，选出最优解。否则，继续向下执行。11) 根据进化策略，采用11.1)-11.4) 产生新群体：11.1) 重组：从父代个体中随机取出两个个体，交换目标变量和随机因子，产生新个体。目标变量与随机因子均采用黄金分割重组。11.2)突变：对重组后的个体添加随机变量，按照式与产生新个体。其中及取为1，。11.3) 计算个体适应度。11.4) 选择：采用选择策略，挑选优良的个体作为进化的结果。12) 反复执行第11)步，直到满足终止条件，选择最佳的个体作为进化策略的结果，即为与实特征值相对应的最优特征向量。5 仿真实例为了验证本文算法在求解矩阵特征值与特征向量时的正确性，适应度函数分别取为：求特征值时取，其中；求特征向量时取，其中。根据上节算法的思想，当与的值越接近1 时，表示特征值、特征向量与精确解间的误差越小；以下算例，均采用选择策略，其中， ，终止条件均取；精确解由Maple软件求得。例1 求矩阵的特征值及与实特征值相对应的特征向量。由本文算法，可求出矩阵的特征值及与实特征值相对应的特征向量，结果见表1。表1 复数域内特征值与实特征值相对应的特征向量精确解Matlab所求解3同步求解法4本文算法特征值特征向量此例中含有一个二重特征值-2，从表1中可以看出本文算法求解的特征值与Matlab所求解相比最大误差为10，与文献4中的同步求解法所得解及精确解间的最大误差为10，优于Matlab法；求特征向量时，与Matlab所求解相比本文最大误差为10，与文献4中的同步求解法所求解及精确解间的最大误差为10。由此例可看出利用本文算法在求解含重特征值时仍然是有效的。图1、2给出了所求特征值及与实特征值相对应的特征向量的适应度函数值随迭代次数变化的曲线，从图中可以看出所求近似解的变化趋势及收敛速度。30200.650.70.750.80.850.90.951510152535404550迭代次数特征值1特征值2特征值3适应度值 10.60.70.90.80.5302520151050.40.10.20.3迭代次数50404535特征向量1特征向量2特征向量3适应度值 图1 特征值对应的适应度函数变化曲线 图2 特征向量对应的适应度函数变化曲线例2 求矩阵的特征值及与实特征值相对应的特征向量。利用上节算法，所求特征值及与实特征值相对应的特征向量如表2。表2 复数域内特征值与实特征值相对应的特征向量精确解Languerre迭代分治算法5牛顿迭代分治算法5本文算法特征值特征向量由表2可以看出牛顿迭代法只得到矩阵的两个实特征值，一对复特征值被遗漏，Languerre迭代法虽然求出了矩阵的四个特征值，但精度较低，并且与精确解间的误差大于本文算法与精确解间的误差；所求的特征向量与精确解间的误差为10，精度非常高。图3、4分别为特征值及与实特征值相对应的特征向量的适应度函数值随迭代次数变化的曲线，从图中可以看出所求解的精度高，收敛速度快。0.21特征值1特征值2特征值30.40.310300.8特征值40.10.90.70.60.5515202535404550迭代次数迭代次数适应度值特征值1特征值2特征值3特征值4 特征向量2迭代次数特征向量1504535403025200.10.20.30.40.50.70.60.80.9115105适应度值 图3 特征值对应的适应度函数变化曲线 图4 特征向量对应的适应度函数变化曲线6 结 论 文中给出的进化策略算法可用于求任意实矩阵的特征值、特征向量，由算例可以看出该算法所求得的解，精度高、收敛速度快。对于含虚特征值的情形，由于Newton迭代法不收敛，故求不出矩阵的虚特征值，而本文算法能将阶矩阵在复数域内的所有特征值求出，求解精度高于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 II: Theoretical Aspects. In: Genetic Algorithms in Engineering and Computer Science M, Winter G(ed), Wiley, 1995, 127-140.3 John H. Mathews, Kurtis D.Fink. Numerical Methods Using MATLAB (Fourth Edition)M. Beijing: Publishing House of Electronics Industry, 2005.4 杨廷俊.矩阵特征值与特征向量的同步求解J.甘肃联合大学学报，2006，20(3).5 罗晓广，李晓梅.解非对称矩阵特征值问题的一种并行分治算法J.高等学校计算数学学报，1999 (第二期).- 7 -