《非线性方程的数值解法精选PPT.ppt》由会员分享，可在线阅读，更多相关《非线性方程的数值解法精选PPT.ppt（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、非线性方程的数值解法第1页，此课件共51页哦1本章要讨论的问题：本章要讨论的问题：（非线性）方程（非线性）方程f(x)=0的数值解法的数值解法首先引入定义：首先引入定义：1.f(x)=0的解的解x*称为方程称为方程f(x)=0的根或函数的根或函数f(x)的零点的零点.2.若若f(x)=(x-x*)m g(x),g(x*)0，其中其中m为正整数，为正整数，则称则称 x*为方程为方程f(x)=0的的m重根，或重根，或称称 x*为为函数函数 f(x)的的m重零点重零点.上一页上一页 下一页下一页 返回返回 第2页，此课件共51页哦21 方程求根的二分法方程求根的二分法 方程求根步骤：方程求根步骤：根
2、的隔离根的隔离 确定根所在的区间确定根所在的区间a,b,使在使在a,b内至少有方程的一个根内至少有方程的一个根.有根区间有根区间近似根的精确化近似根的精确化 已知根的一个近似值后已知根的一个近似值后,构造某种算法构造某种算法,将此近似值精确将此近似值精确化化,使其满足给定的精度要求使其满足给定的精度要求.越小越好越小越好上一页上一页 下一页下一页 返回返回 第3页，此课件共51页哦3下面介绍方程求根的下面介绍方程求根的二分法二分法在确立了有根区间在确立了有根区间a,b后后,需要逐步缩小有根区间需要逐步缩小有根区间.取取a,b的中点的中点x0 0=(=(a+b)/)/2,将区间一分为二将区间一分
3、为二.若若 f(x0 0)=0,)=0,则则x0 0 就是方程的根就是方程的根,否则判别根否则判别根 x*在在x0 0 的左侧还是右侧的左侧还是右侧.不论出现哪种情况不论出现哪种情况,(a1,b1)均为新的有根区间均为新的有根区间,它的长它的长度只有原有根区间长度的一半度只有原有根区间长度的一半,达到了压缩有根区间的目的达到了压缩有根区间的目的.上一页上一页 下一页下一页 返回返回 第4页，此课件共51页哦4 重复以上过程重复以上过程,继续进行二分继续进行二分,可得一系列有根区间可得一系列有根区间 由于每个小区间都是有根区间由于每个小区间都是有根区间,所以这个点就是所求方程所以这个点就是所求方
4、程的根的根.同时同时,在每次二分时在每次二分时,所求出的中点所求出的中点 形形成一个无穷数列成一个无穷数列 这个数列必定收敛于这个数列必定收敛于 x*.上一页上一页 下一页下一页 返回返回 第5页，此课件共51页哦5abx0 x1a1b2When to stop?x*b1上一页上一页 下一页下一页 返回返回 a2第6页，此课件共51页哦6误差误差 分析：分析：第第1步产生的步产生的有误差有误差第第 k 步产生的步产生的 xk1 有误差有误差对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k：算法简单算法简单;对对f(x)要求不高要求不高(只要连续即可只要连续即可)
5、，收敛性总，收敛性总能得到保证能得到保证 无法求复数根及偶数重根（函数值的正负号相同）；无法求复数根及偶数重根（函数值的正负号相同）；要计算很多次函数值，收敛慢要计算很多次函数值，收敛慢二分法的误差估计式二分法的误差估计式上一页上一页 下一页下一页 返回返回 第7页，此课件共51页哦7例例1 用二分法求用二分法求f(x)=x 3-x-1=0 在区间在区间1,1.5内内的一个实根的一个实根,要求误差要求误差不超过不超过0.005.0.005.解：解：由题可知由题可知x*(1,1.5),要想要想解之得解之得取取 n6.按二分法计算的过程见下表按二分法计算的过程见下表,x6 为所求之近似根为所求之近
6、似根.上一页上一页 下一页下一页 返回返回 第8页，此课件共51页哦8nanbnxnf(xn)备注备注01.01.51.25-f(a0)0 根据精度要求根据精度要求xn取取到小数点四位即可到小数点四位即可.11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-上一页上一页 下一页下一页 返回返回 第9页，此课件共51页哦9逐步搜索法逐步搜索法 从区间从区间a，b的左端点的左端点 a 出发出发,按选定的步长按选定的步长 h 0 一步
7、一步步向右搜索步向右搜索,若：若：则区间则区间a+j h,a+(j+1)h内必有根内必有根.上一页上一页 下一页下一页 返回返回 于是可确定一个缩小了的有根区间于是可确定一个缩小了的有根区间a+j h,a+(j+1)h.再对新的有根区间，取新的更小的预定步长，继续搜索，再对新的有根区间，取新的更小的预定步长，继续搜索，直到有根区间的长度足够小。直到有根区间的长度足够小。搜索过程也可从搜索过程也可从 b 开始开始,这时应取步长这时应取步长 h 0.第10页，此课件共51页哦102 一元方程的不动点迭代法一元方程的不动点迭代法迭代格式迭代格式一、不动点迭代法及其收敛性一、不动点迭代法及其收敛性1.
8、迭代法的基本思想迭代法的基本思想 将方程将方程 f(x)=0化为等价方程化为等价方程 然后在有然后在有根区间内取一点根区间内取一点 x0,按下式计算按下式计算计算结果生成数列计算结果生成数列 xk 上一页上一页 下一页下一页 返回返回 第11页，此课件共51页哦11 如果这个数列有极限如果这个数列有极限 ,x*就是方程就是方程 的根的根.迭代式（迭代式（1）称为）称为基本迭代法基本迭代法.称为称为迭代函数迭代函数,x 0称为称为迭代初值迭代初值,数列数列(2)称称为为迭代序列迭代序列.上一页上一页 下一页下一页 返回返回 如果迭代序列收敛如果迭代序列收敛,则称迭代格式则称迭代格式收敛收敛,否则
9、称为否则称为发发散散.x*称为称为 的的不动点。不动点。迭代过程中，迭代过程中，xk+1仅由仅由xk决定，因此，这是一种单决定，因此，这是一种单步法。步法。第12页，此课件共51页哦12例例2 用迭代法求方程用迭代法求方程 x 4+2 x 2-x-3=0在区间在区间1,1.2内的实根内的实根.解：解：对方程进行如下三种变形对方程进行如下三种变形 分别按以上三种形式建立迭代格式分别按以上三种形式建立迭代格式,并取并取 x0=1进行迭代计算进行迭代计算,结果结果如下：如下：准确根准确根 x*=1.124123029,可见迭代格式不同可见迭代格式不同,收敛情况也不同收敛情况也不同,收敛收敛速度也不同
10、速度也不同.上一页上一页 下一页下一页 返回返回 第13页，此课件共51页哦13上一页上一页 下一页下一页 返回返回 例例3 3 解：解：把把f(x)=0 转换成等价形式转换成等价形式对应的迭代法为对应的迭代法为取初值取初值x0=1,=1,迭代结果分别收敛到迭代结果分别收敛到x*=,计算结果见下表计算结果见下表 k 0 1 2 3 4 5 xk 1 1.5 1.41666667 1.41421569 1.41421356 1.41421356xk -1 -1.5 -1.41666667 -1.41421569 -1.41421356 -1.41421356 从而可见，基本迭代法的收敛性取决于迭
11、代函数从而可见，基本迭代法的收敛性取决于迭代函数 和初和初值值x0 0的选取。的选取。第14页，此课件共51页哦14问问题题2.迭代格式应该满足什么条件才能保证收敛？迭代格式应该满足什么条件才能保证收敛？3.如何判断迭代收敛的速度如何判断迭代收敛的速度,建立收敛快的迭代格式？建立收敛快的迭代格式？上一页上一页 下一页下一页 返回返回 1.迭代函数迭代函数 如何构造？如何构造？第15页，此课件共51页哦15定理定理1 2.收敛条件与误差估计收敛条件与误差估计上一页上一页 下一页下一页 返回返回 迭代格式的收敛性与迭代函数迭代格式的收敛性与迭代函数 密切相关密切相关.方程方程 x=，Ca,b,满足
12、条件满足条件(1)当当 x a,b 时，时，a,b；(2)0 L 1 使得使得|L 1 对对 x a,b 成立成立.则则(1)函数函数 在在a,b 上有唯一不动点上有唯一不动点 x*;(2)对任意迭代初值对任意迭代初值 x0 a,b,迭代序列迭代序列 x k+1 收敛于收敛于x*.*.（3）有下列误差估计式：有下列误差估计式：第16页，此课件共51页哦16(k=1,2,)反之反之,若在区间若在区间R 内内 ,则迭代必发散则迭代必发散.上一页上一页 下一页下一页 返回返回 L 越越小小 收敛越快收敛越快尚未计算时便估计出第尚未计算时便估计出第 k 次迭代近似值的误差次迭代近似值的误差,称为称为事
13、先误差估计事先误差估计.第17页，此课件共51页哦17 由定理由定理1的误差估计式可看出的误差估计式可看出,只要相邻两次迭代近似值只要相邻两次迭代近似值 xk 与与 xk-1的偏差的偏差|xk xk-1|充分小充分小,就可以保证迭代值就可以保证迭代值 xk 足够精确足够精确.这种用前后两次迭代结果估计这种用前后两次迭代结果估计误差的办法称为误差的办法称为事后误差估计事后误差估计上一页上一页 下一页下一页 返回返回 因此对于给定的允许误差因此对于给定的允许误差,当当 L 较小时较小时,常用前后两次迭代是常用前后两次迭代是否满足否满足|xk xk-1-1|来终止迭代来终止迭代.第18页，此课件共5
14、1页哦18不但可以估计迭代不但可以估计迭代 k 次时的误差次时的误差,也可以用来确定达到误差精度要求的迭代次数也可以用来确定达到误差精度要求的迭代次数 k.当要求误差精度为当要求误差精度为,即要求即要求 ,只要只要即可即可,从中解出从中解出 k 为为实际应用中实际应用中,控制迭代结束的条件也常取为控制迭代结束的条件也常取为 E 其中其中上一页上一页 下一页下一页 返回返回 第19页，此课件共51页哦19xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1上一页上一页 下一页下
15、一页 返回返回 迭代过程的几何解释如下图迭代过程的几何解释如下图第20页，此课件共51页哦20上一页上一页 下一页下一页 返回返回 例例4 4 对于例对于例2 2中的三种迭代法，讨论它们的收敛性。中的三种迭代法，讨论它们的收敛性。解解：对于下面三种迭代函数对于下面三种迭代函数其导函数在其导函数在1,1.2内分别有内分别有 根据定理根据定理1，例，例2中的第三种迭代法发散，第一、二种迭代格式收中的第三种迭代法发散，第一、二种迭代格式收敛，而且第二种迭代法比第一种迭代法收敛快得多。这与实际计算结敛，而且第二种迭代法比第一种迭代法收敛快得多。这与实际计算结果完全吻合。果完全吻合。第21页，此课件共5
16、1页哦21迭代法的流程图如下：迭代法的流程图如下：上一页上一页 下一页下一页 返回返回 第22页，此课件共51页哦22上一页上一页 下一页下一页 返回返回 例例5 5 解解：即可得等价的方程即可得等价的方程 有时，对于不满足定理条件的问题，可以通过转化，化为适合于有时，对于不满足定理条件的问题，可以通过转化，化为适合于迭代的形式。迭代的形式。令令则有则有故故第23页，此课件共51页哦23上一页上一页 下一页下一页 返回返回 二、局部收敛性和加速收敛法二、局部收敛性和加速收敛法定理定理1 1中，迭代法在区间中，迭代法在区间 a,b 上的收敛性，称之为上的收敛性，称之为全局收敛性全局收敛性.定义定
17、义:若在若在 x*的某的某 邻域邻域 R=x|x x*|,使迭代过程使迭代过程xk+1=(xk),k=0,1,2,对于任意对于任意x0 R 均收敛均收敛,则称该迭代过程则称该迭代过程在在x*处具有处具有局部收敛性局部收敛性.定理定理2 第24页，此课件共51页哦24迭代过程的收敛速度迭代过程的收敛速度定义定义 p的大小反映了迭代过程收敛的快慢的大小反映了迭代过程收敛的快慢,p 越大收敛速度越快越大收敛速度越快.上一页上一页 下一页下一页 返回返回 第25页，此课件共51页哦25定理定理3 上一页上一页 下一页下一页 返回返回 设设 x*为函数为函数 的不动点的不动点,在在x*的邻域的邻域 内内
18、 有连续的有连续的p p 阶导数阶导数(p p1),),那么那么(1)0|1,则迭代过程在则迭代过程在x*的邻近为线性收敛；的邻近为线性收敛；第26页，此课件共51页哦26例例6 证明迭代公式证明迭代公式 是求是求 的三阶方法的三阶方法.假设假设 xo 充充分靠近分靠近 x*,求求 解：解：此迭代格式的迭代函数为此迭代格式的迭代函数为方程两边对方程两边对 x 求导求导,得得上一页上一页 下一页下一页 返回返回 第27页，此课件共51页哦27再将上式两边对再将上式两边对 x 求导求导,得得上式再对上式再对 x 求导求导,得得上一页上一页 下一页下一页 返回返回 所以，迭代格式是所以，迭代格式是3
19、 3阶收敛的阶收敛的.第28页，此课件共51页哦28加速收敛的加速收敛的Steffensen迭代法迭代法 对于线性收敛的迭代法，收敛很慢。对于线性收敛的迭代法，收敛很慢。上一页上一页 下一页下一页 返回返回 设设 xk 是方程是方程 根根 x*的一个近似值，由的一个近似值，由xk 开始相继迭代两次开始相继迭代两次,将其将其结果记作结果记作第29页，此课件共51页哦29于是得到如下迭代格式于是得到如下迭代格式称之为称之为Steffensen迭代法迭代法(其他教材也称之为其他教材也称之为埃特金埃特金(Aitken)外推加速外推加速法法).上一页上一页 下一页下一页 返回返回 它的不动点迭代格式是它
20、的不动点迭代格式是其中迭代函数为其中迭代函数为第30页，此课件共51页哦30若对此格式用若对此格式用Steffensen法法,则则上一页上一页 下一页下一页 返回返回 例例7 7 第31页，此课件共51页哦31上一页上一页 下一页下一页 返回返回 第32页，此课件共51页哦32上一页上一页 下一页下一页 返回返回 例例8 8 现在用函数现在用函数 构造构造Steffensen迭代法迭代法,k 0 1 5 6xk 1.5 1.4162930 1.3247180 1.3247180可见，可见，Steffensen迭代法对这种不收敛的情形同样有效。迭代法对这种不收敛的情形同样有效。第33页，此课件共
21、51页哦333 一元方程的常用迭代法一元方程的常用迭代法一、一、Newton迭代法迭代法 设设x*是方程是方程f(x)=0的实根。取的实根。取 x0 x*，将将 f(x)在在 x0 做一阶做一阶Taylor展开展开:，在在 x0 和和 x 之间。之间。将将(x*x0)2 看成高阶小量，则有：看成高阶小量，则有：xyx*x0上一页上一页 下一页下一页 返回返回 由图示，可见由图示，可见xk+1为函数为函数f(x)在点在点xk处处的切线与横坐标轴的交点，所以，的切线与横坐标轴的交点，所以，Newton迭代法也称迭代法也称切线法切线法。Newton迭代格式迭代格式 第34页，此课件共51页哦34上一
22、页上一页 下一页下一页 返回返回 与上一节例与上一节例7 7相比，牛顿法的收敛速度快很多。相比，牛顿法的收敛速度快很多。例例9 9 第35页，此课件共51页哦35上一页上一页 下一页下一页 返回返回 牛牛顿顿迭迭代代法法的的流流程程图图第36页，此课件共51页哦36注：注：注：注：牛顿迭代法的收敛性依赖于牛顿迭代法的收敛性依赖于x0 的选取。的选取。x*x0 x0 x0上一页上一页 下一页下一页 返回返回 第37页，此课件共51页哦37定理定理 上一页上一页 下一页下一页 返回返回 （收敛的充分条件收敛的充分条件）设）设 f C2a,b，若，若(1)f(a)f(b)0；则牛顿迭代法产生的序列则
23、牛顿迭代法产生的序列 xk 收敛到收敛到f(x)在在 a,b 的唯一根。的唯一根。定理定理 有根有根根唯一根唯一产生的序列单调有产生的序列单调有界，保证收敛。界，保证收敛。保证保证f(x)上凸或上凸或下凸下凸第38页，此课件共51页哦38上一页上一页 下一页下一页 返回返回 10 第39页，此课件共51页哦39Q1:若若 ，牛顿迭代法牛顿迭代法是否仍收敛？是否仍收敛？设设 x*是是 f 的的 m 重零点重零点,则：则：且且 A1:有局部收敛性，但仅为线性收敛有局部收敛性，但仅为线性收敛.下面介绍计算重根的牛顿迭代法下面介绍计算重根的牛顿迭代法上一页上一页 下一页下一页 返回返回 第40页，此课
24、件共51页哦40因此因此,求求f(x)=0)=0 之之m重根重根x*等价于求等价于求 (x)=0 的单根的单根x*。而对而对 (x)=0用牛顿迭代法求根则是平方收敛的用牛顿迭代法求根则是平方收敛的,其迭代格式为其迭代格式为 令令 ，则，则 f 的重零点就是的重零点就是 的单零点。的单零点。A2:方法方法1：将求将求 f 的重零点转化为求另一函数的单零点。的重零点转化为求另一函数的单零点。Q2:如何加速求重根的收敛速度？如何加速求重根的收敛速度？上一页上一页 下一页下一页 返回返回 第41页，此课件共51页哦41方法方法2：采用如下迭代格式采用如下迭代格式可以证明它是求可以证明它是求m重根重根
25、x*的具有平方收敛的迭代格式的具有平方收敛的迭代格式.如何确定根的重数如何确定根的重数 m?则：则：上一页上一页 下一页下一页 返回返回 第42页，此课件共51页哦42例例11 用牛顿迭代法求方程用牛顿迭代法求方程解解：kxkk1/(1-k)00.9510.974427920.987058330.99348780.50902.036940.99673280.50472.019050.99835760.50072.002860.99919010.51252.0511上一页上一页 下一页下一页 返回返回 第43页，此课件共51页哦43上一页上一页 下一页下一页 返回返回 第44页，此课件共51页哦
26、44例例12 用用3种方法求解方程种方法求解方程解解：上一页上一页 下一页下一页 返回返回 都取都取x0=1.5，计算结果见下表：，计算结果见下表：第45页，此课件共51页哦45 方法（方法（2）和方法（）和方法（3）都是二阶方法，）都是二阶方法，x3都精确到了小数点后第都精确到了小数点后第9位，方法（位，方法（1）即普通牛顿迭代法，解重根是一阶方法，要近）即普通牛顿迭代法，解重根是一阶方法，要近30次迭代次迭代才能有相同的精度。才能有相同的精度。xk方法（方法（1 1）方法（方法（2 2）方法（方法（3 3）x01.51.51.5x11.458 333 3331.416 666 6671.4
27、11 764 706x21.436 607 1431.414 215 6861.414 211 438x31.425 497 6191.414 213 5621.414 213 562上一页上一页 下一页下一页 返回返回 第46页，此课件共51页哦46牛顿法的牛顿法的优点优点 收敛速度快收敛速度快 牛顿法的牛顿法的缺点缺点 每次迭代要计算一次导数值每次迭代要计算一次导数值 ，当，当 表达式表达式复杂或无明显表达式时求解困难。复杂或无明显表达式时求解困难。第47页，此课件共51页哦47简化牛顿迭代法简化牛顿迭代法此式称此式称简化简化牛顿迭代法牛顿迭代法.简化简化Newton法的收敛速度为线性法的
28、收敛速度为线性.xyx*x0几何意义：几何意义：用平行线代替牛顿法中的用平行线代替牛顿法中的切线切线.此法收敛较慢此法收敛较慢.上一页上一页 下一页下一页 返回返回 主要思路：主要思路：第48页，此课件共51页哦48二、割线法二、割线法xyx*x0P0 x1P1x2P2称之为（称之为（双点）割线法双点）割线法.这样的迭代格式称之为这样的迭代格式称之为单点割线法单点割线法.它的收敛速度是线性的它的收敛速度是线性的.上一页上一页 下一页下一页 返回返回 注：注：计算之前必需给出两个初值计算之前必需给出两个初值x0和和x1.第49页，此课件共51页哦49例例13 用双点割线法求方程用双点割线法求方程
29、 f(x)=x3+10 x 20=0在区间在区间1.5,2内之根的近内之根的近似值。似值。解解 显然显然 f(x)=x3+10 x 20在区间在区间1.5,2内连续且有零点。内连续且有零点。取取x0=1.5，x1=2，建立双点割线法的迭代公式，建立双点割线法的迭代公式计算结果如下：计算结果如下：上一页上一页 下一页下一页 返回返回 第50页，此课件共51页哦50例例14 用牛顿迭代法和割线法求方程用牛顿迭代法和割线法求方程 f(x)=x4+2x2 x-3=0在区间在区间(1,1.5)内之根内之根(=10=10-9-9)解：解：取取 x0=1.5,用牛顿法可得用牛顿法可得 x6=1.124123030.取取 x0=1.5,x1=1,用双点割线法用双点割线法,迭代迭代6次得到同样的结果次得到同样的结果,而采用单而采用单点割线法点割线法,则迭代则迭代18次得次得 x18=1.124123029.上一页上一页 下一页下一页 返回返回 （双点）割线法的收敛阶虽然低于（双点）割线法的收敛阶虽然低于Newton法，但是迭代一次只要计算法，但是迭代一次只要计算一次一次f(xk)，不需要计算导数值，不需要计算导数值f(xk)，所以效率高，实际问题中经常使，所以效率高，实际问题中经常使用。用。第51页，此课件共51页哦51