数值计算与算法分析

《数值计算与算法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数值计算的一般原理介绍张兴元西南交通大学峨眉校区基础课部目录数值计算的一般原理数学问题与数值计算数值问题与算法数值计算的共同思想与方法数值计算中的精确度分析误差来源与分类误差传播问题病态问题算法分析与设计实例数学问题与数值计算数学问题：（狭义）实际应用中所导出的简化了的数学模型。数值计算：面向数学问题适合于计算机计算的数值方法，是计算数学的重要组成部分。数值问题与算法数值问题：输入数据（即数学问题中的自变量与原始数据）与输出数据（结果）之间函数关系的一个确定而无歧义的描述。算法：（狭义）求解数值问题的解法，它按照规定顺序执行一个或多个完整的进程。

2、算法分类串行算法：只有一个进程，适用于串行计算机；并行算法：两个或两个以上进程的算法，适用于并行计算机。一个面向计算机，计算复杂性好，又有可靠理论分析的算法就是一个好算法。算法好坏的判断计算复杂性：包含时间复杂性和空间复杂性两个方面，在同一精度下，计算时间少的较好，而占用内存空间少的较好。例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

3、)改写为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*附近

4、G’(x)

5、<1，则序列收敛，且

6、

7、G’(x)

8、越小收敛越快，在精度要求内迭代次数愈少则收敛越快。求解线性方程组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)的形式，并选取某个合适的初始近似。为了减少迭代次数，通常必须在多种方案中选取收敛较快的方法，因而

9、同一问题可以产生各种不同的迭代法。以直代曲简单定义，一种将非线性问题线性化的思路，它是在一个局部范围内用直线代替曲线的方法。我们以求方程f(x)=0的根为例说明。参看下图：用一般的n次多项式Pn(x)=a0+a1x+…+anx逼近函数f(x)。其中包括泰勒展开、内插法和其他数值逼近方法。在此基础上，方程求根、定积分计算、常微分方程数值求解等都能导出各种不同的数值算法。推广化整为零将整个问题分割为若干个小问题处理。典型例子是数值积分的复化求积公式和常微分方程数值解公式。外推法对于依赖步长h的数值计算公式T(h)，可用新的步长h’代替h（一般情况是h

10、’=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)式具有更高的计算精度。数值计算中的精确度分

11、析误差来源与分类模型误差观测误差截断误差（方法误差）舍入误差误差传播问题一个算法如果输入数据有误差，而计算过程中舍入误差不增长则称此算法是数值稳定的，否则此算法就称为不稳定的。例：对n=0，1，…，8计算积分yn=。解：由于yn+5yn-1=1/n，可得到计算yn的一些递推公式记真实值与近似值的误差为和相应的误差传播规律为：和相应的计算结果见下表nyn00.1823220.1820.18210.0883920.0900.08820.0580390.0500.05830.0431390.0830.04340.034306-0.1650.03450.

12、0284681.0250.02860.024325-4.9580.02570.02123124.9330.02180.018846-12