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

第一章 绪论
误差来源：模型误差、观测误差、截断误差（方法误差）、舍入误差
ε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.1415926…≤0.5×100,则x*有效数字为1位，即个位上的3，或说 x *精确到个位。
科学计数法：记x*=±0.a1a2⋯an×10m其中a1≠0,若x-x*≤0.5×10m-n，则x*有n位有效数字，精确到10m-n。
由有效数字求相对误差限：设近似值x*=±0.a1a2⋯an×10m（a1≠0）有n位有效数字，则其相对误差限为12a1×101-n
由相对误差限求有效数字：设近似值x*=±0.a1a2⋯an×10m（a1≠0）的相对误差限为为12（a1+1）×101-n则它有n位有效数字
令x*、y*是x、y的近似值，且|x*-x|≤ηx、|y*-y|≤η(y)
1. x+y近似值为x*+y*,且ηx+y=ηx+η（y）和的误差（限）等于误差（限）的和
2. x-y近似值为x*-y*,且ηx+y=ηx+η（y）
3. xy近似值为x*y*,ηxy≈x**ηy+y**η(x)
4. η(xy)≈x**ηy+y**η(x)|y*|2
1．避免两相近数相减
2．避免用绝对值很小的数作除数
3．避免大数吃小数
4．尽量减少计算工作量
第二章 非线性方程求根
1.逐步搜索法
设f (a) <0, f (b)> 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)的有根区间为[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⁡(ε)ln2
3.比例法
一般地，设 [ak,bk]为有根区间，过(ak, f(ak))、 (bk, f(bk))作直线，与x轴交于一点xk,则：x=a-f(a)fb-f(a)*(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-(xk+1-xk)2xk+1-2xk+1+xk
Newton法：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*h12
b=fxk-1-c*h02-fxk-2-c*h12h1*h02-h0*h12
c=f(xk)
则：
xk+1=xk+-2cb+b2-4ac,b>0xk+2cb+b2-4ac ,b≤0
设迭代 xk+1 = g(xk) 收敛到g(x) 的不动点（根） x* 设 ek = xk - x*若limk→∞ek+1ekp=C，则称该迭代为p （不小于1）阶收敛，其中 C (不为0)称为渐进误差常数
第三章 解线性方程组直接法
列主元LU分解法：计算主元Si=aik-r=1k-1lirurk，i=k,k+1…n选主元Sik=maxk≤i≤nSi
u1j=a1j，（j=1,2…n)li1=ai1u11，（i=2,3…n)
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，Doolittle分解：L为单位下三角矩阵，U为上三角矩阵；Crout分解：L为下三角矩阵，U为单位上矩阵。可分解为：
Ly=b，下三角方程组Ux=y，上三角方程组若利用紧凑格式可化为：Ux=y
y1=b1yk=bk-m=1k-1lkmym，（k=2,3…n）
Cholesky平方根法：系数矩阵A必须对称正定AX=b⇔Ly=bLTx=y(其中A=LLT)
l11=a11，li1=ai1l11(i=2,3…n)lkk=akk-m=1k-1lkm2，lik=1lkk(aik-m=1k-1limlkm)(i=k+1,k+2…n，k=2,3…n)
改进Cholesky分解法：A=LDLT
L=1l211l31l321………⋱ln1ln2…ln(n-1)1，D=d1d2⋱⋱dn。由A=L(DLT)
A=1l211l31l321………⋱ln1ln2…ln(n-1)1，D=d1d1l21d1l31…d1ln1d2d2l32…d2ln2⋱…d3ln3⋱⋮dn，逐行相乘
lij=1dj(aij-k=1j-1likdkljk)，（j=1,2…i-1)di=aii-k=1j-1lik2dk，（i=1,2…n)为减少计算量，令cij=lijdj，可改为：
cij=aij-k=1j-1cikljklij=cijdjdj=aii-k=1i-1ciklik(i=2,3…n，j=1,2…i-1)，等价于Ly=bLTx=D-1y
其中：D-1=1d11d2⋱1dn
追赶法：Ax=d(A=LU),可化为Ly=d,Ux=y
A=a1c1b1a2c2⋱⋱⋱an-1bn-1cn-1anbn=1l21⋱⋱ln-11ln1u1c1u2c2⋱⋱un-1cn-1un
u1=b1li=aiui-1ui=bi-lici-1，（i=2,3…n)
向量范数：：A1=i=1nxi，1-范数A2=i=1nxi2，2-范数或欧氏范数A∞=limp→+∞xp=max1≤i≤n{xi}，∞-范数
矩阵范数：A1=max1≤j≤ni=1naij，列范数A2=λmaxATA，谱范数A∞=max1≤i≤nj=1naij，行范数
谱半径:ρA=max1≤i≤n{λi}λ为特征值,且ρA≤A,若A为对称阵则：ρA=A2
收敛条件：谱半径小于1
条件数：Cond=A-1*A，Cond2A=λmaxλmin
第四章 解线性方程组的迭代法
Jacobi迭代：xi(k+1)=1aii(bi-j=1i-1aijxjk-j=i+1naijxjk),(i=1,2…n;k=0,1,2…)
基于Jacobi迭代的Gauss-Seidel迭代:
xi(k+1)=1aii(bi-j=1i-1aijxjk+1-j=i+1naijxjk),(i=1,2…n;k=0,1,2…)
迭代收敛：谱半径小于1，范数小于1能推出收敛但不能反推
逐次超松弛迭代（SOR）:
xi(k+1)=xi(k)-ϖaii(bi-j=1i-1aijxjk+1-j=i+1naijxjk),(i=1,2…n;k=0,1,2…)
或：xi(k+1)=1-ϖxik+ϖaii(bi-j=1i-1aijxjk+1-j=i+1naijxjk),(i=1,2…n;k=0,1,2…)
当ϖ=1时，就是基于Jacobi迭代的Gauss-Seidel迭代（加权平均）。
第五章 插值法
Lagrange插值法：
ljxi=0，i≠j1，i=j，则ljx=i=0nx-xixj-xi
构造插值函数：Lnxi=fxi=yi，i=0,1…n，令Lx=l0xy0+l1xy1+…+ln(x)yn
则：y=Lnx=j=0nljxyj=j=0ni=0i≠jn(x-xi)(xj-xi)yj
若记：wx=x-x0x-x1…x-xn=i=0n（x-xi）
则可改为：ljx=wn+1(x)x-xjw'n+1(xj)，则Lnx=j=0ni=0i≠jn(x-xi)(xj-xi)yj=j=0nw(x)x-xjw'(xj)yj
则插值余项：Rnx=fx-Lnx=fn+1ξn+1!wn+1(x)
逐次线性插值法Aitken （埃特金法）：
L 0,1…k,lx=L0,1…kx+L0,1…k-1x-L0,1…kxxl-xkx-xk=1xl-xkf(xl)x-xlf(xk)x-xk
Newton插值法：
N(x)=a0+a1(x-x0)+a2(x-x0)(x-x1)+…+an(x-x0)(x-x1)…(x-xn)并满足N(x)=f(x)
差商的函数值表示：fx0,x1…xk=i=0kf(xi)wk+1(xi)
差商与导数的关系：fx0,x1…xk=fn(ξ)n!
则：fx=fx0+fx0,x1w1x+…+fx0,x1…xnwnx+fx,x0,x1…xn+1wn+1x
等距节点Newton插值公式：
Newton向前插值：Nna+th=fx+k=1n∆ky0tk，其中tk=tt-1…(t-k+1)k!
余项：Rnx=fn+1ξhn+1tn+1，t=x-x0h
Newton向后插值：Nnxn+th=fxn+k=1n∇kynt+k-1k
余项：Rnx=fn+1ξhn+1t+nn+1
Hermite插值：Hx=j=0nαjxyj+j=0nβjxy'j
αjx=Ax+Blj2x，βjx=Cx+Dlj2(x)
可得：αix=1-2x-xik=0k≠in1xi-xkli2(x)βix=x-xili2(x)
插值余项：R2n+1x=fx-H2n+1x=f2n+2ξ2n+2!wn+12(x)
待定系数：Hx=L0,1…n(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
对于附加弯矩约束条件：
2μ1λ22μ2λ32⋱⋱⋱μn-2λn-12M1M2M3⋮Mn-1=6fx0,x1,x2-λ1M06fx1,x2，x36fx2,x3，x4⋮6fxn-2,xn-1,xn-μn-1Mn
λiMi-1+2Mi+μiMi+1=6f[xi-1,xi,xi+1]
对于附加转角边界条件：
21λ12μ1λ22μ2⋱⋱⋱λn-12μn-112M0M1M2⋮Mn-1Mn=6fx0,x1-m0h1fx0,x1，x2fx1,x2，x3⋮fxn-2,xn-1,xnmn-fxn-2,xn-1,xnhn
对于附加周期性边界条件：
2λ0μ0λ12μ1λ22μ2⋱⋱⋱λn-22μn-2μn-1λn-22M0M1M2⋮Mn-2Mn-1=6{fx0,x1-fxn-1,xn}h1+hnfx0,x1，x2fx1,x2，x3⋮fxn-3,xn-2,xn-1fxn-2,xn-1,xn
sx=Mi-1(xi-x)36hi+Mi(x-xi-1)36hi+fxi-1-Mi-1hi26xi-xhi+[fxi-Mihi26]x-xi-1hi
上式保证了s(x)在相邻两点的连续性
第六章 函数逼近与曲线拟合
主要求法方程
第七章 数值积分与数值微分
求积公式具有m次代数精度的充要条件：
abxkdx=i=0nAixik，k=0,1…n，abxm+1dx≠i=0nAixim+1
插值型求积公式abfx=dx≈i=0nAif(xi)求积系数公式：Ai=ablixdx，i=0,1…n
Newton-Cotes（等分）
梯形求积公式（n=1），具有1次代数收敛精度abfxdx≈b-a2[fa+fb]
误差公式：E1f=-b-a312f''(η)
抛物型求积公式（Simpson求积公式，n=2），具有3次代数收敛精度
abfxdx≈b-a6[fa+4fa+b2+fb]
误差公式E2f=-b-a52880f（4）(η)
Newton求积公式（Simpon3/8法则） 具有3次代数收敛精度
Nf≈b-a8[fa+3fa+h+3fa+2h+fb，h=b-an
Cotes求积公式（n=4），具有5次收敛精度
abfxdx≈b-a90[7fa+32fa+h+12fa+2h+32fa+3h+7fb，h=b-an
误差公式E4f=-2（b-a)945(b-a4)6f（6）(η)
节点数为奇数时，代数精度为n;为偶数时，代数精度为n+1。代数精度都是奇数。
复化梯形求积公式：Tnf=h2[fa+2i=1n-1fxi+f(b)]
截断误差：Ern(f)=-b-a12h2f''(η)
复化Simpson公式：Snf=h6[fa+2i=1n-1fxi+4i=0n-1fxi+12+f(b)]
截断误差：Esnf=-b-a2880h4f4(η)
复化Cotes求积：
Cnf=h90[7fa+14i=1n-1fxi+32i=1n-1fxi+h4+12i=1n-1fxi+h2+32i=1n-1fxi+3h4+7fb]
截断误差：Ecnf=-2b-a945h46f6(η)
若一个复化积分公式的误差满足 limh→0R[f]hp=C<∞且C ¹ 0，则称该公式是 p 阶收敛的。
复化求积公式（需要2n+1个求积节点）
Romberg求积算法：
Sn=43T2n-13Tn
Cn=1615S2n-115Sn
Rn=6463C2n-163Cn
复化梯形求积公式：T2nf+13T2nf-Tnf=Sn(f)
复化Cotes求积公式：C2nf+163C2nf-Cnf=Rn(f)
Gauss型求积公式：
内积公式：p,ωn+1=abpxωn+1xρxdx
截断误差：Enf=f2n+1(η)2n+2!abωn+1x2ρxdx，η∈（a,b）
高斯求积公式代数精度为2n+1
Gauss-Legendre求积公式（注意区间（-1,1），变换可得）：形如：-11fxdx≈i=0nAif(xi)
求积系数可通过代数精度或插值型求积公式求积系数公式求出，亦可由下式求得：Ai=21-xi2[pn+1'x]2，i=0,1…n
截断误差：Enf=22n+3n+1!42n+32n+2!3f2n+2η，η∈（-1,1）
Gauss-Chebyshev求积公式：形如：1-1f(x)dx1-x2≈i=0nAif(xi)
求积系数：Ai=πn+1(i=0,1…n)(必为正)
截断误差：Enf=π22n+12n+2!f2n+2η，η∈（-1,1）
Gauss-Laguerre求积公式：形如：0∞f(x)e-xdx≈i=0nAif(xi)
求积系数：Ai=[n+1!]2xi[Ln+1'xi]2，i=0,1…n
截断误差：Enf=n+1!22n+1!f2n+2η，η∈（0，+∞）
Gauss-Hermite求积公式：形如：-∞+∞f(x)e-x2dx≈i=0nAif(xi)
求积系数：Ai=2n+2n+1!π[Hn+1'xi]2，i=0,1…n
截断误差：Enf=n+1!π2n+12n+2!f2n+2η，η∈（-∞，+∞）
三点数值微分公式：f'x=fx2-fx02h-h26f'''ξ2，ξ2∈（x0,x2)
泰勒级数展开：f'x0≈4Th2f;x0-Th(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)