非线性方程求根 (3)优秀课件.ppt

《非线性方程求根 (3)优秀课件.ppt》由会员分享，可在线阅读，更多相关《非线性方程求根 (3)优秀课件.ppt（76页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、非线性方程求根第1页，本讲稿共76页一、一、问题的提出问题的提出二、二、有关概念有关概念三、三、二分法原理二分法原理四、收敛性分析四、收敛性分析五、五、二分法的优缺点二分法的优缺点六、六、例题求解例题求解七、七、原理概述原理概述第3章：非线性方程求根 -二分法第2页，本讲稿共76页一、问题的提出 函数方程函数方程 f f（x x）=0 (1)=0 (1)若f(x)不是x的线性函数，则称(1)为非线性方非线性方程，特别若f(x)是n次多项式，则称(1)为n次多项式方程或代数方程；若f(x)是超越函数，则称(1)为超越方程。第3页，本讲稿共76页第4页，本讲稿共76页 求根问题包括：根的存在性、根

2、的范围和根的精确化。定义收敛阶：设迭代过程 收敛于方程 的根 如果迭代误差 满足极限式：(c是不为零的常数,p0)则称该迭代过程是P阶收敛的。特别地，P=1时称线性收敛，P 1时称超线性收敛，P=2时称平方收敛。二、有关概念第5页，本讲稿共76页有关概念有关概念(续续)单根和重根单根和重根第6页，本讲稿共76页有关概念有关概念(续续)例例3-13-1第7页，本讲稿共76页第8页，本讲稿共76页 三、二分法原理 给定方程f(x)=0,设f(x)在区间a,b连续,且f(a)f(b)0,则方程f(x)=0在(a,b)内至少有一根,为便于讨论,不妨设方程f(x)=0在(a,b)内只有一实根 ，采取使有

3、根区间逐步缩小,从而得到满足精度要求的实根 的近似值 。第9页，本讲稿共76页第10页，本讲稿共76页第11页，本讲稿共76页第12页，本讲稿共76页 第13页，本讲稿共76页 四、收敛性分析 现在来研究用二分法求方程的根的精确性。假定f(x)是连续函数,并且它在区间a0.b0的两端点所取的值有相反的符号,于是在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,

4、.由于这些区间的宽度在每一步中都除以2,所以可断定r-cn 可见经过n步后将算出一个近似根，其误差至多为 。第14页，本讲稿共76页 五、二分法的优缺点 二分法计算过程简单，程序容易实现。但在大范围内求根时，该方法收敛较慢，且不能求偶数重根和复根，一般用于求根的初始近似值，而后在使用其它的求根方法。二分法收敛速度不快，其收敛速度仅与一个以 1/2为比值的等比级数相同。第15页，本讲稿共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

5、=(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第16页，本讲稿共76页第17页，本讲稿共76页第18页，本讲稿共76页 七、原理阐述七、原理阐述 如果我们把二分法与跨步区间法结合起来如果我们把二分法与跨步区间法结合起来,就可以求非就可以求非线性方程在任一区间上的全部实根。线性方程在任一区间上的全部实根。首先首先,将方程式将方程式f(x)=0f(x)=0化为函数式化为函数式

6、y=f(x).y=f(x).假设方程求假设方程求解区间为解区间为x x a,b,a,b,跨步区间为跨步区间为h h长长,允许误差为允许误差为。如图如图3 3所示。所示。由由a a点出发向点出发向 b b点跨步点跨步,每跨一步每跨一步h,h,经过判断在该区经过判断在该区间内是否有根。如有根则进行二分法求根计算间内是否有根。如有根则进行二分法求根计算,否则继否则继续以续以h h为步长向前跨步找根为步长向前跨步找根,直到走出区间直到走出区间a,ba,b为止为止 。这样这样,我们就可以按顺序将方程的全部我们就可以按顺序将方程的全部实根找出。实根找出。第19页，本讲稿共76页第20页，本讲稿共76页 y

7、 x a b o 图3 第21页，本讲稿共76页解解 因为 所以二分6次，可满足精度要求要 只需 即 第22页，本讲稿共76页 迭代法是求解非线性方程近似根的一种方法，这种方法的关键是确定迭代函数g(x)，不动点迭代法用直接的方法从原方程中隐含的求出x，从而确定迭代函数g(x)，这种迭代法收敛速度较慢，迭代次数多，因此常用于理论中，Newton迭代法采用另一种迭代格式，具有较快的收敛速度，由牛顿迭代法可以得到很多其它迭牛顿迭代法可以得到很多其它迭代格式代格式。第第3章：非线性方程求根章：非线性方程求根 -迭代法迭代法第23页，本讲稿共76页一、不动点迭代法的概念与收敛性一、不动点迭代法的概念与

8、收敛性二、二、NewtonNewton迭代法及其收敛性迭代法及其收敛性三、牛顿法的几何意义三、牛顿法的几何意义四、牛顿迭代法的步骤四、牛顿迭代法的步骤五、例题五、例题六、其他注意的事项（牛顿法变形）六、其他注意的事项（牛顿法变形）七、牛顿迭代法的优缺点七、牛顿迭代法的优缺点八、迭代的一般概念八、迭代的一般概念主要内容主要内容第24页，本讲稿共76页一、不动点迭代法的概念与收敛性不动点迭代法的概念与收敛性 不动点迭代法又称逐次迭代法，基本思想是构造不动点迭代法又称逐次迭代法，基本思想是构造不动点方程，以求得近似根。即由方程不动点方程，以求得近似根。即由方程f(x)=0f(x)=0变换变换为为x=

9、x=g(x)g(x),然后建立迭代格式，然后建立迭代格式，当给定处值当给定处值x x0 0 后后,由迭代格式可求得数列由迭代格式可求得数列xxk k。如果如果xxk k 收敛于收敛于x x*，则它就是方程的根。因为：，则它就是方程的根。因为：但迭代格式有多种，迭代格式如何建立才能保证迭但迭代格式有多种，迭代格式如何建立才能保证迭代法的数列收敛？代法的数列收敛？例3-4,方程与例3-2相同第25页，本讲稿共76页第26页，本讲稿共76页什么原因？什么原因？第27页，本讲稿共76页定理一：假定函数 ，满足下列条件：1、对任意 有 ；（映内性）(1.1)2、存在正数 L1，使对任意 有 （压缩性）(

10、1.2)则迭代过程 对于任意初值 均收敛于方程 的根 ，且有如下的误差估计式：(1.3)实用中(1.2)式常用 第28页，本讲稿共76页第29页，本讲稿共76页证明：设方程 在区间 根为 ，则有 由故据此反复递推有第30页，本讲稿共76页故当 时迭代值按(1.2)式 有 (1.4)，据此反复递推得：于是对任意正整数p有 在上式令 ，注意到 即得式(1.3)。证毕。第31页，本讲稿共76页第32页，本讲稿共76页第33页，本讲稿共76页定义一：如果存在 的某个邻域 ，使迭代过程 对于任意初值 均收敛，则称迭代过程 在根 邻近具有局部收敛性。定理二：设 为方程 的根，在 的邻近连续。则迭代过程在

11、邻近具有局部收敛性。第34页，本讲稿共76页证明：由连续函数的性质，存在 的某个邻域 ，使对于任意 成立 此外,对于任意 总有 。这是因为 依据定理一，可以断定，迭代过程 对于任意初值 均收敛。证毕。第35页，本讲稿共76页第36页，本讲稿共76页第37页，本讲稿共76页第38页，本讲稿共76页第39页，本讲稿共76页第40页，本讲稿共76页二、二、Newton迭代法及其收敛性迭代法及其收敛性 设设 是是f(x)=0的一个近似根，把的一个近似根，把f(x)在在 处作泰勒展开处作泰勒展开 若取前两项来近似代替若取前两项来近似代替f(x)(称为称为f(x)的线性化的线性化)，则得近似的线，则得近似

12、的线性方程性方程 设设 ，令其解为，令其解为 ，得，得 （1）这称为这称为f(x)=0的牛顿迭格式。的牛顿迭格式。第41页，本讲稿共76页它对应的迭代方程为 显然是f(x)=0的同解方程，故其迭代函数为 在 f(x)=0的根 的某个邻域 内,在 的邻域 R 内，对任意初值 ，应用由公式（1）来解方程的方法就称为牛顿迭代法。它是解代数方程和超越方程的有效方法之一。第42页，本讲稿共76页三、牛顿法的几何意义 由（由（1 1）式知）式知 是点是点 处处 的切线的切线 与与X X轴的交点的横坐标（如图）。也就是轴的交点的横坐标（如图）。也就是说，新的近似值说，新的近似值 是用代替曲线是用代替曲线y=

13、f(x)y=f(x)的切线与的切线与x x 轴相交轴相交得到的。继续取点得到的。继续取点 ,再做切线与再做切线与x x轴相交，又可得轴相交，又可得 。由图可见，只要初值取的充分靠近。由图可见，只要初值取的充分靠近 ,这个序列就会很快这个序列就会很快收敛于收敛于 。NewtonNewton迭代法又称切线法。迭代法又称切线法。第43页，本讲稿共76页第44页，本讲稿共76页判别判别Newton Newton 法收敛的充分条件法收敛的充分条件设(x)在有根区间(a,b)上存在二阶导数，且满足（1）(a)(b)0；（2），x(a,b)；（3）不变号，x(a,b)；（4）初值x0(a,b)；且使 。则牛

14、顿迭代序列xi收敛于(x)=0 在(a,b)内唯一的根。第45页，本讲稿共76页四、牛顿迭代法的步骤 步一、准备。选定初始近似值步一、准备。选定初始近似值 ，计算，计算 步二、迭代。按公式步二、迭代。按公式 迭代一次，得到新的近似值迭代一次，得到新的近似值 ，计算，计算 步三、控制。如果步三、控制。如果 满足满足 或或 ，则终止迭代，则终止迭代，以以 作为所求的根；否则转步四。此处作为所求的根；否则转步四。此处 是允许误差。是允许误差。第46页，本讲稿共76页而 。其中c是取绝对值或相对误差的控制常数，一般可取c=1。步四、修改。如果迭代次数达到预定指定的次数N，或者 则方法失败；否则以 代替

15、 转步二继续迭代。第47页，本讲稿共76页 五.例题例1:用牛顿法求下面方程的根 解 因 ,所以迭代公式为 选取 ,计算结果列于下表从计算结果可以看出,牛顿法的收敛速度是很快的,进行了四次迭代就得到了较满意的结果。第48页，本讲稿共76页例例2 计算计算 的近似值。的近似值。=10-6 x0=0.88 解：解：令令x=问题转化为求问题转化为求(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.88467

16、5 满足了精度要求。满足了精度要求。=0.884675 第49页，本讲稿共76页六其他注意的事项（牛顿法变形）六其他注意的事项（牛顿法变形）第50页，本讲稿共76页算法和例题见算法和例题见P54P54第51页，本讲稿共76页算法和例题见算法和例题见P55P55见参考文献见参考文献22第52页，本讲稿共76页重根计算和加速收敛见重根计算和加速收敛见P56-60P56-60第53页，本讲稿共76页第54页，本讲稿共76页提高牛顿法求重根的收敛阶有两种改进方法。见提高牛顿法求重根的收敛阶有两种改进方法。见P57P57。第55页，本讲稿共76页七、牛顿迭代法的优缺点七、牛顿迭代法的优缺点1 1、优点：

17、优点：牛顿迭代法具有牛顿迭代法具有平方收敛平方收敛的速度，所以在迭代过的速度，所以在迭代过程中只要迭代几次就会得到很精确的解。这是牛顿迭代法比程中只要迭代几次就会得到很精确的解。这是牛顿迭代法比不动点迭代法优越的地方。不动点迭代法优越的地方。2 2、缺点缺点：选定的初值要接近方程的解，否则有可能的不到：选定的初值要接近方程的解，否则有可能的不到收敛的结果。再者，牛顿迭代法计算量比较大。因每次迭收敛的结果。再者，牛顿迭代法计算量比较大。因每次迭代除计算函数值外还要计算微商值。代除计算函数值外还要计算微商值。第56页，本讲稿共76页八、迭代的一般概念 迭代法可分为单点迭代法与多点迭代法。单点迭代法

18、的一般形式为：xi+1=(xi)i=0,1,2,.需一个初始点 x0启动 多点迭代法的一般形式为：xi+1=(xi，xi-1,xi-k+1)需多个初始点 x0，x1,x2,xk启动对于单点迭代：n=1第57页，本讲稿共76页 1、求方程x3+x=2x2+3在x0=4附近的根。解：函数(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.

19、437500000000 6 2.174559410293 3 2.213032716315 7 2.174559410292 8 2.174559410292 例题及Matlab应用第58页，本讲稿共76页第59页，本讲稿共76页第60页，本讲稿共76页第61页，本讲稿共76页P67P67作业作业3-133-13第62页，本讲稿共76页第63页，本讲稿共76页第64页，本讲稿共76页第65页，本讲稿共76页第66页，本讲稿共76页第67页，本讲稿共76页P67P67作业作业3-143-14第68页，本讲稿共76页第69页，本讲稿共76页第70页，本讲稿共76页第71页，本讲稿共76页第72页，本讲稿共76页第73页，本讲稿共76页用用Matlab求解的求解的结果结果第74页，本讲稿共76页应用实例应用实例P63P63第75页，本讲稿共76页对上题也可直接用对上题也可直接用MatlabMatlab命令求解特征方程命令求解特征方程:第76页，本讲稿共76页