数值分析方程求根的迭代法精品文稿.ppt

《数值分析方程求根的迭代法精品文稿.ppt》由会员分享，可在线阅读，更多相关《数值分析方程求根的迭代法精品文稿.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数值分析方程求根的迭代法数值分析方程求根的迭代法第1页，本讲稿共30页方程求根需要考虑的问题求求 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 的一个实根的一个实根在在有根的前提下求出方程的的前提下求出方程的近似根。研究研究 内容：内容：第2页，本讲稿共30页迭代法的基本

2、思想基基本本思思路路同解同解迭代迭代公式公式给定初值给定初值存在存在等价于等价于迭代迭代函数函数？转换是转换是否唯一否唯一几何几何意义意义第3页，本讲稿共30页转换例子(1)x=1(x)=x3-6x2+10 x-2;(2);(3);(4);例：已知方程已知方程 x3-6x2+9x-2=0 在在 3,4 内有一根，考虑迭代内有一根，考虑迭代？哪种转换方法好哪种转换方法好第4页，本讲稿共30页几何含义xyy=xxyy=xx*x*y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 第5页，本讲稿共30页几何含义xyy=xxyy=xx*x*y=(x)y=(x)x0p0 x1p1x0p0 x

3、1p1第6页，本讲稿共30页压缩映像定理定理定理设设 (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*。(b)有如下的误差估计有如下的误差估计可用可用|x k+1-xk|来控制收敛精度来控制收敛精度L 越小收敛越快越小收敛越快第7页，本讲稿共30页压缩映像定理证明(a)由压缩映像定理可知，不动点由压缩映像定理可知，

4、不动点 x*存在且唯一。存在且唯一。第8页，本讲稿共30页压缩映像定理证明(b)又又第9页，本讲稿共30页全局收敛与局部收敛p 定理的条件保证了不动点迭代的定理的条件保证了不动点迭代的全局收敛性全局收敛性。即迭代的收敛性与初始点的选取无关。即迭代的收敛性与初始点的选取无关。p 这种在这种在 x*的邻域内具有的收敛性称为的邻域内具有的收敛性称为局部收敛性局部收敛性。定理中的条件定理中的条件|(x)|L 1 可以适当放宽可以适当放宽(2)(x)在在 x*的某个邻域内连续，且的某个邻域内连续，且|(x*)|1由由 (x)的连续性及的连续性及|(x*)|1 即可推出：即可推出：存在存在 x*的的某个某

5、个 邻域邻域 N(x*)=x*-,x*+,使得对使得对 x N(x*)都有都有|(x)|L 1,则由则由 x0 N(x*)开始开始的迭代都收敛。的迭代都收敛。第10页，本讲稿共30页迭代过程的收敛速度定义定义则称该迭代为则称该迭代为 r 阶收敛。(1)当当 r=1 时称为时称为线性收敛，此时，此时 C 1 时称为时称为超线性收敛。p 二分法线性收敛二分法线性收敛p 不动点迭代中，若不动点迭代中，若 (x*)0，则则取极限得取极限得(C为常数为常数)线性收敛线性收敛第11页，本讲稿共30页P阶收敛设迭代设迭代 xk+1=(xk)，若，若 (p)(x)在在 x*的某邻域内连续，的某邻域内连续，则该

6、迭代法具有则该迭代法具有 p 阶收敛的充要条件是阶收敛的充要条件是定理定理并且有并且有证明：充分性充分性.根据泰勒展开有根据泰勒展开有第12页，本讲稿共30页必要性的证明必要性必要性.设迭代设迭代 xk+1=(xk)是是 p 阶收敛。阶收敛。迭代两边取极限迭代两边取极限，由，由 (x)的连续性可知的连续性可知 x*=(x*)。设设 p0 是满足是满足的最小正整数。的最小正整数。由充分性的证明过程可知迭代由充分性的证明过程可知迭代 p0 阶收敛。阶收敛。又又若若 p0 p，与迭代与迭代 p 阶收敛矛盾阶收敛矛盾p0=p第13页，本讲稿共30页迭代过程的加速p 设有不动点迭代：设有不动点迭代：设：

7、设：缺点缺点：每次迭代需计算每次迭代需计算第14页，本讲稿共30页埃特金算法设：设：Aitken 加速加速当当 x 收敛到收敛到 x*时，修正项分子趋于零。时，修正项分子趋于零。第15页，本讲稿共30页一点注记第16页，本讲稿共30页Newton迭代迭代p 基本思想：基本思想：将非线性方程将非线性方程线性化设设 xk 是是 f(x)=0 的近似根，的近似根，将将 f(x)在在 xk 一阶一阶 Taylor 展开展开:，在在 xk 和和 x 之间。之间。xyx*xkxk+1条件：条件：f(x)0第17页，本讲稿共30页Newton迭代迭代p Newton 法可以看作下面的不动点迭代：法可以看作下

8、面的不动点迭代：其中其中(x*)=0Newton 法至少法至少 二阶 局部收敛定理定理 设设 f(x)在其零点在其零点 x*的某个邻域内的某个邻域内二阶连续可导二阶连续可导且且 f(x)0，则存在，则存在 x*的的某个某个 邻域邻域 N(x*)=x*-,x*+,使得对使得对 x0 N(x*)，Newton 法产生的序列以法产生的序列以不低于不低于二阶二阶的收敛速度收敛到的收敛速度收敛到 x*。第18页，本讲稿共30页Newton迭代迭代p Newton 法也可以看作一类特殊的加速迭代法也可以看作一类特殊的加速迭代取取 (x)=x-f(x)第19页，本讲稿共30页收敛性定理收敛性定理定理定理设设

9、 f C2a,b，且，且 f 满足满足(1)f(a)f(b)0；则则 Newton 法产生的序列收敛到法产生的序列收敛到 f 在在 a,b 的唯一零点的唯一零点 x*。第20页，本讲稿共30页全局收敛性定理全局收敛性定理定理定理设设 f C2a,b，且，且 f 满足满足(1)f(a)f(b)0)。解：转化为求转化为求 x2-a=0 的正根的正根Newton 迭代：迭代：二阶收敛二阶收敛mynewton.m第22页，本讲稿共30页重根情形重根情形p 设设 x*是是 f(x)的的 m(m 2)重根，重根，Newton法是否收敛？法是否收敛？Taylor 展式展式Newton 迭代：迭代：线性收敛。

10、线性收敛。且重数且重数 m 越高，收敛越慢。越高，收敛越慢。第23页，本讲稿共30页提高收敛阶提高收敛阶p 提高收敛速度提高收敛速度但但 m 通常无法预先知道通常无法预先知道！法一：取法一：取 二阶收敛二阶收敛法二：将求法二：将求 f(x)的重根转化为求的重根转化为求 另一个函数另一个函数 的单根。的单根。构造针对构造针对 (x)的具有二阶收敛的的具有二阶收敛的 Newton 迭代：迭代：令令 ，则，则 x*是是 (x)的单重根。的单重根。第24页，本讲稿共30页降低初始点的要求降低初始点的要求例：例：求求 sin(x)-x/6=0 的正根。的正根。mynewton.mp Newton 下山法

11、：下山法：k k 为数列为数列 中满足中满足 的最大数。的最大数。p 算法 7.2(Newton下山法下山法)给定初始点给定初始点 x0，精度要求，精度要求 1.如果如果|f(xk)|,停机，输出停机，输出 xk2.计算计算 ，=13.如果如果|f(xk+dk)|f(xk)|，令，令 xk+1=xk+dk，返回第，返回第1步；步；否则否则 折半，重新计算第折半，重新计算第3步步Newton 法的收敛依赖于初始点的选取。法的收敛依赖于初始点的选取。第25页，本讲稿共30页割线法割线法p Newton法的缺点：法的缺点：每步迭代都要计算导数值每步迭代都要计算导数值 只需计算函数值，避免计算导数；只

12、需计算函数值，避免计算导数；切线斜率切线斜率 割线斜率割线斜率xk-1xkxk+1xk+1切线切线割线割线 需要两个初始点；需要两个初始点；收敛比收敛比Newton法稍慢，但对初始点要求同样高。法稍慢，但对初始点要求同样高。第26页，本讲稿共30页割线法公式割线法公式p 两点割线法p 单点割线法第27页，本讲稿共30页误差估计误差估计引理引理 设设 f(x)在其零点在其零点 x*的的某个邻域某个邻域 N(x*)=x*-,x*+内存在连续的二阶导数，且内存在连续的二阶导数，且 f(x)0，又设，又设 xk-1,xk N(x*)x*，且互不相等，则由两点割线法的误，且互不相等，则由两点割线法的误差差 ek=xk-x*满足满足其中其中第28页，本讲稿共30页局部收敛性定理局部收敛性定理定理定理 设设 x*是是 f(x)的单重零点，的单重零点，f”(x)在在 x*的的某个邻域内连某个邻域内连续，则存在续，则存在 x*的的一个邻域一个邻域 N(x*)=x*-,x*+，使得当，使得当x0,x1 N(x*)时，由两点割线法产生的序列收敛到时，由两点割线法产生的序列收敛到 x*，且收，且收敛阶为敛阶为第29页，本讲稿共30页本章结束本章结束谢谢！第30页，本讲稿共30页