华南理工大学数值分析期末复习总结

1、1期末复习总结期末复习总结数值分析2第一章数值计算的误差计算方法数值计算中的误差数值计算中的误差n来源及种类来源及种类 - 模型误差、参数误差、模型误差、参数误差、 截断误差、舍入误差截断误差、舍入误差。1. 模型误差（也称描述误差）模型误差（也称描述误差） 模型误差是在建立数学模型时，由于忽略了一些次要因素而产生的误差，它是数学建模阶段要考虑的误差，不是计算方法可以解决的。2. 参数误差（也称观测误差）参数误差（也称观测误差） 测量已知参数时，数据带来的误差 ，它也不是计算方法能解决的问题。 数值计算中的误差数值计算中的误差3. 截断误差（也称方法误差）截断误差（也称方法误差） 截断误差是对

2、参与计算的数学公式做简化可行处理后所产生的误差（用有限过程代替无限过程或用容易计算的方法代替不容易计算的方法），是计算方法关注的内容。4. 舍入误差（也称计算误差）舍入误差（也称计算误差） 舍入误差是由于计算机只能表示有限位数字，因而只能取有限位数进行计算所得的误差，它也是计算方法关注的内容。5绝对误差：绝对误差：绝对误差绝对误差*exxx 精确值精确值x* 近似值近似值则称则称 * 为为 绝对误差限绝对误差限/误差限误差限l 若存在一个正数若存在一个正数 *，使得，使得工程上通常记为：工程上通常记为：x = x* *|e*| = |x* - x| *l 绝对误差绝对误差 可能取正，也可能取负

3、可能取正，也可能取负l 绝对误差绝对误差 越小越具有参考价值越小越具有参考价值l 但但 绝对误差绝对误差 却不能很好地表示近似值的精确程度却不能很好地表示近似值的精确程度6相对误差相对误差相对误差：相对误差： x* - x er* = x（精确）（精确） l 若存在正数若存在正数 r*，使得，使得 |er*| r*， 则称则称 r*为为相对误差限相对误差限l 由于真值难以求出，通常也使用下面的定义作为相对误差由于真值难以求出，通常也使用下面的定义作为相对误差 x* - x er* = x*（近似）（近似） l 近似值的精确程度取决于近似值的精确程度取决于 相对误差相对误差 的大小的大小l 实际

4、计算中我们所能得到的是实际计算中我们所能得到的是 误差限误差限 或或 相对误差限相对误差限7有效数字有效数字有效数字：有效数字：若近似值若近似值 x* 的误差限是某一位的半个单的误差限是某一位的半个单位位（即截取按四舍五入规则）（即截取按四舍五入规则） ，且该位到，且该位到 x* 的第一位非的第一位非零数字共有零数字共有 n 位，则称位，则称 x* 有有 n 位有效数字位有效数字x* = a1.a2an 10m (a1 0)且有且有|x - x*| 0.5 10m-n则则 x* 有有 n 位有效数字位有效数字 设设 x*为为 x 的近似值，若的近似值，若 x* 可表示为可表示为l 等价描述等价

5、描述 8有效数字（与相对误差限的关系）有效数字（与相对误差限的关系）定理：定理：设近似值设近似值 x* 可表示为可表示为 x* = a1.a2al 10m (a1 0)，若若 x* 具有具有 n 位有效数字，则其相对误差限满足位有效数字，则其相对误差限满足 1 r* 2a1 10-(n-1)反之，若反之，若 x* 的的相对误差限相对误差限满足满足 则则 x* 至少有至少有 n 位有效数字。位有效数字。 1 r* 2(a1+1) 10-(n-1)有效位数越多，有效位数越多，相对误差限越小相对误差限越小 对于一个问题，所使用的数据集记作D，所得的解集为S，于是问题简记为Sf (D)。 然而在实际中

6、，使用的数据为D*且有一定误差，从而所得解集S*f (D*)也将不会精确地为S(不考虑输入误差及公式误差)。一个重要的是：当数据集D*很接近精确值D时，其解集是否也一定很接近精确解S呢？这就是“解对数据的敏感性”问题。 ：对问题 f (*)，如数据集非常接近精确值D时，相应解集S* f (D*)也非常接近精确解S f (D)，则称问题 f (*)是的，或；否则，称f (*)是的，或。 描述问题的敏感性，常采用“”这一概念。对不同的问题，条件数的具体定义及计算也不尽一样。作为实例，后面将讨论求解线性方程组问题。 需要指出，这种变化并不是由舍入误差引起，也不是计算公式造成，而是由问题本身对系数的敏

7、感性决定的。求高阶多项式的零点问题往往是病态的。 对于良态问题，原则上讲可以求得满足精度要求的解。但输入误差不可避免，因而还应保证所使用的算法不会扩展误差在计算结果中的影响，否则计算结果仍不可信。 ：对于一个由多阶段运算组成的算法，若每经过一个阶段的运算，原有的初值误差或舍入误差的影响不增长，则称这个算法是。 数值计算中应注意的几个问题数值计算中应注意的几个问题n某些原则某些原则 - 使用数值稳定的计算方法；使用数值稳定的计算方法；小心处理病态的数学问题；小心处理病态的数学问题；注意简化计算步骤，减少算术运算的次数；注意简化计算步骤，减少算术运算的次数；避免两个相近的数相减，避免绝对值太小的数

8、作除数；避免两个相近的数相减，避免绝对值太小的数作除数；防止大数防止大数“吃掉吃掉”小数小数 6.简化计算步骤以节省计算量（秦九韶算法）简化计算步骤以节省计算量（秦九韶算法） 7.减少有效数字的损失减少有效数字的损失计算机运算时，绝对值很小的数作除数会溢出停机，而且当绝对值很小的除数稍有一点误差时，对计算结果影响很大，例如2.71822.71822718.2;2471.10.0010.00.00001112第二章插值法计算方法13插值基本概念插值基本概念已知函数已知函数 y = f(x) 在在 a, b 上有定义，且已经测得在点上有定义，且已经测得在点 a x0 x1 xn b 处的函数值为处

9、的函数值为 y0 = f(x0)， ，yn = f(xn)什么是插值如果存在一个如果存在一个简单易算简单易算的函数的函数 P(x)，使得，使得 P(xi) = f(xi)，i = 1, 2, . , n则称则称 P(x) 为为 f(x) 的的插值函数插值函数插值区间插值区间插值节点插值节点求插值函数求插值函数 P(x) 的方法就称为的方法就称为插值法插值法插值节点插值节点无需递无需递增排列增排列，但必须，但必须确保确保互不相同互不相同！插值条件插值条件14基函数插值法基函数插值法基函数法通过基通过基函数来构造函数来构造插值多项式的方法插值多项式的方法就就称为称为基函数基函数插值插值法法Ln(x

10、) = 次数不超过次数不超过 n 的多项式的全体的多项式的全体记记n+1 维线性空间维线性空间设设 l0(x), l1(x), . , ln(x) 构成构成 Ln(x) 的一组基，则插值多项式的一组基，则插值多项式P(x) = f0l0(x) + f1l1(x) + + fnln(x) 寻找合适的基函数寻找合适的基函数 确定插值多项式在这组基下的表示系数确定插值多项式在这组基下的表示系数基函数法基本步骤基函数法基本步骤15Lagrange插值插值Lagrange插值基函数设设 lk(x) 是是 n 次多项式，在插值节点次多项式，在插值节点 x0 , x1 , , xn 上满足上满足1,()0,

11、kjjklxjk 则称则称 lk(x) 为节点为节点 x0 , x1 , , xn 上的上的拉格朗日插值基函数拉格朗日插值基函数单项式单项式基函数利用线性无关的单项式族：利用线性无关的单项式族：21,nxxx构造构造 n 次多项式：次多项式：2012( )nnf xaa xa xa x 16线性与抛物线插值线性与抛物线插值两种特殊情形 n=10110 01 1010110( )( )( )xxxxL xy lxy l xyyxxxx 线性插值多项式（一次插值多项式）线性插值多项式（一次插值多项式）n=2020112012010210122021()()()()()()()()()()()()x

12、xxxxxxxxxxxyyyxxxxxxxxxxxx 抛物线插值多项式（二次插值多项式）抛物线插值多项式（二次插值多项式）2( )Lx17Lagrange插值插值l0(x) , l1(x) , , ln(x) 构成构成 Ln(x) 的一组的一组基基函数函数性质性质注意注意l0(x) , l1(x) , , ln(x) 与插值节点有关，与插值节点有关，但与函数但与函数 f(x) 无关无关lk(x) 的表达式的表达式0110111,()()( ) ()()()()()()kknkkkknjjj kkknjkkxxxxxlxxxxxxxxxxxxxxxx 由构造法可得由构造法可得18误差估计误差估计

13、如何估计误差 )()()(xLxfxRnn 插值余项插值余项(1)1()( )( )( )( )(1)!nxnnnfRxf xLxxn 定理定理设设 f(x) Cna, b ( n 阶连续可微阶连续可微 )，且，且 f (n+1)(x)在在 (a, b) 内存在，则对内存在，则对 x a,b，有，有其中其中 x (a, b) 且与且与 x 有关有关,101( )()()()nnxxxxxxx 19插值余项插值余项l 余项公式只有当余项公式只有当 f(x) 的高阶导数存在时才能使用的高阶导数存在时才能使用几点说明 l 计算插值点计算插值点 x 上的近似值时，应选取与上的近似值时，应选取与 x 相

14、近插值节点相近插值节点10( ) (1)!nnniiMRxxxn 如果如果 ，则，则(1)1( )nnfxM l x 与与 x 有关，通常无法确定有关，通常无法确定, 实际使用中通常是估计其上界实际使用中通常是估计其上界20Newton 插值插值为什么 Newton 插值Lagrange 插值简单易用，但若要增加一个节点时，全部基函插值简单易用，但若要增加一个节点时，全部基函数数 lk(x) 都需重新计算，不太方便。都需重新计算，不太方便。设计一个可以逐次生成插值多项式的算法，即设计一个可以逐次生成插值多项式的算法，即 n 次插值多项式次插值多项式可以通过可以通过 n-1 次插值多项式生成次插

15、值多项式生成 Newton 插值法插值法解决办法解决办法21新的基函数新的基函数n 设插值节点为设插值节点为 x0 , , xn ，考虑插值基函数组，考虑插值基函数组010201011( )1( )( )()()( )()()()nnxxxxxxxxxxxxxxxx l 当增加一个节点当增加一个节点 xn+1 时，只需加上基函数时，只需加上基函数 10()nniixx 22Newton 插值插值n 此时此时 f(x) 的的 n 次插值多项式为次插值多项式为10102010( )()()()()nnnkkpxaa xxaxxxxaxx 问题问题l 如何从如何从 pn-1(x) 得到得到 pn(x

16、) ?l 怎样确定参数怎样确定参数 a0 , , an ? 需要用到需要用到 差商差商（均差）（均差）23差商差商什么是差商设函数设函数 f(x)，节点，节点 x0 , , xn ()(),jiijjif xf xf x xxx f(x) 关于点关于点 xi , xj 的的一阶差商一阶差商,jkijijkkif xxf x xf x xxxx f(x) 关于点关于点 xi , xj , xk 的的二阶差商二阶差商101010,kkkkf xxf xxf xxxxx k 阶差商阶差商差商的一般定义差商的一般定义24差商的性质差商的性质l k 阶差商与阶差商与 k 阶导数之间的关系：阶导数之间的关

17、系：若若 f (x) 在在 a,b 上上 具有具有 k 阶导数，则至少存在一点阶导数，则至少存在一点 (a, b)，使得使得( )01( ),!kkff xxxk 25差商的计算差商的计算如何巧妙地计算差商差商表差商表xi(xi)一阶一阶差商差商二阶差商二阶差商三阶差商三阶差商n 阶差商阶差商x0 x1x2x3 xn(x0)(x1)(x2)(x3) (xn)x0, x1x1, x2x2, x3 xn-1, xnx0, x1, x2x1, x2, x3 xn-2, xn-1, xnx0, x1, x2, x3 xn-3, xn-2, xn-1, xnx0, x1, xn26差商举例差商举例例：例

18、：已知已知 y = (x) 的函数值表，的函数值表，试计算其各阶差商试计算其各阶差商i0123xi-2-112f(xi)531721解：解：差商表如下差商表如下xi(xi)一阶差商一阶差商二阶差商二阶差商三阶差商三阶差商-2-112531721-2743-1-1ex24.mex23.m27Newton 插值插值公式公式Newton 插值公式由差商的定义可得由差商的定义可得000( )() () ,f xf xxx f x x 1,)(,101100 xxxfxxxxfxxf 2 ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf n 11+ (x x0) 2+ + (x x0)(x

19、 xn 1) n 1.)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)28Newton 插值插值公式公式 f (x) = Nn(x) + Rn(x) 10102011()()()( )()nniinaa xxaxxxxaxNxx 001 , . ,().()( )nnnnf x xxxRxxxxxx Nn(x) 是是 n 次多项式次多项式Nn(xi) = f (xi)，i = 0, 1, 2, , n重要性质重要性质Nn(x) 是是 f (x) 的的 n 次插值

20、多项式次插值多项式nixxfaxfaii, 2 , 1 , ),(000 其中其中29Newton / LagrangeNewton 插值多项式与 Lagrange 插值多项式f (x) 在在 x0 , x1 , , xn 上上的的 n 次插值多项式是唯一的！次插值多项式是唯一的！Nn(x) Ln(x)余项也相同余项也相同(1)000()()()(1)!nnnxniiiiff x,x , .,xxxxxn (1)0()(1) !nxnff x,x , . ,xn !)()(0kfx,.,xfkk 将将 x 看作节点看作节点30插值举例插值举例例：例：已知函数已知函数 y = lnx 的函数值如

21、下的函数值如下解解：取节点取节点 0.5, 0.6, 0.4 作差商表作差商表试分别用试分别用牛顿牛顿线性插值和抛物线插值计算线性插值和抛物线插值计算 ln 0.54 的近似值的近似值x0.40.50.60.70.8lnx-0.9163-0.6931-0.5108-0.3567-0.2231xi(xi)一阶差商一阶差商 二阶差商二阶差商0.50.60.4-0.6931-0.5108-0.91631.82302.0275-2.0450N1(x) = -0.6931 + 1.8230(x-0.5)N1(0.54) = -0.6202N2(x) = -0.6931 + 1.8230(x-0.5) -

22、 2.0450(x-0.5)(x-0.6)N2(0.54) = -0.6153ex25.m插值节点无需递插值节点无需递增排列，但必须增排列，但必须确保互不相同！确保互不相同！31第三章函数逼近与曲线拟合计算方法32 函数逼近函数逼近q 三个问题三个问题问题一问题一已知一个函数的数值表已知一个函数的数值表xx1x2xnyy1y2yn能否找到一个能否找到一个简单易算简单易算的的 p(x) ，使得使得 p(xi) = yi 。问题二问题二 函数函数 f(x) 的表达式非常复杂，能否找到一个的表达式非常复杂，能否找到一个简简单易算单易算的的 p(x) ，使得使得p(x) 是是 f(x) 的一个的一个合

23、理的逼近合理的逼近。问题三问题三 问题一的表中的数值带有误差，能否找到一问题一的表中的数值带有误差，能否找到一个个简单易算简单易算的的 p(x) ，可以可以近似地表示这些数据近似地表示这些数据。插值插值数值逼近数值逼近33赋范线性空间赋范线性空间赋范线性空间赋范线性空间 Ca, b线性空间线性空间 Ca, b ，f(x) Ca, b 1-范数范数：1 ( )( ) dbaf xf xx 22 ( )( ) dbaf xfxx ( )max( ) a x bf xf x 2-范数：范数： -范数：范数：34逼近标准逼近标准q 度量度量 p(x) 与与 f(x) 的近似程度的常用两种标准的近似程度

24、的常用两种标准使使 尽可能地小尽可能地小。| )()(|maxxfxpfpbxa使使 尽可能地小尽可能地小。2122)()(badxxfxpfp一致逼近一致逼近平方逼近平方逼近35函数逼近函数逼近 记记 Hn 为所有次数不超过为所有次数不超过 n 的多项式组的多项式组成的集合，给定函数成的集合，给定函数 f(x) Ca, b，若，若 P*(x) Hn 使得使得( )*( )min( )( )nP Hf xPxf xP x 则称则称 P*(x) 为为 f(x) 在在 Ca, b 上的上的 最佳逼近多项式最佳逼近多项式最佳逼近最佳逼近最佳一致逼近最佳一致逼近( )*( )min( )( )nP H

25、f xPxf xP x 36函数逼近函数逼近最小二乘拟合最小二乘拟合21()()niiif xP x 寻找寻找 P*(x) ，使得下面的离散，使得下面的离散 2-范数最小范数最小给定给定 f(x) Ca, b 的数据表的数据表xx0 x1xnyy0y1yn最佳平方逼近最佳平方逼近22( )*( )min( )( )nP Hf xPxf xP x 37正交多项式正交多项式定义定义设设 n(x) 是是首项系数不为首项系数不为 0 的的 n 次多项式次多项式，若，若则称则称 为为 a, b 上带权上带权 (x) 正交正交性质性质 1设设 是正交多项式族，是正交多项式族，Hn 为所有次数不超过为所有次

26、数不超过 n 的多项式组成的线性空间，则的多项式组成的线性空间，则0, (,)( )( )( )0, bjkjkakjkxxx dxAjk 构成构成 Hn 的一组基的一组基 0nn 0kk 称称 n(x) 为为 n 次正交多项式次正交多项式 012 ( ), ( ), ( ) , , ( ) nxxxx 38最佳平方逼近最佳平方逼近设设 f(x) Ca, b， 0(x), 1(x), , n(x) Ca, b 线性线性无关，令无关，令 01span,n 求求 S*(x) ，使得使得2222( )*( )min( )( )sf xSxf xS x S*(x) 称为称为 f(x) 在在 中的中的

27、最佳平方逼近函数最佳平方逼近函数 其中其中 222( )( ), ( )( )( )dbaf xS xfSxffSxS xx 39最佳平方逼近最佳平方逼近如何求如何求 S*(x) ？对任意对任意 S(x) ，可设可设 S(x) = a0 0 + a1 1 + + an n(x)则求则求 S*(x) 等价于求下面的多元函数的最小值点等价于求下面的多元函数的最小值点2010(,)( )( )( )dnbnjjajI a aaxf xaxx 0kIa k = 0, 1, , n40最佳平方逼近最佳平方逼近02( )( )( )( )d0nbjjkajkIxf xaxxxa 即即1( )( )( )d

28、( ) ( )( )dnbbjjkkaajaxxxxx f xxx k = 0, 1, , n 0,njkjkjaf 000100010111110(,)(,)(,)(,)(,)(,)(,)(,)(,)nnnnnnnnnadadad ,kkdf 法方程法方程G41求求 在在0, 1上的一次最佳平方逼近多项式上的一次最佳平方逼近多项式举例举例例：例：(教材教材68页，例页，例 6)2( )1f xx 解：解： 12000,1,1 d1.147dffxx 12110,1 d0.609dfx fxxx 001111/ 21/ 21/ 3adad 010.934, 0.426aa S*(x) = 0.

29、934 + 0.426 x 22220( )( ),0.0026njjjxf xaf ( )0.066x 42最佳平方逼近多项式最佳平方逼近多项式f(x) Ca, b 在在 Hn 中的最佳平方逼近，记为中的最佳平方逼近，记为n 次最佳平方逼近多项式次最佳平方逼近多项式l 取取 Hn 的一组基：的一组基：1, x, x2, , xn ，则法方程为，则法方程为111211123111112nnnnn 0011nnadadad HHilbert 矩阵矩阵H 严重病态严重病态只适合求低只适合求低次最佳逼近次最佳逼近nS 43正交函数作逼近正交函数作逼近若若 0, 1, , n 正交，则法方程的解为正交

30、，则法方程的解为 ,kkkkfa 所以所以k = 0, 1, , n 01010011,*( )( )( )( ),nnnnfffSxxxx l 误差误差 222220,( )( ),nkkkkfxf x 2220,( ),nkkkkff x Bessel 不等式不等式44曲线拟合曲线拟合能否找到一个简单易算的能否找到一个简单易算的 p(x) ，使得，使得 f(x) p(x)已知已知 f(x) 在某些点的函数值：在某些点的函数值：xx0 x1xm f(x)y0y1ym但是但是 m 通常很大通常很大 yi 本身是测量值，不准确，即本身是测量值，不准确，即 yi f (xi) 这时不要求这时不要求

31、 p(xi) = yi , 而只要而只要 p(xi) yi 总体上尽可能小总体上尽可能小 45l 使使 最小最小l 使使 最小最小曲线拟合曲线拟合 p(xi) yi 总体上尽可能小总体上尽可能小 l 使使 最小最小|)(|max1iimiyxpmiiiyxp1|)(|miiiyxp12|)(|q 常见做法常见做法太复杂太复杂 不可导，求不可导，求解困难解困难 最小二乘法：最小二乘法：目前最好的多项式曲线拟合算法目前最好的多项式曲线拟合算法46最小二乘最小二乘曲线拟合的最小二乘问题曲线拟合的最小二乘问题l 这个问题实质上是最佳平方逼近问题的这个问题实质上是最佳平方逼近问题的离散形式离散形式。可以

32、将求连续函数的最佳平方逼近函数的方法直接用可以将求连续函数的最佳平方逼近函数的方法直接用于求解该问题。于求解该问题。已知函数值表已知函数值表 ( xi , yi )，在函数空间在函数空间 中求中求 S*(x) ，使得，使得 22( )00()min ()mmiiiiiis xiiSxyS xy 其中其中 i 是点是点 xi 处的权。处的权。47最小二乘求解最小二乘求解对任意对任意 S(x) = span 0, 1, , n，可设可设 S(x) = a0 0 + a1 1 + + an n(x)则求则求 S*(x) 等价于求下面的多元函数的最小值点等价于求下面的多元函数的最小值点 2010(,)

33、()mniiiiI a aaS xy 200()mnijjiiijaxy0kIa k = 0, 1, , n最小值点最小值点48最小二乘求解最小二乘求解njkkkjfa0),(),( ( k = 0, 1, , n )这里的内积是这里的内积是离散带权内积离散带权内积，即，即0(,)()()mjkijikiixx 0( ,)()()mkiikiiff xx ，000100010111110(,)(,)(,)(,)(,)(,)(,)(,)(,)nnnnnnnnnadadad ,kkdf 法方程法方程G法方程法方程49最小二乘求解最小二乘求解设法方程的解为：设法方程的解为： a0* , a1*, ,

34、 an* , 则则 S*(x) = a0* 0 + a1* 1 + + an* n(x)结论结论S*(x) 是是 f(x) 在在 中的中的 最小二乘解最小二乘解50举例举例最小二乘问题中，如何选择最小二乘问题中，如何选择数学模型数学模型很重要，即如何选取很重要，即如何选取函数空间函数空间 = span 0, 1, , n ，通常需要根据物理，通常需要根据物理意义，或所给数据的分布情况来选取合适的数学模型。意义，或所给数据的分布情况来选取合适的数学模型。51多项式拟合多项式拟合 Hn= span1, x, ., xn, 即即 i = xi, 则相应的法方程为则相应的法方程为miiniimiiii

35、miiinminiiminiiminiiminiimiiimiiiminiimiiimiifxfxfaaaxxxxxxxx000100201001020000 此时此时 为为 f(x) 的的 n 次最小二乘次最小二乘拟合多项式拟合多项式0( )nkkkSxa x 多项式最小二乘曲线拟合多项式最小二乘曲线拟合52举例举例例：例：求下面数据表的二次最小二乘拟合多项式求下面数据表的二次最小二乘拟合多项式 得法方程得法方程4015. 44514. 57680. 83828. 15625. 1875. 15625. 1875. 15 . 2875. 15 . 25210aaaxi00.250.500.7

36、51.00f (xi )1.00001.28401.64872.11702.7183解：解：设二次拟合多项式为设二次拟合多项式为22102)(xaxaaxp解得解得8437. 0,8641. 0,0052. 1210aaa所以此组数据的二次最小二乘拟合多项式为所以此组数据的二次最小二乘拟合多项式为228437. 08641. 00052. 1)(xxxp(1) 若题目中没有给出各点的权值若题目中没有给出各点的权值 i ，默认为默认为 i = 1 (2) 该方法不适合该方法不适合 n 较大时的情形较大时的情形 （病态问题）（病态问题）53第四章数值积分与数值微分计算方法54数值积分数值积分( )

37、( ) dbaI ff xx l 微积分基本公式：微积分基本公式：baaFbFxxf)()(d)(3) f (x) 表达式未知表达式未知，只有通过测量或实验得来的数据表，只有通过测量或实验得来的数据表l 但是在许多实际计算问题中但是在许多实际计算问题中(2) F(x) 难求！难求！甚至有时不能用初等函数表示。甚至有时不能用初等函数表示。 如如21( )sin , xf xxex (1) F(x) 表达式较复杂表达式较复杂时，计算较困难。如时，计算较困难。如61( )1f xx 55几个简单公式几个简单公式l 矩形公式矩形公式( )d() ( )baf xxba f a ( )d()2baabf

38、 xxba f ( )d() ( )baf xxba f b l 梯形公式梯形公式 1( )d()( )( )2baf xxbaf af b l 抛物线公式抛物线公式1( )d()( )4( )62baabf xxbaf aff b ( )d() ( )baf xxba f q 基本思想：基本思想：( , )a b 56一般形式一般形式数值积分公式的一般形式数值积分公式的一般形式0( )d()nbiiaif xxA f x 求积节点求积节点求积系数求积系数机械求积方法机械求积方法l 将定积分计算转化成被积函数的将定积分计算转化成被积函数的函数值函数值的计算的计算l 无需求原函数无需求原函数l

39、易于计算机实现易于计算机实现一般地，用一般地，用 f(x) 在在 a, b 上的一些离散点上的一些离散点 a x0 x1 xn b 上的函数值的加权平均作为上的函数值的加权平均作为 f ( ) 的近似值，可得的近似值，可得57代数精度代数精度定义定义：如果对于所有次数不超过：如果对于所有次数不超过 m 的多项式的多项式 f (x) ，公式，公式精确成立，但对某个次数为精确成立，但对某个次数为 m +1 的多项式不精确成立，则称的多项式不精确成立，则称该求积公式具有该求积公式具有 m 次代数精度次代数精度0( )d()nbiiaif xxA f x l 将将 f (x) = 1, x, x2,

40、, xm 依次代入，公式精确成立依次代入，公式精确成立;l 但对但对 f (x) = xm+1 不精确成立。即：不精确成立。即：22110 d2mmnbmmiiaibaA xxxm ( k = 0, 1, , m )代数精度的验证方法代数精度的验证方法110 d1kknbkkiiaibaA xxxk 58举例举例例：例：试确定系数试确定系数 Ai ，使得下面的求积公式具有尽可能高的使得下面的求积公式具有尽可能高的代数精度，并求出此求积公式的代数精度。代数精度，并求出此求积公式的代数精度。10121( )d ( 1)(0)(1)f xxA fA fA f 解：解：将将 f (x)1, x, x2

41、 代入求积公式，使其精确成立，可得代入求积公式，使其精确成立，可得 1101222023302() /12 () / 20 () / 32/ 3AAAbaAAbaAAba 解得解得 A0 =1/3, A1 =4/3, A2 =1/3。所以求积公式为。所以求积公式为3 )1()0(4)1( d)(11fffxxf 易验证该公式对易验证该公式对 f (x)x3 也精确成立，但对也精确成立，但对 f (x)x4 不精不精确成立，所以此求积公式具有确成立，所以此求积公式具有 3 次代数精度。次代数精度。59插值型求积公式插值型求积公式设求积节点为：设求积节点为：a x0 x1 0, 总存在一算子范数总

42、存在一算子范数 | | ，使得，使得 | | (A) + 90稳定性理论分析稳定性理论分析q 理论分析：理论分析：bbxxA设设|1bAxbAx1又又|xAb| |1bbAAxx(1)(1)由于右端项的扰动而引起的解的变化由于右端项的扰动而引起的解的变化(2)(2)由于系数矩阵的扰动而引起的解的变化由于系数矩阵的扰动而引起的解的变化 bxxAA设设|1xxAAx)(1xxAAx| | |1AAAAxxxAx = b 的的条件数矩阵矩阵A 的的条件数91稳定性理论分析稳定性理论分析定理：定理：考虑线性方程组考虑线性方程组 Ax=b，设，设 b 是精确的，是精确的，A 有有微小微小的变化的变化 A

43、，此时的解为，此时的解为 x + x ，则，则111AxAAAAxAAA 证明：证明：l 当当 A 充分小时，不等式右端约为充分小时，不等式右端约为1AAAA bxxAA设设11| | | | | | ()xAAxxAAxx)(1xxAAx结论结论92矩阵条件数矩阵条件数n 条件数与范数有关，常用的有条件数与范数有关，常用的有无穷范数无穷范数和和2-范数范数l Cond(A)2 称为称为谱条件数谱条件数，当，当 A 对称时有对称时有1Cond( )AAA 1222Cond( )AAA 112221maxCond( )minii nii nAAA 1( ) | | Cond AAA93举例举例例

44、：例： 计算计算 Cond(A) 和和 Cond(A)21111.0001A 解：解：Cond(A) =|A-1| |A| 4 104110001100001000010000A 22.00012.00010.0004( )02A Cond(A)2= max / min 4 104A 对称，且对称，且94第六章线性方程组的迭代解法计算方法95矩阵分裂迭代法矩阵分裂迭代法矩阵分裂迭代法基本思想矩阵分裂迭代法基本思想Ax = b(1)( )kkxBxf k = 0, 1, 2, 给定一个初始向量给定一个初始向量 x(0)，可得，可得 迭代格式迭代格式其中其中 B = M-1N 称为称为迭代矩阵迭代

45、矩阵 11xM NxM bA = M - NMx = Nx + bM 非奇异非奇异A 的一个的一个矩阵分裂矩阵分裂96收敛性分析收敛性分析(1)( )kkxBxf 定理定理：对任意初始向量对任意初始向量 x(0)，上述迭代格式收敛的充要条件是，上述迭代格式收敛的充要条件是( )1B 证明：板书证明：板书定理定理：若存在算子范数若存在算子范数 | |，使得，使得 |B| 1，对任意的初始向量，对任意的初始向量 x(0)，上述迭代格式收敛。，上述迭代格式收敛。例例：考虑迭代法考虑迭代法 x(k+1) = Bx(k) + f 的收敛性，其中的收敛性，其中0.900.30.8B 基本收基本收敛定理敛定

46、理充分条件充分条件97Jacobi 迭代迭代考虑线性方程组考虑线性方程组Ax = b其中其中 A=(aij)n n 非奇异，且对角线元素全不为非奇异，且对角线元素全不为 0。1122diag(,)nnDaaa 211,10 0,0nn naLaa l 将将 A 分裂成分裂成 A = D - L- U， 其中其中1211,000nnnaaUa 98Jacobi 迭代迭代(1)1( )1()kkxDLU xD b k = 0, 1, 2, 令令 M = D，N = L + U，可得，可得 雅可比雅可比 (Jacobi) 迭代方法迭代方法 Jacobi 迭代迭代l 迭代矩阵记为：迭代矩阵记为：1()

47、JDLU l 分量形式：分量形式：1(1)11inkiiijjijjiijj ixba xa xa i = 1, 2, , n， k = 0, 1, 2, 99Gauss-Seidel 迭代迭代l 在计算在计算 时，如果用时，如果用 代替代替 ，则可能会得到更好的收敛效果。则可能会得到更好的收敛效果。(1)kix (1)(1)11,kkixx( )( )11,kkixx (1)( )( )( )11122133111(1)( )( )( )22211233222(1)( )( )( )1122,11 kkkknnkkkknnkkkknnnnn nnnnxba xa xa xaxba xa xa

48、 xaxba xa xaxa (1)( )( )( )11122133111(1)(1)( )( )22211233222(1)(1)(1)(1)1122,11 kkkknnkkkknnkkkknnnnn nnnnxba xa xa xaxba xa xa xaxba xa xaxa 100Gauss-Seidel 迭代迭代 (1)1(1)( )kkkxDbLxUx 写成矩阵形式写成矩阵形式:此迭代方法称为此迭代方法称为 高斯高斯-塞德尔塞德尔 (Gauss-Seidel) 迭代法迭代法k = 0, 1, 2, 11(1)( )kkxDLUxDLb 可得可得1GDLUl 迭代矩阵记为：迭代矩阵

49、记为： 11(1)( )111( )( )( )kkkkkxDLDLA xDLbIDLA xDLbxDLbAx101SOR 迭代迭代l 为了得到更好的收敛效果，可在修正项前乘以一个为了得到更好的收敛效果，可在修正项前乘以一个 松弛因子松弛因子 ，于是可得迭代格式，于是可得迭代格式在在 G-S 迭代中迭代中 (1)(1)(1)( )( )11,11,11,kkkkkiiii iii iii nniixba xaxaxa xa 1(1)( )1( )inkkiijjijjiijj ikiba xa xax (1)1(1)()1()inkkiijjijjiijkiij ikba xaaxxx 1(1

50、)(1)(11)(1)inkkiijjijjiijjkikiiba xaxa xx 102SOR 迭代迭代 (1)( )1(1)( )( )kkkkkxxDbLxUxDx 11(1)( )(1)kkxDLDU xDLb 写成矩阵形式写成矩阵形式:可得可得 SOR (Successive Over-Relaxation) 迭代方法迭代方法 1(1)LDLDU l 迭代矩阵记为：迭代矩阵记为：l SOR 的优点的优点：通过选取合适的：通过选取合适的 ，可获得更快的收敛速度，可获得更快的收敛速度l SOR 的缺点的缺点：最优参数最优参数 的的选取比较困难选取比较困难103l Jacobi 迭代收敛的

51、迭代收敛的充要充要条件条件 (J)1l G-S 迭代收敛的迭代收敛的充要充要条件条件 (G)1l SOR 迭代收敛的迭代收敛的充要充要条件条件 (L )1收敛性收敛性收敛性定理收敛性定理l Jacobi 迭代收敛的迭代收敛的充分充分条件条件 |J| 1l G-S 迭代收敛的迭代收敛的充分充分条件条件 |G| 1l SOR 迭代收敛的迭代收敛的充分充分条件条件 |L | 1104Jacobi、G-S 收敛性收敛性定理定理：若若 A 严格对角占优严格对角占优或或不可约弱对角占优不可约弱对角占优，则，则 A 非奇异非奇异定理定理：若若 A 严格对角占优严格对角占优或或不可约弱对角占优不可约弱对角占优

52、，则，则 Jacobi 迭迭代和代和 G-S 迭代均收敛迭代均收敛 定理定理：若若 A 对称，且对角线元素均大于对称，且对角线元素均大于 0，则，则Jacobi 迭代收敛的充要条件是迭代收敛的充要条件是 A 与与 2D-A 均正定；均正定；(1) G-S 迭代收敛的充要条件是迭代收敛的充要条件是 A 正定。正定。105SOR 收敛性收敛性定理定理：若若 SOR 迭代收敛，则迭代收敛，则 0 2。l SOR 收敛的必要条件收敛的必要条件定理定理：若若 A 对称正定，且对称正定，且 0 2，则则 SOR 迭代收敛。迭代收敛。l SOR 收敛的充分条件收敛的充分条件定理定理：若若 A 严格对角占优或

53、不可弱约对角占优，且严格对角占优或不可弱约对角占优，且 0 1，则则 SOR 迭代收敛。迭代收敛。106举例举例例例：设设 ，给出，给出 Jacobi 和和 G-S 收敛的充要条件收敛的充要条件 111aaAaaaa 解：解：A 对称，且对角线元素均大于对称，且对角线元素均大于 0，故，故 (1) Jacobi 收敛的充要条件是收敛的充要条件是 A 和和 2D-A 均正定均正定(2) G-S 收敛的充要条件是收敛的充要条件是 A 正定正定A 正定正定2212310,10,(1) (12 )0DDaDaa 0.51a 2D-A 正定正定2212310,10,(1) (12 )0DDaDaa 0.

54、50.5aJacobi 收敛的充要条件是：收敛的充要条件是：-0.5a0.5G-S 收敛的充要条件是：收敛的充要条件是：-0.5a1107举例举例解法二：解法二：Jacobi 的迭代矩阵为的迭代矩阵为设设 是是 J 的特征值，则由的特征值，则由 det( I - J) = 0 可得可得000aaJaaaa ( - a)2 ( +2a) = 0Jacobi 收敛的充要条件是收敛的充要条件是 (J)1 | |1，即即 -0.5a0.5108收敛速度收敛速度定义定义：迭代格式迭代格式 x(k+1) = Bx(k) + f 的平均收敛速度为的平均收敛速度为1( )lnkkkR BB 渐进收敛速度为渐进

55、收敛速度为( )ln( )R BB l (B) 越小，收敛越快越小，收敛越快109第七章非线性方程(组)的数值解法计算方法110不动点迭代不动点迭代q 基本思想基本思想l 构造构造 f (x) = 0 的一个等价方程：的一个等价方程： ( )xx (x) 的不动点的不动点f (x) = 0 x = (x)等价变换等价变换f (x) 的零点的零点111不动点迭代不动点迭代q 具体过程具体过程l 任取一个迭代初始值任取一个迭代初始值 x0 ，计算，计算得到一个迭代序列：得到一个迭代序列： x0，x1，x2，. . . ，xn，. . . 1()kkxx k = 0, 1, 2, . . 几何含义：

56、几何含义：求曲线求曲线 y = (x) 与直线与直线 y = x 的交点的交点112连续性分析连续性分析设设 (x) 连续，若连续，若 收敛，即收敛，即 ，则，则 1limlim ()limkkkkkkxxx lim*kkxx 0kkx *( *)xx ( *)0f x 即即q 收敛性分析收敛性分析性质：性质：若若 ，则不动点迭代，则不动点迭代收敛收敛，且，且 x* 是是 f(x)=0 的解；否则迭代法的解；否则迭代法发散发散。lim*kkxx 113解的存在唯一性解的存在唯一性定理定理：设设 (x) Ca,b 且满足且满足证明：板书证明：板书对任意的对任意的 x a,b 有有 (x) a,b

57、存在常数存在常数 0L1，使得任意的，使得任意的 x, y a,b 有有( )( )xyL xy 则则 (x) 在在 a,b 上存在上存在唯一的不动点唯一的不动点 x*解的存在唯一性解的存在唯一性114收敛性分析收敛性分析定理定理：设设 (x) Ca,b 且满足且满足证明：板书证明：板书对任意的对任意的 x a,b 有有 (x) a,b存在常数存在常数 0L1，使得任意的，使得任意的 x, y a,b 有有( )( )xyL xy 则对任意初始值则对任意初始值 x0 a,b，不动点迭代，不动点迭代 xk+1= (xk) 收敛，且收敛，且不动点迭代的收敛性不动点迭代的收敛性11011kkkkLL

58、xxxxxxLL 115收敛性分析收敛性分析不动点迭代的收敛性不动点迭代的收敛性若若 (x) C1a,b 且对任意且对任意 x a,b 有有 | (x)| L1则上述定理中的结论成立。则上述定理中的结论成立。收敛性结论表明：收敛性结论表明：收敛性与初始值的选取无关收敛性与初始值的选取无关全局收敛全局收敛116举例举例例：例：求求 f(x) = x3 x 1=0 在区间在区间 1, 2 中的根中的根 3( )1xx 231( )(1)3xx 31( )0.2513x (1)1( )2x (1,2)x 3( )1xx 2( )3xx ( )1x (2)0( )7x (1,2)x ex71.m117

59、局部收敛局部收敛定义定义：设设 x* 是是 (x) 的不动点，若存的不动点，若存在在 x* 的某个的某个 -邻域邻域 U(x*) =x*- , x* + ，对任意，对任意 x0 U(x*)，不动点迭代，不动点迭代 xk+1 = (xk) 产生的点列都收敛到产生的点列都收敛到 x*，则称该迭代，则称该迭代局部收敛。局部收敛。定理：定理：设设 x* 是是 (x) 的不动点，若的不动点，若 (x) 在在 x* 的某个邻域内的某个邻域内连续，且连续，且 | (x*)| 0，则称该迭代为，则称该迭代为 p 阶收敛阶收敛。当当 r =1 时称为时称为线性收敛线性收敛，此时，此时 C 1 时称为时称为超线性

60、收敛超线性收敛l 二分法是线性收敛的二分法是线性收敛的l 若若 (x*) 0，则，则不动点迭代不动点迭代 xk+1 = (xk) 线性收敛线性收敛119收敛速度收敛速度定理：定理：设设 x* 是是 (x) 的不动点的不动点，若若 (p)(x) 在在 x* 的的某邻域内连续，且某邻域内连续，且(1)()( *)( *)( *)0,( *)0ppxxxx 则迭代则迭代 xk+1 = (xk) 是是 p 阶收敛的。阶收敛的。证明：板书证明：板书120举例举例例：例：求求 f(x) = x2 - 3=0 的正根的正根 2( )3xxx (1)( *)2 311x ex72.m*3x 23( )4xxx