非线性方程迭代法的一般理论.ppt

*,*,二分法,二分法简述,.,k,a,k,b,k,x,k,f(x,k,),符号,0,1,2,3,4,5,6,1.0,1.25,1.3125,1.3203,1.5,1.375,1.3438,1.3281,1.25,1.375,1.3125,1.3438,1.3281,1.3203,1.3242,+,+,+,二分法优、缺点；用途。,迭代法的一般理论,不动点迭代法,不动点迭代的收敛性,迭代序列的收敛速度,序列收敛加速方法,一种圆周率计算方案,:,初值,:,x,0,=1,(,n=,1,2,3,),迭代格式,:,将一个计算过程反复进行称为迭代,，,迭代法是一类常见常用的计算技术,。,不动点迭代,法,x,2,x,1,x,0,y=x,f,(,x,)=0,迭代格式,:,(,n=,0,1,2,),迭代函数,若存在,x,*,使得,则称,x,*,为不动点,k,x,k,0,1,2,3,4,5,6,7,1.5,1.35721,1.33086,1.32588,1.32494,1.32476,1.32473,1.32472,例,2,方程,x,3,+4,x,2,10=0,在,1,2,上有一个根,将方程变换成另一形式,:,(1),(,n,=0,1,2,),(,n,=0,1,2,),(2),fi=inline(0.5*sqrt(10-x3);,x0=1.5;er=1;k=0;,while er0.00001,x=fi(x0);,er=abs(x-x0);,x0=x;k=k+1;,end,fi=inline(sqrt(10/(4+x);,x0=1.5;er=1;k=0;,while er0.00001,x=fi(x0);,er=abs(x-x0);,x0=x;k=k+1;,end,k,=16,x,0,=1.3652,k,=6,x,0,=1.3652,roots(1,4,0,-10),ans=,-2.6826+0.3583i,-2.6826-0.3583i,1.3652,x,3,+4,x,2,10=0,构造有效的迭代格式,选取合适的迭代初值,对迭代格式进行收敛性分析,不动点迭代,法需要研究的问题,引,理,1,如果,满足条件,:,;,则,在,a,b,有,唯一,的不动点,x,*,.,证,若,或,显然,有不动点,.,设,则有,记,则有,所以,存在,x,*,使得,即,x,*,即为不动点,.,不动点迭代序列的收敛速度,定,理,2,如,果,满足条件,:,;(2),则对任意的,x,0,a,b,迭代格式,产生的序列,x,n,收敛到不动点,x,*,且有,证,(0,L,0,r,0,使得,则称数列,x,n,r,阶收敛,.,特别,:(1),收敛阶,r,=1,时,称为线性收敛,;,(2),收敛阶,r,1,时,称为超收敛,;,(3),收敛阶,r,=2,时,称为平方收敛,。,序列的收敛阶数越高,收敛速度越快。,例,4,方程,x,3,+10,x,-20=0,取,x,0,=1.5,证明迭代法,是线性收敛,证,:,令,f,(,x,)=,x,3,+10,x,20,绘出,y,=,f,(,x,),图形,可知,方程的根,x,*1.5,令,利用,Lagrange,中值定理,有,其中,介于,x,n,和,x,*,之间,.,所以,由此可知,这一序列的收敛阶数为,1,即迭代法是线性收敛,.,显然,在,x,*,附近,定理,3,设,x,*,是,的不动点,且,而,则,p,阶收敛,。,由,Taylor,公式,其中,介于,x,n,和,x,*,之间,。,所以,故迭代法,p,阶收敛,。,数列收敛加速原理,线性收敛数列,Steffensen迭代法,Aitkin,加速收敛序列,x0=1;f=1;n=1;,k=0;error=1;,t=cputime;,while error0.00001,f=-f;n=n+2;,x=x0+f/n;,error=abs(x-x0);,x0=x;k=k+1;,end,cputime-t,k,4*x,例,2.3,数列,收敛于,速度慢,time=0.3900,k=50000,ans=3.1416,迭代加速方法,:,time=0,k=26,ans=3.1416,x1=1;x2=x1-1/3;x3=x2+1/5;,y0=x3;k=3;n=5;,f=1;error=1;,t=cputime;,while error0.00001,y=x3-(x3-x2)2/(x3-2*x2+x1);,error=abs(y-y0);y0=y;k=k+1;,x1=x2;x2=x3;,f=-f;n=n+2;x3=x3+f/n;,end,time=cputime-t,k,4*y,