数值计算与算法分析

1、数值计算一般原理数值计算一般原理 数值计算的一般原理介绍数值计算的一般原理介绍张兴元张兴元西南交通大学峨眉校区基础课部西南交通大学峨眉校区基础课部数值计算一般原理数值计算一般原理 目录目录数值计算的一般原理数值计算的一般原理数学问题与数值计算数学问题与数值计算数值问题与算法数值问题与算法数值计算的共同思想与方法数值计算的共同思想与方法数值计算中的精确度分析数值计算中的精确度分析误差来源与分类误差来源与分类误差传播问题误差传播问题病态问题病态问题算法分析与设计实例算法分析与设计实例数值计算一般原理数值计算一般原理 数学问题与数值计算数学问题与数值计算数学问题数学问题：（狭义）：（狭义） 实际应用

2、中所导出的简化了的数学模型。实际应用中所导出的简化了的数学模型。数值计算数值计算： 面向数学问题适合于计算机计算的数值方法，面向数学问题适合于计算机计算的数值方法，是计算数学的重要组成部分。是计算数学的重要组成部分。 数值计算一般原理数值计算一般原理 数值问题与算法数值问题与算法 数值问题数值问题： 输入数据（即数学问题中的自变量与原始数据）与输入数据（即数学问题中的自变量与原始数据）与 输出数据（结果）之间函数关系的一个确定而无歧义的描述。输出数据（结果）之间函数关系的一个确定而无歧义的描述。算法算法：（狭义）：（狭义） 求解数值问题的解法，它按照规定顺序执行一个或多个求解数值问题的解法，它

3、按照规定顺序执行一个或多个完整的进程。完整的进程。 数值计算一般原理数值计算一般原理 算法分类算法分类串行算法串行算法： 只有一个进程，适用于串行计算机；只有一个进程，适用于串行计算机；并行算法并行算法： 两个或两个以上进程的算法，适用于并行计算机。两个或两个以上进程的算法，适用于并行计算机。 数值计算一般原理数值计算一般原理 一个面向计算机，计算复杂性好，又有可靠理论分析的一个面向计算机，计算复杂性好，又有可靠理论分析的算法就是一个好算法。算法就是一个好算法。算法好坏的判断算法好坏的判断计算复杂性计算复杂性：包含：包含时间复杂性时间复杂性和和空间复杂性空间复杂性两个方面，两个方面，在同一精度

4、下，计算时间少的较好，而占用内存空间少的较好。在同一精度下，计算时间少的较好，而占用内存空间少的较好。 数值计算一般原理数值计算一般原理 例例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 ， 用递推公式

5、表示为用递推公式表示为 b0=a0，bk=ak+bk-1x，k=1，2，n，bn=P(x) 数值计算一般原理数值计算一般原理 这两种方法的计算复杂性比较见下表这两种方法的计算复杂性比较见下表 算法算法时间复杂性时间复杂性空间复杂性空间复杂性加法次数加法次数乘法次数乘法次数方法一方法一n2n-12n+1方法二方法二nnn+2方法二比方法一好。方法二比方法一好。数值计算一般原理数值计算一般原理 人类计算能力等于计算工具的性人类计算能力等于计算工具的性能与计算方法效率的乘积。能与计算方法效率的乘积。 观点观点数值计算一般原理数值计算一般原理 数值计算的共同思想与方法数值计算的共同思想与方法v 迭代法

6、迭代法v 以直代曲以直代曲v 化整为零化整为零v 外推法外推法数值计算一般原理数值计算一般原理 迭代法迭代法简单定义，简单定义，按照同一公式重复计算的一个数值过程。按照同一公式重复计算的一个数值过程。常见形式常见形式q 求解方程求解方程 x=G(x)可构造可构造 xk+1=G(xk)结论结论：若在根：若在根x*附近附近|G(x)|1，则序列收敛，则序列收敛， 且且|G(x)|越小收敛越快，越小收敛越快， 在精度要求内迭代次数愈少则收敛越快。在精度要求内迭代次数愈少则收敛越快。 数值计算一般原理数值计算一般原理 q 求解线性方程组求解线性方程组 AX=bX X(k+1)(k+1)=BX=BX(k

7、)(k)+f+f，k=0,1,2,k=0,1,2, 其中其中B=MB=M-1-1NRNRnxnnxn称为迭代矩阵，称为迭代矩阵，f=Mf=M-1-1b b 若B B的范数的范数B1,BX*，X*即为原方程组的解。即为原方程组的解。 数值计算一般原理数值计算一般原理 观点观点 无论在实用上或理论上，处理线性或非线性问题，无论在实用上或理论上，处理线性或非线性问题，迭代法都是最重要的手段之一，但无论哪种问题都必须迭代法都是最重要的手段之一，但无论哪种问题都必须找到合适的方法把方程转化成类似方程找到合适的方法把方程转化成类似方程 X=G(X) X=G(X) 的形式，的形式，并选取某个合适的初始近似。

8、为了减少迭代次数，通常并选取某个合适的初始近似。为了减少迭代次数，通常必须在多种方案中选取收敛较快的方法，因而同一问题必须在多种方案中选取收敛较快的方法，因而同一问题可以产生各种不同的迭代法。可以产生各种不同的迭代法。 数值计算一般原理数值计算一般原理 以直代曲以直代曲 简单定简单定义，一种将非线性问题线性化的思路，义，一种将非线性问题线性化的思路，它是在一个局部范围内用直线代替曲线的方法。它是在一个局部范围内用直线代替曲线的方法。 我们以求方程我们以求方程f(x)=0的根为例说明。参看下图：的根为例说明。参看下图： 数值计算一般原理数值计算一般原理 用一般的用一般的n次多项式次多项式 Pn(

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

10、公式的数值计算公式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+ (3)用

11、用(3)-4x(2)得到得到 T(2h)-I=4T(h)-I+O(h4)忽略忽略O(h4)得到新的数值计算公式：得到新的数值计算公式：IT(h)+T(h)-T(2h)/3 （4）(4)式具有更高的计算精度。式具有更高的计算精度。 badx)x( f 1n0i1ii2h)x( f)x( f 数值计算一般原理数值计算一般原理 数值计算中的精确度分析数值计算中的精确度分析v误差来源与分类误差来源与分类q模型误差模型误差q观测误差观测误差q截断误差（方法误差）截断误差（方法误差）q舍入误差舍入误差v误差传播问题误差传播问题 一一个算法如果输入数据有误差，而计算过程中个算法如果输入数据有误差，而计算过程

12、中舍入误差不增长则称此算法是数值稳定的，否则此舍入误差不增长则称此算法是数值稳定的，否则此算法就称为不稳定的。算法就称为不稳定的。 数值计算一般原理数值计算一般原理 例：对例：对n=0，1，8计算积分计算积分 yn= 。 105xxdxn解：由于解：由于 yn+5yn-1=1/n，可得到计算，可得到计算yn的一些递推公式的一些递推公式8,.,2 , 1ny5n/1y1nn ，)y(ynn1511n 记真实值与近似值的误差为记真实值与近似值的误差为nnnyy 和和nnnyy 相应的误差传播规律为：相应的误差传播规律为：0n1nn)5()5( 和和8 , 2 , 1k,)(8k51k8 相应的计算

13、结果见下表相应的计算结果见下表数值计算一般原理数值计算一般原理 nynynyn00.1823220.1820.18210.0883920.0900.08820.0580390.0500.05830.0431390.0830.04340.034306-0.1650.03450.0284681.0250.02860.024325-4.9580.02570.02123124.9330.02180.018846-124.5400.019数值计算一般原理数值计算一般原理 v建议建议在实际计算中，算法的选用应遵循如下原则：在实际计算中，算法的选用应遵循如下原则：A、要尽量简化计算步骤以减少运算次数、要尽量

14、简化计算步骤以减少运算次数B、要防止大数、要防止大数“吃掉吃掉”小数小数C、尽量避免相近的数相减、尽量避免相近的数相减D、除法运算中应尽量避免除数的绝对值远远小于、除法运算中应尽量避免除数的绝对值远远小于 被除数的绝对值被除数的绝对值E、选用数值稳定性好的公式，以控制舍入误差的传播选用数值稳定性好的公式，以控制舍入误差的传播 数值计算一般原理数值计算一般原理 算法分析与设计实例算法分析与设计实例多多路数组聚集计算示例路数组聚集计算示例三维数组的切块统计计算三维数组的切块统计计算 考虑一个包含维考虑一个包含维A、B、C的的3维数组。该维数组。该3维数组被划分成维数组被划分成小的、基于内存的块。在

15、本例中，数组被划分成小的、基于内存的块。在本例中，数组被划分成64块，如下图块，如下图所示。所示。 数值计算一般原理数值计算一般原理 假定数组的大小对于维假定数组的大小对于维A、B、C分别是分别是40,400,4000，并，并将将A、b、C分成分成4等分等分。 我们的问题我们的问题： 确定其有效的小内存块确定其有效的小内存块扫描次序扫描次序，以计算如下一些，以计算如下一些的统计值：和、平均值、中值、方差等等的统计值：和、平均值、中值、方差等等。 v 2D方块方块AB、AC和和BC 即，整个方体在即，整个方体在AB、AC和和BC上的统计上的统计数值计算一般原理数值计算一般原理 v 1D方块：方块

16、：A、B、C，由，由 1 1）的结果间接计算；）的结果间接计算； v 0D方块方块，ABC的所有数据的统计结果的所有数据的统计结果 存在多种可能的次序存在多种可能的次序，将块读入内存，用于计算，将块读入内存，用于计算2D立立方体。考虑上图从方体。考虑上图从1到到64标记的次序。标记的次序。 下面是计算下面是计算b0c0的示意图。的示意图。数值计算一般原理数值计算一般原理 通过扫描块通过扫描块1到到4可以计算出可以计算出b0c0，此时分配给，此时分配给b0c0的内存的内存可以可以分给下一个块分给下一个块b1c0 ，在完成对，在完成对ABC的的4个块（个块（5到到8）的扫）的扫描后，计算出描后，计

17、算出b1c0。如此继续下去，可以计算整个。如此继续下去，可以计算整个BC方体，方体，因此，对于因此，对于BC中所有块的计算，一次只需一个中所有块的计算，一次只需一个BC块在内存。块在内存。 数值计算一般原理数值计算一般原理 在在BC方体的计算中，我们将扫描方体的计算中，我们将扫描64块中的每一块。块中的每一块。“为计算其它方体，如为计算其它方体，如AB和和AC，有没有办法避免重新扫，有没有办法避免重新扫描所有的块？描所有的块？” 回答是肯定的。回答是肯定的。 这正是多路计算的思路。这正是多路计算的思路。 例如，在扫描块例如，在扫描块1（即（即a0b0c0）时，同时计算与）时，同时计算与a0b0

18、c0有关有关的所有的所有2D方块方块:a:a0 0b b0 0，a a0 0c c0 0，b b0 0c c0 0。 换句话说，当一个换句话说，当一个3D块在内存时，多路计算向每一个块在内存时，多路计算向每一个2D平面的聚集。平面的聚集。 数值计算一般原理数值计算一般原理 下面考虑，下面考虑， 不同的块扫描次序和方体计算次序对整个数据立方体不同的块扫描次序和方体计算次序对整个数据立方体的计算效率的影响。的计算效率的影响。 下表是各平面相关块大下的数据下表是各平面相关块大下的数据 方体方体项目项目ABACBCABC整块大小整块大小16 000160 0001 600 000404004000子块

19、大小子块大小1 00010 000100 000101001000数值计算一般原理数值计算一般原理 下面的讨论，我们都假定扫描次序为下面的讨论，我们都假定扫描次序为1到到64。按照这种次序，按照这种次序， 扫描完块扫描完块4后就是就可以计算出后就是就可以计算出b0c0， 扫描完块扫描完块13 后可以计算出后可以计算出a0c0， 扫描完块扫描完块49 后可以计算出后可以计算出a0b0。也即对方块的计算次序为：也即对方块的计算次序为：BC、AC、AB。此时，在块内存中保持所有相关的此时，在块内存中保持所有相关的2D平面所需最小存储为：平面所需最小存储为：（整个（整个ABAB平面）平面）+ +（ACAC平面的一行）平面的一行）+ +（BCBC平面的一块）平面的一块）4040400+40400+401 000+1001 000+1001 000=156 0001 000=156 000。 数值计算一般原理数值计算一般原理 数值计算一般原理数值计算一般原理 假定块的扫描次序为假定块的扫描次序为1，17，33，49，5，21，37，53，。即是，假定计算