非线性方程求解课件

第二章非线性

方程求解

第二章非线性

方程求解1第二章非线性方程求解目录§1对分法§2迭代法

2.1迭代法的基本思想2.2迭代法的收敛条件2.3Steffensen方法——简单迭代

法的加速§3Newton法与弦截法

3.1Newton法3.2弦截法§4抛物线法第二章非线性方程求解目录§1对分法2第二章非线性方程求解概述很多科学计算问题常归结为求解方程：

第二章非线性方程求解概述很多科学计算问题常3非线性方程求解概述(续）例如，从曲线y=

x和y=lgx的简单草图可看出方程lg

x+x=0有唯一的正根x*，但是没有求x*的准确值的已知方法，即使是对代数方程，要求其精确解也是困难的。对于二次方程ax2+bx+c=0，我们可以用熟悉的求根公式：

对于三、四次代数方程，尽管存在求解公式，但并不实用。而对于大于等于五次的代数方程，它的根不能用方程系数的解析式表示，至于一般的超越方程，更没有求根公式。因此，为求解一个非线性方程，我们必须依靠某种数值方法来求其近似解。对于方程（2-1）要求得其准确解一般来说是不可能的。非线性方程求解概述(续）例如，从曲线y=x和4求方程根近似解的几个问题：求方程根的近似解，一般有下列几个问题：

3.根的精确化：已知一个根的粗略近似值后，建立计算方法将近似解逐步精确化，直到满足给定精度为止。设函数f(x)在区间[a,b]上连续，严格单调，且f(a)f(b)<0，则在[a,b]内方程f(x)=0有且仅有一个实根。

根据此结论，我们可以采用如下两种方法求出根的隔离区间。1.根的存在性：方程是否有根？如果有根，有几个根？2.根的隔离：确定根所在的区间，使方程在这个小区间内有且仅有一个根，这一过程称为根的隔离，完成根的隔离，就可得到方程的各个根的近似值。

关于根的存在性是纯数学问题，不详细介绍，可查阅有

关代数学内容。

根的隔离主要依据如下结论：求方程根近似解的几个问题：求方程根的近似解，一般有下列几个5求根的隔离区间的两种方法1.描图法：

画出y=f(x)的草图，由f(x)与x轴交点的大概位置来确定有根区间。也可利用导函数f

(x)的正、负与函数f(x)的单调性的关系来确定根的大概位置。例1

求f(x)=3x

1

cosx=0的有根区间解：将方程变形为3x

1=cosx绘出曲线y=3x

1及y=cosx，由图2-1可知，方程只有一个实根：yxx*图2-1例2紧接下屏求根的隔离区间的两种方法1.描图法：6例2（续）2.逐步搜索法：

从区间[a,b]的左端点a出发，按选定的步长h一步步向右搜索，若:则区间[a+jh,a+(j+1)h]内必有根。搜索过程也可以从

b开始，这时应取步长h<0。求出根的隔离区间后，就可采用适当的方法，使其进一步精确化。解：

令f

(x)=4x3

12x2=0，可得驻点x1=0,x2=3,由此而得到三个区间(

,0)(0,3),(3,

),

f

(x)在此三个区间上的正负号分别为“

”，“

”，“+”，由此可见，函数f(x)在此三个区间上为“减”，“减”，“增”，并且因为f(

)>0,f(0)=1>0,f(3)=

26<0,f(

)>0所以仅有二个实根，分别位于(0,3),(3,

)内。又因f(4)=1>0,所以，二个隔根区间确定为(0,3),(3,4)。例2（续）2.逐步搜索法：7§1对分法

设f(x)在区间[a,b]上连续，严格单调，且f(a)f(b)<0，不妨设f(a)<0,f(b)>0，则方程f(x)=0在[a,b]内存在唯一实根，对分法的基本思想是：用对分区间的方法，通过判别函数f(x)在每个对分区间中点的符号，逐步将有根区间缩小，最终求得一个具有相当精确程度的近似根。具体步骤为:§1对分法设f(x)在区间[a,b8对分法（续）

若每次对分区间时所取区间中点都不是根，则上述过程将无限地进行下去，当n→∞时，区间将最终收缩为一点x*，显然x*就是所求方程的根。对分法（续）若每次对分区间时所取区间中点都不9对分法的误差估计作为x*的近似值，则误差为：

只要n足够大（即区间对分次数足够多），xn的误差就可足够小，且只要f(x)连续，对分区间总是收敛的。

式（2-2）不仅可以估计对分区间法的误差，而且可以给定的误差限

估计出对分区间的次数，因为由式（2-2）有：

若取区间[an,bn]的中点：对分法的误差估计作为x*的近似值，则误差为：只要n足够大（10对分法举例例3解：因为f(x)连续且f

(x)=3x2+10>0(

x

(

,

))，故f(x)在(

,

)上单调增加而f(1)=

9<0,f(2)=8>0

所以原方程在（1，2）内有唯一实根。对分法举例例3解：因为f(x)连续且f11例3(续)Nanbnxnf(xn)0121.5-1.62511.521.752.85937521.51.751.6250.5410156331.51.6251.5625-0.5603027341.56251.6251.59375-0.0143127451.593751.6251.6093750.2621727061.593751.60937501.60156250.1236367271.593751.60156251.59765620.0545888581.593751.59765621.59570310.0201197991.593751.59570311.59472660.00289896101.593751.59472661.5942383-0.00570803111.59423831.59472661.5944824-0.00140482121.59448241.59472661.59460450.00074700131.59448241.59460451.5945435-0.00032893141.59454361.59460461.5945741

表2-1例3(续)Nanbnxnf(xn)0121.5-1.625112对分法的优缺点

对分法的优点是计算简单，

方法可靠，容易估计误差。

但它收敛较慢，不能求偶次

重根，也不能求复根。

因此，一般在求方程近似根

时，很少单独使用，常用于为其

他高速收敛算法（如牛顿法）提

供初值。对分法的优缺点对分法的优点是计算简单，

方13§2迭代法

迭代法是求解方程f(x)=0

的根的一种主要方法。它是利

用同一个迭代公式，逐次逼近

方程的根，使其得到满足预先

给定精度要求的近似值。§2迭代法迭代法是求解方程f(x)142.1迭代法的基本思想

迭代法是一种重要的逐次逼近法，其基本思想是：

设方程f(x)=0在区间[a,b]内有一根x*，将方程化为等价方程x=

(x)，并在[a,b]内任取一点x0作为初始近似值，然后按迭代公式计算：产生迭代序列x0,x1,…,xn,…,显然，若{xn}收敛于x*，

(x)在x*处连续，就有:

这种求根方法称为迭代法，式（2-3）称为迭代格式，

(x)称为迭代函数，x0称为迭代初值，{xn}称为迭代序列如果迭代序列收敛，则称迭代格式（2-3）收敛，否则称为发散。即：x*是方程f(x)=0的解。故：当n充分大时，可取xn作为方程的近似解。满足x=

(x)的点x也称为不动点2.1迭代法的基本思想迭代法是一种重要15迭代法举例例4解：容易验证，方程在[1,2]内有根，取x0=1.5迭代法举例例4解：容易验证，16例4（续）nxnnxn01.581.594493411.632653191.594590021.5790858101.594550831.6008309111.594566741.5920196121.594560351.5955928131.594562961.5941442141.594561871.5947315151.5945622表2-2例4（续）nxnnxn01.581.594493411.6317迭代法举例续例5解：

对方程进行变换，可得如下三种等价形式：

分别按以上三种形式建立迭代格式，并取x0=1进行迭代计算，结果如下：

例5的计算结果表明：将一方程化为等价方程的方法很多，由此可构造许多不同的迭代函数，得到多种迭代格式。而它们所产生的迭代序列则可能收敛，也可能发散，可能收敛很快，也可能收敛很慢。迭代法的收敛性取决于迭代函数在方程的根的邻近的性态。迭代法举例续例5解：对方程进行变换，可得如下三种等价形式18迭代法的几何含义

从几何上看，迭代法是将求曲线y=f(x)的零点问题化为求曲线y=

(x)与直线y=x的交点，迭代过程如图2-2所示，从初始点x0出发，沿直线x=x0走到曲线y=

(x)，得点(x0,

(x0))，再沿直线y=

(x0)走到直线y=x，交点

为(x1,

(x1))，如此继续下去，越来越接近点(x*,x*)。

y=xy=

(x)xx0x2x*x1xyy=xy=

(x)x2x0x*x1图2-2迭代法的几何含义从几何上看，迭代法是将求曲线19当然，迭代过程也可能出现图2-3所示的情况，此时点(xn,xn)越来越远离交点(x*,x*)，迭代序列发散。yy=xy=

(x)xx2x0x*x3x1y=xy=

(x)xx2x0x*x1图2-3

由此可见，使用迭代法必须解决两个问题：一是迭代格式满足什么条件才能保证收敛；二是如何判别迭代收敛的速度，建立收敛快的迭代格式。

迭代法的几何含义（续）当然，迭代过程也可能出现图2-3所示的情况，此时202.2迭代法的收敛条件（三大定理）定理2.1（压缩映象原理）设函数

(x)在区间[a,b]上满足条件：

则方程x=

(x)在[a,b]内有唯一的根x*，且对任意初值x0

[a,b]，迭代序列：证明见下屏：定理

给出了判别迭代收敛的充分条件。2.12.2迭代法的收敛条件（三大定理）定理2.1（压缩映21压缩映象原理的证明由条件（2）易得

(x)在[a,b]上连续。令

(x)=x

(x)，则

(x)也在[a,b]上连续，且：由连续函数介值定理，存在

[a,b]，使得

(

)=0，即

=

(

)所以方程x=

(x)在[a,b]内有根。

假设方程x=

(x)在[a,b]内有两个根x1*

x2*，由条件（2）有：导出矛盾，唯一性得证。

（存在性）（唯一性）压缩映象原理的证明22对任意的x0

[a,b]，由迭代公式有：

即对任意初值x0

[a,b]，迭代序列{xn}均收敛到方程的根x*。压缩映象原理的证明（续1）（收敛性）（2对任意的x0[a,b]，由迭代公式有：即对任意初值23类似地，对任意正整数K，有：定理2.1证明中的两个误差估计式（2-5）,（2-6）是很有意义的。

压缩映象原理的证明（续2）（误差估计公式）<证毕！>利用类似地，对任意正整数K，有：定理2.1证明中的两个误差估计24两个重要误差公式说明1.

式（2-5）说明，在正常情况下，即L不太接近于1（若L接近于1，则收敛速度很慢），可用相邻两次迭代值之差的绝对值来估计误差，控制迭代次数。就停止计算，取xn作为方程的近似根。这种用相邻两次计算结果来估计误差的方法，称为事后估计法。

即当给定精度ε时，如果有：两个重要误差公式说明1.式（2-5）说明，在正常情况下，252.

而式（2-6）的误差估计，称为事前估计法，因为用它可以估计出要达到给定精度ε

所需次数n事实上，由

注意：定理8.1给出了判别迭代收敛的充分条件。在实际计算时，由于L比较难求，而我们所讨论的函数通常是可导函数，因此，实用的收敛条件是用导数的界得到的。见下屏的定理2.2：

两个重要误差公式说明（续）2.而式（2-6）的误差估计，称为事前估计法，因26迭代法的收敛条件之二定理2.2

（1）对任意的x

[a,b]，有

(x)

[a,b]；（2）存在常数0<L<1，使得对任意x

[a,b]，都有：则方程x=

(x)在[a,b]上有唯一的根x*，且对任意初值

x0

[a,b]，迭代序列：均收敛于x*，并有：证明见下屏：设函数

(x)在区间[a,b]上满足条件：迭代法的收敛条件之二定理2.2（1）对任意的x[a27定理2.2证明设x,y为[a,b]上的任意两点，由微分中值定理，在

x,y之间至少存在一点

，使得:于是：即

(x)满足定理2.1的条件（2），故结论成立。<证毕！>定理2.2证明设x,y为[a,b]上的任意两点，由微分中28定理2.2应用举例采用的三种迭代格式，在隔根区间（1,1.2）内有：

用定理2.2判别简单迭代法的收敛性比定理2.1方便如对例题5：定理2.2应用举例采用的三种迭代格式，用定理2.2判别简单29第一种迭代格式发散，第二、三种迭代格式收敛且第三种迭代格式比第二种迭代格式中的L要小，因而收敛要快得多，这与实际迭代结果完全吻合。故可取n=7，只需迭代7次就可达到所要求的精度。定理2.2应用举例（续）根据定理2.2可知，对第三种迭代格式，为使与方程近似根的误差不超过10-6，可估计迭代次数：

第一种迭代格式发散，第二、三种迭代格式收敛且第三种30应用举例Leonardo于1225年研究了方程曾经轰动一时，因为没有人知道他用的是什么方法。我们现在可用迭代法求解：还可用Newton法，弦截法求解应用举例Leonardo于1225年研究了方程曾经轰动一时，31迭代法的收敛条件之三定理2.3

定理2.1以及定理2.2中条件（1）实际很难检查因此有如下的定理2.3迭代法的收敛条件之三定理2.3定理2.1以及定理2.2中条32

定理2.3强调迭代初值x0应取在根x*的邻域中。如果对任意给定的x0，迭代格式均收敛，则称此格式具有全局收敛性，但这样的格式是极其稀少的。如果对根x*的某邻域内的任一点x0，迭代格式均收敛，则此格式具有局部收敛性。

即可保证对其中任取的一点x0迭代收敛。事实上，在用迭代法求解方程（2-1）时，常常先用对分区间求得较好的初值，然后再进行迭代。本定理给出的就是局部收敛性条件。具体解题时，虽然无法判别隔根区间是否为以x*为中心的邻域，但只要它足够小，且在邻域中满足：定理2.3

（续）定理2.3强调迭代初值x0应取在根x*的邻域332.3Steffensen方程——简单迭代法的加速收敛速度（收敛速度的阶）：成立，则称{xn}是r

阶收敛的，或称{xn}的收敛阶为r，收敛阶r的大小刻划了序列{xn}的收敛速度：

r越大，收敛越快:

r=1线性收敛

r>1超线性收敛

r=2平方收敛设序列{xn}收敛于x*，若存在正数r和a使得：2.3Steffensen方程——简单迭代法的加速收敛34{xn}的r阶收敛定理定理2.4设迭代函数

(x)在x*邻近有r阶连续导数，且x*=

(x*)，并且有证明：1）

(x)满足收敛定理的条件

{xn}

x*；

紧接下屏{xn}的r阶收敛定理定理2.4设迭代函数(35定理2.4（续）2）利用Taylor公式将

(x)在x*附近展开：

这表明：{xn}是r阶收敛的。一阶收敛即为线性收敛，收敛速度较慢，下面想法加速：

<证毕！>定理2.4（续）2）利用Taylor公式将(x)在x*附近361、Aitken加速法若序列{xn}线性收敛于x*，可按式：

当n充分大时，有：紧接下屏1、Aitken加速法若序列{xn}线性收敛于x*，可37Aitken加速法（续）由此式可推导出：

由此可得比值：

Aitken加速法（续）由此式可推导出：由此可得比值：382、Steffensen加速收敛式将Aitken加速法与简单迭代格式xn+1

=

(xn)相结合就得到Steffensen加速收敛式

：当n

时，比值中分子趋于0的速度比分母趋于0的速度快，亦即分子是比分母高阶的无穷小，这表明{xn}比{xn}更快地收敛于x*。2、Steffensen加速收敛式39例6于是由x0=1.5，可计算：

继续下去，在此可求x2,x3,…由此例题可见：Steffensen方法收敛很快，达到了加快收敛的目的。Steffensen加速收敛举例用Steffensen方法求方程：

的根，取x0=1.5，误差精度

=10

6。

例6于是由x0=1.5，继续下去由此例题可见：Steff40§3Newton法与弦截法3.1Newton法

将非线性方程线性化，以线性方程的解逐步逼近非线性方程的解，这就是Newton法的基本思想。设已知方程f(x)=0的近似根x0，f(x)在其零点x*邻近一阶连续可微，且f

(x)

0，当x0充分接近x*时，f(x)可用Taylor公式近似表示为：则方程f(x)=0可用线性方程近似代替，即：§3Newton法与弦截法3.1Newton法41Newton法（续）解此线性方程得：

取此x作为原方程的新近似值x1，重复以上步骤，于是得迭代公式：按式（2-7）求方程f(x)=0近似解称为Newton法。Newton法（续）解此线性方程得：取此x作为原方42Newton法的几何意义如此继续下去，xn+1为曲线上点(xn,f(xn))处的切线与x轴的交点。因此Newton法是用曲线的切线与x轴的交点作为曲线与x轴交点的近似，故Newton法又称为切线法。

Xx*x2x1x0Y图2-4

Newton迭代法有着明显的几何意义如图2-4所示，过点(x0,f(x0))作曲线y=f(x)的切线，

切线方程为：

y=f(x0)+f

(x)(x

x0)

该切线与x轴的交点的横坐标即为新的近似值x1，而x2则是曲线上点(x1,f(x1))处的切线与x轴的交点。Newton法的几何意义如此继续下去，xn+1为43Newton法举例例7解：

因为f

(x)=3x2+10，故Newton迭代公式为：

x1=1.5970149，x2=1.5945637，x3=1.5945621=x4

迭代三次所得近似解就准确到8位有效数字。代入初值x0得：

可见Newton法收敛很快。一般地，有如下屏定理2-5：Newton法举例例7解：因为f(x)=3x2+144Newton法收敛定理定理2.5

设函数f(x)在其零点x*邻近二阶连续可微，且f

(x*)

0，则存在

>0，使得对任意x0

[x*

,x*+

]，Newton法所产生的序列{xn}至少二阶收敛于x*。按式（2-7），Newton法的迭代函数为：于是有：

证明：Newton法收敛定理定理2.5设函数f(x)在其零点x45定理2.5（续）由已知f

(x)在x*邻近连续，因而

(x)在x*邻近连续，且根据定理2.4，Newton法产生的序列{xn}至少二阶收敛于x*。<证毕！>

定理2.5表明，当初值x0充分接近x*时，Newton法的收敛速度较快，但当初值不够好时，可能会不收敛或收敛于别的根，这可从Newton法的几何意义看到：紧接下屏定理2.5（续）由已知f(x)在x46Newton法的几何意义及其优劣如图2-5（a）所示.应用中可由实际问题的背景来预测利用对分区间法求得较好的初值x0。使在其邻近f

(x)f

(x)不变号，并且使f(x0)f

(x0)>0，这就能保证收敛，如图2-5（b）~（d）。

Newton法具有收敛快，稳定性好，精度高等优点，它是求解非线性方程的有效方法之一。但它每次迭代均需要计算函数值与导数值，故计算量较大。而且当导数值提供有困难时，Newton法无法进行。x1x0x*X(a)x1x0x*X(b)x*x0x1X(c)x*x1x0X(d)（图2-5）Newton法的几何意义及其优劣如图2-5（a）所示.应用中473.2计算重根的牛顿迭代法

若x*为方程f(x)=0的m(m>1)重根，则f(x)可表为:

其中g(x*)

0，此时用牛顿迭代法求x*仍然收敛，只是收敛速度将大大减慢。事实上，因为:

3.2计算重根的牛顿迭代法若x*为方程f(x)48计算重根的牛顿迭代法(续1）可见用牛顿法求方程的重根仅为线性收敛。

为了提高求重根的收敛速度，有两种可供选择方法:(1)方法之一是将求重根的问题转化为求单根。注意到函数：计算重根的牛顿迭代法(续1）可见用牛顿法求方程的重根仅为线性49计算重根的牛顿迭代法(续2）

上述迭代格式右端较复杂，应用起来不方便。(2)另一种求m重根的方法是采用如下迭代格式：

可以证明它是求m重根x*的具平方收敛的迭代格式。

问题是如何确定根的重数m？下面介绍一个边迭代边估计重数方法。设xk－2，xk－1，xk为用牛顿迭代格式（2-7）所得三个相邻的迭代值，令

计算重根的牛顿迭代法(续2）上述迭代格式右端较复杂，50计算重根的牛顿迭代法(续3）则由式（2-8）可知故因此可用下式估计m

计算重根的牛顿迭代法(续3）则由式（2-8）可知故因此可51例8用牛顿迭代法求方程

在0.95附近之根。解

取x0=0.95，用牛顿迭代法，按式（2-7）求得的xk见表2-3，由表中数据可见xk收敛很慢。由

可知，所求根为m=2重根，改用式(2-9)迭代格式，得：

收敛速度大大快于直接用牛顿迭代公式（2-6）.例8用牛顿迭代法求方程在0.95附近之根。解取x052例8（续）表2-3kxk

k01234560.950.97442790.98705830.99348780.99673280.99835760.9991901

0.50900.50470.50070.5125

2.03692.01902.00282.0511m例8（续）表2-3kxkk00.95

m533.2弦截法不足之处：需要计算导数值，较难；——这就是弦截法迭代公式

Newton法优点：收敛快（平方阶），固定格式；修正：以差商代替导数（微商）3.2弦截法不足之处：需要计算导54弦截法迭代公式的几何解释与x轴相交，即y=0，解出x得：

即以割线代替曲线f(x)，以割线与x轴的交点去近似曲线与x轴的交点，故弦截法又称为割线法。

割线法也可看作以（xn-1，f(xn-1)），(xn，f(xn))作线性插值，而以此插值多项式近似f(x)，以其零点近似f(x)的零点。弦截法迭代公式的几何解释与x轴相交，即以割55弦截法的几点说明

1。需要两个点x0，x1才能开始进行迭代：（1）若只给定x0，则须利用其他方法，如对分法，求x1，然后再利用弦截法，求x2，x3，…；

（2）若给定一有根区间，可直接用两端点作

x0，x1。{xn}收敛，收敛阶为1.618，超线性收敛。

弦截法的几点说明1。需要两个点x0，x1才能开始进行迭代：56

3.上述弦截法又称为变端点弦截法，其实还可写为：固定一端点x0，称为定端点弦截法（单点），如右图：x1x2x3x0xy图8-5弦截法的几点说明(续）

3.上述弦截法又称为变端点弦截法，其实还可57弦截法举例例9用定端点，变端点截线法求方程：

f(x)=x3

2x

5在区间[2,3]内的一个实根（有12位有效数字的实根为

=2.09455148514）。解：取x0=2,x1=3，用两种方法计算结果如下：

（见表2-4）