幾种有效的数值算法.pptVIP

几种有效的数值算法 报告人：王 武 中科院超级计算中心 Email: wangwu@sccas.cn 20010年5月 Fast Algorithm year method reference storage flops 1947 GE Von Neumann, Goldstine n5 n7 1950 SOR Young n3 n4logn 1971 CG Reid n3 n3.5logn 1984 MG Brandt n3 n3 1987 FMM Greengard, Rokhlin n2logn n2logn n n If n=64, this table implies an overall reduction in flops of 160 million, which meets the Moore’s Law! (doubling in 1.5 year) SciDAC Initiative, DOE, CSGF, 2005 n 1. 快速多极子方法 快速多极子方法克服了多粒子模拟中最大的瓶颈：精确计算N个粒子之间通过万有引力或静电力的相互作用（比如星系中的星体，或蛋白质中的分子）需要O(N2)的量级。而FMM达到了O(N)的量级。FMM显著的优点之一是它可以任意调整精度 这种算法通过多极展开（空间的粒子或质点、偶极子，四重极子等等）来近似远处的粒子组对近端的局部粒子组的作用 一个递归划分的空间用来描述随距离增大的更大的组 Fast Multipole Method (FMM) , 1987 L Greengard V Rokhlin, Yale University 静电场和引力场 位势的多极子展开 矩阵向量乘积形式 N 体问题 FMM的应用综述1 Electromagnetic Scattering Stellar Clusters Protein Folding FMM的应用综述2 RBF Interpolation Vortex Particle Method for Turbulence Acoustic Pressure aroung the Wing FM-BEM for Composite Materials 涡粒子方法 Navier-Stokes方程 Gauss型基函数 多极子展开 Helmholtz 型 Laplace 型 Gauss 型 2. Monte Carlo方法 基于随机模拟的计算方法 确定性问题。建立概率模型，再进行随机抽样观察，其算术平均即为所求解的近似估计。精度可用估计值的标准误差表示。 例如计算积分（多重积分，与维数无关）、计算面积（圆周率） 随机性问题。根据物理情况的概率法则，用计算机抽样试验。 例如中子在介质中的扩散、随机服务系统中的排队、动物的生态竞争（MCNP是Los Alamos实验室开发的大型蒙特卡罗程序，可计算中子、光子和电子的联合输运问题以及临界问题） Π/4=S(round)/S(square) Π=4N(round)/N(square) N= no. of random points The Metropolis Algorithm for Monte Carlo John von Neumann, et al, Los Alamos Lab, 1946 收敛性 误差 对于独立同分布随机序列，由中心极限定理可知 Monte Carlo方法求积分 任何一个积分，都可看作某个随机变量的期望值， 因此，可以用这个随机变量的平均值来近似它 f(x): 概率密度函数 正态分布概率误差 3. 单纯形方法 具有约束条件的线性规划问题如何求最优解？ 单纯形方法的基本思想是：从可行域的某一个极点出发，迭代到另一个极点，并使目标函数的值有所改善，直到找出有无最优解时为止 该方法用到了单纯形的概念，单纯形是指N维中的N + 1个顶点的凸包，是一个多胞体(比如直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体） 单纯形法尽管理论上讲效果是指数衰减的，但在实践中却是高度有效的 在线性空间中极大化Z ??????? 极大化 并满足约束 Simplex Method for Linear Programming George Dantzig, RAND Corporation, 1947 其中 4. Krylov子空间迭代法 Krylov子空间迭代法是用来求解形如Ax=b 的方程组，A是一个NxN 的矩阵，当N充分大时，直接计算x=A-1b变得非常困难。 Krylov方法则巧妙地将其变为如下迭代形式求解。 Kx(i