数值计算方法二

1、第二章第二章 非线性方程的数值解法非线性方程的数值解法 2.1 二分法二分法 2.2 一般迭代法一般迭代法 2.3 牛顿迭代法牛顿迭代法 2.4 弦截法弦截法 （1）确定初始含根区间）确定初始含根区间 数值计算方法主要分为两大类。数值计算方法主要分为两大类。第一类是第一类是区间收缩法区间收缩法。 0)(: xf求求解解问问题题（2）收缩含根区间）收缩含根区间第二类是第二类是迭代法迭代法。 （1）选定根的初始近似值）选定根的初始近似值（2）按某种原则生成收敛于根的近似点列）按某种原则生成收敛于根的近似点列2.1 二分法二分法(对分法对分法) 一、根的隔离一、根的隔离 将含根区间一个个隔开，找到根

2、的范围，使每将含根区间一个个隔开，找到根的范围，使每个区间只有一个根。个区间只有一个根。 定理定理：对：对f(x)=0,f(x)在在a,b上连续上连续,f(a)f(b) 0时时 g(x) 单调增，单调增，故有故有2 g(2) g(x) g(3) 323321( )03(25)20( )(2)193gxxgxg又由在取间内单调减得故由定理故由定理2.2得：任取得：任取 ，该迭代格式收敛。该迭代格式收敛。02,3x 三、三、 迭代法的误差估计迭代法的误差估计 )42(), 2 , 1(|11 kxxLxxkkkk), 2 , 1(|1211 sxxLxxLxxkkssksksksk故对正整数故对正

3、整数 p，有，有 | )1(1| )(|1111211 kkpkkppkkpkpkpkpkkpkxxLLLxxLLLxxxxxxxx取极限得取极限得令令 p)52()(1|1kkkxxLLxx|1|01xxLLxxkk 由此，对给定的精度由此，对给定的精度 可进行可进行 |*xx1ln1|ln|ln|101 LxxLK |11kkxxLL（2）事后误差估计）事后误差估计 (1) 事前误差估计事前误差估计简单地代之以简单地代之以 |1kkxx)2/1(|1nkkaaxx 或或 三、三、 迭代法的误差估计迭代法的误差估计 对给定的精度对给定的精度 可进行可进行 |*xxk 例例 2.2 试建立收敛

4、的迭代格式求解试建立收敛的迭代格式求解 x e x =0 在在x=0.5附近的一个根（附近的一个根（=10-3）。）。 解解建立迭代格式建立迭代格式 5 . 0)(0 xxgexx初初始始值值,1)(15.000收收敛敛kxkxexeexg 0 0.5 6 0.564860.60653 7 0.568440.54524 8 0.566410.57970 9 0.567560.56006 10 0.5669115 0.57117kkkxkx3*10910100.567.xxxx 四、四、 迭代法的收敛速度与加速收敛技巧迭代法的收敛速度与加速收敛技巧 则称该迭代格式是则称该迭代格式是 p 阶收敛阶

5、收敛的。的。p=1时称为时称为线性收敛线性收敛1p2 时称为时称为超线性收敛超线性收敛p=2 时称为时称为平方收敛平方收敛。 )112()0(1 为为常常数数CCeepkk 定义定义2.2 设迭代格式设迭代格式 的解序列的解序列 收收敛于敛于 的根的根 ，如果迭代误差，如果迭代误差 当当 时满足渐近关系式时满足渐近关系式)(1kkxgx kx xxekk k)(xgx *x对分法：线性收敛对分法：线性收敛212/ )(4/ )(2/ )(2/ )(111111*11 kkkkkkkkkkkkababababxxxxee一般迭代法：线性收敛一般迭代法：线性收敛*11*()()( )()( )()

6、1kkkkkkkkkexxg xg xgxxexxxxxxgg x 2.3 牛顿迭代法牛顿迭代法 一、一、 牛顿迭代公式的构造牛顿迭代公式的构造 设设 f (x) 在其零点在其零点 附近连续可微，已知附近连续可微，已知 为的第为的第k次近似值，则次近似值，则 *xkx )()()()()()()(12xPxxxfxfxxOxxxfxfxfkkkkkkk 取取 的根作为的根作为 的第的第k+1次近似值次近似值 0)(1xPx1kx)122()()(1 kkkkxfxfxx解解得得其迭代函数为其迭代函数为 )132()()()( xfxfxxg牛顿迭代法牛顿迭代法ABxyoab x1 kx)( x

7、fy kx2 kx几何意义几何意义：过点：过点 作函数作函数 y= f (x) 的切线的切线 l： )(,kkxfxP)()(kkkxxxfxfy以切线以切线 l 与与 x 轴的交点轴的交点 作为作为 的新近似值的新近似值 1kx*x二、二、 牛顿迭代法的收敛性与收敛速度牛顿迭代法的收敛性与收敛速度 定理定理 2.3 给定给定 f (x)=0，如果在根，如果在根 附近附近 f (x)二阶连二阶连续，且续，且 为为 f (x)=0的单根，则牛顿迭代法在的单根，则牛顿迭代法在 附附近至少是平方收敛的。近至少是平方收敛的。 *x*x*x证证 2)()()()(xfxfxfxg 对对牛牛顿顿迭迭代代法

8、法首先证明牛顿迭代法的收敛性：首先证明牛顿迭代法的收敛性： 因此由定理因此由定理2.1的推论知，牛顿迭代法局部收敛。的推论知，牛顿迭代法局部收敛。 1)( xg即即证证1)(0)(0)(* xgxgxf而而单单根根条条件件保保证证了了其次证明牛顿迭代法的收敛速度：其次证明牛顿迭代法的收敛速度： 之之间间与与介介于于由由kkkkkxxxxfxxxfxfxf 2)(21)()()(0整理得整理得 212)()()(21)()()(21)()(kkkkkkkkxxxffxxxxffxfxfxx )()(21)()(2121 xfxfxffeekkkk 所所以以 可见，当可见，当 时，牛顿迭代法为平方

9、收敛；时，牛顿迭代法为平方收敛；当当 时，牛顿迭代法超平方收敛。时，牛顿迭代法超平方收敛。 0)( xf0)( xf例例 2.4 试用牛顿迭代法求解试用牛顿迭代法求解 在区在区间间 (2,3) 内满足精度要求内满足精度要求 的根。的根。 052)(3xxxf810相应于该方程的牛顿迭代公式为相应于该方程的牛顿迭代公式为 2352231 kkkkkxxxxx取取 x0 = 2 ，计算结果见表，计算结果见表2-4。 解解0 2 1 2.1 0.1 2.094568121 -0.005431879 2.094551482 -0.000016639 2 2.094551482 01 kkkxxxk83

10、410 xx牛顿迭代法评述牛顿迭代法评述 优点优点：是收敛速度比较快：是收敛速度比较快 缺点缺点：(1) 局部收敛，对初始值的要求比较高。为解局部收敛，对初始值的要求比较高。为解决这一问题，可采用二分法来提供足够决这一问题，可采用二分法来提供足够“好好”的近似值作的近似值作为迭代初值，或通过增加为迭代初值，或通过增加“下山下山”限制来放宽对初值的要限制来放宽对初值的要求，即把牛顿迭代法修改为求，即把牛顿迭代法修改为 01)()(xxfxfxxkkkkk 其中其中 的选取使得的选取使得 （这称为（这称为“下山下山”限限制）。该方法称为制）。该方法称为牛顿下山法牛顿下山法。 )()(1kkxfxf

11、 k （2）当）当 为为 重根时，牛顿迭代重根时，牛顿迭代法仅仅线性收敛。法仅仅线性收敛。 )2(0)( mxf的的*x （3）由于涉及）由于涉及 的计算，导致了对函数的要求的计算，导致了对函数的要求高，并增加了每一迭代步的计算量，这在一定程度上减高，并增加了每一迭代步的计算量，这在一定程度上减弱了该迭代法收敛快的优越性，而且在向非线性方程组弱了该迭代法收敛快的优越性，而且在向非线性方程组推广时，使计算量和对函数的要求大大增加。因此，人推广时，使计算量和对函数的要求大大增加。因此，人们致力于研究建立牛顿迭代法的修改格式以回避对函数们致力于研究建立牛顿迭代法的修改格式以回避对函数导数值的计算。本

12、章仅对非线性方程介绍一种较为有效导数值的计算。本章仅对非线性方程介绍一种较为有效的修改算法的修改算法弦截法。弦截法。 )(xf 2.4 2.4 弦截法弦截法 , 1 , 0,)()()()(10111 kxxxxxfxfxfxxkkkkkkk弦截法弦截法 计算思想是：若已知计算思想是：若已知 x* 的两个近似值的两个近似值 xk 和和 xk-1，则，则以以 f (x) 在在 xk 与与 xk-1 之间的平均变化率之间的平均变化率(差商差商) 近似代替近似代替 ，据此把牛顿迭代法修改为，据此把牛顿迭代法修改为 11)()( kkkkxxxfxf)(kxf 几何意义几何意义是以过是以过 和和 两点

13、两点做曲线做曲线 的弦线的弦线 l ： )(,kkxfxP )(,11 kkxfxQ)(xfy )()()()(11kkkkkkxxxxxfxfxfy 以以 l 与与 x 轴的交点轴的交点 作为的新近似值作为的新近似值1 kxyo xkxy=f(x)PQ1 kx1 kxx 该定理说明弦截法是超线性收敛的算法，也是局部收该定理说明弦截法是超线性收敛的算法，也是局部收敛的方法，其迭代初始值亦可用二分法提供。敛的方法，其迭代初始值亦可用二分法提供。 定理定理 2.4 设设 f (x) 在其零点在其零点 x* 的邻域的邻域 内二阶连续，且对内二阶连续，且对 ，则对，则对 ，相应的弦截法是相应的弦截法是

14、 阶收敛的。阶收敛的。 |xxx0)(, xfx 10, xx618. 1251 p 例例 2.5 试用弦截法求解试用弦截法求解 在区间在区间(2,3)内满足精度要求内满足精度要求 的根。的根。 052)(3 xxxf810 相应于该方程的弦截法公式为相应于该方程的弦截法公式为 )()52()52(521131331 kkkkkkkkkkxxxxxxxxxx解解取取 计算，结果见表计算，结果见表2-5。 3,210 xx 例例 2.6 试讨论函数方程 的根的分布情况， 分别用牛顿迭代法和弦截法求其最小正根， 使误差小于 ，并比较它们的工作量 02sin5)(3xxxf910因为 x-2-1-1

15、0 01 12f(x)-+-+知知又又由由xxxfxxxfsin56)(,cos53)(2 故故 f (x) 在在(0,1)内有惟一零点，所以最小正根内有惟一零点，所以最小正根 1 。 若采用牛顿迭代法计算，则若采用牛顿迭代法计算，则 kkkkkkxxxxxxcos532sin5231 取计算取计算 ，结果见表，结果见表27。 00 x解解在在(0,1)内，内， , 0)( , 0)( xfxf若采用弦截法计算，则若采用弦截法计算，则 )()2sin5(2sin52sin51131331 kkkkkkkkkkxxxxxxxxxx取取 ，解得的结果见表，解得的结果见表2-8。 0, 101xx例

16、例1：用简单迭代法、牛顿迭代法求：用简单迭代法、牛顿迭代法求在（在（0，1）内的根的近似值。）内的根的近似值。( )20 xf xx)10(4 解解 , 1 ,05 .02ln2122ln21)()1 ,0(12ln2)(2 , 1 ,02)5 .0(20110kxxxxxfxxgkxxxkkkxxkkkxxxkx迭迭代代格格式式为为牛牛顿顿迭迭代代法法：简简单单迭迭代代法法：列表计算列表计算简单迭代法简单迭代法 牛顿迭代法牛顿迭代法kkkxkxkxk0 0.5 6 0.640061 0 0.50.707107 7 0.641680 1 0.6389860.612547 8 0.640964 2 0.6411850.654041 9 0.641285 3 0