数值计算与算法分析.ppt

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(

3、x)=(a0 x+a1)x+an-1)x+an ， 用递推公式表示为 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

4、)+f，k=0,1,2,其中B=M-1NRnxn称为迭代矩阵，f=M-1b,若B的范数BX*，X*即为原方程组的解。,观点,无论在实用上或理论上，处理线性或非线性问题， 迭代法都是最重要的手段之一，但无论哪种问题都必须 找到合适的方法把方程转化成类似方程 X=G(X) 的形式， 并选取某个合适的初始近似。为了减少迭代次数，通常 必须在多种方案中选取收敛较快的方法，因而同一问题 可以产生各种不同的迭代法。,以直代曲,简单定义，一种将非线性问题线性化的思路， 它是在一个局部范围内用直线代替曲线的方法。,我们以求方程f(x)=0的根为例说明。参看下图：,用一般的n次多项式 Pn(x)=a0+a1x+

5、anx 逼近函数f(x)。 其中包括泰勒展开、内插法和其他数值逼近方法。在此基础 上，方程求根、定积分计算、常微分方程数值求解等都能导 出各种不同的数值算法。,推广,化整为零,将整个问题分割为若干个小问题处理。,典型例子是数值积分的复化求积公式和常微分方程 数值解公式。,外推法,对于依赖步长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)

6、其中c1，c2不依赖于h，若用步长h=2h计算，则 T(2h)=I+c1(2h)2+c2(2h)4+ (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，可得到计算y

7、n的一些递推公式,记真实值与近似值的误差为,和,相应的误差传播规律为：,和,相应的计算结果见下表,建议,在实际计算中，算法的选用应遵循如下原则： A、要尽量简化计算步骤以减少运算次数 B、要防止大数“吃掉”小数 C、尽量避免相近的数相减 D、除法运算中应尽量避免除数的绝对值远远小于 被除数的绝对值 E、选用数值稳定性好的公式，以控制舍入误差的传播,算法分析与设计实例,多路数组聚集计算示例三维数组的切块统计计算,考虑一个包含维A、B、C的3维数组。该3维数组被划分成 小的、基于内存的块。在本例中，数组被划分成64块，如下图 所示。,假定数组的大小对于维A、B、C分别是40,400,4000，并将

8、A、b、C分成4等分。,我们的问题： 确定其有效的小内存块扫描次序，以计算如下一些 的统计值：和、平均值、中值、方差等等。,2D方块AB、AC和BC,即，整个方体在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中所

9、有块的计算，一次只需一个BC块在内存。,在BC方体的计算中，我们将扫描64块中的每一块。 “为计算其它方体，如AB和AC，有没有办法避免重新扫 描所有的块？”,回答是肯定的。 这正是多路计算的思路。,例如，在扫描块1（即a0b0c0）时，同时计算与a0b0c0有关 的所有2D方块:a0b0，a0c0，b0c0。,换句话说，当一个3D块在内存时，多路计算向每一个 2D平面的聚集。,下面考虑， 不同的块扫描次序和方体计算次序对整个数据立方体 的计算效率的影响。,下表是各平面相关块大下的数据,下面的讨论，我们都假定扫描次序为1到64。,按照这种次序， 扫描完块4后就是就可以计算出b0c0， 扫描完块

10、13 后可以计算出a0c0， 扫描完块49 后可以计算出a0b0。,也即对方块的计算次序为：BC、AC、AB。,此时，在块内存中保持所有相关的2D平面所需最小存储为： （整个AB平面）+（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。,参考文献：