二十世纪十大算法

二十世纪十大算法摘要:二十世纪十大算法。下面的内容是对“二十世纪十大算法”的罗列和简要的描述，这些算法是由《计算机科学与工程》（简称CISE）杂志的编辑选出来的，这是他们2000年一月至二月刊的主要话题。这十大算法是20世纪在科学与工程的发展和实践方面最有影响力的算法，并且应该是20世纪数值数学和计算科学发展的一个摘要。对于这样的一种选择，我们可以持赞同或者反对的态度，但至少不应该低估它们，因为它们是发达国家具备很高素质的计算机科学家们的观点。编辑们向该杂志的读者们征询他们对于这个选择的看法和感受。在随后的几期CISE中得到的反馈结果是，关于这个选择只有赞成而没有分歧。因此可以得出结论，CISE作出的选择很好并且得到了国际科学界的认可。整数关系探测法（简称IRD）多年来，研究人员都梦想着能有这样一种设备，这种设备可以让他们识别满足数学公式的数值常量。随着高效的IRD算法的出现，这一时代到来了。令为x=（X,X，…,X）一个实数或者复数向量。如果存在不为零的整数a，x就拥12ni有这样一个整数关系，使得ax+ax+...+ax=0。一个整1122nn数关系算法是一种实用的计算方案，它可以恢复整数向量（若存在），或者可以i产生不存在整数关系的范围。这些都是计算数论的行为。对IRD而言，最有效的算法是Ferguson最近发现的PSLQ算法。作为一个例子，下面是PSLQ1997发现的一个公式，使我们能够计算兀的第n位16进制数。兀="1k=016k42兀="1k=016k8k+18k+48k+58k+6」另一个例子是定义一个常数B3=3.54409035955...，它是数理逻辑图x=rx1—x）里的第三个分叉点，这表现出了在混沌出现之前周期缩短了一倍：为了保证精确，B3是参数r的最小取值，这样逐次迭代工,就具有8个周期而不是4个周期。可以类似地来定义常数B2和B］。使用了PsLq前身算法的计算发现B3是如下方程的根t12—12111+48110—4019—19318+39217+4416+815—97714—60413+210812+4913=0使用了IRD后，研究人员在数学和物理方面有了许多新的发现，而这些发现又相应的产生了有价值的新见解。这个过程常常被称为“实验数学”，即利用现代计算机发现新的数学原理，我们期望它在21世纪的纯数学和应用数学里扮演一个更为广泛的角色。线性规划的单纯形法GeorgeDantzig创立了一种单纯形算法来解决大型企业在计划和决策方面的线性规划问题。这个算法的成功带来了其一系列的专业化和推广，这个算法半个世纪以来主导着实际研究活动。在这种单纯形法的许多形式中，LP的问题是其中之一：Minimize(w.r.t.x)CTx约束条件Ax=b在实际应用中，矩阵A和向量b是分开的，使LP问题写为：Minimize(w.r.t.x)CTxsubjecttoA1x<blA2x=b2A3x>b3xN0松弛和多余变量的使用可以使问题从一种形式转换成另一种形式。在使用单纯形法时存在的一些问题如下：•我们如何得到一个初始的可行解，或者说，更重要的是，我们如何能得知是否有可行的解决方案？•如果约束条件不能使目标值减小会怎样？也就是说，如果这种方案不受约束会怎么样？•如果几个顶点得到相同的目标值会怎样？现代有关于线性规划问题的教科书都是用单纯形法，这种方法摒弃了早起作品中的表格和术语。Krylov子空间迭代法许多问题导致了运用于大型系统的方程中出现成千上万甚至是成百上千万的未知数：电子电路仿真、磁场计算、天气预报、化工工艺、半导体器件仿真、核反应堆安全分析、机械结构应力等系统。当我们遇到一个用线性方程Ax=b、nxn阶矩阵A和N维向量b以及N维未知向量x描述的大型系统时，我们就会想到一种诸如逐次超松弛迭代法/SOR的迭代算法。另一种帮助解决类似问题的迭代方法是交替方向迭代法，这种方法试图通过依次求解每个坐标方向上的一维问题，在二维或三维网络上来解决离散偏微分方程。一个迭代过程开始之前，我们首先要尝试找到一个解决问题的很好的猜想，例如通过解决一个更简单的相近（理想化的）问题来找到这种猜想。为了达到这个目的，假设我们通过一个更简单的矩阵K来逼近Ax=b系统里的A矩阵。那么迭代过程可以归结为：在第i+1步中，为了最终可以解出Ax=b中的x，从Kx=Kx+b-Ax解出新的近似值X。在二十世纪五十年代，Lanczosi+1iii+1提出了一种想法，保留所有迭代过程中的近似计算直到将它们重组为一个更好的解决方法。Lanczos认为在良好的结构化子空间中的基本迭代能近似得到x。这些子空间是由r,Ar,A2r,...,Ai-1r生成的，其中r=b-Ax。这样的子空000000间是一个含有A和r的i维Krylov子空间。利用Krylov子空间迭代方法，科学家们又发现了如共轭梯度法、广义最小残差算法以及双共轭梯度法，这些方法在解决当N大于1000000时Ax=b系统的问题和解一个元素大多数都为零的稀疏矩阵A时都很有用。QR算法假设我们都默认这样一种观点，矩阵特征值的快速计算能力是现代科学家和工程师们的一个重要工具。QR算法是一种非常令人满意的方法，但是QR算法的成功并不意味着它是这个问题的最后方案。矩阵理论和特征值问题随着矩阵力学和量子理论的到来而变得越发的重要，并且在流体力学、核反应分析、地球物理及其他学科中有着进一步的发展。QR算法的基本思想是，任何NxN阶实矩阵A都可以被分解成a=A：QR1，Q是正交矩阵oQ=Q-1，R上三角矩阵。下一步是找出A=RQ=Q-1AQ，然后分解为A=QR等。它表明，该序列44211111222A,A，…收敛到一个上三角形式的矩阵A，A的特征值按照对角线向下单调递12减。QR分解法的一个重要性质是它保留了矩阵的以下特征：对称性、对三角形式以及Hessenberg形式。由于这一性质，对于一般的矩阵要求其特征值可以借助Householder方法转化为Hessenberg形式，。一旦一个矩阵化成了Hessenberg形式，QR变换就可以运用迭代将其汇聚成一种形式，这种形式的矩阵或者是由特征值独立构成对角线，或者构成一个对角线是特征值的2x2阶的子矩阵。有两种不同的算法用于计算QR分解：Gram-Schmidt算法和正交三角化。快速排序法排序是计算机科学中研究最多的一个问题，因为它已经用于很多实际应用，并且它还具有重要的内在理论。基本的排序问题是以升序或者降序的方式重新排列给定的项目集合。尽管研究人员已经开发和分析出了许多种排列算法，快速排序算法还是脱颖而出了。TonyHoare早在1962年就提出了最初的算法，目前快速排序法仍然是最著名的实用排序算法。矩阵计算的分解法矩阵的分解方法无论陈新有很多，新的方法一直在不断的涌现出来。然而，只有六种分解法因其使用性和稳定性而占据着主导地位。下面对这六种分解法分别进行简要的描述。1、Cholesky分解法。给定一个正定矩阵A，存在一个特殊的上三角矩阵R，它的对角线元素均为正，使得A=RtR。这种形式的分解就称为Cholesky分解。它通常写成这样的形式A=LDLT，其中D是对角阵，L是对角线为1的下三角矩阵。Cholesky分解法主要用于求解正定线性系统。2、LU分解法。令A为一个NxN阶的矩阵。存在矩阵P、Q使得PtAQ=LU，其中L是单位下三角矩阵，U是上三角矩阵。矩阵P、Q并不是唯一的，选择它们的过程称为旋转运算。LU分解法主要用于求解线性系统Ax=b，其中A是一般矩阵。高斯消元法对Cholesky分解法和LU分解法的计算有一定的帮助。3、QR分解法。详见上面的第四节内容。4、谱分解法。令A为一个NxN阶的对称矩阵。存在一个正交矩阵V使得A=VAVt，其中y=diag（X，…,人）。如果v.表示V的第i列，那么，1N1Av=Xv。因此，（Xv）是A的一组特征值和特征向量，A的谱分解表示Aiiiii的特征值总是伴随着完整的特征向量正交系统的。5、Schur分解法。令A为一个NxN阶的矩阵。存在一个矩阵U使得A=UTUh，其中T是一个上三角矩阵，uH是U的共轭转置矩阵。T的对角线元素是A的特征值，通过对U的适当选择，可以使A的特征值出现各种不同的顺序。这种分解法称为对A的Schur分解。一个实矩阵会有复杂的特征值，因此会有复杂的Schur形式。通过让T在对角线上有2x2阶的实块，包含复杂的特征值，整个分解就成为了实分解。这种分解法又是也称为实Schur形式。在对Hessenberg形式做了初步的缩减之后，Schur形式用于QR算法的计算。6、奇异值分解法/SVD。令A为一个MxN阶矩阵，其中M>N。存在正交矩阵U和V使得ntAV（o），其中O=diak，…,b）b>b>...>b>0。UTAv=1N12N这种方法称为对A的SVD法\°如果U是由U的前n列构成的，可以写为a=UOVt，有时候称之为A的奇异值分解。Z的对角线元素b称为A的奇异值。U和V相应的列称为A的左右奇异向量。有三种算法来计算谱分解和SVD：QR算法，分治算法和Jacobi’s算法。快速傅里叶变换法近几年来，数字技术以一个几乎难以置信的速度在发展。似乎每个人都意识到了数据在互联网上疾驰，繁忙的穿梭于我们的调制解调器之间，或者是涌入我们的手机中，这些数据终究只是一些由0和1组成的数字序列，如今这些数据神奇地将我们的世界变成了一个便捷、高速的社会。这些神奇的变化很大程度上要归功于算法家族，它们统称为快速傅里叶变换/FFT。FFT也许是当今用于分析处理数字或者离散数据最普遍的算法了。Metropolis算法Metropolis算法是曾经被称为“蒙特卡洛方法”的众多算法中最成功也是最有影响力的一种算法。在传统的概念里，蒙特卡洛方法使用的是采样法，这种采样法是由冯诺依曼提出的，称为拒绝法。Metropolis等人在1953年提出了另一种采样法，这种方法应该比拒绝法更高效。FortranI编译器FortranI编译器是第一个例证，它证明了将高级语言自动生成高效的机器代码是有可能的。因此，它有着巨大的影响力。良好的技术应用于FortranI编译器，可以解决解析表达、循环优化以及寄存器分配问题。快速多极算法涉及到计算大量粒子间的相互作用的问题渗透在科学和工程的许多分支中。当粒子在静电场/库仑或者重力场/牛顿电势中相互作用时，所产生的长距离的力在计算方面让人感到头疼。这是因为在这样的系统中，力是由电极（或者质量）产生的。在仿真中，由于电极数随着粒子数N呈二次方增长，如果没有一个经过精心设计的计算策略O（N2）,仿真计算就会相当复杂。这很快就让对所谓的N体问题的仿真研究实际上并不可能实现，因为系统规模的增加已经到了相关现实问题的水平。这就是快速多极算法大显身手的时候了。结束语1、上述的所有十种算法里，有四种涉及到了矩阵的特性及应用，即线性规划的单纯形算法、Krylov子空间迭代法、QR算法和矩阵计算的分解法。这一事实表明，矩阵在上个世纪的科学和工程领域中扮演着非常重要的角色。这一角色解决的问题有，线性系统方程杰=b以及北=Xx中的特征值问题，这在未来可能会变得越来越重要，尤其是迎合了解决线性方程或者特征值问题的需求，这些问题涉及到N是百万级别的“畸形”矩阵。矩阵理论的重要性也可以从这一事实中看出来，即有一个专门致力于研究它科技期刊：SIAM矩阵分析及应用杂志。2、用于解决科学和工程领域中问题的数学模型大都包括线性常微分方程、偏微分方程和积分方程或积分微分方程。当我们用有限差分或者有限元法来解决这些问题时，它们会被转化为含有矩阵的线性方程系统。3、数学过去常常被高度理论化，完全依靠演绎推理，现在数学变得更具有“实验性”，正如整数关系探测法中所说的一样。因此，数学中的演绎推理如今已被大多数数学家完全接受。4、解决约束优化问题的方法，比如用于解决线性问题的Dantzig单纯形法，因以下事实变得越来越重要了。为了在一个全球自由竞争不断变化的世界中生存下来，生产者要求生产及经营过程要以最高的效率和生产率来执行，当然不能牺牲产品的质量。5、许多科学问题都具有多面性，因此对这些系统进行确定的仿真并不容易。这时候蒙特卡洛仿真可以补救这一缺点，比如用于多维集成。具有随机性的仿真系统确实需要蒙特卡洛仿真。在所有的这些应用中，为了提高仿真效率需要用Metropolis方法，而不会牺牲结论的有效性。6、分子动力学和分子力学仿真，如今在计算物理、计算化学、计算