非线性方程求根（2newton法迭代法的收敛阶）课件.ppt

《非线性方程求根（2newton法迭代法的收敛阶）课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第k步产生的xk有误差对于给定的精度,可估计二分法所需的步数k：二分法迭代法f(x)=0x=g(x)等价变换f(x)的根g(x)的不动点f(x)=0化为等价方程x=g(x)的方式是不唯一的,有的收敛,有的发散.定理考虑方程x=g(x),g(x)C[a,b],若(I)当x[a,b]时，g(x)[a,b]；(II)0L<1使得

2、g’(x)

3、L<1对x[a,b]成立。则任取x0[a,b]，由xk+1=g(xk)得到的序列收敛于g(x)在[a,b]上的唯一不动点。并且有误差估计式：且存在极限k注：定理条件非必要条件，而且定理中的压缩条件不好验证，一

4、般来讲，若知道迭代函数g(x)∈C1『a,b］,并且满足

5、g′(x)

6、≤≤1,对任意的x∈［a,b］,则迭代法收敛。Aitken加速：xyy=xy=g(x)x*x0P(x0,x1)x1x2P(x1,x2)一般地，有：比收敛得略快。Steffensen加速：§4牛顿法原理：将非线性方程线性化——Taylor展开取x0作为初始近似值，将f(x)在x0做一阶Taylor展开:，在x0和x之间。将(x*x0)2看成高阶小量，则有：线性作为第一次近似值重复上述过程Newton迭代公式只要fC1，每一步迭代都有f’(xk)0，而且，则x*就是f的根。牛顿法

7、的几何意义xyx*x0x1x2牛顿法也称为切线法定理（收敛的充分条件）设fC2[a,b]，若(1)f(a)f(b)<0；(2)在整个[a,b]上f”不变号且f’(x)0；(3)选取x0[a,b]使得f(x0)f”(x0)>0；则Newton’sMethod产生的序列{xk}收敛到f(x)在[a,b]的唯一根。有根根唯一产生的序列单调有界，保证收敛。定义设迭代过程收敛于方程的根x*,如果迭代误差当时成立下列渐进关系式：则称该迭代过程是p阶收敛的.特别地，p=1时称为线性收敛，p>1超线性收敛，p=2时称为平方收敛.Q:如何实际确定收敛阶？定理设x*为x=g(x

8、)的不动点，若，p2；，且，则xk+1=g(xk)在内p阶收敛。证明：x*由上式得因此，对于迭代误差，有这表明迭代过程确实是p阶收敛的.定理（局部收敛性）设fC2[a,b]，若x*为f(x)在[a,b]上的根，且f’(x*)0，则存在x*的邻域使得任取初值，Newton’sMethod产生的序列{xk}收敛到x*，且满足至少平方收敛证明：Newton’sMethod事实上是一种特殊的不动点迭代其中，则收敛由Taylor展开：只要f’(x*)0，则令可得结论。在单根附近收敛快注：Newton’sMethod收敛性依赖于x0的选取。x*x0x0x0HW:

9、p.162#10,#14改进与推广重根加速收敛法：Q1:若　　　，Newton’sMethod是否仍收敛？设x*是f的n重根，则：且。因为Newton’sMethod事实上是一种特殊的不动点迭代，其中，则A1:有局部收敛性，但重数n越高，收敛越慢。Q2:如何加速重根的收敛？A2:将求f的重根转化为求另一函数的单根。令　　　　　，则f的重根=的单根。Q3:当x*是f(x)=0的m重根,是否平方收敛？A3:线性收敛下山法/*DescentMethod*/——Newton’sMethod局部微调：原理：若由xk得到的xk+1不能使

10、f

11、减小，则在xk和xk+1

12、之间找一个更好的点，使得。xkxk+1注：=1时就是Newton’sMethod公式。当=1代入效果不好时，将减半计算。弦截法（正割法）：Newton’sMethod一步要计算f和f’，相当于2个函数值，比较费时。现用f的值近似f’，可少算一个函数值。x0x1切线割线切线斜率割线斜率需要2个初值x0和x1。收敛比Newton’sMethod慢，且对初值要求同样高。§6劈因子法/*SplittingMethod*/求多项式的根从f(x)中分离出一个2次因子。即：通过　　　　　　可解出一对共轭复根。思路从一对初值(u,v)出发，则有其中(r,s)取决于u和v

13、，可以看作是(u,v)的函数，即r=r(u,v)，s=s(u,v)。目标：r=r(u*,v*)=0，s=s(u*,v*)=0。将r和s在初值点(u,v)做一阶Taylor展开，并代入(u*,v*)：从中解出，以更新u和v再迭代，直到r和s充分接近0。每步迭代须计算计算r和s：可记为bn1若令，则计算：n2阶多项式n4阶多项式与前一步同理，可导出　　　和　的公式。计算：而前一步得到可见