现代数值计算方法公式总结.doc

现代数值计算方法公式一、 插值法1.拉格朗日（Lagrange）插值法a)两点一次：L1x=x-x1x0-x1y0+x-x0x1-x0y1R1x=fx-L1x=f2!(x-x0)(x-x1) (x0x1)b)三点二次：L2x=x-x1x-x2x0-x1x0-x2y0+x-x0x-x2x1-x0x1-x2y1+x-x0x-x1x2-x0x2-x1y2R2x=fx-L2x=f33!(x-x0)(x-x1)(x-x2) (x0x2)2.牛顿（Newton）插值a)n次牛顿法多项式：Nnx=fx0+fx0,x1x-x0+fx0,x1,xnx-x0(x-xn-1)Rnx=fx-Nnx=fn+1n+1!n+1x (x0xn)其中n+1x=x-x0x-x1(x-xn-1)XKF(XK)一阶差商二阶差商三阶差商四阶差商X0f(x0)fx0,x1fx1,x2fx2,x3fx3,x4fx0,x1,x2,x3fx1,x2,x3,x4X1f(x1)fx0,x1,x2X2f(x2)fx1,x2,x3fx0,x1,x2,x3,x4X3f(x3)fx2,x3,x4X4f(x4)fx0,x1=fx1-fx0x1-x0fx0,x1,x2=fx1,x2-fx0,x1x2-x0b)向前差分：Nnx0+th=y0+ty0+tt-1t-2(t-n+1)n!ny0Rnx0+th=tt-1t-2t-nn+1!hn+1fn+1 (x0xn)XKYKYI2YI3YI4YIX0y0y0y1y2y33y03y1X1y12y0X2y22y14y0X3y32y2X4y4yi=YI+1-YI2yi=YI+1-YI下减上c)向后差分：Nnxn+th=yn+tyn+tt+1(t+n-1)n!nynRnxn+th=tt+1t+2t+nn+1!hn+1fn+1 (x0xn)XKYKYI2YI3YI4YIX4y4y4y3y2y13y43y3X3y32y4X2y22y34y4X1y12y2X0y0yi=yi-yi-12yi=yi-yi-1上减下3.三次埃米尔特（Hermite）插值XX0X1YY0Y0YM0M1H3X=A0XY0+A1XY1+0XM0+1(X)M1A0X=(1+2X-X0X1-X0)(X-X1X0-X1)2A1X=(1+2X-X1X0-X1)(X-X0X1-X0)20X=(X-X0)(X-X1X0-X1)21X=(X-X1)(X-X0X1-X0)2R3X=F44!(X-X0)2(X-X1)2 (x0x1)二、 拟合曲线（最小二乘）x=a0+a1x+a2x2Sa0,a1,a2=i=1nxi-yi2=i=1n(a0+a1xi+a2xi2)-yi2Sa0=0Sa1=0Sa2=0三、 数值积分1. 牛顿-柯特思（Newton-Cotes）公式梯形求积公式（2节点）IT1=b-a2fa-f(b)RT1=-b-a312f()复化梯形求积公式Ih2fa+2k=1n-1fxk+f(b)TnRTn=-b-a12fh2=O(h2)辛普生求积公式（3节点）IS1=b-a6fa+4fa+b2+fbRS1=-b-a52880f4()复化辛普生求积公式Ih6fa+4k=0n-1fxk+12+2k=1n-1fxk+f(b)RSn=-b-a2880h4f4=O(h4)2. 高斯（Gauss）公式高斯-勒让德求积公式1. 先用勒让德公式求解xiLnx=12nn!dndxn(x2-1)n2. 利用“高斯积分公式具有2n+1次代数精度”将xi带入求Ai3. 将xi、Ai带入公式求取积分、并计算误差。-11fxi=0nAifxiRnf=22n+3n+1!42n+32n+2!3f2n+2()普通积分化标准形式：I=abfxdx积分区间a,b变换x=b-a2t-a+b2abfxdx=b-a2-11f(b-a2t+a+b2)dt3. 代数精度若求积公式对f(x)=1,x,x2,xm时精确成立，而对f(x)=xm+1时不成立，则称此求积公式具有m次代数精确度四、 解线性代数方程组的直接方法三角形分解法求解Ax=b，先将A分解为A=LU，则原式变为Ux=y，那么问题就变为了求解Ly=bUx=y五、 解线性代数方程的迭代法1. 范数向量范数定义：设 xRn(or Cn) 其中R为实数域、C为复数域，若某实值函数N(x)|x|满足条件1） 非负性|x|0，|x|=0当且仅当x=0成立2） 其次行ax=a |x|3） 三角不等式x+yx+|y|称N(x)|x|为Rn(or Cn)域上的一个向量范数常见范数：|x|=max1in|xi|x|1=i=1n|xi|x|2=i=1n|xi|21/2矩阵范数定义：设 ARnn(or Cnn) 其中R为实数域、C为复数域，若某实值函数N(A)|A|满足条件1） 非负性|A|0，|A|=0当且仅当A=0成立2） 其次行aA=a |A|3） 三角不等式A+BA+|B|4） 乘积性质ABA B称N(A)|A|为Rnn(or Cnn)域上的一个矩阵范数常见范数：|A|=max1inj=1naij(行范数)|A|1=max1jni=1naij(列范数)|A|2=1,1为ATA的最大按模特征值|A|F=i,j=1naij21/22. 谱半径A=max1in|i|3. 雅可比迭代向量：用第i个方程解出xi的方程，分量通式如下：xik+1=1aii(bi-j=1jinaijxj(k)矩阵：对于Ax=b，先将A拆分成对角线矩阵D减去下三角矩阵L，再减去上三角矩阵U。xk+1=BJxk+fJ其中BJ=D-1L+U,fJ=D-1b4. 高斯-塞德尔迭代向量：用第i个方程解出xi的方程，并将上式得到的xi(k+1)带入下边的公式，分量通式如下：xik+1=1aii(bi-j=1i-1aijxj(k+1)-j=i+1naijxj(k)矩阵：对于Ax=b，先将A拆分成对角线矩阵D减去下三角矩阵L，再减去上三角矩阵U。xk+1=BSxk+fS其中BS=(D-L)-1U,fS=(D-L)-1b5. 松弛迭代雅可比松弛（JOR）：x(k+1)=I-D-1Axk+D-1b注：当02i时，收敛雅可比方法收敛时，01收敛逐次超松弛（SOR）：xik+1=aii(bi-j=1i-1aijxj(k+1)-j=i+1naijxj(k)注：系数矩阵A对称正定，02时收敛六、 方程求根1. 大范围收敛定理a) j(x)在a,b上连续；b) 当xa,b时，j(x) a,b；c) j(x)存在，且对任意xa,b有|(x)|L12. 牛顿迭代法xk+1=xk-f(xk)f(xk)牛顿下山法xk+1=xk-fxkfxk，其中13. 割线法xk+1=xk-xk-xk-1fxk-fxk-1fxk七、 矩阵特征问题求解1. 规范化乘幂法y(k)=xk/max(x(k)x(k+1)=Ay(k)2. 原点位移乘幂法取一个l0，用B=A-I*l0替代A，则得到的特征值ui=li-l0，特征向量不变八、 常微分方程的数值解法1. 欧拉公式yn+1=yn+hf(xn,yn)yx0=y02. 向后欧拉公式yn+1=yn+hf(xn+1,yn+1)yx0=y03. 梯形公式yn+1=yn+h2fxn,yn+f(xn+1,yn+1)yx0=y04. 改进欧拉公式yn+1=yn+h2fxn,yn+f(xn+1,yn+hf(xn,yn)