数值分析(计算方法)总结.docx

1、第一章 绪论 误差来源：模型误差、观测误差、截断误差（方法误差）、舍入误差 x=|xx|是x的绝对误差，e=xx是x的误差，x=xx，为x的绝对误差限（或误差限） er=ex=xxx为x 的相对误差，当|er|较小时，令 er=ex=xxx相对误差绝对值得上限称为相对误差限记为：r 即：er=|xx|xx=r绝对误差有量纲，而相对误差无量纲若近似值x的绝对误差限为某一位上的半个单位，且该位直到x的第一位非零数字共有n位，则称近似值 x有n位有效数字，或说 x 精确到该位。例：设x=3.1415926那么x=3,1x=0.14159260.5100,则x有效数字为1位，即个位上的3，或说 x 精

2、确到个位。科学计数法：记x=0.a1a2an10m其中a10,若xx0.510mn，则x有n位有效数字，精确到10mn。由有效数字求相对误差限：设近似值x=0.a1a2an10m（a10）有n位有效数字，则其相对误差限为12a1101n由相对误差限求有效数字：设近似值x=0.a1a2an10m（a10）的相对误差限为为12（a1+1）101n则它有n位有效数字令x、y是x、y的近似值，且|xx|x、|yy|(y)1. x+y近似值为x+y,且x+y=x+（y）和的误差（限）等于误差（限）的和2. x-y近似值为xy,且x+y=x+（y）3. xy近似值为xy,xyxy+y(x)4. (xy)x

3、y+y(x)|y|21避免两相近数相减2避免用绝对值很小的数作除数3避免大数吃小数4尽量减少计算工作量第二章 非线性方程求根1.逐步搜索法设f (a) 0，有根区间为 (a, b)，从x0=a出发， 按某个预定步长(例如h=(b-a)/N)一步一步向右跨，每跨一步进行一次根的搜索，即判别f(xk)=f(a+kh)的符号，若f(xk)0(而f(xk-1)0),则有根区间缩小为xk-1,xk (若f(xk)=0，xk即为所求根), 然后从xk-1出发，把搜索步长再缩小，重复上面步骤，直到满足精度：|xk-xk-1|E为止，此时取x*(xk+xk-1)/2作为近似根。2.二分法设f(x)的有根区间为

4、a,b= a0,b0, f(a)0.将a0,b0对分，中点x0= (a0+b0)/2),计算f(x0)。对于给定精度，即ba2klnbaln()ln23.比例法一般地，设 ak,bk为有根区间，过(ak, f(ak)、 (bk, f(bk)作直线，与x轴交于一点xk,则： 1.试位法每次迭代比二分法多算一次乘法，而且不保证收敛。2.比例法不是通过使求根区间缩小到0来求根，而是在一定条件下直接构造出一个点列（递推公式），使该点列收敛到方程的根。这正是迭代法的基本思想。 事先估计:|xxk|L1L|x1x0|事后估计|xxk|11L|xk+1xk|局部收敛性判定定理：设x为方程x=x的根，(x)在

5、x的某一邻域内连续， 且(x)0xk+2cb+b24ac ,b0 设迭代 xk+1 = g(xk) 收敛到g(x) 的不动点（根） x* 设 ek = xk - x*若limkek+1ekp=C，则称该迭代为p （不小于1）阶收敛，其中 C (不为0)称为渐进误差常数第三章 解线性方程组直接法列主元LU分解法：计算主元Si=aikr=1k1lirurk，i=k,k+1n选主元Sik=maxkinSiu1j=a1j，（j=1,2n)li1=ai1u11，（i=2,3n)ukj=akjm=1k1lkmumj，j=k,k+1,n，即为上式主元lik=1ukkaikm=1k1limumk，i=k+1,

6、k+2,n 对于Ax=b，三角分解A=LU，Doolittle分解：L为单位下三角矩阵，U为上三角矩阵；Crout分解：L为下三角矩阵，U为单位上矩阵。可分解为：Ly=b，下三角方程组Ux=y，上三角方程组若利用紧凑格式可化为：Ux=yy1=b1yk=bkm=1k1lkmym，（k=2,3n） Cholesky平方根法：系数矩阵A必须对称正定AX=bLy=bLTx=y(其中A=LLT)l11=a11，li1=ai1l11(i=2,3n)lkk=akkm=1k1lkm2，lik=1lkk(aikm=1k1limlkm)(i=k+1,k+2n，k=2,3n) 改进Cholesky分解法：A=LDL

7、TL=1l211l31l321ln1ln2ln(n1)1，D=d1d2dn。由A=L(DLT)A=1l211l31l321ln1ln2ln(n1)1，D=d1d1l21d1l31d1ln1d2d2l32d2ln2d3ln3dn，逐行相乘lij=1dj(aijk=1j1likdkljk)，（j=1,2i1)di=aiik=1j1lik2dk，（i=1,2n)为减少计算量，令cij=lijdj，可改为：cij=aijk=1j1cikljklij=cijdjdj=aiik=1i1ciklik(i=2,3n，j=1,2i1)，等价于Ly=bLTx=D1y其中：D1=1d11d21dn 追赶法：Ax=d

8、(A=LU),可化为Ly=d,Ux=yA=a1c1b1a2c2an1bn1cn1anbn=1l21ln11ln1u1c1u2c2un1cn1unu1=b1li=aiui1ui=bilici1，（i=2,3n) 向量范数：A1=i=1nxi，1范数A2=i=1nxi2，2范数或欧氏范数A=limp+xp=max1inxi，范数矩阵范数：A1=max1jni=1naij，列范数A2=maxATA，谱范数A=max1inj=1naij，行范数谱半径:A=max1ini为特征值,且AA,若A为对称阵则：A=A2收敛条件：谱半径小于1条件数：Cond=A1A，Cond2A=maxmin第四章 解线性方程

9、组的迭代法Jacobi迭代：xi(k+1)=1aii(bij=1i1aijxjkj=i+1naijxjk),(i=1,2n;k=0,1,2) 基于Jacobi迭代的Gauss-Seidel迭代:xi(k+1)=1aii(bij=1i1aijxjk+1j=i+1naijxjk),(i=1,2n;k=0,1,2)迭代收敛：谱半径小于1，范数小于1能推出收敛但不能反推 逐次超松弛迭代（SOR）:xi(k+1)=xi(k)aii(bij=1i1aijxjk+1j=i+1naijxjk),(i=1,2n;k=0,1,2)或：xi(k+1)=1xik+aii(bij=1i1aijxjk+1j=i+1nai

10、jxjk),(i=1,2n;k=0,1,2) 当=1时，就是基于Jacobi迭代的Gauss-Seidel迭代（加权平均）。第五章 插值法 Lagrange插值法：ljxi=0，ij1，i=j，则ljx=i=0nxxixjxi构造插值函数：Lnxi=fxi=yi，i=0,1n，令Lx=l0xy0+l1xy1+ln(x)yn 则：y=Lnx=j=0nljxyj=j=0ni=0ijn(xxi)(xjxi)yj 若记：wx=xx0xx1xxn=i=0n（xxi） 则可改为：ljx=wn+1(x)xxjwn+1(xj)，则Lnx=j=0ni=0ijn(xxi)(xjxi)yj=j=0nw(x)xxjw

11、(xj)yj 则插值余项：Rnx=fxLnx=fn+1n+1!wn+1(x) 逐次线性插值法Aitken （埃特金法）：L 0,1k,lx=L0,1kx+L0,1k1xL0,1kxxlxkxxk=1xlxkf(xl)xxlf(xk)xxk Newton插值法： N(x)=a0+a1(x-x0)+a2(x-x0)(x-x1)+an(x-x0)(x-x1)(x-xn)并满足N(x)=f(x) 差商的函数值表示：fx0,x1xk=i=0kf(xi)wk+1(xi) 差商与导数的关系：fx0,x1xk=fn()n! 则：fx=fx0+fx0,x1w1x+fx0,x1xnwnx+fx,x0,x1xn+1

12、wn+1x 等距节点Newton插值公式： Newton向前插值：Nna+th=fx+k=1nky0tk，其中tk=tt1(tk+1)k! 余项：Rnx=fn+1hn+1tn+1，t=xx0h Newton向后插值：Nnxn+th=fxn+k=1nkynt+k1k 余项：Rnx=fn+1hn+1t+nn+1 Hermite插值：Hx=j=0njxyj+j=0njxyj jx=Ax+Blj2x，jx=Cx+Dlj2(x) 可得：ix=12xxik=0kin1xixkli2(x)ix=xxili2(x) 插值余项：R2n+1x=fxH2n+1x=f2n+22n+2!wn+12(x) 待定系数：Hx

13、=L0,1n(Aitken)+xx1xx2xxn(Ax+B) 三次样条插值：（三弯矩构造法） 记sxi=Mi对s积分两次并满足插值条件，hi=xixi1，i=hihi+hi+1，i=hi+1hi+hi+1 对于附加弯矩约束条件：2122232n2n12M1M2M3Mn1=6fx0,x1,x21M06fx1,x2，x36fx2,x3，x46fxn2,xn1,xnn1MniMi1+2Mi+iMi+1=6fxi1,xi,xi+1 对于附加转角边界条件：21121222n12n112M0M1M2Mn1Mn=6fx0,x1m0h1fx0,x1，x2fx1,x2，x3fxn2,xn1,xnmnfxn2,x

14、n1,xnhn 对于附加周期性边界条件：200121222n22n2n1n22M0M1M2Mn2Mn1=6fx0,x1fxn1,xnh1+hnfx0,x1，x2fx1,x2，x3fxn3,xn2,xn1fxn2,xn1,xnsx=Mi1(xix)36hi+Mi(xxi1)36hi+fxi1Mi1hi26xixhi+fxiMihi26xxi1hi 上式保证了s(x)在相邻两点的连续性第六章 函数逼近与曲线拟合 主要求法方程第七章 数值积分与数值微分 求积公式具有m次代数精度的充要条件：abxkdx=i=0nAixik，k=0,1n，abxm+1dxi=0nAixim+1 插值型求积公式abfx=

15、dxi=0nAif(xi)求积系数公式：Ai=ablixdx，i=0,1n Newton-Cotes（等分） 梯形求积公式（n=1），具有1次代数收敛精度abfxdxba2fa+fb 误差公式：E1f=ba312f() 抛物型求积公式（Simpson求积公式，n=2），具有3次代数收敛精度abfxdxba6fa+4fa+b2+fb 误差公式E2f=ba52880f（4）() Newton求积公式（Simpon3/8法则） 具有3次代数收敛精度Nfba8fa+3fa+h+3fa+2h+fb，h=ban Cotes求积公式（n=4），具有5次收敛精度abfxdxba907fa+32fa+h+12f

16、a+2h+32fa+3h+7fb，h=ban 误差公式E4f=2（ba)945(ba4)6f（6）() 节点数为奇数时，代数精度为n;为偶数时，代数精度为n+1。代数精度都是奇数。 复化梯形求积公式：Tnf=h2fa+2i=1n1fxi+f(b) 截断误差：Ern(f)=ba12h2f() 复化Simpson公式：Snf=h6fa+2i=1n1fxi+4i=0n1fxi+12+f(b) 截断误差：Esnf=ba2880h4f4() 复化Cotes求积： Cnf=h907fa+14i=1n1fxi+32i=1n1fxi+h4+12i=1n1fxi+h2+32i=1n1fxi+3h4+7fb 截断

17、误差：Ecnf=2ba945h46f6() 若一个复化积分公式的误差满足 limh0Rfhp=C且C 0，则称该公式是 p 阶收敛的。 复化求积公式（需要2n+1个求积节点） Romberg求积算法：Sn=43T2n13TnCn=1615S2n115SnRn=6463C2n163Cn 复化梯形求积公式：T2nf+13T2nfTnf=Sn(f) 复化Cotes求积公式：C2nf+163C2nfCnf=Rn(f) Gauss型求积公式： 内积公式：p,n+1=abpxn+1xxdx 截断误差：Enf=f2n+1()2n+2!abn+1x2xdx，（a,b） 高斯求积公式代数精度为2n+1 Gaus

18、s-Legendre求积公式（注意区间（-1,1），变换可得）：形如：11fxdxi=0nAif(xi)求积系数可通过代数精度或插值型求积公式求积系数公式求出，亦可由下式求得：Ai=21xi2pn+1x2，i=0,1n 截断误差：Enf=22n+3n+1!42n+32n+2!3f2n+2，（1,1） Gauss-Chebyshev求积公式：形如：11f(x)dx1x2i=0nAif(xi) 求积系数：Ai=n+1(i=0,1n)(必为正) 截断误差：Enf=22n+12n+2!f2n+2，（1,1） Gauss-Laguerre求积公式：形如：0f(x)exdxi=0nAif(xi) 求积系数

19、：Ai=n+1!2xiLn+1xi2，i=0,1n 截断误差：Enf=n+1!22n+1!f2n+2，（0，+） Gauss-Hermite求积公式：形如：+f(x)ex2dxi=0nAif(xi) 求积系数：Ai=2n+2n+1!Hn+1xi2，i=0,1n 截断误差：Enf=n+1!2n+12n+2!f2n+2，（，+） 三点数值微分公式：fx=fx2fx02hh26f2，2（x0,x2) 泰勒级数展开：fx04Th2f;x0Th(f;x0)3第八章 常微分方程求解 Euler法：yn+1=yn+hf(xn，yn)为一阶法（f(x,y)为y的导数） 梯形方法（改进Euler法）：yn+1=yn+h2fxn，yn+fxn+1，yn+1 四级四阶经典Runge-Kutta公式yn+1=yn+h6(K1+2K2+2K3+K4)K1=f(xn，yn)K2=f(xn+12h，yn+h2K1)K3=f(xn+12h，yn+h2K2)K4=f(xn+h，yn+hK3)