1、计算方法计算方法复习课 2019-12-29教学内容教学内容l引论l第一章 插值方法l第二章 数值积分l第三章 常微分方程的差分方法l第四章 方程求根的迭代法l第五章 线性方程组的迭代法l第六章 线性方程组的直接法（但精度、误差等概念要贯穿于考题中）考题形式考题形式l填空题主要考察基本概念，对方法的理解共8题，共40分五章的内容基本平均分配l大题计算、证明等5-6道题，共60分五章的内容基本平均分配其中有1-2道题为作业题或书上的例题（可能改数）第一章第一章 插值方法插值方法l拉格朗日插值（插值余项）l埃特金算法l牛顿插值l埃尔米特插值l分段插值l样条插值l曲线拟合的最小二乘法第一章第一章 插
2、值方法插值方法 第一章第一章 插值方法插值方法nkyxpkkn,1,0)()(00)(),1,0()(0nkyk第一章第一章 插值方法插值方法几何几何意义：意义：x0 x1x2x3x4xg(x)f(x)()yg x()yf x 代数插值：代数插值：为多项式函数集为多项式函数集()g x第一章第一章 插值方法插值方法代数插值：代数插值：为多项式函数集为多项式函数集()g x 第一章第一章 插值方法插值方法0()()nniiiP xl x y njijjijixxxxxl0)()()(10()ijijijl xij 与与 节点节点 有关，而与有关，而与 f 无关无关给定给定 xi=i+1,i=0,
3、1,2,3,4,5.下面哪个是下面哪个是 l2(x)的图像？的图像？y 0-1 0.5 -0.5 1 2 3 4 5 6 x y 0-1 0.5 -0.5 1 2 3 4 5 6 x y 0-1 0.5 -0.5 1 2 3 4 5 6 x ABC第一章第一章 插值方法插值方法0()()nniiiP xl x y njijjijixxxxxl0)()()(思考思考2：f(x)=xk(k=0,1,n)关于互异节点关于互异节点xi(i=0,1,n)的拉格朗日插值公式的拉格朗日插值公式第一章第一章 插值方法插值方法0()()nniiiP xl x y njijjijixxxxxl0)()()(1.2
4、 0.4 -0.8-2.0yi=f(xi)2.0 1.8 1.4 1.0 xi()yf x 求求 的值的值 1 5(.)f求方程求方程 在在1，2内根的近似值内根的近似值 。x 0()f x 例：例：已知单调连续函数已知单调连续函数 在如下采样点的函数值：在如下采样点的函数值：第一章第一章 插值方法插值方法0()()nniiiP xl x y njijjijixxxxxl0)()()(（2）Lagrange插值多项式结构插值多项式结构对称对称，形式简单，形式简单.注注：（1）若不将多项式次数限制为若不将多项式次数限制为 n，则插值多项式，则插值多项式不唯一不唯一。（4）当插值当插值节点增加节点
5、增加时，时，拉氏基函数需要拉氏基函数需要重新重新计算，计算，n较大时，计算量非常大较大时，计算量非常大,故故常用于理论分析。常用于理论分析。（3）误差估计误差估计nkknxxnfxr01)()!1()()(第一章第一章 插值方法插值方法(效率，或临时增加一个节点效率，或临时增加一个节点)kixfxxxxxfxxxxxfikkikkkikiik)()()(111111特点：特点：高次插值过程归结为线性插值的多次重复；数据的一致程度可判断插值结果的精度。给定3个节点及节点上的函数值(xi，f(xi)(i=0，2)，按Aitken插值方法构造插值函数，试在下图中画出任意给定x对应的f2(x2)第一章
6、第一章 插值方法插值方法)()()(,()()(,()(,()()(1010102100100nnnxxxxxxxxxfxxxxxxxfxxxxfxfxpnknkjjjkknxxxfxxxf0010)()(),(011100010110)()()()(),(xxxfxxxfxxxfxfxxf021021210),(),(),(xxxxfxxfxxxf差商具有对称性差商具有对称性余项？!)(),(10nfxxxfnn第一章第一章 插值方法插值方法nkyxpkkn,1,0)()(00)(),1,0()(0nkykTaylor插值 20000000()()()()()()()()2!nnnfxfxP
7、 xf xfxxxxxxxn110()()()()1!nnnff xP xxxn第一章第一章 插值方法插值方法Hermite插值求函数求函数f(x)的二次近似式的二次近似式P2(x)，满足：，满足：P2(x0)=f(x0)=y0,P2(x0)=f(x0)=y0,P2(x1)=f(x1)=y1。求函数求函数f(x)的三次近似式的三次近似式p3(x)，满足：，满足：P3(x0)=f(x0)=y0,P3(x0)=f(x0)=y0,P3(x1)=f(x1)=y1，P3(x1)=f(x1)=y1第一章第一章 插值方法插值方法分段插值-5-4-3-2-1 0 1 2 3 4 5-0.5 0 0.5 1 1
8、.5 2 2.5 第一章第一章 插值方法插值方法分段插值样条插值第二章第二章 数值积分数值积分l机械求积l牛顿-柯特斯公式l龙贝格算法l高斯公式l数值微分第二章第二章 数值积分数值积分为什么研究数值积分：为什么研究数值积分：(1)有些函数的原函数不能用初等函数表现为有限的形式；有些函数的原函数不能用初等函数表现为有限的形式；(2)原函数的形式复杂；原函数的形式复杂；(3)原函数没有具体的表达式，只有离散点。原函数没有具体的表达式，只有离散点。定积分的数值解法定积分的数值解法(效率效率+精度精度)。第二章第二章 数值积分数值积分l机械求积 niiinxfAfIfI0)()()(baxxffId)
9、()(第二章第二章 数值积分数值积分l机械求积niiinxfAfIfI0)()()(求积公式的求积公式的收敛性收敛性:0lim()()nbkkankA f xf x dx 0nkkAba 求积系数的求积系数的特征特征:求积公式的求积公式的稳定性稳定性:求积系数全为正时，公式是稳定的求积系数全为正时，公式是稳定的第二章第二章 数值积分数值积分l机械求积niiinxfAfIfI0)()()(求积公式的求积公式的精度：精度：如果求积公式如果求积公式对一切不高于对一切不高于m次的多项式都恒成立，而对于某个次的多项式都恒成立，而对于某个m+1次次多项式不能精确成立，则称该求积公式具有多项式不能精确成立，
10、则称该求积公式具有m次次代数精度代数精度。0()()nnkkkIfA f x 0()()nnkkkIfA f x 求积公式求积公式 具有次具有次m代数精代数精度的充要条件是度的充要条件是 为为 时求积公式时求积公式精确成立精确成立，而，而 为为 时求积公式时求积公式不能成为等式。不能成为等式。()f x231mxxxx、()f x1mx 第二章第二章 数值积分数值积分l机械求积niiinxfAfIfI0)()()(Q1、节点已知，系数Ai如何选取Q2、节点自由选取，怎么选第二章第二章 数值积分数值积分l求积节点固定的情况nkkknxlxfxp0)()()(0()()nbkkaklx f xdx
11、 0()()nbkkakf xlx dx 0()nkkkA f x ()()bbnaaf x dxLx dx bakkxxlAd)(baniinnxxxnffRd)()!1()()(01插值型插值型求积公式余项：求积公式余项：插值型插值型求积公式的代数精度：求积公式的代数精度：插值型求积公式至少具有插值型求积公式至少具有n次代数精度次代数精度 具有具有n次代数精度的求积公式必是插值型的次代数精度的求积公式必是插值型的第二章第二章 数值积分数值积分l求积节点固定的情况第二章第二章 数值积分数值积分l求积节点固定的情况00()()(1)()(1)(2)(1)(1)()()()!()!ninnjij
12、jijjijixxtjlxt tttititnxxijini nininiiintntitittttinihAxfAfI00d)()1)(1()2)(1()!(!)1()()(0(1)(1)(2)(1)(1)()d!()!n iniiACt tttititntban i ni 0()()()nniiiIfbaC f x牛顿牛顿-柯特斯公式柯特斯公式第二章第二章 数值积分数值积分l求积节点固定的情况梯形公式梯形公式Simpson公式公式Cotes公式公式阶数越高越好？阶数越高越好？精度？稳定性？n为为偶数偶数时，时，NewtonCotes求积公式求积公式至少具有至少具有n+1次代数精度。次代数精
13、度。n为为奇数奇数时，时，NewtonCotes求积公式求积公式至少具有至少具有n次代数精度。次代数精度。复化求积公式复化求积公式第二章第二章 数值积分数值积分l求积节点可选择的情况高斯求积公式提高精度当求积当求积节点个数节点个数确定后，不管这些求积节点如何选确定后，不管这些求积节点如何选 取，取，求积公式的求积公式的代数精度代数精度最高最高能达到多少？能达到多少？具有具有最高最高代数精度代数精度的求积公式的求积公式中求积节点如何选取？中求积节点如何选取？第二章第二章 数值积分数值积分l求积节点可选择的情况高斯求积公式提高精度niiixfAxxffI111)(d)()(第二章第二章 数值积分数
14、值积分l求积节点可选择的情况高斯求积公式提高精度11()d2(0)f xxf中点公式)()(d)(221111xfAxfAxxf1212113xxAA)232()232(2d)(ababfababfabxxfba第二章第二章 数值积分数值积分l求积节点可选择的情况高斯求积公式提高精度0d)()(11xxwxpniixxxw1)()(第二章第二章 数值积分数值积分l求积节点可选择的情况高斯求积公式提高精度1()nnkkkRfIA f x 2212()()()!nnbiaifxxdxn Gauss型型求积公式总是稳定的。求积公式总是稳定的。0kA 设设f在在a,b上连续，则上连续，则Gauss型求
15、积公式是收敛的型求积公式是收敛的第三章第三章 常微分方程的差分方法常微分方程的差分方法l欧拉方法l改进的欧拉方法l龙格-库塔方法l亚当姆斯方法l收敛性与稳定性l方程组与高阶方程的情形l边值问题重点：重点：构造某种格式构造某种格式 格式的收敛性和稳定性格式的收敛性和稳定性 格式的精度格式的精度第三章第三章 常微分方程的差分方法常微分方程的差分方法00)(),(yxyyxfy初值问题初值问题 的解表示过点的解表示过点 的一条的一条曲线曲线()00(,)xy初值问题初值问题 的数值解表示一组的数值解表示一组离散点列离散点列()(,)iixyoxynx(,)nnxy),(00yx()yy x 0 x)
16、,(00yx 2x),(22yx 1x),(11yx 第三章第三章 常微分方程的差分方法常微分方程的差分方法设设 是是准确准确的，用某种方法的，用某种方法计算计算 时产生的截时产生的截断误差，断误差，称为该方法的称为该方法的局部截断局部截断误差误差ny1ny 称称 为某方为某方法在点法在点 的的整体截断整体截断误差误差1nx 111()nnney xy ny去掉去掉 准确准确的前提的前提)(lim,00nnnhnxyynhxx第三章第三章 常微分方程的差分方法常微分方程的差分方法已知011111)2,1,0)(,()(,()()()()()()()(ynyxfhyyxyxfhxyxyhxyxy
17、xxxyxyxynnnnnnnnnnnnnnn11()()()2nnny xy xyxh11()()()nnny xy xyxh第三章第三章 常微分方程的差分方法常微分方程的差分方法1111d(,)d()()(,)dnnnnnnxxxnnxxxyxf x yxy xy xf x yx)(,(),(2)()(111nnnnnnxyxfyxfhxyxy)(,()()(1nnnnxyxfhxyxy),(1nnnnyxfhyy),(),(2111nnnnnnyxfyxfhyy第三章第三章 常微分方程的差分方法常微分方程的差分方法l改进的欧拉方法：预报-校正系统),(,(),(2),(),(2),(11
18、1111nnnnnnnnnnnnnnnnnnyxfhyxfyxfhyyyxfyxfhyyyxfhyy第三章第三章 常微分方程的差分方法常微分方程的差分方法l龙格-库塔方法111()()()()()(,()(,()nnnnnny xy xyy xy xhfyhyyhfy)(,(yf第三章第三章 常微分方程的差分方法常微分方程的差分方法l龙格-库塔方法111()()()()()(,()(,()nnnnnny xy xyy xy xhfyhyyhfy)(,(yfpxqx第三章第三章 常微分方程的差分方法常微分方程的差分方法l龙格-库塔方法),(),()1(121211phKyxfKyxfKKKhyy
19、npnnnnn第三章第三章 常微分方程的差分方法常微分方程的差分方法pxqx2nx1nx龙格库塔方法的基本思想亚当姆斯方法的基本思想第三章第三章 常微分方程的差分方法常微分方程的差分方法l亚当姆斯方法)(,()()(1yfhxyxynn),(),()1(11111nnnnnnnnnnyxfyyxfyyyhyy)3(211nnnnyyhyy第三章第三章 常微分方程的差分方法常微分方程的差分方法l亚当姆斯方法)9375955(243211nnnnnnyyyyhyy)51623(12211nnnnnyyyhyy)(211nnnnyyhyy第三章第三章 常微分方程的差分方法常微分方程的差分方法l收敛性
20、与稳定性)(lim,00nnnhnxyynhxx欧拉格式：欧拉格式：如果初值准确，则有如果初值准确，则有h0,en 0，Euler格式收敛。格式收敛。第三章第三章 常微分方程的差分方法常微分方程的差分方法l收敛性与稳定性mmnnyxynmyxyn)()(，有，而，01234567891011-6-4-2024errorx h=0.2 h=1 h=1.12211111.332,nnnnnnnnnnyyyyhfxyyyhfxyerroryy 2124801xyyy 第四章第四章 方程根的迭代法方程根的迭代法l迭代过程的收敛性l迭代过程的加速l牛顿法l弦截法重点：重点：不动点理论不动点理论 写出有收
21、敛性的格式，写出有收敛性的格式，用于解题用于解题第四章第四章 方程根的迭代法方程根的迭代法l迭代法基本思想*limkkxx第四章第四章 方程根的迭代法方程根的迭代法迭代格式迭代格式 如何构造序列 如何判断迭代格式的好坏收敛性及收敛速度收敛性及收敛速度误差估计误差估计第四章第四章 方程根的迭代法方程根的迭代法*xxpxekkCeekkk1lim第四章第四章 方程根的迭代法方程根的迭代法f(x)=0 x=g(x)（迭代函数）（迭代函数）等价变换等价变换f(x)的根的根x g(x)的不动点的不动点x 10 1 2(),(*)kkxg xk 第四章第四章 方程根的迭代法方程根的迭代法,)(,baxgb
22、ax gxL*101kkkLexxxxL11|*|1kkkxxxxLl不动点迭代不动点理论（压缩映像原理）第四章第四章 方程根的迭代法方程根的迭代法,)(,baxgbax gxL*101kkkLexxxxL11|*|1kkkxxxxL第四章第四章 方程根的迭代法方程根的迭代法l局部收敛 设设 为为 的不动点，的不动点，在在 的某邻域连续，的某邻域连续，且且 ，则迭代法，则迭代法(*)局部收敛。局部收敛。x g gx x 1gxL 第四章第四章 方程根的迭代法方程根的迭代法l收敛速度*kkexxCeekkk1lim第四章第四章 方程根的迭代法方程根的迭代法l牛顿法10 1 2(),()kkkkf
23、 xxxkfx xyx*x01x2xl假设函数假设函数f(x)有有m(m 2)阶连续导阶连续导数，数，x*是方程是方程f(x)=0的单根，则当的单根，则当x0充分接近充分接近x*时，时，Newton法收敛，法收敛，且至少为二阶收敛。且至少为二阶收敛。牛顿迭代法的优缺点牛顿迭代法的优缺点 优点：优点：在单根附近在单根附近,牛顿迭代法具有平方收敛牛顿迭代法具有平方收敛(至少至少)的的 速度，所以在迭代过程中只要迭代几次就会得速度，所以在迭代过程中只要迭代几次就会得 到很精确解到很精确解。缺点缺点:1.重根情形下为局部线性收敛重根情形下为局部线性收敛;2.牛顿迭代法计算量比较大牛顿迭代法计算量比较大
24、:因每次迭代除计算因每次迭代除计算 函数值外还要计算导数值函数值外还要计算导数值;3.选定的初值要接近方程的解，否则有可能得不选定的初值要接近方程的解，否则有可能得不 到收敛的结果到收敛的结果;第四章第四章 方程根的迭代法方程根的迭代法第四章第四章 方程根的迭代法方程根的迭代法l弦截法2,1,0),()()()(001kxxxfxfxfxxkkkkk00()()()()kkkf xf xfxxx提高收敛速度？提高收敛速度？11()()()()kkkkkf xf xfxxx2x1x0 x*x()yf xyx3x2x1x0 x*x()yf xyx3x第五章第五章 线性方程组的迭代法线性方程组的迭代
25、法l迭代公式的建立l迭代过程的收敛性第五章第五章 线性方程组的迭代法线性方程组的迭代法l迭代公式的建立与解与解f(x)=0 的的不动点迭代不动点迭代相似相似，将方程组将方程组等价改写成等价改写成 形式，从而建立形式，从而建立迭代格式迭代格式Ax=bx=Mx+g1()()xMxgkk ，从，从 出发，生成迭代序列出发，生成迭代序列0()x()x k第五章第五章 线性方程组的迭代法线性方程组的迭代法l迭代过程的收敛性M0k迭代法迭代法 收敛的充要条件是收敛的充要条件是1()()xMxgkk 1()()xMxgkk *(1)(0)|1|kkkeMxxxxM11212212,1121312323132
26、3300000000000000000000000000000000nnn nnnnnnnaaaaaaaaaaaaaaaaA=L+D+U第五章第五章 线性方程组的迭代法线性方程组的迭代法l雅可比迭代从而有：从而有：,2,1,2,1)(11)1()(knixabaxnijjkjijiiiki；对角占优对角占优对角占优方程组的对角占优方程组的Jacobi迭代收敛迭代收敛1nijiijj iaa第五章第五章 线性方程组的迭代法线性方程组的迭代法l高斯-塞德尔迭代,2,1,2,1)(11)1(11)()(knixaxabaxnijkjijijkjijiiiki；第五章第五章 线性方程组的迭代法线性方程组的迭代法l松弛法(Gauss-Seidel的加速方法)；nixxaxabaxkinijkjijijkjijiiiki,2,1)1()()1(1)1(11)()(注意注意l准确性、精度、有效数字的概念贯穿于各个求解过程当中l考试中没有特别复杂的计算l要把解题思想写清楚l低阶的公式应该记住
