第二章非线性方程求根

第二章非线性方程求根第1页，共90页，2023年，2月20日，星期三第二章方程求根2.1增值寻根法与二分法2.2迭代法（重点）2.3迭代收敛的加速2.4牛顿法（重点）2.5割线法第2页，共90页，2023年，2月20日，星期三历史背景代数方程的求根问题是一个古老的数学问题。理论上，n次代数方程在复数域内一定有

n个根(考虑重数)。早在16世纪就找到了三次、四次方程的求根公式，但直到19世纪才证明大于等于5次的一般代数方程式不能用代数公式求解，而对于超越方程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个。一般也不存在根的解析表达式。因此需要研究数值方法求得满足一定精度要求的根的近似解。第3页，共90页，2023年，2月20日，星期三根的概念给定方程f

(x)=0，如果有a使得f(a)=0，则称a为f(x)=0的根或f(x)的零点.设有正整数m使得f(x)=(x-a)mg(x)且g(a)0，则当m2时，称a为f(x)=0的m重根；当m=1时，称为f(x)=0的单根.本章只讨论实根的求法.第4页，共90页，2023年，2月20日，星期三

本章重点介绍求解非线性方程的几种常见和有效的数值方法,简单介绍一些最基本的解法.无论在理论上,还是在实际应用中,这些数值解法都是对经典的解析方法的突破性开拓和补充,许多问题的求解,在解析方法无能为力时,数值方法则可以借助于计算机出色完成.第5页，共90页，2023年，2月20日，星期三2.1.1增值寻根法求非线性方程确定方程的有根区间(如增值寻根法)计算根的近似值（如二分法）有根区间：存在根隔根区间：唯一根的根的方法常分为两步：第6页，共90页，2023年，2月20日，星期三零点定理：设，且，则方程在区间上至少有一个根。如果在上恒正或恒负，则此根唯一。零点定理第7页，共90页，2023年，2月20日，星期三等步长扫描用计算机求有根区间：等步长扫描法。设h>0是给定的步长，取，若则扫描成功；否则令，继续上述方法，直到成功。如果则扫描失败。再将h

缩小，重复以上步骤。第8页，共90页，2023年，2月20日，星期三例题例设方程解：取h=0.1,扫描得：又即在有唯一根。第9页，共90页，2023年，2月20日，星期三设有非线性方程f(x)=0其中，f(x)为[a,b]上连续函数且设 f(a)f(b)<0不妨设方程于[a,b]内仅有一个实根。求方程实根x*的二分法过程，就是将含根区间[a,b]逐步分半，检查函数符号的变化，以便确定含根的充分小区间。2.2二分法第10页，共90页，2023年，2月20日，星期三示意图ba1b2x*ab1a2第11页，共90页，2023年，2月20日，星期三二分法的步骤用二分法(将区间对平分)求解。令若，则为有根区间，否则为有根区间记新的有根区间为，则且第12页，共90页，2023年，2月20日，星期三二分法对重复上述做法得且

第13页，共90页，2023年，2月20日，星期三

设所求的根为，则即取为的近似解，则

第14页，共90页，2023年，2月20日，星期三收敛速度可用二分法求方程实根x*的近似值到任意指定的精度。事实上，设ε为给定精度要求，试确定分半次数n使由两边取对数，即得且二分法收敛速度与公比为1/2的等比级数相同。第15页，共90页，2023年，2月20日，星期三

解:为达到要求的精度，用二分法需进行

即最多需要11次二分。第16页，共90页，2023年，2月20日，星期三k1[1.0,2.0]1.52.3752[1.0,1.5]1.25-1.7968753[1.25,1.5]1.3750.1621093754[1.25,1.375]1.3125-0.8483886725[1.3125,1.375]1.34375-0.3509826666[1.34375,1.375]1.359375-0.0964088447[1.359375,1.375]1.36718750.0323557858[1.359375,1.367187500]1.36328125-0.0321499719[1.363281250,1.367187500]1.3652433750.00007202510[1.363281250,1.365234375]1.364257813-0.01604669111[1.364257813,1.365234375]1.364746094-0.00798926312[1.364746094,1.365234375]1.364990235-0.003959102计算结果

第17页，共90页，2023年，2月20日，星期三2.2.1迭代法基本思想对于有时可以写成形式如：第18页，共90页，2023年，2月20日，星期三迭代法及收敛性考察方程。一般不能直接求出它的根。但如果给出根的某个猜测值，代入中的右端得到，再以为一个猜测值，代入的右端得反复迭代得第19页，共90页，2023年，2月20日，星期三简单迭代法（单点迭代法）将变为另一种等价形式。选取的某一近似值，则按递推关系产生的迭代序列。这种方法算为单点迭代法。形如的迭代公式称为多点迭代法。第20页，共90页，2023年，2月20日，星期三迭代法及收敛性若收敛，即则得的一个根称此迭代过程收敛。第21页，共90页，2023年，2月20日，星期三迭代法的几何意义交点的横坐标xyy=xx*y=(x)x0p0x1p1第22页，共90页，2023年，2月20日，星期三例题例试用迭代法求方程在区间(1，2)内的实根，初始近似值取１.５。解：由建立迭代关系

k=0,1,2,3,…计算结果如下:第23页，共90页，2023年，2月20日，星期三例题精确到小数点后五位kxkKxk01.551.3247611.3572161.3247321.3308671.3247231.3258881.3247241.32494第24页，共90页，2023年，2月20日，星期三例题但如果由建立迭代公式仍取，则有，显然结果越来越大，是发散序列第25页，共90页，2023年，2月20日，星期三２.２.３迭代法收敛的条件压缩映像原理

设迭代函数在闭区间上满足（1）（2）满足Lipschitz条件即:有且，称为李普希兹常数。第26页，共90页，2023年，2月20日，星期三压缩映像原理则在上存在唯一解，点也称为函数的不动点。且对，由产生的序列收敛于。第27页，共90页，2023年，2月20日，星期三压缩映像原理证明证明：不失一般性,不妨设

否则a或b为方程的根。根的存在性令

第28页，共90页，2023年，2月20日，星期三压缩映像原理证明则，即由是上的连续函数是上的连续函数。故由零点定理在上至少有一根第29页，共90页，2023年，2月20日，星期三压缩映像原理证明根的唯一性假设有均为方程的根，则因为0<L<1，故：，即根是唯一的。第30页，共90页，2023年，2月20日，星期三压缩映像原理证明序列的收敛性

与n无关，而0<L<1即第31页，共90页，2023年，2月20日，星期三误差估计★★第32页，共90页，2023年，2月20日，星期三误差估计若满足压缩映像原理条件，则

这是事后估计，也就是停机标准，L越小，收敛速度越快。这是事前估计。选取n，预先估计迭代次数。★★第33页，共90页，2023年，2月20日，星期三例若取迭代函数，不满足压缩映像原理，故不能肯定收敛到方程的根。第34页，共90页，2023年，2月20日，星期三例证明函数在区间[1，2]上满足迭代收敛条件。证明：第35页，共90页，2023年，2月20日，星期三

第36页，共90页，2023年，2月20日，星期三２.２.３迭代法收敛的条件第37页，共90页，2023年，2月20日，星期三2.2.3迭代法收敛的条件★★第38页，共90页，2023年，2月20日，星期三

满足Lipschitz条件满足条件１第39页，共90页，2023年，2月20日，星期三2.2.3迭代法收敛的条件

满足Lipschitz条件满足条件１第40页，共90页，2023年，2月20日，星期三注1：设方程

在区间内有根

，且存在有

，则对任意初值

，且

,迭代过程

发散.第41页，共90页，2023年，2月20日，星期三注2：定理中的假设条件：

在一般情况下，可能对于大范围的含根区间不满足，而在

根的邻近是进成立的，为此有迭代过程局部收敛性结果：

第42页，共90页，2023年，2月20日，星期三２.２.２几何示意图

第43页，共90页，2023年，2月20日，星期三1>|L|≈1

第44页，共90页，2023年，2月20日，星期三|L|较小

★L越小收敛速度越快。第45页，共90页，2023年，2月20日，星期三迭代公式：第46页，共90页，2023年，2月20日，星期三迭代公式比较第47页，共90页，2023年，2月20日，星期三迭代公式比较第48页，共90页，2023年，2月20日，星期三n（1）（2）（3）（4）01.51.51.51.51-0.8750.81651.286953771.3483997326.7322.99691.402540801.367376373-469.7

1.345458381.364957014

1.375170251.365264755

1.360094191.365225596

1.361946971.365223067

1.363887001.365229948

1.365916731.365230029

1.364878221.3652300110

1.36541006

15

1.36522368

20

1.36523024

23

1.36522998

25

1.36523001

第49页，共90页，2023年，2月20日，星期三2.2.4迭代法收敛的速度定义2设序列收敛于，令 若有实数和正常数C，使得 则称该序列是p阶收敛的；

其中C称为渐进误差常数。

★第50页，共90页，2023年，2月20日，星期三迭代法收敛的阶当p=1时，称为线性收敛；当2>p>1时，称为超线性收敛；当p=2时，称为平方收敛或二次收敛。第51页，共90页，2023年，2月20日，星期三定理3（迭代法收敛的阶）

★第52页，共90页，2023年，2月20日，星期三证明：第53页，共90页，2023年，2月20日，星期三

第54页，共90页，2023年，2月20日，星期三

第55页，共90页，2023年，2月20日，星期三

解：从而知(1)是平方收敛的。第56页，共90页，2023年，2月20日，星期三将看作由下述方程确定的隐函数从而，上式两边对求导，得从而，再两边对求导，得上式两边对求导，得令，可得第57页，共90页，2023年，2月20日，星期三例迭代过程是否收敛？如发散，试构造一收敛的迭代公式。

方程为x-4+2x=0.设f(x)=x-4+2x，则f(1)<0，f(2)>0，故方程f(x)=0在区间(1,2)内有根.题中(x)=4-2x，当x(1,2)时,'

(x)=-2xln2>2ln2>1

，由定理2不能用来迭代求根.把方程改写为x=ln(4-x)/ln2，此时(x)=ln(4-x)/ln2,则1°当x[1,2]时，(x)[1,ln3/ln2]

[1,2]2°x(1,2)，有

'(x)=

故可用迭代公式xn+1=ln(4-xn)/ln2来求解(1,2)区间内的唯一根.第58页，共90页，2023年，2月20日，星期三２.３迭代收敛的加速

２.３.１松弛法

第59页，共90页，2023年，2月20日，星期三

２.３.１松弛法

第60页，共90页，2023年，2月20日，星期三２.３.２埃特金（Aitken)方法

第61页，共90页，2023年，2月20日，星期三２.３.２埃特金（Aitken)方法

第62页，共90页，2023年，2月20日，星期三

埃特金（Aitken)方法第63页，共90页，2023年，2月20日，星期三例：

第64页，共90页，2023年，2月20日，星期三k（a）(b)(c)(d)(e)01．51．51．51．51．51-0.8750.81651.286953771.348399731.373333326.7322.99691.402540801.367376371.365262013-469.71.345458381.36495701.3652300141.03×1081.375170251.3652647581.365916731.3652300291.364878221.36523001231.36522998251.36523001对选取的gi(x)，取初始近似值x0=1.5，迭代计算结果列在表。第65页，共90页，2023年，2月20日，星期三比较可得，与x8的误差差不多。

简单观察迭代过程，(a)(b)不定，(c)(d)(e)都收敛，但收敛速度相差很大。例：对g4(x)产生的迭代序列进行Aitken加速。解:利用计算公式得第66页，共90页，2023年，2月20日，星期三第67页，共90页，2023年，2月20日，星期三

第68页，共90页，2023年，2月20日，星期三2.4牛顿迭代法

2.4.1基本思想将在点展开为Taylor展式有近似方程

★第69页，共90页，2023年，2月20日，星期三2.4.2牛顿迭代法的几何意义xyx*x0x2x1y=f(x)第70页，共90页，2023年，2月20日，星期三牛顿迭代法设方程在根附近取初始近似根由迭代公式求解方法这种求根算法称为Newton法（切线法）此公式称为Newton迭代公式.第71页，共90页，2023年，2月20日，星期三牛顿迭代法Newton法的迭代函数是从而

由此知若

是

的一个单根，则在附近Newton法是局部收敛的，并且收敛速度至少是平方收敛的.但如果

是

的m>1重根，则此时Newton法仅有线性收敛速度.第72页，共90页，2023年，2月20日，星期三2.4.3Newton法收敛的充分条件第73页，共90页，2023年，2月20日，星期三Newton迭代法收敛性证明：根的存在性根的唯一性第74页，共90页，2023年，2月20日，星期三第75页，共90页，2023年，2月20日，星期三２.４.４牛顿２阶导数法第76页，共90页，2023年，2月20日，星期三牛顿２阶导数法迭代公式第77页，共90页，2023年，2月20日，星期三由前例