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

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

1、117991799年，高斯证明了代数方程必有一个实根或复根的定年，高斯证明了代数方程必有一个实根或复根的定理，称此为代数基本定理，并由此可以立刻推理理，称此为代数基本定理，并由此可以立刻推理n n次代数次代数方程必有方程必有n n个实根或复根。个实根或复根。但在以后的几十年中仍然没有找出高次代数方程的公式但在以后的几十年中仍然没有找出高次代数方程的公式解。一直到解。一直到1818世纪，法国数学家拉格朗日用根置换方法世纪，法国数学家拉格朗日用根置换方法统一了二、三、四方程的解法。统一了二、三、四方程的解法。但求解五次方程时未能如愿但求解五次方程时未能如愿,开始意识到有潜藏其中的奥开始意识到有潜藏

2、其中的奥妙妙,用现代术语表示就是置换群理论问题。用现代术语表示就是置换群理论问题。在继续探索在继续探索5 5次以上方程解的艰难历程中，第一个重大突次以上方程解的艰难历程中，第一个重大突破的是挪威数学家阿贝尔破的是挪威数学家阿贝尔(N(NAbel1802-1829)1824Abel1802-1829)1824年年阿贝尔发表了阿贝尔发表了“五次方程代数解法不可能存在五次方程代数解法不可能存在”的论文，的论文，但并未受到重视，连数学大师高斯也未理解这项成果的但并未受到重视，连数学大师高斯也未理解这项成果的重要意义。重要意义。第1页/共73页21828年年17岁的法国数学家伽罗华岁的法国数学家伽罗华(

3、EGalois 1811-1832)写出了划时代的论文写出了划时代的论文“关于五次方程的代数解法关于五次方程的代数解法问题问题”，指出即使在公式中容许用，指出即使在公式中容许用n次方根，并用类似算次方根，并用类似算法求五次或更高次代数方程的根是不可能的法求五次或更高次代数方程的根是不可能的文章呈交法兰西科学院后，因辈份太低遭到冷遇，且文文章呈交法兰西科学院后，因辈份太低遭到冷遇，且文稿丢失。稿丢失。1830年伽罗华再进科学院递稿，得到泊松院士年伽罗华再进科学院递稿，得到泊松院士的判词的判词“完全不能理解完全不能理解”。后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈后来伽罗华命运不佳，投考名校

4、巴黎工科大学落榜，屈就高等师院，并卷入政事两次入狱，被开除学籍，又决就高等师院，并卷入政事两次入狱，被开除学籍，又决斗受伤，死于斗受伤，死于1832年。决斗前，他把关于五次代数求解年。决斗前，他把关于五次代数求解的研究成果写成长信，留了下来。的研究成果写成长信，留了下来。第2页/共73页3十四年后，法国数学家刘维尔十四年后，法国数学家刘维尔(JLiouville)整理并发整理并发表了伽罗华的遗作，人们才意识到这项近代数学发展史表了伽罗华的遗作，人们才意识到这项近代数学发展史上的重要成果的宝贵。上的重要成果的宝贵。38年后，即年后，即1870年，法国数学家若当年，法国数学家若当(CJordan)

5、在在专著专著论置换与代数方程论置换与代数方程中阐发了伽罗华的思想，一中阐发了伽罗华的思想，一门现代数学的分支门现代数学的分支群论诞生了。群论诞生了。在前几个世纪中，曾开发出一些求解代数方程的有效算在前几个世纪中，曾开发出一些求解代数方程的有效算法，它们构成了数值分析中的古典算法。至于超越方程法，它们构成了数值分析中的古典算法。至于超越方程则不存在一般的求根方式。则不存在一般的求根方式。第3页/共73页4在科学研究的数学问题中更多的是非线性问题，它们又常常归结为非线性方程或非线性方程组的求解问题。第4页/共73页5第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法/*Num

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

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

8、几个根？判定根的存在性。即方程有没有根？如果有根，有几个根？确定根的分布范围。即将每一个根用区间隔离开来，这个过程实际上是获确定根的分布范围。即将每一个根用区间隔离开来，这个过程实际上是获得方程各根的初始近似值。得方程各根的初始近似值。根的精确化。将根的初始近似值按某种方法逐步精确化，直到满足预先要根的精确化。将根的初始近似值按某种方法逐步精确化，直到满足预先要求的精度为止求的精度为止.第8页/共73页9如何求方程的有根区间？设 f(x)Ca,b,且 f(a)f(b)0,存在(a,b)，使 f()=0.根的存在性定理闭区间上连续函数的介值定理有根区间如果f(x)在a,b上还是单调递增或递减的，

9、则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内。第9页/共73页10对的根进行搜索计算，例2求方程的有根区间.由此可知方程的有根区间为(2)逐步搜索法 先确定方程f(x)=0的所有实根所在的区间为a,b,从x0=a 出发,以步长 h=(b-a)/n 其中n是正整数，在a,b内

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

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

12、，只能算出其中一个零点。即使 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。第17页/共73页187.2 不动点迭代法及其收敛性不动点迭代法及其收敛性 7.2.1 不动点与不动点迭代法/*Fixed-PointIteration*/（2.1）若满足，则；反之亦

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

14、0p0 x1p1第21页/共73页22 例5求方程（2.3）在附近的根设将方程改写成建立迭代公式解各步迭代的结果如下表即为所求的根.如果仅取6位数字，结果与完全相同，发散说明：迭代函数不唯一，迭代点列可能收敛，也可能发散，迭代收敛与否不仅与迭代函数有关，还与初始点有关。第22页/共73页237.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性 不动点的存在唯一性定理 定理1设满足以下两个条件：1.对任意有2.存在正常数，使对任意都有（2.4）则在上存在唯一的不动点证明存在性 若或，则不动点为或，因，以下设及，定义函数显然，且由零点定理知存在,使,即第23页/共73页24唯一

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

16、间中不满足定理条件.当时，在区间中，所以迭代法是收敛的.第27页/共73页287.2.3 局部收敛性与收敛阶局部收敛性与收敛阶 迭代序列在区间上的收敛性，全局收敛性 定义1设有不动点,如果存在的某个邻域对任意，迭代产生的序列且收敛到，则称迭代法局部收敛.定理3设为的不动点，在的某个邻域连续，且，则迭代法局部收敛.局部收敛性证明由连续函数的性质，存在的某个邻域使对于任意成立所以，对于任意，总有。因为第28页/共73页29迭代序列的收敛速度 例6用不同方法求方程的根 解 构造不同的迭代法第29页/共73页30取，对上述4种迭代法，计算三步所得的结果如下表.从计算结果看到迭代法（1）及（2）均不收敛

17、，且它们均不满足定理3中的局部收敛条件.注意.迭代法（3）和（4）均满足局部收敛条件，且迭代法（4）比（3）收敛快，因在迭代法（4）中.第30页/共73页31 求方程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.606530.545240.579700.560060.571170.1

18、06530.061290.034460.019640.011116789100.564860.568440.566410.567560.566910.006310.003580.002030.001150.00065 解 第31页/共73页32 所以,取近似根x10=0.56691满足精度要求。如果精度要求为=10-5,则由可知,需要迭代20次。实际上,方程在区间0.55,0.6上有唯一根，而在区间0.55,0.6上有|(x)|e-0.550.581)阶收敛的方法，改用Stefensen迭代方法优点不多。第42页/共73页437.4 牛顿法牛顿法 7.4.1 牛顿法及其收敛性 设已知方程有近似

19、根（假定)，将函数在点展开，有于是方程可近似地表示为（4.1）这是个线性方程，记其根为，则的计算公式为（4.2）牛顿法第43页/共73页44几何意义切线法收敛性（4.2）xyx*x0只要 f C1，每一步迭代都有f(xk)0，而 ，则 x*就是 f 的根。迭代函数假定是的一个单根，即，则由上式知局部平方收敛（4.3）第44页/共73页45注：注：Newtons Method 收敛性依赖于x0 的选取。x*x0 x0 x06.1.4 牛顿迭代法第45页/共73页46例10用牛顿法解方程（4.4）解取迭代初值，迭代结果列于表7-7中.所给方程（4.4）实际上是方程的等价形式.牛顿公式为若用不动点迭

20、代到同一精度要迭代17次.可见牛顿法的收敛速度是很快的.第46页/共73页47牛顿法的计算步骤：步骤1准备选定初始近似值，计算步骤2迭代按公式迭代一次，得新的近似值，计算步骤3控制如果满足或，则终止迭代，以作为所求的根；否则转步骤4.此处是允许误差，而其中是取绝对误差或相对误差的控制常数，一般可取步骤4修改如果迭代次数达到预先指定的次数，或者，则方法失败；否则以代替转步骤2继续迭代.第47页/共73页48 7.4.2 牛顿法应用举例 对于给定的正数，应用牛顿法解二次方程可导出求开方值的计算程序（4.5）这个迭代公式对于任意初值都是收敛的.配方两式相除反复递推（4.6）第48页/共73页49取初

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

22、牛顿法公式（4.9）计算迭代3次得到的结果有6位有效数字.第51页/共73页52这个结果反而比更偏离了所求的根.附加要求（4.10）满足这项要求的算法称下山法.保证函数值稳定下降牛顿法的计算结果前一步的近似值（4.11）其中称为下山因子，（4.12）牛顿下山法xkxk+1第52页/共73页53从开始，逐次将减半进行试算，直到能使下降条件成立为止.下山因子的选取当时求得，通过逐次取半进行试算，当时可求得此时有，而不满足条件显然.由计算时,均能使下山条件成立.（4.12）第53页/共73页54计算结果：即为的近似.下山条件成立，可得到，从而使收敛.第54页/共73页55 7.4.4 重根情形重根情

23、形 设，整数，则为方程的重根，此时有设导数且，则.牛顿法的改进 迭代法（4.13）局部线性收敛牛顿法迭代函数求重根，至少有2阶收敛，知道的重数第55页/共73页56令若是的重根，则迭代法（4.14）至少2阶收敛.故是的单根.牛顿法改进求重根迭代法的改进迭代函数为第56页/共73页57 例12方程的根是二重根，用上述三种方法求根.解（1）牛顿法（2）用（4.13）式（3）用（4.14）式取初值，计算结果如表7-9.（4.13）（4.14）第57页/共73页58从结果看出，经过三步计算，方法（2）及（3）均达到10位有效数字，而由于牛顿法只有线性收敛，所以要达到同样精度需迭代30次.第58页/共7

24、3页597.5 弦截法与抛物线法弦截法与抛物线法 计算较困难每步迭代要计算及.缺点7.5.1 弦截法设是的近似根，利用构造一次插值多项式，并用的根作为新的近似根.（5.1）由有（5.2）牛顿公式中的导数用差商取代的结果.第59页/共73页60几何意义曲线上横坐标为的点分别记为，则弦线的斜率等于差商值,其方程为按（5.2)式求得的实际上是弦线与轴交点的横坐标.这种算法因此而称为弦截法.表7-6第60页/共73页61而弦截法（5.2），在求时要用到前面两步的结果，弦截法与切线法的区别切线法在计算时只用到前一步的值.因此使用这种方法必须先给出两个开始值.例12用弦截法解方程设取作为开始值，用弦截法求

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

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

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