数值分析全册完整课件.ppt

1、 计计 算算 方方 法法 数值分析全册完整课件 教材和参考书教材和参考书 教材： 数值分析，电子科技大学应用数学学院，钟尔杰， 黄廷祝主编，高等教育出版社 参考书：参考书： 数值方法（数值方法（MATLAB版）（第三版），版）（第三版），John H. Mathews,Kurtis D. Fink 著，电子工业出版社；著，电子工业出版社； 数值分析（第四版），李庆扬，王能超，易大义编，清华数值分析（第四版），李庆扬，王能超，易大义编，清华 大学出版社；大学出版社； 计算方法（第二版），邓建中，刘之行，西安交通大学出计算方法（第二版），邓建中，刘之行，西安交通大学出 版社；版社； 数值分析与实验

2、学习指导，蔡大用编，清华大学出版社。数值分析与实验学习指导，蔡大用编，清华大学出版社。 教学要求教学要求 了解计算方法研究的主要内容； 掌握计算方法的基本概念和基本原理，进一步提掌握计算方法的基本概念和基本原理，进一步提 高抽象思维和逻辑推理的能力；高抽象思维和逻辑推理的能力； 掌握数值计算的各种方法（或算法）的基本思掌握数值计算的各种方法（或算法）的基本思 想，进一步提高数值计算能力想，进一步提高数值计算能力 ； 能够与实际问题相结合，利用所学算法解决一些能够与实际问题相结合，利用所学算法解决一些 实际的数学模型问题实际的数学模型问题 ； 能够利用数学软件编程实现所学算法（可用能够利用数学软

3、件编程实现所学算法（可用 MATLAB，MATHEMATICA等）。等）。 课程内容 引论（误差、有效数字等） 非线性方程求根 线性方程组的直接解法 线性方程组的迭代解法 数值揑值方法 数据拟吅方法 数值积分不数值微分 常微分方程的数值解法 说明：说明： 学时： 授课48上机16 （课程设计） 成绩评定： 期末考试（60%） 半期考试（20%） 平时成绩（20%） 第一章第一章 引论引论 第一章第一章 引论引论 1.1 计算方法研究的对象不特点 1.2 数值计算的误差不有效数字 1.3 数值运算的误差估计 1.4 数值计算中的一些基本原则 计算方法是做什么用的？ 1.1 计算方法研究的对象不特

4、点 计算计算 方法方法 输入复杂问题或运算输入复杂问题或运算 .),(,)( ,ln, xf dx d dxxf bxAxax b a x 计算机计算机 近似解近似解 研究对象：用计算机求解各种数学问题的数值计算 方法及其理论不软件实现。 计算机解决科学计算的过程：计算机解决科学计算的过程： 实际问题实际问题数学模型数学模型数值计算方法数值计算方法程序设计程序设计结果结果 实际上述过程可分两部分：实际上述过程可分两部分： 1.由实际问题应用有关知识和数学理论建立模型，由实际问题应用有关知识和数学理论建立模型， -应用数学任务应用数学任务 2.由数学模型提出求解的数值计算方法直到编程出结果，由数

5、学模型提出求解的数值计算方法直到编程出结果， -计算数学任务计算数学任务 计算方法是计算数学的一个主要部分，研究的即是后半 部分，将理论与计算相结合。 特点: 面向计算机，提供切实可行的算法； 有可靠的理论分析，能达到精度要求，保证近 似算法的收敛性和数值稳定性； 要有好的计算复杂性，节省时间及存储量； 有数值实验，证明算法有效。 算法基本结构：算法基本结构：顺序，分支，循环顺序，分支，循环 算法描述：算法描述：程序或流程图程序或流程图 常采用的处理方法： 构造性方法 离散化方法 递推化方法 迭代法 近似替代方法 以直代曲法 化整为零的处理方法 外推法 微积分的若干定理： 罗尔定理和微分中值定

6、理； 介值定理及推论； 泰勒公式（一元、二元）； 积分中值定理； 高等代数的若干概念和结论：高等代数的若干概念和结论： 多项式；多项式； 行列式；行列式； 初等矩阵；初等矩阵； 特殊三角阵。特殊三角阵。 数学基础：数学基础： 1.2 数值计算的误差与有效数字数值计算的误差与有效数字 1.2.1 误差来源与分类误差来源与分类: 按来源分，分为固有误差和计算误差。按来源分，分为固有误差和计算误差。 固有误差固有误差：建立模型时已存在。：建立模型时已存在。 模型误差模型误差：建立数学模型时所引起的误差；建立数学模型时所引起的误差； 观测误差观测误差：测量工具的限制或在数据的获取时测量工具的限制或在数

7、据的获取时 随机因素所引起的物理量的误差。随机因素所引起的物理量的误差。 计算误差计算误差：计算过程中出现的误差。：计算过程中出现的误差。 截断误差截断误差：用数值方法求解数学模型时，用简单用数值方法求解数学模型时，用简单 代替复杂代替复杂, ,或者用有限过程代替无限过程所引起的或者用有限过程代替无限过程所引起的 误差；误差； . ! . ! 2 1 2 n xx xe n x ! . ! 2 1)( 2 n xx xxS n n 10 , )!1( )( 1 x n n x e n x xSe 例如：例如： 由泰勒余项定理得其截断误差为：由泰勒余项定理得其截断误差为： 舍入误差舍入误差：计算

8、机表示的数的位数有限，通常用计算机表示的数的位数有限，通常用 四舍五入的办法取近似值，由此引起的误差。四舍五入的办法取近似值，由此引起的误差。 14159265. 3 414213562. 12 166666666. 0 6 1 ! 3 1 1415927. 3 4142136. 12 16666667. 0 ! 3 1 将将 作作Taylor展开后再积分展开后再积分 2 x e . 9 1 !4 1 7 1 !3 1 5 1 !2 1 3 1 1 ). !4!3!2 1( 1 0 864 2 1 0 dx xxx xdxe 2 x S4 R4 743002401033301 42 1 10

9、1 3 1 1 4 .S 0010200050. 舍入误差舍入误差 21 0 0 0050 0010 006 -x edx. 总体误差的的 （= 0.747） , 1 0 4 Sdxe 2 x 取取 则则 . 11 1 !5 1 9 1 !4 1 4 R 称为称为截断误差截断误差 0050 9 1 !4 1 4 .R 这里这里 dxe x 1 0 2 例：例：近似计算近似计算 解：解： 例：蝴蝶效应 纽约的一只蝴蝶翅膀一拍， 风和日丽的北京就刮起台风来了？！ NY BJ 误差的传播与积累：误差的传播与积累： 该问题是一病态问题。该问题是一病态问题。 营长对值班军官营长对值班军官: : 明晚大约

10、明晚大约 8 8点钟左右，哈雷彗星将可点钟左右，哈雷彗星将可 能在这个地区看到，这种彗星每隔能在这个地区看到，这种彗星每隔 7676年才能看见一次。年才能看见一次。 命令所有士兵着野战服在操场上集合，我将向他们解释命令所有士兵着野战服在操场上集合，我将向他们解释 这一罕见的现象。如果下雨的话，就在礼堂集合，我为这一罕见的现象。如果下雨的话，就在礼堂集合，我为 他们放一部有关彗星的影片。他们放一部有关彗星的影片。 值班军官对连长值班军官对连长: : 根据营长的命令，明晚根据营长的命令，明晚8 8点哈雷彗星点哈雷彗星 将在操场上空出现。如果下雨的话，就让士兵穿着野战服将在操场上空出现。如果下雨的话

11、，就让士兵穿着野战服 列队前往礼堂，这一罕见的现象将在那里出现。列队前往礼堂，这一罕见的现象将在那里出现。 据说，美军据说，美军 1910 1910 年的一次部队的命令传递是这样的年的一次部队的命令传递是这样的: : 班长对士兵班长对士兵: : 在明晚在明晚8 8点下雨的时候，著名的点下雨的时候，著名的7676岁哈雷岁哈雷 将军将在营长的陪同下身着野战服，开着他那将军将在营长的陪同下身着野战服，开着他那“彗星彗星”牌牌 汽车，经过操场前往礼堂。汽车，经过操场前往礼堂。 连长对排长连长对排长: : 根据营长的命令，明晚根据营长的命令，明晚8 8点，非凡的哈雷点，非凡的哈雷 彗星将身穿野战服在礼堂

12、中出现。如果操场上下雨，营长彗星将身穿野战服在礼堂中出现。如果操场上下雨，营长 将下达另一个命令，这种命令每隔将下达另一个命令，这种命令每隔7676年才会出现一次。年才会出现一次。 排长对班长排长对班长: : 明晚明晚8 8点，营长将带着哈雷彗星在礼堂中点，营长将带着哈雷彗星在礼堂中 出现，这是每隔出现，这是每隔 7676年才有的事。如果下雨的话，营长将年才有的事。如果下雨的话，营长将 命令彗星穿上野战服到操场上去。命令彗星穿上野战服到操场上去。 1.2.2 误差与有效数字误差与有效数字: 定义定义1.1 设设x*为某一数据的准确值，为某一数据的准确值，x为为x*的一个近的一个近 似值，称似值

13、，称e(x)=x-x*(近似值准确值近似值准确值)为近似值为近似值x的的绝对绝对 误差误差，简称误差。，简称误差。 e(x) 可正可负，当可正可负，当e(x) 0时近似值偏大，叫强近似值；当时近似值偏大，叫强近似值；当e(x) 0时近似值偏小时近似值偏小，叫弱近似值。叫弱近似值。 由于由于x*通常无法确定，只能估计其绝对误差值通常无法确定，只能估计其绝对误差值 不超过某整数不超过某整数 (x)，即即 )(| )(|xxxxe 则称则称 (x) 为为绝对误差限绝对误差限。 1. 绝对误差与相对误差绝对误差与相对误差： )()(xxxxx )( * xxx 由上式得由上式得 可知可知x*的范围。或

14、记为的范围。或记为 但误差但误差e(x)并不足以刻划并不足以刻划x的精度。的精度。 如：如： x*=152, x=15, (x) =2; y*=10005, y=1000, (y)=5 因此考虑精度时除看误差大小外，还应考虑精确值本因此考虑精度时除看误差大小外，还应考虑精确值本 身的大小，故引入相对误差概念。身的大小，故引入相对误差概念。 定义定义1.2 设设x*为某一数据的准确值，为某一数据的准确值，x为为x*的一个近似的一个近似 值，称值，称 )0(, )( )( * x x xx x xe xer 为近似值为近似值x的的相对误差相对误差。 实际计算时，由于实际计算时，由于x*不知，通常取

15、不知，通常取 x xx x xe xer * )( )( 如果存在一适当小的如果存在一适当小的正数正数 r ， ，使得使得 rr x xx x xe xe )( )( 则称则称 r为 为相对误差限相对误差限。 例：例：x=15, (x) =2， r( (x)=2/15=13.33% )=2/15=13.33%； y=1000, (y)=5 , r( (y)=5/1000=0.5% )=5/1000=0.5% 2. 有效数字：有效数字： 定义定义1.3 若近似值若近似值x的误差限是某一位的半个单位，的误差限是某一位的半个单位， 该位到该位到x的第一位非零数字共有的第一位非零数字共有n位，就说位，

16、就说x有有n位有位有 效数字，效数字，x可表示为可表示为 m n aaax10. 0 21 其中，其中， a1, a2, , an 都是都是 0 9 中的任一整数，中的任一整数， 但但 a10。 其绝对误差限满足：其绝对误差限满足： nm xxxe 10 2 1 )( 如：如：x*= =3.14159265 （1）取）取x3.14，则则m=1， 31 10 2 1 005. 0002. 0 xx 即即n=3，有三位有效数字；有三位有效数字； （2）取）取x=3.1416，则则m=1， 51 10 2 1 00005. 0000008. 0 xx 即即n=5，有有5位有效数字。位有效数字。 定理

17、定理1：设近似数设近似数x表示为表示为 m n aaax10. 0 21 若若x具有具有n位有效数字，则其相对误差限为位有效数字，则其相对误差限为 )1( 1 10 2 1 )( n r a x 反之，若反之，若x的相对误差限为的相对误差限为 )1( 1 10 )1(2 1 )( n r a x 则则x至少具有至少具有n位有效数字。位有效数字。 例例1. 某零件质量取决于零件某参数某零件质量取决于零件某参数x，设参数标定值设参数标定值 为为1个单位，在生产过程中允许参数与标定值间有一定个单位，在生产过程中允许参数与标定值间有一定 误差，据此将零件分成误差，据此将零件分成A、B、C三等，等级由相

18、对误三等，等级由相对误 差限决定，差限决定，A：1%，B：5 %，C：10 %，试确定三个试确定三个 等级的零件参数允许变化的范围。等级的零件参数允许变化的范围。 解解 x*=1， 由由 r x xx 得得 故故 )1 (*)1 (* rr xxx 将三个相对误差限分别带入，得范围如下：将三个相对误差限分别带入，得范围如下： A：x 0.99,1.01 B：x 0.95,0.99)U( 1.01,1.05 C：x 0.9,0.95)U(1.05,1.1 rr x x 1 * 例例2. 测量一物体的长度为测量一物体的长度为954cm，问测量数据的相对问测量数据的相对 误差限多大？误差限多大？ 解

19、解 因因实际问题所截取的近似数，其绝对误差限一般实际问题所截取的近似数，其绝对误差限一般 不超过最小刻度的半个单位不超过最小刻度的半个单位， 故当故当x=954cm时，有时，有 (x)0.5cm， 而而x的相对误差的相对误差 er(x) 0.5/954=0.0005241.0.00053=0.053 % 故故 r( (x)= )=0.053 %. 例例3. 200.1%要使的相对误差不超过，应取 几位有效数字？ 解解: . 420 1 a的首位数是 .20位有效数字有的近似值设nx * 1 * 1 |1 |( )|10 |2 n r xx ex xa 则由定理则由定理1，相对误差满足，相对误差

20、满足 001. 010 42 1 1 n 097. 3n 即应取即应取4位有效数字，近似值的误差不超过位有效数字，近似值的误差不超过0.1%. 1.3 数值运算的误差估计 1. 函数运算的误差估计：函数运算的误差估计： 设设y=f(x)为一元函数，自变量准确值为一元函数，自变量准确值x*，对应函数准确对应函数准确 值值y*=f(x*)，x误差为误差为e(x)，误差限为误差限为 (x)，函数近似值函数近似值 误差误差e(y)，误差限为误差限为 (y)。则（可由则（可由Taylor公式推得）公式推得） )(| )( |)(xxfy )( | )(| | )( | )(x xf xxf y rr 对

21、于多元函数对于多元函数 ),( 21n xxxfz 设准确值设准确值 ),( * 2 * 1 * n xxxfz 由多元函数由多元函数Taylor公式，可得误差估计：公式，可得误差估计： 1 ( )() n k k k f zx x 相对误差限为：相对误差限为： 1 () ( ) n rk rk k k xf zx xz 2. 算术运算的误差估计：算术运算的误差估计： 两个近似数两个近似数x1, x2，其误差限分别为其误差限分别为 (x1)， (x2)，它它 们进行加、减、乘、除运算得到的误差限分别为：们进行加、减、乘、除运算得到的误差限分别为： )()()( 2121 xxxx )()()(

22、 122121 xxxxxx 2 2 1221 2 1 )()( )( x xxxx x x 例例4: 设设a=2.31,b=1.93,c=2.24都是三位有效数字的近似数，令都是三位有效数字的近似数，令 p=a+bc，求求 (p)和和 r( (p p) )， ，并判断并判断p p有几位有效数字。有几位有效数字。 解解 由题知，由题知， (a) = (b) = (c)=0.005 (p)= (a)+ (bc) (a)+|b| (c)+|c| (b) =0.005+1.93 0.005+2.24 0.005=0.02585 p=a+bc=2.31+1.93 2.24=6.6332 又又 故故 r

23、( (p p)= )= (p)/|p| 0.02585/6.6332 0.0039=0.39% 因为因为 (p) 0.025850.05=1/2 101-2 所以所以 p=6.6332中只有两位有效数字。中只有两位有效数字。 1. 避免除数的绝对值进小亍被除数的绝对值； 2. 避免两个相近的数相减； 3. 防止大数“吃掉”小数现象； 4. 简化计算步骤，减少运算次数； 5. 选用数值稳定性好的算法。 1.4 数值运算中的一些基本原则 1. 避免除数的绝对值远小于被除数的绝对值；避免除数的绝对值远小于被除数的绝对值； 设设 )0( x x y z若若|x|x2|xn| |，应按绝对值由小到大的顺

24、，应按绝对值由小到大的顺 序累加。序累加。 例例 计算方程计算方程 010)110( 992 xx 的根。的根。 算法一：算法一： 利用求根公式利用求根公式 a acbb x 2 4 2 在计算机内，在计算机内， 109存为存为0.1 1010 ，1存为存为0.1 101。做加做加 法时，两加数的指数先向大指数对齐，再将浮点部分相法时，两加数的指数先向大指数对齐，再将浮点部分相 加。加。 即即1 的指数部分须变为的指数部分须变为1010 ，则：，则：1 = 0.0000000001 1010 ，取单精度时就成为：，取单精度时就成为： 109 +1=0.10000000 1010 +0.0000

25、0000 1010 =0.10000000 1010 0 2 4 ,10 2 4 2 2 9 2 1 a acbb x a acbb x 算法二：算法二： 先解出先解出 9 2 1 10 2 4)( a acbbsignb x 再利用再利用 1 10 10 9 9 1 221 xa c x a c xx 例例2（思考题）：（思考题）： 按从小到大、以及从大到小的顺序分别计算按从小到大、以及从大到小的顺序分别计算 1 + 2 + 3 + + 40 + 109 4. 简化计算步骤，减少运算次数；简化计算步骤，减少运算次数； （即减少计算工作量）（即减少计算工作量） 如：如： 计算计算 01 1 1

26、 )(axaxaxaxP n n n nn 若直接求和，计算第若直接求和，计算第k项时需项时需n-k+1次乘法，故共需次乘法，故共需 n(n+1)/2次“”和次“”和n次“”。次“”。 若将公式改写为：若将公式改写为： 0121 )()(aaaaxaxxxxP nnnn 则只需则只需n次“”，次“”，n次“”，即次“”，即秦九韶算法秦九韶算法。 5. 选用数值稳定性好的算法。选用数值稳定性好的算法。 将输入数据有误差，但在运算过程中舍入误差不增长将输入数据有误差，但在运算过程中舍入误差不增长 的算法称的算法称数值稳定的数值稳定的，否则是，否则是数值不稳定的数值不稳定的。 只有数值稳定的数值方法

27、才能给出可靠的计算结果。只有数值稳定的数值方法才能给出可靠的计算结果。 例：例： 设有递推关系：设有递推关系： 110 1 nn yy(n=1,2,) 若取若取 41. 12 0 y （三位有效数字）（三位有效数字） 试问计算到试问计算到y10时误差有多大？时误差有多大？ 解：解： 因因 41.1,2 0 * 0 yy 而而 2* 00 10 2 1 yy 1010110110 * 00 * 00 * 11 yyyyyy 2* 11 * 11 * 22 1010110110yyyyyy 于是有于是有 类推，有类推，有 10* 1010 10 yy 即计算到即计算到y10，其误差限为，其误差限为

28、 1010 ，亦即若在，亦即若在y0处有误差处有误差 限为限为 ，则，则y10的误差限将扩的误差限将扩 大大1010 倍，可见这个计算过倍，可见这个计算过 程是不稳定的。程是不稳定的。 P1718. 习题一：1，2，3，4，5，8。 本章作业 第二章第二章 非线性方程的求根方法非线性方程的求根方法 第二章第二章 非线性方程的求根方法非线性方程的求根方法 引言 方程求根的二分法 迭代法及其收敛性 Newton迭代法 方程是在科学研究中丌可缺少的工具； 方程求解是科学计算中一个重要的研究对象； 几百年前就已经找到了代数方程中二次至四次方程 的求解公式； 但是，对亍更高次数的代数方程目前仍无有效的精

29、 确解法； 对亍无规徇的非代数方程的求解也无精确解法； 因此，研究非线性方程的数值解法成为必然。 2.1 引言 非线性方程的一般形式：非线性方程的一般形式： f(x)=0 代数方程：代数方程： f(x)=a0+a1x+anxn （an 0） 超越方程超越方程 ：f(x)中含三角函数、指数函数、或其中含三角函数、指数函数、或其 他超越函数。他超越函数。 用数值方法求解非线性方程的步骤：用数值方法求解非线性方程的步骤： （1）找出隔根区间；（只含一个实根的区间称隔根）找出隔根区间；（只含一个实根的区间称隔根 区间）区间） （2）近似根的精确化。从隔根区间内的一个或多个）近似根的精确化。从隔根区间内

30、的一个或多个 点出发，逐次逼近，寻求满足精度的根的近似值。点出发，逐次逼近，寻求满足精度的根的近似值。 2.2 方程求根的二分法 定理定理1（介值定理）设函数（介值定理）设函数f(x)在区间在区间a,b连续，连续， 且且f(a)f(b)0，则，则x*在在x0右侧，令右侧，令a1=x0， b1=b; （2）若）若f(x0)f(a)0，则，则x*在在x0左侧，令左侧，令a1=a， b1= x0。 。 )( 2 1 abab k kk 以以a1, b1为新的隔根区间，且仅为为新的隔根区间，且仅为a, b的一半，对的一半，对 a1, b1重复前过程，得新的隔根区间重复前过程，得新的隔根区间a2, b2

31、， 如此二分下去，得一系列隔根区间：如此二分下去，得一系列隔根区间： a, b a1, b1 a2, b2 ak, bk 其中每个区间都是前一区间的一半，故其中每个区间都是前一区间的一半，故ak, bk 的长度：的长度： 当当k趋于无穷时趋于趋于无穷时趋于0。 即若二分过程无限继续下去，这些区间最后必收敛于即若二分过程无限继续下去，这些区间最后必收敛于 一点一点x*，即方程的根。，即方程的根。 二分法性质： f(an) f(bn)0; bn an = (b a)/ 2n 实际计算中，若给定充分小的正数实际计算中，若给定充分小的正数 0和允许误差和允许误差 限限 1，当，当|f(xn)| 0或或

32、bn- an 1时，均可取时，均可取x* xn。 每次二分后，取有根区间的中点每次二分后，取有根区间的中点xk= (ak+bk) /2作作 为根的近似值，则可得一近似根序列：为根的近似值，则可得一近似根序列： x0, x1, x2, 该序列必以根该序列必以根x*为极限。为极限。 定理2 设x*为方程f(x)=0在a, b内唯一根，且f(x) 满足f(a)f(b)0，则由二分法产生的第n个区间an, bn 的中点xn满足丌等式 1 22 * n nn n abab xx 1 2 * n n ab xx 证明：证明： 计算过程简单，收敛性可保证； 对函数的性质要求低，只要连续即可。 收敛速度慢；

33、丌能求复根和重根； 调用一次求解一个a, b间的多个根无法求得。 二分法求解非线性方程的优缺点： 丌动点迭代法 丌动点的存在性不迭代法的收敛性 迭代收敛的加速方法 2.3 迭代法及其收敛性 迭代法的基本思想： 迭代法是一种逐次逼近的方法，用某个固定公式迭代法是一种逐次逼近的方法，用某个固定公式 反复校正根的近似值，使之逐步精确化，最后得到反复校正根的近似值，使之逐步精确化，最后得到 满足精度要求的结果。满足精度要求的结果。 例：求方程例：求方程 x3-x-1=0 在在 x=1.5 附近的一个根。附近的一个根。 解：将所给方程改写成解：将所给方程改写成 3 1xx 假设初值假设初值x0=1.5是

34、其根，代入得是其根，代入得 35721. 115 . 11 3 3 01 xx x1x0，再将，再将x1代入得代入得 33086. 1135721. 11 3 3 12 xx x2x1，再将，再将x2代入得代入得 32588. 1133086. 11 3 3 23 xx 如此下去，这种逐步校正的过程称为如此下去，这种逐步校正的过程称为迭代过程迭代过程。 这里用的公式称为这里用的公式称为迭代公式迭代公式，即，即 3 1 1 kk xxk=0,1,2, 迭代结果见下表：迭代结果见下表： k xk k xk 0 1 2 3 4 1.5 1.35721 1.33086 1.32588 1.32494

35、5 6 7 8 1.32476 1.32473 1.32472 1.32472 仅取六位数字，仅取六位数字，x7与与x8相同，即认为相同，即认为x8是是 方程的根。方程的根。 x*x8=1.32472 2.3.1 丌动点迭代法 将连续函数方程将连续函数方程f(x)0改写为等价形式：改写为等价形式：x= (x) 其中其中 (x)也是连续函数，称为迭代函数。也是连续函数，称为迭代函数。 不动点不动点：若：若x*满足满足f(x*)=0，则，则x*= (x*)；反之，若；反之，若 x*= (x*) ，则，则f(x*)=0 ，称，称x*为为 (x)的一个不动点。的一个不动点。 不动点迭代不动点迭代： )

36、( 1kk xx (k=0,1,) 若对任意若对任意 x0 a, b，由上述迭代得序列，由上述迭代得序列xk，有极限，有极限 *limxxk k 则称迭代过程则称迭代过程收敛收敛，且，且x*= (x*)为为 (x)的不动点。的不动点。 )(xx )(xy xy x2 x1 x0 y = x )(xy 几何意义：几何意义： 但迭代法并不总令人满意，如将前述方程但迭代法并不总令人满意，如将前述方程x3-x- 1=0改写为另一等价形式：改写为另一等价形式： 1 3 xx 1 3 1 kk xx 此时称迭代过程此时称迭代过程发散发散。 则有则有x1=2.375， x2=12.396，x3=1904,

37、结果越来越大。结果越来越大。 仍取初值仍取初值x0=1.5， 建迭代公式：建迭代公式： 012 *xxxxO )(xy xy 0231 *xxxxxO )(xy xy 收敛收敛 附近较平缓在 *)(xx 2013 *xxxxxO )(xy xy * 012 xxxxO )(xy xy 发散发散 附近较陡峭在 *)(xx 定理3（存在性） 设 (x) Ca, b且满足 以下两个条件： （1）对亍仸意x a, b，有a (x)b； （2 2）若 (x)在a, b一阶连续，且存在常 数0 0L1，使得对仸意x a, b，成立 | (x)| L 则 (x)在a, b上存在唯一的丌动点x*。 2.3.2

38、 丌动点的存在性不迭代法的收敛 性 不动点的存在性证明：不动点的存在性证明： 证：证： 若若 aa )(bb )(或或 显然显然 (x) 有不动点；有不动点； 否则，设否则，设 aa )(bb )( 则有则有 aa )(bb )(（因（因a (x)b） 记记 xxx)()(则有则有 0)()(ba 故存在故存在x*使得使得 0*)(x 即即 *)(xx x*即为不动点。即为不动点。 不动点存在的唯一性证明：不动点存在的唯一性证明： 设有设有 x1* x2*, 使得使得 * 1 * 1 )(xx * 2 * 2) (xx 则则 |)(| )()(| * 2 * 1 * 2 * 1 * 2 * 1

39、 xxxxxx 其中，其中，介于介于 x1* 和和 x2* 之间。之间。 由定理条件由定理条件 1| )(|Lx 可得可得 | * 2 * 1 * 2 * 1 xxxx 矛盾！矛盾！ 故故 x1* = x2*，不动点唯一存在。，不动点唯一存在。 定理定理4（全局收敛性）（全局收敛性） 设设 (x) C a, b且满足以下两个条件：且满足以下两个条件： 则对任意则对任意x0 a, b，由由xn+1= (xn )得到的迭代序得到的迭代序 列列xn 收敛到收敛到 (x)的不动点的不动点x*，并有误差估计：，并有误差估计： | 1 1 | 1 * nnn xx L xx 01 1 *xx L L xx

40、 n n （2）若）若 (x)在在a, b一阶连续，且存在常数一阶连续，且存在常数0L1， 使得对任意使得对任意x a, b，成立，成立 | (x)| L （1）对于任意）对于任意x a, b，有，有a (x)b； )( )( * 1 xx xx nn |)(| | )()(| * 1 * 1 * xx xxxx n nn | * 1 * xxLxx nn | * 0 * xxLxx n n 0|lim|lim * 0 * xxLxx n n n n ( 0L1 ) 故迭代格式收敛。故迭代格式收敛。 * limxxn n 所以所以 证明：证明： | | * 1 * 11 * 11 * xxLx

41、xxxxx xxxxxx nnnnnn nnnn | )1( 1 * nnn xxxxL | 1 1 | 1 * nnn xx L xx 反复递推，可得误差估计式反复递推，可得误差估计式 01 1 *xx L L xx n n 定义 设 (x)有丌动点x*，若存在x*的某邻域 R：|x-x*| ，对仸意x0 R，迭代过程 xk+1= (xk )产生的序列xk R且收敛到x*， 则称丌动点迭代法xk+1= (xk )局部收敛。 定理定理4给出的收敛性称全局收敛性，实际应用给出的收敛性称全局收敛性，实际应用 时通常只在不动点时通常只在不动点x*邻近考察其收敛性，称局部收邻近考察其收敛性，称局部收

42、敛性。敛性。 证明：根据连续函数性质，因 (x)连续，存在x*的某 邻域R：|x-x*| ，对仸意x R， | (x)| L1，且 | (x)-x*| = | (x)- (x*)| = | ()| | x- x*| L | x- x*| | x- x*| 即对仸意x R， 总有 (x) R。 由全局收敛性定义知，迭代过程 xk+1= (xk )对亍仸意初 值x0 R均收敛。 定理定理5（局部收敛性）（局部收敛性） 设设x*为为 (x)的不动点，的不动点， (x)在在x*的某邻域连续，且的某邻域连续，且| (x*)|1时称时称超线性收敛超线性收敛。 且且r 越大，收敛越快。越大，收敛越快。 定理

43、：设x*为x= (x )的丌动点，若 (x )满足： （1） (x )在x*附近是p次连续可微的(p1)； （2） 则迭代过程xn+1= (xn )在点x*邻近是p阶收敛的。 p nn p nnn xx p xxxxxxxx)( ! 1 )( ! 2 1 )()()( *)(2* 0*)(, 0*)(*)(*)( )()1( xxxx pp )( ! | *| |*)()(| *| )( 1n p p n nn p xx xxxx 得得 |*)(| ! 1 | )(| ! 1 lim |*| |*| lim )()( 1 x ppxx xx p n p n p n n n 所以所以 故故迭代过

44、程迭代过程xn+1= (xn ) p阶收敛。阶收敛。 证：证：由由Taylor公式公式 假定 (x )改变丌大，近似取某个近似值L，则有 2.3.3 迭代收敛的加速方法 *)(*)()(* 001 xxxxxx *)(* 01 xxLxx *)(* 12 xxLxx * * * * 1 0 2 1 xx xx xx xx 一、一、Aitken加速收敛方法：加速收敛方法： 由微分中值定理，有由微分中值定理，有 同理同理 两式相比，得两式相比，得 类推可得 0 012 2 01 0 012 2 120 2 )( 2 *x xxx xx x xxx xxx x 21 2 1 2 )( kkk kk

45、kk xxx xx xx 故故 上式即为上式即为Aitken加速收敛方法的迭代格式。加速收敛方法的迭代格式。 将Aitken加速技巧不丌动点迭代结吅可得 )( kk xy)( kk yz kkk kk kk xyz xy xx 2 )( 2 1 或将其写为或将其写为 )( 1kk xx xxx xx xx )(2)( )( )( 2 二、二、Steffensen迭代法：迭代法： 解：由前知，迭代格式 xk+1=xk3-1 是发散的。现用 steffensen迭代法计算。取 (x )=x3-1，结果如下： k xk yk zk 0 1 2 3 4 5 1.5 1.41629 1.35565 1.

46、32895 1.32480 1.32472 2.37500 1.84092 1.49140 1.34710 1.32518 12.3965 5.23888 2.31728 1.44435 1.32714 表明即使不动点迭代法不收敛，用表明即使不动点迭代法不收敛，用steffensen迭迭 代法仍可能收敛。代法仍可能收敛。 例例：用：用steffensen迭代法求解方程迭代法求解方程 x3-x-1=0 。 求方程求方程 2 30 x xe 在在3,4中的解。中的解。 例例 解解 由由 2 3 x ex 取对数取对数 2 ln32lnln3( )xxxx 构造迭代格式构造迭代格式 1 2lnln3 kk xx 故故 2 ( )x x 当当x 3,4时，时， (x ) 3,4，且，且 2 max |( )|1 3 x故迭代格式收敛。故迭代格式收敛。 取取x0=3.5，经计算可得迭代，经计算