第二章非线性方程的解法

第二章非线性方程的解法第一页，共三十三页，2022年，8月28日第一节引言

在科学技术和生产实践中，我们经常会遇到求解高次代数方程或超越方程的问题。例如高次代数方程 X5-3X+7 =0

或超越方程e-x-cos(лx/3)=0

这些方程看似简单，但却不易求其准确根。而在实际问题中，只要能获得满足一定精确度的近似根就可以了，所以研究适用于实际计算的求方程近似根的数值方法，具有重要的现实意义。方程的形式很多，我们主要讨论一元非线性方程，也即 f(x)=0

其中f(x)为非线性函数，若有数x*使f(x*)=0,成立，则称x*为方程f(x)=0的根。或称x*为函数f(x)的零点。第二页，共三十三页，2022年，8月28日求一元非线性方程根的三个步骤（1）判断根的存在性。方程有没有根？如果有根，有几个根？

（2）确定根的初始近似值（称之为初始近似根）。（3）根的精确化。根据根的初始近似值按某种方法逐步精确化，直至满足预先要求的精度为止。第三页，共三十三页，2022年，8月28日一元非线性方程根初始近似值的求法

设f(x)在区间[a,b]上连续,且f(a)f(b)<0。根据连续函数的性质知f(x)=0在(a,b)内至少有一个实根。若再设f(x)在[a,b]上单调,那么f(x)=0在(a,b)上有且仅一个实根(如右图)。根据这个道理,我们可以采用下面介绍的逐步扫描法求根的初始近似值。abx*xyf(x)第四页，共三十三页，2022年，8月28日求根初始近似值的逐步扫描法

方程f(x)=0的根的分布可能很复杂,一般我们可用试探的办法或根据函数的图象,确定出根的分布范围,即将函数f(x)的定义域分成若干个只含一个实根的区间。于是，我们总可以假设在某个区间内有且仅有一个单实根x*(如上图)。若数值b–a较小,那么我们可在(a,b)上任取一点作为方程的初始近似根。一般若有根区间(a,b)为已知,我们可从左端x0=a出发,按某个预选的步长h一步一步地向右跨,每跨一步进行一次根的“扫描”，即检查每一步的起点x0和终点x0+h的函数值是否异号,如果发现f(x0)与f(x0+h)异号,即f(x0)f(x0+h)<0,那么所求的根x*必在区间(x0,x0+h)中,这时可取x0或x0+h作为初始近似根。

第五页，共三十三页，2022年，8月28日逐步扫描法确定方程初始近似根的计算步骤(1)x0=

a;(2)若f(x0)f(x0+h)<0,则x*必在(x0,x0+h)中，故取x0或x0+h作为初始近似根,否则转(3);（3）x0=a+h,转(2)。

第六页，共三十三页，2022年，8月28日逐步扫描法确定方程初始近似根的例子

例1考虑方程

f(x)=x3-x-1=0

由于f(0)<0,f(∞)>0,故方程至少有一正实根。

设从x=0出发,取h=0.5为步长向右计算,将各个点上的函数值的符号列于下表。因为f(1)<0,f(1.5)>0,又f(x)在区间(1,1.5)上单调连续,可知在区间(1,1.5)内有且仅有一个实根,故可取x0=1.0或x0=1.5作为初始近似根。xf(x)00.51.51–––+第七页，共三十三页，2022年，8月28日方程的初始近似根逐步精确化的方法

用逐步扫描法得到方程

f(x)=0的某个初始近似根后，就可以通过某种过程使之逐步精确化。常用的方程初始近似根逐步精确化的方法(数值解法)有：

(1)二分法(对分法）

(2)迭代法

(3)牛顿迭代法

(4)弦截法

(5)埃特金迭代法等。第八页，共三十三页，2022年，8月28日

第二节二分法

设函数在[a,b]上单调连续，且

f(a)f(b)<0根据连续函数的性质，方程

f(x)=0在区间(a,b)内有且仅有一个实根x*

。第九页，共三十三页，2022年，8月28日二分法的基本思想

将含方程根的区间均分为两个小区间，然后判断根在哪个小区间，舍去无根的区间,而把有根的区间再一分为二，再判断根属于哪个更小的区间，如此周而复始，直到求出满足精度要求的近似根。

第十页，共三十三页，2022年，8月28日二分法具体计算过程

第一次二分,取初始近似根x0=(a+b)/2,将区间(a,b)分为两个长度相等的子区间(a,x0)和(x0,b)，计算f(a)与f(x0)，若f(a)f(x0)<0则根x*∈(a,x0),令a1=a,b1=x0；否则，令a1=x0,b1=b。从而得到新的有根区间(a1,b1),其长度为区间（a,b）长度的一半。第二次二分，对有根区间(a1,b1)施行同样的手续，即取中点x1=(a1+b1)/2，再将(a1,b1)分为两个子区间(a1,x1)和(x1,b1)，计算f(a1)与f(x1)，若f(a1)f(x1)<0则x*∈(a1,x1),令a2=a1,b2=x1；否则令a2=x1,b2=b1

。这样又确定了一个有根区间(a2,b2)，其长度是区间(a1,b1)长度的一半。如此反复二分k次(k的值由预先给定的精度决定),便得到一系列有根区间：(a,b)(a1,b1)(a2,b2)…

(ak,bk)。最后，取xk=(ak+bk)/2作为方程f(x)=0根x*的近似值。第十一页，共三十三页，2022年，8月28日二分法误差分析

设a0=a,b0=b,经过k次二分后显然有

bk–ak=(b-a)/2k,(k=0,1,2,…)而|x*–xk|(bk–ak)/2=(b-a)/2k+1(Xk为第k+1次二分所得的近似值)所以

|x*–xk|(b-a)/2k+1

这就说明，经过k+1次二分后，近似值xk与准确值x*的误差不会超过(b-a)/2k+1。假定我们要求用二分法求出的近似值xk与准确值x*的误差不能超过ε

，也就是说，|x*–xk|

ε，那么我们如何确定二分的次数呢？要求|x*–xk|ε,而|x*–xk|(b-a)/2k+1,若(b-a)/2k+1ε,则|x*–xk|ε。于是我们可以利用(b-a)/2k+1

ε来确定需要二分的次数。由于要求|x*–xk|ε,而|x*–xk|(bk–ak)/2,所以在实际中也可用(bk–ak)/2ε(也就是|bk+1–ak+1|ε)来控制需要二分的次数。第十二页，共三十三页，2022年，8月28日二分法求方程f(x)=0近似根的例子

例2求方程f(x)=x3-x-1=0在区间(1,1.5）内的根，要求用四位小数计算，精确到10-2(即误差不能超过小数点后第二位小数的半个单位)。解这里a=1,b=1.5,ε=0.5×10-2,我们先估计所要二分的次数，按|x*–xk|(b-a)/2k+1

K应满足(b-a)/2k+1

ε(即(1.5-1)/2k+10.5×10-2

)求得k+1=7，即只要二分七次便可达到所要求的精度。计算过程如下：

K值xk值函数值有根区间

f(1)<0f(1.5)>0(1,1.5）

0x0=1.25

f(1.25)<0（1.25,1.5）

1x1=1.375f(1.375)>0(1.25,1.375)2x2=1.3125f(1.3125)<0(1.3125,1.375)3x3=1.3438f(1.3438)>0(1.3125,1.3438)4x4=1.3281f(1.3281)>0(1.3125,1.3281)5x5=1.3203f(1.3203)<0(1.3203,1.3281)6x6=1.3242f(1.3242)<0(1.3242,1.3281)

故原方程在区间(1,1.5)内的根x*≈x6

≈1.3242≈1.32。

第十三页，共三十三页，2022年，8月28日

二分法的计算机实现

二分法是计算机上一种常用的算法,它具有简单和易操作的优点。注意到每个小区间左端点的函数值f(ak)都与f(a)同号,因此f(xk)只需与f(a)比较符号

(不需与f(ak)比较符号。这样就避免了每次确定有根区间时需要计算f(ak)的麻烦,从而减少了计算量)即可,故二分法的计算步骤如下：

(1)输入有根区间的端点a,b及预先给定的精度ε,y=f(a)。

(2)x=(a+b)/2。

(3)若f(x)==0,则输出方程的根x,结束;若yf(x)<0,则b=x,否则a=x。

(4)若b-a<ε,则输出方程满足精度的根x,结束;否则转向(2)。第十四页，共三十三页，2022年，8月28日第三节迭代法的一般知识

第十五页，共三十三页，2022年，8月28日一、迭代法的基本思想及几何意义

第十六页，共三十三页，2022年，8月28日

迭代法的基本思想

设法将方程f(x)=0化为x=g(x)然后按该式构造迭代公式

Xk=g(xk-1)，k=1,2,…若该迭代公式收敛,则从给定的初始近似根X0出发,依次确定出

X0,X1,

X2,

…

,

Xk直到|Xk–Xk-1|<ε时,取Xk作为方程f(x)=0的近似根。这种求根法就称为迭代法，或称逐次逼近法。我们称

X0,X1,

X2,

…

,

Xk为迭代序列，而称X=g(x)式中的g(x)为迭代函数。称

Xk=g(xk-1)，k=1,2,…为迭代公式或迭代格式。当由该式产生的迭代序列收敛时，就称迭代法或该迭代公式是收敛的，否则就称为是发散的。第十七页，共三十三页，2022年，8月28日迭代法求方程f(x)=0近似根的例子

例3求方程f(x)=x-10x+2=0的一个根。解因为f(0)=1>0,f(1)=-7<0,所以此方程在(0,1)中必有一实根，现将原方程改写成等价形式

x=㏒10(x+2)由此得迭代公式xk=㏒10(xk-1+2)取初始值x0=1，可逐次算得

x1=0.4771,x2=0.3939,…,x6=0.3758,x7=0.3758因为x6和x7已趋于一致(也就是说明该迭代公式收敛，并且|Xk–Xk-1|<ε),所以取x7=0.3758作为原方程在(0,1)内的一个根的近似值。第十八页，共三十三页，2022年，8月28日迭代法的几何意义

把方程f(x)=0求根的问题改写成x=g(x),实际上是把求根问题转化为求两条曲线y=x和y=g(x)的交点A*,其A*的横坐标就是方程f(x)=0的根(如下图)。yxy=xy=g(x)x0x2x1x*0…A*(x*,g(x*))A0(x0,g(x0))A1(x1,g(x1))A2(x2,g(x2))A1′

(g(x0),g(x0))A2′(g(x1),g(x1))第十九页，共三十三页，2022年，8月28日二、迭代法的收敛条件及误差估计式

一般说来，一个方程的迭代公式并不是唯一的，且迭代也不总是收敛的。如例3的方程f(x)=x-10x+2=0也可改写成x=10x–2得迭代公式Xk=10xk-1

–2仍取x0=1算得

X1=10-2=8,X2=108-2≈108,X3=10108

-2,…

其迭代值越来越大,不可能趋向于某个极限,因此迭代是发散的。所以，我们需要讨论什么样的迭代函数才收敛，即迭代法的收敛条件是什么。迭代法的收敛性解决以后,我们还需讨论迭代法的误差情况,以确定近似值达到预先给定的精度所需的迭代次数、估计所求得的近似值与准确值之间的误差。

第二十页，共三十三页，2022年，8月28日迭代法的收敛性判别有两种方法（1）利用迭代法的几何意义如P26图2-1,如果点列{Ak}趋向于点A,则迭代序列收敛到所求的根x*，亦即迭代法收敛,见图2-1(a)和(b)；否则迭代法发散,见图2-1(c)和(d)。（2）利用定理

利用迭代法的几何意义进行判断,不仅要画图(麻烦),而且也很不准确,通常利用下面的定理来进行判断。第二十一页，共三十三页，2022年，8月28日迭代法的收敛条件及误差估计定理

设方程x=g(x)在(a,b)内有根x*，如果

(1)

当x∈[a,b]时，g(x)∈[a,b](2)

g(x)可微,且存在正数q<1,使得对任意x∈[a,b]都有

|g´(x)|≤q<1则x=g(x)在(a,b)内有唯一的根；且迭代公式

xk=g(xk-1)对(a,b)内任意初始近似根x0均收敛于方程的根x*；还有误差估计式

|x*-xk|≤|xk-xk-1|q/(1-q)≤|x1-x0|qk/(1-q)第二十二页，共三十三页，2022年，8月28日迭代法的具体计算步骤

(1)确定方程f(x)=0的等价形式x=g(x)，为确保迭代过程的收敛，要求g(x)在某个含根区间(a,b)内满足|g´(x)|≤q<1；

(2)选取初始根x0，按公式

xk=g(xk-1),k=1,2,…

进行迭代；

(3)若|Xk–Xk-1|<ε,则停止计算,x*≈Xk。第二十三页，共三十三页，2022年，8月28日迭代法的具体计算步骤举例

例4求方程x=e-x在x=0.5附近的一个根。按五位小数计算,计算结果的精度要求为ε=10-3。解过x=0.5,以步长h=0.1计算f(x)=x-e-x由于f(0.5)<0,f(0.6)>0，故所求的根在区间(0.5,0.6)内,且在(0.5,0.6)内

|(e-x)´|≤e-0.5<0.61<1因此用迭代公式xk=e-xk-1进行迭代计算是收敛的。其迭代结果如下表所示。

kxkxk–xk-1kxkxk–xk-100.560.56486-0.0063110.606530.1065370.568440.0035820.54524-0.0612980.56641-0.0020330.579700.0344690.567560.0011540.56006-0.01963100.56691-0.0006550.571170.01110由表可见x*≈X10≈0.567为方程x=e-x满足精度要求的根。第二十四页，共三十三页，2022年，8月28日迭代法的计算机实现及优点

迭代法的计算机实现可参考迭代法的具体计算步骤。

迭代法的优点是算法的逻辑结构简单，且在计算时中间结果即便有扰动也不影响计算结果。第二十五页，共三十三页，2022年，8月28日第四节牛顿迭代法(牛顿切线法）

牛顿（Newton）迭代法是求方程近似根的一种重要方法，也是计算方法中的一种基本方法。

第二十六页，共三十三页，2022年，8月28日牛顿迭代法的基本思想

设法将非线性方程f(x)=0逐步转化为某种线性方程来求解。对于非线性方程f(x)=0,设已知其近似根xk,则函数f(x)在点xk附近泰勒展开f(x)=f(xk)+f´(xk)(x-xk)+f"(xk)(x-xk)2/2!+…忽略高次项有f(x)≈f(xk)+f´(xk)(x-xk)右端是线性方程,用这个线性方程来近似非线性方程f(x)。设非线性方程f(x)=0的根为x*,则有

f(x*)=0于是有f(xk)+f´(xk)(x*-xk)≈f(x*)=0即f(xk)+f´(xk)(x*-xk)≈0解出x*≈xk–f(xk)/f´(xk)将右端取为xk+1,即xk+1是比xk更接近于x*的近似值，即

xk+1=xk–f(xk)/f´(xk)这就是牛顿迭代公式,相应的迭代函数是

g(x)=x–f(x)/f´(x)

当然牛顿迭代公式xk+1=xk–f(xk)/f´(xk)也可写为

xk=xk-1–f(xk-1)/f´(xk-1)。第二十七页，共三十三页，2022年，8月28日牛顿迭代法的几何意义

曲线y=f(x)与x轴的交点的横坐标就是方程f(x)=0的根x*。牛顿迭代法就是逐次用切线与x轴的交点来逼近曲线y=f(x)与x轴的交点x*;或者说,用y=f(x)在点(xk,f(xk))处切线与x轴的交点的横坐标xk+1来代替曲线y=f(x)与x轴交点的横坐标x*。如下图所示。

由于这一几何背景,牛顿迭代法亦称切线法。y0X*x2x1x0y=f(x)p0(x0,f(x0))p1(x1,f(x1))p2(x2,f(x2))y-f(x0)=f'(x0)(x-x0)[y=0时,x=x0-f(x0)/f'(x0)(即x1)]y-f(x1)=f'(x1)(x-x1)[y=0时,x=x1-f(x1)/f'(x1)(即x2)]第二十八页，共三十三页，2022年，8月28日牛顿迭代法的具体计算步骤

(1)给出初始近似根x0及精度ε;

(2)计算x1=x0–f(x0)/f'(x0)；

(3)

若|x1–

x0|<ε,转向(4);否则,x0=

x1,转向(2)；

(4)输出满足精度的根x1,结束。

第二十九页，共三十三页，2022年，8月28日用牛顿迭代法求方程f(x)=0近似根举例

例5用牛顿迭代法求方程xex-1=0在x=0.5附近的根(取五位小数计算),精度要求为ε=10-3

。解其牛顿迭代公式为

xk+1=xk–f(xk)/f´(xk)=xk–(xkexk-1)/[(1+xk)exk

]即xk+1=xk–(xk-e-xk)/(1+xk)取x0=0