数值计算期末复习资料讲解

1、 引言例： 利用秦九韶算法求多项式p(x)=x5-3x4+4x2-x+1,在x=3 时的值。（课本11页习题3）解：p(x)=(x-3)x4+4x2-x+1=(x-3)x2+4)x2-x+1=(x-3)x2+4)x-1)x+1=(0*x2+4)x-1)x+1=(4x-1)x+1=(4*3-1)*3+1=34练习. x=3, f=2x5 5x4 4 x3 + 3x2 6 x + 7n 解：f=(2x-5)x4 4 x3 + 3x2 6 x + 7=(2x-5)x 4 ) x3 + 3x2 6 x + 7=(2x-5)x 4 ) x + 3)x2 6 x + 7= (2x-5)x 4 ) x +

2、3)x 6) x +7=(2*3-5)*3 4 )* 3 + 3)*3 6) *3 +7=-11练习：用二分法求方程ex+10x-2=0在0,1内的近似根，要求误差不超过1/2*10-2.(课本11页，习题1）kakbkxkf(ak)* f(xk) 0010.5000010.50000.2500020.25000.1250040.06250.0937060.07810.0859070.08590.0898误差的来源：误差限和有效数字：n 误差限： 设以x代表x*的近似值，则 绝对误差为：|x-x*|，若有|x-x*|则称为近似值x的绝对误差限，简称误差限，或称精度。n 有效数字：对于x*的近似

3、值（规格化形式） x=0.a1a2an10m(其中a1，a2，an是0-9之间的自然数）如果误差|x-x*|1/210m-l,1 l n则称近似值x有l位有效数字，或称x准确到第l位。n 凡是由准确值经过四舍五入而得到的近似值，其绝对误差限等于该近似值末位的半个单位。n 1、用四舍五入法取准确值的前n位作为近似值，则x*必有n位有效数字n 2、有效数字相同的两个近似数，绝对误差限不一定相同。例如，设x1*=12345及x2*=0.12345均有五位有效数字，而它们的绝对误差限分别为0.5和0.000005n 3、准确值被认为具有无穷位有效数字相对误差与有效数字的联系：设x,y分别是数x*,y*

4、的近似值，考察x-y的相对误差相对误差与有效数字：n 由此可见：两个值相近的近似数相减，可能会造成有效数字的严重损失。n 在实际计算时，需要加工计算公式，以避免这种情况发生。n 8、已知e=2.71828,试问其近似值x1=2.7,x2=2.71,x3=2.718各有几位有效数字？并给出它们的相对误差限。n 解：x1=0.27101,x2=0.271101, x3=0.2718101n |x1-e|=0.01828 1/2101-2,有效数字2位，n |x2-e|/=0.008281/2101-2有效数字2位，n |x3-e|=0.000281/2101-4,有效数字4位算法设计中，避免误差危

5、害的要点：n 避免除数绝对值远小于被除数绝对值的除法，否则可能会扩大舍入误差。n 避免两相近数相减，否则会使有效数字严重损失。n 尽可能防止大数“吃掉”小数，否则可能影响计算结果的可靠性。n 简化计算步骤，将少运算次数。n 选用数值稳定的算法 第一章 差值方法例1：解：带入x0=100, 得用p1(x)计算：n 误差估计：n 用p2(x)计算：练习：课本54页1，求作f(x)=sin x在节点x0=0的5次泰勒多项式，并估计插值误差。2、拉格朗日插值n 求作n次多项式pn(x),使满足条件 pn(xi)=yi , i=0,1, , n这就是所谓拉格朗日插值点xi（互不相同），称为插值节点。1.

6、2 拉格朗日插值公式1、线性插值n 问题3：求作一次式p1(x),使满足条件 p1(x0)=y0 , p1(x1)=y1几何意义：y=p1(x)表示通过两点（x0,y0),(x1,y1)的直线，因此，一次插值又称线性插值n 它的解p1(x)可表为点斜式：解：已知x0=100,y0=10,x1=121,y1=11,x=115, 带入线性插值公式，得插值基函数：n 线性插值公式亦可表为对称式：注意：这里的l0(x)和l1(x)分别可以看做是满足条件：称为问题3的插值基函数练习：习题6（1），构造拉格朗日插值多项式p(x),逼近f(x)=x3,要求取节点x0=-1,x1=1n 解：y0=-1,y1=

7、12、抛物插值n 问题4：求作二次式p2(x),使满足条件 p2(x0)=y0 , p2(x1)=y1， p2(x2)=y2几何意义：y=p1(x)表示通过三点（x0,y0),(x1,y1) ,(x2,y2)的抛物线， 因此，二次插值又称抛物插值。p2(x)的解？问题4的解：设取已知数据y0,y1,y2作为组合系数，将插值基函数l0(x),l1(x),l2(x)组合，即可得到问题4的解（即抛物插值的解）：例3：利用100，121，144的开方值求解：用抛物插值 已知：x0=100,y0=10 , x1=121,y1=11, x2=144,y2=12 , x=115代入抛物插值公式得：问题2的解

8、（拉格朗日插值）用前面的插值基函数，可得到问题2的解：n 即拉格朗日插值公式练习：习题6（1），构造拉格朗日插值多项式p(x),逼近f(x)=x3,要求取节点x0=-1,x1=0,x2=1,x3=2作三次插值。1.3 插值余项拉格朗日余项定理：n 插值余项：R(x)=f(x)-pn(x) 也称截断误差。n 定理3（拉格朗日余项定理）：设区间a,b,含有节点x0,x1,xn, 而f(x)在a,b内有连续的直到n+1阶导数，且f(xi)=yi(i=0,1,n)已给，则当xa,b时，对于由式（10）给出的Pn(x),成立式中是与x有关的点，它包含在由点x0,x1,xn和x所界定的范围内，因而a,b罗

9、尔定理：若函数f(x)满足下列条件：1、 在闭区间a,b内连续；2、在开区间（a,b）内可导；3、f(a)=f(b)则至少存在一点（a,b),使得f()=0例：设f(x)=ln(x),给出函数表,试估计ln0.60的值x0.400.500.700.80lnx-0.916291-0.693147-0.356675-0.223144解：取x0=0.40,x1=0.50,x3=0.70,x4=0.80,算出插值基函数值：l0(0.60)=-1/6,l1(0.60=2/3,l2(0.60)=2/3,l3(0.60)=-1/6在区间（0.40，0.80）上，104/40961/4104/256。所以-1

10、/256R(0.60)-1/4096事后误差估计法：n 考察3个节点x0,x1,x2,对于给定的插值点x:n 先用x0与x1,x2进行线性插值，求出y=f(x)的一个近似值y1；同样取x0与 x2,求出y2。n 按余项定理得：n 将上面两个式子相除1.5牛顿差值公式2、差商定义及性质1.差商定义 称 为 在 两点处的一阶差商. 为二阶差商. 为n阶差商. 补充定义：f(xi)为零阶差商 特点：具有鲜明的承袭性差商的性质 (1) k阶差商 是函数值 的线性组合. 注:由性质看到,差商关于定义它的结点是对称的,即k阶差商 可以随意改变结点次序,而差商值不变.(2) 若f(x) 在a,b内存在n阶导

11、数,且结点 则n阶差商与导数关系 (3)若 是一个m次代数多项式,则其中 am 为 f(x) 的首项系数.例:已知 1 2 3 4 0 -5 -6 3求满足以上插值条件的牛顿型插值多项式。解:一阶差商二阶差商三阶差商 1 2 3 4 0 -5 -6 3 -5 -1 9 2 5 1由上述差商表对角线上取得的值则牛顿三次插值多项式为 练习：已知函数y=f(x)的数据如下表i0123Xi0123yi=f(xi)13927试用Newton插值公式作一个三次多项式p3(x)，利用p3(x)计算解：利用Newton插值公式：4 差分与等距结点插值一、差分定义及性质1.差分定义向前差分算子 向后差分算子中心

12、差分算子1. Newton向前插值公式条件: 结点 要计算 x0 附近点x 的函数值.令 x=x0+th 向前插值公式: 插值余项:2. Newton向后插值公式条件: 要计算Xn 附近点X 的函数值.插值结点按 排序.令x=xn+th 向后插值公式:插值余项:例 已知函数 y-f(x) 的数值表： 0 1 2 3 1 2 17 64试作出f(x) 三次Newton向前向后插值公式,并 计算 f(0.5) ,f(2.5) 的近似值。解：由 X0=0,Xn=3,h=1 令构造差分表如下：xi fi fi 2fi 3fi 0 1 2 3 1 2 17 64 11547143218由上表得：牛顿三次

13、向前、向后插值公式分别为得：练习：给定数据表如下x0.20.40.60.81.01.2f(x)212523202124用三次插值多项式计算f(0.7)的近似值用二次插值多项式计算f(0.95)的近似值解：由于节点等距，故可用牛顿向前、向后插值公式进行计算，先构造差分表xiyiyi2yi3yi4yi5yi0.2214-650-70.425-2-15-70.623-34-20.820121.02131.224选x1=0.4,x2=0.6,x3=0.8,x4=1.0作为节点，构造三次向前牛顿插值多项式由0.4+0.2t=0.7解得t=1.5,代入上式得：f(0.7) N3(0.7)=21.3125

14、1.7 分段插值法1、为什么要引入分段插值法？答：（1）并非插值多项式的次数越高，逼近效果越好。有些函数随着插值多项式次数的增大以及逼近区间的增大，使得在逼近区间发生振荡现象。从而使得逼近效果不理想（龙格Runge现象）。（2）插值误差除来自截断误差外，还来自初始数据的误差和计算过程中的舍入误差。插值次数越高，计算工作量越大，积累误差也可能越大。（3）因此，在实际操作过程中，常常用分段低次插值进行计算，即把整个插值区间分成若干个小区间，在每个小区间上进行低次插值。xi012345yi10.50.20.10.058820.03846练习：对下列数据作分段线性插值，并计算f(1.2),f(3.3)

15、xi-3-1239yi1251612四、分段三次插值xi012yi10.50.2分段插值的优缺点1、优点：显示算法，方法简单，收敛性好，只要节 点距离充分小，分段插值总能达到所要的精度要 求，而不会象高次插值那样发生龙格现象。另一个 重要特点就是局部性质。如果修改某个数据，那么 插值曲线仅仅在某个局部范围受到影响，而代数插值却会影响到整个插值区间。2、缺点：分段线性插值与分段三次埃尔米特插值（问 题8）虽然改善了精度，但是这种插值要求给出各个节点上的导数值，所要提供的信息太多，同时它的光滑性也不高（只有连续的一阶导数）。改进这 种插值以克服其缺点，这就是下一节介绍的三次样条插值方法（问 第二章

16、 数值积分数值求积方法：对平均高度f()提供一种数值算法若f()近似的用积分区间端点处的函数值f(a)和f(b)的算术平均值代替，便可导出计算积分的梯形公式：若f()近似的用积分区间中点(a+b)/2处的函数值代替，便可导出计算积分的中矩形公式：若f()近似的用a,b,(a+b)/2三点高度的加权平均值1/6f(a)+4f(c)+f(b) ,c=(a+b)/2代替，便可导出计算积分的辛普森公式：一般地，欲使该求积公式具有m次代数精度，只要令它对于f(x)=1,x,x2,xm都准确成立即可 梯形公式：所以，梯形公式具有一次代数精度中矩形公式：所以，中矩形公式具有一次代数精度辛普森公式：所以，辛普

17、森公式具有三次代数精度解线性方程组（P80题2 ） 计算积分（P81题4 ） 2.2 牛顿柯特斯公式1.公式的导出将区间a,b划分为n等分，步长h=(b-a)/n,取等分点xk=a+kh,(k=0,1,n),构造出插值型求积公式:称作牛顿柯特斯公式，Ck称柯特斯系数。求Ck:解：计算结果见下表，表中最末一列指明有效数字的位数m（I的准确值为0.9460831）nInm10.9270354120.9461359330.9461109340.9460830650.946083064 龙贝格求积公式可见，利用两种步长计算的结果能估计截断误差.若将该截断误差加到计算结果中，例：计算已知对于e = 10

18、-6 须将区间对分 9 次，得到 T512 = 3.14159202由 来计算 I 效果是否好些？ 来计算 I 效果是否好些？= 3.141592502= S4改进梯形求积公式的右边实际是这就是说用梯形法二分前后的两个积分值Tn与T2n的线性组合的结果得到复化辛普森法求积公式一般有： 第三章 常微分方程的差分方法CH 3.1 欧拉方法一、欧拉格式讨论下列节点列上X1X2 .Xn的近似解：y1,y2,.,yn,.规定：相邻两个节点的间距 h=Xn+1-Xn 称为步长，在以后如不特别声明，步长就为定值h。并用 y(xn) 的近似值 yn 代入上式的右端，记所得结果为 yn+1 ，于是有yn+1=y

19、n+hf(xn,yn),n=0,1,2,3.这就是欧拉公式(Euler)xnyny(xn)xnyny(xn)0.11.10001.09540.61.50901.48320.21.19181.18320.71.58031.54920.31.27741.26490.81.64981.61250.41.35821.34160.91.71781.67330.51.43511.41421.01.78481.73213、局部截断误差和精度在 的前提下估计 的误差称为局部截断误差。如果一种数值方法的局部截断误差为 ，则称这种方法的精度为 n 阶。即有欧拉格式的精度是p 阶。事实上，有因此，欧拉格式具有一阶精

20、度。 三、两步欧拉格式（二阶精度）用中心差商 替代方程中的导数项 ，有（两步欧拉格式）计算当前步的值需要用到前两步的值，因此，得名两步格式。同时，也称前两种方法为单步方法。介绍了常微分方程初值问题数值求解的欧拉格式，这些格式分别具有一阶和二阶精度。同时，需要注意：1、欧拉格式建立的基本思想就是用差商代替微商（向前、向后和中心差商）；2、步长的选取。欧拉格式 一阶精度隐式欧拉格式 一阶精度两步欧拉格式 二阶精度4、 改进的欧拉格式1、 预报值 (Prediction)由欧拉格式计算得一个初步的近似值，记为 ，并称之为预报值，即2、校正值 (Correct)把上述 代入（8）式的右端计算得到另一个

21、值 yn+1 ，并称为校正值，即4、 改进欧拉格式的嵌套形式5、 改写为平均化（平均斜率）形式 具有二阶精度 第四章 方程求根的迭代法2、 线性迭代函数的启示考察线性迭代函数(x)=kx+d的简单情形取初值x0=1.5,可得迭代结果：例1：求方程x3-x-1=0的唯一正根取初值x0=1.5,可得迭代结果：4、迭代过程的局部收敛性 例2：用迭代法求方程x=e-x,在x=0.5附近的一个根x*,要求精度为10-5.5、 迭代过程的收敛速度第2章 课后习题3.确定下列求积公式中的待定参数，使其代数精度尽量的高，并指明求积公式所具有的代数精度。所以，原式具有3次代数精度题5：证明上述3/8辛普森公式是插值型的二、牛顿方法的几何意义切线与x轴的交点。因此，牛顿迭代方法又称切线法。5：用牛顿法解方程xex-1=0四、开方公式的推导牛顿方法的应用例7：用牛顿法求方程x3-x-1=0在x=1.5附近的一个根第5章 线性方程组的迭代法Jacobi 迭代一： 设有方程组 a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 . . . . .