数值分析第四章学习小结

1、节 4.1 非线性方程的迭代解法和 4.2 非线性方程组的迭代解法。本章出它的根的近似值，本章将要介绍几种常用的有效的数值求根方法，它们都属于迭代法，因而还要讨论这些方法的收敛性和收敛速度。4.1.1 对分法（1）基本思想：确定方程有根的区间；将区间逐次分半缩小，得到一个区间长度以1/2 的比例减小的 含根区间序列 ，在给定根的误差界时，利用长度趋于零的特点，xk1 的等比2数列的收敛速度相同。ababk(2)迭代终止条件或者b a x 12 x skk( ) f x2k2kk(3)二分法的优缺点：优点：程序简单，总能求出近似根，对要求不高。f(x)缺点：收敛速度慢，只能求单根和奇数重根，不能

2、求偶重根，复根。二分法一般用于对根求近似根。4.1.2 简单迭代法及其收敛性迭代法的基本思想:f(x)0 x (x)xk1(x ),k 0,1,2,k.之逐步精确化，最后得到满足精度要求的解。迭代法的基本思想是将隐式方程的求根问题归结为计算( )x x一组显式公式( )x xk1k 产生的序列 收敛于 ，x x收敛性：若由迭代公式x (x k 1,2,3.k1kk则 是原方程的根。x收敛条件：a非局部收敛性定理：设函数 (x)Ca,b，在（a，b）内可导，且满足两个条件：（1）当xa,b(x)a,bxa,b时， (x) L1，其中L 为一常数。则有如下结论：（1）方程在上有唯一的根( ) ,

3、x xa b 产生的序列且x a,b0 x x( )xa b , k1kk收敛于kL（3）成立误差估计式或ssx x xx x x1L110Lk1kkk这种形式的收敛定理称为大范围收敛性定理，但当条件不够充分时，预先指定一个区间常常是不可能的。b局部收敛性定理( ),( )设s s x 在包含s ( ) 1 s存在当时，由简单迭代法产生的序列0 x s,s0 x (x )k1k 且收敛于s。x s s, k4.1.3 简单迭代法的收敛速度. 成立，则称序列 收敛于s 具有当（某个正整数）时，ek Kcxk1kerk xr 是 r 的大小反映了序列 收敛xkk的快慢程度，r 越大收敛越快。r=1

4、 时称序列线性收敛的，r=2 时，为平方收敛的。线性收敛的条件：设函数 (x)Ca,b，且满足如下条(x)C(a,b)xa,b时，(x)a,b；（2）当xa,b时， (x) L1，其中L 为一常数。 则对任取的于方程产生的序列收敛x a,b( )x xxa b , 0k1kk 在内的唯一的根时 是线性收敛x (x) a,bx s0 xk的。m 阶收敛的条件： 设在包含 s 的某个开区间内连续( ), ( )s sx(m)（ 如果则存在，当 ( ) 0( 1,2, , ( ) 0m2s i m( ) s 0(i)m 但产生的序列x s s, x s0 x x( )xa b , 0k1kk以 m

5、阶收敛速度收敛于s。4.1.4 迭代的加速过程1.加权迭代法: x (x k1k1L1或者改进： x x xx k1 (x )Lx 1Lk11L1Lk1kkk缺点：L值的确定需要函数的迭代信息，不便于实际应用。x s L,k2x s L 2Aitken 加速法：设序列 线性收敛于s，则k1x sxsxkk1kx s x s(x x)2k1k2 x xs2k1kx s x sk2 x x x2k1kk1k2k1k3.Steffensen 迭代法( ),( )y x z y迭代公式： kkkk(y x )2x x ,k kkk12y xk z.kkk无论迭代法是否收敛于s，Steffensen迭代

6、法都能以不低于二阶的收敛速度收敛于s。4.1.5 Newton法推导f(x)0 h(x)f(x)0h(s)0( )0 sh(x)f(x)x x(x )fx x ,kf(x )k1k推出迭代公式kk Newton法可求方程的实数根和复数根，求实数根时有明显的几何 上的点(x ,f(x )作该曲线的切线，y f(x)xkkk此曲线与X轴相交的交点的横坐标就是Newton法迭代序列的第k+1个元素 ，因此Newton法又称为切线法。xk1局部收敛性定理：设 s 是方程的根，在包含 s 的某个开区间内连续且( )x x( )f x，则存在，当时，由Newton法产生的序列f (x) 00 x s,s0

7、 收敛于s；若且，则序列 是平方收敛的。xf (s) 0 x s0 xkk 在区间 上存在二阶连续导数，且f(x)a,bf(a)fb)0在区间 f (x)a,bxa,b时，。则有Newton法产f (x) 0 x a,b, f (x )f (x ) 0000 生的序列 单调收敛于方程在 内唯一的根s，并且至少( ) , x a b xxk是平方收敛的。4.1.6求方程m重根的Newton法设s是方程的m重根（m2 在s的某邻域内有mf x( )( )x xf(x)阶连续导数，这时(x) xf (s) f(s) fs( ) 0,fs( ) 0(m1)(m)f (x).1( ) ,( ) 1s s

8、 s m（2）变形的Newton 法(x)令 (x) xf (x)道重根的重数（3）若s 是方程迭代函数：g(x) x迭代公式：x x 的 m 重根，则s 为u(x)的单根。f(x)f(x)kkk1k2kkkf(x ) f(x )kk1f(x x x )fkkkf(x ) f(x )kkkk1f(s)0 当x ,x Ix0k.远是割线上的一点。2.迭代公式：x x 00k1k100f(x x x )kkk1kk03.几何意义：在区间a,b（1）f(a)fb)0。则由单点割线x ,x a,b010001xkff12n1 1f( )212n2x212nn F(x)0fx x x x x x( ,

9、, n212n12nii1.(x) F(x) 2min (x)min F(x) 24.2.2简单迭代法R R设F(x):方程组：nnF(x)0 xG(x)（）Fx(k1)2.收敛性：非局部收敛性定理G(x ),k 0,1,2,G(k)设在闭区域把 映入它G:D R RD DDnn00自身，即在 上压缩映射，即存在常数，L（0,1）（D DD000使对任意的有则有下列结论：x,yDG(x)G(y) L x y0 x D( )k（1）对任取的，由迭代公式产生的序列，且收敛于x(0) D00方程内的唯一解 ；xk（2）成立误差估计式或x x( ) xxk1LLx x x x(k)(k)(k1L实际计

10、算时，可预先给定精度水平，当迭代序列满足0 x x(k)(k时停止迭代，取当前的 作为方程组的近似解。(k)xx(k)4.2.3 Newton1.基本思想将非线性方程组线性化，构造迭代格式。f(x,y)0(x,y)0设为方程组解的一组初始近似解。(x ,y )1f002fff (x,y) f (x ,y ) (xx ) (y y )11xy110000fff (x,y) f (x ,y )(xx )(y y )22xy220000.x(k1)F x x F(x ) ( ), 0,1,2,k(k)(k) 1(k)3.收敛性：条件：连续可微，非奇异；F(x)F (x ) 结论： 超线性收敛于xxk

11、 二次连续可微，则 平方收敛于k若F(x)xx4.Newton算法x xx(k)x F(x ) F(x )(k)(k(k)(k) 1(k)x(k x x( )( )F x( ) x( ) F x( ) ( )( )kkkkk5.Newton法的优缺点：优点：收敛快，一般都能达到平方收敛；缺点：对初值要求较苛刻，且要求4.2.4 离散Newton 法的各个偏导数存在。f (x)i1.基本思想：用差商代替导数。(x h e ) f (x )f (x ) f(k)(k)(k)(k)ijjh(k)iixjj (f x) ( )f x( )(e f x( ) ( )h e(k)f xh( )(k)(k)

12、kkk111111nnhh(k)(k)1n( ) ( , )F xJ x h(k)(k)(k)(x h e ) f (x )f (x h e ) f (x ) f(k)(k)(k)k( )k( )k( )n11nnnnnhh(k)(k)1n2.迭代公式：3. 的选取x(k1) x J(x ,h ) F(x ),k 0,1,2,(k)(k)(k) 1(k)h(k)(1)保证:h x h e , j ,n(k)(k)(k)jjj(2)Newton-Steffensen 方法，取（ 为非零常数；h c F(x )c(k)(k)jjjj=1,2，n）（3） 也可取与k 无关的常数。h(k)j.8.设

13、s 是方程的根，在 s 的某个邻域内连续，并且f(x)0f(x)f (x)4f(x)。令 (x) x为使迭代法f(x) 0h(x2x (x )(k 0,1,)k1f (x)f (x)k能够至少以三阶收敛速度收敛于s，则应如何选取函数 ？h(x)解：由定理 4.4 可知，至少三阶收敛速度于 s。则，(s) 0(1)f(x)(s)0，(s) 0。令u(x)，于是(x) xu(x)h(x)u(x)2。(2)(3)f (x)通过求导可得：( ) 1 ( ) ( ) ( ) 2 ( ) ( ) ( ) 0; u x h x u x h x u x u x x ( )u (x)h (xu (x)2h(xu

14、(xu(x) x2h(xu(x) 2h(xu(xu (x)0;2 ( ) 0. xf(2)(x)h(x)2f (x)9.试分别用割线法和单点割线法求方程 xsinx1的根，要求。x x / x 6kk1k解：令 f(x) xsinx1， f(0)10, f(1)sin10，所以 f(0)f(1)0。f(x x x )（1）割线法：迭代公式x x ,k 0,1,2,k1kkf(x ) f(x )k1kkk1由于 f(0)f(1)0， f(x) xsinx1在0,1 只有一个根。f(x )(x x )取x 0,x 1，则x x 0.543044125100(x ) f(x )0 f10101.f(

15、x )(x x )0 0.543044125f(x ) f(x )0.059788703(0.5430441251)0.0597887030.841470984x x 1121100.508092841f(x )(x x )x x 0.508092841221f(x ) f(x)32210.543044125)0.0053952610.0597887030.510985750算到x 0.510973429即可。5（2）单点割线法f(x) xsinx1，f(x)1cos, f(x)sinx，满足定理4.9的4个条件：（1）f(0)f(1)0； （2）当；x0,1, f (x)0(2)在区间, f

16、 (x)0且x ,x 0,1f (1)f (1)0, f (1)f (x )0011取x 0,x 1，由单点割线法产生的迭代公式01f(x x x ) 由单点割线法产生的序列 单调收x x ,k 0,1,2,0 xkkf(x ) f(x )k1kkk0敛于方程在 内唯一的根。0,1f(x x x )1x x 10f111f(x ) f(x )f(1) f12110f(x x x )1x x 1f22f(x ) f(x )f f3221结果为s x 0.51097342882.查阅其他参考书，寻找用牛顿法求解多项式方程根的特殊方法，再找一种加权法。解: (1)Newton法1.基本思想.将非线性

17、方程组线性化，构造迭代格式。f(x,y)0(x,y)0设为方程组解的一组初始近似解。(x ,y )1f002fff (x,y) f (x ,y ) (xx ) (y y )11xy110000fff (x,y) f (x ,y )(xx )(y y )22xy220000 x(k1)F x x F(x ) ( ), 0,1,2,k(k)(k) 1(k)3.收敛性：条件：连续可微，非奇异；F(x)F (x ) 结论： 超线性收敛于xxk 二次连续可微，则 平方收敛于k若F(x)xx4.Newton算法x xx(k)x F(x ) F(x )(k)(k(k)(k) 1(k)x(k x x( )(

18、)F x( ) x( ) F x( ) ( )( )kkkkk5.Newton法的优缺点：优点：收敛快，一般都能达到平方收敛；缺点：对初值要求较苛刻，且要求(2)离散Newton 法的各个偏导数存在。f (x)i1.基本思想：用差商代替导数。(x h e ) f (x )f (x ) f(k)(k)(k)(k)ijjh(k)iixjj (f x) ( )f x( )(e f x( ) ( )h e(k)f xh( )(k)(k)kkk111111nnhh(k)(k)1n( ) ( , )F xJ x h(k)(k)(k)(x h e ) f (x )f (x h e ) f (x ) f(k)

19、(k)(k)k( )k( )k( )n11nnnnnhh(k)(k)1n2.迭代公式：3. 的选取x(k1) x J(x ,h ) F(x ),k 0,1,2,(k)(k)(k) 1(k)h(k).(1)保证:h x h e , j ,njcjjjj=1,2，n）hj简化牛顿法，也称平行弦法. 其迭代公式为:k1kk迭代函数:若在根 附近成立 (x) 1 (x) 1，即取0 xf (x)2,则迭 x代法xk1kk1在x，则称为简化牛ck1kkf0 x.牛顿法收敛性依赖初值 的选取如果 偏离所求根 较远，则x0 x0 x牛顿法可能发散.为了防止迭代发散，对迭代过程再附加一项要求，即具有单调性:

20、f(x ) f(x ). 满足这项要求的算法称下山法.k1k将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度.f(x )将牛顿法的计算结果与前一步的近似值适当加x x k( )f xk1kk权 平 均 作 为 新 的 改 进 值 , x x )x ,其 中k1k1kf(x )(0 1) 称为下山因子,即称为牛顿 x x (k k( )f xk1kk下山法.选择下山因子时从 1 下降条件成立为止.f(x ) f(x k1k任玉杰习题 2.81.用抛物线法求方程 f(x)2x 5x10的一个实根的近似值x 3k精确到 。6x01,xx在 MATLAB工作窗口

21、输入x=-2:0.001:2;y=2.*x.3-5.*x-1;plot(x,y);grid,gtext(y=2x3-5x-1)运行后得出图形 1-1，可知区间内有一个实根，故取初值(0.5,0).y=2.*x.3-5.*x-1;（3）保存名为paowu.m的M文件(4)在MATLAB工作窗口输入（5）运行后输出结果为0.5000 -0.2022 -0.0058提示：根的判别式值为正数.ans=2.0000 0.0478 0.2367 -0.2034提示：根的判别式值为正数.ans=3.0000 0.0012提示：根的判别式值为正数.ans=4.0000 0.0000 0.0000 -0.203

22、4提示：根的判别式值为正数.0.00000.0060 -0.2034 -0.000000ans=5.0000k=50.00000.0000 -0.2034piancha=1.1558e-010 xdpiancha=5.6836e-010 xk=-0.2034yk=0k =5 的根的近似值106值为yk=0，x 的相邻最小偏差为piancha=1.1558e-010，其相对误差k为xdpiancha=5.6836e-010.表1-1xdpianchakpianchaxk1.00002.00003.00004.00005.00000.25000.04780.00120.00000.00000.50

23、000.23670.00600.00000.0000-0.2022-0.2034-0.2034-0.2034-0.2034-0.00580.0000-0.000000.9(3,（3）保存名为paowu.m的M文件(4)在MATLAB工作窗口输入.k,piancha,xdpiancha,xk,yk=paowu(-2,-1,-3,1e-9,1e-9,100)（5）运行后输出结果为提示：根的判别式值为正数.ans=1.0000提示：根的判别式值为正数.ans=2.0000 0.0871提示：根的判别式值为正数.ans=3.0000 0.0086 0.0045 -1.9042提示：根的判别式值为正数.

24、ans=4.0000 0.0001提示：根的判别式值为正数.ans=5.0000 0.0000 0.0000 -1.9042提示：根的判别式值为正数.1.00000.3333 -1.9129 -0.08650.0455 -1.9042 -0.00070.00000.0000 -1.9042 -0.000000ans=6.0000k=60.00000.0000 -1.9042piancha=4.4409e-016xdpiancha=2.3322e-016xk=-1.9042yk=0k =6 的根的近似值109值为yk=0，x 的相邻最小偏差为piancha=4.4409e-016，其相对误差k为xdpiancha=2.3322e-016.表2-1kpianchaxk1.00002.00001.00000.08710.00860.00010.00000.00000.33330.04550.00450.00000.00000.0000-1.9129-1.9042-1.9042-1.9042-1.9042-1.9042-0.0865-0.00070.0000-0.000006.00000 x3.求曲线与曲线之间的最小垂直距离处的 xf (x)