数值计算与算法分析

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