《数值分析实验》PPT课件.ppt

《《数值分析实验》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数值分析实验》PPT课件.ppt（56页珍藏版）》请在三一办公上搜索。

1、数值分析实验,合肥工业大学计算机学院朱晓玲,实验内容,方程求根的数值方法 插值方法数值积分线性方程组解法常微分方程的数值解法,方程求根的数值方法,牛顿迭代法牛顿下山迭代法,插值方法,拉格朗日插值牛顿插值,数值积分,复化辛普生算法梯形递推算法龙贝格算法,线性方程组解法,高斯-塞得尔迭代算法列主元的高斯消去算法,常微分方程的数值解法,改进的欧拉公式四阶龙格-库塔算法,实验一 方程求根的数值方法,实验目的要求算法基本思想算法流程图 计算实例,实验目的要求,理解牛顿迭代法，牛顿下山迭代法的基本思想编程实现上述迭代算法比较算法的差异，领会算法改进的背景和思路算法基本思想,算法基本思想-牛顿迭代,对于非线

2、性方程求根，牛顿迭代法是重要的局部收敛方法。方程无重根时牛顿迭代公式为：。当初始点x0在根x*附近时，迭代序列至少平方收敛。由于，故近似的可以通过判断相邻两点误差 是否小于给定精度e，决定迭代是否结束。结束时的xk为方程的近似解。,算法基本思想-牛顿下山法,牛顿下山法是在牛顿迭代中初值选取不当，导致迭代序列发散的情况下提出的。下山公式 下山条件|f(xk+1)|f(xk)|下山实现：公式中 取1，1/2，1/4，1/8.，依次试算直到下山条件满足；如在规定次数内取不到相应，则需重新选择初值x0,输入x0，e，N,k=0,f(x0)=0,k=k+1 x0=x1,|x1-x0|e,输出迭代失败,输

3、出奇异标志,输出x1,k=N,结束,Y,N,Y,N,N,Y,开始,牛顿算法流程图,N,i=i+1,|f(x1)|f(x0)|,输入x0，e，N,M,i=0=1,输出迭代失败,输出奇异标志,输出x1,i=M,f(x0)=0,Y,Y,N,N,N,K=0,k=k+1 x0=x1,|x1-x0|e,Y,N,k=N,重新选择x0,Y,Y,牛顿下山算法流程图,计算实例,用Newton法求方程f(x)=x3-x-1=0在x0=1.3附近的一个根，使其精确到10-5e。分别用1.5和0.6作为初值，输出迭代次数和结果，并进行分析。对上述问题，用 Newton下山法，0.6作为初值，输出各步下山因子和迭代结果。

4、,实验二 插值方法,实验目的要求算法基本思想算法流程图 计算实例,实验目的要求,理解拉格朗日插值、牛顿插值的基本思想编程实现上述迭代算法编程实现算法比较算法的差异（效率差异和精度差异）,算法基本思想-拉格朗日插值,多项式插值问题：已知n+1个节点（xi,yi）构造多项式函数pn(x),使pn(xi)=yi,pn(x)为插值多项式。拉格朗日插值多项式是最基本的插值多项式，在数值积分和微分中显得尤其重要。公式为：其中从公式中不难看出：当节点数量增加时，拉格朗日插值多项式的所有工作必须重新开始。,算法基本思想-牛顿插值,牛顿插值多项式是插值多项式的另一种表示形式，具有承袭特点，可克服拉格朗日插值节点

5、增加时的缺点。公式：,拉格朗日插值和牛顿插值多项式公式比较,算法基本思想-牛顿插值,算法基本思想-牛顿插值,差商表可用来求差商 差商表实现：存储采用n*m的二维数组，n表示最后节点的下标，m表示差商的最高阶数A(i,j)表示以xi为最后节点的j阶差商表结构：A(i,0)=f(xi)A(i,j)（I=j）对角线元素为牛顿插值公式系数,N,输入xi，yi,x,N,k=0 y=0,输出y,N,t=1,kN,Y,Y,y=y+t*yk,k=k+1,拉格朗日插值算法流程图,N,输入xi，yi,x,N,K=0 y=0,输出y,t=1,kN,Y,y=y+t*A(k,k),k=k+1,A(i,0)=yiA(i,

6、j)=j=1,2N;I=j,j+1,N,牛顿插值算法流程图,计算实例,已知sinx在0.5，0.6，0.7处值如表,分别用一次、二次的拉格朗日插值求sin0.57891的近似值，并比较精度差异给出上述三点的二阶差商表，用二次牛顿插值算法求sin0.57891的近似值，并和二次的拉格朗日插值结果作比较,实验三 数值积分,实验目的要求算法基本思想算法流程图 计算实例,实验目的要求,理解辛普生算法、梯形递推算法和龙贝格算法的基本思想 编程实现上述积分算法比较算法的精度差异，并领会改进算法提高精度的过程,算法基本思想-复化辛普生,求定积分，用分段线性插值函数作为f(x)的近似，即得复化梯形公式，误差是

7、O(h2)用分段二次拉格朗日插值插值函数作为f(x)的近似，得复化辛普生公式，误差是O(h4)。,或,算法基本思想-变步长梯形公式,精度给定时，上述复化求积公式均需确定步。步长的计算涉及求导往往比较麻烦。梯形递推公式建立在复化梯形基础上，是步长能自动选取的自适应算法，每递推一次，步长减半，直到符合精度要求。前后两次的计算结果分别记为：和，递推关系如下：表示每次步长减半即分段加倍时新增节点，原分点不需重复计算,算法基本思想-龙贝格公式,将T2n和Tn进行线性组合可得复化辛普生公式Sn，将S2n和Sn进行线性组合得复化柯特斯Cn，将C2n和Cn进一步线性组合得龙贝格公式Rn，误差由O(h2)到O(

8、h4)到O(h6)，最后减少到O(h8)这种将收敛速度缓慢的梯形序列加工成敛速度快的龙贝格序列的方法称龙贝格算法加工流程如下图：,T1,按行优先的顺序展开计算，循环终止条件|R1-R2|e存储结构可采用一维或二维数组 图中前三行部分空白数据的处理,N,输入a,b,N,x=x+0.5h s=s+4f(x)x=x+0.5h s=s+2f(x),输出s,xb,Y,s=h/6*s,H=(b-a)/N x=as=f(a)-f(b),N,复化辛普生算法流程图,T2=0.5T1+0.5h*sT=T1T1=T2 h=0.5h,N,输入a,b,e,S=0 x=a+0.5h,输出T2,S=s+f(x)x=x+h,

9、xb,Y,H=b-aT1=0.5 h(f(a)+f(b),|T-T1|e,Y,N,梯形递推算法流程图,N,输出R2,由梯形递推求T2,|R2-R1|e,Y,N,S1=S2,T1=T2 k=k+1,C1=C2,R1=R2,k=2,k=1,k=0,Y,Y,Y,N,N,龙贝格算法流程图,N,k=0,计算实例,用复化辛普生算法n=8计算用梯形递推算法和龙贝格算法计算，并给出精度为10-7e时的二分次数,实验四 线性方程组的解法,实验目的要求算法基本思想算法流程图 计算实例,实验目的要求,理解选主元的高斯消去和高斯塞得尔迭代的基本思想编程实现上述迭代算法比较算法的差异，领会算法改进的背景和思路,算法基本

10、思想,线性方程组的解法有两类：直接法和迭代法。直接法适合阶数小稠密的系数阵，而迭代法适于大型稀疏的系数阵。列主元的高斯消去法是最基本的直接法，高斯-塞得尔迭代是一种有效的迭代法,算法基本思想,列主元的高斯消去法包括4大模块：选主元、换行、消元和回代。列主元即 其中 k=i=n 选主元目的是为了避免消元过程中小数作除数，误差扩散的情况。消元过程:（i=k+1,n;j=k,.,n）,回代过程：（i=n,1）,算法基本思想-高斯-塞得尔迭代,高斯-塞得尔迭代公式为：，i=1,2,.,n公式特点：一旦求出变元xi的某个新值xi(k+1)，将用新值替代老值xi(k)，并进行剩下计算。故公式可进一步表示为

11、下面动态形式：迭代结果的误差可以由|xi(k+1)-xi(k)|进行控制。,i=n,1,k=k+1,i=k+1,n;j=k,.,n,N,输入a,b,xi,n,输出x1.xn,选主元,k=n,Y,k=1,选主元高斯消去算法流程图,d=0,t=aej aej=akj akj=ts=be be=bk bk=sj=k,n,d=aik e=i,N,i=k+1,i=n+1,Y,d=akk e=k,|aik|d|,e=k,N,Y,N,Y,N,Y,输出奇异标志,i=i+1,返回主程序,主程序入口,选主元过程,e1=0 i=1,N,k=0,Y,|xi-t|=e1,i=N+1,N,Y,N,Y,N,Y,输出失败,t

12、=xi,输入ann,bn,e,N,e1=|xi-t|,i=i+1,e1e,k=N,k=k+1,输出x1,x2xn,N,高斯-塞得尔迭代算法流程图,计算实例,用列主元消去法解方程组用高斯-塞得尔迭代解方程组，要求精确到小数点后4位（0.5*10-4e）,给出迭代次数和近似解,实验五 常微分方程的数值解法,实验目的要求算法基本思想算法流程图 计算实例,实验目的要求,解改进的欧拉公式、龙格库塔法的基本思想编程实现上述迭代算法编程实现算法 比较算法的差异，领会算法改进的背景和思路,算法基本思想,对于常微分方程初值问题y=f(x,y)y(x0)=y0的数值解，即找到一系列离散点（x0,y0）（x1,y1

13、）（x2,y2）（xn,yn）近似满足常微分方程。用差商代替导数是实现连续问题离散化的有效方法。选取不同的差商和导数可以导出不同公式。改进欧拉公式可以达到较好的精度，是常用方法之一。而龙格-库塔法则向我们提供获得更高精度算法的思路。,算法基本思想-改进的欧拉公式,改进的欧拉公式是二阶方法包括预测和校正两步：先用欧拉公式预测出，再代入梯形公式进行校正公式为：,算法基本思想-龙格库塔法,四阶（经典）龙格-库塔法：在区间xk,xk+1取四点，并对这四点的斜率进行加权平均作为平均斜率，以使其计算公式的局部截断误差O(h5)故求解公式：,输入x0,y0,N,X1=x0+h,输出x1,y1,i=i+1X0

14、=x1 y0=y1,h=(b-a)/N i=0,i=N,结束,改进的欧拉算法流程图,N,Y,N,输入x0,y0,N,x1=x0+h,输出x1,y1,Y,i=i+1X0=x1 y0=y1,h=(b-a)/N i=0,i=N,结束,四阶龙格-库塔算法流程图,计算实例,对初值问题 取步长h=0.1，分别用改进的欧拉算法和四阶龙格-库塔算法求其数值解，并与精确解作比较进行误差分析。,本学期实验具体要求：,必做实验计算实例实验报告,必做实验,方程求根的牛顿下山迭代法数值积分的龙贝格算法求解线性方程组的高斯-塞得尔迭代算法求解常微分方程的四阶龙格-库塔算法,计算实例,用 Newton下山法求方程f(x)=x3-x-1=0在x0=1.3附近的一个根，使其精确到10-5e。用0.6作为初值，输出各步下山因子和迭代结果。,用龙贝格算法计算，并给出精度为10-7e时的二分次数,计算实例,用高斯-塞得尔迭代解方程组，要求精确到小数点后4位（0.5*10-4e）,给出所需迭代次数和近似解,计算实例,对初值问题取步长h=0.1，分别用四阶龙格-库塔算法求其数值解，并与精确解作比较进行误差分析,实验报告要求,实验任务算法基本思想算法流程图算法实现关键技术（如数据结构等）计算实例（输入、输出）总结,