计算声学第三章非线性方程的数值解法PPT课件

1第三章 非线性方程的数值解法 科学技术研究与工程实践中，经常会遇到求解非线性方程的问题，一般归纳为求解方程其中 是一元非线性实函数一元非线性实函数。根据 是代数多项式还是超越函数（指数函数、对数函数、三角函数等），方程分别称为代数方程代数方程或超越方程超越方程。次代数方程：超越方程：0)(xf)(xf)(xfn00111axaxaxannnn0lncos2xexx2第三章 非线性方程的数值解法 对于代数方程，根的数目与方程的次数相同，不高于4次的代数方程已有求根公式，高于4次的代数方程没有精确的求根公式；超越方程则复杂得多，如果有解，可能是一个或多个，或无穷多个，没有精确的求解公式。因此，需要研究如何采用一定的数值算法求得满足一定精度要求的近似根近似根。l内容提要内容提要：隔根区间的确定、二分法、迭代法、牛顿迭代法、弦截法l重点内容重点内容：迭代法、牛顿迭代法3第三章 非线性方程的数值解法数值方法求方程 根的近似值，要解决三个问题：1、根的存在性存在性：方程有没有根，如果有根，有几个；2、根的隔离隔离：找出有根区间，把有根区间分成较小的子区 间，每个子区间只有一个根（隔根区间）；3、根的精确化精确化：确定了隔根区间后，可以用各种方法将某 一近似根 逐步精确化。按照一定的方法产生一个序列 ，此序列在一定的条件下收敛于方程 的根 。产生序列 的不同方法就构成了不 同的方程求根方法。0)(xfx,10kxxx0)(xf*xkx4第三章 非线性方程的数值解法应用举例：本征声线求解：本征声线求解本征声线本征声线：从声源出发经过一定的传播路径到达接收点的声线，接收点处的声场是所有本征声线能量叠加的结果。折射定律折射定律(Snell)：常数zcccoscos005第三章 非线性方程的数值解法对于给定的海洋环境，每条声线的轨迹由声线的起始掠射角唯一决定。设声源位于 处，接收点位于 处，声线轨迹方程：需要导出声线以掠射角 从声源出发，经过一定水平距离 到达深度 的计算公式，有改变 ，给定精度要求，进行求解。sz,0rrzx,zcczndzznzxzzssss022 ,coscos,sxrsxz,0,rrszxzs605001000150020002500300035004000450050000102030405060708090100水 平 距 离/m深度/m声 线 轨 迹第三章 非线性方程的数值解法71 根的搜索与二分法 根的搜索根的搜索l定义（隔根区间隔根区间）：如果在区间 内只有方程的一个根，则称区间 为隔根区间隔根区间。隔根区间的确定l描图法描图法l逐步搜索法逐步搜索法,ba0)(xf,ba8l介值定理介值定理：定理定理1 1：设函数 在区间 上连续，且 ，则方程 在 上至少有一个根。定理定理2 2：设函数 在区间 上是单调连续函数，且 ，则方程 在 有且仅有一个根。1 根的搜索与二分法 xf xfba,ba,0bfaf 0bfaf 0 xf 0 xfba,ba,91 根的搜索与二分法l描图法：描图法：画出 的简图，由曲线与 轴的交点位置确定出隔根区间。或者将方程等价变形为 ，画出函数 和 的简图，从两条曲线交点的横坐标位置确定隔根区间。例：例：求方程 的隔根区间。解：由图可知，方程仅有一个实根，隔根区间为 。)(xfy x)()(21xgxg)(1xgy)(2xgy 0cos13xx0.1,5.0101 根的搜索与二分法l逐步搜索法：逐步搜索法：首先确定方程 的实根所在区间 再按照选定的步长 （n为正整数），逐点计算 处的函数值 ，当 与异号时，则 即为方程的一个隔根区间。对于 次代数方程其根的绝对值的上下界有如下结论结论：（1）如果 ，则方程的根的绝对值小于 ；（2）如果 ，则方程根的绝对值大 于 。0)(xf,banabh),2,1,0(nkkhaxk)(kxf)(kxf)(1kxf,1kkxxm0)(12211mmmmmaxaxaxaxxfmaaa,max211121,1max1mmaaaa11111 根的搜索与二分法例：例：求方程 的隔根区间。解：解：利用逐步搜索法设方程的根为 ，则 即根的所在区间为 和 。取 计算 ，隔根区间为08.09.12.323xxx2.38.0,9.1,2.3max0.49.1,2.3,1max8.012.4)1(112.02.02.42.42.05.0,8hn)(kxf2.2,7.1,7.1,2.1,2.0,7.0kx)(kxf-4.2-0.7-0.20.20.71.21.72.24.2-137.72-2.440.281.060.910.20-0.310.1426.42121 根的搜索与二分法l二分法二分法基本思想：基本思想：通过计算隔根区间的中点，逐步缩小隔根区间，从而得到方程的近似根序列 。过程：过程：设 为连续函数，方程 的隔根区间为，则函数值 异号。（1）将区间 二分得到中点 ，计算函数值 ；（2）根据计算得到的函数值进行判断，如果 ，则方程的根为 ；否则判断 的符号，如果其与 异号，则隔根区间变为 ；如果其与 异号，则隔根区间变为 ；nx)(xf0)(xf,ba)(),(bfaf,ba2ba 2baf02baf2*bax2baf)(afbba,22,baa)(bf131 根的搜索与二分法（3）把新的隔根区间记为 ，继续按照上述规则对隔根区间 进行二分。满足精度要求则停止。通过不断的二分，就得到一系列隔根区间有 。由于后一区间的长度都是前一区间长度的一半，所以 的长度为当 时，区间 的长度趋于零，即区间最终会收敛于方程 的解 。实际计算中，只要二分的次数足够多，可取最后区间中点 作为方程根的近似值，即,11ba,11ba,11kkbababa),(,0)()(*kkkkbaxbfaf,kkbakkkabab2k,kkba0)(xf*x2kkkbax2*kkkbaxx141 根的搜索与二分法误差：误差：如果事先给定精度要求为 ，则满足时，停止计算。1*22kkkkababxx1*2kkabxx151 根的搜索与二分法例：例：用二分法求方程 在 内的根的近似值，要求绝对误差不超过 。解：解：即 严格单调增加，又 ，所以方程在 上有唯一实根。令 ，得到 ，取 ，即至少二分7次。计算过程如下：010423 xx2,1 210212,1,083)(104)(223xxxxfxxxf)(xf0)2()1(ff2,1 2110212kab64.6k7k161 根的搜索与二分法function f=f3(x)f=x3+4*x*x-10;a0=1;b0=2;k=0;while 1 k=k+1;x=(a0+b0)/2;if f3(x)*f3(a0)0 b0=x;else a0=x;end if(b0-a0)/20.005 break;endendx=(b0+a0)/2;171 根的搜索与二分法kkx)(kxf隔根区间1 11.51.52.3752.3751,1.51,1.52 21.251.25-1.7969-1.79691.25,1.51.25,1.53 31.3751.3750.16210.16211.25,1.3751.25,1.3754 41.31251.3125-0.8484-0.84841.3125,1.3751.3125,1.3755 51.343751.34375-0.3510-0.35101.34375,1.3751.34375,1.3756 61.3593751.359375-0.0964-0.09641.359375,1.3751.359375,1.3757 71.36718751.36718750.03240.03241.359375,1.36718751.359375,1.3671875所以最后得 363.1)1.36718751.359375(21*x181 根的搜索与二分法例：例：用二分法求方程 在 内的根，要求精确到小数点后第三位小数，需要二分多少次？解：解：设 ，由于 ，所以在区间 内方程 有唯一实根。令 ，求得所需对分次数至少是10次。l特点：特点：运算简单，方法可靠，对函数只要求在区间上连续；但收敛速度慢，不能用来求复数根及偶数重根。常用于为其它求根方法提供较好的近似初始值。016 xx2,1 1)(6xxxf)21(0)(,0)2()1(xxfff2,1 0)(xf3110212kab192 迭代法及其迭代收敛的加速方法 l迭代法（逐次逼近）迭代法（逐次逼近）基本思想：基本思想：利用某种递推算式，使某个预知的近似根（初值）逐次精确化，直到得到满足精度要求的近似根。算法：算法：给定方程 ，其中 在有根区间 上连续。设 是方程的一个近似根，将方程 改写为，代入初值 构造迭代序列0)(xf)(xf,ba0 x0)(xf)(xx0 x)()()(11201kkxxxxxx202 迭代法及其迭代收敛的加速方法这种求方程近似根的方法称为迭代法迭代法（或简单迭代法迭代法），称为迭代函数迭代函数。如果由迭代法产生的迭代序列 极限存在，即 ，则称 收敛，否则称 发散。称为迭代函数 的不动点不动点，或是方程 的解。由 转化为 时，迭代函数 不是唯一的，不同，会产生不同的序列 ，从而收敛情况也不一样。)(xkx*limxxkkkxkx*x)(x)(xx0)(xf)(xx)(x)(xkx212 迭代法及其迭代收敛的加速方法l几何意义：几何意义：求方程 的根 ，在几何上就是求直线 与曲线 交点 的横坐标，如图所示。从图中可以看出，当迭代函数迭代函数 的导数导数 在根 处满足不同条件时，迭代过程的收敛情况也有所不同。所以迭代过程的收敛依赖于迭代函数 的构造，为使迭代法有效，必须保证其收敛性。)(xx*xxy)(xy*P)(x)(x*x)(x222 迭代法及其迭代收敛的加速方法1)(0*x0)(1*x232 迭代法及其迭代收敛的加速方法1)(*x1)(*x242 迭代法及其迭代收敛的加速方法例：例：已知方程 在 内有一个根，用两种不同的迭代公式（1）；（2）进行迭代，观察所得序列的收敛性。解：解：计算结果如表所示0210 xx4.0,3.02101kxkx)2lg(1kkxxkxkxk （1）（2）00.30.31-0.00470.36172-1.01080.37323-1.90250.37534-1.98750.3757252 迭代法及其迭代收敛的加速方法x0=0.3;k=0;while 1 k=k+1;xk=10 x0-2;%公式1%xk=log10(x0+2)%公式2 if abs(xk-x0)=0.0005 break;end x0=xk;end262 迭代法及其迭代收敛的加速方法例：例：对于方程 ，试采用如下迭代法求方程的根(1)；(2)；(3)选取初值 。解：计算结果见下表 016 xx161kkxx611kkxx),2,1,0(,1151kxxkk50.10 xkkxkxkx (1)(2)(3)01.501.501.50110.39061.16500.151721.2585e+0061.1374-1.000131.1350-0.499941.1347-0.969751.1347-0.53846-0.95677-0.555127x0=1.5;k=0;while 1 k=k+1;xk=x06-1;%公式1，发散%xk=(x0+1)(1/6);%公式2，收敛%xk=1/(x05-1);%公式3，发散 if abs(xk-x0)=0.0005 break;end x0=xk;end2 迭代法及其迭代收敛的加速方法282 迭代法及其迭代收敛的加速方法迭代法收敛定理迭代法收敛定理：设方程 ，若迭代函数 在有根区间 上满足：（1）当 时，；（2）在 上可导，且有 ，；则有（1）方程 在 上有唯一的根 ；（2）对任意初值 ，迭代公式 产生的数列 收敛于方程的唯一根 ，即 ；（3）误差估计)(xx)(x,ba,bax,)(bax)(x,ba1)(Lx,bax)(xx,ba*x,0bax),2,1,0)(1kxxkkkx*x*limxxkk01*1xxLLxxkk292 迭代法及其迭代收敛的加速方法拉格朗日中值定理拉格朗日中值定理：如果函数 在闭区间 上连续，在开区间 内可导，则至少存在一点 使得,ba)(xf),(ba),(ba)()()(abfafbf302 迭代法及其迭代收敛的加速方法证明：证明：（1）根的存在性存在性：令 ，则 在 上连续，由条件1有由连续函数的介值定理，必存在 使得 ，即为方程的根。根的唯一性唯一性：假设另有 也是方程的根，则有两式相减并应用微分中值定理得)()(xxxg)(xg,ba,0)()(aaag0)()(bbbg,*bax 0)(*xg*x)(,*1*1xxbax)(),(*1*1xxxx*1*1*1)()()(xxxxxx312 迭代法及其迭代收敛的加速方法式中 在 和 之间，所以 ，由条件（2）有上式不成立，所以有 。（2）收敛性收敛性：取 时，有 ，由微分中值定理可知，在 和之间存在 使得：反复应用上述关系可得由条件（2），所以即*1x*x,ba*1*1*1xxxxLxx*1xx,0bax),2,1(,kbaxk)()(1*kkxxxx*x1kx0*2*21*xxLxxLxxLxxkkkk1L0lim0*xxLkk*limxxkk1*1*1*)()()(kkkkxxLxxxxxx322 迭代法及其迭代收敛的加速方法（3）误差估计误差估计：由微分中值定理，在 和 之间存在 使得同样得到同时即因为所以反复应用 ，最后得到*xkxkkkkxxLxxxxxx*1*)()()(1111)()()(kkkkkkkkxxLxxxxxxkkkkkkkkkxxLxxLxxxxxxxxxxxx*1*1*1)1()()(kkkxxLxx1*1111kkkkxxLxx11*111kkkkkxxLLxxLxx11kkkkxxLxx),2,1(101*kxxLLxxkk332 迭代法及其迭代收敛的加速方法l迭代次数估计迭代次数估计：给定精度要求 ，即 ，只要从而迭代次数满足 kxx*011xxLLkLxxLkln)1(ln01342 迭代法及其迭代收敛的加速方法注意：注意：由式 可以看出，当越小时，序列 收敛越快。只要相邻两次迭代的偏差足够小，就可以保证近似解 有足够的精度。所以，常采用条件 来控制迭代次数。11*111kkkkkxxLLxxLxx10 Lkx1kkxxkx1kkxx352 迭代法及其迭代收敛的加速方法例：例：求方程 的最大根，要求精度 。解：解：（1）求隔根区间方程变为 ，做 和的图形，由图可知方程的最大根在区间 内。07lg2)(xxxf410 xxlg7272 xyxylg4,5.3362 迭代法及其迭代收敛的加速方法2）建立迭代公式，判断收敛性。方程变形为 ，迭代公式为 在区间 内可导，并且单调递增。又 ，所以，当 时，由于 ，所以 迭代法收敛。)7(lg21xx)7(lg211kkxx)(),4,5.3(0110ln21)(xxxx4,5.380.3)4(,77.3)5.3(4,5.3x4,5.3)(x4,5.3,0)(xx106.0)5.3()(max45.3xLx372 迭代法及其迭代收敛的加速方法（3）迭代计算过程如下表所示。所以方程的最大根kkx4110kkxx03.513.7720340.27203423.7882880.01625433.7892210.00093343.7892750.000054789.34*xx38x0=3.5;k=0;while 1 k=k+1;xk=(log10(x0)+7)/2;if abs(xk-x0)=0.0001 break;end x0=xk;end2 迭代法及其迭代收敛的加速方法392 迭代法及其迭代收敛的加速方法l定理（局部收敛性定理）：定理（局部收敛性定理）：设 是方程 的根，在 的某一邻域连续，且 ，则必存在 的一个邻域 ，对任意选取的初值 ，迭代公式 产生的数列 收敛于方程的根 ，称迭代法在 的邻域 具有局部收敛性局部收敛性。*x)(xx)(x*x1)(*x*x*x*x|*xxxSSx 0),2,1,0()(1kxxkkkxS40注意：注意：在实际应用中 事先不知道，因此条件 无法验证。但是如果已知根的初始值 在根 的附近，又根据 的连续性，可采用条件来代替 。2 迭代法及其迭代收敛的加速方法*x*x1)(*x0 x)(x1)(x1)(*x412 迭代法及其迭代收敛的加速方法例：例：用迭代法求方程 在隔根区间 内的根，要求精确到小数点后第4位。解：解：(1)构造迭代公式：，迭代公式为(2)判断收敛性：由局部收敛性定理 ，所以迭代法收敛0123 xx5.1,4.1)(132xxx3211kkxx322)1(32)(xxx15.0)(x422 迭代法及其迭代收敛的加速方法(3)迭代计算过程如下表所示：kkx411021kkxx01.511.48124800.018752021.47270570.008542331.46881730.003888441.46704800.001769351.46624300.000805061.46587680.000366271.46571020.000166681.46563450.000075791.46560000.0000345432 迭代法及其迭代收敛的加速方法x0=1.5;k=0;while 1 k=k+1;xk=(x0*x0+1)(1/3);if abs(xk-x0)=0.00005 break;end x0=xk;end442 迭代法及其迭代收敛的加速方法l用迭代法求方程根的近似值的计算步骤计算步骤如下：(1)准备准备：选定初值 ，确定方程 的等价方程 (2)迭代迭代：按迭代公式 计算出(3)判别判别：如果 ，则终止迭代计算，取 作为方程的近似根。否则，转到第(2)步继续迭代计算。0 x0)(xf)(xx)(1kkxx),2,1(kxk1kkxxkx452 迭代法及其迭代收敛的加速方法l迭代收敛的加速方法迭代收敛的加速方法迭代迭代-加速公式加速公式:记 ，则由微分中值定理有其中 在 和 之间。设 在根 附近变化不大，又设 ，由迭代收敛条件 ，有上式整理为 )(1kkxx)()()(*1xxxxxxkkkkx*x)(x*xqx)(1)(x)(*1xxqxxkk)(11*1kkkxxqqxx462 迭代法及其迭代收敛的加速方法上式说明 作为根的近似值时绝对误差大致为如果把该误差作为一种补偿，可以得到更好的近似值记得到迭代-加速公式1kx)(11kkxxqq)(111*kkkxxqqxx)(1111kkkkxxqqxxkkkkkxqqxqxxx111)(111472 迭代法及其迭代收敛的加速方法例例:用迭代-加速公式求 在区间 内的根。解解:，加速-迭代公式为0123 xx5.1,4.1 qx45.0)(kkkkkkkxxxqqxqxxx11911201111111321),2,1,0(kkkxkx411021kkxx01.511.48124801.46590550.034094521.46572331.46557420.000331331.46557261.46557130.0000029482 迭代法及其迭代收敛的加速方法x0=1.5;k=0;while 1 k=k+1;xk1=(x0*x0+1)(1/3);xk=20*xk1/11-9*x0/11;if abs(xk-x0)=0.00005 break;end x0=xk;end493 牛顿（Newton）迭代法l应用范围：应用范围：用于求解高次代数方程、超越方程等非线性方程；可求方程的实根、复根，也可求单根和重根。l基本思想：基本思想：将非线性方程 逐步转化为线性方程来进行求解。牛顿迭代法的最大优点是在方程的单根附近具有较高的收敛速度，是一种将近似根精确化的相当有效的迭代法。0)(xf503 牛顿（Newton）迭代法对于非线性方程 ，设 连续可微，将 在 处泰勒（泰勒（TaylorTaylor）展开）展开如果 ，则可在点 附近取线性部分近似替代 ，得到 的近似方程进行变换，得0)(xf)(xf)(xf0 x 200000)(!2)()()()(xxxfxxxfxfxf0)(0 xf0 x)(xf0)(xf0)()()(000 xxxfxfxf)()(000 xfxfxx513 牛顿（Newton）迭代法由迭代法思想，上式写为迭代公式的一般形式称上式为牛顿（牛顿（NewtonNewton）迭代公式）迭代公式，其迭代函数为,2,1,0 )()(1kxfxfxxkkkk)()()(xfxfxx523 牛顿（Newton）迭代法l几何意义：几何意义：533 牛顿（Newton）迭代法如图所示，假设 是非线性方程 在隔根区间 内的根，在 内可导，且对于 有 。任取初值 ，过曲线 上的点 作切线以其作为曲线 的近似表达式。切线交 轴于 ，则以 作为方程根的第一次近似值。同理，过曲线 上点 做切线*x0)(xf,ba)(xf,ba,bax0)(xf,0bax)(xfy)(,(00 xfx)()(000 xxxfxfy)(xfy x1x)()(0001xfxfxx1x)(xfy)(,(11xfx)()(111xxxfxfy543 牛顿（Newton）迭代法切线交 轴于 ，则 然后以 作为方程根的第二次近似值。反复作切线，第k+1条切线方程为它与 轴的交点横坐标为由此得到方程的近似根数列 。几何意义即依次用切线代替曲线，用线性函数 的零点作为函数零点的近似值，牛顿迭代法又称为切线法切线法。x2x)()(1112xfxfxx2x)()(kkkxxxfxfyx),2,1,0()()(1kxfxfxxkkkkkx)(xf553 牛顿（Newton）迭代法l初始值初始值 的选取的选取：定理（局部收敛性定理局部收敛性定理）：设 是方程 的根，若（1）函数 在 的邻域内具有连续的二阶导数；（2）在 的邻域内 ，则存在 的某个邻域 ，对于任意的初值，由牛顿迭代法产生的数列收敛于根 。0 x*x0)(xf)(xf*x*x0)(xf*x|*xxxSSx 0*x563 牛顿（Newton）迭代法证明证明：迭代函数 的导数为由条件(1)和(2)可知，在 的邻域内可导。又 ，所以在 的某个邻域 内恒有)(x2)()()()(xfxfxfx)(x*x0)(*x*x|*xxxS1)(Lx573 牛顿（Newton）迭代法定理（非局部收敛定理非局部收敛定理）：设 是方程 在隔根区间内的根，如果（1）对于 连续且不变号；（2）选取初始值 ，使 ，则由牛顿迭代公式产生的数列收敛于根 。如果在 上 的符号不容易判断，则利用下式确定初值即如果在 处，满足上式，并且 ，则大多数情况下可以保证牛顿迭代法是收敛的。*x0)(xf,ba)(),(,xfxfbax,0bax 0)()(00 xfxf*x,ba)(),(xfxf)(2)()(0020 xfxfxf 0 x)(xf0)(0 xf583 牛顿（Newton）迭代法l计算步骤：计算步骤：1.选定初值 ，构造迭代公式 ；2.迭代计算，得到 ；3.迭代终止判断，由迭代终止控制条件 控制迭代计算是否终止；4.迭代计算终止，得到方程根的近似值。0 x),2,1,0()()(1kxfxfxxkkkk),2,1(kxk1kkxx593 牛顿（Newton）迭代法例：例：用牛顿迭代法求方程 在隔根区间 内的根，要求精确到小数点后第4位小数。解解:(1)令 ，牛顿迭代公式为(2)判断收敛性所以取 时满足 ，牛顿迭代法收敛。0123 xx5.1,4.1 1)(23xxxfkkkkkkkkxxxxxfxfxx2312)()(223113.0)5.1(,22.0)4.1(ff5.1,4.1,0)23(23)(2xxxxxxf5.1,4.1,026)(xxxf5.10 x0)5.1()5.1(ff603 牛顿（Newton）迭代法(3)计算过程如下表kkx411021kkxx01.511.4666670.03333321.4655720.00109531.4655710.00000161x0=1.5;k=0;while 1 k=k+1;xk=(2*x03-x02+1)/(3*x02-2*x0);if abs(xk-x0)=0.00005 break;end x0=xk;end3 牛顿（Newton）迭代法623 牛顿（Newton）迭代法例：例：用牛顿迭代法求方程 在 附近的根，精确到小数点后第4位。解：解：所以由此 成立，所以可取为初始值。迭代公式为：01)(341xxxf10 xxxxfxxxf3820)(21,341)(39240 823)1(21,44)1(,1)1(fff823)1(2)1(193644)1(22 fff10 x24034113411240)()(xxxxxfxfxxkkkk633 牛顿（Newton）迭代法迭代计算过程如下表所示kkx411021kkxx0-11-0.9772730.0227272-0.9604610.0168123-0.9533910.0070704-0.9525000.0008915-0.9524840.00001664x0=-1;k=0;while 1 k=k+1;xk=(40*x041+2*x03-1)/(41*x040+3*x02);if abs(xk-x0)=0.00005 break;end x0=xk;end3 牛顿（Newton）迭代法653 牛顿（Newton）迭代法例：例：用牛顿迭代法建立计算 近似值的迭代公式。解：解：令 ，则以上问题化为求方程的正根，牛顿迭代公式为继续证明对于任意初值 ，上面迭代公式恒收敛。证明：对于任意 有 即序列 有下界；)0(CCCx 0)(2CxxfkkkkkkxCxxCxxx2122100 x00 x0kxCCxCxxCxxkkkkk212121kx663 牛顿（Newton）迭代法又即 单调下降，所以迭代公式收敛。计算 的近似值。的值在1011之间，取初值 ，迭代公式为1221221/)(2121CCxCxxCxxxkkkkkkkx115115100 x,1,0 ,115211kxxxkkk673 牛顿（Newton）迭代法x0=10;C=115;k=0;while 1 k=k+1;xk=(x0+C/x0)/2 err=abs(xk-x0)if err=0.000005 break;end x0=xk;end683 牛顿（Newton）迭代法迭代计算过程如下（）：947610.7238052115 kkx511021kkxx11107489.4010110.750.75210.723837210.02616279310.723805290.00003192410.7238052969迭代过程的收敛速度定义：定义：如果从任何可取得的初始值出发，由迭代法产生的迭代序列都收敛于方程的根，则称该迭代法是大范围收敛大范围收敛；如果选取的初始值充分接近于方程的根，或者说存在根的某一邻域，使得在其中任意选取初始值，迭代序列都收敛于方程的根，则称该迭代法为局部收敛局部收敛。一种迭代法具有使用价值，不但需要是收敛收敛的，还要求收敛的比较快。所谓迭代过程的收敛速度收敛速度，是指在接近收敛时迭代误差的下降速度。70迭代过程的收敛速度定义：定义：设迭代法 产生的数列 收敛于 的根 ，令误差 ，如果存在某个实数 以及正常数 ，使则称数列 是 阶收敛阶收敛的，相应的迭代法是 阶方法阶方法，常数 称为渐进误差常数渐进误差常数。kx*x*xxekk1pCeepkkk1limkxppkkxx1 xxCC71迭代过程的收敛速度 可以看出，和 为同阶无穷小量，即以 为基本无穷小量时，为 阶无穷小量，阶数 越高，收敛速度越快。收敛速度是误差的收缩率，阶数越高，误差下降的越快。当 时，称数列 线性收敛线性收敛；当 时，称数列 为平方收敛平方收敛（或二阶收敛）；当 时，称数列为超线性收敛超线性收敛。显然，越大，数列收敛的越快，所以迭代法的收敛阶收敛阶是对迭代法收敛速度的一种度量。1kepkeke1keppp10,1Cpkx2pkx1p72迭代过程的收敛速度证明简单迭代法是线性收敛：设 是方程 的根，在 的某一邻域连续，在邻域内有 ，且 ，则简单迭代法线性收敛。证明证明：设迭代过程 收敛于 ，则式中 在 和 之间。令 ，则于是迭代过程一阶收敛（线性收敛）。*x*x*x*x)(xx)(x0)(x1)(*x)(1kkxx)()()(*1*kkkxxxxxxkxk)()(lim*xk)0()(limlim*1*1Lxeexxxxkkkkkk73迭代过程的收敛速度证明牛顿迭代法平方收敛：设 是 在隔根区间 内的根，如果（1）对于 连续且不变号；（2）选取初始值 ，使 ，则牛顿迭代法平方收敛。证明：证明：将 在 处做泰勒展开，有式中 介于 之间。整理上式得*x0)(xf,ba)(),(,xfxfbax,0bax 0)()(00 xfxf)(*xfkx0)(2)()()()(2*kkkkkxxfxxxfxfxfk*,xxk2*)()(2)()()(kkkkkkxxxffxfxfxx 74迭代过程的收敛速度即两边取极限，并利用得所以牛顿迭代法平方收敛。)(2)()()()(2)(2*12*1*kkkkkkkkxffxxxxxxxffxx *lim,limxxxkkkk0)(2)()(2)(limlim)(lim*212*1 xfxfxffeexxxxkkkkkkkkk754 弦截法如果函数 比较复杂，求导可能比较困难，有时甚至导函数不存在。尤其是当 很小时，计算中容易产生很大的误差。这时可将牛顿迭代公式中的 用差商差商来代，即就得到求解非线性方程的弦截法弦截法。)(xf)(xf 11)()()(kkkkkxxxfxfxf)(kxf764 弦截法774 弦截法设方程 的一个隔根区间为 ，如图所示。连结曲线 上的两点 得到弦AB，令 ，则弦AB的方程为则弦AB与 轴交点的横坐标 为以 作为方程根 的一个近似值。0)(xf,ba)(xfy)(,(),(,(bfbBafaAbxax10,)()()()(101011xxxxxfxfxfy)()()()(0101112xxxfxfxfxxx2x2x*x784 弦截法然后过曲线 上的两点 做弦，得到其与 轴交点的横坐标 为于是把 作为方程根 的一个新的近似值。反复做弦，得到迭代公式的一般形式为利用上述公式求方程 根的近似值的方法就叫做弦截法弦截法。)(xfy)(,(),(,(2211xfxxfxx3x)()()()(1212223xxxfxfxfxx3x*x)()()()(111kkkkkkkxxxfxfxfxx0)(xf794 弦截法l几何意义：几何意义：依次用弦来代替曲线，用线性函数的零点作为函数 零点的近似值。l定理（弦截法收敛定理）定理（弦截法收敛定理）：如果 在根 的某个邻域 内有二阶连续导数，且对任意 ，有 ，则当 邻域充分小时，对 邻域内任意的 ，由弦截法迭代公式得到的近似值序列 收敛到方程 的根 。并可证明弦截法是按阶 收敛的。)(xf)(xf*x|*xxxSSx0)(xfSS10,xxnx0)(xf*x618.12/)51(p804 弦截法计算步骤：计算步骤：（1）准备：选定初始近似值 ，并计算 ；（2）迭代计算：依迭代公式 计算得到 ，并计算 ；（3）控制：如果 或 ，则终止迭代。否则 以 分别代替 ，转（2）继续迭代计算。弦截法和牛顿法比较：都是先把 线性化，但方式不同，牛顿法用切线方程来近似代替非线性方程，而弦截法是用弦线来近似代替非线性方程。10,xx)(),(10 xfxf)()()()(0101112xxxfxfxfxx2x)(2xf12)(xf212 xx)(,(),(,(2211xfxxfx)(,(),(,(1100 xfxxfx)(xf814 弦截法例：例：用弦截法求方程 在区间 内根的近似值。精确到小数点后第4位。解：解：令 ，取 ，弦截法迭代公式为042 xex 1,5.04)(2xexfx1,5.010 xx)(4 )()()()(112221111kkkxkxkxkkkkkkkkxxxexexexxxxfxfxfxxkkk824 弦截法迭代计算过程如下表所示：kkx411021kkxx00.51120.5755900.42441030.5995400.02395040.6106930.01115350.6103580.00033560.6103620.000003834 弦截法x0=0.5;x1=1;k=0;while 1 k=k+1;xk=x1-(exp(2*x1)+x1-4)*(x1-x0)/(exp(2*x1)+x1-exp(2*x0)-x0);if abs(xk-x0)=0.00005 break;end x0=x1;x1=xk;end84课后题1、二分法求方程 在区间 内的根，要求误差不超过 。2、已知方程 在区间 内有一根，试问用二分法求根，使其具有5位有效数字至少应二分多少次？3、判断下列方程由几个根，求出隔根区间，并写出收敛的迭代公式。（1）（2）5、用迭代法求的 正根，要求准确到小数点后第5位。0134 xx4.0,3.021021043 xx2,104sincosxxx042xx02.05 xx85课后题4、方程 在1.5附近有根，把方程写成4种不同的等价形式，并建立相应的迭代公式：判断每种迭代公式产生的数列在1.5附近的收敛性，并用（1）的迭代公式求方程的根，要求误差不超过 。0123 xx 321231,11nnxxxx 21211,112nnxxxx 11,11312nnxxxx 1,143132xxxxn3102186课后题6、用迭代法求方程 的根，要求准确到小数点后第4位。7、用迭代-加速公式求方程 在 附近的根，要求准确到小数点后第4位。9、应用牛顿法于方程 和 ，分别导出求 的迭代公式，并求 10、用牛顿法求方程 在 附近的根，要求准确到小数点后第3位。0210 xexxex5.0 x0)(axxfn01)(nxaxfna 21limknknkxaxa0133 xx20 x87课后题11、证明计算 的牛顿迭代公式为取 ，计算 ，要求 。12、用弦截法求 的根，取 ，计算到 为止。3C21231nnnxCxx10 x33611021nnxx0sin1xx1,010 xx21021sin1xx881、解解：令 ，则所以 单调增；所以 在区间 内单调减。又 ，所以方程有唯一实根。有课后题 134xxxf,4.0,3.0,0122 xxxf xf,0892.23.0 f,0744.24.0 f xf4.0,3.01081.03.0f1744.04.0f432.3102123.04.0102122121kkabkkkkxkxf隔根区间10.35-0.0350.3,0.3520.3250.0360.325,0.3530.33750.0004750.3375,0.3540.34375-0.0170.3375,0.34375892、解解：根的区间为 ，近似值具有5位有效数字，则精确到小数点后4为小数，即取 。4、解解：（1），所以迭代公式收敛。课后题2,129.131021212102124141kabkk14k3/223/12132)(,)1()(xxxxx14558.0)5.1(90（2），收敛（3）（4）利用公式（1）计算方程的根，列表如下 课后题15926.0)5.1(,2)(,1)(32xxxx14142.1)5.1(,)1(21)(,)1()(2/32/1xxxx119.2)5.1(,)1(23)(,)1()(2/1322/13xxxxxkkx311021kkxx01.511.4812480.01875261.4658770.000366915、解解：方程变形为 ，分别画出 和的图形，可知交点在 的范围；取 ，则，可知交点在 的范围，所以隔根区间可取为 。令 ，从而 单调减；单调增；，满足条件1；，满足条件2，所以迭代公式收敛。课后题2.05 xx51xy 2.02 xy1x1.1x3.1,6105.121yy1.1x1.1,1512.0 xx 512.0 xx 59542.0254,2.051 xxxx xx,0 xx,0 054.11.1,037.11 1173.0192迭代公式为：计算过程如下：课后题5112.0kkxxkkx511021kkxx5100099.351005.571048.80111.0371370.03713721.0434790.00634031.0445460.00106841.0447260.00017951.04475661.0447671.04476936、解解：（1）求隔根区间方程变形为 ，做 和 的图形。由图可知，方程的根在区间 内。（2）建立迭代公式，判断其收敛性将方程等价变形为 ，迭代函数 ，迭代公式为 。课后题xex102xey xy1022.0,0 xex210110512101)(xxeexkxkex2101194因为 ，当 时，所以 单调递减；又 ，所以 ；，所以 ；由定理可知，迭代公式收敛。（3）计算：取 ，列表计算课后题10)(,10)(xxexex 2.0,0 x0)(,0)(xx)(),(xx0779.0)2.0(,1.0)0(2.0,0)(x1.0)0(1221.0)2.0(1)(x00 xkkx411021kkxx0010.10.120.0894830.01051750.0905260.000013957、解解：取 ，迭代-加速公式为：计算过程如下：课后题 ,xxexex,6065.05.05.0e6.0qkkx411021kkxx510124.100.510.566580.0665820.567130.000550230.56714kkkxkxqqxqxexk111111969、证明证明：（1）对于方程 ，牛顿迭代公式为所以 课后题0)(axxfn 1nnxxf,2,1,0,11knxaxxxfxfxxnknkkkkknknkknkkknnkkknnkkknnknknkknknkanxxanxannnxaxannnnxaxnnanxanxaxxaxaxa2121lim21lim211lim2111limlimlim1212197（2）对于方程 ，牛顿迭代公式为所以课后题01)(nxaxf 1nnxaxf,2,1,0,1111knxanxxnxaaxxxfxfxxknkknknkkkkkknnknkknkkknnkkknknkknkknknkanaaanxxanxnannxanxannxanxanxxaxaxa212121lim21lim2111limlimlim121219810、解解：令 ，牛顿迭代公式为 牛顿迭代公式为满足局部收敛性定理，计算过程如下表所示课后题13)(3xxxf33)(2xxfxxf6)(3313)()(231kkkkkkkkxxxxxfxfxxkkx311021kkxx0211.8888890.11111121.8794520.00943731.8793850.0000679911、证明证明：由 ，牛顿迭代公式为取 ，计算过程如下：课后题CxCx33 233,xxfCxxf2233231231333)()(nnnnnnnnnnnnxCxxCxxxCxxxfxfxx10 xnnx611021nnxx4106231.57101929.20111.6666670.666666721.4711110.195555631.4428120.028299041.44225051.442250100课后题12、解解：令 ，满足收敛条件，取 ，弦截法迭代公式为计算过程如下表所示 xxxfsin1)(xxfcos11,010 xx)(sinsinsin1 )()()()(111111kkkkkkkkkkkkkkkkxxxxxxxxxxxxfxfxfxxkkx21021sin1kkxx001120.5430440.05978930.5080930.00539540.5109860.000023101第三章 非线性方程的数值解法l主要内容：主要内容：1.确定隔根区间；2.二分法；3.简单迭代法；4.迭代收敛的加速方法；5.牛顿迭代法；6.弦截法；7.迭代法的收敛阶。102第三章 非线性方程的数值解法l二分法：二分法：kkkabab22*kkkbaxx1*22kkkkababxx1*2kkabxx103迭代法收敛定理迭代法收敛定理：设方程 ，若迭代函数 在有根区间 上满足：（1）当 时，；（2）在 上可导，且有 ，；则有（1）方程 在 上有唯一的根 ；（2）对任意初值 ，迭代公式 产生的数列 收敛于方程的唯一根 ，即 ；（3）误差估计)(xx)(x,ba,bax,)(bax)(x,ba1)(Lx,bax)(xx,ba*x,0bax),2,1,0)(1kxxkkkx*x*limxxkk01*1xxLLxxkk第三章 非线性方程的数值解法104第三章 非线性方程的数值解法l定理（局部收敛性定理）：定理（局部收敛性定理）：设 是方程 的根，在 的某一邻域连续，且 ，则必存在 的一个邻域 ，对任意选取的初值 ，迭代公式 产生的数列 收敛于方程的根 ，称迭代法在 的邻域 具有局部收敛性局部收敛性。*x)(xx)(x*x1)(*x*x*x*x|*xxxSSx 0),2,1,0()(1kxxkkkxS105第三章 非线性方程的数值解法l迭代迭代-加速公式加速公式：l牛顿迭代法牛顿迭代法kkkkkxqqxqxxx111)(111,2,1,0 )()(1kxfxfxxkkkk106第三章 非线性方程的数值解法l初始值初始值 的选取的选取：定理（局部收敛性定理局部收敛性定理）：设 是方程 的根，若（1）函数 在 的邻域内具有连续的二阶导数；（2）在 的邻域内 ，则存在 的某个邻域 ，对于任意的初值，由牛顿迭代法产生的数列收敛于根 。0 x*x0)(xf)(xf*x*x0)(xf*x|*xxxSSx 0*x107第三章 非线性方程的数值解法定理（非局部收敛定理非局部收敛定理）：设 是方程 在隔根区间内的根，如果（1）对于 连续且不变号；（2）选取初始值 ，使 ，则由牛顿迭代公式产生的数列收敛于根 。如果在 上 的符号不容易判断，则利用下式确定初值即如果在 处，满足上式，并且 ，则大多数情况下可以保证牛顿迭代法是收敛的。*x0)(xf,ba)(),(,xfxfbax,0bax 0)()(00 xfxf*x,ba)(),(xfxf)(2)()(0020 xfxfxf 0 x)(xf0)(0 xf108第三章 非线性方程的数值解法二分法：二分法：由公式有取 。即采用二分法求解，得到满足精度要求的根需要二分13次。1*2kkabxx29.12102125.0141kk13k109第三章 非线性方程的数值解法简单迭代法：简单迭代法：方程 变形为而 即迭代函数单调减，又 ；所以 单调减，所以所以在区间 上迭代法收敛，取初始值 ；042 xex)4ln(21)(),4ln(21xxxx 1,5.0,0)4(21)(xxx55.0)1(,63.0)5.0(1,5.0,0)4(21)(2 xxx)(x17.0)1(,14.0)5.0(1)(x 1,5.05.00 x110第三章 非线性方程的数值解法迭代计算过程如下表所示：kkx411021kkxx00.510.6263810.12638120.6079930.01838830.6107110.00271840.6103100.00040150.6103700.00006060.6103610.000009111第三章 非线性方程的数值解法迭代迭代-加速公式加速公式：取 ，公式为取初始值 ，)4ln(21)(),4ln(21xxxx17.0)1(,14.0)5.0(2.0q),2,1,0(,111)4ln(21)(111kxqqxqxxxxkkkkk5.00 x112第三章 非线性方程的数值解法迭代计算过程如下表所示：kkx411021kkxx00.510.6053180.10531820.6101410.00482330.6103520.00021140.6103610.000009113第三章 非线性方程的数值解法牛顿迭代法：牛顿迭代法：当 时，不变号；又 ，所以取 ；迭代公式为4)(2xexfxxxexfexf224)(,12)(1,5.0 x)(),(xfxf 39.4)1(,78.1)5.0(ff56.29)1(,87.10)5.0(ff0)1()1(ff10 x124)12()()(221kkxxkkkkkeexxfxfxx114第三章 非线性方程的数值解法迭代计算过程如下表所示：kkx411021kkxx0110.7218260.27817420.6206930.10113430.6104540.01023840.6103620.00009350.6103620.000000007115总结：总结：1、对非线性方程 求根，首选要对 的性态及根的近似位置有一个大致了解，使用较小的有根区间把方程的根分离出来；2、简单迭代法是一种逐次逼近的方法，需要判断收敛性，了解收敛速度，可以采用加速公式；3、牛顿迭代法是最常用的一种迭代方法，具有二阶收敛速度，但是对初值的选取比较苛刻，需要靠近方程的根，否则可能不收敛；4、弦截法是牛顿迭代法的一种修改，虽然收敛速度较牛顿法慢，但不需要计算导数，使用更加方便。同样要求初始值的选取比较靠近方程的根。第三章 非线性方程的数值解法 0 xf xf