《数值计算与算法分析.ppt》由会员分享，可在线阅读，更多相关《数值计算与算法分析.ppt（32页珍藏版）》请在三一办公上搜索。
1、数值计算的一般原理介绍,张兴元,西南交通大学峨眉校区基础课部,目录,数值计算的一般原理数学问题与数值计算数值问题与算法数值计算的共同思想与方法数值计算中的精确度分析误差来源与分类误差传播问题病态问题算法分析与设计实例,数学问题与数值计算,数学问题：（狭义）实际应用中所导出的简化了的数学模型。数值计算：面向数学问题适合于计算机计算的数值方法，是计算数学的重要组成部分。,数值问题与算法,数值问题：输入数据（即数学问题中的自变量与原始数据）与 输出数据（结果）之间函数关系的一个确定而无歧义的描述。算法：（狭义）求解数值问题的解法，它按照规定顺序执行一个或多个完整的进程。,算法分类,串行算法：只有一个
2、进程，适用于串行计算机；,并行算法：两个或两个以上进程的算法，适用于并行计算机。,一个面向计算机，计算复杂性好，又有可靠理论分析的算法就是一个好算法。,算法好坏的判断,计算复杂性：包含时间复杂性和空间复杂性两个方面，在同一精度下，计算时间少的较好，而占用内存空间少的较好。,例1：计算多项式 P(x)=a0 xn+a1xn-1+an-1x+an 的值。,这是一个数值问题，输入数据：a0，a1，an-1，an及x，输出数据为P(x)。,方法一：（1）、计算出x2，x3，xn；（2）、计算出 akxn-k；（3）、求和。,方法二：将P(x)改写为 P(x)=(a0 x+a1)x+an-1)x+an，
3、用递推公式表示为 b0=a0，bk=ak+bk-1x，k=1，2，n，bn=P(x),这两种方法的计算复杂性比较见下表,方法二比方法一好。,人类计算能力等于计算工具的性能与计算方法效率的乘积。,观点,数值计算的共同思想与方法,迭代法 以直代曲 化整为零 外推法,迭代法,简单定义，按照同一公式重复计算的一个数值过程。,常见形式,求解方程 x=G(x),可构造 xk+1=G(xk),结论：若在根x*附近|G(x)|1，则序列收敛，且|G(x)|越小收敛越快，在精度要求内迭代次数愈少则收敛越快。,求解线性方程组 AX=b,X(k+1)=BX(k)+f，k=0,1,2,其中B=M-1NRnxn称为迭代
4、矩阵，f=M-1b,若B的范数BX*，X*即为原方程组的解。,观点,无论在实用上或理论上，处理线性或非线性问题，迭代法都是最重要的手段之一，但无论哪种问题都必须找到合适的方法把方程转化成类似方程 X=G(X)的形式，并选取某个合适的初始近似。为了减少迭代次数，通常必须在多种方案中选取收敛较快的方法，因而同一问题可以产生各种不同的迭代法。,以直代曲,简单定义，一种将非线性问题线性化的思路，它是在一个局部范围内用直线代替曲线的方法。,我们以求方程f(x)=0的根为例说明。参看下图：,用一般的n次多项式 Pn(x)=a0+a1x+anx 逼近函数f(x)。其中包括泰勒展开、内插法和其他数值逼近方法。
5、在此基础上，方程求根、定积分计算、常微分方程数值求解等都能导出各种不同的数值算法。,推广,化整为零,将整个问题分割为若干个小问题处理。,典型例子是数值积分的复化求积公式和常微分方程数值解公式。,外推法,对于依赖步长h的数值计算公式T(h)，可用新的步长h代替h（一般情况是h=2h，h=3h，）得到新的数值计算公式T(h)，然后根据T(h)和T(h)得到新的精度更高的数值计算公式。,例如，计算定积分I=的梯形公式为 IT(h)=(1)当h0时，T(h)=I+O(h2)=I+c1h2+c2h4+(2)其中c1，c2不依赖于h，若用步长h=2h计算，则T(2h)=I+c1(2h)2+c2(2h)4+
6、(3)用(3)-4x(2)得到 T(2h)-I=4T(h)-I+O(h4)忽略O(h4)得到新的数值计算公式：IT(h)+T(h)-T(2h)/3（4）(4)式具有更高的计算精度。,数值计算中的精确度分析,误差来源与分类模型误差观测误差截断误差（方法误差）舍入误差误差传播问题,一个算法如果输入数据有误差，而计算过程中舍入误差不增长则称此算法是数值稳定的，否则此算法就称为不稳定的。,例：对n=0，1，8计算积分 yn=。,解：由于 yn+5yn-1=1/n，可得到计算yn的一些递推公式,记真实值与近似值的误差为,和,相应的误差传播规律为：,和,相应的计算结果见下表,建议,在实际计算中，算法的选用
7、应遵循如下原则：A、要尽量简化计算步骤以减少运算次数B、要防止大数“吃掉”小数C、尽量避免相近的数相减D、除法运算中应尽量避免除数的绝对值远远小于 被除数的绝对值E、选用数值稳定性好的公式，以控制舍入误差的传播,算法分析与设计实例,多路数组聚集计算示例三维数组的切块统计计算,考虑一个包含维A、B、C的3维数组。该3维数组被划分成小的、基于内存的块。在本例中，数组被划分成64块，如下图所示。,假定数组的大小对于维A、B、C分别是40,400,4000，并将A、b、C分成4等分。,我们的问题：确定其有效的小内存块扫描次序，以计算如下一些的统计值：和、平均值、中值、方差等等。,2D方块AB、AC和B
8、C,即，整个方体在AB、AC和BC上的统计,1D方块：A、B、C，由 1）的结果间接计算；0D方块，ABC的所有数据的统计结果,存在多种可能的次序，将块读入内存，用于计算2D立方体。考虑上图从1到64标记的次序。,下面是计算b0c0的示意图。,通过扫描块1到4可以计算出b0c0，此时分配给b0c0的内存可以分给下一个块b1c0，在完成对ABC的4个块（5到8）的扫描后，计算出b1c0。如此继续下去，可以计算整个BC方体，因此，对于BC中所有块的计算，一次只需一个BC块在内存。,在BC方体的计算中，我们将扫描64块中的每一块。“为计算其它方体，如AB和AC，有没有办法避免重新扫描所有的块？”,回
9、答是肯定的。这正是多路计算的思路。,例如，在扫描块1（即a0b0c0）时，同时计算与a0b0c0有关的所有2D方块:a0b0，a0c0，b0c0。,换句话说，当一个3D块在内存时，多路计算向每一个2D平面的聚集。,下面考虑，不同的块扫描次序和方体计算次序对整个数据立方体的计算效率的影响。,下表是各平面相关块大下的数据,下面的讨论，我们都假定扫描次序为1到64。,按照这种次序，扫描完块4后就是就可以计算出b0c0，扫描完块13 后可以计算出a0c0，扫描完块49 后可以计算出a0b0。,也即对方块的计算次序为：BC、AC、AB。,此时，在块内存中保持所有相关的2D平面所需最小存储为：（整个AB平
10、面）+（AC平面的一行）+（BC平面的一块）40400+401 000+1001 000=156 000。,假定块的扫描次序为1，17，33，49，5，21，37，53，。即是，假定计算扫描次序是 首先向AB平面，然后向AC平面，最后向BC平面聚集。保持二维平面在块内存的最小内存需求量为：（整个BC平面）+（AC平面的一行）+（AB平面的一块）4004 000+401 000+10100=1 641 000,类似地，我们可以算出1D和0D方体多路计算的最小内存需求量。,基于数据立方体计算的最小内存需求，下图给出了最有效的次序和效率最差的次序。最有效的块次序是1到64。,参考文献：【1】数值计算原理，李庆扬、关治等 清华大学出版社【2】数值方法（MATLAB版），John H.Mathews，电子工业出版社【3】计算方法引论（第三版），徐萃薇 孙绳武，高等教育出版社【4】数值分析，钟尔杰 黄廷祝，高等教育出版社【5】计算方法，李信真，西北工业大学出版社【6】数学手册，高等教育出版社,
