《计算方法及实现》由会员分享，可在线阅读，更多相关《计算方法及实现（15页珍藏版）》请在金锄头文库上搜索。
1、浙江工业大学计算方法及实现期末论文计算方法牛顿迭代法摘要迭代法分为精确迭代和近似迭代，而在17世纪提出的牛顿迭代法即属于近似迭代， 是一种近似求解方程的方法，即牛顿拉夫森迭代法。其基本思路是经讲非线性函数 f(x) 线性化，从而将非线性方程f(x)= 0近似的转化为线性方程求解。这里我们就来讨论下 牛顿迭代发从演变到修正的过程，以及在学习和生活中的各种应用，充分的了解它的 功能以及优缺点。关键词：牛顿迭代算法；近似解；改进AbstractIteration iteration is divided into precise and approximate iterative, and rais
2、ed in the 17th century that are approximate Newton iteration iteration is an approximate method of solving equations, namely Newton Raphson iteration method. The basic idea is that by speaking nonlinear function f (x) linear, nonlinear equation thus f (x) = 0 approximated into linear equations. Here
3、 we come to discuss the next Newton iteration made from the process of evolution to fix, as well as learning and life in a variety of applications, a full understanding of its features and advantages and disadvantages.Keywords:Newton iterative algorithm; approximate solution;improvement;引言牛顿拉夫森迭代法是牛
4、顿在17世纪提出的一种在实数域和复数域上近似求解方程 的方法。众所周知，多数方程就不存在求根公式，所以要求精确的根可以说是根本不 可能，那么怎么样才能寻找到合适的方法求出跟就显得很是重要，这时牛顿迭代法就 依据其在方程f(x)=0的単根附近具有平方收敛，而且还可以用来求方程的重根、福根 的优点成为了求解此类方程的重要的方法之一。除此之外，它还具有适用面广，收敛 速度快等优点。牛顿迭代法方法简单，每次都是简单的重复计算，也比较适合编程人员编程，并 且它还可以用增加迭代的次数来弥补自称位数少的不足。在此基础上它对的初值还可 以自己取，即使中间的结果有偶然误差也不会对最后的结果获得造成影响。那什么是
5、牛顿迭代算法呢？下面来讲一下有关于牛顿迭代的原理等一些相关知 识。(一)牛顿迭代法的基本原理1牛顿迭代法原理设已知方程f(x) = 0的近似根x ,则在x附近f(x)可用一阶泰勒多项式00p(x) = f (x ) + f(x )(x - x )近似代替.因此，方程f (x) = 0可近似地表示为p(x) = 00 0 0浙江工业大学用X表示p(x) = 0的根,它与f (x) = 0的根差异不大文献1.设 f(x )丰 0,由于 x 满足 f (x ) + f(x )(x x ) = 0,解得0 1 0f (x )0 f (x )0重复这一过程，得到迭代格式f(x )n - f(x )n这就
6、是著名的牛顿迭代公式，它相应的不动点方程为2. 牛顿迭代法的几何解析牛顿迭代法也称为牛顿切线法，这是由于f (x)的线性化近似函数1 (x)二f (x0)+广(x0)(x x0)是曲线y二f (x)过点(x0,f (x0)的切线而得名的，求f (x)的零点 代之以求1(x)的零点，即切线1(x)与x轴交点的横坐标，如右图所示，这就是牛顿切线 法的几何解释。实际上，牛顿迭代法也可以从几何意义上推出。利用牛顿迭代公式，由xk得到xk+1，从几何图形上看，就是过点(xk, f(xk)作函数f(x)的切线1k，切线1k与x轴的交点就是xk+1，所以有 也能得出牛顿迭代公式：xk+1f (x )kf(x
7、 ) Ok of (x )kx 一 xkk+1整理后3牛顿迭代法的收敛性计算可得g(x)二f (x)f(x)，设x*是f (x) = 0的单根，有f (x*)二 0,f(x*)丰 0,则 f( x)2g(x *)=-fr=0，故在x*附近，有|g(x)| 1 .根据不动点原理知牛顿迭代法收敛.4牛顿迭代法的收敛速度浙江工业大学计算方法及实现期末论文定理(牛顿法收敛定理)设f (x)在区间a,b上有二阶连续导数,且满足f (a)f (b) 0, f(x)在a,b上不变号，f(x)在a,b上不等于 0,令m minf (x)|, M maxf(x)|,axbaxba,b，牛顿迭代格式收敛于f (x
8、) = 0在a,b中的唯一实根x*,并且:2M2m-Mq 叫 q m 1.M |x - x * x - xn2m i nn-1n2f (x ) - f (x) 为避免牛顿迭代法中导数的计算，文献2、7、8可用平均变化率：xn-x0来近似代替广()，于是得到如下迭代公式：f (x )nf (x ) - f (x )nx x - n+1n是一个固定lim _ x f (x ) - x f (x )0f (x ) f (x)n0称为单点弦截法。单点弦截法具有明显的几何意义， 它是用联结点A( x0，y0 )与点B( xn，yn )的直线，代 替曲线求取与横轴交点作为近似值+1的方法，以后 再过(x0
9、，y0 )与(J + 1，打+ 1 )两点，作直线求取与横 轴的交点作为 + 2，等等。其中(x0，y0 ) 点，称为不动点，另一点则不断更换，故名单点弦截 法。可以证明，单点弦截法具有收敛的阶r=l,即具 有线性收敛速度。2双点弦截法若把单点弦截法中的不动点(x0，y0 )改为变动点(J-，yn-1 )，则得到下面的双点 弦截法的迭代公式：f (x )() x f (x ) - x f (x )n+1 n f (x ) - f (x ) n n-1f (x ) - f (x )nn-1nn-1n+1 - x* -,牛顿迭代法为2阶收敛. n* (x - x*)22f(x*)n5.迭代法的变形
10、一弦截法1单点弦截法用弦截法求根的近似值，在几何上相当于过点(xk1, f(xk1),和点(xk, f(xk) 作弦，然后用弦与x轴的交点的横坐标xk 1作为X*的新的近似值。由于在双点弦截法中，构造的迭代公式在计算新的近似值Xk 1时，不仅 用到点Xk上的函数值f(Xk),而且还用到点Xk 1及其 函数值，这就有可能提高迭代法的收敛速度。与牛顿法一样，如果函数y f (x)在其根x*附近 具有直到二阶的连续导数，且f(x) ,则弦截法具 有局部收敛性，即当初始近似值充分接近于x*时， 按双点弦截法迭代公式得到的迭代序列收敛于根x*。可以证明弦截法具有超线性收速度，且收敛阶数为P=1.618。
11、双点弦截法迭代公式与前面介绍的单点迭代法有明显的不同，就是在计算Xn 1时要用到前两步的计算结果 Xn、Xn1,所以在使用迭代公式前，必须先给出两个初始值X、X1,因此，这种迭代法 也称两步法，而单点迭代法称为一步法。(二)牛顿迭代的修正随着算法的逐步发展以及人们对算法研究的更加的透彻，并且伴随着算法在人们 生产、生活和学习各个领域的中运用范围的扩大，使得牛顿迭代法在演变中逐步的得 到修正，使得其功能更加的完备，计算的结果更加的精细和准确，更好的为人们的生 产和生活服务。研究人员逐步利用牛顿迭代法和微分中值定理文献3、4、5、7 “中值点”的渐 进性，提出了多点迭代：f(x )nf(xn(1r
12、) f(x )f (x )n一种修正的 New ton Raphsn 算法给出了牛顿(New ton-Rapfson)算法的一种修正的形式，并证明了当r ；时修正的 牛顿(Newton-Rapfson)算法是二阶收敛的，当参数r ：时是三阶收敛时，数值实验得 出结果，与经典牛顿迭代法相比，该修正牛顿(New to n-Rapfson)算法具有一定的优势.众所周知的，数值求解非线性方程f(x) 的根的方法很多经典的牛顿迭代法是非线性方程组求根的一个基本的方法，它二次收敛到单根，线性收敛到重根牛顿法因收敛 速度快而得到广泛应用，也倍受学者的重视，近年来很多文献中提出各种改进的牛顿 方法文献9中利用
13、Newton-Rapfson迭代法和微分中值定理“中值点”的渐进性， 提出的一种多点迭代的算法.设 f (x) 满足下述条件：f (x) e cg-a + (b a)附近，并随区间变小而趋于其渐近的位置.图所示的迭代算法构造图本 方案基于上述考虑，给出一种通过迭代点而选取另一个点，利用两个点进行迭代求近 似根的新方法.这种方法虽然在迭代中又只利用了一个其它的点，但其计算精度却相当 的高，它的某一种特殊情形恰是通常的 Newton-Rapfson 迭代算法.为了更加直观起见， 我们通过几何直观图来构造这种迭代算法设f (x)满足条件(A)，当选定初值 la,b, f (a)f (b) 0)，0如
14、图所示，作交点的切线交x轴于也_光切1 图 2g - a + (b a).也就是说，在区间(a,b)不甚大的时候，中值点g 一定在其渐近的位置AQ 线段的斜率为：f(x0)由微分中值定理得知存在鹉 十得:0f( Xo)二 f( Xo)-f(x0)V*Xof(Xo)八Xo）丿，因此，我们取数（1 Ar 4討，在点P x (1 r) o(, f Xo (1r)f丄II作切线PC，图中AD平行于PC.即用点P 八xo）丿丿的导数f o -（1 “問）取代点A的导数，而继续用点A的迭代格式得到的点D的坐标f (x )-7f x (1 r)off,0丿重复上述过程，得到多点迭代公式：k+1f x - (1 - r)kf ( x )kf ( X )八xk)丿其中 x e la,bl， k = 1,2,k浙江工业大学面我们对上述事实，从理论上加以严格的证明.定理 设f (x)满
