数值分析4.doc

关于牛顿迭代法的课程设计实验指导

非线性方程（或方程组）问题可以描述为求 x 使得f(x) = 0。在求解非线性方程的方法中，牛顿迭代法是求非线性方程（非线性方程组）数值解的一种重要的方法。牛顿是微积分创立者之一，微积分理论本质上是立足于对世界的这种认识：很多物理规律在微观上是线性的。近几百年来，这种局部线性化方法取得了辉煌成功，大到行星轨道计算，小到机械部件设计。牛顿迭代法正是将局部线性化的方法用于求解方程。
一、牛顿迭代法及其收敛速度
牛顿迭代法又称为牛顿-拉夫逊方法（Newton-Raphson method），是一种在实数域和复数域上通过迭代计算求出非线性方程的数值解方法。方法的基本思路是利用一个根的猜测值x0做初始近似值，使用函数f(x)在x0处的泰勒级数展式的前两项做为函数f(x)的近似表达式。由于该表达式是一个线性函数，通过线性表达式替代方程f(x) = 0中的f(x)求得近似解 y

x
O x* x1 x0
x1。即将方程f(x) = 0在x0处局部线性化计算出近似解x1，重复这一过程，将方程f(x) = 0在x1处局部线性化计算出x2，求得近似解x2，……。详细叙述如下：假设方程的解x*在x0附近（x0是方程解x*的近似），函数f(x)在点x0处的局部线化表达式为

由此得一次方程
图1 牛顿迭代法示意图

求解，得

如图1所示，x1比x0更接近于x*。该方法的几何意义是：用曲线上某点（x0，y0）的切线代替曲线，以该切线与x轴的交点（x1，0）作为曲线与x轴的交点（x*，0）的近似（所以牛顿迭代法又称为切线法）。设xn是方程解x*的近似，迭代格式
( n = 0，1，2，……)
就是著名的牛顿迭代公式，通过迭代计算实现逐次逼近方程的解。牛顿迭代法的最大优点是收敛速度快，具有二阶收敛。以著名的平方根算法为例，说明二阶收敛速度的意义。
例1．已知，求等价于求方程f(x) = x2 – 2 = 0的解。由于。应用牛顿迭代法，得迭代计算格式
，（n = 0，1，2，……）
取x0= 1.4为初值，迭代计算3次的数据列表如下
表1 牛顿迭代法数值实验
迭代次数
近似值
15位有效数
误差
0
1.4
1.41421356237310
-1.42e-002
1
1.41428571428571
1.41421356237310
7.21e-005
2
1.41421356421356
1.41421356237310
1.84e-009
3
1.41421356237309
1.41421356237310
-2.22e-016
其中，第三栏15位有效数是利用MATLAB的命令sqrt(2)计算结果。观察表中数据，第一次迭代数据准确到小数点后四位，第二次迭代数据准确到小数点后八位，……。二阶收敛速度可解释为，每迭代一次，近似值的有效数位以二倍速度递增。对于计算任意正数C的平方根，牛顿迭代法计算同样具有快速逼近的性质。
二、牛顿迭代法的收敛性
牛顿迭代法在使用受条件限制，这个限制就是通常所说的牛顿迭代法的局部收敛性。
定理 假设f(x)在x*的某邻域内具有连续的二阶导数，且设f(x*)=0，，则对充分靠近x*的初始值x0，牛顿迭代法产生的序列{xn}收敛于x*。
下面例子是牛顿迭代法不收敛的反例。反例说明，牛顿迭代法局部收敛性要求初始点要取得合适，否则导致错误结果。
例2用牛顿迭代法解方程 f(x) = x3 – x – 3 = 0。
分析：利用MATLAB求多项式零点命令roots(p)，计算得三次方程的三个根如下表
表2 三次方程的三个根
r1
r2
r3
1.6717
-0.8358 - 1.0469i
-0.8358 + 1.0469i
显然，三次方程有一个实根r1。
为了使用牛顿迭代法计算，对于 f(x) = x3 – x – 3 ，首先求导数，得。取x0 = 0和x0 = 1取分别用牛顿迭代法计算，得
表3 不同初始值的迭代计算结果
x0
0
1
x1
-3.0000
2.5000
x2
-1.9615
1.9296
x3
-1.1472
1.7079
x4
-0.0066
1.6726
x5
-3.0004
1.6717
x6
-1.9618
1.6717
……
……
……
对于迭代初值取x0=0，迭代数列中的第四项又回到初始点x0 = 0附近，算法将陷入死循环。

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

图3 牛顿迭代法收敛区域色图
问题分析：记f(z) = z3 – 1，则，所以牛顿迭代公式为

由于牛顿迭代法的二阶收敛速度，对于一个取定的初值z0，如果z0是一个可以导致迭代收敛的初值，则迭代10次已经达到足够精度，故可以取迭代次数为10。考虑以坐标原点为中心的正方形区域

取步长h=0.02，在区域内取离散网格点
，( j，k =0，1，…，200)
由此可以构造出规则的复数
zjk = xj + i yk，( j，k =0，1，…，200)
对于这些点，逐一用牛顿迭代法取初值进行迭代实验，判断是否收敛？如果收敛，到底以该点为初值的迭代序列收敛到哪方程的一个根？
为了记录实验结果，构造四个阶数均为201×201矩阵：Z0、Z1、Z2、Z3，开始时这四个矩阵都设为全零矩阵。如果以zjk为初值的迭代实验结果是不收敛，则将Z0的第j行第k列的元素改写为1；如果以zjk为初值的迭代实验结果是收敛到第一个根，则将Z1的第j行第k列的元素改写为1；如果以zjk为初值的迭代实验结果是收敛到第二个根，则将Z2的第j行第k列的元素改写为1；如果以zjk为初值的迭代实验结果是收敛到第三个根，则将Z3的第j行第k列的元素改写为1。
首先分析矩阵Z0的数据，由于该矩阵在开始时刻为全零矩阵，而在迭代实验结束后，不收敛的点对应元素被改写为“1”。所以，矩阵的元素只可能是“0”或“1”，根据该矩阵的全部的非零元素所在的位置可以使用MATLAB的图形绘制命令spy)或pcolor()等显示出一个特殊的图形。根据Z0数据绘的图形如下所示

图4 牛顿迭代法不收敛区域色图
导致牛顿迭代法不收敛的初始点所形成的平面点集是一个著名的集合，称为茹莉亚集（为纪念法国女数学家茹莉亚而命名）。
为了得到全局的收敛或不收敛情况，需要对四个矩阵进行叠加。如果直接相加将导致一个全“1”矩阵，不可能得出希望的结果。故，对矩阵做如下组合处理，令
Z = Z0 + 2Z1 + 3Z2 + 4Z3
则矩阵Z的元素由“1”、“2”、“3”、“4”这四个元素组成。该矩阵的某一位置上数据为“1”，说明这一位置上的复数做初值导致牛顿迭代法不收敛；位置上数据为“2”，说明这一位置上的复数做初值导致牛顿迭代法收敛到第一个根；位置上数据为“3”，说明这一位置上的复数做初值导致牛顿迭代法收敛到第二个根；位置上数据为“4”，说明这一位置上的复数做初值导致牛顿迭代法收敛到第三个根。所以该矩阵包含了矩阵区域内离散点集合做为牛顿迭代法收敛实验结果的全部信息。将这一矩阵用MATLAB作图命令pcolor()作用，将绘出图3所示的收敛区域色图。
导致牛顿迭代法收敛到第一个根的初始点所形成的平面点集，可以根据Z1数据绘图形

四、关于实验的注记
1．MATLAB相关命令介绍
（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.8660i
1.0000
（2）绘伪彩色图命令pcolor()
该命令主要用于绘制矩阵色图，根据矩阵中元素数据的大小不同绘不同颜色。常常与命令shading interp结合使用效果会更好。
在 MATLAB命令窗口中键入help pcolor，可获得英文帮助信息。
2． 例题3所用MATLAB程序及注释：
X=roots([1,0,0,-1]); %利用MATLAB命令求三次方程的根
r1=X(1);r2=X(2);r3=X(3);
h=0.02;N=1+4/h; %确定网格步长及网格点规模
z0(N,N)=0;z1=z0;z2=z0;z3=z0; %定义四个大矩阵为全零矩阵
t=(-2:h:2)+eps;
[x,y]=meshgrid(t); %确定网格点坐标
z=x+y*i;
for j=1:N
for k=1:N
p=z(j,k); %提取迭代初始点
for n=1:10
p=p-(p-1/p^2)/3; %牛顿迭代操作
end
if abs(p-r1)<0.01
z1(j,k)=1; %确定收敛到第一个根的初始点
elseif abs(p-r2)<0.01
z2(j,k)=1; %确定收敛到第二个根的初始点
elseif abs(p-r3)<0.01
z3(j,k)=1; %确定收敛到第三个根的初始点
else
z0(j,k)=1; %确定不收敛的初始点
end
end
end
Z=z0+2*z1+3*z2+4*z3;
figure(1)
pcolor(x,y,Z),shading interp %绘牛顿迭代法收敛域
figure(2)
pcolor(x,y,z0),shading interp %绘牛顿迭代法不收敛域

课程设计实验题目
1．牛顿迭代法解复方程z n + 1 = 0的收敛域问题。
实验目的：
了解Newton迭代法解复方程z n + 1 = 0(n≥3)时收敛域的结构。
实验原理：
Newton迭代法可以用于求解复数方程z n + 1 = 0，例如对 z6 + 1 = 0，该方程在复平面上六个根分别是
，，，
，，
选择中心位于坐标原点，边长为4的正方形（或半径为4的圆）内的任意点作初始值进行迭代，将不收敛的初值点归为第一类，再把收敛到六个根的初值归为另外六类，分别以不同颜色做图。对充分多的初始点进行实验，绘出牛顿迭代法对该方程的收敛域彩色图。
2．牛顿迭代法计算隐函数值实验
实验目的：
了解隐函数存大定理与牛顿迭代法之间的联系。
实验原理：
隐函数存在定理叙述为：如果f(x，y)及皆在（x0，y0）附近连续，而且
f(x0，y0) = 0，
则在（x0，y0）的附近，方程f(x，y) = 0恰有一个连续解y =y(x)。
隐函数存在定理具有局部性，这种局部性与牛顿迭代法的局部收敛性有相通之处。在邻域
d(x0，y0) =d(x0)×d(y0)={(x，y) | |x – x0| < d，|y – y0| < d }
内计算隐函数的值。取x1∈d(x0)={x | |x – x0| < d }，存在y1∈d(y0)={y | |y – y0| < d }，使得y1 =y(x1)满足f(x1，y1) = 0。由此导出关于函数值y的一元非线性方程
g(y) = f(x1，y) = 0
由于f(x，y)及皆在d(x0，y0)连续，故，且y1≈y0。应用牛顿迭代法，得迭代计算格式
y (k+1)= y (k) – f(x1，y (k) )/fy(x1，y (k))
迭代初值取为：y(0) = y0。由牛顿迭代法的局部收敛性可知，迭代计算可求得隐函数的高精度函数值。将这一过程进行下去可计算出一系列的函数值并制做出函数表。
例如对于二元多项式函数G(x，y) = 3x7 + 2y2 – x3 + y – 3，方程G(x，y)=0定义了隐函数y =y(x)。当x=0时，有y=0。应用牛顿迭代法，从x= 0开始，以0.1为步长依次进行到x=4为止。
3．牛顿迭代法计算矩阵近似逆。
实验目的：
了解矩阵近似逆的迭代计算过程。
实验原理：
设A 为主对角严格占优矩阵，求A-1 的牛顿迭代公式为：Xn+1 = Xn(2I –AXn )，迭代计算的收敛要求为初值满足条件：|| I – A X0 || < 1。

附：牛顿迭代法课程设计实验报告格式
实验名称：
姓名（学号）：
一、 问题叙述
二、 问题分析
三、 实验程序及注释
四、 实验数据结果及分析