科学计算4非线性方程

计算机基础教育系第4章非线性方程的数值解法第2章非线性方程的数值解法求方程f(x)=0的实根本章恒设f(x)连续主要内容何谓数值解法根的存在性——介值定理根的存在范围——根的隔离根的精确化方法重点算法：对分法、迭代法和牛顿法Step1Step2非线性方程的求解过程1、判断是否有根，确定根的存在范围n次的代数方程最多有n个根，可能有一对共轭复根2、根的隔离，求隔根区间试值法、作图法、扫描法3、根的精确化对分法、迭代法、牛顿法、弦割法4.2根的隔离-试值法根据函数的性质，进行一些试算。例2.1求方程的隔根区间。，其定义域为其导函数为所以当时，，函数单调上升；当时，，函数单调下降；当时，解设，函数单调上升。试值法于是在每个区间上至多只有一个根。取几个特殊的点计算函数值，f(-4)=-40，f(-3)=1，f(-1)=5，f(0)=-8，f(2)=-4，f(3)=37

所以，隔根区间可取为(-4,-3)、(-1,0)和(2,3)。由于f(x)为三次多项式，至多有3个实根。因此方程f(x)=0所有的隔根区间为(-4,-3)、(-1,0)和(2,3)。的函数曲线f(x)=0所有的隔根区间为(-4,-3)、(-1,0)和(2,3)2.2根的隔离-作图法例2.2求方程的隔根区间。

解，，当x<0时，；当x>0时，，画出的草图如图2-1，从图中可大致确定隔根区间为(-2,-1)、(-1,1)和(1,2)。y=x3-3x-1的曲线图4.2根的隔离——扫描法扫描法就是将有根区间等分为若干个子区间，然后逐个小区间检验是不是隔根区间，检验的办法就是判断区间端点的函数值是否异号。连续函数的介值定理：扫描法ab令x=a,取步长h，检验区间[x,x+h]上是否有根x+hx[x,x+h]为一隔根区间，继续看下一个区间是否有根x+2hxx+h直到x>b为止扫描法的算法输入有根区间的端点a,b及子区间长度h；

(3)若，则；输出隔根区间(4)(5)若x<b-h/2，则返回(3)；否则结束。代数方程的实根的上、下界对于代数方程设，则其实根的上、下界分别为和由此即可确定其有根区间[a,b]。4.3对分法已知[a,b]为一个隔根区间，即有且仅有一个跟，且f(a)*f(b)<0abccab什么时候停止？或x*每次缩小一倍的区间，收敛速度为1/2，较慢，且只能求一个根，使用条件限制较大

2xx*不能保证x

的精度对分法的算法

(1)输入隔根区间的端点a,b及预先给定的精度要求eps；

(2)(a+b)/2=>c；

(3)若f(c)=0，则输出c，结束；否则若，则否则(4)若b-a<eps，则输出根的近似值c，结束；否则转向(2)继续。2.4迭代法f(x)=x3-x-1，将x3-x-1=0改写为：1.x=x3-1，

x=x3-1

φ

(x)=x3-12.x3=x+1x=(x+1)1/3φ

(x)=

(x+1)1/33.x(x2-1)=1x=1/(x2-1)

φ

(x)=1/(x2-1)

4.x(x2-1)=1x=(1+1/x)1/2φ(x)=(1+1/x)1/2………第3和第4种改法不可取，因为函数φ(x)不再连续。f(x)=0x=φ(x)等价变换取x0带入x1=

φ(x0)

x2=

φ(x1)

x3=

φ(x2)

……xk=

φ(xk-1)

从一个初值x0

出发，计算x1

=φ(x0),x2

=φ(x1),…,xk+1

=φ(xk),…若收敛，即存在x*使得

且φ

连续，则由可知x*=φ(x*)，即x*是φ

的不动点，也就是f

的根。2.4迭代法f(x)=0x=φ(x)等价变换f(x)的根φ(x)的不动点迭代法举例(1)将方程改写成等价形式则迭代公式为取初始近似值为x0=1.5，迭代结果见下表。(k=0,1,2,…)k1234xk2.37512.39651904.00286902441984由表可见，迭代是发散的。例2.3求方程在x0=1.5附近的根的近似值，精度要求为10-4。迭代法举例例2.3求方程在x0=1.5附近的根的近似值，精度要求为10-4。解：(2)可将方程改写成等价形式于是有迭代公式(k=0,1,2,…)将初值x0=1.5代入，可得迭代序列x1,x2,…，例2.3k123456xk1.3572091.3308611.3258841.3249391.3247601.324726可见迭代法(2.4)是收敛的，就是满足精度要求的一个近似根。取初值x0=1.5迭代法的收敛性什么因素影响收敛？Φ(x)不同两种方法的区别？迭代收敛定理对于同一个方程，不同的做法收敛性是不一样的，那么，收敛还是发散受什么条件的影响？两种做法主要的区别在什么地方？Φ(x)满足什么条件会收敛？

叙述证明思考关于不动点原理取一个浅盒和一张纸，纸恰好盖住盒内的底面。可想而知此时纸上的每个点与正在它下面的盒底上的那些点配成对。把这张纸拿起来，随机地揉成一个小球，再把小球扔进盒里。拓扑学家已经证明，不管小球是怎样揉成的，也不管它落在盒底的什么地方，在揉成小球的纸上至少有一个这样的点，它恰好处在它盒底原来配对点的正上方。迭代收敛定理

定理2.1

设迭代函数满足时，(2)存在正数L<1，对任意，均有则在[a,b]内存在唯一根，并且对任意初始值，迭代法(k=0,1,2,…)①②(1)当收敛于，且（2.6）（2.7）定理内容已知条件-迭代函数Φ(x)有界（有界性）迭代函数的导数有界，小于1（压缩性）结论迭代收敛迭代序列的极限就是方程的根两个不等式的意义误差事后估计的依据收敛速度和L的关系123定理分析

证：先证根的存在性，由条件(1)知，在区间[a,b]上有

当F(a)=0或F(b)=0时，a或b就是方程的根，否则有因连续，所以F(x)也连续，由连续函数性质可知，存在，使，即，于是是方程的根。作辅助函数迭代收敛定理的证明可知，F(x)在区间[a,b]上严格单调上升，所以F(x)在此区间上至多有一个根，根的唯一性得证。

再证根的唯一性。最后证明迭代序列的极限就是方程的根。由根据微分中值定理，必存在ξ介于xk与α之间，及介于xk与xk-1之间，使得由条件(2)知(2.8)于是整理可得此即(1)式。将上式代入(2.6)式后，即得此即(2.7)式。再反复利用(2.8)式的第2式，可得由可知必有即故迭代法收敛于方程的根得证。1、等价形式Φ(x)2、初值选取x0定理的应用满足时，(2)存在正数L<1，对任意，均有(1)当构造满足定理条件的等价形式一般难于做到：局部收敛定理迭代过程往往就在根的附近进行，只要假定在附近连续，且满足，则根据连续函数的性质，一定存在的某邻域S：，使得在S上满足定理2.1的条件，故在S中任取初始值x0，迭代公式必将收敛于方程的根这种收敛称为局部收敛。迭代法的算法(1)输入初始近似值x0，精度要求eps，控制最大迭代次数M；(3)当k<M且>eps时做循环，，(4)如果eps，则输出x1；否则输出迭代失败信息。(2)xyy=xx*y=g(x)x0p0x1p1

xyy=xx*y=g(x)x0p0x1p1

迭代法的几何意义迭代法的加速（选学）如何加快迭代收敛的速度？根据不等式②知L越小，收敛速度越快加快收敛速度的办法就是设法让L变小迭代法的加速1松弛法在x=φ(x)的两端同时加上λx，得变形为：相当于根据迭代收敛定理，导数要尽可能地小，所以取迭代法的加速这样，迭代公式变为：令则此即松弛法，不收敛的迭代函数，经加速后一般也能获得收敛。迭代法的加速2埃特金法（Altken）松弛法中计算导数不方便，用差商代替导数，用

代替得得迭代公式埃特金公式有时可能使一个本来不收敛的迭代格式获得收敛。4.5牛顿法“以直代曲”的思想，将f(x)在初值处作Taylor展开取线性部分作为f(x)的近似，有：若，则有记为类似，我们可以得到xyx*x0可以得到迭代序列Newton迭代的等价方程为：所以若f(x)在a处为单根，则所以，根据局部收敛定理，迭代格式收敛2.5牛顿法收敛速度

定义2.1设由迭代公式产生的迭代序列(k=0,1,2,…)收敛于方程的根，记

，若存在实数及非零常数c，使得

则称迭代过程是p阶收敛的。当p=1时，称为线性收敛；当p>1时，称为超线性收敛；当p=2时，称为平方收敛。显然，p越大收敛速度越快。简单迭代的收敛速度

由微分中值定理可知，必存在一点介于xk与之间，使得于是由此可知，简单迭代法至少是线性收敛的。函数在a处作Taylor展开即牛顿迭代收敛速度快，格式简单，应用广泛牛顿法的收敛速度x*x0

x0

x0注：牛顿法初值选择的规则：f"(x0)f(x0)>0牛顿法初值的选取规则牛顿法举例例2.4用牛顿法求

解将求转化为求方程则相应的牛顿迭代公式为(k=0,1,2,…)(2.12)可选取任意大于的数，比如2作为根的初始近似值

的根可选取任意大于的数，比如2作为根的初始近似值

的近似值，误差要求为10-54.6弦割法将Newton迭代中的导数，用差商代替，有格式是2步格式。收敛速度比Newton迭代慢x0x1切线

割线

非线性方程数值解法经典算法：对分法迭代法牛顿法弦割法MATLAB函