数值分析实验

1、数值分析实验数值分析实验合肥工业大学计算机学院朱晓玲实验内容n方程求根的数值方法方程求根的数值方法n 插值方法插值方法n数值积分数值积分n线性方程组解法线性方程组解法n常微分方程的数值解法常微分方程的数值解法 方程求根的数值方法方程求根的数值方法n牛顿迭代法n牛顿下山迭代法 插值方法插值方法n拉格朗日插值n牛顿插值 数值积分数值积分n复化辛普生算法n梯形递推算法n龙贝格算法线性方程组解法线性方程组解法n高斯-塞得尔迭代算法n列主元的高斯消去算法常微分方程的数值解法常微分方程的数值解法n改进的欧拉公式n四阶龙格-库塔算法实验一实验一 方程求根的数值方法方程求根的数值方法 n实验目的要求n算法基本

2、思想n算法流程图 n计算实例 实验目的要求实验目的要求n理解牛顿迭代法，牛顿下山迭代法的基本思想n编程实现上述迭代算法n比较算法的差异，领会算法改进的背景和思路算法基本思想算法基本思想算法基本思想-牛顿迭代n对于非线性方程求根，牛顿迭代法是重要的局部收敛方法。n方程无重根时牛顿迭代公式为： 。n当初始点x0在根x*附近时，迭代序列至少平方收敛。n由于 ， 故近似的可以通过判断相邻两点误差 是否小于给定精度e，决定迭代是否结束。n结束时的xk为方程的近似解。 |11|*|1kkkxxLxx|1kkxx)()(1kkkkxfxfxx算法基本思想算法基本思想-牛顿下山法n牛顿下山法是在牛顿迭代中初值

3、选取不当，导致迭代序列发散的情况下提出的。n下山公式 n下山条件|f(xk+1)|f(xk)| n下山实现：公式中 取1，1/2，1/4，1/8.，依次试算直到下山条件满足；如在规定次数内取不到相应 ，则需重新选择初值x0 )()(1kkkkxfxfxx输入x0，e，Nk=0f(x0)=0k=k+1x0=x1|x1-x0|=N结束YNYNNY开始 牛顿算法流程图Ni= i+1|f(x1)|=Mf(x0)=0YYNNNK= 0 k =k+1 x0= x1|x1-x0|=N重新选重新选择择x0YY)()(0001xfxfxx5 . 0*牛顿下山算法流程图计算实例计算实例n用Newton法求方程f(

4、x)=x3-x-1=0在x0=1.3附近的一个根，使其精确到10-5e。分别用1.5和0.6作为初值，输出迭代次数和结果，并进行分析。n对上述问题，用 Newton下山法，0.6作为初值，输出各步下山因子和迭代结果。实验二实验二 插值方法插值方法 n实验目的要求n算法基本思想n算法流程图 n计算实例 实验目的要求实验目的要求n理解拉格朗日插值、牛顿插值的基本思想编程实现上述迭代算法n编程实现算法n比较算法的差异（效率差异和精度差异） 算法基本思想算法基本思想-拉格朗日插值n多项式插值问题：已知n+1个节点（xi,yi）构造多项式函数pn(x),使pn(xi)=yi, pn(x)为插值多项式。n

5、拉格朗日插值多项式是最基本的插值多项式，在数值积分和微分中显得尤其重要。n公式为： 其中n从公式中不难看出：当节点数量增加时，拉格朗日插值多项式的所有工作必须重新开始。 nkkknxlyxp0)()(nkjjjkjkxxxxxl0)(算法基本思想算法基本思想-牛顿插值n牛顿插值多项式是插值多项式的另一种表示形式，具有承袭特点，可克服拉格朗日插值节点增加时的缺点。 n公式：).()(,.,.)(,)()(110100100nnnxxxxxxxxxfxxxxfxfxN,.,10nxxxf011021,.,.,xxxxxfxxxfnnn拉格朗日插值和牛顿插值多项式公式比较算法基本思想算法基本思想-牛

6、顿插值x0f(x0)x1f(x1)fx0,x1x2f(x2)fx1,x2fx0,x1,x2x3f(x3)fx2,x3fx1,x2,x3fx0,x1,x2,x3xkf(xk)fxk,xk+1fxk,xk+1,xk+2fxk,xk+1,xk+2,xk+3算法基本思想算法基本思想-牛顿插值n差商表可用来求差商 n差商表实现：存储采用n*m的二维数组，n表示最后节点的下标，m表示差商的最高阶数A(i,j)表示以xi为最后节点的j阶差商n表结构：A(i,0)= f(xi) n A(i,j) （I=j）n对角线元素为牛顿插值公式系数jiixxjiAjiA) 1, 1() 1,(N输入输入xi，yi,x,

7、Nk= 0 y= 0输出输出yNt =1kNYYy= y+t*ykk=k+1Nkkjtxxxxtjkj, 1, 1, 0*拉格朗日插值算法流程图N输入输入xi，yi, x,NK= 0 y= 0输出输出yt =1kNYy= y+t*A(k,k)k= k+1A(i,0)= yiA(i,j)= j=1,2N;I= j,j+1,NjiixxjiAjiA) 1, 1() 1,(1,.,0*)(kjtxxtj牛顿插值算法流程图牛顿插值算法流程图计算实例计算实例n已知sinx在0.5，0.6，0.7处值如表x0.50.60.7sinx0.479430.564640.64422v分别用一次、二次的拉格朗日插值

8、求sin0.57891的近似值，并比较精度差异v给出上述三点的二阶差商表，用二次牛顿插值算法求sin0.57891的近似值，并和二次的拉格朗日插值结果作比较 实验三实验三 数值积分数值积分 n实验目的要求n算法基本思想n算法流程图 n计算实例 实验目的要求实验目的要求n理解辛普生算法、梯形递推算法和龙贝格算法的基本思想 n编程实现上述积分算法n比较算法的精度差异，并领会改进算法提高精度的过程 算法基本思想算法基本思想-复化辛普生n求定积分 ，用分段线性插值函数作为f(x)的近似，即得复化梯形公式，误差是O(h2) n用分段二次拉格朗日插值插值函数作为f(x)的近似，得复化辛普生公式，误差是O(

9、h4)。n badxxfI)()()()(2(211bfafxfhTnkkn)()()(4)(2(6115 . 011bfafxfxfhSnkknkkn)()()(4)(2(6115 . 01bfafxfxfhSnkknkkn或算法基本思想算法基本思想-变步长梯形公式n精度给定时，上述复化求积公式均需确定步。步长的计算涉及求导往往比较麻烦。n梯形递推公式建立在复化梯形基础上，是步长能自动选取的自适应算法，每递推一次，步长减半，直到符合精度要求。n前后两次的计算结果分别记为： 和 ，递推关系如下： 表示每次步长减半即分段加倍时新增节点，原分点不需重复计算 nTnT2115 . 02)(22nkk

10、nnxfhTT5 . 0kx算法基本思想算法基本思想-龙贝格公式n将T2n和Tn进行线性组合可得复化辛普生公式Sn，将S2n和Sn进行线性组合得复化柯特斯Cn，将C2n和Cn进一步线性组合得龙贝格公式Rn，误差由O(h2)到O(h4)到O(h6)，最后减少到O(h8)n这种将收敛速度缓慢的梯形序列加工成敛速度快的龙贝格序列的方法称龙贝格算法n加工流程如下图 ：T1T2S1T4S2C1T8S4C2R1T16S8C4R2nnnTTS31342nnnSSC15115162nnnCCR63163642v按行优先的顺序展开计算，循环终止条件|R1-R2|ev存储结构可采用一维或二维数组 v图中前三行部分

11、空白数据的处理N输入输入a,b,Nx =x+0.5h s = s+4f(x)x =x+0.5h s =s+2f(x)输出输出sxbYs= h/6*sH= (b-a)/N x= as =f(a)-f(b)N复化辛普生算法流程图复化辛普生算法流程图T2= 0.5T1+0.5h*sT=T1T1= T2 h=0.5hN输入输入a,b,eS= 0 x= a+0.5h输出输出T2S= s+f(x) x=x+hxbYH= b-aT1= 0.5 h(f(a)+f(b)|T-T1|eYN梯形递推算法流程图梯形递推算法流程图N输出输出R2由由梯形递推梯形递推求求T2|R2-R1|eYNS1= S2T1= T2 k

12、=k+1C1= C2 R1=R2k=2k=1k=0YYYNN1223134TTS1221511516SSC1226316364CCR龙贝格算法流程图龙贝格算法流程图Nk= 0计算实例计算实例n用复化辛普生算法n=8计算n用梯形递推算法和龙贝格算法计算 ，并给出精度为10-7e时的二分次数 10sindxxxI10sindxxxI实验四实验四 线性方程组的解法线性方程组的解法 n实验目的要求n算法基本思想n算法流程图 n计算实例 实验目的要求实验目的要求n理解选主元的高斯消去和高斯塞得尔迭代的基本思想n编程实现上述迭代算法n比较算法的差异，领会算法改进的背景和思路 算法基本思想算法基本思想n线性

13、方程组的解法有两类：直接法和迭代法。直接法适合阶数小稠密的系数阵，而迭代法适于大型稀疏的系数阵。n列主元的高斯消去法是最基本的直接法，高斯-塞得尔迭代是一种有效的迭代法 算法基本思想算法基本思想n列主元的高斯消去法包括4大模块：选主元、换行、消元和回代。n列主元即 其中 k=i|d|e=kNYNYNY输出奇输出奇异标志异标志i =i+1返回主程序返回主程序主程序入口主程序入口选主元过程选主元过程e1= 0 i =1Nk =0Y|xi-t|=e1i=N+1NYNYNY输出失败输出失败t= xi输入输入ann,bn,e,Ne1= |xi-t|i =i+1e1ek=Nk= k+1输出输出x1,x2x

14、nNinji ijijixaxab1/)(高斯高斯-塞得尔迭代算法流程图塞得尔迭代算法流程图计算实例计算实例n用列主元消去法解方程组n用高斯-塞得尔迭代解方程组，要求精确到小数点后4位（0.5*10-4e）,给出迭代次数和近似解43531187132321321321xxxxxxxxx3612363311420238321321321xxxxxxxxx实验五实验五 常微分方程的数值解法常微分方程的数值解法 n实验目的要求n算法基本思想n算法流程图 n计算实例 实验目的要求实验目的要求n解改进的欧拉公式、龙格库塔法的基本思想编程实现上述迭代算法n编程实现算法 n比较算法的差异，领会算法改进的背景

15、和思路 算法基本思想算法基本思想n对于常微分方程初值问题y=f(x,y) y(x0)=y0的数值解，即找到一系列离散点（x0,y0）（x1,y1）（x2,y2）（xn,yn）近似满足常微分方程。n用差商代替导数是实现连续问题离散化的有效方法。选取不同的差商和导数可以导出不同公式。n改进欧拉公式可以达到较好的精度，是常用方法之一。而龙格-库塔法则向我们提供获得更高精度算法的思路。算法基本思想算法基本思想-改进的欧拉公式n改进的欧拉公式是二阶方法n包括预测和校正两步：先用欧拉公式预测出 ，再代入梯形公式进行校正n公式为：),(1nnnnyxhfyy),(),(2111nnnnnnyxfyxfhyy

16、1ny算法基本思想算法基本思想-龙格库塔法n四阶（经典）龙格-库塔法：在区间xk,xk+1取四点，并对这四点的斜率进行加权平均作为平均斜率，以使其计算公式的局部截断误差O(h5)n故求解公式： )hK,yf(xK)0.5hK,yf(xK)0.5hK,yf(xK),yf(xK)K2K2K(K6hyy3n1n42n0.5n31n0.5n2nn14321n1n输入输入x0,y0,NX1= x0+h输出输出x1,y1i= i+1X0= x1 y0= y1 h =(b-a)/N i =0i=N结束结束),(0001yxhfyy),(),(2110001yxfyxfhyy改进的欧拉算法流程图改进的欧拉算法

17、流程图NYN输入输入x0,y0,Nx1=x0+h输出输出x1,y1Yi =i+1X0= x1 y0= y1 h =(b-a)/N i= 0i=N结束结束)5 . 05 . 040100000000K2K2K(K6hyy)hKh,yf(xK)0.5hKh,yf(xK)0.5hKh,yf(xK),yf(xK3213423121四阶龙格四阶龙格-库塔算法流程库塔算法流程图图计算实例计算实例n对初值问题 取步长h=0.1，分别用改进的欧拉算法和四阶龙格-库塔算法求其数值解，并与精确解作比较进行误差分析。 1)0(yyy10 X本学期实验具体要求：本学期实验具体要求：必做实验计算实例实验报告 必做实验必做实验n方程求根的牛顿下山迭代法n数值积分的龙贝格算法n求解线性方程组的高斯-塞得尔迭代算法n求解常微分方程的四阶龙格-库塔算法 计算实例计算实例n用 Newton下山法求方程f(x)=x3-x-1=0在x0=1.3附近的一个根，使其精确到10-5e。用0.6作为初值，