数值分析非线性方程的数值解法;.pptx

《数值分析非线性方程的数值解法;.pptx》由会员分享，可在线阅读，更多相关《数值分析非线性方程的数值解法;.pptx（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法/*Numerical Solutions of Nonlinear Equations*/7.1方程求根与二分法7.2不动点迭代法及其收敛性7.3迭代收敛的加速方法7.4牛顿法7.5弦截法与抛物线法7.6求根问题的敏感性与多项式的零点7.7非线性方程组的数值解法第1页/共69页27.1 方程求根与二分法方程求根与二分法 7.1.1 引言（1.1）单变量非线性方程的一般形式其中也可以是无穷区间.f(x)是高次多项式函数或超越函数（1.2）如果函数是多项式函数，即其中为实数，则称方程(1.1)为次代数方程.超越函数不能表示

2、为多项式的函数如 (x)=3x5-2x4+8x2-7x+1(x)=e2x+1-xln(sinx)-2高次代数方程超越方程第2页/共69页3若是的重零点，且充分光滑，则次方程在复数域有且只有个根（含重根，重根为个根）.超越方程它在整个轴上有无穷多个解，若取值范围不同，解也不同，因此讨论非线性方程(1.1)的求解必须强调的定义域，即的求解区间如果实数满足，则称是方程(1.1)的根，或称是的零点.若可分解为其中为正整数，且则称为方程(1.1)的重根，或为的重零点，时为单根.结论第3页/共69页4通常方程根的数值解法大致分为三个步骤进行：非线性问题一般不存在直接的求解公式，要使用迭代法.本章将介绍常用

3、的求解非线性方程的近似根的几种数值解法 判定根的存在性。即方程有没有根？如果有根，有几个根？判定根的存在性。即方程有没有根？如果有根，有几个根？确定根的分布范围。即将每一个根用区间隔离开来，这个过程实际上是获确定根的分布范围。即将每一个根用区间隔离开来，这个过程实际上是获得方程各根的初始近似值。得方程各根的初始近似值。根的精确化。将根的初始近似值按某种方法逐步精确化，直到满足预先要根的精确化。将根的初始近似值按某种方法逐步精确化，直到满足预先要求的精度为止求的精度为止.第4页/共69页5如何求方程的有根区间？设 f(x)Ca,b,且 f(a)f(b)0,存在(a,b)，使 f()=0.根的存在

4、性定理闭区间上连续函数的介值定理有根区间如果f(x)在a,b上还是单调递增或递减的，则f(x)=0仅有一个实根。(1)描图法画出y=f(x)的略图，从而看出曲线与x轴交点的大致位置。也可将f(x)=0等价变形为g1(x)=g2(x)的形式，y=g1(x)与y=g2(x)两曲线交点的横坐标所在的子区间即为含根区间。例1 求方程3x-1-cosx=0的有根区间。方程等价变形为3x-1=cosx，y=3x-1与y=cosx的图像只有一个交点位于0.5，1内。第5页/共69页6对的根进行搜索计算，例2求方程的有根区间.由此可知方程的有根区间为(2)逐步搜索法 先确定方程f(x)=0的所有实根所在的区间

5、为a,b,从x0=a 出发,以步长 h=(b-a)/n 其中n是正整数，在a,b内取定节点：xi=x0ih (i=0,1,2，n)计算f(xi)的值,依据函数值异号及实根的个数确定有根区间,通过调整步长，总可找到所有有根区间。解第6页/共69页77.1.2 二分法求解方程f(x)=0的近似根的一种常用的简单方法。原理基本思想设函数f(x)在闭区间a,b上连续,且f(a)f(b)0,则 f(x)=0在(a,b)内必有实根区间。逐步将区间二等分,通过判断区间端点f(x)的符号,逐步将有根区间缩小,直至有根区间足够地小,便可求出满足精度要求的近似根。具体做法第7页/共69页8以此类推由二分法的过程知

6、(1)(2)(3)作为根的近似可得一个近似根的序列第8页/共69页9（1.3）且(4)只要二分足够多次（即充分大），便有这里为预定的精度.要使解：例3 用二分法求方程 在区间 上的根，误差限为 ，问至少需对分多少次？第9页/共69页10二分法的算法步骤1准备计算在有根区间端点处的值步骤2二分计算在区间中点处的值步骤3判断若，则即是根，计算过程结束，否则检验.若，则以代替，否则以代替.此时中点即为所求近似根.误差，反复执行步骤2和步骤3，直到区间长度小于允许第10页/共69页11第11页/共69页12例4求方程在区间内的一个实根，要求准确到小数点后第2位.欲使只需，即只要二分6次，便能达到预定的

7、精度.解得到新的有根区间第12页/共69页13二分法对多个零点的情况，只能算出其中一个零点。即使 f(x)在a,b上有零点，也未必有 f(a)f(b)0。不管有根区间多大,总能求出满足精度要求的根,且对函数f(x)的要求不高,只要连续即可,计算亦简单。优点缺点注：注：用二分法求根，最好先给出 f(x)草图以确定根的大概位置。或用搜索程序，将a,b分为若干小区间，对每一个满足 f(ak)f(bk)0 的区间调用二分法程序，可找出区间a,b内的多个根，且不必要求 f(a)f(b)0。第13页/共69页147.2 不动点迭代法及其收敛性不动点迭代法及其收敛性 7.2.1 不动点与不动点迭代法/*Fi

8、xed-PointIteration*/（2.1）若满足，则；反之亦然，称为函数的一个不动点.求 的零点就等价于求 的不动点.基本思想（2.2）称为迭代函数.得到的序列有极限如果对任何，由迭代不动点迭代法第14页/共69页15则称迭代法收敛，且为的不动点，不动点迭代是一种逐次逼近的方法,用某个固定公式反复校正根的近似值,使之逐步精确化，最后得到满足精度要求的结果。对预先给定的精度要求，只要某个k满足即可结束计算并取 迭代终止的判定第15页/共69页16几何意义 交点的横坐标 y=x第16页/共69页17xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)

9、y=g(x)x0p0 x1p1x0p0 x1p1x0p0 x1p1x0p0 x1p1第17页/共69页18 例5求方程（2.3）在附近的根设将方程改写成建立迭代公式解各步迭代的结果如下表即为所求的根.如果仅取6位数字，结果与完全相同，发散说明：迭代函数不唯一，迭代点列可能收敛，也可能发散，迭代收敛与否不仅与迭代函数有关，还与初始点有关。第18页/共69页197.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性 不动点的存在唯一性定理 定理1设满足以下两个条件：1.对任意有2.存在正常数，使对任意都有（2.4）则在上存在唯一的不动点证明存在性 若或，则不动点为或，因，以下设及

10、，定义函数显然，且由零点定理知存在,使,即第19页/共69页20唯一性设都是的不动点，故的不动点是唯一的.则由即为的不动点.得矛盾.（2.5）定理2设满足定理1中的两个条件，则对任意，由得到的迭代序列收敛到的不动点，并有误差估计L 越收敛越快小事前估计：选取k，预先估计迭代次数。第20页/共69页21证明设是在上的唯一不动点，由条件，可知因，故当时序列收敛到.又由误差估计收敛性由（2.6）得反复递推得第21页/共69页22迭代过程的控制只要相邻两次计算结果的偏差足够小，即可保证近似值具有足够精度.事后估计事前估计：选取k，预先估计迭代次数。注：定理1、2的条件(2)可替换为（2.7）如果且对任

11、意有则由中值定理可知对有第22页/共69页23例5又因，而当时，在区间中不满足定理条件.当时，在区间中，所以迭代法是收敛的.第23页/共69页247.2.3 局部收敛性与收敛阶局部收敛性与收敛阶 迭代序列在区间上的收敛性，全局收敛性 定义1设有不动点,如果存在的某个邻域对任意，迭代产生的序列且收敛到，则称迭代法局部收敛.定理3设为的不动点，在的某个邻域连续，且，则迭代法局部收敛.局部收敛性证明由连续函数的性质，存在的某个邻域使对于任意成立所以，对于任意，总有。因为第24页/共69页25迭代序列的收敛速度 例6用不同方法求方程的根 解 构造不同的迭代法第25页/共69页26取，对上述4种迭代法，

12、计算三步所得的结果如下表.从计算结果看到迭代法（1）及（2）均不收敛，且它们均不满足定理3中的局部收敛条件.注意.迭代法（3）和（4）均满足局部收敛条件，且迭代法（4）比（3）收敛快，因在迭代法（4）中.第26页/共69页27 求方程xex-1=0在0.5附近的根,精度要求=10-3。可以验证方程xex-1=0在区间0.5,0.61内仅有一个根。例例7 改写方程为x=e-x,建立迭代格式 由于(x)=e-x,在0.5,0.61上有|(x)|e-0.50.6 1，且(x)0.5,0.61，所以迭代法收敛。取x0=0.5,得kxk|xk-xk-1|kxk|xk-xk-1|0123450.50.60

13、6530.545240.579700.560060.571170.106530.061290.034460.019640.011116789100.564860.568440.566410.567560.566910.006310.003580.002030.001150.00065 解 第27页/共69页28 所以,取近似根x10=0.56691满足精度要求。如果精度要求为=10-5,则由可知,需要迭代20次。实际上,方程在区间0.55,0.6上有唯一根，而在区间0.55,0.6上有|(x)|e-0.550.581)阶收敛的方法，改用Stefensen迭代方法优点不多。第38页/共69页39

14、7.4 牛顿法牛顿法 7.4.1 牛顿法及其收敛性 设已知方程有近似根（假定)，将函数在点展开，有于是方程可近似地表示为（4.1）这是个线性方程，记其根为，则的计算公式为（4.2）牛顿法第39页/共69页40几何意义切线法收敛性（4.2）xyx*x0只要 f C1，每一步迭代都有f(xk)0，而 ，则 x*就是 f 的根。迭代函数假定是的一个单根，即，则由上式知局部平方收敛（4.3）第40页/共69页41注：注：Newtons Method 收敛性依赖于x0 的选取。x*x0 x0 x06.1.4 牛顿迭代法第41页/共69页42例10用牛顿法解方程（4.4）解取迭代初值，迭代结果列于表7-7

15、中.所给方程（4.4）实际上是方程的等价形式.牛顿公式为若用不动点迭代到同一精度要迭代17次.可见牛顿法的收敛速度是很快的.第42页/共69页43牛顿法的计算步骤：步骤1准备选定初始近似值，计算步骤2迭代按公式迭代一次，得新的近似值，计算步骤3控制如果满足或，则终止迭代，以作为所求的根；否则转步骤4.此处是允许误差，而其中是取绝对误差或相对误差的控制常数，一般可取步骤4修改如果迭代次数达到预先指定的次数，或者，则方法失败；否则以代替转步骤2继续迭代.第43页/共69页44 7.4.2 牛顿法应用举例 对于给定的正数，应用牛顿法解二次方程可导出求开方值的计算程序（4.5）这个迭代公式对于任意初值

16、都是收敛的.配方两式相除反复递推（4.6）第44页/共69页45取初值，对按(4.5)式迭代3次便得到精度为的结果（见表7-8).例11求.解由于公式（4.5）对任意初值均收敛，并且收敛的速度很快，因此可取确定的初值如编成通用程序.第45页/共69页46 7.4.3 简化牛顿法与牛顿下山法简化牛顿法与牛顿下山法 牛顿法的改进牛顿法的改进每步迭代要计算及.牛顿法的变形(1)简化牛顿法-平行弦法（4.7）迭代函数初始近似只在根附近才能保证收敛.优点缺点收敛快若在根附近成立，该迭代法局部收敛.取-简化牛顿法第46页/共69页47用平行弦与轴交点作为的近似.图7-5oxyy=(x)xx0 x1x2x3

17、几何意义(2)牛顿下山法牛顿法求方程在附近的一个根.设取迭代初值，用牛顿法公式（4.9）计算迭代3次得到的结果有6位有效数字.第47页/共69页48这个结果反而比更偏离了所求的根.附加要求（4.10）满足这项要求的算法称下山法.保证函数值稳定下降牛顿法的计算结果前一步的近似值（4.11）其中称为下山因子，（4.12）牛顿下山法xkxk+1第48页/共69页49从开始，逐次将减半进行试算，直到能使下降条件成立为止.下山因子的选取当时求得，通过逐次取半进行试算，当时可求得此时有，而不满足条件显然.由计算时,均能使下山条件成立.（4.12）第49页/共69页50计算结果：即为的近似.下山条件成立，可

18、得到，从而使收敛.第50页/共69页51 7.4.4 重根情形重根情形 设，整数，则为方程的重根，此时有设导数且，则.牛顿法的改进 迭代法（4.13）局部线性收敛牛顿法迭代函数求重根，至少有2阶收敛，知道的重数第51页/共69页52令若是的重根，则迭代法（4.14）至少2阶收敛.故是的单根.牛顿法改进求重根迭代法的改进迭代函数为第52页/共69页53 例12方程的根是二重根，用上述三种方法求根.解（1）牛顿法（2）用（4.13）式（3）用（4.14）式取初值，计算结果如表7-9.（4.13）（4.14）第53页/共69页54从结果看出，经过三步计算，方法（2）及（3）均达到10位有效数字，而由

19、于牛顿法只有线性收敛，所以要达到同样精度需迭代30次.第54页/共69页557.5 弦截法与抛物线法弦截法与抛物线法 计算较困难每步迭代要计算及.缺点7.5.1 弦截法设是的近似根，利用构造一次插值多项式，并用的根作为新的近似根.（5.1）由有（5.2）牛顿公式中的导数用差商取代的结果.第55页/共69页56几何意义曲线上横坐标为的点分别记为，则弦线的斜率等于差商值,其方程为按（5.2)式求得的实际上是弦线与轴交点的横坐标.这种算法因此而称为弦截法.表7-6第56页/共69页57而弦截法（5.2），在求时要用到前面两步的结果，弦截法与切线法的区别切线法在计算时只用到前一步的值.因此使用这种方法

20、必须先给出两个开始值.例12用弦截法解方程设取作为开始值，用弦截法求得的结果见表7-10，解弦截法的收敛速度也是相当快的第57页/共69页58这里是方程的正根.定理6假设在根的邻域内具有二阶连续导数，且对任意有，又初值那么当邻域充分小时，弦截法（5.2）将按阶收敛到根.（5.2）第58页/共69页59设已知方程的三个近似根，几何上，这种方法的基本思想是用抛物线与轴的交点作为所求根的近似位置（图7-7).图7-7以这三点为节点构造二次插值多项式，的一个零点作为新的近似根，并适当选取密勒（Mller）法 7.5.2 抛物线法 插值多项式 第59页/共69页60有两个零点：（5.3）式中问题是该如何

21、确定.假定在三个近似根中，更接近所求的根.为了保证精度，选（5.3）中较接近的一个值作为新的近似根.为此，只要取根式前的符号与的符号相同.第60页/共69页61例13用抛物线法求解方程设用表7-10的前三个值作为开始值，计算得解故代入（5.3）式求得第61页/共69页62以上计算表明，抛物线法比弦截法收敛得更快.在一定条件下可以证明，对于抛物线法，迭代误差有下列渐近关系式从（5.3）看到，即使均为实数，也可以是复数，所以抛物线法适用于求多项式的实根和复根.可见抛物线法也是超线性收敛的，其收敛的阶,收敛速度比弦截法更接近于牛顿法.第62页/共69页637.6 求根问题的敏感性与多项式的零点7.6

22、.1 求根问题的敏感性与病态代数方程 7.6.2 多项式的零点（6.5）牛顿法求出一个根利用秦九韶算法计算及的值.牛顿法计算到，则得到.再求的一个根，,如此反复直到求出全部个根.第63页/共69页64一般地，这里为二次多项式，在此过程中当增加时不精确性也增加，为了解决此困难可通过原方程的牛顿法改进的结果.若是复根，使用抛物线法更有利.若为复根，记，则也是一个根，于是是的一个二次因子，于是是阶多项式，可降低二阶.第64页/共69页65例求的全部零点.先用抛物线法求方程的根，取计算到为止.结果见表7-11.解第65页/共69页66求得根为，再由可求得另外两根为可对原方程，以此两根为初值，用牛顿法迭代一次可得到更精确的根从而可得第66页/共69页67转化为求矩阵的特征值问题求多项式零点.利用计算矩阵特征值方法求矩阵的全部特征值，则可得到方程的全部根，MATLAB中的roots函数使用的就是这种方法.的特征多项式，第67页/共69页68作业 (1)P238 1,2,3 (2)P238 5,8 (3)P238 7,9,12 第68页/共69页69感谢您的观看。第69页/共69页