Cht7非线性方程求根

1§1方程求根与二分法第7章非线性方程求根一、引言非线性方程的分两类：2那么可用搜索法求有根区间.x

−1012f(x)的符号−−++求根问题的三个方面：存在性，分布，精确化。3§1方程求根的二分法

方程求根步骤：①根的隔离

确定根所在的区间[a,b],使在[a,b]内至少有方程的一个根.有根区间②近似根的精确化根的一个近似值后,构造某种算法,将此近似值精确化,使其满足给定的精度要求.越小越好上一页下一页

返回

4下面介绍方程求根的二分法在确立了有根区间[a,b]后,需要逐步缩小有根区间.取[a,b]的中点x0=(a+b)/2,将区间一分为二.假设f(x0)=0,那么x0就是方程的根,否那么判别根x*在x0的左侧还是右侧.不管出现哪种情况,(a1,b1)均为新的有根区间,它的长度只有原有根区间长度的一半,到达了压缩有根区间的目的.上一页下一页

返回

5

重复以上过程,继续进行二分,可得一系列有根区间

由于每个小区间都是有根区间,所以这个点就是所求方程的根.

同时,在每次二分时,所求出的中点形成一个无穷数列这个数列必定收敛于x*.上一页下一页

返回

6abx0x1a1b2Whentostop?x*b1上一页下一页

返回

a27误差分析：第1步产生的有误差第k步产生的xk－1

有误差对于给定的精度

,可估计二分法所需的步数k：①算法简单;

②对f(x)

要求不高(只要连续即可)，收敛性总能得到保证①无法求复数根及偶数重根〔函数值的正负号相同〕；②要计算很屡次函数值，收敛慢二分法的误差估计式上一页下一页

返回

8例1

用二分法求f(x)=x3-x-1=0在区间[1,1.5]内的一个实根,要求误差不超过0.005.解：由题可知x*(1,1.5)

,要想解之得取n＝6.按二分法计算的过程见下表,x6为所求之近似根.上一页下一页

返回

9nanbnxnf(xn)备注01.01.51.25-①f(a0)<0,f(b0)>0②根据精度要求xn取到小数点四位即可.11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-上一页下一页

返回

10逐步搜索法从区间[a，b]的左端点a出发,按选定的步长h>0一步步向右搜索,假设：那么区间[a+jh,a+(j+1)h]内必有根.上一页下一页

返回

于是可确定一个缩小了的有根区间[a+jh,a+(j+1)h].

再对新的有根区间，取新的更小的预定步长，继续搜索，直到有根区间的长度足够小。搜索过程也可从b开始,这时应取步长

h<0.11§2迭代法及其收敛性一、不动点迭代1213例2

用迭代法求方程x4+2x2-

x-3=0在区间[1,1.2]内的实根.解：对方程进行如下三种变形

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

准确根x*=1.124123029,可见迭代格式不同,收敛情况也不同,收敛速度也不同.上一页下一页

返回

14迭代法的几何意义交点的横坐标y=x15迭代法需解决的三个问题迭代函数的构造由迭代函数产生的解序列的收敛性序列的收敛速度和误差估计16kxk012345671.51.357211.330861.325881.324941.324761.324731.3247217二、不动点的存在性与迭代法的收敛性1819202122

(k=1,2,…)反之,若在区间R内,则迭代必发散.上一页下一页

返回

L越小收敛越快尚未计算时便估计出第k次迭代近似值的误差,称为事先误差估计.23

由定理1的误差估计式可看出,只要相邻两次迭代近似值xk与xk-1的偏差|xk–xk-1

|充分小,就可以保证迭代值xk足够精确.这种用前后两次迭代结果估计误差的方法称为事后误差估计上一页下一页

返回

因此对于给定的允许误差ε,当L较小时,常用前后两次迭代是否满足

|xk–xk-1

|<ε

来终止迭代.24不但可以估计迭代k次时的误差,也可以用来确定到达误差精度要求的迭代次数k.当要求误差精度为ε,即要求,只要即可,从中解出k为实际应用中,控制迭代结束的条件也常取为E<ε其中上一页下一页

返回

25xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=φ(x)y=φ(x)y=φ(x)y=φ(x)x0p0x1p1

x0p0x1p1

x0p0x1p1

x0p0x1p1

上一页下一页

返回

迭代过程的几何解释如以下图26上一页下一页

返回

例4

对于例2中的三种迭代法，讨论它们的收敛性。解：对于下面三种迭代函数其导函数在[1,1.2]内分别有

根据定理1，例2中的第三种迭代法发散，第一、二种迭代格式收敛，而且第二种迭代法比第一种迭代法收敛快得多。这与实际计算结果完全吻合。27上一页下一页

返回

例5解：即可得等价的方程

有时，对于不满足定理条件的问题，可以通过转化，化为适合于迭代的形式。令那么有故28三、局部收敛性与收敛阶2930kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4)0123

׃

x0

x1

x2

x3

׃23987׃21.521.5׃21.751.734751.732631׃21.751.7321431.732051׃313233例6

证明迭代公式是求的三阶方法.假设xo充分靠近x*,求解：此迭代格式的迭代函数为方程两边对x

求导,得上一页下一页

返回

34再将上式两边对x

求导,得上式再对x

求导,得上一页下一页

返回

所以，迭代格式是3阶收敛的.35§3迭代收敛的加速方法一、埃特金加速收敛方法36373839

Aitken加速：xyy=xy=g(x)x*x0P(x0,x1)x1x2P(x1,x2)一般地，有：比收敛得略快。40二、斯蒂芬森迭代法41Steffensen迭代格式几何解释

42kxkykzk0123451.51.416291.355651.329851.324801.324722.375001.840921.491401.347101.3251812.39655.238882.317281.444351.32714说明:(2.2)不收敛,(3.3)可能收敛;(2.2)线性收敛,(3.3)平方收敛!43kxkykzk0123.53.734443.733073.604143.733813.662023.7334744假设对此格式用Steffensen法,那么上一页下一页

返回

例745§4牛顿法一、牛顿法及其收敛性4647图7-34849定理上一页下一页

返回

〔收敛的充分条件〕设fC2[a,b]，假设(1)f(a)f(b)<0；(2)在整个[a,b]上f’’不变号且f’(x)0；(3)选取x0[a,b]使得f(x0)f”(x0)>0；那么牛顿迭代法产生的序列{xk}收敛到f(x)在[a,b]的唯一根。定理有根根唯一产生的序列单调有界，保证收敛。保证f(x)上凸或下凸50上一页下一页

返回

与上一节例7相比，牛顿法的收敛速度快很多。

例9

51上一页下一页

返回

牛顿迭代法的流程图52注：牛顿迭代法的收敛性依赖于x0

的选取。x*x0

x0

x0上一页下一页

返回

53上一页下一页

返回

1054二、牛顿法应用举例kxk01230.50.571020.567160.56714kxk012341010.75000010.72383710.72380510.72380555〔4.5〕这种迭代公式对于任意初值都是收敛的.事实上，对〔4.5〕式施行配方手续，易知以上两式相除得据此反复递推有〔4.6〕56记整理〔4.6〕式，得对任意，总有，故由上式推知，当时，即迭代过程恒收敛.57三、简化牛顿法与牛顿下山法图7-458〔2〕牛顿下山法.牛顿法收敛性依赖初值的选取.如果偏离所求根较远，则牛顿法可能发散.例如，用牛顿法求方程〔4.8〕在附近的一个根.设取迭代初值，用牛顿法公式〔4.9〕计算得迭代3次得到的结果有6位有效数字.59但如果改用作为迭代初值，则依牛顿法公式（4.9）迭代一次得这个结果反而比更偏离了所求的根.为了防止迭代发散，对迭代过程再附加一项要求，即具有单调性：〔4.10〕满足这项要求的算法称下山法.将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度.将牛顿法的计算结果60与前一步的近似值适当加权平均作为新的改进值〔4.11〕其中称为下山因子，（4.11）即为〔4.12〕(4.12)称为牛顿下山法.选择下山因子时从开始，逐次将减半进行试算，直到能使下降条件（4.10）成立为止.若用此法解方程（4.8），当时由（4.9）求得61，它不满足条件（4.10）.通过逐次取半进行试算，当时可求得

.此时有，而显然.由计算时,均能使条件（4.10）成立.计算结果如下：即为的近似.一般情况只要能使条件（4.10）成立，则可得到，从而使收敛.62Q1:

若，牛顿迭代法是否仍收敛？设x*是f

的m

重零点,则：且A1:

有局部收敛性，但仅为线性收敛.下面介绍计算重根的牛顿迭代法上一页下一页

返回

63因此,求f(x)=0之m重根x*等价于求

(x)=0

的单根x*

。而对(x)=0用牛顿迭代法求根那么是平方收敛的,其迭代格式为令，则f

的重零点就是

的单零点。A2:

方法1：将求

f

的重零点转化为求另一函数的单零点。Q2:

如何加速求重根的收敛速度？上一页下一页

返回

64方法2：采用如下迭代格式可以证明它是求m重根x*的具有平方收敛的迭代格式.如何确定根的重数m?那么：上一页下一页

返回

65例11

用牛顿迭代法求方程解：kxkλk1/(1-λk)00.9510.974427920.987058330.99348780.50902.036940.99673280.50472.019050.99835760.50072.002860.99919010.51252.0511上一页下一页

返回

66上一页下一页

返回

67例12

用3种方法求解方程解：上一页下一页

返回

都取x0=1.5，计算结果见下表：68方法〔2〕和方法〔3〕都是二阶方法，x3都精确到了小数点后第9位，方法〔1〕即普通牛顿迭代法，解重根是一阶方法，要近30次迭代才能有相同的精度。xk方法（1）方法（2）方法（3）x01.51.51.5x11.4583333331.4166666671.411764706x21.4366071431.4142156861.414211438x31.4254976191.4142135621.414213562上一页下一页

返回

69四、重根情形7071kxk(1)(2)(3)0123x0x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.41421356272§5弦截法与抛物线法73图7-574弦截法与切线法〔牛顿法〕都是线性化方法，但两者有本质的区别.切线法在计算时只用到前一步的值，而弦截法（5.2），在求时要用到前面两步的结果，因此使用这种方法必须先给出两个开始值.

例10用弦截法解方程

解设取作为开始值，用弦截法求得的结果见表7-8，比较例7牛顿法的计算结果可以看出，弦截法的收敛速度也是相当快的.实际上，弦截法具有超线性的收敛性.7576

7.5.2抛物线法设已知方程的三个近似根，以这三点为节点构造二次插值多项式，并适当选取的一个零点作为新的近似根，这样确定的迭代过程称抛物线法，亦称密勒（Müller）法.在几何上，这种方法的基本思想是用抛物线与轴的交点作为所求根的近似位置（图7-6).图7-677插值多项式有两个零点：〔5.3〕式中问题是该如何确定，假定在三个近似根中，更接近所求的根，为了保证精度，选（5.3）中较接近的一个值作为新的近似根.为此，只要取根式前的符号与的符号相同.78

例11用抛物线法求解方程

解设用表7-8的前三个值作为开始值，计算得故代入〔5.3〕式求