范文一:牛顿迭代法的收敛条件 实验二迭代法初始值与收敛性
导读:就爱阅读网友为您分享以下“实验二迭代法初始值与收敛性”的资讯,希望对您有所帮助,感谢您对92to.com的支持!
实验二:迭代法、初始值与收敛性
一:实验要求
考虑一个简单的代数方程
x2?x?1?0,
针对上述方程,可以构造多种迭代法,如xn?1?xn?1,xn?1?1?
验,记录各算法的迭代过程。 21,xn?1?xn
1
二:实验要求及实验结果
(1) 取定某个初始值,按如上迭代格式进行计算,它们的收敛性如何,重复选取不同放入初始值,反复实验。请读者自行
设计一种比较形象的记录方式(如何利用Matlab的图形功能),分析三种迭代法的收敛性与初值的选取关系。
(2) 对三个迭代法中的某一个,取不同的初值进行迭代,结果如何,试分析对不同的初值是否有差异,
实验内容:
2?)对xn?1?xn?1进行迭代运算,选取迭代次数n=20;分别选择初值-0.6, 1.6进行实验,并画出迭代结果的趋势图。 编写MATLAB运算程序如下: %迭代法求解
%令x=x -1
2
clear
n=30;
x=-0.5;
x1=x -1;
for i=1:n
end x1=x1 -1; xx(i)=x1;
m=linspace(0,29,n);
plot(m,xx)
title('x=-0.5')
x=-0.6
x=1.6
3
如上图所示,选取初值分别为-0.6、1.6时,结果都是不收敛的。
2分析:g(x)?xn?1,g'(x)?2x,要想在某一邻域上g'(x)?2x?1,则?x?[?1,1]但是g(x)?[?1,1],所以不存在某
个邻域使得该迭代公式收敛。即迭代公式对任何初值都是发散的。
?)对xn?1?1?1进行迭代运算,选取迭代次数n=30;分别选择初值=-0.7, 2.1进行实验,并画出迭代结果的趋势图。 xn
编写MATLAB运算程序如下:
%迭代法求解
%令x=x -1
clear
4
n=20;
x=-0.5;
x1=1+1./x;
for i=1:n
end
m=linspace(0,29,n);
plot(m,xx,'b')
title('x=-0.5')
x=-0.7
x1=1+1./x1; xx(i)=x1; x=2.1
如上图所示,选取初值分别为-0.7、2.1时,结果都是收敛。
5
分析:g(x)?1?1,设 xng(x)?[1.65,??],?x?[1.65,??],g'(x)??1x2在[1.65,??]上有界,且
g'(x)?11g(x)?1?,产生的序列都收敛。同时由则由迭代式对任意初始值x?[1.65,??
]?1,?x?[1.65,
??]0xnx2
1,可以看到,在x0?[??,??]选取初值,在进行n次迭代后,都会存在一个xn?1.65,此时xn相当于是在xng(x)?1?
[1.65,??]范围内的初始值,迭代公式产生的序列收敛。所以初值的选取对数列的收敛性没有影响。
?)对xn?1? n=20;分别选择初值=-0.6,2.1进行实验,并画出迭代结果的趋势图。编写MATLAB运算程序如下:
6
%迭代法求解
%令x=sqrt(1+x)
clear
n=20;
x=-0.5;
x1= sqrt(1.+x);
for i=1:n
end
m=linspace(0,29,n);
plot(m,xx,'b')
title('x=-0.5')
7
x=-0.6
x1= sqrt(1+x1); xx(i)=x1;
如上图所示,选取初值分别为-0.6、2.1时,结果都是收敛。
分析:g(x)?
设 g(x)?[?1,??],?x?[?1,??],g'(x)?
在[?1,??]实数域上有界,
且g'(x)??1,?x?[?1,??]则由迭代式对任意初始值
x0?[?1,??]g(x)?产生的序列都收敛。同时由g(x)?x0?[??,?1]选取初值,对迭代结果所产生的虚数的实部和虚部也是收敛的。如初值选取x=-3,得到20次的迭代结果如下:实部收敛于1.618,虚部收敛于0,
8
9
范文二:牛顿迭代法收敛定理
非线性方程(或方程组)问题可以描述为求 x 使得f(x) = 0。在求解非线性方程的方
法中,牛顿迭代法是求非线性方程(非线性方程组)数值解的一种重要的方法。牛顿是微积
分创立者之一,微积分理论本质上是立足于对世界的这种认识:很多物理规律在微观上是线
性的。近几百年来,这种局部线性化方法取得了辉煌成功,大到行星轨道计算,小到机械部
件设计。牛顿迭代法正是将局部线性化的方法用于求解方程。
一、牛顿迭代法及其收敛速度
牛顿迭代法又称为牛顿-拉夫逊方法(Newton-Raphson method),是一种在实数域和复数域上通过迭代计算求出非线性方程的数值解方法。方法的基本思路是利用一个根的猜测值
x做初始近似值,使用函数f(x)在x处的泰勒级数展式的前两项做为函数f(x)的近似表达00
式。由于该表达式是一个线性函数,通过线性表达式替代方程f(x) = 0中的f(x)求得近似解x。即将方程f(x) = 0在x处局部线性化计算出10 y
近似解x,重复这一过程,将方程f(x) = 0在x11
处局部线性化计算出x,求得近似解x,??。22 *详细叙述如下:假设方程的解x在x附近(x是00 *方程解x的近似),函数f(x)在点x处的局部线化 0
表达式为
f(x)f(x)(xx)f(x) 000 x 由此得一次方程 O x* x x10
f(x)(xx)f(x)0 000
求解,得
图1 牛顿迭代法示意图 f(x)0 xx10f(x)0
*如图1所示,x比x更接近于x。该方法的几何意义是:用曲线上某点(x,y)的切线1000*代替曲线,以该切线与x轴的交点(x,0)作为曲线与x轴的交点(x,0)的近似(所以1*牛顿迭代法又称为切线法)。设x是方程解x的近似,迭代格式 n
f(x)n ( n = 0,1,2,??) x,x,n,1n,f(x)n
就是著名的牛顿迭代公式,通过迭代计算实现逐次逼近方程的解。牛顿迭代法的最大优点是
收敛速度快,具有二阶收敛。以著名的平方根算法为例,说明二阶收敛速度的意义。
21.已知21.42f(x)2x,求等价于求方程f(x) = x – 2 = 0的解。由于。
应用牛顿迭代法,得迭代计算格式
1x(x2/x),(n = 0,1,2,??) n1nn2
取x= 1.4为初值,迭代计算3次的数据列表如下 0
表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
C的平方其中,第三栏15位有效数是利用MATLAB的命令sqrt(2)计算结果。观察表中数据,第一次
根,牛顿迭代法计算同样具有快速逼近的性质。 迭代数据准确到小数点后四位,第二次迭代数据准确到小数点后八位,??。二阶收敛速度
可解释为,每迭代一次,近似值的有效数位以二倍速度递增。对于计算任意正数
二、牛顿迭代法的收敛性
牛顿迭代法在使用受条件限制,这个限制就是通常所说的牛顿迭代法的局部收敛性。
*** 假设f(x)0f(x)在x的某邻域内具有连续的二阶导数,且设f(x)=0,,则
**对充分靠近x的初始值x,牛顿迭代法产生的序列{x}收敛于x。 0n
下面例子是牛顿迭代法不收敛的反例。反例说明,牛顿迭代法局部收敛性要求初始点要
取得合适,否则导致错误结果。
32用牛顿迭代法解方程 f(x) = x – x – 3 = 0。
分析:利用MATLAB求多项式零点命令roots(p),计算得三次方程的三个根如下表
表2 三次方程的三个根
rrr1 2 3
1.6717 -0.8358 - 1.0469i -0.8358 + 1.0469i 显然,三次方程有一个实根r。 13为了使用牛顿迭代法计算,对于 f(x) = x – x – 3 ,首先求导数,得f(x)3x1。
取x = 0和x = 1取分别用牛顿迭代法计算,得 00
表3 不同初始值的迭代计算结果
0 1 x0
-3.0000 2.5000 x1
-1.9615 1.9296 x2
-1.1472 1.7079 x3
-0.0066 1.6726 x4
-3.0004 1.6717 x5
-1.9618 1.6717 x6
?? ?? ??
对于迭代初值取x=0,迭代数列中的第四项又回到初始点x = 0附近,算法将陷入死循环。 00
y
x x x x 2301
x
3y=x – x – 3
图2 牛顿迭代法初值不收敛示意图 而迭代初值取x=1,可以使牛顿迭代法得到收敛。 0
三、特殊代数方程的牛顿迭代法收敛区域
将牛顿迭代法用于求解高阶代数方程时,首先回顾一个代数基本定理,即“一个n阶多项式在复数域内有n个根”。根据牛顿迭代法的局部收敛性质,任意取一个数据做为牛顿迭
代的初值,可能导致迭代不收敛,即使这一个初值可以使迭代法收敛,下一个有趣的问题是
3z – 1 = 0,该方程在复平面上三个根分别是 “迭代序列将收敛于哪一个根”,其规律如何?
3牛顿迭代法的收敛区域问题:Newton迭代法可以用于求解复数方程 1313ziziz,1,, 2312222选择中心位于坐标原点,边长为4的正方形内的任意点作初始值,进行迭代,将不收敛的点
定义为第一类,给它们标一种颜色;再把收敛到三个根的初值分为三类,并分别标上不同颜
色。对充分多的初始点进行实验,绘出牛顿迭代法对该方程的收敛域彩色图。
图3 牛顿迭代法收敛区域色图
问题分析:记
32f(z)3zf(z) = z – 1,则,所以牛顿迭代公式为
2zz(z1/z)/3 n1nnn
由于牛顿迭代法的二阶收敛速度,对于一个取定的初值z,如果z是一个可以导致迭代收00敛的初值,则迭代10次已经达到足够精度,故可以取迭代次数为10。考虑以坐标原点为中心的正方形区域
,{(x,y)|2x2,2y2} 取步长h=0.02,在区域内取离散网格点
x2jhj,( j,k =0,1,?,200) y2khk
由此可以构造出规则的复数
z = x + i y,( j,k =0,1,?,200) jkjk
对于这些点,逐一用牛顿迭代法取初值进行迭代实验,判断是否收敛?如果收敛,到底以该
点为初值的迭代序列收敛到哪方程的一个根?
为了记录实验结果,构造四个阶数均为201×201矩阵:Z、Z、Z、Z,开始时这四0123个矩阵都设为全零矩阵。如果以z为初值的迭代实验结果是不收敛,则将Z的第j行第kjk0
列的元素改写为1;如果以z为初值的迭代实验结果是收敛到第一个根,则将Z的第j行jk1
第k列的元素改写为1;如果以z为初值的迭代实验结果是收敛到第二个根,则将Z的第jk2j行第k列的元素改写为1;如果以z为初值的迭代实验结果是收敛到第三个根,则将Zjk3的第j行第k列的元素改写为1。
首先分析矩阵Z的数据,由于该矩阵在开始时刻为全零矩阵,而在迭代实验结束后,0
不收敛的点对应元素被改写为“1”。所以,矩阵的元素只可能是“0”或“1”,根据该矩阵的全部的非零元素所在的位置可以使用MATLAB的图形绘制命令spy()或pcolor()等显示出一个特殊的图形。根据Z数据绘的图形如下所示 0
图4 牛顿迭代法不收敛区域色图
导致牛顿迭代法不收敛的初始点所形成的平面点集是一个著名的集合,称为茹莉亚集(为纪
念法国女数学家茹莉亚而命名)。
为了得到全局的收敛或不收敛情况,需要对四个矩阵进行叠加。如果直接相加将导致
一个全“1”矩阵,不可能得出希望的结果。故,对矩阵做如下组合处理,令
Z = Z + 2Z + 3Z + 4Z0123
则矩阵Z的元素由“1”、“2”、“3”、“4”这四个元素组成。该矩阵的某一位置上数据为“1”,说明这一位置上的复数做初值导致牛顿迭代法不收敛;位置上数据为“2”,说明这一位置上的复数做初值导致牛顿迭代法收敛到第一个根;位置上数据为“3”,说明这一位置上的复数做初值导致牛顿迭代法收敛到第二个根;位置上数据为“4”,说明这一位置上的复数做初值
导致牛顿迭代法收敛到第三个根。所以该矩阵包含了矩阵区域内离散点集合做为牛顿迭代法
收敛实验结果的全部信息。将这一矩阵用MATLAB作图命令pcolor()作用,将绘出图3所示的收敛区域色图。
导致牛顿迭代法收敛到第一个根的初始点所形成的平面点集,可以根据Z数据绘图形 1
四、关于实验的注记
1.MATLAB相关命令介绍
(1)求多项式零点命令roots()
nn-13该命令用于求多项式P(x) = ax + ax + ? + ax + a的全部零点。例如z – 1 12 nn+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>0.01>
z1(j,k)=1; %确定收敛到第一个根的初始点
elseif abs(p-r2)<0.01>0.01>
z2(j,k)=1; %确定收敛到第二个根的初始点
elseif abs(p-r3)<0.01>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 %绘牛顿迭代法不收敛域
n1.牛顿迭代法解复方程z + 1 = 0的收敛域问题。
实验目的: n了解Newton迭代法解复方程z + 1 = 0(n?3)时收敛域的结构。 实验原理: n6Newton迭代法可以用于求解复数方程z + 1 = 0,例如对 z + 1 = 0,该方程在复平面上六个根分别是
3131zizizi,,, 1232222
3131zizizi,, 5642222
选择中心位于坐标原点,边长为4的正方形内的任意点作初始值进行迭代,将不收敛的初值
点归为第一类,再把收敛到六个根的初值归为另外六类,分别以不同颜色做图。对充分多的
初始点进行实验,绘出牛顿迭代法对该方程的收敛域彩色图。
2.牛顿迭代法计算隐函数值实验
实验目的:
了解隐函数存大定理与牛顿迭代法之间的联系。
实验原理:
隐函数存在定理叙述为:如果f(x,y)f(x,y)及皆在(x,y)附近连续,而且 00y
f(x,y)0f(x,y) = 0, 00y00
则在(x,y)的附近,方程f(x,y) = 0恰有一个连续解y =y(x)。 00
隐函数存在定理具有局部性,这种局部性与牛顿迭代法的局部收敛性有相通之处。在邻
域
,(x,y) =,(x)×,(y)={(x,y) | |x – x| < ,,|y="" –="" y|="">< ,="" }="" 000000内计算隐函数的值。取x?,(x)="{x" |="" |x="" –="" x|="">< ,},存在y?,(y)="{y" |="" |y="" –="" y|="">< ,},使100="" 100="">
得y =y(x)满足f(x,y) = 0。由此导出关于函数值y的一元非线性方程 1111
g(y) = f(x,y) = 0 1
由于f(x,y)f(x,y)0f(x,y)及皆在,(x,y)连续,故,且y?y。应用牛顿迭0010yy11
代法,得迭代计算格式
(k+1) (k) (k) (k)y= y – f(x,y)/f(x,y) 1y1(0)迭代初值取为:y = y。由牛顿迭代法的局部收敛性可知,迭代计算可求得隐函数的高精0
度函数值。将这一过程进行下去可计算出一系列的函数值并制做出函数表。
723例如对于二元多项式函数G(x,y) = 3x + 2y – x + y – 3,方程G(x,y)=0定义了隐函
数y =y(x)。当x=0时,有y=0。应用牛顿迭代法,从x= 0开始,以0.1为步长依次进行到x=4为止。
3.牛顿迭代法计算矩阵近似逆。
实验目的:
了解矩阵近似逆的迭代计算过程。
实验原理:
-1设A 为主对角严格占优矩阵,求A 的牛顿迭代公式为:X = X(2I –AX ),迭代n+1nn
计算的收敛要求为初值满足条件:|| I – A X|| < 1。="" 0="">
实验名称:
姓名(学号):
一、问题叙述
二、问题分析
三、实验程序及注释
四、实验数据结果及分析
五、实验结论
范文三:牛顿迭代法收敛及算法实验
MATLAB 主程序
function [y,f]=newjushou(x)
f=fnq(x); fz=fnq(x)*ddfnq(x)/((dfnq(x))^2+eps);
y=abs(fz);
if (y<>
disp(' 恭喜您!此迭代序列收敛,φ(x)导数值的绝对值y=|dφ(x)/dx|和
方程f(x)=0的函数f(x)值f 如下' )
else
disp(' 请注意观察下面显示的φ(x)的导数值的绝对值y=|dφ(x)/dx|和方程f(x)=0的函数f(x)值' )
end
P=[y,f]';
例 2.6.2 用牛顿切线法的局部收敛性判别方程 ex sin
始值x 0产生的迭代序列是否收敛?
⑴x 0=-1; ⑵x 0=0; ⑶x 0=1; ⑷x 0=2; ⑸ x 0=5.5;⑹x 0=8.
解 在MATLAB 工作窗口输入程序
>> [y,f]=newjushou(-1)
运行后输出结果
请注意观察下面显示的φ(x)的导数值的绝对值y=|dφ(x)/dx|和方程f(x)=0的函数f(x)值
y =
139.5644
f =
4.3096 x =4的近似根时,由下列初
(2)输入程序
>> [y,f]=newjushou(0)
运行后输出结果
请注意观察下面显示的φ(x)的导数值的绝对值y=|dφ(x)/dx|和方程f(x)=0的函数f(x)的值f
y =
8.0000
f =
4
(3)输入程序
>> [y,f]=newjushou(1)
运行后输出结果
恭喜您!此迭代序列收敛, φ(x)导数值的绝对值y=|dφ(x)/dx|和方程f(x)=0的函数f(x)值f 如下
y =
0.3566
f =
1.7126
(4)输入程序:
>> [y,f]=newjushou(2)
运行后输出结果
请注意观察下面显示的φ(x)的导数值的绝对值y=|dφ(x)/dx|和方程f(x)=0的函数f(x)值
y =
1.2593
f =
-2.7188
(5)输入程序
>> [y,f]=newjushou(5.5)
运行后输出结果
请注意观察下面显示的φ(x)的导数值的绝对值y=|dφ(x)/dx|和方程f(x)=0的函数f(x)值
y =
1.0447e+005
f =
176.6400
(6)输入程序
>> [y,f]=newjushou(8)
运行后输出结果
恭喜您!此迭代序列收敛, φ(x)导数值的绝对值y=|dφ(x)/dx|和方程f(x)=0的函数f(x)值f 如下
y =
0.4038
f =
-2.9452e+003
2.6.3 牛顿切线法的MATLAB 程序
牛顿切线法的MATLAB 主程序
现提供名为newtonqx.m 的M 文件:
function
[k,xk,yk,piancha,xdpiancha]=newtonqx(x0,tol,ftol,gxmax)
x(1)=x0;
for i=1: gxmax
x(i+1)=x(i)-fnq(x(i))/(dfnq(x(i))+eps);
piancha=abs(x(i+1)-x(i));
xdpiancha= piancha/( abs(x(i+1))+eps); i=i+1;
xk=x(i);yk=fnq(x(i)); [(i-1) xk yk piancha xdpiancha]
if (abs(yk)<><><>
k=i-1; xk=x(i);[(i-1) xk yk piancha xdpiancha]
return ;
end
end
if i>gxmax
disp(' 请注意:迭代次数超过给定的最大值gxmax 。' )
k=i-1; xk=x(i);[(i-1) xk yk piancha xdpiancha]
return ;
end
[(i-1),xk,yk,piancha,xdpiancha]';
例 2.6.3 用牛顿切线法求方程2x -3x +1=0在x 0=-0. 4和0. 9的近似根,要求精度ε=10.
解
在MATLAB 工作窗口输入程序
>> [k,xk,yk,piancha,xdpiancha]=newtonqx(-0.4,0.001, 0.001,100) 运行后输出初始值x 0=-0. 4的迭代结果. -332
2.6.4 求n c 的方法及其MATLAB 程序 求c 的方法及其MATLAB 主程序
现提供名为kai2fang .m 的M 文件:
function [k,xk,yk,piancha,xdpiancha,P]=kainfang(x0,c,n,tol, gxmax)
x(1)=x0;
for i=1: gxmax
u(i)= (x(i)^n-c)/(n*x(i)^(n-1)); x(i+1)= x(i)-u(i); piancha=abs(x(i+1)-x(i));
xdpiancha=piancha/( abs(x(i+1))+eps);
i=i+1; xk=x(i);yk=fnq(x(i));
[(i-1),xk,yk,piancha,xdpiancha]
if (piancha<><>
k=i-1;xk=x(i); yk=fnq(x(i));
return ; n
end
end
if i>gxmax
disp(' 请注意:迭代次数超过给定的最大值gxmax.' ) k=i-1;xk=x(i); yk=fnq(x(i));
[(i-1),xk,yk,piancha,xdpiancha]
return ;
end
P=[(i-1),xk,yk,piancha,xdpiancha]';
范文四:【doc】 牛顿迭代法收敛速度分析
牛顿迭代法收敛速度分析
第20卷第4期
2005年11月
郑州轻工业学院(自然科学版)
JOURNALOFZHENGZHOUUNIVERSITYOFLIGHTINDUSTRY(Na
turalScience)
V01.20No.4
Nov.20o5
文章编号:1004—1478(2005)04—0100—03
牛顿迭代法收敛速度分析
高建强,薛薇
(天津科技大学电子信息与自动化学院,天津300222)
摘要:根据一阶导数的性质,讨论了在一些相对弱的条件下牛顿迭代法的超线性收敛性,得到了迭
代法的收敛因子.在VisualC++环境下的数值实验表明,近似效果良好.
关键词:Lipschitz条件;Hslder条件;牛顿迭代法;超线性收敛性
中图分类号:0241.7文献标识码:A
AnalysisoftheconvergencerateonNewtoniterationmethod
GAOJian—qiang,XUEWei
(CollegeofEleetr.Infor.andAuto.,TianjinUniv.ofSci.andTech.,Tianjin300222,(~ina)
Abstract:Newtoniterationmethodisproposedaccordingtothecharacterofderivativeoftheequations.ItsSU—
peflinearconvergenceisalsoprovedunderanoppositelyweaklyconditionandtheconvergencefactorare
gotten.Accordingly,somenumericalexperimentsareperformedintheenvironmnetoftheVisualC++andthe
approximationofNewtoniterationmethodisobtained.
Keywords:Lipschitzcondition;H61dercondition;Newtoniterationmethod;supedinearconvergence
O引言
牛顿迭代法是数值计算中求解非线性方程的常
用方法,在工程计算,物理学,力学和经济学等各个
领域有广泛的应用,对它的研究也是数值计算中非
常活跃的一个领域.其基本思想是将非线性方程
f()=0逐步归结为某一线性方程来求解.它的迭
代公式是
XnXn一’2’…?+一l’…
通过逐次逼近,将隐式方程f()=0归结为一
组显式的计算公式.
定义1[】设函数()有不动点,若存在
X0?,使lim()存在,则称迭代法是收敛的.
如果存在的某个邻域R:I一I?艿,对任意
?R,迭代法产生的序列{}?尺且收敛到,
则称迭代法是局部收敛的.
定义2…设迭代法+1:()产生的序列
{}收敛于方程=()的根,若迭代误差为
e=一,当n一..时渐进关系式e/e一C(常
数C?0)成立,则称该迭代过程是P阶收敛的.迭代
过程的收敛速度P是指在接近收敛的过程中,迭代
误差的下降速度.
当P=1时称为线性收敛,P>1时称为超线性
收敛,P=2时称为平方收敛或二次收敛.
定理lI2]设函数厂()满足厂()=0,
,()?咀f()在的邻域内有2阶连续导
收稿日期:2005—04—10
基金项目:天津市高等学校科技发展基金项目(20030514)
作者简介:高建强(1982一),男,河北省邯郸市人,天津科技大学硕士研
究生.主要研究方向:智能控制,非线性控制,计算数学
第4期高建强等:牛顿迭代法收敛速度分析
数,则当初值足够接近于时,由牛顿迭代公式
得到的序列{{至少是2阶收敛的,并且有
.+1一厂()
n’一广L,
当是单根时,牛顿迭代法至少是局部2阶收
敛的.该定理需要研究2阶导数的性质,这有时是很
难的.因此有必要将该定理条件中的”f()在
的邻域内有2阶连续导数”这个很强的限制条件进
行弱化l3].文献[4]将此条件弱化为”2阶导数存
在”,在文献[5]根据f()的性质研究牛顿法收敛
性:的基础上,能否进一步根据1阶导数的性质将条
件弱化,对于牛顿迭代法的应用和发展有积极意义.
1牛顿迭代法在弱条件下的收敛性
在定理1的基础上,通过分析1阶导数的性质
来研究牛顿迭代法在较弱条件下的收敛性.
定义3若存在正常数,J,对任何1,:?[.,
6]有
lF(1)一F(2)l?Lll一2l
则称F()在[0,6]上满足Lipsehitz条件.其中称
为Lipsehitz常数.
将定理1中的条件”.厂()在的邻域内有2阶
连续导数”弱化为”,’()在的邻域内的1阶导数
/()满足Lipsehitz条件”,若仍能保证牛顿迭代法
至少是局部2阶收敛的,便可以有如下结论.
定理2设函数f()在的某邻域0(,
满足条件:1)f()在0(,)内的1阶导数f()
满足Lipsehitz条件,2)当初值为时,由牛顿迭代
公式得到的序列{{使[f()]存在,那么当o
足够接近于时,牛顿迭代法至少是2阶收敛的,
井且有2阶比值收敛因子估计式
证明由迭代公式?和微分中值定理可得
f()
n+一n—j一
[_/()]一{f()(一)一[,()一,()]}:
[f()]一[f()一f(e)](一)
其中,,位于与之间,即
+1一=[f()]?
[,()一,(,)](一)?
另外,由f()在的邻域内满足Lipsehitz条
件可知
l+l—l=l[f()]一?
[f()一f(,)](一)l?
lf()l一l,一,ll一l?
LIf()l一l一l
其中,>0.则当n_’..时,牛顿迭代法至少是2阶
收敛的.
定义4若存在正常数和的某邻域
0(,),使对任何?0(,都有
lF()一F()l?Ll—l
则称F()在邻域0(,上满足中心Lipschitz条
件,其中称为中心Lipschitz常数.
若将定理2中的条件1)改为”f()在的某
邻域0(,内满足中心Lipsehitz条件”,其他条
件不变,则有如下结论.
定理3当初值足够接近于时,牛顿迭
代法至少是2阶收敛的,并且2阶比值收敛因子估
计式为
证明由式?和f()在的某邻域0(,
)内满足中心Lipschitz条件可知
l+l一l:l[/’()]一?
[,()一,(,)](一)l?
l,()I[If()一/()l+
l,(,)一f()1]l一l?
2LJf()J一J一J
其中,L>0.那么当n一?时,牛顿迭代法至少是2
阶收敛的.
定义5若存在正常数,J,使对任何.,?
[.,6]有
lF(1)一F(2)I?Ll1一2l
则称,()在[.,b]上满足I-I~lder条件,其中0<
?1.
定理4设函数厂()在的某邻域0(,
满足条件:1)厂()在的某邻域0(,内的1
阶导数厂()满足H~lder条件,2)当初值为.时,
由牛顿迭代公式得到的序列{}使得[/()]存
在,那么当初值.足够接近于时,牛顿迭代法至
少是(1+)阶收敛的,并且有收敛因子估计式
证明由式?和,()在的某邻域0(,
)内满足HtJlder条件可知
?
l02?郑州轻工业学院(自然科学版)2005芷
I+一I=I[f()]一?
[f()一f(,)](一)I?
,If()I一.I一II一I?
If()I一I一I.
其中,L>0.当一?时,牛顿迭代法至少是(1+)
阶收敛的.
表1数值计算结果
2数值实验3结论
例l设,c={sin’/+2sin,
[?,b]=[一0.5,0.5],则=0,且
c={sin’/一c.s’/+2c.s
f”()=
『12xsin(1/x)一6xcos(1/x)一sin(1/x)一2sinx?O
Io=o
这里,f()?0,f”()存在,但f”()在的
某邻域内不连续.由文献[4]可知,牛顿迭代法至少
是2阶收敛的.
例2设c={::’e一::,n,=
[一0.5,0.5],则=0,且
厂,():{o?5e?oL0.5<0
这里,f()?0,f”()不存在,但是f()在
的某邻域内满足Lipschitz条件.此时可取L=1,
由定理2知,牛顿迭代法至少是2阶收敛的.
侈u3设()={sin’/+2sin,
[?,b]=[一1.0,1.0],则=0,且
c{sin’/一)s’/+2..s二兰
这里,f()=2#0,f”()不存在,f()不满足
Lipschitz条件,但满足中心Lipschitz条件.由定理3
知,牛顿迭代法至少是2阶收敛的.
利用牛顿迭代公式数值求解非线性方程
f()=O的根?[n,b],例题的计算结果及函
数值的偏差If()I见表1.
运用VisualC++编程工具,对上述3个例子进
行模拟,得到了比较理想的结果.
在方程求解问题的应用中,f()的表达式一般
都比较复杂.本文通过理论推导,在计算方法中运用
VisualC++编程工具,实现了用牛顿迭代法解决方
程近似解的问题.在编程中定义的函数,可以根据实
际问题,适当地设定参数的大小,从而有效地解决工
程实践中的一些相关问题,充分发挥牛顿迭代法收
敛速度快的优点.
本文对1阶导函数f()在的某一邻域内
满足Lipschitz条件,中心Lipschitz条件和Htfider条
件的函数进行了理论推导,并对一些例题进行数值
实验.虽然本文仅在一维情况下对牛顿迭代法在多
个相对弱的条件下的收敛性和收敛速度进行了分
析,但其方法和思想可以借助范数的理论推广到一
般的多元向量函数空间l6],这对于讨论非线性方
程组的解法具有一定的启发性.
参考文献:
李庆扬,王能超,易大义.数值分析[M].北京,海德堡:
清华大学出版社,施普林格出版社,2001.
关治.陆金甫.数值计算基础[M].北京:高等教育出版
社,2002.
吴新元.对牛顿迭代法的一个重要修改[J].应用数学
和力学,1999,2o(8):863--866.
郑权.牛顿迭代法的一点注记和改进[J].北方工业大
学,2002,14(3):2l一24.
郑权.牛顿迭代法在弱条件下的二阶收敛性和比值收
敛因子[J].北方工业大学,2003,15(1):26—29.
李庆扬,关治,白峰彬.数值计算原理[M].北京:清华
大学出版社,2000.
蔡大用.数值分析与实验学习辅导[M].北京:清华大
学出版社,2oo1.
华中理工大学数学系.计算方法[M].北京,海德堡:高
等教育出版社,施普林格出版社,1998.
]]]JJ
n乜,!J
范文五:弱L平均条件下非精确牛顿型迭代法的半局部收敛性
弱L平均条件下非精确牛顿型迭代法的半局部收敛性
文章编号:
弱三一平均条件下非精确牛顿型迭代法的半局部收敛性
刘
肖媛
涛,徐秀斌,
浙江师范大学数理与信息工程学院,浙江金华
摘要:主要研究了在弱 一平均条件下非精确牛顿型迭代法在求解非线性算
子方程时的半局部收敛性.这种
弱 平均条件包含了常用的条件作为特殊情形,故所得收敛结果具有一般性. 关键词:非线性算子方程;非精确牛顿型迭代法;半局部收敛;弱?平均条件 中图分类号: 文献标识码:?
, ,
.
增。孵‰毋,胁历帆./
:?
己一
.
沧. :;
? ; ;
一
引 言
令和王,是欧氏空间或一般的空间,是的一个开凸子集,设:?,是一个 可导的非线性算子,
.
求解非线性方程的近似解是一个重要的问题,因为大量的不同类型的实际问
题都可归结为方程
的形式,如微分方程、边界值问题、积分方程等.常常用非精确迭代程序求方
程解的问题,它的一般
表达形式为
石名后;
‘’
戈。。一‰,裴笔当可?田。,是,,?.
式中:初始点%给定;在“中。是一个
的非奇异矩阵;控制序列仇满足?仇?.当
戈。 茗。时,可以得到非精确牛顿型迭代法,其迭代程序为 收文日期:;修订日期:?
作者简介:刘涛一,男,河南固始入,硕士研究生.研究方向:非线性数值逼近 万方数据
浙江师范大学学报自然科学版
戈十?;
石‘’
’茁。。一,戈。。,嵩?叩。,忌,,?.
当戈。’‰时,可以得到简化的非精确牛顿迭代法;当戈。近似于 戈。时,就得到了非精确
牛顿型迭代法.
非精确牛顿迭代法包含了经典的牛顿迭代法心。,对于非精确牛顿法残余序列的选择影响着非精确
牛顿法的收敛性.文献给出了非精确牛顿法的半局部收敛定理,其中残余序列满足:
??黼?叼。;』’戈。一。一。一。?,,。石。?。一。.
此时?叩。叩.文献利用条件在开集曰茁。,鳓上给出了非精确牛顿迭代法的半局
部收敛定理,此时。满足
’。~ ?田。 ’茹。一。 ,?卢.
文献利用条件,在集合。,上给出了非精确牛顿迭代法的半局部收敛定理.文献
利用局部弱.平均条件
’石一’戈一’?,、,石?茗。,,
;
在集合。,?上给出了非精确牛顿迭代法的局部收敛定理.其中:戈戈一戈
一石丁.文献利用弱已.平均条件
????
’菇。一’戈一’并’?,、“,石?。,艿,戈’?戈,占一,
在集合石。,上给出了非精确牛顿迭代法的半局部收敛定理.其中:省一省。;’
彳一算’.
本文主要通过利用弱 一平均条件和控制条件 ’戈。一,.。一厶一,?。 。一戈川研究非精
确牛顿型迭代法的半局部收敛性,所得结果比文献,的相关结论更具有一般性.
引 理
根据本文的需要,首先给出个引理及证明,然后在这些引理的基础上证明迭代方法的半局部
收敛性.
设和,是空间,用算,表示在集合中以戈为中心、以为半径的开球,设卢,叼,,都
是大于零的常数,?,且假设卢,常数满足??./,残余序列满足
。.
在给出收敛定理之前先定义如下个辅助函数:
一
以 卢一 ?【、 一,??;
,
卢一
一配,???
式和式中,为非负非减可积的连续函数.
函数八戈和戈的导函数分别为:
,
厂’一.【 ,??; ,
’一?
三,??.
则由式和式可以得到 一’ ?一’ ,??. 取靠,使得
万方数据
第期 刘涛,等:弱 一平均条件下非精确牛顿型迭代法的半局部收敛性
’
?:。厶耻?,
且记
:广。 ?“.
兰
设厂如式所示,满足等‘ “?,则/在区间,吼上单调递减,在区
间,上单调递增且
.
八卢,“一?卢,爪冗卢 故厂在定义域,尺内恰有个正根,分别记为和”,且有
‘一.
证明由式知
以卢,
一?上,? ??
又由前面给出的条件易得厂’, ,’,故可以得到数以在区间,上单 调递减,在区间。,上单调递增;又因八一?:,故厂在区间,内恰有个正根’和
一,所以有一.引理证毕.
引理设迭代序列
。。“一筹,铲吣’,?.
式中,八, 由式和式定义.设是方程八在区间,阮的一个根,则由式 产生的序列。有
。。, ?,
且。单调递增收敛到,并有
‰。‘?一黠占.
证明由式可得
铲旷黠鲁邓
下证。 .由引理知以一:卢,且,在区间,如上有一正根.又 :?必, ?兰??羔,
?
所以可得妥?吼,且卢占甬?吼.又
八口卢?』: 卢一配,
因此由的单调性可知,卢.
现在假设。?。.由式和式易知’ 。,八。,故有 ,
。卜一黠地
另一方面,由式可以得到
。。咆一筹“一黠,
且函数 一?浩在区间。‖上单调递增,则 万方数据 拄
浙江师范大学学报自然科学版 ‰。轧一篇“一黯“.
所以式得证.序列。单调递增地收敛于一点,记为?,,且也是方程八的一个
根.又由于是方程以在,‘内唯一的一个根,所以,即序列。收敛到’.
最后证明式成立.由式可以得到 ,
‰。等?黠???黠占.
故式成立.引理证毕.
引理假设’戈‘’在开域,’上满足 一互?
石。。戈一
戈’?,、“,
且对于任意??。,,’并。存在,则 ’戈一 龙。?一’ 一戈。一. 证明 由已知可得
“,
。。
’戈一,?【
则由引理和式易得
’算’。? 一’菇一 .
表?五才蕊
故式成立.引理证毕.
引理旧设
一
妒 乱 “?,
其中??,且“在,’上非负递增,则在, 一上关于单调递增. 半局部收敛性定理
根据上面的引理,以下给出非精确牛顿型迭代法的半局部收敛性定理. 定理 假设:?是一阶连续可导的非线性算子,是的开凸子集.若存在初始 点 ,使得’茗。~?,存在,且有:
‰。。一?卢;
,罚’。一’戈一’菇’?,、“,菇,戈’?;
,
’茗一“一“一。?叼戈一髫一。,,,?.
若?吼且?曰‰,‘’,设当,?时,满足如下条件: 可逆;
’‰一戈一’戈??,;戈’??:.
则非精确牛顿型迭代法产生的序列戈。仍在。,内且收敛到方程的解筇’.
此外有
菇一并‘?‘?,,,?;
菇一戈‘?‘一,,,?.
证明 由非精确牛顿型迭代法的迭代式可以得到 。一戈。一戈。一戈。戈。一。,,,,?, 所以
菇。,一石。 。一戈。一。?
戈。一 戈。 ’戈。一’。 ,’戈。一。一。. 万方数据
刘
第期 涛,等:弱.平均条件下非精确牛顿型迭代法的半局部收敛性
下面用数学归纳法证明式和
髫,一?算,一,,,?
成立.
当时,由式有
.
菇?。戈一?卢?,
又对互丑戈,’一,有
一菇 ?一戈 戈? ?’一?一,
即得?召菇。,一。.故当时:式和式成立. 下面假设当凡一时结论成立,即有
?。一;戈。,’一。生矗茹。一,’一。.。一 由。一并。一戈。一算。一一。一可得
戈。一。。一石。一。一石。一。艽。一。一。一。:一。 ’戈。一铼。曲一孙算。一铱。一。
其中:戈?,戈。一。戈。一戈剃;下.所以由式和式及引理有 ’戈。一’,一’菇。一髫。一茗。一
’菇。一算。一。?
’茗。‘。一??
川戈。一?
丛‘川一
?
戈一戈~ 丁? 戈 , 茗
上,。。一。
““一。一”。一戈。一。一“三名。一。一石。“叼脚。搿。一算。一。』
戈 一?‘戈。一并。
:寺。
?
茗。
叼?。茗。一茗。一。
并一并? 叼?一“.?
南“~。一 。一? 。一“
“。”。一。一一“ 。一叼? 。一 。一. 。一。一一“ 。一 叼? 。一 。
一.
所以由引理、引理及式有
。一’。 ’石。。’算。 ’茗。以菇。一。?
并。,一。?
?
二『:::『电?卜“一。。“搿,菇一一“三省?一‰比?髫一茗? 二蒜?:~一 一?一 一??
以。一八。一。一’。一,。一。一。
一黠‰“.
所以,序列戈。是序列,故存在戈使得川.对?川,‘一川,有 一戈。? 。 戈。一菇。?一。。?。‘一。.
因此,石?曰髫。,.说明当时式和式成立.在式中当?时,可得, 即戈是方程的解,从而结论成立.定理证毕.
应用
根据定理,当’菇时,可以给出非精确牛顿迭代法的半局部收敛性定理.此时
优函数
万方数据
转载请注明出处范文大全网 » 牛顿迭代法的收敛条件实验二迭