《北京交通大学(数字分析研究生课程)2求根课件-11综述》由会员分享，可在线阅读，更多相关《北京交通大学(数字分析研究生课程)2求根课件-11综述（70页珍藏版）》请在金锄头文库上搜索。
1、第2章 非线性方程的求根方法本章探讨函数方程求根的常用数值方法的构造和原理，主要介绍非线性方程求根方法的有关知识和方法.重点论述二分法、简单迭代法、牛顿迭代法及其变形的原理、构造、收敛性等内容。2.1 实际案例如下关于角度a的方程来自某种门的气压控制问题，工程师要求出满足如上方程的a的值以设计出一种自动控制装置。2.2问题的描述与基本概念定义2.1 设f(x)为一元连续函数，称f(x)=0 （2.1）为函数方程；当f(x)不是x的线性函数时，称对应的函数方程为非线性方程。非线性方程中，当函数f(x)是多项式函数时，称为代数方程，否则称为超越方程。l n次代数方程 在非线性方程中，绝大部分是没有
2、求根公式的，因此寻找求近似根的方法是非常重要!。l 求根问题的本质根的存在性、根的范围和根的精确化根的精确化是方程求根问题的核心。l 数值分析中求根方法分类两类：区间法,迭代法方法共同点是构造收敛根的数列。定义2.2 设数列收敛于x*，若存在正数 p 和C，满足则称的收敛阶为p或方法具有p阶敛速。l 当p1且C1时称方法超线性收敛。收敛阶越大，收敛越快，方法越好！2.3 二分法二分法也称对分区间法、对分法等，是最简单的求根方法，属于区间法求根类型。基本思想利用连续函数零点定理，将含根区间逐次减半缩小，构造点列来逼近根x*。1. 构造原理假设在区间中只有一个根，且满足，则二分法求根数列的构造过程
3、为： 记，取的中点，计算； 判别的值若，则，终止；若，则，取；若，则，取; 记，取的中点 判别是否成立（为给定的精度）若成立，取x*x1，终止；否则用代替，转。按上述步骤求根的方法称为二分法。（构造过程一般是重复的，其描述要写出其重复体）l 求根数列描述若记第k次二分区间处理得到的含根区间为，则有二分法对应的求根数列算式为 ，。2.分析因为，且，所以有的误差满足 （2.2）于是当时，由得到说明由二分法产生的数列总是收敛于根x*的。l 计算次数控制给定精度后，要成立，取k满足 即可，解出k，有 （2.3）（事先估计）这样就可以保证进行k次二分计算得到的 xk 就是满足精度要求的近似根。式（2.3
4、）确定的k往往偏大，主要用于理论估计。由二分法的构造，有故总成立有 （2.4）（事后估计）因而当时就有，此时xk是满足精度的近似根。式（2.4）确定的k往往较小，主要用于实际控制。例2.1用二分法求方程在区间1,2内的根，绝对误差。解 令，则，因为，且在1，2内不变号。可知方程在1，2内有唯一根。由二分法算法有，由，得 ，由，得，类似计算，可得,；,；，得近似解 例2.2 写出二分法求根的算法。解 二分法算法可以由计算过程和误差控制给出，设非线性方程为，为给定的精度。因为是实数，为描述其为零的情况，引入充分小的数，用表示。此外，借助计算机的存贮特点，将二分法中的数列ak都存在变量a中，bk都存
5、在变量b中，用变量x记录xk，由此得二分法算法二分法算法输入 a，b，输出 根x步骤： 若, 则输出根x，停止 若，做否则做 若 则输出根，停止否则转注：数值实验的编程二分法程序：Clearxfx_=Input“键入函数f(x)=”;a= Input“键入左端点a=”;b=Input“键入右端点b=”;Print“a=”,a, “ b=”,b, “ f(x)=”,fxe1=10(-10);eps=Input“键入根的误差限eps=”;n=0;Whileb-aeps,x=(a+b)/2;n=n+1;w=fx;IfAbswe1,Print“n=”,n, “ x=”,x, “ fx=”,w;Brea
6、k;p=fa*w/N; Ifp0,b=x,a=x;Print“n=”,n, “ x=”,x/N, “ eps=”,b-a/N说明：本程序用于求非线性方程f(x)=0在区间a,b内的根，这里要求f(x)在区间a,b连续,且f(a)f(b)0。程序执行后，先通过键盘输入函数f(x)和区间左端点a和右端点b及根的精度要求e，程序即可给出每次二分的次数和对应的点列x k，其中最后输出的结果即为所求的根。程序中变量说明：x：存放初值x 0和二分法中的x ka: 存放含根区间的左端点akb: 存放含根区间的右端点bke1:描述f(xk)=0的微小值,这里用|f(xk)|e1表示f(xk)=0n: 存放二分
7、次数注：语句Ifp0,b=x,a=x中p的一定要是算出的数值，否则会出现错误。本程序中用“p=fa*w/N”而不用“p=fa*w”就是这个原因。 2.4 简单迭代法基本思想利用对方程做等价变换根不发生变化的特点，将方程等价变形为，获得迭代计算公式由它算出逼近根x*的数列。1. 构造原理 将方程改写成另一等价形式； 构造迭代公式； 取定一个初值x0，由迭代公式算出数列。由上述得出称为迭代数列，函数为迭代函数，如上求根方法称为简单迭代法。就迭代格式而言，一般情况下，迭代函数把点变为后，有，此两点是不同；但对根，有，变不动它，点形象的称为的不动点；称方程为不动点方程。非线性方程求根问题就是求对应的迭
8、代函数不动点的问题。 2.简单迭代法的几何意义方程的根，在几何上就是直线与曲线交点的横坐标,如图2-4所示。 3.分析按简单迭代法计算产生的数列能收敛到根x* 吗？先假设是收敛的，不妨设。函数是连续的，有说明迭代数列的极限就是所求的根，故用简单迭代法求根是可行的。但：由方程，可以得到很多的不动点方程，例如方程，它的不动点方程可以有，是否这些方程的每个迭代格式产生的迭代数列都是收敛的呢？考虑方程，其在附近有一个根。若选择迭代不动点方程建立迭代格式取进行迭代计算得，此数列是收敛的，得近似根0.375812。但如果选择不动点方程建立迭代格式也取进行计算，就有，显然这个数列肯定不收敛。判别收敛的充分条
9、件。定理2.1 设迭代函数满足两个条件1.当时，有；2.，存在常数满足则有1.在中有唯一的不动点;2.迭代公式对任取，产生的数列都收敛于。证明存在性易证迭代函数 。作辅助函数显然。由条件1知由中值定理，至少存在一个，使，即，这说明在上有不动点。唯一性如果在上还有一个不动点，有，利用条件2，有矛盾，这就证明了满足定理条件的在中有唯一的不动点，记为。的收敛性由是不动点、迭代格式及条件2，有注意到，在上式中令，可得，有 ，因而有定理得证。例2.3证明迭代格式产生的数列是收敛的。证明 由迭代格式可知迭代函数为取其定义区间为实数R，显然有，另外任取有取L=0.51，则由定理有，迭代数列都收敛于不动点，故
10、有本题结论成立。定理2.1的条件2：，存在常数满足不易使用。实用中此条件常用，代替。推论2.1 设迭代函数满足1. 当时，有2. ，则在上有唯一的不动点，且对任意初值，迭代公式产生的数列都收敛于。在较大的范围满足不容易做到，但在较小范围还是较容易做到。通常称在根的附近取初值才能保证收敛的求根方法为局部收敛方法，没有这种取初值限制的方法称为全局收敛方法。二分法是全局收敛的，简单迭代法一般是局部收敛的。局部收敛定理定理2.2 设是迭代函数的不动点，且在点处连续，则1.若，迭代局部收敛；2.若，迭代发散定理2.2可以得到一个更容易使用的判别简单迭代法收敛的充分条件。证明 只给出1的证明。由和在点处连续性，存在一个正实数L1和的某个闭邻域，使时有成立。注意到，当时，由及中值定理有所以时，有，由推论2.1可知迭代产生的数列对任意都收敛于不动点，故迭代格式局部收敛。4. 误差估计和收敛速度定理2.3 设定理2.1的条件成立，则有如下误差估计式1） （事后估计）2） （事先估计）证明 只证1）。由迭代公式和定理2.
