第二章 数值分析--方程求根

第二章 方程求根

教学内容：

1．二分法 2．基本迭代法 3．牛顿法 4．弦位法

5．埃特金法和斯基芬森法 6．重根的情况

教学重点：

各种算法的思路及迭代公式的构造

教学难点：

各种算法的收敛性、收敛速度及误差估计

计划学时：5-6学时 授课提纲：

方程求根就是求函数f(x)的零点x*，即求解方程 f(x)?0

这里，f(x)?0可以是代数方程，也可以不是，如超越方程。

方程的根既可以是实数，也可以是复数；既可能是单根，也可能是重根；即可能要求求出给定范围内的某个根，也可能要求求出方程全部的根。

本章介绍的方法对两类方程都适用，但大部分都是要求知道根在什么范围内，且在此范围内只有一个单根。若有?使得f(?)?0,f?(?)?0，则称?是方程f(x)?0的单根；若有?使得

f(?)?f?(?)???f(m?1)(?)?0,f(m)(?)?0，

则称?是方程f(x)?0的m重根。

设f(x)在区间[a,b]连续，若f(a)f(b)?0，则f(x)在区间（a,b）内至少有一个实根，若再有f?(x)不变号，则有根区间（a,b）内仅有一个实根。除特别声明，本章介绍的算法都是求单实根。

2.1 二分法

二分法又称区间对分法，是最直观、最简单的一种方法。 2.1.1 二分法原理

若 f (x)在[a, b]内单调连续，且f(a) f(b)<0，则f在(a, b)内必有惟一的实根。

1

2.1.2 二分法思想

区间对分，去同存异 2.1.3 二分法计算步骤

步1：令x0?(a?b)/2，计算f(x0)； 步2：若f(x0)?0，令x*?x0，计算结束； 步3：若f(x0)*f(a)>0，令a?x0；否则令b?x0；

步4：若|b?a|??，令x*?(a?b)/2,计算结束；否则转步1。 2.1.4 二分法误差分析和收敛性

记第k次区间中点为xk，则有

x*?x0?(b?a)/2，x*?x1?(b?a)/22，?,x*?xk?(b?a)/2k?1

故当k??时，xk?x*。

为使x*?xk??，解不等式(b?a)/2k?1??，得

k?[ln(b?a)?ln?]/ln2?1

2.1.5 二分法的优缺点

? 算法简单直观，易编程计算； ? 只需f(x)连续即可；

? 区间收缩速率相同，收敛速度慢；

? 无法求复根和偶重根。 例2-1 p15例1

2.2 迭代法

2.2.1 迭代法原理

f(x)?0 ? x??(x) f(x)的根 ?(x)的不动点

2.2.2 迭代法思路

任取初值x0?[a,b]，令x1??(x0)，x2??(x1)，反复迭代，即得

xk?1??(xk),(k?0,1,2,?)

直到满足精度要求的xk来近似x*。称x??(x)为迭代公式，?(x)为迭代函数，{xk}为迭代序列。

若{xk}收敛时，称迭代公式是收敛的。此时设limxk?x*，当?(x)连续时

k??x*?limxk?1?lim?(xk)??(lim)??(x*)

k??k??k??亦即f(x*)?0。若{xk}不收敛，称迭代公式是发散的。

2

2.2.3 迭代法的计算步骤

步1：选取初值x0及精度?，置k=0; 步2：计算xk?1??(xk)；

步3：若xk?1?xk??，令x*?xk?1，计算结束；令k=k+1,转第2步。 2.2.4 迭代法的几何意义及收敛性条件

迭代法的几何意义是求曲线y?x和y??(x)交点的横坐标x*。

x1 x0 x* p1 x x0 x* p0 x0 y x1 x* y = x x x0 y y=?(x) p0 x* x1 y = x x p0 y p1 y = x y=?(x) y p0 y = x ? ? p1 y=?(x) y=?(x) ? ? p1 x x1 可以看出，若?(x)的变化幅度小于x的变化幅度时，迭代公式收敛，否则，迭代公式不收敛。

迭代序列的收敛性依赖于构造的迭代函数（不唯一）。

例2-2 求方程f(x)?x5?2x?1在（1，2）内的根。分别构造迭代函数

1 ?1(x)?52x?1 ?2(x)?(x5?1)

2定理2-1 迭代收敛基本定理 设迭代函数?(x)在[a,b]内连续，在(a,b)内可导，且满足

（1）映内性：当x?[a,b]时，有?(x)?[a,b]； （2）压缩性：?0?L?1，?x?[a,b]，有??(x)?L；

3

则

① 函数?(x)在[a,b]内存在惟一的不动点x*；

② ?x0?[a,b]，迭代公式xk?1??(xk)产生的序列{xk}?k?1?[a,b]，且

xk?x* limk??③ 有如下误差估计 1xk?1?xk x*?xk?1?LLkx1?x0 x?xk?1?L*(k?1,2,?)

(k?1,2,?)；

x*?xk?1 ④ lim*???(x*)

k??x?xk说明：(i) 常用xk?1?xk来控制是收敛精度，L越小，收敛越快。

(ii) 条件?0?L?1，?x?[a,b]，有??(x)?L太强，但是好验证，可以

改为较弱的条件：

?x1,x2?[a,b],?(x1)??(x2)?Lx1?x2,其中L是与x1,x2无关的常数（Lipschitz常数），且0?L?1。

（ⅲ）定理的条件是迭代公式收敛的充分条件，非充要条件。

p19例3。

定义2-1 如果存在x*的某个邻域N(x*,?)，使迭代过程xk?1??(xk)对任意的初值x0?N(x*,?)均收敛，则称该迭代过程在根x*邻近具有局部收敛性。

定理2-2 局部收敛性定理 设x*是x??(x)的不动点，??(x)在x*的某个邻域N(x*,?)内连续且??(x)?L?1，则迭代公式xk?1??(xk)对任意的初值

x0?N(x*,?)局部收敛。

定理2-3 设x*是x??(x)的不动点，??(x)在x*附近连续，若存在x*的某个邻域N(x*,?)，?x?N(x*,?)，都有??(x)?1，则迭代公式不对任意的初值

x0?N(x*,?)收敛，称为发散。见p19定理3。

定理2-4 对于迭代公式xk?1??(xk)，如果?(p)(x)在x*附近连续，且有

??(x*)????(x*)????(p?1)(x*)?0,?(p)(x*)?0

则该迭代公式在x*附近是p阶收敛的。见p20定理4。

4

证明：由??(x*)?0及定理2-2知，迭代过程xk?1??(xk)在x*的附近具有局部收敛性。再将?(xk)在x*处做泰勒展开，则有

?(p)(?)* ?(xk)??(x)?(xk?x*)p （?介于xk和x*之间）

p!注意到xk?1??(xk)及x??(x)，从而有xk?1?xk?**?(p)(?)p!(xk?x*)p

xk?1?x*?(x*)ek?1*x故 limp?lim，迭代公式在附近是p阶收敛的。 ?k??ek??*pp!kxk?x迭代法的收敛阶是对迭代法收敛速度的一种度量。 例4（见p20）

例 设a,x0?0，证明迭代公式xk?1并计算limk??2xk(xk?3a)是计算a的3阶方法，?23xk?aa?xk?1(a?xk)3。

证明 显然当a,x0?0，xk?0(k?1,2,?)， 令?(x)?x(x2?3a)3x?a2，则??(x)???3(x2?a)2(3x?a)22。

则?x?0，可使??(x)?1，即迭代收敛。设xk?x*，则有 x?*x(x*?3a)3x*?a22，解之得x*?0,a,?a，取x*?a。则

3xk?3axka?23xk?alimk??a?xk?1(a?xk)3=limk??(a?xk)3=lim11= 32k??3x2?ak??4a(a?xk)(3xk?a)k(a?xk)3=lim故迭代是3阶收敛。

例 已知迭代公式xk?1明该迭代公式平方收敛。

x2?3x2?4x?3证法一：迭代函数?(x)?，经计算??(x)?，??(x*)?0， 22x?42(x?2)2xk?3x2?3局部收敛于方程x?的根x*?1，证?2x?42xk?4???(x)?

1，而???(x*)?0，有定理2-4知，迭代公式平方收敛。 3(x?2)5

证法二：由于limxk?x*?1，则ek?xk?1。于是

k??ek?122xk?3(xk?1)2ek ?xk?1?1??1??2xk?42xk?42xk?4ek?111??0。 从而 lim2?limk??k??2x?42ekk2.2.4 迭代法的特点

? 算法逻辑结构简单；

? 在计算时,中间结果若有扰动,仍不会影响计算结果； ? 不同的迭代公式在收敛性、收敛速度上有差别。

2.3 牛顿（Newton）法

2.3.1牛顿法原理

牛顿法是把非线性方程f(x)?0线性化的一种近似方法。

把f(x)在x0点附近展开成泰勒（Taylor）级数

11f(x)?f(x0)?f?(x0)(x?x0)?f??(x0)(x?x0)2???f(n)(x0)(x?x0)n??取

2!n!其线性部分，当f?(x0)?0时，得到第1次迭代结果，

x1?x0?f(x0)/f?(x0)

若f?(x1)?0，在x1点作线性近似，得到第2次迭代结果

x2?x1?f(x1)/f?(x1)

这样，得到牛顿法的一个迭代序列 xk?1?xk?f(xk)/f?(xk) 2.3.2牛顿法的几何意义

f(x)过点(xk,f(xk))的切线方程为y?f(xn)?f?(xn)(x?xn)，

该切线与x轴的交点是xk?f(xk)/f?(xk)，把它记作xk?1作为下一次迭代点。故牛顿法也叫做切线法。

6

2.3.3牛顿法的计算步骤

步1：选取初值x0及精度;

步2：计算f(x0),f?(x0)，令x1?x0?f(x0)/f?(x0)；

x?x0??，步3：若x1?x0??或1令x*?x1，计算结束；否则，令x0?x1,x1转第2步。

例5 p23，参[1] p20例2-8，2-9，2-10 2.3.4牛顿法的收敛性及收敛速度

定理2-5 牛顿迭代法平方局部收敛定理 设x*是方程f(x)?0的单根，且

f(x)在x*的某邻域有二阶连续导数，则牛顿法在x*附近局部收敛，且至少是

二阶收敛，有

limk??ek?1ek2?limk??x*?xk?1x?xk*2?f??(x*)2f?(x)* （参[6]p61）

问题与思考：

1．牛顿法的收敛性与初值x0的选取是否有关系？ 有 2．当有重根即f(x*)=0时，牛顿法仍收敛吗？ 是 3．当x*是方程f(x)?0的m重根时，是否仍平方收敛？

线性收敛，且limk??xk?1?x*xk?x*?m?1 m4．收敛速度与得光滑性有关系吗？ 有 例6 p23

定理2-6 收敛充分条件 若f(x)在区间[a,b]上满足： （1）f(a)?f(b)?0； 有根 （2）f?(x)?0； 唯一根 （3）f??(x)不变号； {xk}单调有界 （4）选取初值x0?[a,b]，使f(x0)f??(x0)?0， 自身映射 则牛顿法产生的迭代序列单调收敛于方程f(x)?0在该区间上的惟一解。

例 用牛顿迭代法推导求a(a?0)的迭代公式，并求收敛的阶。

7

解 方法一：设f(x)?x2?a，则有xk?1?此时，??(x)?1a(xk?)。 2xk1aa1(1?2)，???(x)?3，??(a)?0，???(a)??0， 2x4x4a故该迭代公式为二阶收敛迭代公式。

2xka1方法二：设f(x)?1?2，则有xk?1?xk(3?)。

x2a3x33x23此时，??(x)??，???(x)??，??(a)?0，???(a)???0，由于

a22aa6af??(x)??4，故取x0?(0,a)时，迭代公式二阶收敛。

x3a方法三：设f(x)?(x2?a)2，则有xk?1?xk?，此时

44xk3a1?2，由于?(a)?a，而0???(a)??1， 44x2故该迭代公式仅为线性收敛迭代公式。

??(x)?2.3.5牛顿法的特点及牛顿下山法

牛顿法有以下特点：

? 收敛速度快，达到平方收敛；

? 计算量较大，对函数f(x)解析性质要求较高。

? 具有局部收敛性，即当初值x0与x*太远时，收敛速度很慢，甚至不收敛，仅在x*附近可达到平方收敛；

将牛顿迭代公式修改为以下形式

f(xk) xk?1?xk??

f?(xk)111其中参数??(0,1)称为下山因子。用试算的方法选取?(1,,2,3,?)，使得

222f(xk?1)?f(xk)

称满足上述要求的算法为牛顿下山法。

2.4 弦位法

2.4.1 弦位法的思想

弦位法又称弦截法或割线法。是用差商代替牛顿公式中的微商f?(xk)；或者说是用f(x)在点(xk?1,f(xk?1))和(xk,f(xk))处的割线的零点作为新的迭代点

8

xk?1?xk?2.4.2 弦位法的几何意义 略

2.4.3 弦位法的计算步骤 略

2.4.4 弦位法的收敛性及收敛速度

f(xk)(xk?xk?1)

f(xk)?f(xk?1)定理2-7 设x*是方程f(x)?0的单根，且f(x)在x*的某邻域有二阶连续导数，则?x0,x1?N(x*,?)，弦位法在x*附近局部收敛，且按阶1.618收敛到x*。 2.4.4 弦位法的特点

? 收敛速度夹较快，但比牛顿法慢； ? 超线性收敛，收敛阶为1.618；

? 无需计算导数，每步只需计算一次函数值；

? 属于多点迭代，而牛顿法和一般迭代法属于单点迭代。

2.5 迭代法的改善与加速

2.5.1 一般的加速算法

加速算法思想是先求xk?1??(xk)，然后选取合适的数m和n，令 xk?1?mxk?1?nxk 作为下一次迭代点。

为选取合适的线性组合系数m,n。由于?(x)连续，且x*??(x*)，从而 x*?xk?1??(x*)??(xk)???(?)(x*?xk) 用a近似代替上式中的??(?)，立即有 x*?xk?1?a(x*?xk) 整理得

1axk?1?xk 1?a1?a从而得到加速迭代公式

1axk?1??(xk)?xk

1?a1?a x*?2.5.2 埃特金（Aithen）加速算法

埃特金算法的思想是将一般迭代法和弦位法相结合来实现加速迭代算法的收敛速度的。

9

为构造埃特金法加速迭代公式，设xk是x??(x)的一个近似解，首先令

?k?1??(xk) xk?1??(xk)，x?(x然后在曲线y??(x)上，过点P(x,x)和Pkk?1k?1?k?1)做连线，该直线的两点,x式方程为

?k?1?xk?1y?xk?1x ?xk?1?xkx?xk最后考虑到方程x??(x)的解是曲线y??(x)和直线y?x的交点P*的横坐标，

?与直线y?x的交点P代替P*,即用点P的横坐标作为x??(x)的可用弦PPk?1k?1一个近似解，其值可通过将上式中的y用x代替并解出x得到

?k?1?xk2?1xkx x??k?1xk?2xk?1?x用上式进一步可以构造出两种具有加速收敛的迭代公式

?k?1?2xk2?1?k?1?xk)2xkx(x?k?1? xk?1??x?k?1?k?1xk?2xk?1?xxk?2xk?1?x称上式为埃特金算法的迭代公式；

xk?1?k?1?2xk2?1xkx(xk?1?xk)2 ??xk???xk?2xk?1?xk?1xk?2xk?1?xk?1称上式为Steffensen（斯姬芬森）外推迭代公式。实质上，若令

?(x)?x???(x)?x?2?(?(x))?2?(x)?x，则xk?1??(xk)k?0,1,2,?称为Steffensen迭代公式。

2.5.3 埃特金算法的几何意义 略 p25图2-7 2.5.4 埃特金算法的计算步骤

3 略 例8p25，原本发散的迭代公式xk?1?xk?1 用埃特金算法是收敛的。

2.5.4 加速算法的收敛性

设x*是x??(x)的精确解，由迭代法收敛性定理知：若??(x*)在x*的某个邻域上连续，若0???(x*)?1，则迭代算法xk?1??(xk)局部收敛；若??(x*)?1，则迭代算法可能收敛，也可能不收敛；若??(x*)?1，则迭代算法肯定不收敛。但经过改进后的Aitken算法超线性收敛，Steffensen（斯基芬森）外推算法若

????(x)在x*处连续，且??(x*)?1，则算法至少有二次收敛性。

定理2-8 Steffensen迭代法收敛定理 设函数?(x)按上式定义的迭代函数：

10

(1) 若x*是?(x)的不动点，??(x)在x*处连续，且??(x)?1，则x*也是?(x)的不动点，反之，若x*是?(x)的不动点，则x*也是?(x)的不动点。

(2) 若x*是?(x)的不动点，??(x)在x*处连续，且??(x)?1，则Steffensen迭代公式至少是平方收敛。（证明见6p60）

2.6 代数方程求根

当f(x)是多项式时，方程f(x)=0称作代数方程。在牛顿迭代法中，要求

f(x0),f?(x0)，设 f(x)?a0xn?a1xn?1???an?1x?an

?(?((a0x?a1)x?a2)x??an?1)x?an令 b0?a0,bi?ai?x0bi?1(i?1,2,?,n), 则 f(x0)?bn。

为求f?(x0)，考查f(x)求导，即

f?(x)?[?((a0x?a1)x?a2)x??an?1]?x?(?((a0x?a1)x?a2)x??an?1)?([?((a0x?a1)x?a2)x??an?2]?x?(?((a0x?a1)x?a2)x??an?1))x?(?((a0x?a1)x?a2)x??an?1)?(?(a0x?a1)x??(?((a0x?a1)x?a2)x??an?2)x?(?((a0x?a1)x?a2)x??an?1))x?(?((a0x?a1)x?a2)x??an?1)则

f?(x0)?(?(a0x0?a1)x0??(?((a0x0?a1)x0?a2)x0??an?2)x0?(?((a0x0?a1)x0?a2)x0??an?1))x0?(?((a0x0?a1)x0?a2)x0??an?1) ?(?((b0x0?b1)x0?b2)x0??bn?2)x0?bn?1上述结果用于代数方程f(x)=0的牛顿迭代公式xk?1?xk?f(xk)/f?(xk) 中，f(xk),f?(xk)的计算公式如下：

?b0?a0??bi?ai?xkbi?11?i?n ?f(x)?bkn??c0?b0??ci?bi?xkci?11?i?n?1 ?f?(x)?ckn?1?2.7 求方程的m重根

设x*是方程f(x)?0的m(?2)重根，则f(x)?(x?x*)mg(x)，其中

g(x*)?0。若f(x)在x*的某个邻域内有m阶连续导数，由于 f(x*)?f?(x*)???f(m?1)(x*)?0，而f(m)(x*)?0，由泰勒展式，得

11

f(m)(?1)f(x)?(x?x*)m

m!f(m)(?2)f?(x)?(x?x*)m?1

(m?1)!f(m)(?3)f??(x)?(x?x*)m?2

(m?2)!其中?1,?2,?3介于x与x*之间，由牛顿迭代函数?(x)?x?f(x)可得 ?f(x)(x?x*)f(m)(?1)* ?(x)?lim ?(x)?lim[x?]?x(m)x?x*x?x*mf(?2)*(m?1)f(m)(?1)f(m)(?3)f(x)f??(x)1? ??(x)?lim?(x)?lim?lim?1?(m)2x?x*x?x*[f?(x)]2x?x*mm[f(?2)]*由于?(x*)?x*且0???(x*)?1，由定理2-2及2-4知，此时牛顿迭代公式收敛，但只有线性收敛速度。

为提高收敛阶数，分两种情况进行修改：

（1） 当重数m已知时，构造迭代函数?1(x)?x?显然?1(x*)?x*，利用上面的结果lim*x?xmf(x)，此时 ?f(x)f(x)f??(x)1，不难推出 ?1?2m[f?(x)]?(x*)?0，从而迭代公式xk?1??1(xk)至少平方收敛。 ?1f(x)(x?x*)g(x)（2） 当重数m未知时，令u(x)?=， *f?(x)mg(x)?(x?x)g?(x)显然，x*是u(x)的单零点。令迭代函数?2(x)?x??(x*)?lim??(x)?lim?2x?x*u(x)，此时， u?(x)u(x)u??(x)?0，从而迭代公式

x?x*[u?(x)]2 xk?1??2(xk)?xk?u(xk)f(xk)f?(xk)至少平方收敛。 ?xk?u?(xk)[f?(xk)]2?f(xk)f??(xk) P27例9 作业：p28 3,4,9,14,15,18

12

本文来源：https://www.bwwdw.com/article/tlsg.html