牛顿迭代法收敛定理

1、f(x)在X0处的泰勒级数展式的前两项做为函数 个线性函数，通过线性表达式替代方程f(x)的近似表达f(x) = 0中的f(x)求得近似解Xn 12(Xn 2/Xn),(n = 0, 1, 2,关于牛顿迭代法的课程设计实验指导非线性方程(或方程组)问题可以描述为求x使得f(x) = 0。在求解非线性方程的方法中，牛顿迭代法是求非线性方程(非线性方程组)数值解的一种重要的方法。牛顿是微积 分创立者之一，微积分理论本质上是立足于对世界的这种认识：很多物理规律在微观上是线性的。近几百年来，这种局部线性化方法取得了辉煌成功，大到行星轨道计算，小到机械部 件设计。牛顿迭代法正是将局部线性化的方法用于求解

2、方程。一、牛顿迭代法及其收敛速度牛顿迭代法又称为牛顿 -拉夫逊方法(Newton-Raphson method)，是一种在实数域和复 数域上通过迭代计算求出非线性方程的数值解方法。方法的基本思路是利用一个根的猜测值X0做初始近似值，使用函数式。由于该表达式是，XI。即将方程f(x) = 0在X0处局部线性化计算出 近似解XI,重复这一过程，将方程f(x) = 0在X1处局部线性化计算出X2,求得近似解X2,。详细叙述如下：假设方程的解X*在X0附近(X0是方程解X*的近似)，函数f(x)在点X0处的局部线化 表达式为f (Xpx f(X。)+(X-X°)f(X0)由此得一次方程f (

3、x°) +(x-x°)f "(x°) =0求解，得f (Xc)Xi讥f (Xg)如图1所示，X1比X0更接近于x*。该方法的几何意义是：用曲线上某点( X0, y0)的切线 代替曲线，以该切线与 x轴的交点(X1, 0)作为曲线与x轴的交点(x*, 0)的近似(所以 牛顿迭代法又称为切线法)。设Xn是方程解X*的近似，迭代格式Xn 1 =Xn - f (Xn)( n = 0, 1, 2,)f (Xn)就是著名的牛顿迭代公式，通过迭代计算实现逐次逼近方程的解。牛顿迭代法的最大优点是收敛速度快，具有二阶收敛。以著名的平方根算法为例，说明二阶收敛速度的意义。例

4、1 已知21.4，求、2等价于求方程f(x) = x2 -2 = 0的解。由于f (x)二2x。应用牛顿迭代法，得迭代计算格式取X0= 1.4为初值，迭代计算 3次的数据列表如下 表1牛顿迭代法数值实验迭代次数近似值15位有效数误差01.4-1.42e-00217.21e-00521.84e-0093-2.22e-016其中，第三栏15位有效数是利用 MATLAB的命令sqrt(2)计算结果。观察表中数据，第一次 迭代数据准确到小数点后四位， 第二次迭代数据准确到小数点后八位， 。二阶收敛速度 可解释为，每迭代一次，近似值的有效数位以二倍速度递增。对于计算任意正数C的平方根，牛顿迭代法计算同样

5、具有快速逼近的性质。二、牛顿迭代法的收敛性牛顿迭代法在使用受条件限制，这个限制就是通常所说的牛顿迭代法的局部收敛性。定理 假设f(x)在x*的某邻域内具有连续的二阶导数，且设f(x*)=o, (x*) = 0,则对充分靠近x*的初始值xo,牛顿迭代法产生的序列 xn收敛于下面例子是牛顿迭代法不收敛的反例。反例说明，牛顿迭代法局部收敛性要求初始点要取得合适，否则导致错误结果。3例2用牛顿迭代法解方程f(x) = x3 -x -3 = 0。分析：利用 MATLAB求多项式零点命令roots(p)，计算得三次方程的三个根如下表表2三次方程的三个根rir2r31.6717-0.8358 - 1.046

6、9i-0.8358 + 1.0469i显然，三次方程有一个实根3。3为了使用牛顿迭代法计算，对于f(x) = x3 -x -3，首先求导数，得(x) = 3x - 1。取X。= 0和X0 = 1取分别用牛顿迭代法计算，得表3不同初始值的迭代计算结果对于迭代初值取算法将陷入死循环。X001X1-3.00002.5000X2-1.96151.9296X3-1.1472 1.7079X4-0.00661.6726X5-3.00041.6717X6-1.96181.6717而迭代初值取xo=1，可以使牛顿迭代法得到收敛。三、特殊代数方程的牛顿迭代法收敛区域将牛顿迭代法用于求解高阶代数方程时，首先回顾一

7、个代数基本定理，即“一个n阶多项式在复数域内有 n个根”。根据牛顿迭代法的局部收敛性质，任意取一个数据做为牛顿迭 代的初值，可能导致迭代不收敛，即使这一个初值可以使迭代法收敛，下一个有趣的问题是“迭代序列将收敛于哪一个根”例3牛顿迭代法的收敛区域问题: 该方程在复平面上三个根分别是，其规律如何？Newt on迭代法可以用于求解复数方程Z3 -1 = 0 ,4 丄 V3.Z3i2 2选择中心位于坐标原点， 边长为4的正方形内的任意点作初始值，进行迭代，定义为第一类，给它们标一种颜色；再把收敛到三个根的初值分为三类， 色。对充分多的初始点进行实验，绘出牛顿迭代法对该方程的收敛域彩色图。Z1= 1

8、, z2将不收敛的点 并分别标上不同颜0-i2-11图3牛顿迭代法收敛区域色图问题分析：记f(z) = z3 -1,则f (z)二3z2，所以牛顿迭代公式为2Zn 1 =Zn -(Zn -1/Zn)/3由于牛顿迭代法的二阶收敛速度，对于一个取定的初值Z0,如果Z0是一个可以导致迭代收敛的初值，则迭代10次已经达到足够精度，故可以取迭代次数为 10。考虑以坐标原点为中 心的正方形区域11 =（X, y）| _2x2, _2冬 y乞 2取步长h=0.02,在区域内取离散网格点Xj = 2 + j 汉 h小一 2+kS，（ j，k =0，1，200）由此可以构造出规则的复数Zk = Xj + i y

9、k, ( j, k =0, X ，200)对于这些点，逐一用牛顿迭代法取初值进行迭代实验，判断是否收敛？如果收敛，到底以该点为初值的迭代序列收敛到哪方程的一个根？为了记录实验结果，构造四个阶数均为201 X 201矩阵：Z0、Z1、Z2、Z3,开始时这四个矩阵都设为全零矩阵。如果以Zk为初值的迭代实验结果是不收敛，则将Z0的第j行第k列的元素改写为1；如果以Zjk为初值的迭代实验结果是收敛到第一个根，则将乙的第j行第k列的元素改写为1 ；如果以Zjk为初值的迭代实验结果是收敛到第二个根，则将Z2的第j行第k列的元素改写为1 ;如果以Zk为初值的迭代实验结果是收敛到第三个根，则将乙的第j行第k列

10、的元素改写为1。首先分析矩阵Zo的数据，由于该矩阵在开始时刻为全零矩阵，而在迭代实验结束后，不收敛的点对应元素被改写为“ 1 ”所以，矩阵的元素只可能是“ 0”或“ 1”根据该矩阵 的全部的非零元素所在的位置可以使用MATLAB的图形绘制命令 spy()或pcolor()等显示出一个特殊的图形。根据 Zo数据绘的图形如下所示图4牛顿迭代法不收敛区域色图导致牛顿迭代法不收敛的初始点所形成的平面点集是一个著名的集合，称为茹莉亚集(为纪念法国女数学家茹莉亚而命名)。为了得到全局的收敛或不收敛情况，需要对四个矩阵进行叠加。如果直接相加将导致一个全“1”矩阵，不可能得出希望的结果。故，对矩阵做如下组合处

11、理，令Z = Zo + 2Z1 + 3Z2 + 4Z3则矩阵Z的元素由“ 1” “2” “3”、“4”这四个元素组成。该矩阵的某一位置上数据为“1 ”说明这一位置上的复数做初值导致牛顿迭代法不收敛；位置上数据为“2”说明这一位置上的复数做初值导致牛顿迭代法收敛到第一个根；位置上数据为“ 3 ”说明这一位置上的复数做初值导致牛顿迭代法收敛到第二个根；位置上数据为“ 4”说明这一位置上的复数做初值导致牛顿迭代法收敛到第三个根。所以该矩阵包含了矩阵区域内离散点集合做为牛顿迭代法收敛实验结果的全部信息。将这一矩阵用MATLAB作图命令pcolor()作用，将绘出图 3所示的收敛区域色图。导致牛顿迭代法

12、收敛到第一个根的初始点所形成的平面点集，可以根据Z1数据绘图形四、关于实验的注记1. MA TLAB相关命令介绍(1)求多项式零点命令roots()该命令用于求多项式P(x) =a1xn+ a2 xn-1+anx+an+1的全部零点。例如z3-1=0的三个零点，只需用命令： roots(1 0 0 -1)，可得ans =-0.5000 + 0.8660i-0.5000 - 0.8660i1.0000(2 )绘伪彩色图命令 pcolor()该命令主要用于绘制矩阵色图，根据矩阵中元素数据的大小不同绘不同颜色。常常与命令shadi ng in terp结合使用效果会更好。在 MATLAB命令窗口中键

13、入 help pcolor，可获得英文帮助信息。2.例题3所用MATLAB程序及注释：X=roots(1,0,0,-1); r1= X(1);r2=X(2);r3=X(3); h=0.02;N=1+4/h; zO(N,N)=O;z 仁z0;z2=z0;z3=z0; t=(-2:h:2)+eps; x,y=meshgrid(t); z=x+y*i;forj=1:Nfor k=1:N p=z(j,k); for n=1:10 p=p-(p-1/pA2)/3;endif abs(p-r1)<0.01z1(j,k)=1;elseif abs(p-r2)<0.01 z2(j,k)=1;els

14、eif abs(p-r3)<0.01 z3(j,k)=1;else z0(j,k)=1;endendendZ=z0+2*z1+3*z2+4*z3; figure(1) pcolor(x,y,Z),shading interp figure(2) pcolor(x,y,z0),shading interp%利用MATLAB命令求三次方程的根%确定网格步长及网格点规模%定义四个大矩阵为全零矩阵%确定网格点坐标%提取迭代初始点%牛顿迭代操作%确定收敛到第一个根的初始点%确定收敛到第二个根的初始点%确定收敛到第三个根的初始点%确定不收敛的初始点%绘牛顿迭代法收敛域%绘牛顿迭代法不收敛域课程设计实

15、验题目1 牛顿迭代法解复方程 z n + 1=0的收敛域问题。 实验目的：=0(n> 3)时收敛域的结构。了解Newton迭代法解复方程 z n + 1z n + 1 = 0 ,例如对z6 + 1 = 0 ,该方程在复平实验原理：Newt on迭代法可以用于求解复数方程 面上六个根分别是Z1li1 ?231.i , zz= i ,2v31Z6 -i2 2选择中心位于坐标原点，边长为 代，将不收敛的初值点归为第一类， 色做图。对充分多的初始点进行实验， 2 牛顿迭代法计算隐函数值实验实验目的：了解隐函数存大定理与牛顿迭代法之间的联系。 实验原理：31 .+ i2 2 ，的正方形(或半径为4

16、的圆)内的任意点作初始值进行迭 再把收敛到六个根的初值归为另外六类，分别以不同颜绘出牛顿迭代法对该方程的收敛域彩色图。隐函数存在定理叙述为：如果f(x, y)及fy (x, y)皆在(xo, yo)附近连续，而且f(xo, yo) = 0, fy(Xo,yo)=O则在(xo, yo)的附近，方程f(x, y) = 0恰有一个连续解 y =y(x)。隐函数存在定理具有局部性，这种局部性与牛顿迭代法的局部收敛性有相通之处。在邻域、(xo，yo) = (xo) x (yo)=(x, y) | x _xo| <、，|y -yo| <、内计算隐函数的值。取xi 、(xo)=x | x-xo|

17、< ，存在yi 、(yo)=y | |y-yo|< .，使得yi =y(xi)满足f(xi, yi) = o。由此导出关于函数值 y的一元非线性方程g(y) = f(xi, y) = o由于f(x, y)及fy(x,y)皆在.(xo, yo)连续，故fy(xi,yj = 0，且y件yo。应用牛顿迭 代法，得迭代计算格式(k+1)(k) Q 、,(k)、/£/、,(k)、y = y-f(xi, y )/fy(xi, y )迭代初值取为：y(o)= yo。由牛顿迭代法的局部收敛性可知，迭代计算可求得隐函数的高精度函数值。将这一过程进行下去可计算出一系列的函数值并制做出函数表。例如对于二元多项式函数 G(x, y) = 3x7 + 2