资源描述：
《有效的数值算法课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、几种有效的数值算法报告人：王武中科院超级计算中心Email:wangwu@sccas.cn20010年5月1FastAlgorithmyearmethodreferencestorageflops1947GEVonNeumann,Goldstinen5n71950SORYoungn3n4logn1971CGReidn3n3.5logn1984MGBrandtn3n31987FMMGreengard,Rokhlinn2lognn2lognnnIfn=64,thistableimpliesanoverallreductioninflopsof160million
2、,whichmeetstheMoore’sLaw!(doublingin1.5year)SciDACInitiative,DOE,CSGF,2005n21.快速多极子方法快速多极子方法克服了多粒子模拟中最大的瓶颈：精确计算N个粒子之间通过万有引力或静电力的相互作用（比如星系中的星体，或蛋白质中的分子）需要O(N2)的量级。而FMM达到了O(N)的量级。FMM显著的优点之一是它可以任意调整精度这种算法通过多极展开（空间的粒子或质点、偶极子，四重极子等等）来近似远处的粒子组对近端的局部粒子组的作用一个递归划分的空间用来描述随距离增大的更大的组FastMultip
3、oleMethod(FMM),1987LGreengardVRokhlin,YaleUniversity3静电场和引力场位势的多极子展开矩阵向量乘积形式N体问题4FMM的应用综述1ElectromagneticScatteringStellarClustersProteinFolding567多极子展开Helmholtz型Laplace型Gauss型82.MonteCarlo方法基于随机模拟的计算方法确定性问题。建立概率模型，再进行随机抽样观察，其算术平均即为所求解的近似估计。精度可用估计值的标准误差表示。例如计算积分（多重积分，与维数无关）、计算面积（圆周
4、率）随机性问题。根据物理情况的概率法则，用计算机抽样试验。例如中子在介质中的扩散、随机服务系统中的排队、动物的生态竞争（MCNP是LosAlamos实验室开发的大型蒙特卡罗程序，可计算中子、光子和电子的联合输运问题以及临界问题）Π/4=S(round)/S(square)Π=4N(round)/N(square)N=no.ofrandompointsTheMetropolisAlgorithmforMonteCarloJohnvonNeumann,etal,LosAlamosLab,19469收敛性误差对于独立同分布随机序列，由中心极限定理可知MonteCa
5、rlo方法求积分任何一个积分，都可看作某个随机变量的期望值，因此，可以用这个随机变量的平均值来近似它f(x):概率密度函数正态分布概率误差103.单纯形方法具有约束条件的线性规划问题如何求最优解？单纯形方法的基本思想是：从可行域的某一个极点出发，迭代到另一个极点，并使目标函数的值有所改善，直到找出有无最优解时为止该方法用到了单纯形的概念，单纯形是指N维中的N+1个顶点的凸包，是一个多胞体(比如直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体）单纯形法尽管理论上讲效果是指数衰减的，但在实践中却是高度有效的在线性空间中极大化Z极大化并满足约束Simp
6、lexMethodforLinearProgrammingGeorgeDantzig,RANDCorporation,1947其中114.Krylov子空间迭代法Krylov子空间迭代法是用来求解形如Ax=b的方程组，A是一个NxN的矩阵，当N充分大时，直接计算x=A-1b变得非常困难。Krylov方法则巧妙地将其变为如下迭代形式求解。Kx(i+1)=Kx(i)+b-Ax(i)这里的K是一个构造出来的接近于A的矩阵，而迭代形式的算法的妙处在于，它将复杂问题化简为逐步的易于计算的子步骤。当A是对称矩阵时，Lanczos找到了生成子空间K的正交基的方法。Hest
7、enes和Stiefel提出了共轭梯度法。后来的GMRES、BiCGStab等改进并扩展了这些算法。Krylov子空间:Km=span{r0,Ar0,…,Am-1r0},rm=b-Ax(m)伴随迭代法的是预条件子：构造M，用迭代法求解MAx=MbKrylovSubspaceIterationMethod(KSP),1950Hestenes,Stiefel,Lanczos;NationalBureauofStandards125.QR算法把一个方阵变换为一个“几乎是”上三角的矩阵（在主对角线下面的一斜列上可能有非零元素）是相对容易的，但要想不产生大量的误差就把
8、这些非零元素消去，就不是平凡的事了。QR算法正好能达
