第二章非线性方程求根精选文档.ppt

《第二章非线性方程求根精选文档.ppt》由会员分享，可在线阅读，更多相关《第二章非线性方程求根精选文档.ppt（90页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章非线性方程求根本讲稿第一页，共九十页第二章第二章 方程求根方程求根n2.1 增值寻根法与二分法n2.2 迭代法（重点）迭代法（重点）n2.3 迭代收敛的加速n2.4 牛顿法（重点）牛顿法（重点）n2.5 割线法本讲稿第二页，共九十页历史背景 代数方程的求根问题是一个古老的数学问题。理论上，n次代数方程在复数域内一定有 n个根(考虑重数)。早在16世纪就找到了三次、四次方程的求根公式，但直到19世纪才证明大于等于大于等于5 5次的一般代数方程次的一般代数方程式不能用代数公式求解式不能用代数公式求解，而对于超越方程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个。一般也不存在根的

2、解析表达式。因此需要研究数值方法求得满足一定精度要求的根的近似解。本讲稿第三页，共九十页根的概念 n给定方程 f(x)=0，如果有a使得f(a)=0，则称a为 f(x)=0的根根 或f(x)的零点零点.n设有正整数m使得f(x)=(x-a)mg(x)且g(a)0，则当m2时，称a为f(x)=0的m重根重根；当m=1时，称为f(x)=0的单根单根.n本章只讨论实根实根的求法.本讲稿第四页，共九十页 本章重点介绍求解非线性方程的几种常见和有效的数值方法,简单介绍一些最基本的解法.无论在理论上,还是在实际应用中,这些数值解法都是对经典的解析方法的突破性开拓和补充,许多问题的求解,在解析方法无能为力时

3、,数值方法则可以借助于计算机出色完成.本讲稿第五页，共九十页2.1.1 增值寻根法求非线性方程 确定方程的有根区间(如增值寻根法)计算根的近似值（如二分法）有根区间：存在根 隔根区间：唯一根的根的方法常分为两步：本讲稿第六页，共九十页n零点定理零点定理：设 ，且 ，则方程 在区间 上至少有一个根。如果 在 上恒正或恒负，则此根唯一。零点定理本讲稿第七页，共九十页等步长扫描等步长扫描n用计算机求有根区间：等步长扫描法。设h0是给定的步长，取 ，若 则扫描成功；否则令 ，继续上述方法，直到成功。如果 则扫描失败。再将h 缩小，重复以上步骤。本讲稿第八页，共九十页例题n例 设方程 解：取h=0.1,

4、扫描得：又 即 在 有唯一根。本讲稿第九页，共九十页 设有非线性方程 f(x)=0其中，f(x)为 a,b 上连续函数且设 f(a)f(b)0不妨设方程于 a,b 内仅有一个实根。求方程实根 x*的二分法过程，就是将含根区间 a,b 逐步分半，检查函数符号的变化，以便确定含根的充分小区间。2.2 二分法本讲稿第十页，共九十页示意图ba1b2x*ab1a2本讲稿第十一页，共九十页二分法的步骤n 用二分法(将区间对平分)求解。令 若 ，则 为有根区间，否则 为有根区间 记新的有根区间为 ，则 且 本讲稿第十二页，共九十页二分法n对 重复上述做法得n且 本讲稿第十三页，共九十页 设 所求的根为 ，则

5、 即 取 为 的近似解，则 本讲稿第十四页，共九十页收敛速度n可用二分法求方程 实根 x*的近似值到任意指定的精度。事实上，设为给定精度要求，试确定分半次数 n使 由 两边取对数，即得 且二分法收敛速度与公比为二分法收敛速度与公比为1/2的等比级数相同的等比级数相同。本讲稿第十五页，共九十页 解:为达到要求的精度，用二分法需进行 即最多需要11次二分。本讲稿第十六页，共九十页k11.0,2.01.52.37521.0,1.51.25-1.79687531.25,1.51.3750.16210937541.25,1.3751.3125-0.84838867251.3125,1.3751.3437

6、5-0.35098266661.34375,1.3751.359375-0.09640884471.359375,1.3751.36718750.03235578581.359375,1.3671875001.36328125-0.03214997191.363281250,1.3671875001.3652433750.000072025101.363281250,1.3652343751.364257813-0.016046691111.364257813,1.3652343751.364746094-0.007989263121.364746094,1.3652343751.364990

7、235-0.003959102 计算结果本讲稿第十七页，共九十页2.2.1 迭代法基本思想 对于 有时可以写成 形式 如：本讲稿第十八页，共九十页迭代法及收敛性 考察方程 。一般不能直接求出它的根。但如果给出根的某个猜测值 ，代入 中的右端得到 ，再以 为一个猜测值，代入 的右端得 反复迭代得本讲稿第十九页，共九十页简单迭代法（单点迭代法）简单迭代法（单点迭代法）将 变为另一种等价形式 。选取 的某一近似值 ，则按递推关系 产生的迭代序列 。这种方法算为单点迭代法单点迭代法。形如的迭代公式称为多点迭代法多点迭代法。本讲稿第二十页，共九十页迭代法及收敛性 若 收敛，即 则得 的一个根称此迭代过程

8、收敛。本讲稿第二十一页，共九十页迭代法的几何意义n 交点的横坐标 xyy=xx*y=(x)x0p0 x1p1本讲稿第二十二页，共九十页例题例 试用迭代法求方程 在区间(1，2)内的实根，初始近似值取.。解：由 建立迭代关系 k=0,1,2,3,计算结果如下:本讲稿第二十三页，共九十页例题n精确到小数点后五位kxkKxk01.551.3247611.3572161.3247321.3308671.3247231.3258881.3247241.32494本讲稿第二十四页，共九十页例题n但如果由 建立迭代公式 仍取 ，则有 ，显然结果越来越大，是发散序列本讲稿第二十五页，共九十页.迭代法收敛的条件

9、迭代法收敛的条件n压缩映像原理压缩映像原理 设迭代函数 在闭区间 上满足（1）（2）满足 Lipschitz 条件即:有且 ，称为李普希兹常数李普希兹常数。本讲稿第二十六页，共九十页压缩映像原理压缩映像原理则 在 上存在 唯一解 ，点也称为函数的不动点。且对 ，由 产生的序列 收敛于 。本讲稿第二十七页，共九十页压缩映像原理证明n证明：不失一般性,不妨设 否则 a 或 b 为方程的根。n根的存在性根的存在性 令 本讲稿第二十八页，共九十页压缩映像原理证明 则 ，即 由 是 上的连续函数 是 上的连续函数。故由零点定理 在 上至少有一根本讲稿第二十九页，共九十页压缩映像原理证明n根的唯一性根的唯

10、一性 假设有 均为方程的根，则 因为 0L1 ，故：，即根是唯一的。本讲稿第三十页，共九十页压缩映像原理证明n序列的收敛性收敛性 与n 无关，而0L|L|1 本讲稿第四十四页，共九十页|L|较小 L越小收敛速度越快。本讲稿第四十五页，共九十页迭代公式：本讲稿第四十六页，共九十页迭代公式比较本讲稿第四十七页，共九十页迭代公式比较本讲稿第四十八页，共九十页n（1 1）（2 2）（3 3）（4 4）0 01.51.51.51.51.51.51.51.51 1-0.875-0.8750.81650.81651.286953771.286953771.348399731.348399732 26.732

11、6.7322.99692.99691.402540801.402540801.367376371.367376373 3-469.7-469.71.345458381.345458381.364957011.364957014 41.375170251.375170251.365264751.365264755 51.360094191.360094191.365225591.365225596 61.361946971.361946971.365223061.365223067 71.363887001.363887001.365229941.365229948 81.365916731.3

12、65916731.365230021.365230029 91.364878221.364878221.365230011.3652300110101.365410061.3654100615151.365223681.3652236820201.365230241.3652302423231.365229981.3652299825251.365230011.36523001本讲稿第四十九页，共九十页2.2.4 迭代法收敛的速度迭代法收敛的速度 定义定义2 设序列 收敛于 ，令 若有实数 和正常数C，使得 则称该序列是 p 阶收敛阶收敛的；其中C 称为渐进误差常数渐进误差常数。本讲稿第五十页

13、，共九十页迭代法收敛的阶迭代法收敛的阶当p=1时，称为线性收敛；当2p1时，称为超线性收敛；当p=2时，称为平方收敛或二次收敛。本讲稿第五十一页，共九十页定理定理3 （迭代法收敛的阶）（迭代法收敛的阶）本讲稿第五十二页，共九十页证明：本讲稿第五十三页，共九十页本讲稿第五十四页，共九十页 本讲稿第五十五页，共九十页 解：解：解：解：从而知(1)是平方收敛的。本讲稿第五十六页，共九十页将 看作由下述方程确定的隐函数从而，上式两边对 求导，得 从而，再两边对求导，得 上式两边对 求导，得 令，可得 本讲稿第五十七页，共九十页例迭代过程 是否收敛？如发散，试构造一收敛的迭代公式。方程为x-4+2x=0

14、.设f(x)=x-4+2x，则f(1)0，故方程f(x)=0在区间(1,2)内有根.题中(x)=4-2x，当x(1,2)时,(x)=-2xln22ln21，由定理2不能用来迭代求根.把方程改写为x=ln(4-x)/ln2，此时(x)=ln(4-x)/ln2,则 1当x1,2时，(x)1,ln3/ln2 1,2 2x(1,2)，有 (x)=故可用迭代公式xn+1=ln(4-xn)/ln2来求解(1,2)区间内的唯一根.本讲稿第五十八页，共九十页.迭代收敛的加速.松弛法本讲稿第五十九页，共九十页.松弛法本讲稿第六十页，共九十页.埃特金（Aitken)方法 本讲稿第六十一页，共九十页.埃特金（Ait

15、ken)方法 本讲稿第六十二页，共九十页 埃特金（Aitken)方法本讲稿第六十三页，共九十页例：本讲稿第六十四页，共九十页k（a）(b)(c)(d)(e)015151515151-0.8750.81651.286953771.348399731.373333326.7322.99691.402540801.367376371.365262013-469.71.345458381.36495701.3652300141.031081.375170251.3652647581.365916731.3652300291.364878221.36523001231.36522998251.36523

16、001对选取的gi(x)，取初始近似值x0=1.5，迭代计算结果列在表。本讲稿第六十五页，共九十页比较可得，与x8的误差差不多。简单观察迭代过程，(a)(b)不定，(c)(d)(e)都收敛，但收敛速度相差很大。例：对g4(x)产生的迭代序列进行Aitken加速。解:利用计算公式得本讲稿第六十六页，共九十页本讲稿第六十七页，共九十页 本讲稿第六十八页，共九十页2.4 牛顿迭代法2.4.1 基本思想将 在 点展开为Taylor展式有近似方程 本讲稿第六十九页，共九十页2.4.2 牛顿迭代法的几何意义xyx*x0 x2x1y=f(x)本讲稿第七十页，共九十页牛顿迭代法设方程 在根 附近取初始近似根由

17、迭代公式求解方法这种求根算法称为Newton法（切线法）法（切线法）此公式称为Newton迭代公式迭代公式.本讲稿第七十一页，共九十页牛顿迭代法Newton法的迭代函数是从而 由此知若 是 的一个单根，则在 附近Newton法是局部收敛的，并且收敛速度至少是平方收敛的.但如果 是 的m1重根，则此时Newton法仅有线性收敛速度.本讲稿第七十二页，共九十页2.4.3 Newton法收敛的充分条件法收敛的充分条件本讲稿第七十三页，共九十页Newton迭代法收敛性证明：根的存在性存在性 根的唯一性唯一性本讲稿第七十四页，共九十页本讲稿第七十五页，共九十页.牛顿阶导数法本讲稿第七十六页，共九十页牛顿

18、阶导数法迭代公式本讲稿第七十七页，共九十页由前例可知其为阶收敛。本讲稿第七十八页，共九十页牛顿阶导数法由前例可知其为阶收敛。本讲稿第七十九页，共九十页2.5 割线法几何示意图(a)单点割线法 (b)变端点弦截法 本讲稿第八十页，共九十页2.5 割线法Newton迭代法有一个较强的要求是 存在且 ,因此用弦的斜率近似的替代 。本讲稿第八十一页，共九十页割线法解得弦与 轴的交点是坐标 本讲稿第八十二页，共九十页割线法本讲稿第八十三页，共九十页例 用双点割线法求方程在区间 内的实根。解：取 代入公式 计算结果,如下表所示：本讲稿第八十四页，共九十页kxkf(xk)01-112521.16666666

19、7-0.5787036931.253112023-0.2853630241.337206444 0.05388057951.323850096-0.003698116861.324707936-4.273521*10E-571.3247179653.79*10E-8本讲稿第八十五页，共九十页2.5.3 割线法收敛的速度本讲稿第八十六页，共九十页将Newton迭代中的导数，用差商代替，有格式是2步格式。收敛速度比Newton迭代慢x0 x1割线割线 切线切线本讲稿第八十七页，共九十页x0 x1切线切线 割线割线 本讲稿第八十八页，共九十页几何解释几何解释本讲稿第八十九页，共九十页作业习题9 11 一、三一、三 班同学逢单周单周交作业；二二 班同学逢双周双周交作业；本讲稿第九十页，共九十页