数值分析第五版考试总结.doc

学习资料收集于网络，仅供参考第一章：数值分析与科学计算引论截断误差：近似解与精确解之间的误差。近似值的误差e*（x为准确值）：e*=x*-x近似值的误差限*：x*-x *近似值相对误差er*（er*较小时约等）：er*=e*xe*x*近似值相对误差限r*：r*=*x*函数值的误差限*(f(x*)：*(f(x*)f(x*) *(x*)近似值x*=(a1.a2a3an)10m有n位有效数字：*=1210m-n+1r*=*x*12a110-n+1第二章：插值法1.多项式插值Px=a0+a1x+anxn其中： Pxi=yi , i=0,1,na0+a1x0+anx0n=y0a0+a1x1+anx1n=y1a0+a1xn+anxnn=yn2.拉格朗日插值Lnx=k=0nyklkx=k=0nykk+1(x)(x-xk)n+1(xk)n次插值基函数：lkx=(x-x0)(x-xk-1)(x-xk+1)(x-xn)(xk-x0)(xk-xk-1)(xk-xk+1)(xk-xn) , k=0,1,n引入记号：n+1x=(x-x0)(x-x1)(x-xn)余项：Rnx=fx-Lnx=fn+1n+1!n+1x , (a,b)3.牛顿插值多项式：Pnx=fx0+fx0,x1x-x0+fx0,x1,xnx-x0x-xn-1n阶均差（把中间去掉，分别填在左边和右边）：fx0,x1,xn-1,xn=fx1,xn-1,xn-fx0,x1,xn-1xn-x0余项：Rnx=fx,x0,x1,xnn+1x4.牛顿前插公式（令x=x0+th，计算点值，不是多项式）：Pnx0+th=f0+tf0+t(t-1)2!2f0+t(t-1)(t-n-1)n!nf0n阶差分：nf0=n-1f1-n-1f0余项：Rnx=tt-1t-nhn+1n+1!fn+1 , (x0,xn)5.泰勒插值多项式：Pnx=fx0+fx0x-x0+fnx0n!(x-x0)nn阶重节点的均差：fx0,x0,x0=1n!fn(x0)6.埃尔米特三次插值：Px=fx0+fx0,x1x-x0+fx0,x1,x2x-x0x-x1+Ax-x0x-x1(x-x2)其中，A的标定为：Px1=fx17.分段线性插值：Ihx=x-xk+1xk-xk+1fk+x-xkxk+1-xkfk+1第三章：函数逼近与快速傅里叶变换1. Sx属于 n维空间：Sx=j=0najj2.范数：x=max1inxi and maxaibf(x)x1=i=1nxi andabf(x)dxx2=(i=1nxi2)12 and (abf2(x)dx)123.带权内积和带权正交：f,k=i=0m(xi)fxikxi and ab(x)f(x)k(x)dxfx,gx=ab(x) fxgxdx=04.最佳逼近的分类（范数的不同、是否离散）：最优一致（-范数）逼近多项式P*(x)：fx-P*(x)=minPHnfx-P(x)最佳平方（2-范数）逼近多项式P*(x)：fx-P*(x)22=minPHnfx-P(x)22最小二乘拟合（离散点）P*(x)：f-P*22=minPf-P*225.正交多项式递推关系：n+1x=x-nnx-nn-1x0x=1,-1x=0n=(xnx,nx)(nx,nx) ,n=(nx,nx)(n-1x,n-1x)6.勒让德多项式：正交性：-11Pn(x)Pm(x)dx=0 , mn 22n+1 , m=n奇偶性：Pn-x=(-1)nPn(x)递推关系：n+1Pn+1x=2n+1xPnx-nPn-1(x)7切比雪夫多项式：递推关系：Tn+1x=2xTnx-Tn-1x正交性：-11Tn(x)Tm(x)1-x2dx=0cosncosmdx=0 , mn2 , m=n0 , m=n=0Tnx在-1，1上有n个零点：xk=cos2k-12n,k=1,nTn+1x在a,b上有n+1个零点：（最优一致逼近）xk=b-a2cos2k+12(n+1)+b+a2,k=0,1,n首项xn的系数：2n-18.最佳平方逼近：fx-S*(x)22=minS(x)fx-S(x)22=minS(x)ab(x)fx-Sx2dx法方程：j=0nk,jaj=f,k正交函数族的最佳平方逼近：ak*=f,kk,k9.最小二乘法：22=minS(x)i=0m(xi)Sxi-yi2法方程：j=0nk,jaj=f,k正交多项式的最小二乘拟合:ak*=f,PkPk,Pk第四章 数值积分与数值微分1.求积公式具有m次代数精度求积公式（多项式与函数值乘积的和），对于次数不超过m的多项式成立，m+1不成立abf(x)dx=k=0nAkf(xk)2.插值型求积公式In=abLn(x)dx=k=0nablk(x)dxf(xk)=k=0nAkf(xk)Rf=abfx- Ln(x)dx=abRn(x)dx=abfn+1n+1!n+1(x)dx3.求积公式代数精度为m时的余项Rf=abfxdx-k=0nAkfxk=1m+1!abxm+1dx-k=0nAkxkm+14.牛顿-柯特斯公式：将a,b划分为n等份构造出插值型求积公式In=(b-a)k=0nCk(n)f(xk)5.梯形公式：当n=1时，C0(1)=C1(1)=12T=b-a2fa+f(b),Rnf=-b-a12b-a2f()6.辛普森公式：当n=2时，C0(2)=16,C1(2)=46,C2(2)=16S=b-a6fa+4fa+b2+f(b),Rnf=-b-a180(b-a2)4f(4)()7.复合求积公式：h=b-an,xk=a+kh,xk+1/2=xk+h2复合梯形公式：Tn=h2fa+2k=1n-1f(xk)+f(b),Rnf=-b-a12h2f()复合辛普森公式：Sn=h6fa+4k=0n-1f(xk+1/2)+2k=1n-1f(xk)+f(b),Rnf=-b-a180(h2)4f(4)()8.高斯求积公式（求待定参数xk和Ak）：（1）求高斯点（xk）：令 n+1x=(x-x0)(x-x1)(x-xn)与任何次数不超过n的多项式p(x)带权(x)正交，即则abp(x)n+1x(x)dx=0，由n+1个方程求出高斯点x0,x1xn。（2）求待定参数Ak：ab(x)f(x)dx=k=0nAkf(x)，f(x)也为次数不超过n的多项式。9.高斯-勒让德求积公式：取权函数为x=1的勒让德多项式Pn+1(x)的零点即为求积公式的高斯点。10.高斯-切比雪夫求积公式：取权函数为x=11-x2的切比雪夫多项式的零点xk=cos2k+12n+2即为求积公式的高斯点。第五章 解线性方程组的直接方法1.矩阵的从属范数：A=max1inj=1naij(行元素绝对值之和中最大的)A1=max1jni=1naij(列元素绝对值之和中最大的)A2=max(ATA)2.条件数：cond(A)=A-1Acond(A)2=max(ATA)min(AAT),当A=AT时,cond(A)2=max(A)min(A)第六章 解线性方程组的迭代法1.迭代法：Ax=bM-Nx=bx=M-1Nx+M-1bx(k+1)=Bx(k)+f2.迭代法收敛：limkx(k)存在。3.迭代法收敛的充分必要条件：Bj=1jinaij8.弱对角占优矩阵：若此矩阵也为不可约矩阵，则其雅可比迭代法与高斯-塞德尔迭代法均收敛。aiij=1jinaij其中，可约矩阵：n阶矩阵A有如下型式，否则为不可约矩阵。PTAP=A11A120A229.超松弛迭代法：为高斯-塞德尔迭代法的一种修正。Ax=bA=(D-L)-U=(1D-L)-(1D+U-D)M=(1D-L),N=(1D+U-D)M-Nx=bx=M-1Nx+M-1bL=M-1N=D-L-1(U+1-D)=D-L-1(1-D+U)f=M-1b=D-L-1bx(k+1)=Lx(k)+f10.最速下降法：A是对称正定矩阵Ax=b令：xk+1=xk+kp(k)使下式最小：x(k+1)=x(k)+p(k)=x(k)+Ax(k)-b,p(k)+22Ap(k),p(k)则：dd=0,k=-Axk-b,pkApk,pk=r(k),r(k)Ar(k),r(k)其中：p(k)=-xk=-Axk-b=r(k)故而：xk+1=xk+kr(k)11.共轭梯度法：（1）令x0=0，计算r(0)=-Ax0-b，取p(0)=r(0)（2）对k=0,1,，计算xk+1=xk+kp(k)k=r(k),r(k)Apk,pkr(k+1)=r(k)-kApkpk+1=r(k+1)+kpkk=r(k+1),r(k+1)r(k),r(k)（3）若r(k)=0或Apk,pk=0，计算停止。第七章 非线性方程与方程组的数值解法1.二分法：1）计算f(x)在有根区间a,b的端值f(a), f(b) 2）计算区间中点值f(a+b2) 3）判断fa+b2=0或者f(a+b2)f(a)02.不动点迭代法：fx=0x=x=fx+xxk+1=xk3.不动点迭代法收敛：limkxk=x*4. (x)在a,b上存在不动点x*：（压缩映射）a(x)bx-(y)Lx-yL15. 不动点迭代法收敛性：满足上条，则不动点迭代法收敛，误差为：xk-x*Lk1-Lx1-x06.局部收敛：存在x*的某个邻域内的任意的x0，迭代法产生的序列收敛到x*。7.不动点迭代法局部收敛：其中x*为(x)的不动点，(x)在x*邻域连续。(x*)18. P阶收敛：当k时，迭代误差ek=xk-x*，满足ek+1ekpC09.牛顿（m重根）法:xk+1=xk-fxkfxk,xk+1=xk-mf(xk)f(xk)10.简化的牛顿法：xk+1=xk-f(xk)f(x0)11.牛顿下山法：xk+1=xk-fxkfxk,k=0,1,从=1开始试算，之后逐次减半，直到满足下降条件：f(xk+1)23n任取非零向量v0，构造向量序列，v1=Av0,v2=A2v0,vk+1=Ak+1v0,假设：v0=1x1+2x2+nxn,10则：vk=11kx1+22kx2+nnkxn=1k1x1+i=2nii1kxi11kx1limk(vk+1)i(vk)i=15.收敛速度： r=216.幂法改进：u0=v00vk=Auk-1,uk=vkuk,uk=maxvklimkuk=x1maxx1limkuk=17.加速方法（原点平移法）：构造矩阵B，应用幂法使在计算其主特征值的过程中得到加速。B=A-pIr=2-p1-p0一扇门窗 一个故事 一个城市 一座城市 一片草地3.欧拉方法：你是学生，我也是学生。yn+1-ynxn+1-xn=fxn,yn , yn+1=yn