第2章非线性方程求根

非线性方程的求根第二章1例

解：根据阿基米德定律，排出的水质量应等于球体自身的质量：2现代科学技术或工程技术领域的许多实际问题，常常可以归结为求解函数方程：如果函数能写成如下形式如果有使得，则称

为方程的根，或称为函数的零点。3如：①当f(x)为代数方程时，理论上已经证明，大于五次的多项式一般没有代数解法。②当f(x)为超越方程时，一般不能用代数方法求其根。

所以，超越方程(含有指数和对数等)代数方程（多项式）对于一般的非线性方程，只能用数值方法求解。4方程求根的问题分成两步：第二步：根的隔离确定根所在的区间，使方程在这个小区间内仅有一个根，该区间叫隔根区间。第三步：根的精确化已知根的一个近似值后，用某种方法对其进行加工，使之满足给定的精度要求。第一步：根的存在性5求隔根区间的一般方法理论依据：6本章主要介绍二分法与迭代法（包括Newton迭代法及其变型、弦割法等）§1.二分法二分法是方程求根最常用而且也是最保险的方法之一。一、算法的基本思想将区间对分，保留有根的区间，舍去无根的区间。如此往复，以逐步逼近方程的根。基本条件：7二、算法的步骤8ax0ba1b1三、算法的收敛性此时有误差估计：常用来估计k的值9四、算法的优点与缺点缺点：不能求偶数重根及复根；收敛速度非常缓慢，与以1/2为公比的等比级数相同；没有充分利用函数值。因此一般不单独使用，但往往可以为其它快速方法提供初值。优点：计算简单且必收敛，是一种可靠的算法；对函数性质要求低，只要求函数f(x)连续就可以了。用二分法求方程

在[1,1.5]内的实根，要求

解即可推出所需的迭代次数满足

在区间[1,1.5]上至少存在一个根。其具体过程如下：

例2.1.1由于因而由误差估计式1011例2.1.2解即可推出所需的迭代次数满足因而函数在区间[1,2]上存在惟一的零点。

由于以及由误差估计式12二分法的一种修正是试位法。在二分法中，原来区间的中点为新的区间的一个端点。因此，每迭代一步，区间的长度均减半。在试位法中，不用中点，而用过点与的直线的零点作为新区间的一个端点。在实际计算中，试位法比二分法往往收敛得要快。在试位法的每一步计算中，有13§2.非线性方程求解的迭代法等价变换迭代法是一种逐步逼近的方法:首先给出一个粗糙的初值，反复利用同一个迭代公式，逐步逼近精确解。

用迭代法求方程根的基本步骤如下：第一步：化为同解方程14第二步：产生迭代序列先建立适当的迭代格式：利用上述格式可产生一列数：第三步：取极限一定收敛吗？15在直角坐标系中同时作和两条曲线，如图所示，则这两条曲线的交点的横坐标就是方程的根，也就是的根。迭代格式由求，相当于过曲线上作水平线与直线相交，过交点作x轴的垂线，此时垂足至原点距离等于，故垂足横坐标为。

迭代法的几何解释：16由上图可见，曲线斜率时迭代序列收敛，且越小收敛越快；反之，若，则迭代序列发散。xyy=xxyy=xx0p0x1p1x0p0x1p117例2.2.1解18下面给出简单迭代法的一个收敛性定理。Lipschitz条件保证迭代不中断，连续时保证有解压缩映像19①存在唯一性证明做辅助函数，则有所以，存在点若又有，则有所以②收敛性任取初值则所以，任意的初值都收敛。20③误差估计证毕21222324例2.2.3解也可化为等价方程.但此时定理条件不成立，迭代序列不能保证收敛。25例2.2.4解26由于定理中条件(1)一般难于验证，而且在大区间上，这些条件也不一定都成立。所以实际使用迭代法总是在根的邻近进行。表明收敛性与初值的选择有关！27

实际用迭代法计算时，先用二分法求得较好的初值，然后再进行迭代。28性质

1.若方程x=(x)在处有根，则当|'()|<1且'(x)在x=的某邻域内连续时，简单迭代法必在x=的某邻域内收敛；

2.若'(x)在某闭区间上连续且|'(x)|1，则方程x=(x)用相应的简单迭代法所得点列必定发散。29证明：只需证2.用反证法：若简单迭代法所得点列{xn}收敛到，易知x=为方程x=(x)的根。但由于这说明随着n的增加，点列xn越来越远离，故{xn}不可能收敛到，矛盾！前面定理所涉及的收敛性，即在根邻域的收敛性称为局部收敛性，具有局部收敛性质的迭代法通常对初值的要求较高，使用起来不太方便。因而，人们通常希望迭代算法对相对大的范围的初始点具有收敛性，这种收敛性称为全局收敛性。构造迭代法，人们自然希望迭代算法不仅收敛，而且收敛快，即所谓收敛的速度。30定义2.2.1

设迭代过程收敛于的根.如果迭代误差满足下列关系则称该迭代序列是p

阶收敛的(时要求)。

迭代法收敛的阶当p=1时，称为线性收敛；当p>1时，称为超线性收敛；当p=2时，称为平方收敛或二次收敛。显然，迭代序列的收敛阶越高，它的收敛速度就越快。31因为，由得32

在实际使用中收敛的阶有时很难直接确定，常常采用一些其它的方法来确定收敛的阶。使用Taylor展开式是一种常用的方法。如果在根处充分光滑(各阶导数存在)，则可对在处进行Taylor展开，得33上式说明迭代法为p阶收敛的。34补充35例2.2.6建立的迭代法至少是平方收敛的。证明根据上述定理，只需证明因为故该迭代法至少是平方收敛的。Newton迭代法36

迭代法的加速37令新的迭代函数为构造加速迭代序列即38

迭代法的埃特金加速法3940则41(1).

k=0，1，2，…埃特金迭代格式可改写成：(2).

其中迭代函数42

小结43§3.Newton迭代法及其简单变形用迭代法解非线性方程时，如何构造迭代函数是非常重要的，那么怎样构造的迭代函数才能保证迭代法收敛呢？一、Newton迭代法将非线性方程线性化，以线性方程的解逐步逼近非线性方程的解。

基本思想非线性问题的最简单解法是线性近似！44

迭代格式45上述格式称为Newton迭代格式。这样一直下去，可以得到一列迭代序列，其迭代格式为：类似地，同样可以得到46几何意义xyNewton迭代法又称为切线法切线

原来是以直线代替曲线的近似方法啊!47

局部收敛性484950改进：则至少是二阶收敛的。51缺点：对初值要求较高，计算量较大。优点：收敛速度快，精度高，格式简单，应用广泛。

优点与缺点

52下图表明Newton法收敛性依赖于初值x0

的选取。x0x0x0总之，Newton法具有收敛快，稳定性好，精度高等优点，是求解非线性方程的有效方法之一。但它每次迭代均需计算函数值与导数值，故计算量较大。而且当导数值提供有困难时，Newton法无法进行。此外，由于它是局部收敛的，因而对初值要求较高，只有初值选得充分靠近根时，才能保证序列收敛。53注1：使用牛顿迭代法存在从一个根跳到另一个根的情况。注2：如果f(x)=0没有实根，则牛顿迭代序列不收敛。54例2.3.1

用Newton法解方程f(x)=x(x+1)2-1=0在0.4附近的根。解将函数f(x)求导，得到k0123xk0.40.470130.465390.46537所以，取根为0.4654.55

全局收敛性定理2.3.2

保证了根的存在性

函数单调，根唯一函数图形的凸向不变56例2.3.2解57

Newton迭代法的计算步骤58

程序框图终止准则：59例2.3.3解根据全局收敛性定理，对任何满足上述Newton迭代产生的迭代序列均收敛于60二、简化Newton法此格式称为简化Newton迭代。迭代函数为

迭代格式61

几何意义62此格式称为推广的简化Newton迭代。迭代格式为

进一步简化由简单迭代的局部收敛条件

收敛性与收敛速度63得64推广的简化Newton法收敛时，因为所以，推广的简化Newton法只有线性收敛速度。65三、下山Newton迭代在Newton迭代法中，若函数较复杂，初值的选取较困难时，为防止迭代发散，可改用如下的迭代式，以扩大初值的选取范围：成立，上述迭代方法称为下山Newton法。66终止准则：67例2.3.5解68四、弦割法

迭代格式由上式定义的迭代算法称为弦割法，也称为割线法。为什么称为弦割法？是从它的几何意义而言。69

几何意义切线

割线

还是以直线代替曲线的近似方法啊!70

收敛性与收敛速度71例2.3.6解两步方法

72

弦割法的计算步骤73例2.3.7解取x0=1,x1=2,代入公式，计算结果如下表所示。kxkf(xk)01-112521.166666667-0.5787036931.253112023-0.2853630241.3372064440.05388057951.323850096-0.003698116861.324707936-4.273521*10E-571.3247179653.79*10E-87