数值分析期末复习总结ppt课件

《数值分析期末复习总结ppt课件》由会员分享，可在线阅读，更多相关《数值分析期末复习总结ppt课件（138页珍藏版）》请在金锄头文库上搜索。

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

2、参与计算的数学公式做简化可行处理后所产生的误差（用有限过程代替无限过程或用容易计算的方法代替不容易计算的方法），是计算方法关注的内容。4. 舍入误差（也称计算误差）舍入误差（也称计算误差） 舍入误差是由于计算机只能表示有限位数字，因而只能取有限位数进行计算所得的误差，它也是计算方法关注的内容。5绝对误差：绝对误差：绝对误差绝对误差x 精确值精确值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 等价描述等价描述 8

5、有效数字（与相对误差限的关系）有效数字（与相对误差限的关系）定理：定理：设近似值设近似值 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，于

6、是问题简记为Sf (D)。 然而在实际中，使用的数据为D*且有一定误差，从而所得解集S*f (D*)也将不会精确地为S(不考虑输入误差及公式误差)。一个重要的问题问题是：当数据集D*很接近精确值D时，其解集是否也一定很接近精确解S呢？这就是“解对数据的敏感性”问题。 定义定义：对问题 f (*)，如数据集非常接近精确值D时，相应解集S* f (D*)也非常接近精确解S f (D)，则称问题 f (*)是良良态态的，或解对数据不敏感解对数据不敏感；否则，称f (*)是病态病态的，或解对数解对数据敏感据敏感。 描述问题的敏感性，常采用“条件数条件数”这一概念。对不同的问题，条件数的具体定义及计算也

7、不尽一样。作为实例，后面将讨论求解线性方程组问题。 需要指出，这种变化并不是由舍入误差引起，也不是计算公式造成，而是由问题本身对系数的敏感性决定的。求高阶多项式的零点问题往往是病态的。 对于良态问题，原则上讲可以求得满足精度要求的解。但输入误差不可避免，因而还应保证所使用的算法不会扩展误差在计算结果中的影响，否则计算结果仍不可信。 定义定义：对于一个由多阶段运算组成的算法，若每经过一个阶段的运算，原有的初值误差或舍入误差的影响不增长，则称这个算法是数值稳定的数值稳定的数值稳定的数值稳定的。 数值计算中应注意的几个问题数值计算中应注意的几个问题n某些原则某些原则 - 使用数值稳定的计算方法；使用

8、数值稳定的计算方法；小心处理病态的数学问题；小心处理病态的数学问题；注意简化计算步骤，减少算术运算的次数；注意简化计算步骤，减少算术运算的次数；避免两个相近的数相减，避免绝对值太小的数作除数；避免两个相近的数相减，避免绝对值太小的数作除数；防止大数防止大数“吃掉吃掉”小数小数 6.简化计算步骤以节省计算量（秦九韶算法）简化计算步骤以节省计算量（秦九韶算法） 7.减少有效数字的损失减少有效数字的损失计算机运算时，绝对值很小的数作除数会溢出停机，而且当绝对值很小的除数稍有一点误差时，对计算结果影响很大，例如12第二章插值法计算方法13插值基本概念插值基本概念已知函数已知函数 y = f(x) 在在

9、 a, b 上有定义，且已经测得在点上有定义，且已经测得在点 a x0 x1 xn b 处的函数值为处的函数值为 y0 = f(x0)， ，yn = f(xn)什么是插值如果存在一个如果存在一个简单易算简单易算的函数的函数 P(x)，使得，使得 P(xi) = f(xi)，i = 1, 2, . , n则称则称 P(x) 为为 f(x) 的的插值函数插值函数插值区间插值区间插值节点插值节点求插值函数求插值函数 P(x) 的方法就称为的方法就称为插值法插值法插值节点插值节点无需递无需递增排列增排列，但必须，但必须确保确保互不相同互不相同！插值条件插值条件14基函数插值法基函数插值法基函数法通过基

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

11、n 次多项式，在插值节点次多项式，在插值节点 x0 , x1 , , xn 上满足上满足则称则称 lk(x) 为节点为节点 x0 , x1 , , xn 上的上的拉格朗日插值基函数拉格朗日插值基函数单项式单项式基函数利用线性无关的单项式族：利用线性无关的单项式族：构造构造 n 次多项式：次多项式：16线性与抛物线插值线性与抛物线插值两种特殊情形 n=1线性插值多项式（一次插值多项式）线性插值多项式（一次插值多项式）n=2抛物线插值多项式（二次插值多项式）抛物线插值多项式（二次插值多项式）17Lagrange插值插值l0(x) , l1(x) , , ln(x) 构成构成 Ln(x) 的一组的一

12、组基基函数函数性质性质注意注意l0(x) , l1(x) , , ln(x) 与插值节点有关，与插值节点有关，但与函数但与函数 f(x) 无关无关lk(x) 的表达式的表达式由构造法可得由构造法可得18误差估计误差估计如何估计误差 插值余项插值余项定理定理设设 f(x) Cna, b ( n 阶连续可微阶连续可微 )，且，且 f (n+1)(x)在在 (a, b) 内存在，则对内存在，则对 x a,b，有，有其中其中 x (a, b) 且与且与 x 有关有关,19插值余项插值余项l 余项公式只有当余项公式只有当 f(x) 的高阶导数存在时才能使用的高阶导数存在时才能使用几点说明 l 计算插值点

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

14、多项式生成 Newton 插值法插值法解决办法解决办法21新的基函数新的基函数n 设插值节点为设插值节点为 x0 , , xn ，考虑插值基函数组，考虑插值基函数组l 当增加一个节点当增加一个节点 xn+1 时，只需加上基函数时，只需加上基函数 22Newton 插值插值n 此时此时 f(x) 的的 n 次插值多项式为次插值多项式为问题问题l 如何从如何从 pn-1(x) 得到得到 pn(x) ?l 怎样确定参数怎样确定参数 a0 , , an ? 需要用到需要用到 差商差商（均差）（均差）23差商差商什么是差商设函数设函数 f(x)，节点，节点 x0 , , xn f(x) 关于点关于点 x

15、i , xj 的的一阶差商一阶差商f(x) 关于点关于点 xi , xj , xk 的的二阶差商二阶差商k 阶差商阶差商差商的一般定义差商的一般定义24差商的性质差商的性质l k 阶差商与阶差商与 k 阶导数之间的关系：阶导数之间的关系：若若 f (x) 在在 a,b 上上 具有具有 k 阶导数，则至少存在一点阶导数，则至少存在一点 (a, b)，使得使得25差商的计算差商的计算如何巧妙地计算差商差商表差商表xi(xi)一阶一阶差商差商二阶差商二阶差商三阶差商三阶差商n 阶差商阶差商x0x1x2x3xn(x0)(x1)(x2)(x3)(xn)x0, x1x1, x2x2, x3xn-1, xn

16、x0, x1, x2x1, x2, x3xn-2, xn-1, xnx0, x1, x2, x3xn-3, xn-2, xn-1, xnx0, x1, xn26差商举例差商举例例：例：已知已知 y = (x) 的函数值表，的函数值表，试计算其各阶差商试计算其各阶差商i0123xi-2-112f(xi)531721解：解：差商表如下差商表如下xi(xi)一阶差商一阶差商二阶差商二阶差商三阶差商三阶差商-2-112531721-2743-1-1ex24.mex23.m27Newton 插值插值公式公式Newton 插值公式由差商的定义可得由差商的定义可得12 n 11+ (x x0) 2+ + (

17、x x0)(x xn 1) n 1Nn(x)Rn(x)28Newton 插值插值公式公式 f (x) = Nn(x) + Rn(x) Nn(x) 是是 n 次多项式次多项式Nn(xi) = f (xi)，i = 0, 1, 2, , n重要性质重要性质Nn(x) 是是 f (x) 的的 n 次插值多项式次插值多项式其中其中29Newton / LagrangeNewton 插值多项式与 Lagrange 插值多项式f (x) 在在 x0 , x1 , , xn 上上的的 n 次插值多项式是唯一的！次插值多项式是唯一的！Nn(x) Ln(x)余项也相同余项也相同将将 x 看作节点看作节点30插值

18、举例插值举例例：例：已知函数已知函数 y = lnx 的函数值如下的函数值如下解解：取节点取节点 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.6202N

19、2(x) = -0.6931 + 1.8230(x-0.5) - 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) 的表达式非常复杂，能否找到一个的表达式非常复杂，能否找到一个简简单易算单易算的

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

21、可能地小。一致逼近一致逼近平方逼近平方逼近35函数逼近函数逼近 记记 Hn 为所有次数不超过为所有次数不超过 n 的多项式组的多项式组成的集合，给定函数成的集合，给定函数 f(x) Ca, b，若，若 P*(x) Hn 使得使得则称则称 P*(x) 为为 f(x) 在在 Ca, b 上的上的 最佳逼近多项式最佳逼近多项式最佳逼近最佳逼近最佳一致逼近最佳一致逼近36函数逼近函数逼近最小二乘拟合最小二乘拟合寻找寻找 P*(x) ，使得下面的离散，使得下面的离散 2-范数最小范数最小给定给定 f(x) Ca, b 的数据表的数据表xx0x1xnyy0y1yn最佳平方逼近最佳平方逼近37正交多项式正交

22、多项式定义定义设设 n(x) 是是首项系数不为首项系数不为 0 的的 n 次多项式次多项式，若，若则称则称 为为 a, b 上带权上带权 (x) 正交正交性质性质 1设设 是正交多项式族，是正交多项式族，Hn 为所有次数不超过为所有次数不超过 n 的多项式组成的线性空间，则的多项式组成的线性空间，则构成构成 Hn 的一组基的一组基称称 n(x) 为为 n 次正交多项式次正交多项式38最佳平方逼近最佳平方逼近设设 f(x) Ca, b， 0(x), 1(x), , n(x) Ca, b 线性线性无关，令无关，令求求 S*(x) ，使得使得S*(x) 称为称为 f(x) 在在 中的中的 最佳平方逼

23、近函数最佳平方逼近函数 其中其中39最佳平方逼近最佳平方逼近如何求如何求 S*(x) ？对任意对任意 S(x) ，可设可设 S(x) = a0 0 + a1 1 + + an n(x)则求则求 S*(x) 等价于求下面的多元函数的最小值点等价于求下面的多元函数的最小值点k = 0, 1, , n40最佳平方逼近最佳平方逼近即即k = 0, 1, , n法方程法方程G41求求 在在0, 1上的一次最佳平方逼近多项式上的一次最佳平方逼近多项式举例举例例：例：(教材教材68页，例页，例 6)解：解： S*(x) = 0.934 + 0.426 x42最佳平方逼近多项式最佳平方逼近多项式f(x) Ca

24、, b 在在 Hn 中的最佳平方逼近，记为中的最佳平方逼近，记为n 次最佳平方逼近多项式次最佳平方逼近多项式l 取取 Hn 的一组基：的一组基：1, x, x2, , xn ，则法方程为，则法方程为HHilbert 矩阵矩阵H 严重病态严重病态只适合求低只适合求低次最佳逼近次最佳逼近43正交函数作逼近正交函数作逼近若若 0, 1, , n 正交，则法方程的解为正交，则法方程的解为所以所以k = 0, 1, , nl 误差误差Bessel 不等式不等式44曲线拟合曲线拟合能否找到一个简单易算的能否找到一个简单易算的 p(x) ，使得，使得 f(x) p(x)已知已知 f(x) 在某些点的函数值：

25、在某些点的函数值：xx0x1xm f(x)y0y1ym但是但是(1) m 通常很大通常很大 (2) yi 本身是测量值，不准确，即本身是测量值，不准确，即 yi f (xi) 这时不要求这时不要求 p(xi) = yi , 而只要而只要 p(xi) yi 总体上尽可能小总体上尽可能小 45l 使使 最小最小l 使使 最小最小曲线拟合曲线拟合 p(xi) yi 总体上尽可能小总体上尽可能小 l 使使 最小最小q 常见做法常见做法太复杂太复杂 不可导，求不可导，求解困难解困难 最小二乘法：最小二乘法：目前最好的多项式曲线拟合算法目前最好的多项式曲线拟合算法46最小二乘最小二乘曲线拟合的最小二乘问题

26、曲线拟合的最小二乘问题l 这个问题实质上是最佳平方逼近问题的这个问题实质上是最佳平方逼近问题的离散形式离散形式。可以将求连续函数的最佳平方逼近函数的方法直接用可以将求连续函数的最佳平方逼近函数的方法直接用于求解该问题。于求解该问题。已知函数值表已知函数值表 ( xi , yi )，在函数空间在函数空间 中求中求 S*(x) ，使得，使得其中其中 i 是点是点 xi 处的权。处的权。47最小二乘求解最小二乘求解对任意对任意 S(x) = span 0, 1, , n，可设可设 S(x) = a0 0 + a1 1 + + an n(x)则求则求 S*(x) 等价于求下面的多元函数的最小值点等价于

27、求下面的多元函数的最小值点k = 0, 1, , n最小值点最小值点48最小二乘求解最小二乘求解( k = 0, 1, , n )这里的内积是这里的内积是离散带权内积离散带权内积，即，即，法方程法方程G法方程法方程49最小二乘求解最小二乘求解设法方程的解为：设法方程的解为： a0* , a1*, , an* , 则则 S*(x) = a0* 0 + a1* 1 + + an* n(x)结论结论S*(x) 是是 f(x) 在在 中的中的 最小二乘解最小二乘解50举例举例最小二乘问题中，如何选择最小二乘问题中，如何选择数学模型数学模型很重要，即如何选取很重要，即如何选取函数空间函数空间 = spa

28、n 0, 1, , n ，通常需要根据物理，通常需要根据物理意义，或所给数据的分布情况来选取合适的数学模型。意义，或所给数据的分布情况来选取合适的数学模型。51多项式拟合多项式拟合 Hn= span1, x, ., xn, 即即 i = xi, 则相应的法方程为则相应的法方程为此时此时 为为 f(x) 的的 n 次最小二乘次最小二乘拟合多项式拟合多项式多项式最小二乘曲线拟合多项式最小二乘曲线拟合52举例举例例：例：求下面数据表的二次最小二乘拟合多项式求下面数据表的二次最小二乘拟合多项式 得法方程得法方程xi00.250.500.751.00f (xi )1.00001.28401.64872.

29、11702.7183解：解：设二次拟合多项式为设二次拟合多项式为解得解得所以此组数据的二次最小二乘拟合多项式为所以此组数据的二次最小二乘拟合多项式为(1) 若题目中没有给出各点的权值若题目中没有给出各点的权值 i ，默认为默认为 i = 1 (2) 该方法不适合该方法不适合 n 较大时的情形较大时的情形 （病态问题）（病态问题）53第四章数值积分与数值微分计算方法54数值积分数值积分l 微积分基本公式：微积分基本公式：(3) f (x) 表达式未知表达式未知，只有通过测量或实验得来的数据表，只有通过测量或实验得来的数据表l 但是在许多实际计算问题中但是在许多实际计算问题中(2) F(x) 难求

30、！难求！甚至有时不能用初等函数表示。甚至有时不能用初等函数表示。 如如(1) F(x) 表达式较复杂表达式较复杂时，计算较困难。如时，计算较困难。如55几个简单公式几个简单公式l 矩形公式矩形公式l 梯形公式梯形公式l 抛物线公式抛物线公式q 基本思想：基本思想：56一般形式一般形式数值积分公式的一般形式数值积分公式的一般形式求积节点求积节点求积系数求积系数机械求积方法机械求积方法l 将定积分计算转化成被积函数的将定积分计算转化成被积函数的函数值函数值的计算的计算l 无需求原函数无需求原函数l 易于计算机实现易于计算机实现一般地，用一般地，用 f(x) 在在 a, b 上的一些离散点上的一些离

31、散点 a x0 x1 xn b 上的函数值的加权平均作为上的函数值的加权平均作为 f ( ) 的近似值，可得的近似值，可得57代数精度代数精度定义定义：如果对于所有次数不超过：如果对于所有次数不超过 m 的多项式的多项式 f (x) ，公式，公式精确成立，但对某个次数为精确成立，但对某个次数为 m +1 的多项式不精确成立，则称的多项式不精确成立，则称该求积公式具有该求积公式具有 m 次代数精度次代数精度l 将将 f (x) = 1, x, x2, , xm 依次代入，公式精确成立依次代入，公式精确成立;l 但对但对 f (x) = xm+1 不精确成立。即：不精确成立。即：( k = 0,

32、1, , m )代数精度的验证方法代数精度的验证方法58举例举例例：例：试确定系数试确定系数 Ai ，使得下面的求积公式具有尽可能高的使得下面的求积公式具有尽可能高的代数精度，并求出此求积公式的代数精度。代数精度，并求出此求积公式的代数精度。解：解：将将 f (x)1, x, x2 代入求积公式，使其精确成立，可得代入求积公式，使其精确成立，可得 解得解得 A0 =1/3, A1 =4/3, A2 =1/3。所以求积公式为。所以求积公式为易验证该公式对易验证该公式对 f (x)x3 也精确成立，但对也精确成立，但对 f (x)x4 不精不精确成立，所以此求积公式具有确成立，所以此求积公式具有

33、3 次代数精度。次代数精度。59插值型求积公式插值型求积公式设求积节点为：设求积节点为：a x0 x1 0, 总存在一算子范数总存在一算子范数 | | ，使得，使得 | | (A) + 90稳定性理论分析稳定性理论分析q 理论分析：理论分析：设设又又(1)(1)由于右端项的扰动而引起的解的变化由于右端项的扰动而引起的解的变化(2)(2)由于系数矩阵的扰动而引起的解的变化由于系数矩阵的扰动而引起的解的变化设设Ax = b 的的条件数矩阵矩阵A 的的条件数91稳定性理论分析稳定性理论分析定理：定理：考虑线性方程组考虑线性方程组 Ax=b，设，设 b 是精确的，是精确的，A 有有微小微小的变化的变化

34、 A，此时的解为，此时的解为 x + x ，则，则证明：证明：l 当当 A 充分小时，不等式右端约为充分小时，不等式右端约为设设结论结论92矩阵条件数矩阵条件数n 条件数与范数有关，常用的有条件数与范数有关，常用的有无穷范数无穷范数和和2-范数范数l Cond(A)2 称为称为谱条件数谱条件数，当，当 A 对称时有对称时有93举例举例例：例： 计算计算 Cond(A) 和和 Cond(A)2解：解：Cond(A) =|A-1| |A| 4 104Cond(A)2= max / min 4 104A 对称，且对称，且94第六章线性方程组的迭代解法计算方法95矩阵分裂迭代法矩阵分裂迭代法矩阵分裂迭

35、代法基本思想矩阵分裂迭代法基本思想Ax = bk = 0, 1, 2, 给定一个初始向量给定一个初始向量 x(0)，可得，可得 迭代格式迭代格式其中其中 B = M-1N 称为称为迭代矩阵迭代矩阵 A = M - NMx = Nx + bM 非奇异非奇异A 的一个的一个矩阵分裂矩阵分裂96收敛性分析收敛性分析定理定理：对任意初始向量对任意初始向量 x(0)，上述迭代格式收敛的充要条件是，上述迭代格式收敛的充要条件是证明：板书证明：板书定理定理：若存在算子范数若存在算子范数 | |，使得，使得 |B| 1，对任意的初始向量，对任意的初始向量 x(0)，上述迭代格式收敛。，上述迭代格式收敛。例例：

36、考虑迭代法考虑迭代法 x(k+1) = Bx(k) + f 的收敛性，其中的收敛性，其中基本收基本收敛定理敛定理充分条件充分条件97Jacobi 迭代迭代考虑线性方程组考虑线性方程组Ax = b其中其中 A=(aij)n n 非奇异，且对角线元素全不为非奇异，且对角线元素全不为 0。l 将将 A 分裂成分裂成 A = D - L- U， 其中其中98Jacobi 迭代迭代k = 0, 1, 2, 令令 M = D，N = L + U，可得，可得 雅可比雅可比 (Jacobi) 迭代方法迭代方法 Jacobi 迭代迭代l 迭代矩阵记为：迭代矩阵记为：l 分量形式：分量形式：i = 1, 2, ,

37、 n， k = 0, 1, 2, 99Gauss-Seidel 迭代迭代l 在计算在计算 时，如果用时，如果用 代替代替 ，则可能会得到更好的收敛效果。则可能会得到更好的收敛效果。100Gauss-Seidel 迭代迭代写成矩阵形式写成矩阵形式:此迭代方法称为此迭代方法称为 高斯高斯-塞德尔塞德尔 (Gauss-Seidel) 迭代法迭代法k = 0, 1, 2, 可得可得l 迭代矩阵记为：迭代矩阵记为：101SOR 迭代迭代l 为了得到更好的收敛效果，可在修正项前乘以一个为了得到更好的收敛效果，可在修正项前乘以一个 松弛因子松弛因子 ，于是可得迭代格式，于是可得迭代格式在在 G-S 迭代中迭

38、代中102SOR 迭代迭代写成矩阵形式写成矩阵形式:可得可得 SOR (Successive Over-Relaxation) 迭代方法迭代方法l 迭代矩阵记为：迭代矩阵记为：l SOR 的优点的优点：通过选取合适的：通过选取合适的 ，可获得更快的收敛速度，可获得更快的收敛速度l SOR 的缺点的缺点：最优参数最优参数 的的选取比较困难选取比较困难103l Jacobi 迭代收敛的迭代收敛的充要充要条件条件 (J)1l G-S 迭代收敛的迭代收敛的充要充要条件条件 (G)1l SOR 迭代收敛的迭代收敛的充要充要条件条件 (L )1收敛性收敛性收敛性定理收敛性定理l Jacobi 迭代收敛的迭

39、代收敛的充分充分条件条件 |J| 1l G-S 迭代收敛的迭代收敛的充分充分条件条件 |G| 1l SOR 迭代收敛的迭代收敛的充分充分条件条件 |L | 1104Jacobi、G-S 收敛性收敛性定理定理：若若 A 严格对角占优严格对角占优或或不可约弱对角占优不可约弱对角占优，则，则 A 非奇异非奇异定理定理：若若 A 严格对角占优严格对角占优或或不可约弱对角占优不可约弱对角占优，则，则 Jacobi 迭迭代和代和 G-S 迭代均收敛迭代均收敛 定理定理：若若 A 对称，且对角线元素均大于对称，且对角线元素均大于 0，则，则(1)Jacobi 迭代收敛的充要条件是迭代收敛的充要条件是 A 与

40、与 2D-A 均正定；均正定；(2)G-S 迭代收敛的充要条件是迭代收敛的充要条件是 A 正定。正定。105SOR 收敛性收敛性定理定理：若若 SOR 迭代收敛，则迭代收敛，则 0 2。l SOR 收敛的必要条件收敛的必要条件定理定理：若若 A 对称正定，且对称正定，且 0 2，则则 SOR 迭代收敛。迭代收敛。l SOR 收敛的充分条件收敛的充分条件定理定理：若若 A 严格对角占优或不可弱约对角占优，且严格对角占优或不可弱约对角占优，且 0 1，则则 SOR 迭代收敛。迭代收敛。106举例举例例例：设设 ，给出，给出 Jacobi 和和 G-S 收敛的充要条件收敛的充要条件 解：解：A 对称

41、，且对角线元素均大于对称，且对角线元素均大于 0，故，故 (1) Jacobi 收敛的充要条件是收敛的充要条件是 A 和和 2D-A 均正定均正定(2) G-S 收敛的充要条件是收敛的充要条件是 A 正定正定A 正定正定2D-A 正定正定Jacobi 收敛的充要条件是：收敛的充要条件是：-0.5a0.5G-S 收敛的充要条件是：收敛的充要条件是：-0.5a1107举例举例解法二：解法二：Jacobi 的迭代矩阵为的迭代矩阵为设设 是是 J 的特征值，则由的特征值，则由 det( I - J) = 0 可得可得( - a)2 ( +2a) = 0Jacobi 收敛的充要条件是收敛的充要条件是 (

42、J)1 | |1，即即 -0.5a0.5108收敛速度收敛速度定义定义：迭代格式迭代格式 x(k+1) = Bx(k) + f 的平均收敛速度为的平均收敛速度为渐进收敛速度为渐进收敛速度为l (B) 越小，收敛越快越小，收敛越快109第七章非线性方程(组)的数值解法计算方法110不动点迭代不动点迭代q 基本思想基本思想l 构造构造 f (x) = 0 的一个等价方程：的一个等价方程： (x) 的不动点的不动点f (x) = 0x = (x)等价变换等价变换f (x) 的零点的零点111不动点迭代不动点迭代q 具体过程具体过程l 任取一个迭代初始值任取一个迭代初始值 x0 ，计算，计算得到一个迭

43、代序列：得到一个迭代序列： x0，x1，x2，. . . ，xn，. . . k = 0, 1, 2, . . 几何含义：几何含义：求曲线求曲线 y = (x) 与直线与直线 y = x 的交点的交点112连续性分析连续性分析设设 (x) 连续，若连续，若 收敛，即收敛，即 ，则，则即即q 收敛性分析收敛性分析性质：性质：若若 ，则不动点迭代，则不动点迭代收敛收敛，且，且 x* 是是 f(x)=0 的解；否则迭代法的解；否则迭代法发散发散。113解的存在唯一性解的存在唯一性定理定理：设设 (x) Ca,b 且满足且满足证明：板书证明：板书(1)对任意的对任意的 x a,b 有有 (x) a,b

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

45、收敛性若若 (x) C1a,b 且对任意且对任意 x a,b 有有 | (x)| L1则上述定理中的结论成立。则上述定理中的结论成立。收敛性结论表明：收敛性结论表明：收敛性与初始值的选取无关收敛性与初始值的选取无关全局收敛全局收敛116举例举例例：例：求求 f(x) = x3 x 1=0 在区间在区间 1, 2 中的根中的根 (1)(2)ex71.m117局部收敛局部收敛定义定义：设设 x* 是是 (x) 的不动点，若存的不动点，若存在在 x* 的某个的某个 -邻域邻域 U(x*) =x*- , x* + ，对任意，对任意 x0 U(x*)，不动点迭代，不动点迭代 xk+1 = (xk) 产生

46、的点列都收敛到产生的点列都收敛到 x*，则称该迭代，则称该迭代局部收敛。局部收敛。定理：定理：设设 x* 是是 (x) 的不动点，若的不动点，若 (x) 在在 x* 的某个邻域的某个邻域内连续，且内连续，且 | (x*)| 0，则称该迭代为，则称该迭代为 p 阶收敛阶收敛。(1)当当 r =1 时称为时称为线性收敛线性收敛，此时，此时 C 1 时称为时称为超线性收敛超线性收敛l 二分法是线性收敛的二分法是线性收敛的l 若若 (x*) 0，则，则不动点迭代不动点迭代 xk+1 = (xk) 线性收敛线性收敛119收敛速度收敛速度定理：定理：设设 x* 是是 (x) 的不动点的不动点，若若 (p)

47、(x) 在在 x* 的某的某邻域内连续，且邻域内连续，且则迭代则迭代 xk+1 = (xk) 是是 p 阶收敛的。阶收敛的。证明：板书证明：板书120举例举例例：例：求求 f(x) = x2 - 3=0 的正根的正根 (1)ex72.m(2)(3)二次收敛二次收敛局部收敛局部收敛121Newton 法法q 基本思想基本思想将非线性方程将非线性方程线性化线性化l 设设 xk 是是 f (x)=0 的近似根，将的近似根，将 f(x) 在在 xk 处处 Taylor 展开展开令：令：条件：条件： f(x) 0122Newton 法法xyx*xkxk+1123Newton 法法算法算法 ：( Newt

48、on 法法 )(1) 任取迭代初始值任取迭代初始值 x0(2) 对对 k = 1, 2, . , maxit，计算，计算判断收敛性，若收敛，则停止计算，输出近似解判断收敛性，若收敛，则停止计算，输出近似解124收敛性收敛性 k = 0, 1, 2, . . . l 迭代函数迭代函数牛顿法至少二阶牛顿法至少二阶局部收敛局部收敛125举例举例例：例：用用 Newton 法求法求 f(x) = x2 C=0 的正根的正根, 并验证这一并验证这一方法的二阶收敛性方法的二阶收敛性解：解：对任意对任意 x00，总有总有 |q|1，即即牛顿法收敛牛顿法收敛126举例举例二阶收敛二阶收敛关于二次收敛性，事实上

49、关于二次收敛性，事实上第第 八八 章章矩阵特征值计算矩阵特征值计算127128特征值估计与扰动特征值估计与扰动 定义定义1 设设 n 阶矩阵阶矩阵 A=(aij)，令，令 (1) ； (2) 集合集合 称为称为复平面上以复平面上以aii为圆心，以为圆心，以ri为半径的为半径的n阶矩阵阶矩阵A的的n个个格什戈格什戈林林(Gerschgorin)圆盘圆盘.129 定理定理5 (Gerschgorin圆盘定理圆盘定理) 特别地，如果特别地，如果A的一个圆盘的一个圆盘Di是与其它圆盘分离是与其它圆盘分离(即即孤立孤立圆盘圆盘)，则，则Di中精确地包含中精确地包含A的一个特征值的一个特征值. (1) 设

50、设n阶矩阵阶矩阵A(aij)，则，则A的每一个特征值必属于下面某的每一个特征值必属于下面某个圆盘之中个圆盘之中 (2) 如果如果A有有m个个圆盘圆盘组成一个连通的并集组成一个连通的并集S，且，且S与余下与余下n- -m个个圆盘圆盘是分离的，则是分离的，则S内恰包含内恰包含A的的m个特征值个特征值.或者说或者说 A的特征值都在的特征值都在n个圆盘的个圆盘的并集并集中中.130 例例1 估计矩阵估计矩阵A的特征值范围，其中的特征值范围，其中解解 矩阵矩阵A的的3个圆盘为个圆盘为 由定理由定理8，可知，可知A的的3个特征值位于个特征值位于3个圆盘的并集中，由个圆盘的并集中，由于于D1是孤立圆盘，所以

51、是孤立圆盘，所以D1内恰好包含内恰好包含A的一个特征值的一个特征值 1(为实为实特征值特征值)，即，即A的其它两个特征值的其它两个特征值 2, 3包含在包含在D2, D3的并集中的并集中.131现在取对角阵现在取对角阵做相似变换做相似变换 矩阵矩阵A1的的3个圆盘为个圆盘为132第第 九九 章章常微分方程初值问题数值解法常微分方程初值问题数值解法133初值问题初值问题Euler法法局部截断误差：局部截断误差：欧拉法具有欧拉法具有 1 阶精度阶精度隐式隐式后退的后退的Euler法法显式显式局部截断误差：局部截断误差：1阶阶精度精度134梯形方法梯形方法隐式单步法，用迭代法求解隐式单步法，用迭代法

52、求解. . 迭代公式迭代公式135梯形法的局部误差估计梯形法的局部误差估计梯形方法是梯形方法是2阶的，其局部误差主项为阶的，其局部误差主项为136改进的欧拉公式改进的欧拉公式校正一次校正一次迭代一次得迭代一次得 ，这个结果称，这个结果称 校正值校正值. .Step 1: 先用先用显式显式欧拉公式作欧拉公式作预测预测，算出，算出),(1nnnnyxfhyy+ += =+ +Step 2: 再将再将 代入代入隐式隐式梯形公式梯形公式1+ +ny137 预测预测- -校正系统：校正系统： 预测预测校正校正 平均化形式平均化形式 138 例例2 用改进的欧拉方法求解初值问题（用改进的欧拉方法求解初值问题（2.22.2）. .（2.2） 解解 改进的欧拉公式为改进的欧拉公式为 仍取仍取 ，计算，计算结果见表结果见表9-2. 9-2. 改进欧拉法明显改进欧拉法明显改善了精度改善了精度. .