数值分析-第五版-考试归纳.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.迭代法收敛的充分必要条件：B<1，谱半径B=max1ini4.渐进收敛速度：RB=-lnB，迭代次数估计：ksln10RB5.雅可比迭代法：Ax=bA=D-(L+U)=D-ND-Nx=bx=D-1Nx+D-1bx(k+1)=Jx(k)+f6.高斯-塞德尔迭代法：Ax=bA=(D-L)-U=M-UM-Ux=bx=M-1Ux+M-1bx(k+1)=Gx(k)+f7.严格对角占优矩阵：此矩阵为非奇异矩阵，其雅可比迭代法与高斯-塞德尔迭代法均收敛。aii>j=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-yL<15. 不动点迭代法收敛性：满足上条，则不动点迭代法收敛，误差为：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)<f(xk)为止。12.弦截法：xk+1=xk-fxkfxk-fxk-1(xk-xk-1)第八章 矩阵特征值计算1.格什戈林圆盘：以aii为圆心，以ri为半径的所有圆盘ri=j=1jinaij,Di=zz-aiiri,zC2. A的每个特征值必属于某个圆盘之中：-aiiri3. A有m个圆盘组成一个连通的并集S，S与和余下n-m个圆盘是分离的，则S内恰包含A的m个特征值。4.幂法：设A的特征值满足条件：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-p<218.若wTw=1，称矩阵Hw=I-2wwT为初等反射矩阵，可得：HT=H, H-1=H10.设x , y为两个不等的n维向量，x2=y2，令w=x-yx-y2，则wTw=1，则可推导出：Hx=I-2wwTx=y11.豪斯霍尔德约化定理：x2=y2Hx=y=sgn(x1)x2y=-e1w=x+e1x+e12=uu2H=I-2wwT=I-2uuTu22=I-1uuT,=12u22=(+x1)12.吉文斯变换：xi=xi2+xj2,cos=xixi,sin=xjxi,cossin-sincos12.矩阵的QR分解：1）设A非奇异，则存在正交矩阵P，使PA=R，其中R为上三角矩阵。2）设A非奇异，则存在正交矩阵P与上三角矩阵R，使A=QR，当R对角元素为正分解唯一。13.豪斯霍尔德约化矩阵为上海森伯格矩阵：Un-2U2U1AU1U2Un-2=H14. QR方法：1）计算上海森伯格矩阵的全部特征值；2）计算对称三对角矩阵的全部特征值。第九章 常微分方程初值问题数值解法1.一阶常微分初值问题：y=fx,y , xx0,b , yx0=y02.利普西茨条件：满足此条件，上述问题存在唯一的连续可微解。fx,y1-fx,y2Ly1-y2 , L>03.欧拉方法：yn+1-ynxn+1-xn=fxn,yn , yn+1=yn+hfxn,yn4.后退的欧拉法：yn+1-ynxn+1-xn=fxn+1,yn+1 , yn+1=yn+hfxn+1,yn+15.梯形方法：yn+1=yn+h2fxn,yn+fxn+1,yn+16.改进欧拉公式：yp=yn+hfxn,ynyc=yn+hfxn+1,ypyn+1=12yp+yc
