《非线性方程求根 (3)优秀PPT.ppt》由会员分享，可在线阅读，更多相关《非线性方程求根 (3)优秀PPT.ppt（76页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、非线性方程求根第一页，本课件共有76页一、一、问题的提出问题的提出二、二、有关概念有关概念三、三、二分法原理二分法原理四、四、收敛性分析收敛性分析五、二分法的优缺点五、二分法的优缺点六、例题求解六、例题求解七、七、原理概述原理概述第第3 3章：非线性方程求根章：非线性方程求根 -二分法二分法第二页，本课件共有76页一、问题的提出 函数方程函数方程 f f（x x）=0 (1)=0 (1)若f(x)不是x的线性函数，则称(1)为非线性方非线性方程，特别若f(x)是n次多项式，则称(1)为n次多项式方程或代数方程；若f(x)是超越函数，则称(1)为超越方程。第三页，本课件共有76页第四页，本课件共
2、有76页 求根问题包括：求根问题包括：根的存在性、根的范围和根的精确化根的存在性、根的范围和根的精确化。定义收敛阶定义收敛阶：设迭代过程：设迭代过程 收敛于方程收敛于方程 的根的根 如果迭代误差如果迭代误差 满足极限式：满足极限式：(c(c是不为零的常数是不为零的常数,p0),p0)则称该迭代过程是则称该迭代过程是P P阶收敛的。特别地，阶收敛的。特别地，P=1P=1时称时称线性收线性收敛敛，P 1P 1时称时称超线性收敛超线性收敛，P=2P=2时时称称平方收敛平方收敛。二、有关概念二、有关概念第五页，本课件共有76页有关概念有关概念(续续)单根和重根单根和重根第六页，本课件共有76页有关概念
3、有关概念(续续)例例3-13-1第七页，本课件共有76页第八页，本课件共有76页 三、二分法原理 给定方程f(x)=0,设f(x)在区间a,b连续,且f(a)f(b)0,则方程f(x)=0在(a,b)内至少有一根,为便于讨论,不妨设方程f(x)=0在(a,b)内只有一实根 ，采取使有根区间逐步缩小,从而得到满足精度要求的实根 的近似值 。第九页，本课件共有76页第十页，本课件共有76页第十一页，本课件共有76页第十二页，本课件共有76页 第十三页，本课件共有76页 四、收敛性分析 现在来研究用二分法求方程的根的精确性。假定f(x)是连续函数,并且它在区间a0.b0的两端点所取的值有相反的符号,
4、于是在a0.b0中有一个根r,如果用中点c0=(a0+b0)/2作为对r的估计，则有r-c0(b0-a0)/2.如图所示:r-c0 a0 r c0 b0现在应用二分法算法,并将算出的量用a0,b0,c0,a1,b1,c1 等来表示,则由同样的推理,r-cn(bn-an)/2 n=0,1,2,.由于这些区间的宽度在每一步中都除以2,所以可断定r-cn 可见经过n步后将算出一个近似根，其误差至多为 。第十四页，本课件共有76页 五、二分法的优缺点 二分法计算过程简单，程序容易实现。但在大范围内求根时，该方法收敛较慢，且不能求偶数重根和复根，一般用于求根的初始近似值，而后在使用其它的求根方法。二分法
5、收敛速度不快，其收敛速度仅与一个以 1/2为比值的等比级数相同。第十五页，本课件共有76页 六、例题求解例题求解 例1:用二分法求方程 在区间(1,2)内的实根,要求误差限为 。解：令f(1)0 记I0=1,2 ,x0=(1+2)/2=1.5因为 f(x0)f(1)0 得I1=1.5,2 ,x1=(1.5+2)/2=1.75f(x1)f(1.5)0 得I2=1.5,1.75 ,x2=(1.5+1.75)/2=1.625.I6=1.681875,1.6875,I7=1.671875,1.679688b7-a7=0.781310-2 10-2 x*x7=1.6758第十六页，本课件共有76页第十七
6、页，本课件共有76页第十八页，本课件共有76页 七、原理阐述七、原理阐述 如果我们把二分法与跨步区间法结合起来如果我们把二分法与跨步区间法结合起来,就可以求就可以求非线性方程在任一区间上的全部实根。非线性方程在任一区间上的全部实根。首先首先,将方程式将方程式f(x)=0f(x)=0化为函数式化为函数式y=f(x).y=f(x).假设方假设方程求解区间为程求解区间为x x a,b,a,b,跨步区间为跨步区间为h h长长,允许误差允许误差为为。如图。如图3 3所示。所示。由由a a点出发向点出发向 b b点跨步点跨步,每跨一步每跨一步h,h,经过判断在该区经过判断在该区间内是否有根。如有根则进行二
7、分法求根计算间内是否有根。如有根则进行二分法求根计算,否则继否则继续以续以h h为步长向前跨步找根为步长向前跨步找根,直到走出区间直到走出区间a,ba,b为止为止 。这样这样,我们就可以按顺序将方程的全部我们就可以按顺序将方程的全部实根找出。实根找出。第十九页，本课件共有76页第二十页，本课件共有76页 y x a b o 图3 第二十一页，本课件共有76页解解 因为 所以二分6次，可满足精度要求要 只需 即 第二十二页，本课件共有76页 迭代法是求解非线性方程近似根的一种方法，这种方法的关键是确定迭代函数g(x)，不动点迭代法用直接的方法从原方程中隐含的求出x，从而确定迭代函数g(x)，这种
8、迭代法收敛速度较慢，迭代次数多，因此常用于理论中，Newton迭代法采用另一种迭代格式，具有较快的收敛速度，由牛顿迭代法可以得到很多牛顿迭代法可以得到很多其它迭代格式其它迭代格式。第第3章：非线性方程求根章：非线性方程求根 -迭代法迭代法第二十三页，本课件共有76页一、不动点迭代法的概念与收敛性一、不动点迭代法的概念与收敛性二、二、NewtonNewton迭代法及其收敛性迭代法及其收敛性三、牛顿法的几何意义三、牛顿法的几何意义四、牛顿迭代法的步骤四、牛顿迭代法的步骤五、例题五、例题六、其他注意的事项（牛顿法变形）六、其他注意的事项（牛顿法变形）七、牛顿迭代法的优缺点七、牛顿迭代法的优缺点八、迭
9、代的一般概念八、迭代的一般概念主要内容主要内容第二十四页，本课件共有76页一、不动点迭代法的概念与收敛性不动点迭代法的概念与收敛性 不动点迭代法又称逐次迭代法，基本思想是构造不动点迭代法又称逐次迭代法，基本思想是构造不动点方程，以求得近似根。即由方程不动点方程，以求得近似根。即由方程f(x)=0f(x)=0变换为变换为x=x=g(x)g(x),然后建立迭代格式，然后建立迭代格式，当给定处值当给定处值x x0 0 后后,由迭代格式可求得数列由迭代格式可求得数列xxk k。如果如果xxk k 收敛于收敛于x x*，则它就是方程的根。因为：，则它就是方程的根。因为：但迭代格式有多种，迭代格式如何建立
10、才能保但迭代格式有多种，迭代格式如何建立才能保证迭代法的数列收敛？证迭代法的数列收敛？例例3-4,3-4,方程与例方程与例3-23-2相同相同第二十五页，本课件共有76页第二十六页，本课件共有76页什么原因？什么原因？第二十七页，本课件共有76页定理一：定理一：假定函数假定函数 ，满足下列条件：，满足下列条件：1、对任意、对任意 有有 ；（；（映内性映内性）(1.1)2、存在正数、存在正数 L1，使对任意，使对任意 有有 （压缩性压缩性）(1.2)则迭代过程则迭代过程 对于任意初值对于任意初值 均收敛于方程均收敛于方程 的根的根 ，且有如下的误差估计式：，且有如下的误差估计式：(1.3)实用中
11、实用中(1.2)式常用式常用 第二十八页，本课件共有76页第二十九页，本课件共有76页证明：证明：设方程设方程 在区间在区间 根为根为 ，则有则有 由由故故据此反复递推有据此反复递推有第三十页，本课件共有76页故当故当 时迭代值时迭代值按按(1.2)式式 有有 (1.4)，据此反复递推得：据此反复递推得：于是对任意正整数于是对任意正整数p有有 在上式令在上式令 ，注意到，注意到 即得式即得式(1.3)。证毕。证毕。第三十一页，本课件共有76页第三十二页，本课件共有76页第三十三页，本课件共有76页定义一定义一：如果存在如果存在 的某个邻域的某个邻域 ，使迭代过程，使迭代过程 对于任意初值对于任
12、意初值 均收敛，则称迭代过程均收敛，则称迭代过程 在根在根 邻近具有局部收敛性。邻近具有局部收敛性。定理二定理二：设：设 为方程为方程 的根，的根，在在 的邻近连续。则的邻近连续。则迭代过程在迭代过程在 邻近具有局部收敛性。邻近具有局部收敛性。第三十四页，本课件共有76页证明：证明：由连续函数的性质，存在 的某个邻域 ，使对于任意 成立 此外,对于任意 总有 。这是因为 依据定理一，可以断定，迭代过程 对于任意初值 均收敛。证毕。第三十五页，本课件共有76页第三十六页，本课件共有76页第三十七页，本课件共有76页第三十八页，本课件共有76页第三十九页，本课件共有76页第四十页，本课件共有76页
13、二、二、Newton迭代法及其收敛性迭代法及其收敛性 设设 是是f(x)=0的一个近似根，把的一个近似根，把f(x)在在 处作泰勒展开处作泰勒展开 若取前两项来近似代替若取前两项来近似代替f(x)(称为称为f(x)的线性化的线性化)，则得近似的，则得近似的线性方程线性方程 设设 ，令其解为，令其解为 ，得，得 （1）这称为这称为f(x)=0的牛顿迭格式。的牛顿迭格式。第四十一页，本课件共有76页它对应的迭代方程为它对应的迭代方程为 显然是显然是f(x)=0f(x)=0的同解的同解方程，方程，故其迭代函数为故其迭代函数为 在在 f(x)=0 f(x)=0的根的根 的某个邻域的某个邻域 内内,在在
14、 的邻域的邻域 R R 内，对任意初值内，对任意初值 ，应用由公式（，应用由公式（1 1）来解）来解方程的方法就称为牛顿迭代法。它是解代数方程和超越方程的方程的方法就称为牛顿迭代法。它是解代数方程和超越方程的有效方法之一。有效方法之一。第四十二页，本课件共有76页三、牛顿法的几何意义 由（由（1 1）式知）式知 是点是点 处处 的切线的切线 与与X X轴的交点的横坐标（如图）。也就轴的交点的横坐标（如图）。也就是说，新的近似值是说，新的近似值 是用代替曲线是用代替曲线y=f(x)y=f(x)的切线与的切线与x x 轴相交得到的。继续取点轴相交得到的。继续取点 ,再做切线与再做切线与x x轴相交
15、，轴相交，又可得又可得 。由图可见，只要初值取的充分靠近。由图可见，只要初值取的充分靠近 ,这个序这个序列就会很快收敛于列就会很快收敛于 。NewtonNewton迭代法又称切线法。迭代法又称切线法。第四十三页，本课件共有76页第四十四页，本课件共有76页判别判别Newton Newton 法收敛的充分条件法收敛的充分条件设设(x)在有根区间在有根区间(a,b)上存在二阶导数，且满足上存在二阶导数，且满足（1）(a)(b)0；（2），x(a,b)；（3）不变号，不变号，x(a,b)；（4）初值）初值x0 (a,b)；且使；且使 。则牛顿迭代序列则牛顿迭代序列xi收敛于收敛于 (x)=0 在在(
16、a,b)内唯一的根。内唯一的根。第四十五页，本课件共有76页四、牛顿迭代法的步骤 步一、准备。选定初始近似值步一、准备。选定初始近似值 ，计算，计算 步二、迭代。按公式步二、迭代。按公式 迭代一次，得到新的近似迭代一次，得到新的近似值值 ，计算，计算 步三、控制。如果步三、控制。如果 满足满足 或或 ，则终止迭代，则终止迭代，以以 作为所求的根；否则转步四。此处作为所求的根；否则转步四。此处 是允许误差。是允许误差。第四十六页，本课件共有76页而而 。其中。其中c是取绝对值或相对误差是取绝对值或相对误差的控制常数，一般可取的控制常数，一般可取c=1。步四、修改。如果迭代次数达到预定指定的次数步
17、四、修改。如果迭代次数达到预定指定的次数N，或者或者 则方法失败；否则以则方法失败；否则以 代替代替 转步二继续迭代。转步二继续迭代。第四十七页，本课件共有76页 五五.例题例题例例1:用牛顿法求下面方程的根用牛顿法求下面方程的根 解解 因因 ,所以迭代公式为所以迭代公式为 选取选取 ,计算结果列于计算结果列于下表下表从计算结果可以看出从计算结果可以看出,牛顿法的收敛速度是很快的牛顿法的收敛速度是很快的,进行了进行了四次迭代就得到了较满意的结果。四次迭代就得到了较满意的结果。第四十八页，本课件共有76页例例2 计算计算 的近似值。的近似值。=10-6 x0=0.88 解：解：令令x=问题转化为
18、求问题转化为求(x)=x2-0.78265=0的正根的正根由牛顿迭代公式由牛顿迭代公式 xk+1=xk-(xk)/(xk)=xk/2+0.78265/2xk 迭代结果迭代结果 k 0 1 2 3 xk 0.880000 0.884688 0.884675 0.884675 满足了精度要求。满足了精度要求。=0.884675 第四十九页，本课件共有76页六其他注意的事项（牛顿法变形）六其他注意的事项（牛顿法变形）第五十页，本课件共有76页算法和例题见算法和例题见P54P54第五十一页，本课件共有76页算法和例题见算法和例题见P55P55见参考文献见参考文献22第五十二页，本课件共有76页重根计算
19、和加速收敛见重根计算和加速收敛见P56-60P56-60第五十三页，本课件共有76页第五十四页，本课件共有76页提高牛顿法求重根的收敛阶有两种改进方法。见提高牛顿法求重根的收敛阶有两种改进方法。见P57P57。第五十五页，本课件共有76页七、牛顿迭代法的优缺点七、牛顿迭代法的优缺点1 1、优点：优点：牛顿迭代法具有牛顿迭代法具有平方收敛平方收敛的速度，所以在迭代的速度，所以在迭代过程中只要迭代几次就会得到很精确的解。这是牛顿迭代过程中只要迭代几次就会得到很精确的解。这是牛顿迭代法比不动点迭代法优越的地方。法比不动点迭代法优越的地方。2 2、缺点缺点：选定的初值要接近方程的解，否则有可能的不：选
20、定的初值要接近方程的解，否则有可能的不到收敛的结果。再者，牛顿迭代法计算量比较大。因每次到收敛的结果。再者，牛顿迭代法计算量比较大。因每次迭代除计算函数值外还要计算微商值。迭代除计算函数值外还要计算微商值。第五十六页，本课件共有76页八、八、迭代的一般概念 迭代法可分为单点迭代法与多点迭代法。单点迭代法的一般形式为：xi+1=(xi)i=0,1,2,.需一个初始点 x0启动 多点迭代法的一般形式为：xi+1=(xi，xi-1,xi-k+1)需多个初始点 x0，x1,x2,xk启动对于单点迭代：n=1第五十七页，本课件共有76页 1、求方程求方程x3+x=2x2+3在在x0=4附近的根。附近的根
21、。解：函数解：函数(x)=x3-2x2+x-3写成嵌套形式写成嵌套形式 (x)=x3-2x2+x-3=(x-2)x+1)x-3 (x)=3x2-4x+1=(3x-4)x+1计算结果如下：计算结果如下：N X N X 0 4.000000000000 4 2.175554938721 1 3.000000000000 5 2.174560100666 2 2.437500000000 6 2.174559410293 3 2.213032716315 7 2.174559410292 8 2.174559410292 例题及例题及Matlab应用应用第五十八页，本课件共有76页第五十九页，本课件
22、共有76页第六十页，本课件共有76页第六十一页，本课件共有76页P67P67作业作业3-133-13第六十二页，本课件共有76页第六十三页，本课件共有76页第六十四页，本课件共有76页第六十五页，本课件共有76页第六十六页，本课件共有76页第六十七页，本课件共有76页P67P67作业作业3-143-14第六十八页，本课件共有76页第六十九页，本课件共有76页第七十页，本课件共有76页第七十一页，本课件共有76页第七十二页，本课件共有76页第七十三页，本课件共有76页用用Matlab求求解的结果解的结果第七十四页，本课件共有76页应用实例应用实例P63P63第七十五页，本课件共有76页对上题也可直接用对上题也可直接用MatlabMatlab命令求解特征方程命令求解特征方程:第七十六页，本课件共有76页