现代数值计算方法公式总结.doc

现代数值计算方法公式
一、 插值法
1.拉格朗日（Lagrange）插值法
a)两点一次：
L1x=x-x1x0-x1y0+x-x0x1-x0y1
R1x=fx-L1x=f''ξ2!(x-x0)(x-x1) (x0<ξ<x1)
b)三点二次：
L2x=x-x1x-x2x0-x1x0-x2y0+x-x0x-x2x1-x0x1-x2y1+x-x0x-x1x2-x0x2-x1y2
R2x=fx-L2x=f3ξ3!(x-x0)(x-x1)(x-x2) (x0<ξ<x2)
2.牛顿（Newton）插值
a)n次牛顿法多项式：
Nnx=fx0+fx0,x1x-x0+…+fx0,x1,…xnx-x0…(x-xn-1)
Rnx=fx-Nnx=fn+1ξn+1!ωn+1x (x0<ξ<xn)
其中ωn+1x=x-x0x-x1…(x-xn-1)

XK
F(XK)
一阶差商
二阶差商
三阶差商
四阶差商
X0
f(x0)
f[x0,x1]
f[x1,x2]
f[x2,x3]
f[x3,x4]

f[x0,x1,x2,x3]
f[x1,x2,x3,x4]

X1
f(x1)
f[x0,x1,x2]

X2
f(x2)
f[x1,x2,x3]
f[x0,x1,x2,x3,x4]
X3
f(x3)
f[x2,x3,x4]

X4
f(x4)

fx0,x1=fx1-fx0x1-x0
fx0,x1,x2=f[x1,x2]-f[x0,x1]x2-x0
b)向前差分：
Nnx0+th=y0+tΔy0+…+tt-1t-2…(t-n+1)n!Δny0

Rnx0+th=tt-1t-2…t-nn+1!hn+1fn+1ξ (x0<ξ<xn)

XK
YK
ΔYI
Δ2YI
Δ3YI
Δ4YI
X0
y0
Δy0
Δy1
Δy2
Δy3

Δ3y0
Δ3y1

X1
y1
Δ2y0

X2
y2
Δ2y1
Δ4y0
X3
y3
Δ2y2

X4
y4

Δyi=YI+1-YI
Δ2yi=ΔYI+1-ΔYI
下减上

c)向后差分：
Nnxn+th=yn+t∇yn+…+tt+1…(t+n-1)n!∇nyn

Rnxn+th=tt+1t+2…t+nn+1!hn+1fn+1ξ (x0<ξ<xn)

XK
YK
∇YI
∇2YI
∇3YI
∇4YI
X4
y4
∇y4
∇y3
∇y2
∇y1

∇3y4
∇3y3

X3
y3
∇2y4

X2
y2
∇2y3
∇4y4
X1
y1
∇2y2

X0
y0

∇yi=yi-yi-1
∇2yi=∇yi-∇yi-1
上减下

3.三次埃米尔特（Hermite）插值
X
X0
X1
Y
Y0
Y0
Y'
M0
M1

H3X=A0XY0+A1XY1+Β0XM0+Β1(X)M1

A0X=(1+2X-X0X1-X0)(X-X1X0-X1)2
A1X=(1+2X-X1X0-X1)(X-X0X1-X0)2
Β0X=(X-X0)(X-X1X0-X1)2
Β1X=(X-X1)(X-X0X1-X0)2
R3X=F4Ξ4!(X-X0)2(X-X1)2 (x0<ξ<x1)
二、 拟合曲线（最小二乘）
φx=a0+a1x+a2x2
Sa0,a1,a2=i=1n[φxi-yi]2=i=1n[(a0+a1xi+a2xi2)-yi]2
∂S∂a0=0∂S∂a1=0∂S∂a2=0
三、 数值积分
1. 牛顿-柯特思（Newton-Cotes）公式
梯形求积公式（2节点）
I≈T1=b-a2[fa-f(b)]
RT1=-b-a312f''(η)
复化梯形求积公式
I≈h2[fa+2k=1n-1fxk+f(b)]≡Tn
RTn=-b-a12f''ηh2=O(h2)
辛普生求积公式（3节点）
I≈S1=b-a6fa+4fa+b2+fb
RS1=-b-a52880f4(η)
复化辛普生求积公式
I≈h6[fa+4k=0n-1fxk+12+2k=1n-1fxk+f(b)]
RSn=-b-a2880h4f4η=O(h4)

2. 高斯（Gauss）公式
高斯-勒让德求积公式
1. 先用勒让德公式求解xi
Lnx=12n∙n!dndxn[(x2-1)n]
2. 利用“高斯积分公式具有2n+1次代数精度”将xi带入求Ai
3. 将xi、Ai带入公式求取积分、并计算误差。
-11fx≈i=0nAifxi
Rnf=22n+3n+1!42n+32n+2!3f2n+2(ξ)
普通积分化标准形式：
I=abfxdx
积分区间[a,b]变换
x=b-a2t-a+b2
abfxdx=b-a2-11f(b-a2t+a+b2)dt
3. 代数精度
若求积公式对f(x)=1,x,x2,…xm时精确成立，而对f(x)=xm+1时不成立，则称此求积公式具有m次代数精确度

四、 解线性代数方程组的直接方法
三角形分解法
求解Ax=b，先将A分解为A=LU，则原式变为Ux=y，那么问题就变为了求解
Ly=bUx=y
五、 解线性代数方程的迭代法
1. 范数
向量范数
定义：
设 x∈Rn(or Cn) 其中R为实数域、C为复数域，若某实值函数N(x)≡||x||满足条件
1） 非负性 ||x||≥0，||x||=0当且仅当x=0成立
2） 其次行 ax=a ||x||
3） 三角不等式 x+y≤x+||y||
称N(x)≡||x||为Rn(or Cn)域上的一个向量范数
常见范数：
||x||∞=max1≤i≤n|xi|
||x||1=i=1n|xi|
||x||2=[i=1n|xi|2]1/2
矩阵范数
定义：
设 A∈Rn×n(or Cn×n) 其中R为实数域、C为复数域，若某实值函数N(A)≡||A||满足条件
1） 非负性 ||A||≥0，||A||=0当且仅当A=0成立
2） 其次行 aA=a ||A||
3） 三角不等式 A+B≤A+||B||
4） 乘积性质 AB≤A B
称N(A)≡||A||为Rn×n(or Cn×n)域上的一个矩阵范数
常见范数：
||A||∞=max1≤i≤nj=1naij(行范数)
||A||1=max1≤j≤ni=1naij(列范数)
||A||2=λ1,λ1为ATA的最大按模特征值
||A||F=[i,j=1naij2]1/2
2. 谱半径
ρA=max1≤i≤n|λi|
3. 雅可比迭代
向量：
用第i个方程解出xi的方程，分量通式如下：
xik+1=1aii(bi-j=1j≠inaijxj(k))
矩阵：
对于Ax=b，先将A拆分成对角线矩阵D减去下三角矩阵L，再减去上三角矩阵U。
xk+1=BJxk+fJ
其中
BJ=D-1L+U,fJ=D-1b
4. 高斯-塞德尔迭代
向量：
用第i个方程解出xi的方程，并将上式得到的xi(k+1)带入下边的公式，分量通式如下：
xik+1=1aii(bi-j=1i-1aijxj(k+1)-j=i+1naijxj(k))
矩阵：
对于Ax=b，先将A拆分成对角线矩阵D减去下三角矩阵L，再减去上三角矩阵U。
xk+1=BSxk+fS
其中
BS=(D-L)-1U,fS=(D-L)-1b
5. 松弛迭代
雅可比松弛（JOR）：
x(k+1)=I-ωD-1Axk+ωD-1b
注： 当0<ω<2λi时，收敛
雅可比方法收敛时，0<ω<1收敛
逐次超松弛（SOR）：
xik+1=ωaii(bi-j=1i-1aijxj(k+1)-j=i+1naijxj(k))
注： 系数矩阵A对称正定，0<ω<2时收敛
六、 方程求根
1. 大范围收敛定理
a) j(x)在[a,b]上连续；
b) 当xÎ[a,b]时，j(x) Î[a,b]；
c) j’(x)存在，且对任意xÎ[a,b]有
|φ(x)|≤L<1
2. 牛顿迭代法
xk+1=xk-f(xk)f'(xk)
牛顿下山法xk+1=xk-λfxkf'xk，其中λ≤1
3. 割线法
xk+1=xk-xk-xk-1fxk-fxk-1fxk
七、 矩阵特征问题求解
1. 规范化乘幂法
y(k)=xk/max⁡(x(k))x(k+1)=Ay(k)
2. 原点位移乘幂法
取一个l0，用B=A-I*l0替代A，则得到的特征值ui=li-l0，特征向量不变
八、 常微分方程的数值解法
1. 欧拉公式
yn+1=yn+hf(xn,yn)yx0=y0
2. 向后欧拉公式
yn+1=yn+hf(xn+1,yn+1)yx0=y0
3. 梯形公式
yn+1=yn+h2[fxn,yn+f(xn+1,yn+1)]yx0=y0
4. 改进欧拉公式
yn+1=yn+h2[fxn,yn+f(xn+1,yn+hf(xn,yn))]