非线性方程求根

1、第四章 方程求根本章主要内容：二分法，不动点概念，迭代的整体收敛性，迭代的局部收敛性，迭代的收敛阶，埃特金 迭代法，牛顿迭代法，改进的牛顿迭代法，弦截法与抛物线法。教学目的及要求：使学生了解不动点、整体收敛与局部收敛，收敛阶等概念，掌握二分法、牛顿 迭代法、弦截法，会用这些方法计算非线性方程的根。教学重点：迭代的收敛性判定，牛顿迭代法。教学难点：迭代过程收敛的定理。教学方法及手段：非线性方程求根是数值分析中的一个经典内容，讲课中要注意结合几何图形， 讲清讲透计算方法产生的来源，算法的设计，使学生学得懂、记得住、用得上。对 定理应给出完整的证明。在实验教学中，通过具体实例，让学生掌握二分法、埃特

2、金算法、牛顿法、弦 截法等方法的编程。教学时间： 本章的教学的讲授时间为 6 学时，实验学时 4 学时。教学内容：本章主要研究单变量非线性方程f (x) 0( 7.1 )的求根根问题，这里，f ( x) Ca, b。对于这种连续函数方程，一般采用迭代法求根。迭代法要求先给出根x* 的一个近似，若 f(x) Ca,b，且 f(a)f (b) 0 ，根据连续函数性质可知f(x) 0在(a,b)内至少有一个实根，这时称 a,b 为方程 (7.1) 的有根区间。通常可通过逐次搜索法 求得方程 (7.1) 的有根区间。一 二分法假设中点 x0不是 f (x) x* 在 x0 的右侧，这时令 b1 x0

3、。不管出现哪一考察有根区间 a,b ，取中点 x0 (a b)/ 2将它分为两半， 的零点，检查 f(x0)与 f (a)是否同号，若同号，说明所求根 a1 x0， b1 b；否则， x*必在 x0的左侧，这时令a1 a ，种情况，新的有根区间a1,b1 的长度仅为 a,b 的一半。x1 (a1 b1) /2将区对于有根区间 a1,b1 ，又可再施行上述同样操作，即用中点间 a1,b1 再分为两半，然后判定所求根在x1的哪一侧，从而又确定了一个新的有根区间 a2 ,b2 ，其长度是 a1,b1 的一半。 如此反复二分下去，即可得出一系列有根区间 a,b a1,b1 a2,b2an,bn其中每个

4、区间都是前一个区间的一半，因此an ,bn 的长度bn an (b a)/2n当 n 时趋于零，就是说，如果二分过程无限地继续下去，这些区间最终必收缩 于一点 x* ，这点显然就是所求的根。每次二分后，设取有根区间an ,bn 的中点x an bn xn2 作为根的近似值，则在二分过程中可以获得一个近似根的序列 x1 ,x2 , ,xn,该序列必以根 x* 为极限。 不过在实际计算时，我们不可能完成这个无限过程，其实也没有这种必要，因 为数值计算的结果允许带有一个的误差。由于* b ax xnbn ann2 只要二分次数足够多(即 n 充分大)，便有*x xn这里 为预先给定的精度。具体算法如

5、下1 给出计算精度 ，有根区间左右端点a ， b ，取初始误差 r b a 。2 当 r 时，反复做以下操作( 1 )计算 c (a b) / 2。(2)若 f (c) 0，输出精确根 c ，停止计算。( 3)若 f(a) f (c) 0，取 b c ，否则，取 a c 。( 4 ) r b a3 输出近似根 c 。 上述二分法的优点是算法简单，且总是收敛的，缺点是收敛太慢，故一般不单 独将其用于求根，只用来为根求得一个较好的近似值。【例题 1】对于给出的方程f(x) x3 x 1 01 用二分法计算它在 ( 0,2) 之间的近似根，要求精确到小数点后四位；2 给出每次两分后的有根区间；3 画

6、出每次两分的中点，直观描述两分法原理。图 7-1迭代法及其收敛性(一) 不动点迭代法。将方程 f(x) 0改写成等价的形式x (x)( 7.2 )若要求 x*满足 f(x*) 0，则 x*(x* ) ；反之亦然， 称x*为函数 (x)的一个 不动点 。这表明，求 f (x) 的零点就等价于求 (x)的不动点。求不动点一般采用逐次逼近法。为了说明这种方法，我们重温一个经典例子。 我们知道，递推式12xn 1(xn) ( n 0,1, )2xn对于初值 x0 2，所产生的数列 xn单调下降且以2为下界，故 lim xn2。n “温故知新”，这个例子给我们带来了以下几点“新知”。121 如果记 (x

7、) (x ) ，递推式可表示成为xn 1(xn) 。将每个 xn 代入到 (x) 所2x得到的值 (xn) xn 1变小了，即在“动” 。每个 xn不断地代入(x)，意味着“迭代” 。2 有一个特殊值 2 ，代入到 (x)后，所得到的值 ( 2) 21( 2 2 ) 2 没有发 12 生改变，即“不动”。点x*2自然可认为是函数 (x) (x)的“ 不动点 ”。2x3 这里的 x (x)，实际上是方程f (x) x2 2 0，这里的 2 正是方程的根。从这个例子，我们可提炼出求不动点的方法。选择一个初始近似值x0 ，将它代入 x (x) 右端，即可求得x1(x0)可以如此反复迭代计算xn 1

8、(xn) ( n 0,1, )( 7.3)(x) 称为迭代函数。如果对任何 x0 a, b，由 (7.3)得到的序列 xn 有极限*lim xn x*n则称迭代式( 7.3 )收敛，且 x*(x*)为 (x)的不动点，故称( 7.3)为 不动点迭代法。(二) 不动点迭代法的几何意义。方程 x( x)的求根根问题在 xoy平面上就是要确定曲线y (x) 与直线 y x的交点 P* (图 7-2 )。对于 x* 的某个近似值 x0 ，在曲线 y ( x)上可确定一点 P0， 它以 x0为横坐标，而纵坐标为(x0) x1，过 P0 引平行 x轴的直线，设此直线交直线y x于点 Q1 ，然后过 Q1再

9、作平行于 y 直线，它与曲线 y( x)的交点记作 P1，则点 P1的横坐标为 x1，纵坐标则等于(x1) x2 。按图 7-2中箭头所示路径继续做下去，在曲线 y ( x)上得到点列 P1,P2, ，其横坐标分别为依公式xn 1( xn)求得迭代值 x1,x2, 。如果点列 Pn 趋向于点 P* ，则相应的迭代值xn收敛于所求的根 x*。【例题 2】研究用迭代法求方程 f(x) x3 x 1 0在x0 1.5附近的根 x* 。1 方程等价形式为 x 3 x 1 ，迭代公式 xn 1 3 xn 1 ；1 11 12 方程等价形式为 x 2 ，迭代公式 xn 1 2 ；x x2xn xn2333

10、 方程等价形式为 x x3 1 ，迭代公式 xn 1 xn3 1。3 1 1对于迭代 xn 1 x3n 1，其发散性显然。而对于迭代 xn 12 ，可以通过以下实验，观xn xn察出它的发散性。图 7-3而对于迭代 xn 1 3 xn 1 ，可以通过以下实验，观察出它的收敛性。图 7-4例 2 表明原方程转化为不同形式的迭代， 有的收敛， 有的发散， 只有收敛的迭代过程才有意义，为此我们首先要研究(x) 的不动点存在性以及迭代法的收敛性。(三) 不动点的存在性与迭代法的收敛性。【定理 1】设 (x) Ca,b满足以下两个条件1 对任意 x a,b有 a (x) b 。2 存在正常数 L 1，使

11、对任意 x, y a,b都有(x) (y) L x y (7.3 )则 (x) 在 a,b 上存在着唯一的不动点x* 。证明 先证明不动点的存在性 。若 (a) a或 (b) b，显然 (x) 在a,b 上存在着 不动点。因 a (x) b，以下设 (a) a及 (b) b ，定义函数f (x) (x) x显然 f(x)C a, b，且满足 f(a) (a) a0，f(b)(b)b 0 ，由连续函数性质可知存在x* ( a, b)，使得 f(x*) (x* )x*0，即x*(x*)， x* 即为 (x)的不动点。再证明唯一性 。设 x1*及 x*2都是 (x) 在a,b 上的不动点，则* *

12、* * *x1x2(x1 )(x2 )L x1x2x1x2引出矛盾，故 (x) 的不动点只能是唯一的。【定理 2】设 (x) Ca,b满足定理 1 中的两个条件，则对任意x0 a, b，由迭代式 xn 1(xn) (n 0,1, )得到的序列 xn收敛到 (x) 的不动点 x* ，并有误差估计*Lnxn x*x1 x01L证明 设 x* a,b是 ( x)在a,b 上唯一不动点，由条件1，可知 xn a,b ，由条件2有xn x*(xn 1) (x*) L xn 1 x*递推下去，可得* * 2 * n *xn x L xn 1 x L xn 2 x L x0 x因 0 L 1 ，故当 n 时

13、序列 xn 收敛到 x* 。xn 1xnxn 1(xn) (xn 1) L xn反复递推下下去，可得xn 1 xn Lnx1 x0于是对任意正整数 k ，有xn k xnxn k xn k 1 xn k 1 xn k 2xn 1 xn(Ln k1 Ln k 2Ln) x1 x0Ln1Lx1 x0在上式令 k ，注意到lim xn k k，即得*Lx xnx1 x01L注：*Ln1 误差估计式 xn x*x1 x0 用于误差估计并不方便， 原因是因为参数 L 难以1L确定。实际进行误差估计时，我们往往采用 事后估计方法 。xn kxnxnkxn k 1xnk 1xn k2xn 1xn(Lk1 L

14、k 21)xn1 xn1Lxn 1 xn令 k，有xxn11L xn1 xn1L由此可见，只要相邻两次计算结果的偏差xn 1 xn 充分小，就可以保证近似值xn 具有足够精度。2 在许多情况下，定理 1 和定理 2 中的条件 2 往往用以下条件来替换若 (x) C1a,b ，且对任意 x a,b有 (x) L 1。因为利用中值定理，对任意 x, y a,b ，有(x) (y) ( )(x y) L x y ( (a,b)这表明，条件 2 是成立的。(四) 局部收敛性。上面给出了迭代序列 xn 在区间 a,b上的收敛性，通常称为 全局收敛性 。在实际应用 时，通常只在不动点 x* 的附近考察其收

15、敛性，即 局部收敛性 。【定义 1】设 (x) 有不动点 x* ，如果存在 x* 的某个邻域 R: x x*，对任意 x0 R，迭代 xn 1 ( xn )产生的序列 xn R ，且收敛到 x* ，则称该迭代法局部收敛。【定理 3】设 x*为 ( x)的不动点，(x)在 x* 的某个邻域连续，且(x*) 1，则迭代法 xn 1 (xn )局部收敛。*证明 由连续函数的性质，存在x* 的某个邻域 R: x x*，使对于任意 x R成立(x) L 1此外，对于任意 x R，总有 (x) R ，这是因为(x) x*(x) (x* )( )(x x* ) L x x*据定理 2 可以断定迭代过程 xn

16、 1(xn) 对于任意初值 x0 R均收敛。(五) 收敛速度。【例题 3】用不同方法求方程x2 2 0的根 x*2 。解 这 里 f(x) x2 2 0可以改写为各种不同的等价形式 x (x) ，其不动点为x*2 ，由此构造不同的迭代法。xn 1xn2xn2，(x)x2x 2， (x) 2x1，(x*)( 2) 2 2 1 1xn1 x2 ， (x) 2 xnx(x)22 ， (x*)( 2)x( 2)2 112xn 1xn(xn 2) ，4(x) x 1(x2 2) , (x) 1 4(x* )( 2) 11 2 112 221 112 12 2xn 121(xnx2n),(x) 12(x2

17、x),(x) 2(1 x22)(x*)( 2) 21(1 ( 22)2) 0取 x0 2，对上述 4 种迭代法，计算三步所得结果列表如下：nxn迭代法 1迭代法 2迭代法 3迭代法 40x022221x1411.50001.50002x21821.43751.41673x334011.42091.4142注意到 2 1.41421356237310，从计算结果看到迭代法 1及 2均不收敛，且它们不满足 定理 3 中的局部收敛条件， 迭代法 3和 4 均满足局部收敛条件， 且迭代法 4比迭代法 3收敛 快。为了衡量迭代法收敛速度的快慢，可给出如下定义。【定义 2】设迭代过程 xn1(xn)收敛于

18、方程 x (x)的根x*，如果迭代误差en xn x* 满足下式lim enp1 c ( c 0 ) n enp则称该迭代过程是 p阶收敛的 ，特别地， p=1时称 线性收敛 ， p1时称 超线性收敛 ， p=2 时称 平方收敛 。注： 收敛速度定义的意义剖析 lnim xn x*， lnim en lnim( xn x*) 0en 1故 en是 n时的无穷小量。由 lim np1 c可知，当 n 充分大时，有nenppen 1 cen这表明，当 p1 时，第 n 次迭代的误差 en 1会远远小于第 n-1 次迭代的误差 en ，即 迭代收敛变快了，这正是“收敛速度”的涵义所在。【定理 4】对

19、于迭代过程xn 1( xn ) ，如果 ( p) ( x)在所求根 x* 的附近连续，并且(x*)(x*)(p 1)(x*) 0， (p)(x*) 0则该迭代过程在点 x* 的附近是 p 阶收敛的。证明 由于 (x*) 0，据定理 3可以断定迭代过程xn 1( xn )具有局部收敛性。再将 (xn)在根 x* 处做泰勒展开，利用上述条件，有* (p) ( ) * p *(xn)(x*)(xn x* ) p ，这里：在 xn与 x* 之间p!注意到 (xn) xn 1， (x*) x* ，由上式得xn 1 x( p) ( ) * p p(! )(xn x*)pen 1 xn 1 x*(p) (

20、)enp (xn x* ) pp!lim enp1 lim (p)( ) (p)(x*) n enp n p ! p!这表明迭代过程确实为p 阶收敛的。在例 3 中，迭代法3 中的 ( 2)收敛的，由定理 4 知，它是线性收敛的。在例 4 中，迭代法4 中的 ( 2)2 阶收敛的。2 1 0，2( 2) 1 ，由定理 3 知，它是知，该迭代法是12(1 ( 22)2 ) 0, ( 2)1 0, 由定理 4迭代收敛的加速方法对于一些不收敛或者收敛速度较慢的迭代法， 可以通过改造， 使它成为收敛的或者收敛 速度较快的迭代法，埃特金给出了一个处理方法。设 x0是根 x* 的某个近似值，用迭代公式先预

21、报一次得x1(x0 )再预报一次得x1 ( x1) 据微分中值定理，有x1 x*(x0) (x* )( 1)(x0 x* )x1 x*(x1) (x* )( 2)(x1 x*)其中， 1在x0与x*之间， 2在分别 x1 与x*之间。 假定 (x)改变不大，近似地取某个近似值 L ，则有x1 xL( x0 x )x1 xL( x1 x )将两式相除，x1 xx1 xx0 x* ，由此可推出x1 x *(x1 x* )(x1 x*) (x1 x*)(x0 x*)* * 2 x0 x (x )2 * * 2 *(x1) 2x1x ( x )x0x1 x1x*2x (x1 2x1 x0) x0 x1

22、 (x1)*2x (x1 2x1 x0) x0 (x1 2x1 x0) (x1 x0)x* x0 ( x1 x0)2x1 2x1 x0将该值作为 x1 的校正值，亦即( x1 x0 )2x1 x0x1 2x1 x0可以证明，一般情况下，如此得到的x1 比原迭代式所计算出的 x1要好得多。上述方法可归纳出一般情形： 对于给定的 xn ，预报 xn 1(xn )预报 xn 1(xn 1 )校正xn 1x(xn 1 xn )2xnxn 1 2 xn 1 xnn 0,1, )7.4 )7.4 )式称为 埃特金加速方法例题 4】求 x2 2 0的根 x*2 的近似值，用埃特多加速法对不收敛的迭代式2 x

23、n 1 xn xn 2 ，( x0 2)进行改造，并给出五次计算的结果。 经过埃特金加速之后，原发散的迭代被改造成为收敛的。四 牛顿法设方程 f(x) 0有根x* ，且f (x) 0 ，根据函数的几何图象(见图7-5)，我们可以给出一种求 x* 的方法。步1 在x*附任取一点 x0 ，作曲线 y f(x)在点x0处的切线 y f (x0) f (x0 )(x x0)令 y 0，可得到切线与 x轴的交点 x1 x0 f(x0) 。1 0 f (x0)步2 再作曲线 y f (x)在点x1处的切线y f (x1) f (x1)(x x1)令 y 0，可得到切线与 x轴的交点 x2 x1 f(x1)

24、2 1 f (x1)从几何上看， x1， x2越来越接近 x* 。由此，不难归纳出一般的迭代公式f(xn)xn 1 xnn , x0 为初值f (xn)这就是 牛顿法(也称切线法) 。如果 x* 是方程 f (x) 0的一个单根，亦即 f(x* ) 0，而 f (x* ) 0 ，则牛顿迭代法收敛且收敛速度是 2 阶的。事实上，迭代函数为(x) x ff (xx) ，(x) 1f(x)2 f(x)f (x)f (x)2f(x)f (x)2 f (x)2而 (x*) 0，故牛顿法在根 x* 的附近是平方收敛的。这表明： 牛顿迭代法至少具有局部收敛性。 对某些函数来说， 这种迭代还具有整体收敛 性。

25、牛顿迭代算法：步 1 选定初值 x0，计算 f0 f (x0)， f0 f (x0) 。步 2 迭代 x1 x0 f0/ f0 ，计算 f1 f (x1)， f1 f (x1) 。步3 如果x1满足1或 f1 2 ，以x1作为所求根近似值，终止迭代；否则转步4。这里， 1， 2 是允许误差(一般可取 1 2 )，而x1 x0x1 C1 0 1， C 是绝对误差或相对误差的控制常数，一般可取C=1。x1 x0 / x1 x1 C步 4 如果迭代次数达到预先指定的次数 N，或者 f1 0 ，显示方法失败信息；否则，用 (x1, f1, f1 )代替(x0, f0 , f0 ) ，转步 2继续迭代。

26、【例题 5】设方程为f(x) x3 2x2 10x 20 01 给出用牛顿法求方程根的程序；2 该迭代的收敛性与初值 x0 的选取是否有关，通过数值试验来回答这个问题；3 迭代收敛的快慢与初值 x0 的选取是否有关，通过数值试验来回答这个问题；4 适当地对程序作少量修改，求 f(x) x41 x3 1 0在 x0 1附近的实根，精度要求取 18为10 8 ；并说明初值是否可随意取？2五 弦截法牛顿法有一个缺点：每步除计算 f (xn)外还要算 f ( xn ) ，许多情况下，计算 f (xn) 往f(xn), f(xn 1), ，来回避导数值往较困难。为了解决这个问题，我们可以利用已求得的函数

27、值f (xn) 的计算。下面介绍两种常用的方法。(一)弦截法。 对于牛顿法f (xn)f (xn)xn 1xn中的 f (xn)，用差商 f (xn) f(x0) 来代替，从而得到下列迭代式xn x0f(xn) f (x0)(xn x0) (n 0,1, )这一迭代式是f (x) 0 的又一种等价形式xxf (x)f (x) f (x0) (x x0)(x)弦截法的几何意义见图 7-6 。曲线 y f ( x)上横坐标为 x1的点记为 p1，作弦 p0p1 ，该弦的方程为y f (x1)f (x1) f (x0 )x1 x0(x x0 )令 y 0可求得它与 x 轴的交点x2 x1f (x1)

28、f(x1) f(x0)(x1 x0)若记曲线 y f ( x)上横坐标为 x2 的点记为 p2，作弦 p0p2 ，该弦的方程为y f (x2)f (x2) f(x0)x2 x0(x x0)令 y 0可求得它与 x 轴的交点x3 x2f (x2)f (x2) f (x0)(x2 x0)从图中可以看出，如此产生的序列 xn是收敛于 f(x) 0的根 x*。 下面，考察弦截法的收敛性。对迭代函数(x) xf(x)f(x) f (x0)(x x0)求导知(x*) 1 ff(xx0) (xx0) 1f (x* )f(x* ) f(x0)xx0当 x0 充分接近 x* 时， 0(x) 1，故弦截法是线性收敛例题 6】取初值 x0 4， x1 3.8 ，用弦截法求方程f (x) x3 2x 5 0在1 ，