北京交通大学2求根课件.docx

《北京交通大学2求根课件.docx》由会员分享，可在线阅读，更多相关《北京交通大学2求根课件.docx（34页珍藏版）》请在三一办公上搜索。

1、北京交通大学2求根课件第2章 非线性方程的求根方法 本章探讨函数方程求根的常用数值方法的构造和原理，主要介绍非线性方程求根方法的有关知识和方法. 重点论述二分法、简单迭代法、牛顿迭代法及其变形的原理、构造、收敛性等内容。 1 2.1 实际案例 如下关于角度a的方程 cosa(1-0.5tana)-0.32=0 1.4来自某种门的气压控制问题，工程师要求出满足如上方程的a的值以设计出一种自动控制装置。 2 2.2问题的描述与基本概念 定义2.1 设f(x)为一元连续函数，称 f(x)=0 为函数方程； 当f(x)不是x的线性函数时，称对应的函数方程为非线性方程。 非线性方程中，当函数f(x)是多

2、项式函数时，称为代数方程，否则称为超越方程。 3 l n次代数方程 anx+an-1xnn-1+a1x+a0=0 在非线性方程中，绝大部分是没有求根公式的，因此寻找求近似根的方法是非常重要!。 l 求根问题的本质 4 根的存在性、根的范围和根的精确化 根的精确化是方程求根问题的核心。 l 数值分析中求根方法分类 两类：区间法,迭代法 方法共同点是构造收敛根的数列xk。 5 定义2.2 设数列xk收敛于x*，若存在正数 p 和C，满足 limkxk+1-x*xk-x*p=C 则称xk的收敛阶为p或方法具有p阶敛速。 l 当p1且C1时称方法超线性收敛。 收敛阶越大，收敛越快，方法越好！ 6 2.

3、3 二分法 二分法也称对分区间法、对分法等，是最简单的求根方法，属于区间法求根类型。 基本思想 利用连续函数零点定理，将含根区间逐次减半缩小，构造点列xk来逼近根x*。 7 1. 构造原理 假设f(x)=0在区间a,b中只有一个根，且满足f(a)f(b)0，则二分法求根数列xk的构造过程为： 记I0=a,b，取I0的中点x0=0.5(a+b)，计算f(x0)； 判别f(x0)的值 若f(x0)=0，则x*=x0，终止； 若f(x0)f(a)0，则x*x0,b，取I1=x0,b; 8 记I1=a1,b1，取I1的中点x1=0.5(a1+b1) x1-x00给定精度后，要-xke成立，取k满足 1

4、(b-a)ln(b-a)-lne-1 ln2这样就可以保证进行k次二分计算得到的 xk 就是满足精度要求的近似根。 式确定的k往往偏大，主要用于理论估计。 12 由二分法的构造，有 bk-ak=2xk-xk-1 故总成立有 x*-xkxk-xk-1 *xx-xe因而当k时就有-xke，此时xk是满足k-1精度的近似根。 式确定的k往往较小，主要用于实际控制。 13 32x-5x-1=0在区间1,2例2.1用二分法求方程内的根，绝对误差e10-2。 32f(x)=2x-5x-1f(x)=6x-5， 解 令，则因为f(1)0，且f(x)在1，2内不变号。可知方程f(x)=0在1，2内有唯一根。 由

5、二分法算法有 I0=1,2，x0=0.5(1+2)=1.5 由f(x0)f(1)0，得 I1=x0,2=1.5,2，x1=0.5(1.5+2)=1.75 由f(x0)f(x1)10-2； I6=1.671875,1.6875，x6=1.679688， x6-x5=0.007813=0.781310-20为给定的精度。出，设非线性方程为f(x)=0， 因为f(x)是实数，为描述其为零的情况，引入充分小的数e10，用f(xk)e1表示f(xk)=0。 此外，借助计算机的存贮特点，将二分法中的数列ak都存在变量a中，bk都存在变量b中，用变量x记录xk，由此得二分法算法 16 二分法算法 输入 a，

6、b，f(x)，e，e1 输出 根x 步骤： x0.5(a+b) 若f(x)e1, 则输出根x，停止 若f(a)f(x)eps, x=(a+b)/2;n=n+1; w=fx; IfAbswe1,Print“n=”,n, “ x=”,x, “ fx=”,w;Break; p=fa*w/N; Ifp0,b=x,a=x; Print“n=”,n, “ x=”,x/N, “ eps=”,b-a/N 说明：本程序用于求非线性方程f(x)=0在区间a,b内的根，这里要求f(x)在区间a,b连续,且f(a)f(b)0。程序执行后，先通过键盘输入函数f(x)和区间左端点a和右端点b及根的精度要求e，程序即可给出

7、每次二分的次数和对应的点列x k，其中最后输出的结果即为所求的根。 程序中变量说明： x：存放初值x 0和二分法中的x k a: 存放含根区间的左端点ak b: 存放含根区间的右端点bk e1:描述f(xk)=0的微小值,这里用|f(xk)|e1表示f(xk)=0 n: 存放二分次数 注：语句Ifp0,b=x,a=x中p的一定要是算出的数值，否则会出现错误。本程序中用“p=fa*w/N”而不用“p=fa*w”就是这个原因。 18 2.4 简单迭代法 基本思想 利用对方程做等价变换根不发生变化的特点，将方程f(x)=0等价变形为x=j(x)，获得迭代计算公式 xk+1=j(xk) 由它算出逼近根

8、x的数列xk。 * 19 1. 构造原理 将方程f(x)=0改写成另一等价形式x=j(x)； 构造迭代公式xk+1=j(xk)； 取定一个初值x0，由迭代公式算出数列x1=j(x0),x2=j(x1),L。 由上述得出xk称为迭代数列，函数j(x)为迭代函数，如上求根方法称为简单迭代法。 20 就迭代格式而言，一般情况下，迭代函数j把点xk变为xk+1=j(xk)后，有xk+1xk，此两点是不同； *jxxx=j(x)但对根，有，变不动它，点形象的称为j(x)的不动点； 称方程x=j(x)为不动点方程。 非线性方程求根问题就是求对应的迭代函数不动点的问题。 21 2.简单迭代法的几何意义 方程

9、x=j(x)的根，在几何上就是直线y=x 与曲线 y=j(x) 交点的横坐标x*,如图2-4所示。 22 23 3.分析 按简单迭代法计算产生的数列xk能* 收敛到根x吗？ xk=x。先假设xk是收敛的，不妨设limk函数j(x)是连续的，有 x=limxk+1=limj(xk)=j(limxk)=j(x) kkk说明迭代数列xk的极限就是所求的根，故用简单迭代法求根是可行的。 24 但： 由方程f(x)=0，可以得到很多的不动点方程，例如方程x5-x-1=0，它的不动点方程可以有 5-4-3x=x-1，x=x+x，x=51+x 是否这些方程的每个迭代格式产生的迭代数列都是收敛的呢？ 25 x

10、x-10+2=0，考虑方程其在x=1附近有一个根。 x+2建)若选择迭代不动点方程x=lg(立迭代格式 xk+1=lg(xk+2) 取x0=1进行迭代计算得 x1=0.477121，x2=0.393947， x13=0.375812，x14=0.375812 0.375812。 26 此数列是收敛的，得近似根 但如果选择不动点方程x=10x-2建立迭代格式 xxk+1=10k-2 也取x0=1进行计算，就有 x1=8，x2=99999998，x3=1099999998-2，显然这个数列肯定不收敛。 27 判别收敛的充分条件。 定理2.1 设迭代函数j(x)满足两个条件 1.当xa,b时，有j(

11、x)a,b； 2.x1,x2a,b，存在常数L1满足 j(x1)-j(x2)Lx1-x2 则有 *j(x)a,bx1.在中有唯一的不动点; 2.迭代公式xk+1=j(xk)对任取x0a,b，产生*的数列xk都收敛于x。 28 证明 存在性 易证迭代函数 j(x)Ca,b。作辅助函数 y(x)=x-j(x) 显然y(x)Ca,b。由条件1知 y(a)y(b)0 由中值定理，至少存在一个xa,b，使y(x)=0，即x=j(x)，这说明j(x)在a,b上有不动点x。 29 唯一性 如果j(x)在a,b上还有一个不动点h，有h=j(h)，利用条件2，有 x-h=j(x)-j(h)Lx-hx-h 矛盾，

12、这就证明了满足定理条件的j(x)在a,b中有唯一的不动点，记为x*。 30 xk的收敛性 由x*是不动点、迭代格式及条件2，有 xk-x*=j(xk-1)-j(x*)Lxk-1-x*L2xk-2-x*LLkx0-x*注意到0L1，在上式中令k，可得Lk0，有 limkxk-x*=0，因而有limkxk=x* 定理得证。 31 例2.3证明迭代格式 xk+1=3-0.5xk,x0=-15 产生的数列是收敛的。 证明 由迭代格式可知迭代函数为 j(x)=3-0.5x 取其定义区间为实数R，显然有xRj(x)R，另外任取x1,x2R有 j(x1)-j(x2)=3-0.5 x1-(3-0.5 x2)=

13、0.5 x1- x20.5x1-x2取L=0.51，则由定理有x0R，迭代数列xk都收*x敛于不动点，故有本题结论成立。 32 定理2.1的条件2： x1,x2a,b，存在常数L1满足 j(x1)-j(x2)Lx1-x2 不易使用。实用中此条件常用 代替。 j(x)L1，xa,b 33 推论2.1 设迭代函数j(x)满足 1. 当xa,b时，有j(x)a,b L1，xa,b 2. j(x)则 j(x)在a,b上有唯一的不动点x*，且对任意初值x0a,b，迭代公式xk+1=j(xk)产生的数列xk都收敛于x*。 34 x较大的范围满足不容易做到，但在较小范围还是较容易做到。 通常称在根的附近取初

14、值x0才能保证收敛的求根方法为局部收敛方法，没有这种取初值限制的方法称为全局收敛方法。 二分法是全局收敛的，简单迭代法一般是局部收敛的。 j(x)L1在 35 局部收敛定理 *x定理2.2 设是迭代函数j(x)的不动*j(x)x点，且在点处连续，则 *j(x)1，迭代xk+1=j(xk)发散 2.若定理2.2可以得到一个更容易使用的判别简单迭代法收敛的充分条件。 36 证明 只给出1的证明。 *j(x)0，使 正实数L1和的某个闭邻域xD时有j(x)L1成立。 注意到，当xD时，由x*=j(x*)及中值定理有 j(x)-x*=j(x)-j(x*)=j(x)x-x*Lx-x*x-x*d 所以xD

15、时，有j(x)D，由推论2.1可知迭代xk+1=j(xk)产生的数列xk对任意x0D都收敛于不动点x，故迭代格式xk+1=j(xk)局部收敛。 * 37 4. 误差估计和收敛速度 定理2.3 设定理2.1的条件成立，则有如下误差估计式 1）Lx-xkxk-xk-11-L* k2）x*-xLk1-Lx1-x038 证明 只证1）。 由迭代公式和定理2.1的条件，有 xk+1-xk=j(xk)-xk =j(x*k)-j(x)+j(x*)-xk =x*-xk+j(xk)-j(x*)x*-x*k-j(xk)-j(x) x*-xx*k-Lk-x=(1-L)x-xk 39 因为0L1，所以有 1x-xkx

16、k+1-xk 1-L*另一方面 xk+1-xk=j(xk)-j(xk-1)Lxk-xk-1代入式，得结论1）。 2.7）40 可以直接求出满足要求的根迭代次数k kln(1-L)ex1-x0/lnL 2实用中一般不管是否L1成立，都用xk-xk-1e来作为终止条件求出满足精度要求的根。 41 32x+2x+10x-20=0在例2.4用简单迭代法求方程x=1附近的根，计算结果准确到4位有效数字。 解 令f(x)=x3+2x2+10x-20 因为f(1)f(2)0，故原方程f(x)=0在1,2内有唯一的根。将原方程改写为 x=20x2+2x+10，得迭代函数 j(x)=20x2+2x+10。 为观

17、察j(x)在1,2内的取值，注意到 j(x)=-20(2x+2)(x2+2x+10)20， x1,2 故j(x)在1,2单调下降。 42 101020由j(1)=13，j(2)=9，有1920j(x)2。 13于是有当x1,2时，j(x)1,2。 此外，易得当x1,2时 20(2x+2)20(22+2)120j(x)=22=L0.510-2 x2=1.295019517 x2-x1=0.2434420210.510-2 M M x10=1.36869397 x10-x9=0.36584210-30，并有尽可能高的收敛阶。 解:由题意有迭代格式为 xaa2k+1=pxk+qx2+r5kxk 它要

18、局部收敛到b，则b就是其不动点，即有关系2b=pb+qaab2+rb5 47 将b=3a代入并整理有: p+q+r=1 此外要想有尽可能高的收敛阶，由定理2.4还应该有f(b)=0,f(b)=0,L 由于有3个参数，此要有三个方程才有可能有唯一解。选取f(b)=0,f(b)=0有 )aa2f(b=p-2qb3-5rb6=0(b)=6qaa2f b4+30rb7=0 48 化简后得另外两个方程 p-2q-5r=0 q+5r=0这样得到关于p，q，r的方程组 求解之，得 p+q+r=1 p-2q-5r=0q+5r=0p=q=519,r=-949 于是有具体迭代格式 5xk5aa2xk+1=+2-5

19、 99x9xk 因为f(b)=10b-20，故由给出的迭代收50 5. 迭代法的加速 1)增量松弛法 如果迭代公式xk+1=j(xk)产生的数列xk收敛的不好，可以考虑将增量 Dxk=xk+1-xk=j(xk)-xk 加在迭代值j(xk)上进行修正，引入带有变化因子C的增量CDxk代替Dxk可以方便增量值的调控，此时经过修正的值为 xk+1=j(xk)+C(j(xk)-xk) 51 它的迭代函数为 y(x)=j(x)+C(j(x)-x) 式中C-1，是待定常数。 要得到收敛更快的迭代函数，当然选择C使y(x*)=0最理想。注意到 y(x*)=j(x*)+C(j(x*)-1)=0 可得 C=j(

20、x*)1-j(x*) 但由于x*未知，C不可计算。 52 *xxxx由k，考虑用k代替，并令wk=j(xk)，得到C的近似关系： Cj(xk)wk=1-j(xk)1-wk将其代入新的不动点方程x=y(x)，可得加速的迭代格式： x=j(xwkk+1k)+1-w(j(xk)-xk)k=1wk 1-wj(xk)-xkk1-wk 53 2) Aitken方法 不要求迭代函数j(x)存在。具体构造过程： 假设求得xk后，在求xk+1前先用迭代格式 xk+1=j(xk) 连续校正2次得两个迭代值： x(1)(2)(1)k+1=j(xk)，xk+1=j(xk+1) 由微分中值定理有 x(1)*k+1-x=

21、j(xk)-j(x)=j(x)(x*k-x) x(2)+1-x*=j(x(1)k+1)-j(x*)=j(h)(x(1)*kk+1-x) 54 设j(x)j(h)L，由这二个方程，有 (1)*xk-xLx-x() +1k(2)(1)*xk-xLx-x+1k+1() 消去L并解出x*，有 x*xk- (2)(1)xk-2x+x+1k+1k(xk+1-xk)2(1)令该式右端为xk+1，得到Aitken迭代格式 xk+1=xk-xk+1=j(xk)，xk+1=j(xk+1) ，xk+1-2xk+1+xk(2)(1)()2(xk-x)+1k1(1)(2)(1) 55 迭代分类 l 单点迭代 xk+1=

22、j(xk) 要一个初值x0就能计算出迭代数列xk； l 多点迭代 xk+1=j(xk,xk-1,xk-l)，l1为整数 要多于1个初值x1,x2,L,xl，才能构造迭代数列xk。 56 2.5 Newton迭代法 基本思想 将函数f(x)做线性化处理，把方程f(x)=0转化为对应的近似方程L(x)=0，再从L(x)=0中构造迭代公式。 跟着Newton大师学技能！ 57 1. 构造原理 先将f(x)在xk处做Taylor展开 f(x)=f(xf(xk)k)+f(xk)(x-xk)+2!(x-xk)2+L 取f(x)展式中关于x-xk的线性部分即 L(x)=f(xk)+f(xk)(x-xk) 代

23、替f(x)，将方程 f(x)=0 替换为近似方程L(x)=0，有 f(xk)+f(xk)(x-xk)=0 58 从近似方程中求出解，得 f(xk)xk+1=xk-f(xk) 此迭代式称为Newton迭代公式，用此公式求方程f(x)=0根的方法称为Newton迭代法。 59 2. 分析 *f(x)f(x)=0f(x)0x定理5 设，且在*N(x)内有二阶连续导数，则Newton的领域迭代格式 xf(xk)k+1=xk-f(xk) 至少是平方收敛的。 60 证明 由条件知f(x)在N(x*)成立Taylor公式： f(x)=f(xk)+f(xk)(x-xk)+xkN(x*)，xk在x与x之间 k1

24、f(xk)(x-xk)2 2!将x=x代入，有 10=f(x)=f(xk)+f(xk)(x-xk)+f(x)(x*-xk)2 2设f(xk)0，用f(xk)同除上式两端，并利用Newton*迭代公式，整理后可得 f(x)xx+1-x=(xk-x*)2 2f(xk)* 61 所以有 xk+1-x*f(x)f(x*)lim=lim=* *2kk2f(x)2f(x)xk-xk证毕。 Newton迭代法是局部收敛的，故初值x0应充分靠近根x才能保证收敛。 实用中可先用二分法做求根预处理，二分若干次后得到较靠近根x的近似根x0，再用此根作为Newton迭代法的初值求根。 * 62 定理6 设f(x)C2

25、a,b，满足下列3个条件 1. f(a)f(b)0，由Newton迭代格式产生的数列xk一定收敛于a,b上的唯一根x。 * 63 例2.8 用Newton迭代法求例2.4中非线性方程在x=1附近的根，计算到xk+1-xk10-6。 解 令 f(x)=x3+2x2+10x-20 考虑区间a,b=0,2，由f(0)f(2)0，f(x)=6x+40 满足定理6的条件，要f(x0)f(x0)0，取x0=1.5，用Newton迭代法计算： 32xk+2xk+10xk-20xk+1=xk-23xk+4xk+10 64 有 x1=1.37362637363 x1-x0=0.12637410-6 x2=1.3

26、6881481962 x2-x1=0.48115510-210-6 x3=1.36880810783 x3-x2=0.67117910-510-6 x4=1.36880810782 x4-x3=0.13039610-1010-6 所以 x*x4=1.36880810782 即为所求。 把此题与例2.4相比可知Newton迭代法收敛速度是很快的。 65 2.6 Newton迭代法的变形与推广 1. Newton迭代法的变形 1) 割线法 为克服Newton迭代法需要求导数f(xk)的不便，用f(xk)的近似值 代替f(xk)的计算，则 f(xk)-f(xk-1)x k-xk-1Newton迭代公

27、式就变为如下 66 割线法迭代公式 xk-xk-1xk+1=xk-f(xk) f(xk)-f(xk-1)这个计算公式是多点迭代公式，它需要两个初值才能产生迭代数列。 可以证明割线法超线性收敛，收敛阶为 1.618。67 2Newton迭代法的推广 把Newton迭代法的思想推广到求解非线性方程组中，可以得到求解非线性方程组的Newton迭代法。 n个变元的非线性方程组的向量形式为 Fr(xr)=r0 这里，f1(x)f1(x1,x2,L,xn) x1Fr(x)=f2(x)=f2(x1,x2,L,xn)rxMM,x=2。 fn(x)fn(x1,x2,L,xn)Mxn式中fk(x1,x2,L,xn)是x1,x2,L,xn的多元函数，且至少有一个不是x1,x2,L,xn的线性函数。 68 rrr*非线性方程组的解是F(x)=0的一组数 rx*=(x1*,x2*,L,xn*)T 得解非线性方程组的Newton迭代公式 r(m+1)r(m)uurr(m)-1urr(m)x=x-F(x)F(x) 作业： 习题二， ，2，5，6，9，12，. 69 114