数值分析10方程求根的迭代法课件.ppt

1、第四章 方程求根的迭代法高 云方程求根需要考虑的问题求求 f(x)=0 的根的根q 代数方程：代数方程：f(x)=a0+a1x+.+anxn超越方程：超越方程：f(x)含超越函数，如含超越函数，如 sin(x),ex,lnx 等等q 实根与复根实根与复根q 根的重数根的重数 f(x)=(x x*)m g(x)且且 g(x*)0,则则 x*为为 f(x)的的 m 重根重根q 有根区间：有根区间：a,b 上存在上存在 f(x)=0 的一个实根的一个实根在在有根的前提下求出方程的的前提下求出方程的近似根。研究研究 内容：内容：迭代法的基本思想0)(xf基基本本思思路路)(xx 同解同解迭代迭代公式公

2、式)(1kkxx 给定初值给定初值0 xnnxxxx110 序序列列*limxxnn 存在存在*)(xx 0)(*xf等价于等价于迭代迭代函数函数？转换是转换是否唯一否唯一的不动点的不动点为为)(*xx 几何几何意义意义 )(xyxy 转换例子(1)x=1(x)=x3-6x2+10 x-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)

3、x0p0 x1p1 x0p0 x1p1 几何含义xyy=xxyy=xx*x*y=(x)y=(x)x0p0 x1p1x0p0 x1p1压缩映像定理定理定理设设 (x)Ca,b 且可导，若且可导，若(2)0 L 1，使得，使得|(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|*|1kkkxxxxL10|*|1kkLxxxxL可用可

4、用|x k+1-xk|来控制收敛精度来控制收敛精度L 越小收敛越快越小收敛越快压缩映像定理证明(a)由压缩映像定理可知，不动点由压缩映像定理可知，不动点 x*存在且唯一。存在且唯一。111()(*)|()|*|*|*|kkkkxxxxxxxLx 2120|*|*|*|*|kkkkxxL xxLxxLxxlim|*|0kkxx压缩映像定理证明(b)1|*|*|kkxxL xx111|(*)(*)|*kkkkkkxxxxxxxxxx(1)*kL xx11*1kkkxxxxL1111|()()|()|kkkkkkkkxxxxxxL xx 又又11101*111kkkkkkLLxxxxxxxxLLL全

5、局收敛与局部收敛p 定理的条件保证了不动点迭代的定理的条件保证了不动点迭代的全局收敛性全局收敛性。即迭代的收敛性与初始点的选取无关。即迭代的收敛性与初始点的选取无关。p 这种在这种在 x*的邻域内具有的收敛性称为的邻域内具有的收敛性称为局部收敛性局部收敛性。定理中的条件定理中的条件|(x)|L 1 可以适当放宽可以适当放宽(2)(x)在在 x*的某个邻域内连续，且的某个邻域内连续，且|(x*)|1由由 (x)的连续性及的连续性及|(x*)|1 即可推出：即可推出：存在存在 x*的的某个某个 邻域邻域 N(x*)=x*-,x*+,使得对使得对 x N(x*)都有都有|(x)|L 1,则由则由 x

6、0 N(x*)开始开始的迭代都收敛。的迭代都收敛。迭代过程的收敛速度1|lim0|krkkeCe定义定义则称该迭代为则称该迭代为 r 阶收敛。(1)当当 r=1 时称为时称为线性收敛，此时，此时 C 1 时称为时称为超线性收敛。p 二分法线性收敛二分法线性收敛p 不动点迭代中，若不动点迭代中，若 (x*)0，则则11*()(*)()kkkkexxxxe取极限得取极限得1|lim|(*)|0|krkkexe(C为常数为常数)线性收敛线性收敛P阶收敛设迭代设迭代 xk+1=(xk)，若，若 (p)(x)在在 x*的某邻域内连续，的某邻域内连续，则该迭代法具有则该迭代法具有 p 阶收敛的充要条件是阶

7、收敛的充要条件是定理定理(1)()(*)*,(*)(*)(*)0,(*)0ppxxxxxx()11lim(*)!pkrkkexep并且有并且有()1()()(*)(*)(*).(*)!ppkkkkkxxxxxxxxp证明：充分性充分性.根据泰勒展开有根据泰勒展开有()1()*(*)!ppkkkxxxxp()11lim(*)!pkrkkexep必要性的证明必要性必要性.设迭代设迭代 xk+1=(xk)是是 p 阶收敛。阶收敛。迭代两边取极限迭代两边取极限，由，由 (x)的连续性可知的连续性可知 x*=(x*)。设设 p0 是满足是满足00(1)()(*)(*)(*)0,(*)0 ppxxxx的最

8、小正整数。的最小正整数。由充分性的证明过程可知迭代由充分性的证明过程可知迭代 p0 阶收敛。阶收敛。00111kkppppkkkeeeee又又若若 p0 p，与迭代与迭代 p 阶收敛矛盾阶收敛矛盾p0=p迭代过程的加速p 设有不动点迭代：设有不动点迭代：1()kkxx 1*()(*)()(*)kkkxxxxxx 11()*()kkxxx 设：设：()()kx 11()*()kkkkxxxxx 11()()()kkkkkxxxxx 缺点缺点：每次迭代需计算每次迭代需计算()kx 埃特金算法1*()(*)kkkxxxx 设：设：1()()kk 12*kkkkxxxxxxxx Aitken 加速加速

9、211*()(*)kkkxxxx 21212*kkkkkkxxxxxxx 21 2(),()kkkkkkkkkkkyxzyyxxxzyx 当当 x 收敛到收敛到 x*时，修正项分子趋于零。时，修正项分子趋于零。一点注记0)(xf)(xfxx )()(xfxx )(11)(11)(111kkkkkkkkxfLxlxxfxLlxxLx 1)(11 LMxfMxxkkkNewton迭代迭代p 基本思想：基本思想：将非线性方程将非线性方程线性化设设 xk 是是 f(x)=0 的近似根，的近似根，将将 f(x)在在 xk 一阶一阶 Taylor 展开展开:2()()()()()()2!kkkkff xf

10、 xf xxxxx，在在 xk 和和 x 之间。之间。0(*)f x()()(*)kkkf xf xxx()*()kkkf xxxf x1()()kkkkf xxxf xxyx*xkxk+1条件：条件：f(x)0Newton迭代迭代p Newton 法可以看作下面的不动点迭代：法可以看作下面的不动点迭代：1()kkxx其中其中()()()f xxxf x2()()()()f x fxxfx(x*)=0Newton 法至少法至少 二阶 局部收敛定理定理 设设 f(x)在其零点在其零点 x*的某个邻域内的某个邻域内二阶连续可导二阶连续可导且且 f(x)0，则存在，则存在 x*的的某个某个 邻域邻域

11、 N(x*)=x*-,x*+,使得对使得对 x0 N(x*)，Newton 法产生的序列以法产生的序列以不低于不低于二阶二阶的收敛速度收敛到的收敛速度收敛到 x*。Newton迭代迭代p Newton 法也可以看作一类特殊的加速迭代法也可以看作一类特殊的加速迭代11()()()kkkkkxxxxx 取取 (x)=x-f(x)1111()()()kkkkkkxf xfxxxfx ()()()kkkkf xx fxfx ()()kkkf xxfx收敛性定理收敛性定理定理定理设设 f C2a,b，且，且 f 满足满足(1)f(a)f(b)0；则则 Newton 法产生的序列收敛到法产生的序列收敛到

12、f 在在 a,b 的唯一零点的唯一零点 x*。全局收敛性定理全局收敛性定理定理定理设设 f C2a,b，且，且 f 满足满足(1)f(a)f(b)0)。a解：转化为求转化为求 x2-a=0 的正根的正根Newton 迭代：迭代：12()2(12kkkkkkkkkf xxaxaxxxf xxx212kkkxaxaax22222kkkkkxaxaxaxx1212kkkxaxxa12 a二阶收敛二阶收敛mynewton.m重根情形重根情形p 设设 x*是是 f(x)的的 m(m 2)重根，重根，Newton法是否收敛？法是否收敛？10 0()()(*)(*)(*),(*)mmf xfxfxfx Ta

13、ylor 展式展式11()()()(*)!mmf xfxxm 1211()()()(*)()!mmfxfxxm 2312()()()(*)()!mmfxfxxm Newton 迭代：迭代：()()()f xxxf x2*()()(*)lim()lim()xxxxf x fxxxfx11m 线性收敛。线性收敛。且重数且重数 m 越高，收敛越慢。越高，收敛越慢。提高收敛阶提高收敛阶p 提高收敛速度提高收敛速度但但 m 通常无法预先知道通常无法预先知道！法一：取法一：取()()()f xxxmf x(*)0 x二阶收敛二阶收敛法二：将求法二：将求 f(x)的重根转化为求的重根转化为求 另一个函数另一

14、个函数 的单根。的单根。构造针对构造针对 (x)的具有二阶收敛的的具有二阶收敛的 Newton 迭代：迭代：2()()()()()()()()xf x fxxxxxfxf x fx令令 ，则，则 x*是是 (x)的单重根。的单重根。()()()f xxf x降低初始点的要求降低初始点的要求例：例：求求 sin(x)-x/6=0 的正根。的正根。mynewton.mp Newton 下山法：下山法：1 ()()kkkkf xxxfx k k 为数列为数列 中满足中满足 的最大数。的最大数。012ll 1()()kkf xf x p 算法 7.2(Newton下山法下山法)给定初始点给定初始点 x

15、0，精度要求，精度要求 1.如果如果|f(xk)|,停机，输出停机，输出 xk2.计算计算 ，=1()()kkkdf xfx 3.如果如果|f(xk+dk)|f(xk)|，令，令 xk+1=xk+dk，返回第，返回第1步；步；否则否则 折半，重新计算第折半，重新计算第3步步Newton 法的收敛依赖于初始点的选取。法的收敛依赖于初始点的选取。割线法割线法p Newton法的缺点：法的缺点：每步迭代都要计算导数值每步迭代都要计算导数值 只需计算函数值，避免计算导数；只需计算函数值，避免计算导数；切线斜率切线斜率 割线斜率割线斜率11()()()kkkkkf xf xfxxx 111()()()(

16、)kkkkkkkf xxxxxf xf x xk-1xkxk+1xk+1切线切线割线割线 需要两个初始点；需要两个初始点；收敛比收敛比Newton法稍慢，但对初始点要求同样高。法稍慢，但对初始点要求同样高。割线法公式割线法公式111()()()()kkkkkkkf xxxxxf xf x p 两点割线法100()()()()kkkkkf xxxxf xfxx p 单点割线法误差估计误差估计引理引理 设设 f(x)在其零点在其零点 x*的的某个邻域某个邻域 N(x*)=x*-,x*+内存在连续的二阶导数，且内存在连续的二阶导数，且 f(x)0，又设，又设 xk-1,xk N(x*)x*，且互不相等，则由两点割线法的误差，且互不相等，则由两点割线法的误差 ek=xk-x*满足满足112()()kkkkkfee ef 其中其中 11,min,*,max,*kkkkkkxx xxx x 局部收敛性定理局部收敛性定理定理定理 设设 x*是是 f(x)的单重零点，的单重零点，f”(x)在在 x*的的某个邻域内连某个邻域内连续，则存在续，则存在 x*的的一个邻域一个邻域 N(x*)=x*-,x*+，使得当，使得当x0,x1 N(x*)时，由两点割线法产生的序列收敛到时，由两点割线法产生的序列收敛到 x*，且收，且收敛阶为敛阶为 5 1 2 1618.本章结束谢谢！