数值计算课件——第二章非线性方程的数值解法

1、第二章第二章 非线性方程的数值解法非线性方程的数值解法非线性方程求解的基本问题：非线性方程求解的基本问题：根的个数；根的位置根的个数；根的位置。对于非线性方程，由于对于非线性方程，由于f(x)的多样性，求其根尚无一的多样性，求其根尚无一般的解析方法可以使用般的解析方法可以使用。求解方程的根，一般有两种情形求解方程的根，一般有两种情形：求出在给定范围内的某个根求出在给定范围内的某个根求出方程的全部根，而根的数目和位置事先不知道求出方程的全部根，而根的数目和位置事先不知道 本章介绍几种方程求根的方法。这些方法大部分是要已本章介绍几种方程求根的方法。这些方法大部分是要已知根的范围，而且在此范围内只有

2、一个根知根的范围，而且在此范围内只有一个根。求非线性方程根的一些常用方法：求非线性方程根的一些常用方法：区间分割法（逐步搜索法、区间分割法（逐步搜索法、 二分法）二分法）迭代法迭代法牛顿法牛顿法割线法割线法2.1区间搜索法区间搜索法预备知识：预备知识：方程的根：单根、重根。方程的根：单根、重根。 根的存在性定理：根的存在性定理：定理：定理：若若 f 在在a, b上连续，且上连续，且 f (a) f (b) 0，则，则 f 在在 (a, b) 上必有一根；若上必有一根；若 f 在在a, b上上连续且单调连续且单调则则 f 在在 (a, b) 上上有且仅有有且仅有一根。一根。定理定理 函数函数 f

3、 (x)对于对于x* 有有f (x*) =0，但，但 则称则称 为方程的单根。如果有为方程的单根。如果有 但但 ，则称，则称 是方程是方程 的的 m重根。重根。 *()0fx*1)*()()()0mf xfxfx（()*()0mfx*x2.1.1逐步搜索法逐步搜索法思路：思路：先把区间先把区间a,b均分均分为为N等分，从初始值等分，从初始值x0=a开始，步长开始，步长h（ba）/N来增值。每跨一步进行一次根的搜索。来增值。每跨一步进行一次根的搜索。计算速度慢，一般用于确定根的位置计算速度慢，一般用于确定根的位置例：例：求连续函数求连续函数 f(x) 在有根区间在有根区间a,b上的根。上的根。2

4、.1.2 二分法二分法思路思路：二分法的基本思想二分法的基本思想 就是逐步就是逐步对分对分区间区间,经过对根的搜经过对根的搜索，将有根区间的长度缩小到充分小，从而求出满足精度的索，将有根区间的长度缩小到充分小，从而求出满足精度的根根 的近似值。的近似值。二分法的步骤：二分法的步骤： 在有根区间在有根区间 取中点取中点 ，计算函数，计算函数值值 ，若，若 ，就得到方程的实根，就得到方程的实根 ，否则检查否则检查 与与 是否同号，如同号，说明待是否同号，如同号，说明待求的根求的根 在在 的右侧，这时令的右侧，这时令 ；如；如 在在 的左侧，这时令的左侧，这时令 ，这样新的有根区间，这样新的有根区间

5、 的长度为的长度为 之半。之半。 bax 210 2baf02 baf2*bax 0 xf af*x0 xbbxa 101,*x0 x011,xbaa 11,baba,ba,二分法二分法abx0 x1a1x*b1 11,ba 11,ba 11121bax *x1x 22,ba kkbababa,11 kkba , 11,ba ababkkk 21二分法二分法 kkkbax 21,210 xxx*x误差误差 分析分析： ababxxkkkk 1*2121 kxx* kkkbax 21*x二分法二分法优点：优点：简单，简单， 对对f (x) 要求不高要求不高(只要连续即可只要连续即可) .用二分法

6、求根，最好先给出用二分法求根，最好先给出 f (x) 草图以确定根的大草图以确定根的大概位置。或用搜索程序，将概位置。或用搜索程序，将a, b分为若干小区间，对每一分为若干小区间，对每一个满足个满足 f (ak)f (bk) 0 的区间调用二分法程序，可找出区的区间调用二分法程序，可找出区间间a, b内的多个根，内的多个根，二分法二分法二分法特点：二分法特点：缺点缺点：收敛慢（：收敛慢（ 等比级数等比级数） 无法求复根及偶重根无法求复根及偶重根 21对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k ： 12lglglg21 abkabk求方程求方程f(xf(x)

7、=0)=0的根的二分法算法的根的二分法算法).(21)4(;endwhile.,;,0)()()2);(),(21)1|)3(;3,10)()()2(;,:)1(baxbxbaelsexabathenxfafifxfbaxbawhileelsebathenbfafifbaba 输出输出计算计算令令时做时做步步转第转第值值输入输入重新重新步步返回第返回第值及精度控制量值及精度控制量的的有根区间有根区间输入输入 2.2 2.2 简单迭代法简单迭代法2.2.1 2.2.1 迭代原理迭代原理2.2.2 2.2.2 迭代的收敛性迭代的收敛性2.2.3 2.2.3 迭代的收敛速度迭代的收敛速度2.2.4

8、2.2.4 迭代的加速迭代的加速2.2 简单迭代法简单迭代法f (x) = 0 x = (x)等价变换等价变换f (x) 的根的根 (x) 的不动点的不动点思思路路从一个初值从一个初值 x0 出发出发, ,计算计算 x1 = (x0), x2 = (x1), , xk+1 = (xk), 若若 收敛，即存在收敛，即存在 x* 使得使得 ，只要，只要 连续，则连续，则 ，也就是也就是 x* = (x* )，即，即x* 是是 的根，也就是的根，也就是f 的根。的根。若若 xk发散，则迭代发散，则迭代 法失败。法失败。kx*limxxkk kkkkxx limlim12.2.1迭代法原理：迭代法原理

9、：3331101xxxxxx 迭代法迭代法：是一种逐次逼近的方法。是一种逐次逼近的方法。它是它是用某个用某个固定公式反复校正根的近似值，使之逐步精确，最后固定公式反复校正根的近似值，使之逐步精确，最后得到满足精度要求的结果。得到满足精度要求的结果。 xk+1 = (xk) 称为称为迭代格式，迭代格式， (x) 称为称为迭代函数迭代函数x0 x0 称为称为迭代初值迭代初值, , 数列数列 称为称为迭代序列迭代序列 kx 迭代法迭代法思想思想：将隐式方程将隐式方程 的求根问题归的求根问题归结为计算一组显式结为计算一组显式xk+1 = (xk) ，也就是说，迭代过程是，也就是说，迭代过程是一个逐步显

10、式化的过程。一个逐步显式化的过程。x = (x)例题例题 例2.2.1 试用迭代法求方程 在区间(1，2)内的实根。 解：由 建立迭代关系 k=10,1,2,3.计算结果如下:31xx01)(3xxxf311kkxx例题例题n精确到小数点后五位5102132472. 1x例题n但如果由 建立迭代公式 仍取 ，则有 ， 显然结果越来越大， 是发散序列1x3x,.2 , 1131kxxkk 5 . 10 x 2.3751x 12.392x kx 简单迭代法的几何意义：把求方程( ) 0f x 的根的问题， 转化为求( )yxyx两曲线的交点问题，交点的横坐标就是方程的根*x。 xyy = xxyy

11、 = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1简单迭代法简单迭代法收敛定理收敛定理 考虑方程考虑方程 x =(x), (x)在在a, b上连续上连续, 若若( I ) 对所有对所有 x a, b ，有，有 (x) a, b；( II ) 存在存在 0 L 1 ，使所有使所有 x a, b 有有| (x) | L 1 。则：则：1）方程）方程x = (x)在在a, b上的解上的解x*存在且唯一。存在且唯一。 2）任取）任取 x0 a, b，由迭代过程，由迭代过程 xk

12、+1 = (xk) 收敛于收敛于x*简单迭代法简单迭代法推论推论 验后误差估计：验后误差估计：|1|*|1 kkkxxLLxx|1|*|01xxLLxxkk 误差估计式：误差估计式：验前误差估计：验前误差估计：证明：证明： (x) 在在a, b上有根？上有根？令令xxx )()( bxa )( ,0)()( aaa 0)()( bbb )(x 有根有根 根唯一？根唯一？反证：若不然，设还有反证：若不然，设还有 ，则，则)(xx ),*( )()(*)(xxxx xx*在在和和之间。之间。 *xx0)(1)( xx* 而而xx*1| )(| 当当k 时，时， xk 收敛到收敛到 x* ？ |*|

13、kxx|*| )(| )(*)(|11 kkxxxx 0|*|.|*|01 xxLxxLkk 3 简单迭代法简单迭代法 xx 有根有根L1| )1 (1 kkkxxLxxL?|1|*|1 kkkxxLLxx|)|*(| |*|111 kkkkkkkkxxxxLxxxxLxxLxx ?|1|*|01xxLLxxkk | | )(| )()(|2121211 kkkkkkkkxxLxxxxxx 可用可用 来来控制收敛精度控制收敛精度|1 kkxxL 越越 收敛越快收敛越快小小定理条件非必要条件，对某些问题在区间定理条件非必要条件，对某些问题在区间a, b上上不不满足满足| (x) | L 1 ，迭

14、代也收敛。，迭代也收敛。 实际应用中还是用此定理判断收敛性，当不满足收实际应用中还是用此定理判断收敛性，当不满足收敛条件时，改变迭代公式使之满足。敛条件时，改变迭代公式使之满足。3 简单迭代法简单迭代法|1 .|1|1|*|012121xxLLxxLLxxLLxxkkkkkk 2.2.3 迭代法局部收敛性迭代法局部收敛性1 *x bax, bax, *:xx kkxx 1 0 x kkxx 1*x*x*x*x 1* x *:xx 1 Lx *xxxx *xx x *xxxxLxx kkxx 1 0 x x xx *x 1* x kkxx 1由于在实际应用中根由于在实际应用中根 x* 事先不知道

15、，故条件事先不知道，故条件 | (x* )| 1无法验证。但已知根的初值无法验证。但已知根的初值x0在根在根 x*邻域，又根据邻域，又根据 (x)的的连续性，则可采用连续性，则可采用 | (x0 )| 1 来代替来代替| (x* )| 1，判断迭代的收敛性。，判断迭代的收敛性。 *x kkxx 1 xx *xxekk 1 pp 0 ccceepkkk 1limkxp10 , 1 cp2 p1 pc*x kkxx 1p xp 0, 0*1* xxxxpp *xQ: 如何实际确定收敛阶？如何实际确定收敛阶？例题n例：例： 证明函数 在区间1，2上满足迭代收敛条件。n证明：31)x(x上严格单调增函

16、数。是区间所以因为,)(2 , 1 0) 1(31)x(32baxxx例题 2 , 1 1431|) 1(31| )(|332xLxx又23)2(12) 1 (33，而）。满足条件（，所以即1)(2 , 1 )2(),1 (x）。满足条件（所以2)(x满满足足收收敛敛原原理理。在在故故2 , 1 1)x(3 x 例题n若取迭代函数 ， 不满足收敛定理，故不能肯定 收敛到方程的根。 1)x(3 x2 , 1 3|3| )(|2xxx因为,.1 , 0)(1nxxnn Aitken 加速：加速：简单迭代法简单迭代法xyy = xy = (x)x*x0P(x0, x1)x1x2x P(x1, x2)

17、012202201220102)(2)(xxxxxxxxxxxxx 一般地，有：一般地，有：KKKKKKKxxxxxxx 12212)(.),(,),(,),(),(,34123012010 xxxxxxxxxxx 比比 收敛得略快。收敛得略快。 Kx Kx Steffensen 加速：加速：.,),(), (,),(),(,01201012010 xxxxxxxxxxx 2.3 2.3 牛顿迭代法牛顿迭代法2.3.1 2.3.1 迭代公式的建立迭代公式的建立2.3.2 2.3.2 牛顿迭代法的收敛情况牛顿迭代法的收敛情况2.3.3 2.3.3 牛顿迭代法的修正法牛顿迭代法的修正法2.3 牛顿

18、法牛顿法原理：原理：将非线性方程线性化将非线性方程线性化 Taylor 展开展开取取 x0 x*，将将 f (x)在在 x0 做一阶做一阶Taylor展开展开:20000)(! 2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x* 之之间间 。将将 (x* x0)2 看成高阶小量，则有：看成高阶小量，则有：)*)()(*)(0000 xxxfxfxf )()(*000 xfxfxx 线性化线性化xyx*x0 x1)()(1kkkkxfxfxx 迭代公式迭代公式： )()(xfxfxx 迭代函数迭代函数：牛顿切线法牛顿切线法2.3.2牛顿切线法的收敛情况牛顿切线法的收敛情况 定理

19、定理 （局部收敛性局部收敛性）设函数设函数 在包含在包含 的某邻的某邻域内有域内有 阶连续导数，阶连续导数， 是方程是方程 的的单根单根，则当初值则当初值 充分接近充分接近 时，牛顿切线法收敛，且至时，牛顿切线法收敛，且至少为二阶收敛。并有少为二阶收敛。并有*xk12kkxx*f ( x*)lim( xx*)2 f ( x*) xf 2 p*x 0 xf0 x*x这里这里单根单根意味着：意味着：f ( x*)0 牛顿切线法牛顿切线法2.3.2牛顿迭代法的收敛情况牛顿迭代法的收敛情况 定理定理设函数设函数 满足满足 且且 在在 邻域连续，则牛顿迭代法在邻域连续，则牛顿迭代法在 收敛，且至少为二收

20、敛，且至少为二阶收敛。并有阶收敛。并有f ( x*)0, f ( x )0, *)(2*)(*)(*lim21xfxfxxxxkkk xf*xf ( x )*x牛顿切线法牛顿切线法证明：证明：牛顿法牛顿法 事实上是一种特殊的不动点迭代事实上是一种特殊的不动点迭代 其中其中 ，则，则)()()(xfxfxx 10*)(*)(*)(*)(2xfxfxfx 收敛收敛由由 Taylor 展开：展开：2)*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(! 2)()()(*kkkkkkxxxffxfxfxx 1 kx)(2)(*)(*21kkkkxffxxxx 只要只要f (

21、x*) 0在在单根单根 附近收敛快附近收敛快 k 12kkxx*f ( x*)lim( xx*)2 f ( x*) 牛顿切线法牛顿切线法牛顿法收敛性依赖于牛顿法收敛性依赖于x0 的选取。的选取。x*x0 x0 x0具有具有局部恒收敛性局部恒收敛性，收敛性依赖于，收敛性依赖于初值初值 的选取。的选取。收敛性好收敛性好（至少平方收敛）（至少平方收敛）每次计算要计算导数，每次计算要计算导数，效率不高效率不高牛顿法特点：牛顿法特点：例题例题例1: 用Newton法求 的近似解。（取8位有效数字）。解：由零点定理。0cos)(xxxf内有根。在)2, 0(0cosxx迭代公式得及由Newtonxxfsi

22、n1)(,.1 , 0sin1cos1nxxxxxnnnnn例题085133739. 0739085133. 0739085133. 0739085178. 0;73936133. 044*43210 xxxxxxx故取得取例题n例2: 用Newton法计算 。解：220)(2aaxxf其中迭代公式得及由Newtonxxf2)(,.1 , 0)2(212221nxxxxxxnnnnnn。有十位有效数的近似值是已的精确值相比，。与，则取332102414213562. 1414215686. 11.416666675 . 1xxxxx牛顿迭代法算法框图牛顿迭代法算法框图Newton迭代法算法迭代

23、法算法。输出）转（做输入1101001001000:)4(;2) 3;)2;/) 1|while(3);();()2(;,) 1 (xendwhilexxffxxfxffxffx牛顿切线法改进牛顿切线法改进牛顿法的改进与推广牛顿法的改进与推广 改进一：改进一：重根时的收敛速度及改进：重根时的收敛速度及改进：Q1: 若若 ，牛顿法牛顿法是否仍收敛？是否仍收敛？0*)( xf设设 x* 是是 f 的的 n 重根，则：重根，则： 且且 。)(*)()(xqxxxfn 0*)( xq因为因为牛顿法事实上是一种特殊的不动点迭代，牛顿法事实上是一种特殊的不动点迭代，其中其中 ，则，则)()()(xfxfx

24、x 22f ( x*)f ( x*) f ( x*)|( x*)|1f ( x*) 111n A1: 有局部收敛性，收敛慢（有局部收敛性，收敛慢（线性收敛线性收敛）。）。Q2: 如何加速重根的收敛？如何加速重根的收敛？)()( )(xfxfxx A2: 修正修正迭代格式（迭代格式（平方收敛平方收敛）n n证明过程证明过程见书见书p42 改进二：改进二： 牛顿牛顿下山法下山法扩大初值范围的修正牛顿法扩大初值范围的修正牛顿法： 原理原理：若由若由 xk 得到的得到的 xk+1 不能使不能使 | f | 减小，则在减小，则在 xk 和和 xk+1 之间找一个更好的点之间找一个更好的点 ，使得，使得

25、。1 kx)()(1kkxfxf xkxk+1,)1(1kkxx 1, 0 )()()1 ()()(1kkkkkkkkxfxfxxxfxfxx 通过适当选取的通过适当选取的 保证函数值能单调下降保证函数值能单调下降牛顿切线法改进牛顿切线法改进下山法：下山法：迭代过程中保证函数值单调下降，即迭代过程中保证函数值单调下降，即)()(1kkxfxf 牛顿下山法：牛顿下山法：将牛顿法与下山法结合使用的算法将牛顿法与下山法结合使用的算法 下山因子下山因子牛顿牛顿下山法几点讨论下山法几点讨论实用中从实用中从 = 1开始反复将开始反复将 减半计算。一旦单调下降则称减半计算。一旦单调下降则称“下山成功下山成功

26、”。反之则称。反之则称“下山失败下山失败”，需另选初值，需另选初值x0计算。计算。牛顿切线法改进牛顿切线法改进当当 1时。牛顿下山法只有线性收敛速度，但对初值的选时。牛顿下山法只有线性收敛速度，但对初值的选取却可放的很宽。常用牛顿下山法选取初值。取却可放的很宽。常用牛顿下山法选取初值。实用中常用牛顿下山法选取初值。为加快收敛速度，转入牛实用中常用牛顿下山法选取初值。为加快收敛速度，转入牛顿法来求解根的精确值。顿法来求解根的精确值。牛顿法每一步要计算牛顿法每一步要计算 f 和和 f ，相当于，相当于2个函数值，且有些个函数值，且有些导数难求。为了避开导数的计算，用导数难求。为了避开导数的计算，用

27、差商差商代替代替导数。导数。x0切线切线 割线割线 切线斜率切线斜率 割线斜率割线斜率00)()()(xxxfxfxfkkk 2.42.4弦截法弦截法 ：x2x100)()(xxxfxfkk )()()()(001xxxfxfxfxxkkkkk kkkkxfxfxx1 用用割线斜率割线斜率（差商）替换（差商）替换切线斜率切线斜率，代入牛顿法迭代公式：，代入牛顿法迭代公式：上式中，固定弦的一个端点（上式中，固定弦的一个端点（x x0 0, ,f f( (x0) )），而另一端点变动，），而另一端点变动，称为称为单点弦法。单点弦法。2.4.1 2.4.1 单点弦法单点弦法：单点弦法几何意义单点弦法

28、几何意义*0*00*0f ( x )f ( x )( x )1( xx )1f ( x )f ( x )f ( x )xx 因为因为f(xf(x* *) ) = 0 = 0，故求导数得，故求导数得所以所以0 0 (x(x* *) ) 1 1，所以，所以单点弦法单点弦法仅为仅为线性收敛线性收敛。单点弦法收敛速度单点弦法收敛速度：00f ( x )( x )x( xx )f ( x )f ( x ) 迭代函数迭代函数：*0*0f ( x )f ( x )xx *x当初值当初值x x0 0充分接近充分接近 时时很接近很接近f(xf(x* *) )2.4.2 2.4.2 双点弦法双点弦法：为了加快收敛

29、速度为了加快收敛速度，弦的两个端点都在变动，称为弦的两个端点都在变动，称为双点弦法双点弦法或称或称快速弦截法。快速弦截法。迭代时需要迭代时需要2个初值个初值 xk 和和 xk1。 111 kkkkkkkxxxfxfxfxx双点弦法迭代公式双点弦法迭代公式：双点弦法几何意义双点弦法几何意义P1P2双点弦法收敛速度双点弦法收敛速度： 双点弦截法的收敛性与牛顿迭代法一样，即在双点弦截法的收敛性与牛顿迭代法一样，即在根的某个邻域内，根的某个邻域内，f(xf(x) )有直至二阶的连续导数，且有直至二阶的连续导数，且f(xf(x* *) ) 0 0，具有局部收敛性，同时在邻域任取初，具有局部收敛性，同时在邻域任取初值值x0 x0、x1x1，迭代均收敛。，迭代均收敛。 可以证明，双点弦截法具有超线性敛速度，可以证明，双点弦截法具有超线性敛速度，收敛的阶为：收敛的阶为： 1151.6182 用用Newton法和弦截法解下面方程的根，并比较法和弦截法解下面方程的根，并比较0133xx13)(3xxxf设33)(2xxf由由Newton法法由弦截法由弦截法)()()()(111kkkkkkkxxxfxfxfxx)()(1kkkkxfxfxx331323kkkkxxxxx0=0.5;x1