方程求根的迭代法

第四章方程求根的迭代法非线性方程的解法对分区间法简单迭代法312334Newton法与弦截法迭代过程加速对分区间法第一节对分区间法一般理论二分区间法的理论与分析引言1230()fx本章主要讨论单变量非线性方程的求根问题本章研究对象引言方程是在科学研究中不可缺少的工具，方程求解是科学计算中一个重要的研究对象几百年前就已经找到了代数方程中二次至五次方程的求解公式但是,对于更高次数的代数方程目前仍无有效的精确解法对于无规律的非代数方程的求解也无精确解法因此,研究非线性方程的数值解法成为必然.0)(,0)()()()(,)(.)(1)2(1)1(:.0)(),()()(*)(*)1(********xfxfxfxfxgmxfxmxfxmxmxmxgmxgxxxfmmm充分光滑，则且重零点的是若重零点的为重根，或为称当为单根，时，称当则为正整数，且其中若个根有次方程在复数域有且只nn的零点称为函数则若)(,0*)(*xfxxf一般提法与结论一般提法与结论有且仅有一个根。，则在上连续且单调，在设],[0)()(],[)(babfafbaxf.,2202,202(1)1111aababbbbaabafbaxbaf反之，令，否则：若则根为若],,[)(1],[)2(2211baba的计算，并产生区间重复对二、区间二分法可用对分法：根存在，但未必好求，0)(,0)(bfaf不妨设，考察有根区间],[ba...,,...,,,2211kkbabababa可得出一系列有根区间如此反复二分下去，即.,*该点显然就是所求的根于一点即这些区间最终必收敛xab21babaa1211bax211221122,2ababababab区间二分法，的长度其中时当02/,kkkkkkababbakxx*则有,22*1kkkkababxx由于ab21babaa1211bax区间二分法充分大），只要二分足够多次（即k.为预定的精度这里对分区间次数的估计：122*nnnnababxx由不难得出：区间二分法12lnln)ln(abn.2,5.1101)(3位要求准确到小数点后第一个实根内的，在区间求方程xxxf例1解（二分法）0)(,0)(,5.1,0.1bfafba，将区间二等分，取中点25.10x,5.1,25.1,0)(1010bbxaxf令],[11ba得新的有根区间如此二分下去即可。现估计二分次数64.5005.0*nxxn所以二分6次可达到要求。区间二分法例题优点：区间二分法分析区间二分法的分析对函数要求低，计算简单;缺点：收敛慢且对有偶数重根的情况不适合。简单迭代法第二节简单迭代法迭代法的几何意义迭代法的收敛定理基本概念迭代法的局部收敛性12345迭代法的收敛速度迭代法是一种逐次逼近法，指使用迭代公式反复校正根的近似值，使之逐步精确化，直至得出满足精度要求的结果迭代法的求解过程1.提供根的猜测值—迭代初值2.将迭代初值逐步加工成满足精度要求的根基本思想构造一个同解方程，以求得近似根。即由方程f(x)=0变换为其等价形式x=(x),(x)称为迭代函数（设其为连续函数）一、迭代法的设计思想)(1kkxx)()lim()(limlim*1*xxxxxkkkkkk当给定初值x0后,由迭代格式可求得数列{xk}。迭代值xk有极限，则称迭代收敛。如果{xk}收敛于x*，则它就是原方程的根。因为：可作为方程根的近似值充分大时，故kxk基本概念然后建立迭代格式设计思想将方程的求根问题归结为计算一组显式公式，迭代过程实质上是一个逐步显式化的过程)(1kkxx(1)不动点迭代法：).(xx反之亦然，则满足若要求);(,0)(****xxxfx为函数的一个不动点称*x的零点等价于求不动点求)(xf:0)(改写为将方程xf按上述方法构造迭代格式来求解方程的方法称为简单迭代法或逐次迭代法。基本概念称为迭代函数)(x)1,0()(1kxxkk按下列公式反复迭代基本概念*limxxkk则称迭代方程收敛，:}{kx若相应的序列的不动为且)()(**xxx.)(1为不动点迭代法点，称kkxx)()(xxxf因为：的解的解又xyxyxx)()(的解的解所以：)(0)(xxxf迭代法的几何意义（两条线的交点）几何意义yy=xy=(x)0x1x3x5ξx4x2x0xyy=xy=(x)0x3x1ξx0x2x4x迭代法的几何意义设方程改写成下列形式31xx据此建立迭代公式).,2,1,0(131kxxkk求方程01)(3xxxf.5.1*0xx附近的根在例2解（迭代法）简单迭代法例题3311k+1kxxxx迭代公式：31313213321015151113309113259..1.3572..kkxxxxxxxx(1)利用迭代公式取，则3131032133210151112396511904002.2.375..kkxxxxxxxxx(2)利用迭代公式取，则迭代函数满足什么条件时，迭代格式收敛为使迭代有效，必须保证迭代得到的序列是收敛的，如果不收敛则毫无价值二、压缩映像原理()xkxd对于线性迭代函数，设则有保证迭代收敛的充分必要条件是1()xk1*()()()()()kkkxxxxxxxxx对于一般函数，设为的根，则由微分中值定理，有001[,),.[,]()kkkLstxabxLxxeLek若有成立，令e=则有010,,nLke则当时有即迭代收敛定理1压缩映象原理()[,]xab设在上具有连续一阶导数，并且满足下列条件：1201.[,]().[,]xabaxbLxab。对任意有存在常数，使对成立Lx|)(|110111**kkkkkxxxxLLxxxxL10()[,]()*,.kkxxxabxxx则迭代过程对于任意初值均收敛于方程的唯一根且有下列估计式简单迭代法收敛条件证明()(),()[,]fxxxfxab设则在上连续可导,00()()()()faaafbbb由条件(1)0()[,]fxab由根的存在定理，方程在上至少有一个根1100*|()|()()()[,],()[,]()[,]xLfxxfxabfxabxxabx又则在上单调递增在上仅有一个根所以方程在内有唯一解111112***.(),()()()()()()()()okkkkkkkkkkkxxxxxxxxxxxxxx对于迭代法由微分中值定理|()|xL由于压缩映像原理11111****()()()kkkkkkkkkkxxxxxxxxxxLxxxx111*kkkxxxxL211210111*kkkkkkLLxxxxxxLLLxxL11kkkkxxLxx又压缩映像原理0110**,lim(),()kkkkLxxxxxx由于因此对任意初值迭代法均收敛于压缩映像原理说明1.条件1°说明不动点的存在性2.只要相邻两次的迭代值的偏差足够的小，即可保证迭代值xk+1足够准确，用|xk+1-xk|控制迭代过程是否结束3.L越小，收敛越快迭代法的优点逻辑结构简单4.[a,b]较大时，一般不满足条件，一般在根的附近使用迭代法简单迭代法实现步骤0101011213.,,..while(kN)()()xNkxxifxxx输入置初值迭代:输出011else()kkxxendifkN输出迭代失败的标志3/2131)1(31)(1)(xxxx，解：令,]21[3)(1)(2232中，在区间时，而当xxxx.所以迭代法发散求方程01)(3xxxf.5.1*0xx附近的根在例3压缩影响原理应用的例题,1)41(31|)(|]21[3/11x中，，在区间,23)(21313x又因.所以迭代法收敛1|)(|2x015.,x取迭代初值根据迭代公式，有迭代结果kxkkxk01.551.3247611.3572161.3247321.3308671.3247231.3258881.3247241.32494在实际迭代时，通常在根的邻近考察三、迭代过程的局部收敛性0**:xxx如果存在邻域,使得迭代过程对于任意初值x均收敛，称一种迭代过程在根邻近收敛。这种在根的邻近所具有的收敛性称为局部收敛性的某个邻域，且在有根设方程**)(xxxx定理2*()Sxxxx内有一阶连续导数，且成立11*()().kkxLxxx，则迭代格式在邻近具有局部收敛性证明:011**k+1():()()()()()()()kxxxxLxxxxxxxLxxxxxxx由于，存在充分小的邻域使得成立根据微分中值定理当时，，因此有由压缩映射原理知，对于任意的均收敛50510..,xxexx例4用迭代法求方程在附近的根要求精度0505050612.k+1,(),().()(.).kxxxxexexxexe解：迭代函数在附近有由定理知，迭代过程是收敛的KxkKxkkxk00.560.564863120.56706710.60653170.568438130.56727720.54523980.566409140.56711930.57970390.567560150.56715740.560065100.566907160.56713550.571172110.567186170.567148迭代18次满足精度四、收敛速度10*,()kkpkexxkccek在接近收敛时，迭代误差的下降速度：即迭代过程e当时，有常数，则称迭代过p定义程是：阶收敛的12,,pp称为线性收敛，称为平方收敛yp越大迭代法的收敛速度越快，但在实际使用时p很难直接确定，可使用Talor展式确定其收敛阶1111()()()()()()()()()()()()()!!kkppppxxTaylorxxxxxpp如果在根处充分光滑，则可对在处进行展开,有1100()()()()()(),()()()()!ppppkkxxpk+1如果但是，则x-11()()()()!!ppkkppkkxeppxe即p阶收敛定理31200()()k+1k(()()()(),()(pp如果x=x)中的迭代函数(x)在根附近满足:(1)(x)存在p阶连续的导数但是，则迭代法x=x)为p阶收敛1000k+1k()()(()()xxxxx如果迭代函数(x)在x=(x)根附近有连续的二阶导数:且则时，迭代过程x=x)为线性收敛；而，时为平方收敛推广