数值分析10-方程求根的迭代法

第四章方程求根的迭代法高云方程求根需要考虑的问题求f(x)=0的根代数方程：f(x)=a0+a1x+...+anxn超越方程：f(x)含超越函数，如sin(x),ex,lnx等实根与复根根的重数f(x)=(x–x*)m·g(x)且g(x*)0,则x*为f(x)的m重根有根区间：[a,b]上存在f(x)=0的一个实根在有根的前提下求出方程的近似根。研究内容：迭代法的基本思想0)(xf基本思路)(xx同解迭代公式)(1kkxx给定初值0xnnxxxx110序列*limxxnn存在**)(xx0)(*xf等价于迭代函数？转换是否唯一的不动点为)(*xx几何意义)(xyxy转换例子(1)x=1(x)=x3-6x2+10x-2;(2);32926()()xxxx(3);32326923129()xxxxxxxx(4);234692()xxxx例：已知方程x3-6x2+9x-2=0在[3,4]内有一根，考虑迭代？哪种转换方法好几何含义xyy=xxyy=xx*x*y=g(x)y=g(x)x0p0x1p1x0p0x1p1几何含义xyy=xxyy=xx*x*y=(x)y=(x)x0p0x1p1x0p0x1p1压缩映像定理定理设(x)C[a,b]且可导，若(2)0L1，使得|’(x)|L对x[a,b]成立(1)a(x)b对一切x[a,b]都成立则有(a)对任意x0[a,b]，由xk+1=(xk)产生的迭代序列均收敛到(x)在[a,b]中的唯一不动点x*。0kkx(b)有如下的误差估计11|*|||1kkkxxxxL10|*|||1kkLxxxxL可用|xk+1-xk|来控制收敛精度L越小收敛越快压缩映像定理证明(a)由压缩映像定理可知，不动点x*存在且唯一。111()(*)|'()||*||*||*|kkkkxxxxxxxLx2120|*||*||*||*|kkkkxxLxxLxxLxxlim|*|0kkxx压缩映像定理证明(b)1|*||*|kkxxLxx111|(*)(*)|||**kkkkkkxxxxxxxxxx(1)*kLxx11*1kkkxxxxL1111||()()|'()|||||kkkkkkkkxxxxxxLxx又11101*111kkkkkkLLxxxxxxxxLLL全局收敛与局部收敛定理的条件保证了不动点迭代的全局收敛性。即迭代的收敛性与初始点的选取无关。这种在x*的邻域内具有的收敛性称为局部收敛性。定理中的条件|’(x)|L1可以适当放宽(2’)’(x)在x*的某个邻域内连续，且|’(x*)|1由’(x)的连续性及|’(x*)|1即可推出：存在x*的某个邻域N(x*)=[x*-,x*+],使得对xN(x*)都有|’(x)|L1,则由x0N(x*)开始的迭代都收敛。迭代过程的收敛速度1||lim0||krkkeCe定义则称该迭代为r阶收敛。(1)当r=1时称为线性收敛，此时C1；(2)当r=2时称为二次收敛，或平方收敛；(3)当r1时称为超线性收敛。二分法线性收敛不动点迭代中，若’(x*)0，则11*()(*)'()kkkkexxxxe取极限得1||lim|'(*)|0||krkkexe(C为常数)线性收敛P阶收敛设迭代xk+1=(xk)，若(p)(x)在x*的某邻域内连续，则该迭代法具有p阶收敛的充要条件是定理(1)()(*)*,'(*)''(*)(*)0,(*)0ppxxxxxx()11lim(*)!pkrkkexep并且有()1()()(*)'(*)(*)...(*)!ppkkkkkxxxxxxxxp证明：充分性.根据泰勒展开有()1()*(*)!ppkkkxxxxp()11lim(*)!pkrkkexep必要性的证明必要性.设迭代xk+1=(xk)是p阶收敛。迭代两边取极限，由(x)的连续性可知x*=(x*)。设p0是满足00(1)()'(*)'(*)(*)0,(*)0ppxxxx的最小正整数。由充分性的证明过程可知迭代p0阶收敛。00111kkppppkkkeeeee又若p0p，与迭代p阶收敛矛盾p0=p迭代过程的加速设有不动点迭代：1()kkxx1*'()(*)()(*)kkkxxxxxx11'()*'()kkxxx设：'()'()kx11'()*'()kkkkxxxxx11()'()'()kkkkkxxxxx缺点：每次迭代需计算'()kx埃特金算法1*'()(*)kkkxxxx设：1'()'()kk12****kkkkxxxxxxxxAitken加速211*'()(*)kkkxxxx21212*kkkkkkxxxxxxx212(),()kkkkkkkkkkkyxzyyxxxzyx当x收敛到x*时，修正项分子趋于零。一点注记0)(xf)(xfxx)()(xfxx)(11)(11)(111kkkkkkkkxfLxlxxfxLlxxLx1)(11LMxfMxxkkkNewton迭代基本思想：将非线性方程线性化设xk是f(x)=0的近似根，将f(x)在xk一阶Taylor展开:2()()()()()()2!kkkkffxfxfxxxxx，在xk和x之间。0(*)fx()()(*)kkkfxfxxx()*()kkkfxxxfx1()()kkkkfxxxfxxyx*xkxk+1条件：f’(x)0Newton迭代Newton法可以看作下面的不动点迭代：1()kkxx其中()()()fxxxfx2()''()'()'()fxfxxfx’(x*)=0Newton法至少二阶局部收敛定理设f(x)在其零点x*的某个邻域内二阶连续可导且f’(x)0，则存在x*的某个邻域N(x*)=[x*-,x*+],使得对x0N(x*)，Newton法产生的序列以不低于二阶的收敛速度收敛到x*。Newton迭代Newton法也可以看作一类特殊的加速迭代11()'()'()kkkkkxxxxx取(x)=x-f(x)1111()'()'()kkkkkkxfxfxxxfx()'()'()kkkkfxxfxfx()'()kkkfxxfx收敛性定理定理设fC2[a,b]，且f满足(1)f(a)f(b)0(2)对x[a,b]，f’(x)0且f”(x)0；(3)初始点x0[a,b]满足f(x0)f”(x0)0；则Newton法产生的序列收敛到f在[a,b]的唯一零点x*。全局收敛性定理定理设fC2[a,b]，且f满足(1)f(a)f(b)0(2)对x[a,b]，f’(x)0且f”(x)0；则对任意初始点x0[a,b]，Newton法产生的序列收敛到f在[a,b]的唯一零点x*。(3)fafbbafafb()()max,'()'()举例（一）例：设计一个二阶收敛算法计算(a0)。a解：转化为求x2-a=0的正根Newton迭代：12())2(12kkkkkkkkkfxxaxaxxxfxxx212kkkxaxaax22222kkkkkxaxaxaxx1212kkkxaxxa12a二阶收敛mynewton.m重根情形设x*是f(x)的m(m2)重根，Newton法是否收敛？100()()(*)'(*)(*),(*)mmfxfxfxfxTaylor展式11()()()(*)!mmfxfxxm1211()'()()(*)()!mmfxfxxm2312()''()()(*)()!mmfxfxxmNewton迭代：()()()fxxxfx2**()''()'(*)lim'()lim'()xxxxfxfxxxfx11m线性收敛。且重数m越高，收敛越慢。提高收敛阶提高收敛速度但m通常无法预先知道！法一：取()()()fxxxmfx'(*)0x二阶收敛法二：将求f(x)的重根转化为求另一个函数的单根。构造针对(x)的具有二阶收敛的Newton迭代：2()()'()()'()'()()''()xfxfxxxxxfxfxfx令，则x*是(x)的单重根。()()()fxxfx降低初始点的要求例：求sin(x)-x/6=0的正根。mynewton.mNewton下山法：1()'()kkkkfxxxfxkk为数列中满足的最大数。012ll1()()kkfxfx算法7.2(Newton下山法)给定初始点x0，精度要求1.如果|f(xk)|,停机，输出xk2.计算，=1()'()kkkdfxfx3.如果|f(xk+dk)||f(xk)|，令xk+1=xk+dk，返回第1步；否则折半，重新计算第3步Newton法的收敛依赖于初始点的选取。割线法Newton法的缺点：每步迭代都要计算导数值只需计算函数值，避免计算导数；切线斜率割线斜率11()()()kkkkkfxfxfxxx111()()()()kkkkkkkfxxxxxfxfxxk-1xkxk+1xk+1切线割线需要两个初始点；收敛比Newton法稍慢，但对初始点要求同样高。割线法公式111()()()()kkkkkkkfxxxxxfxfx两点割线法100()()()()kkkkkfxxxxfxfxx单点割线法误差估计引理设f(x)在其零点x*的某个邻域N(x*)=[x*-,x*+]内存在连续的二阶导数，且f’(x)0，又设xk-1,xkN(x*)\{x*}，且互不相等，则由两点割线法的误差ek=xk-x*满足112''()'()kkkkkfeeef其中11,min,,*,max,,*kkkkkkxxxxxx局部收敛性定理定理设x*是f(x)的单重零点，f”(x)在x*的某个邻域内连续，则存在x*的一个邻域N(x*)=[x*-,x*+]，使得当x0,x1N(x*)时，由两点割线法产生的序列收敛到x*，且收敛阶为5121618.本章结束谢谢！