应用基础数值 1

应用数值分析第八讲非线性方程（组）求根（一）2二分法

34常用的迭代方法（1）5教学小结提纲迭代法1问题引入教学目标与重难点教学目标运用二分法、迭代法及Newton迭代法解决相关问题。解释二分法、迭代法及Newton迭代法收敛原理。

1.能说出二分法、迭代法及Newton迭代法的定义及解题步骤；2.能解释二分法、迭代法及Newton迭代法收敛原理。教学重点教学难点一问题引入一、问题引入在GPS导航、电路和电力系统计算、人口出生率计算，以及非线性力学等科学与工程等计算中，常常会遇到非线性方程（组）的求根问题。挪威数学家阿贝尔于1824年证明，n次方程（n>=5)没有公式解，故求解高次方程问题的精确解是一个世界难题。除少数特殊的方程，一般都没有解析求解的方法。另外，还有大量的超越方程存在。所以，用解析方法求解是一件非常困难而几乎是不可能完成的事。在实际问题中，通常很难精确求解非线性方程（组），而是利用数值方法近似求解。为此，本章介给求解非线性方程（组）的几种常见的数值方法，这些方法均属于迭代法，即从给定的一个或几个初始近似值出发，按照一定规律产生一个迭代序列，使得该序列收敛到方程（组）的精确解。因此，当迭代次数足够多时，对应的迭代点即可作为方程（组）的近似解。一、问题引入,且

则称为的m重根。当m=1时称为单根,当m>1时称为方程的m重根，此时当g(x)充分光滑时，有的根也称为函数的零点。若可表示为

在工程应用和科学计算中，常常会遇到非线性方程

的求根问题，二二分法二、二分法定理1（零点定理）若在上连续，且，则至少存在一点基本思想：利用零点定理确定根的存在区间，逐步将含根的区间对分。通过判别函数值的符号，将根的存在区间缩小到充分小，从而求出满足精度要求的根的近似值。计算步骤为：计算函数值，（1）若，ε预先给定的误差精度，则为所求根的近似值使二、二分法当，取继续此过程就得到一个包含根的区间套，满足

当n充分大时就有误差估计式为（2）若。则

，取当二、二分法算法（二分法）输入，区间，精度，最大的迭代次数N

（1）对做到第5步（2）（3）（4）若或，则输出停机

（5）若则（6）输出超过最大迭代次数N的信息，停机。Bisection.m二、二分法注1

二分法的优点是方法和计算都简单，且对函数的性质要求不高，只须连续即可。其缺点是不能求偶数重根。在实用中常用二分法来判别根的存在区间，或求出根的初始近似值，以便使用其它的快速迭代法求根。注2应用中常常是取适当的步长h，对区间[a,b]从左到右逐步扫描，检查小区间的两端函数值符号，从而判断根的存在区间，再用收敛速度快的迭代法，迭代计算求根。步长h选择应适当，过大可能漏掉根，过小将会增加计算的工作量。例1判别方程的实根分布的近似区间，要求区间长度不大于1，并求出最小正根的近似值，精度。如下表可知，根的存在区间为x-2-1012f(x)-131-13解二、二分法kakbkxkf(xk)1010.5-3.75200.50.250.26562530.250.50.375-0.0722740.250.750.31250.0930250.31250.3750.343750.00936960.343750.3750.359375-0.0-317170.343750.3593750.35156250.01124前7次的计算结果为二、二分法解由于，且因此方程在[0，1]上有唯一实根。利用Matlab编写m文件example2.m，并运行，得到结果，

例2用二分法求方程在区间[0，1]上的根。k=13x=0.1823三迭代法三、迭代法设方程可以转化为等价的形式从某个初值出发令得到序列。当连续，且序列收敛时，有有即序列的极限是方程的根。(2.1)构造迭代格式的方法称为迭代法。

称(2.1)为迭代格式，函数为迭代函数。三、迭代法例3

构造不同的迭代格式，求方程在(1,2)内的近似根。上连续，且由零点定理，方程(1,2)内至少存在一根。迭代格式分别为

解设三、迭代法取初值，迭代计算的结果分别为1）迭代4次后2）迭代3次后3）迭代25次后4）迭代9次后5）迭代3次后若采用二分法则有

迭代格式构造的不同，可能会出现发散或无意义的情形，即使是收敛的，收敛的速度也有快慢之分。Matlab编制程序：example3三、迭代法单点迭代法计算第k+1个近似值时仅用到第k个点处的信息。多点迭代法计算时需要用到前面P个点处的信息，一般形式为1.迭代法的收敛性迭代法一般只具有局部的收敛性，即当初始值充分接近于根时，迭代法产生的序列才收敛于根，迭代法的收敛性与初值无关的情况是很少见的。如何确定迭代法的初值使其充分接近于根是相当困难的工作，它依赖于函数和迭代函数的性质。为了使初始近似值充分接近于根，常用二分法将根的存在区间尽量缩小，然后再用收敛速度较快的迭代法迭代计算。三、迭代法则称在[a,b]上满足Lipschitz条件，L称为Lipschitz常数。

定义1

若存在常数L>0，使有

注若连续满足Lipschitz条件连续定理2

对迭代方程，若迭代函数满足1)当时，有,上满足Lipschitz条件且Lipschitz常数L<1，2)

在[a,b]①在(a,b)内存在唯一的根②对，迭代格式均收敛，且则有三、迭代法⑤③④由③常用，作为迭代终止的判别条件；由④迭代收敛速度与L的值有关，当L<<1时收敛较快，当L接近于1时收敛较慢，并可由④的右端来近似估计迭代次数。2.收敛速度收敛速度是用来衡量迭代方法好坏的重要标志，常用收敛的阶来刻划。三、迭代法定义2

记迭代格式的第k

次迭代误差为并假设迭代格式是收敛的，若存在实数使得

则称迭代格式是p阶收敛的，C称为渐近误差常数。当p=1时，称迭代格式为线性收敛；当p=2时，称迭代格式为二阶收敛；当1<p<2时，称迭代格式为超线性收敛。

定理3

对迭代格式，若在根的邻域内连续并且则该迭代格式在根的邻域内是p阶收敛的。三、迭代法例4

考查例3中迭代格式③和④的收敛性。对迭代格式③，其迭代函数为有取

迭代格式③的迭代函数在[1,1.5]上满足定理2的条件故迭代格式③收敛。，解三、迭代法对迭代格式④，其迭代函数

取有故迭代格式④在[1，2]内收敛，且由于故迭代格式④比迭代格式③收敛的速度快.四常用的迭代法四、常用的迭代法1.Newton方法对方程Newton法的基本思想是对函数进行线性化处理，从而构造迭代格式将函数在近似值处进行一阶的Taylor展开,（假设二阶可导）有略去高阶无穷小项有四、常用的迭代法故有迭代格式

有

当时，Newton法是二阶收敛的。Newton法的几何意义是：点处的切线与x轴交点处的横坐标。Newton法仍然是只具有局部的收敛性。在例2中迭代格式⑤就是Newton迭代格式。（证明略）四、常用的迭代法算法（Newton迭代法）输入初值，精度，最大迭代次数N(1)对

，做到第6步(2)计算（3）若，停止计算（4）（7）输出超过最大迭代次数的信息，停机（6）（5）若，则输出停机EquaNewton.m四、常用的迭代法例5设f(x)=x3+x-1，证明：方程f(x)=0在区间(-1，1)内有唯一实根，应用Newton法求此根，(取初始值-0.7)。解由于f(x)在[-1，1]上连续，f(-1)f(1)=(-3)×1<0；又

f'(x)=3x2+1>0，x[-1，1]。因此，结合零点定理及单调性可知，方程f(x)=0在区间(-1，1)内有唯一实根，应用Newton迭代公式，得为使计算结果精确到10-8，我们利用Matlab编写m文件Example5.m并运行，经7次迭代后得到近似解0.68232780383详细结果见表.四、常用的迭代法%Example5eps=1e-8;N=100;x0=-0.7;f=@(x)(x^3+x-1);Df=@(x)(3*x^2+1);Hfun=@EquaNewton[k,x,f_value]=feval(Hfun,f,Df,x0,eps,N)kxkf(xk)0-0.7-2.0430000000010.12712550607-0.8708200320620.957678119180.8360100970130.734827794990.13