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

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

2、0,则x*有效数字为1位，即个位上的3，或说 x *精确到个位。科学计数法:记x*=±0.a1a2an×10m其中a10,若x-x*0.5×10m-n，则x*有n位有效数字,精确到10m-n.由有效数字求相对误差限:设近似值x*=±0.a1a2an×10m（a10）有n位有效数字,则其相对误差限为12a1×101-n由相对误差限求有效数字:设近似值x*=±0.a1a2an×10m（a10）的相对误差限为为12（a1+1）×101-n则它有n位有效数字令x*、y*是x、y的近似值，且|x*-x|x、|y*-

3、y|(y)1. x+y近似值为x*+y*,且x+y=x+（y）和的误差(限）等于误差（限）的和2. xy近似值为x*-y*,且x+y=x+（y）3. xy近似值为x*y*,xyx*y+y*(x)4. (xy)x*y+y*(x)|y*|21避免两相近数相减2避免用绝对值很小的数作除数3避免大数吃小数4尽量减少计算工作量第二章 非线性方程求根1。逐步搜索法设f (a) 0， f （b) 0,有根区间为 （a， b），从x0=a出发， 按某个预定步长(例如h=（ba）/N）一步一步向右跨，每跨一步进行一次根的搜索，即判别f（xk）=f（a+kh）的符号，若f（xk）0(而f（xk1）0),则有根区间

4、缩小为xk1，xk （若f（xk)=0,xk即为所求根）, 然后从xk1出发，把搜索步长再缩小，重复上面步骤，直到满足精度:|xkxk1<E为止,此时取x（xk+xk-1)/2作为近似根。2。二分法设f（x）的有根区间为a,b= a0,b0, f(a）0， f（b）>0.将a0，b0对分，中点x0= (（a0+b0）/2),计算f（x0）。对于给定精度，即b-a2k<，可得所需步数k，k>lnb-a-ln()ln23.比例法一般地，设 ak，bk为有根区间,过（ak， f(ak）、 （bk, f(bk）)作直线，与x轴交于一点xk，则：x=a-f(a)fb-f(a)*(

5、b-a)1。试位法每次迭代比二分法多算一次乘法,而且不保证收敛。2.比例法不是通过使求根区间缩小到0来求根，而是在一定条件下直接构造出一个点列（递推公式），使该点列收敛到方程的根.-这正是迭代法的基本思想。事先估计:|x*-xk|L1-L|x1-x0|事后估计|x*-xk|11-L|xk+1-xk|局部收敛性判定定理:设x*为方程x=x的根，(x)'在x*的某一邻域内连续，且(x*)'<1，则该迭代局部收敛局部收敛性定理对迭代函数的要求较弱,但对初始点要求较高,即初始点必须选在精确解的附近Steffensen迭代格式：xk+1=(xk)xk+1=(xk+1)xk+1=xk

6、-(xk+1-xk)2xk+1-2xk+1+xkNewton法：xk+1=xk-f(xk)f'(xk)Newton下山法：xk+1=xk-f(xk)f'(xk),是下山因子弦割法：xk+1=xk-fxk*(xk-xk-1)fxk-f(xk-1)抛物线法：令t=x-xk,h0=xk-2-xk,h1=xk-1-xk,可化为yt=at2+bt+c其中:a=fxk-2-c*h1-fxk-1-c*h0h1*h02-h0*h12b=fxk-1-c*h02-fxk-2-c*h12h1*h02-h0*h12c=f(xk)则：xk+1=xk+-2cb+b2-4ac,b>0xk+2cb+b2

7、-4ac ,b0设迭代 xk+1 = g（xk） 收敛到g（x） 的不动点（根）x设 ek = xk-x*若limkek+1ekp=C，则称该迭代为p(不小于1）阶收敛，其中 C（不为0）称为渐进误差常数第三章 解线性方程组直接法列主元LU分解法：计算主元Si=aik-r=1k-1lirurk，i=k,k+1n选主元Sik=maxkinSiu1j=a1j，（j=1,2n)li1=ai1u11，（i=2,3n)ukj=akj-m=1k-1lkmumj，j=k,k+1,n，即为上式主元lik=1ukkaik-m=1k-1limumk，i=k+1,k+2,n对于Ax=b，三角分解A=LU，Dooli

8、ttle分解：L为单位下三角矩阵,U为上三角矩阵；Crout分解:L为下三角矩阵，U为单位上矩阵.可分解为:Ly=b，下三角方程组Ux=y，上三角方程组若利用紧凑格式可化为:Ux=yy1=b1yk=bk-m=1k-1lkmym，（k=2,3n）Cholesky平方根法：系数矩阵A必须对称正定AX=bLy=bLTx=y(其中A=LLT)l11=a11，li1=ai1l11(i=2,3n)lkk=akk-m=1k-1lkm2，lik=1lkk(aik-m=1k-1limlkm)(i=k+1,k+2n，k=2,3n)改进Cholesky分解法：A=LDLTL=1l211l31l321ln1ln2ln

9、(n-1)1，D=d1d2dn。由A=L(DLT)A=1l211l31l321ln1ln2ln(n-1)1，D=d1d1l21d1l31d1ln1d2d2l32d2ln2d3ln3dn，逐行相乘lij=1dj(aij-k=1j-1likdkljk)，（j=1,2i-1)di=aii-k=1j-1lik2dk，（i=1,2n)为减少计算量，令cij=lijdj，可改为：cij=aij-k=1j-1cikljklij=cijdjdj=aii-k=1i-1ciklik(i=2,3n，j=1,2i-1)，等价于Ly=bLTx=D-1y其中：D-1=1d11d21dn追赶法：Ax=d（A=LU），可化为

10、Ly=d，Ux=yA=a1c1b1a2c2an-1bn-1cn-1anbn=1l21ln-11ln1u1c1u2c2un-1cn-1unu1=b1li=aiui-1ui=bi-lici-1，（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=A-1*A，Cond2A=maxmin第四章 解

11、线性方程组的迭代法Jacobi迭代：xi(k+1)=1aii(bi-j=1i-1aijxjk-j=i+1naijxjk),(i=1,2n;k=0,1,2)基于Jacobi迭代的GaussSeidel迭代：xi(k+1)=1aii(bi-j=1i-1aijxjk+1-j=i+1naijxjk),(i=1,2n;k=0,1,2)迭代收敛:谱半径小于1，范数小于1能推出收敛但不能反推逐次超松弛迭代(SOR）:xi(k+1)=xi(k)-aii(bi-j=1i-1aijxjk+1-j=i+1naijxjk),(i=1,2n;k=0,1,2)或：xi(k+1)=1-xik+aii(bi-j=1i-1ai

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

13、-xi)(xj-xi)yj=j=0nw(x)x-xjw'(xj)yj则插值余项：Rnx=fx-Lnx=fn+1n+1!wn+1(x)逐次线性插值法Aitken (埃特金法):L 0,1k,lx=L0,1kx+L0,1k-1x-L0,1kxxl-xkx-xk=1xl-xkf(xl)x-xlf(xk)x-xkNewton插值法:N（x）=a0+a1(xx0)+a2（xx0)(xx1)+an（x-x0）（xx1）（xxn）并满足N(x）=f(x)差商的函数值表示:fx0,x1xk=i=0kf(xi)wk+1(xi)差商与导数的关系：fx0,x1xk=fn()n!则:fx=fx0+fx0,x1

14、w1x+fx0,x1xnwnx+fx,x0,x1xn+1wn+1x等距节点Newton插值公式：Newton向前插值：Nna+th=fx+k=1nky0tk，其中tk=tt-1(t-k+1)k!余项：Rnx=fn+1hn+1tn+1，t=x-x0hNewton向后插值：Nnxn+th=fxn+k=1nkynt+k-1k余项：Rnx=fn+1hn+1t+nn+1Hermite插值:Hx=j=0njxyj+j=0njxy'jjx=Ax+Blj2x，jx=Cx+Dlj2(x)可得：ix=1-2x-xik=0kin1xi-xkli2(x)ix=x-xili2(x)插值余项:R2n+1x=fx-

15、H2n+1x=f2n+22n+2!wn+12(x)待定系数：Hx=L0,1n(Aitken)+x-x1*x-x2*x-xn*(Ax+B)三次样条插值：（三弯矩构造法)记s''xi=Mi对s积分两次并满足插值条件，hi=xi-xi-1，i=hihi+hi+1，i=hi+1hi+hi+1对于附加弯矩约束条件:2122232n-2n-12M1M2M3Mn-1=6fx0,x1,x2-1M06fx1,x2，x36fx2,x3，x46fxn-2,xn-1,xn-n-1MniMi-1+2Mi+iMi+1=6fxi-1,xi,xi+1对于附加转角边界条件：21121222n-12n-112M0

16、M1M2Mn-1Mn=6fx0,x1-m0h1fx0,x1，x2fx1,x2，x3fxn-2,xn-1,xnmn-fxn-2,xn-1,xnhn对于附加周期性边界条件:200121222n-22n-2n-1n-22M0M1M2Mn-2Mn-1=6fx0,x1-fxn-1,xnh1+hnfx0,x1，x2fx1,x2，x3fxn-3,xn-2,xn-1fxn-2,xn-1,xnsx=Mi-1(xi-x)36hi+Mi(x-xi-1)36hi+fxi-1-Mi-1hi26xi-xhi+fxi-Mihi26x-xi-1hi上式保证了s（x）在相邻两点的连续性第六章 函数逼近与曲线拟合主要求法方程第七

17、章 数值积分与数值微分求积公式具有m次代数精度的充要条件：abxkdx=i=0nAixik，k=0,1n，abxm+1dxi=0nAixim+1插值型求积公式abfx=dxi=0nAif(xi)求积系数公式：Ai=ablixdx，i=0,1nNewtonCotes(等分)梯形求积公式（n=1），具有1次代数收敛精度abfxdxb-a2fa+fb误差公式:E1f=-b-a312f''()抛物型求积公式(Simpson求积公式，n=2），具有3次代数收敛精度abfxdxb-a6fa+4fa+b2+fb误差公式E2f=-b-a52880f（4）()Newton求积公式(Simpon3

18、/8法则） 具有3次代数收敛精度Nfb-a8fa+3fa+h+3fa+2h+fb，h=b-anCotes求积公式（n=4）,具有5次收敛精度abfxdxb-a907fa+32fa+h+12fa+2h+32fa+3h+7fb，h=b-an误差公式E4f=-2（b-a)945(b-a4)6f（6）()节点数为奇数时，代数精度为n；为偶数时,代数精度为n+1.代数精度都是奇数。复化梯形求积公式:Tnf=h2fa+2i=1n-1fxi+f(b)截断误差：Ern(f)=-b-a12h2f''()复化Simpson公式:Snf=h6fa+2i=1n-1fxi+4i=0n-1fxi+12+f

19、(b)截断误差：Esnf=-b-a2880h4f4()复化Cotes求积：Cnf=h907fa+14i=1n-1fxi+32i=1n-1fxi+h4+12i=1n-1fxi+h2+32i=1n-1fxi+3h4+7fb截断误差:Ecnf=-2b-a945h46f6()若一个复化积分公式的误差满足 limh0Rfhp=C<且C ¹ 0，则称该公式是 p阶收敛的。复化求积公式（需要2n+1个求积节点）Romberg求积算法:Sn=43T2n-13TnCn=1615S2n-115SnRn=6463C2n-163Cn复化梯形求积公式：T2nf+13T2nf-Tnf=Sn(f)复化Cotes求积公式:C2nf+163C2nf-Cnf=Rn(f)Gauss型求积公式：内积公式:p,n+1=abpxn+1xxdx截断误差:Enf=f2n+1()2n+2!abn+1x2xdx，（a,b）高斯求积公式代数精度为2n+1GaussLegendre求积公式（注意区间（-1,1），变换可得）：形如：-11fxdxi=0nAif(xi)求积系数可通过代数精度或插值型求积公式求积系数公式求出，亦可由下式求得:Ai=21-xi2pn+1'x2，i=