数值计算幻灯片.ppt

数值计算课件第1页，共16页，编辑于2022年，星期六构造有效的迭代格式构造有效的迭代格式选取合适的迭代初值选取合适的迭代初值对迭代格式进行收敛性分析对迭代格式进行收敛性分析一种圆周率计算方案一种圆周率计算方案:初值初值:x0=1(n=1,2,3,)迭代格式迭代格式:2/16将将一一个个计计算算过过程程反反复复进进行行称称为为迭迭代代,迭迭代代法法是是一一类常见常用的计算技术类常见常用的计算技术第2页，共16页，编辑于2022年，星期六x2 x1 x0y=xf(x)=0迭代格式迭代格式:(n=0,1,2,)迭代函数迭代函数若存在若存在 x*,使得使得 ,则称则称x*为不动点为不动点6/16第3页，共16页，编辑于2022年，星期六例例 已已知知方方程程x2+x-6=0在在区区间间0,3内内有有一一实实根根，用用简简单单迭迭代代法法求求一一个个实实根根的的近近似似值值，精精度度要要求求为为=10-43/161.x2+x-6=0 x=6-x2，取取初初始始近近似似值值x0=1代代入入其其迭迭代代格格式式xn+1=6-xn2中中，计计算算得得到到的的迭迭代代值值序序列列为为x0=1;x1=5;x2=-19;x3=-3552.x2+x-6=0 x=(6+3x-x2)/4，取取初初始始近近似似值值x0=1代代入入其其迭迭代代格格式式xn+1=(6+3xn-xn2)中中，计计算算得得到到的的迭代值序列为迭代值序列为x0=1;x1=2;x2=2;x3=2第4页，共16页，编辑于2022年，星期六例例2.2 2.2 方方程程 x3+4x2 10=0 在在 1,2 上上有有一一个个根根,将方程变换成另一形式将方程变换成另一形式(1)(n=0,1,2,)(2)(n=0,1,2,)4/16第5页，共16页，编辑于2022年，星期六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;endfi=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;endk=16x0=1.3652k=6x0=1.36525/16第6页，共16页，编辑于2022年，星期六引理引理2.1 如果如果 ,满足条件满足条件:(1);(2)则则 在在 a,b 有唯一的不动点有唯一的不动点 x*证证 若若 或或 ,显然显然 有不动点有不动点设设 ,则有则有 ,记记 则有则有所以所以,存在存在x*,使得使得即即 ,x*即为不动点即为不动点.条件条件(2)是证明唯一性的条件。是证明唯一性的条件。7/16第7页，共16页，编辑于2022年，星期六定理定理2.4 如果如果 ,满足条件满足条件:(1);(2)则对任意的则对任意的 x0 a,b,迭代格式迭代格式 产生的序列产生的序列 xn 收敛到不动点收敛到不动点 x*,且有且有证证8/16第8页，共16页，编辑于2022年，星期六(0L1)所以所以,故迭代格式收敛故迭代格式收敛9/16第9页，共16页，编辑于2022年，星期六不动点迭代产生序列的收敛速度不动点迭代产生序列的收敛速度数列的数列的 r r 阶收敛概念阶收敛概念(局部收敛性局部收敛性|xn-x x*|0,r0 使得使得则称数列则称数列xn r 阶收敛阶收敛.特别特别:(1)收敛阶收敛阶r=1时时,称为线性收敛称为线性收敛;(2)收敛阶收敛阶r1时时,称为超收敛称为超收敛;(3)收敛阶收敛阶r=2 时时,称为平方收敛称为平方收敛序列的收敛阶数序列的收敛阶数r r越高越高,收敛速度越快收敛速度越快10/16第10页，共16页，编辑于2022年，星期六例例2.3 方程方程 x3+10 x-20=0,取取 x0=1.5,证明迭代法证明迭代法是线性收敛是线性收敛证证:令令 f(x)=x3+10 x 20,绘出绘出 y=f(x)图形可知图形可知方程的根方程的根 x*1.5,令令求导数求导数,得得11/16第11页，共16页，编辑于2022年，星期六利用利用Lagrange中值定理中值定理,有有其中其中,介于介于xn和和x*之间之间.所以所以由此可知由此可知,这一序列的收敛阶数为这一序列的收敛阶数为1,即迭代法是线即迭代法是线性收敛性收敛.显然显然,在在x*附近附近12/16第12页，共16页，编辑于2022年，星期六定理定理2.6 设设x*是是 的不动点的不动点,且且而而 则则 p阶收敛阶收敛由由Taylor公式公式其中其中,介于介于xn和和x*之间之间.所以所以故迭代法故迭代法p阶收敛阶收敛.13/16第13页，共16页，编辑于2022年，星期六数列收敛加速原理数列收敛加速原理(Aitken)对于线性收敛数列对于线性收敛数列,有有于是于是整理化简整理化简得加速收敛得加速收敛序列序列15/16第14页，共16页，编辑于2022年，星期六1阶收敛的数列阶收敛的数列xn的加速收敛算法的加速收敛算法s1=1;s2=s1-1/3;s3=s2+1/5;y0=s3;k=3;n=5;f=1;eor=1;while eor0.00005 y=s3-(s2-s3)2/(s3-2*s2+s1);eor=abs(y-y0);y0=y;k=k+1;s1=s2;s2=s3;f=-f;n=n+2;s3=s3+f/n;ends=4*y例例 数列数列 收敛于收敛于 但速度极慢但速度极慢S=3.14151898559528k=1714/16第15页，共16页，编辑于2022年，星期六迭代法迭代法 的的steffensen加速收敛加速收敛校正校正再校正再校正改进改进取初始值取初始值 x0,对对n=0,1,2,计算计算16/16第16页，共16页，编辑于2022年，星期六