数值分析课件 (第7章)

1、机动上页下页首页结束 工科研究生公共课程数学系列 内容提要内容提要 7.1 方程求根与二分法方程求根与二分法 7.2 迭代法及其收敛性迭代法及其收敛性 7.3 牛顿法牛顿法 7.4 弦截法弦截法 机动上页下页首页结束 工科研究生公共课程数学系列 7.1 方程求根与方程求根与二分法二分法 一、引言一、引言 . b, aC)x( f ,Rx 0)x( f 的求根问题，其中的求根问题，其中 考虑单变量非线性方程考虑单变量非线性方程 非线性方程的分类非线性方程的分类 . 0ex : . 2 . 01xx : ).n, 1 , 0i (Ra, 0a , 0axaxaxa . 1 x 3 i0 n1n 1

2、n 1 n 0 如如超越方程超越方程 如如其中其中 代数方程代数方程 机动上页下页首页结束 工科研究生公共课程数学系列 32 11.138.841.770 xxx例如求方程的有根区间 搜搜索索法法求求有有根根区区间间。则则可可用用若若 。此此时时 重重零零点点。的的为为则则称称为为正正整整数数其其中中 可可以以分分解解为为如如果果 , 0)b( f)a( f,b, aC)x( f 0*)x(f , 0*)x(f*)x(f*)x( f m)x( f*x .m ,|*)x(g|0 ),x(g*)xx()x( f )x( f )m()1m( m 由此可知方程的有根区间为由此可知方程的有根区间为1,2

3、 3,4 5,61,2 3,4 5,6 求根问题的三个方面：存在性，分布，精确化。求根问题的三个方面：存在性，分布，精确化。 x 0 1 2 3 4 5 6 f(x)的符号 + + + 机动上页下页首页结束 工科研究生公共课程数学系列 0 0 0 0 101110 ( )( )0,()/2. ()( ) ,. ( )() ,; , f af bxab f xf x x f af x ax bbaa bx 设取 假如是的零点， 那么输出停止 假若不然， 若与同号，则 否则。 11 11 01 11 (1) , , , (2) x , x =, , x =, 22 - (3) - , , , ,

4、22 kk kk k kk k a ba bab abba b ab a b ababa 二分过程中有三个量在变： （区间、近似根、区间长度） 二、二分法 0 x y X* x0 ab y=f(x) a1 b1 机动上页下页首页结束 工科研究生公共课程数学系列 3 ( )101.0,1.5- 2. f xxx 求在内的一个 实根，准确到小数点后位 例例7 17 1 1 k |*| ()/2()/2 ()/2*(). xx k kkk kkk xxbab a xabxk k 收敛性分析： 因 故有, 因此，只要二分的足够多次（即 充分大）， 便有，这里 为预定的精度。 机动上页下页首页结束 工科

5、研究生公共课程数学系列 k ak bk xkf(xk)符号 0 1 2 3 4 5 6 1.0 1.25 1.3125 1.3203 1.5 1.375 1.3438 1.3281 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.3242 + + + 005. 0 xx 6k6 6 * 度度），便便能能达达到到预预定定的的精精次次（只只要要二二分分 机动上页下页首页结束 工科研究生公共课程数学系列 。的的一一个个为为函函数数称称 化化为为等等价价形形式式将将非非线线性性方方程程 不不动动点点)x(*x ; )*x(*x0*)x(f )x(x 0)x(f 二分法

6、的优点是算法简单，且总是收敛的，缺点是二分法的优点是算法简单，且总是收敛的，缺点是 收收 敛太慢敛太慢,故一般不单独将其用于求根，只用其为根求故一般不单独将其用于求根，只用其为根求 得一个较好的近似值。得一个较好的近似值。 7.2 迭代法迭代法 一、不动点迭代与不动点迭代法一、不动点迭代与不动点迭代法 机动上页下页首页结束 工科研究生公共课程数学系列 010 1 ,() (), 0,1,2,.2.2 ( ) kk xxx xxk x 给定初始近似值可以得到 如此反复，构造迭代公式 （） 称为迭代函数。 上述迭代法是一种逐次逼近法，其基本思想是将隐式方上述迭代法是一种逐次逼近法，其基本思想是将隐

7、式方 程归结为一组显示的计算公式，就是说，迭代过程实质上是程归结为一组显示的计算公式，就是说，迭代过程实质上是 一个逐步显示的过程。一个逐步显示的过程。 0 , 2.2 lim ()( ) 2.2 k k k xa bx xx xxx 如果对任何，由式（）得到的序列有极限 则称迭代方程收敛，且为的不动点， 称式（）为不动点迭代法。 机动上页下页首页结束 工科研究生公共课程数学系列 3 101.5-*xxx求在附近的根。 例例7 7 2 2 k xkkxkkxk 0 1 2 1.5 1.35721 1.33086 3 4 5 1.32588 1.32494 1.32476 6 7 8 1.324

8、73 1.32472 1.32472 ), 2 , 1 , 0k(1xx 1xx 1 3 k1k 3 据据此此建建立立迭迭代代公公式式 式式）将将方方程程改改写写成成下下列列形形解解：（ 即即为为所所求求的的根根。 实实际际上上已已满满足足方方程程完完全全相相同同，可可以以认认为为与与结结果果 787 xxx 机动上页下页首页结束 工科研究生公共课程数学系列 3 3 1 0 12 (2) xx -1 1 1.5, 2.375,12.39, . kk xx x xx 另一种等价形式 建立迭代公式 迭代初值仍取则有 继续迭代下去已经没有必要，因为结果显然会越来越大，继续迭代下去已经没有必要，因为结

9、果显然会越来越大， 不可能趋于某个极限。这种不收敛的迭代过程称作是发散的。不可能趋于某个极限。这种不收敛的迭代过程称作是发散的。 一个发散的迭代过程，纵使进行了千百次迭代，其结果也毫一个发散的迭代过程，纵使进行了千百次迭代，其结果也毫 无价值。因此，迭代格式形式不同，有的收敛，有的发散，只无价值。因此，迭代格式形式不同，有的收敛，有的发散，只 有收敛的迭代过程才有意义，为此要研究不动点的存在性及迭有收敛的迭代过程才有意义，为此要研究不动点的存在性及迭 代法的收敛性。代法的收敛性。 即即为为所所求求的的根根。 实实际际上上已已满满足足方方程程完完全全相相同同，可可以以认认为为与与结结果果 787

10、 xxx 机动上页下页首页结束 工科研究生公共课程数学系列 的的不不动动点点。即即为为 即即使使在在由由连连续续函函数数性性质质可可知知存存 且且满满足足显显然然 定定义义函函数数因因 上上存存在在不不动动点点。在在，显显然然或或若若 性性。证证明明：先先证证不不动动点点存存在在 )x(x),x(x 0,)x(f)b, a(x 0b)b()b(f , 0a)a()a(f ,b, aC)x(f x)x()x(f ,b)x(a b, a)x(b)b(a)a( 二、不动点的存在性与迭代法的收敛性二、不动点的存在性与迭代法的收敛性 .*xb,a)x( 2.4 |;yx|L| )y()x(| ,b,ay

11、,x , 1L0 (2) ,b,a)x( ,b,ax (1) , b,aC)x( 上上存存在在唯唯一一的的不不动动点点在在那那么么 ）（ 都都有有使使得得常常数数 都都有有 并并且且设设迭迭代代函函数数 定定理理1 1 机动上页下页首页结束 工科研究生公共课程数学系列 代代替替。可可用用它它表表明明定定理理中中的的条条件件 有有则则由由中中值值定定理理可可知知对对 有有且且对对任任意意 ，在在使使用用时时如如果果中中的的条条件件和和定定理理对对定定理理 2.7)(2 )b, a(,y-xL)yx)()y()x( b, ay, x 2.7)( 1L)x( b, axb, aC)x( 221 0

12、1 0 。的的不不动动点点只只能能是是唯唯一一的的引引出出矛矛盾盾。故故 得得则则由由 的的不不动动点点，都都是是及及再再证证唯唯一一性性。设设 )x( xxxxL )x()x(xx 2.4 )x(b, axx 2121 121 1 2 2 机动上页下页首页结束 工科研究生公共课程数学系列 2/33 1 3 33 32 1 -(x)x1(x)(x1), 3 1 1 1,2(x)( )1, 3 4 12(x)32 11 (x)x1(x)3x1 2(x)1 在例7 2中，当时， 在区间中，又因 故定理 中条件 成立。所以迭代法收敛。 而当时，在区间 ，中 不满足定理条件。 (2.5) | (2.2

13、) . | 1 |* *,)( ,1 01 0 xx L L xx xx bax k k 的的不不动动点点均均收收敛敛于于 迭迭代代序序列列对对任任意意初初值值的的条条件件下下在在定定理理 定定理理2 2 机动上页下页首页结束 工科研究生公共课程数学系列 具具有有足足够够精精度度。足足够够小小即即可可保保证证近近似似值值 次次计计算算结结果果的的偏偏差差由由此此可可见见，只只要要相相邻邻两两 将将其其化化为为而而不不便便于于实实际际应应用用。可可由由于于含含有有信信息息 但但它它次次数数原原则则上上可可用用于于确确定定迭迭代代误误差差估估计计式式 k kk kkk x xx xx L xx |

14、 . | 1 |* 1 1 1 | L , (2.5) . | 1 1 |* |,| 1 |* *, *,0)( ; 1| )(|, 10 ,)(, )( 1 01 0 1 kkk k k xx L xx xx L L xx xbax xbaxf LxbaxL baxbax baCx | 4) | 3) (2.2) 2) 1) (2) (1) , , 均收敛于均收敛于迭代序列迭代序列对任意初值对任意初值 上有唯一的根上有唯一的根在在方程方程那么那么 都有都有使得使得 都有都有 并且并且如果迭代函数如果迭代函数 推论推论 机动上页下页首页结束 工科研究生公共课程数学系列 32 0 1 22 32

15、2 3 1 2 x -x -10 x1.5 11 (1) 7-3 1, 1; (2)1,1 11 (3), 11 k k kk k k xx xx xxxx xx xx 为求在附近的一个根，设奖方程改写成下 列等价形式，并建立相应的迭代公式： 迭代公式 迭代公式 迭代公式 试分析每种迭代公式的收敛性，并选取一种公式求出具有四位有效 数 例 字的近似根。 上上整整体体收收敛敛。 在在故故迭迭代代式式， ，时时当当 来来考考察察，的的邻邻域域取取解解 6 .1 , 3 .1 1 11 3 .1 22 6 .1 , 3 .1 1 1)(6 .1 , 3 .1 5 .1 2 1 33 2 0 k k

16、x xL x x xx x (x) (1) 1.61.3 : 机动上页下页首页结束 工科研究生公共课程数学系列 , L (x) (x) x1(x) 32 下下表表计计算算结结果果见见取取 只只需需数数字字要要求求结结果果具具有有四四位位有有效效 中中迭迭代代公公式式计计算算。较较小小，故故取取的的由由于于 发发散散。故故 上上整整体体收收敛敛。在在故故 时时当当 5 .1 105 .010 2 11 )2()2( 1 1 , 1 )16 .1 (2 1 )1(2 1 )(, 1 1 )3( 6 .1 , 3 .1 1 1522.0 )3 .11 ( 6 .1 3 2 )1 (3 2 6 .1

17、, 3 .1 6 .1 , 3 .1 )2( 0 33 1 1 2/3 3 2 1 3/223/22 x L L xx x x x x x xx L x x x kk k k kk 机动上页下页首页结束 工科研究生公共课程数学系列 k xk k xk 1 2 3 1.484248034 1.472705730 1.468817314 4 5 6 1.467047973 1.466243010 1.465876820 .1x 0 5.取取初初值值 k x x k 10 e10 x-20 (1) 0 1 (2) x(2-e )/10,x0 7 4 - . 比较求的根到三位小数所需的计算量： 在区间

18、 ，内用二分法； 用迭代法取初值 例 466.1,10 2 1 6 3 xxxx故故可可取取由由于于 机动上页下页首页结束 工科研究生公共课程数学系列 迭迭代代计计算算结结果果如如下下上上整整体体收收敛敛。取取在在 时时，当当 具具有有三三位位有有效效数数字字。 用用二二分分法法计计算算，此此时时 故故因因解解： , 0 x0.5, 0 )e2( 10 1 )x(,5 . 0 , 0)x(0.5, 0 x)2( xx ,10 2 1 000030517. 0 2 1 xx , 1x0, 0)1(f , 0)0(f,1 , 0 x)1( 0 x 14 * 4 15 14 k k xk k xk

19、1 2 3 0.1 0.089482908 0.090639135 4 5 6 0.090512616 0.090526468 0.090524951 精精确确到到三三位位小小数数。故故 此此时时 6 4- 566 xx ,10 2 1 00000720. 0 xx L1 L xx 机动上页下页首页结束 工科研究生公共课程数学系列 . , , : . , 均均收收敛敛对对于于任任意意初初值值迭迭代代过过程程于于是是依依据据定定理理可可以以断断定定 是是因因为为 这这总总有有对对于于任任意意此此外外成成立立于于任任意意 使使对对的的某某个个邻邻域域存存在在由由连连续续函函数数性性质质证证明明 是

20、是局局部部收收敛敛的的则则迭迭代代法法且且 的的某某邻邻域域内内有有连连续续在在的的不不动动点点为为迭迭代代函函数数设设 Rxxx xxxxLxxxx RxRxLxRx xxRx x xxxx kk 01 )( )()()( )(. 1)( *:* )2 . 2(, 1|*)(| *)(,)(* 定定理理3 3 . *x b,ax k 局局部部收收敛敛性性附附近近考考察察收收敛敛性性，称称为为 点点。应应用用上上经经常常只只在在不不动动不不容容易易由由定定理理作作出出判判断断 局局收收敛敛性性；上上的的收收敛敛性性通通常常称称为为全全在在迭迭代代序序列列 三、局部收敛性与收敛阶三、局部收敛性与

21、收敛阶 局局部部收收敛敛。法法 则则称称迭迭代代且且收收敛敛到到产产生生的的序序列列迭迭代代对对任任意意 的的某某个个邻邻域域如如果果存存在在有有不不动动点点设设 )2 . 2( *,)2 . 2(, ,:*, 0 (x) xRxRx xxRxx k 定定义义1 1 机动上页下页首页结束 工科研究生公共课程数学系列 . 0*)x() x 3 1 ( 2 1 ) x() x 3 x( 2 1 x4 ;134. 0 2 3 1*)x( 2 x 1) x() 3x( 4 1 xx3 ; 1*)x( x 3 ) x( x 3 x2 ; 1132*)x(1x2) x(3xxx1 2 k k1k 2 kk

22、1k 2 k 1k k 2 k1k ，）（ ，）（ ，）（ ，）（ 2 30*3-.xx只用四则运算不用开方求方程的根例例7 57 5 kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4) 0 1 2 3 ? x0 x1 x2 x3 ? 2 3 9 87 ? 2 1.5 2 1.5 ? 2 1.75 1.73475 1.732631 ? 2 1.75 1.732143 1.732051 ? 机动上页下页首页结束 工科研究生公共课程数学系列 .p*x ,0*)x(0*)x(*)x(*)x( , p*x)x(x)x( )p()1p( 阶阶收收敛敛的的附附近近是是那那么么迭迭代代过过程程在在 ，

23、并并且且连连续续导导数数 阶阶邻邻近近具具有有的的根根在在如如果果迭迭代代函函数数 定定理理4 4 .2p 1p1p . p ,C ,C e e lim *,xxe*,x)x(x p k 1k k kkk1k 时时为为平平方方收收敛敛超超线线性性收收敛敛；当当 时时为为当当时时迭迭代代法法为为线线性性收收敛敛；特特别别地地，当当收收敛敛 阶阶则则称称迭迭代代过过程程为为是是不不等等于于零零的的常常数数若若 误误差差收收敛敛于于设设迭迭代代过过程程 定定义义2 2 阶收敛阶收敛该迭代法为该迭代法为知知由定理由定理，而，而的的 ，而迭代法，而迭代法，故它只是线性收敛的，故它只是线性收敛的的的中，迭

24、代法中，迭代法例例 平方收敛平方收敛时时当当 迭代法线性收敛迭代法线性收敛时时特别地，当特别地，当 2 4 4 . ,0 2, 0 3 2 )(0)( )4(0)()3( ,0*)(, 0*)( ;1|*)(| pxx x xx x 机动上页下页首页结束 工科研究生公共课程数学系列 1 2 (1) (2-), 11 ( ),( )2(1), 11 -2( )0( )-2a0, 11 lim( ) 2 k k k xxax xxax aa xa aa e a ea 解: 迭代函数为（ ） 且即是（ ）的不动点。又 （ ），所以，由定理4知， 迭代是二阶收敛的，且 0 1 0 2 0, (2-),

25、 0,1,2, 7-6 , 0 1-1 kkk k x a xxaxka xax 给定初值以及迭代公式 常数 证明：(1) 该迭代式是二阶收敛的； (2) 该迭代产生的序列收敛的充要条件是 例 机动上页下页首页结束 工科研究生公共课程数学系列 1 2 -11111 242 120 2 0 11 (2) -(-1)-1, 1 (1- ), 1(1) 1 (1)(1) 1 11 lim0lim k k kkkkk kkkkk kkkkkkk k k kk kk kk exaxrax aa xxrer a raxaxrrrr rrrr err e aa 因,令则 等价于 然而 故 由此可知 0 0

26、0,lim01, 1-1 kk k rr ax r 而又等价于即 机动上页下页首页结束 工科研究生公共课程数学系列 (4.1) , 0)xx)(x(f)x(f 0)x(f ),xx)(x(f)x(f)x(f Taylor, 0)x(f,x 0)x(f : kkk kkk kk 近近似似表表示示为为于于是是 展展开开做做并并假假定定近近似似根根 的的设设已已知知方方程程线线性性化化牛牛顿顿迭迭代代公公式式的的推推导导、 . 4.2 . )x(f )x( f xx ,x k k k1k 1k 牛牛顿顿迭迭代代法法这这就就是是 ）（ 则则有有计计算算公公式式记记 其根为 7.3 牛顿法牛顿法 一、一

27、、牛顿法及其收敛性牛顿法及其收敛性 机动上页下页首页结束 工科研究生公共课程数学系列 则则进进行行加加速速若若用用 迭迭代代收收敛敛，由由定定理理 当当解解： ,)3 . 3( .73307. 3x , 5 . 3x2 ,4 , 3)x(,4 , 3x , 1 3 2 )x(max , x 2 )x( 160 4x3 2 303,-4. x xe求方程在中的解例例7 77 7 kxkykzk 0 1 2 3.5 3.73444 3.73307 3.60414 3.73381 3.66202 3.73347 机动上页下页首页结束 工科研究生公共课程数学系列 ）（ 性性牛牛顿顿迭迭代代法法的的局局

28、部部收收敛敛 义义牛牛顿顿迭迭代代公公式式的的几几何何意意 4.3 . *)x(f2 *)x(f *)xx( *xx lim , *)x(f *)x(f *)x(f 0*)x(f*)x(f0*)x(f*)x(f *)x( , )x(f )x(f )x(f )x(f )x(f )x(f)x(f 1)x( , )x(f )x(f x)x( . . 2 k 1k k 4 2 22 2 机动上页下页首页结束 工科研究生公共课程数学系列 0-. x xe用牛顿法求方程的根例例7 87 8 . 5 . 0 x ), 2 , 1 , 0k( x1 ex x x 0 k x k k1k k 取取初初值值 解解

29、：牛牛顿顿迭迭代代公公式式为为 ;115 0Cx ,C 2 并并求求 ，应应用用牛牛顿顿法法解解二二次次方方程程对对于于给给定定正正数数 例例8 8 二、牛顿法应用举例二、牛顿法应用举例 kxkkxk 0 1 0.5 0.57102 3 4 0.56716 0.56714 机动上页下页首页结束 工科研究生公共课程数学系列 Cx Cx q Cx C-x Cx Cx Cx C-x Cx Cx )Cx( 2x 1 Cx )C-x( 2x 1 Cx ) x C x( 2 1 x .0 x 0 0 2 k k 1k 1k 2 k k 1k 1k 2 k k 1k 2 k k 1k k k1k 0 k 记

30、记 据据此此反反复复递递推推有有 以以上上两两式式相相除除得得 式式施施行行配配方方手手续续，易易知知事事实实上上，对对 迭迭代代公公式式皆皆平平方方收收敛敛证证明明： 机动上页下页首页结束 工科研究生公共课程数学系列 的的结结果果。精精度度为为 次次便便得得到到。迭迭代代初初值值取取 利利用用 6 0 k k1k 10 301x ,115C ) x C x( 2 1 x 即即迭迭代代过过程程恒恒收收敛敛。 时时故故由由上上式式推推知知，当当总总有有对对任任意意 整整理理上上式式，得得 ,Cx k1,q,0 x q1 q C2Cx k 0 2 2 k k kxkkxk 0 1 2 10 10.

31、750000 10.723837 3 4 10.723805 10.723805 机动上页下页首页结束 工科研究生公共课程数学系列 . )x(f)x(f 1, (4.12) , 2 , 1 , 0k, )x(f )x(f xx x)1(xx (4.7) . )x(f )x(f xx k1k k k k1k k1k1k 0 k k1k 逐逐次次折折半半直直到到满满足足其其中中下下山山因因子子 牛牛顿顿下下山山法法： 简简化化牛牛顿顿法法： 三、简化牛顿法与牛顿下山法三、简化牛顿法与牛顿下山法 . )x(f 1 C,2)x(fC0 1, )x(fC1)x(g ., 2 , 1 , 0k, 0C )

32、x(Cfxx 0 kk1k 公公式式局局部部收收敛敛时时即即当当 构构造造迭迭代代公公式式 机动上页下页首页结束 工科研究生公共课程数学系列 3 000 101.5*. 1.50.60.6 11/32 xxx xxx 如、再求在附近的根 ：依次用牛顿法，简化牛顿法， ，折半，计算结果如下： 例例 解解 kxkxkxk f(xk) 0 1 2 3 4 1.5 1.34783 1.32520 1.32472 0.6 17.9 发散 0.6 -1.384 1.140625 -0.656643 1.36181 0.1866 1.32628 0.00667 1.32472 0.0000086 机动上页下

33、页首页结束 工科研究生公共课程数学系列 .0)x(*x , )x(g*)xx()x(mg )x(g*)xx( )x( m)x( f*x)x(f / )x( f)x( . (4.13) , )x(f )x( f mxx )x(g*)xx()x( f ,m k k k1k m 的的单单根根是是故故 重重根根，则则的的是是，若若还还可可令令 仍仍平平方方收收敛敛 可可将将迭迭代代法法改改为为 ，牛牛顿顿法法不不是是平平方方收收敛敛重重根根情情形形 四、重根情形四、重根情形 机动上页下页首页结束 工科研究生公共课程数学系列 . |)x(p)x(f|min|)x(p)x(f | | ,H)x(p ,b,

34、 aC)x(f n Hp * n n * n nn 或或切切比比雪雪夫夫逼逼近近问问题题此此即即所所谓谓最最佳佳一一致致逼逼近近 使使得得误误差差求求多多项项式式本本节节讨讨论论 . (4.14) , )x(f )x( f)x(f )x(f )x( f xx )x( kk 2 k kk k1k 仍仍平平方方收收敛敛 用用牛牛顿顿法法得得对对 42 2 1 2 1 2 1 2 440*2. 2 1 4 2 2 (4.13) 2 (2) 3 (4 - .14) . 2 9 k kk k k kk k kk kk k xxx x xx x x xx x xx xx x 用上述三种方法求的二重根 ：（ ）牛顿法； （ ）； （ ） 计算结果如下： 7 7 解解 例例 机动上页下页首页结束 工科研究生公共课程数学系列 ).xx( xx )x(f)x(f )x(f )xx(x,x f )x(f )x(p xx .1 )x(f ).x(f )x(f,0)x(f k 0k 0k k k0kk1 0k kk k ，得得到到线线性性插插值值函函数数为为插插值值节节点点和和以以 单单点点弦弦截截法法 的的迭迭代代法法。下下面面介介绍绍避避免免求求要要计计算算 外外还还每每步步除除计计算算程程用用牛牛顿顿法法求求解解非非线线性性方方 kxk(1)(2