第一章 误差
1. 误差的分类
- 模型误差:数学模型本身包含的误差;
- 观测误差:观测结果带来的误差;
- 数据误差:数据可能由先前的计算等途径得到,从而导致的误差;
- 截断误差(方法误差):模型的准确解和用数值方法求得的解之差;
- 舍入误差:计算过程中只能取有限位数字进行运算而引来的误差.
2. 近似计算中需要注意的一些现象
- 要避免两个相近的数相减;
- 两个相差很大的数进行运算时,要防止小的那个数被“吃掉”;
- 要注意计算步骤的简化,减少运算次数;
- 要避免做被除数的绝对值远远大于除数绝对值的除法;
- 要选用数值稳定的计算公式.
第二章 插值法与数值微分
1. 线性插值
线性插值就是用直线近似地代替函数 f(x) 。用两个点( x0 , y0 )和( x1 , y1 )通过两点式来构建直线方程 ϕ1(x) ,得到的 ϕ1(x) 就是插值函数:
ϕ1(x)=y0x0−x1x−x1+y1x1−x0x−x0
记 l0(x) = x0−x1x−x1 , l1(x) = x1−x0x−x0 ,并把 l0(x) 叫做 x0 的一次插值基函数, l1(x) 叫做 x1 的一次插值基函数.
Lagrange 插值
插值函数 ϕ1(x) 是两个插值基函数 l0(x) 和 l1(x) 的线性组合,其组合系数就是对应点的函数值 y0 和 y1 ,即:
ϕ1(x)=y0l0(x)+y1l1(x)
这种形式的插值函数称为 Lagrange 插值。
Newton 插值
把直线用点斜式表示,有:
ϕ1(x)=y0+x1−x0f(x1)−f(x0)(x−x0)
函数 f(x) 在 xi , xj 的一阶均方差的定义是:
f[xi,xj]=xi−xjf(xi)−f(xj)
利用均方差的对称性,可以将点斜式表示为:
ϕ1(x)=y0+(x−x0)f[x0,x1]
这种形式的插值叫做 Newton 插值。
2. 二次插值
过三个点 ( x0 , y0 ),( x1 , y1 ) 和 ( x2 , y2 ) 来构造 y=f(x) 的插值函数,就是二次插值(该插值函数的次数不高于二次)。
二次 Lagrange 插值
二次拉格朗日插值多项式为 ϕ2(x)=y0l0(x)+y1l1(x)+y2l2(x) ,其中三个插值基函数分别为:
l0(x)=(x0−x1)(x0−x2)(x−x1)(x−x2)
l1(x)=(x1−x0)(x1−x2)(x−x0)(x−x2)
l2(x)=(x2−x0)(x2−x1)(x−x0)(x−x1)
二次 Newton 插值
二次牛顿插值多项式为:
ϕ2(x)=f(x0)+(x−x0)f[x0,x1]+(x−x0)(x−x1)f[x0,x1,x2]=f(x0)+(x−x0)x0−x1f(x0)−f(x1)+(x−x0)(x−x1)x0−x2f[x0−x1]−f[x1−x2]
3. n 次插值
n 次 Lagrange 插值
n 次拉格朗日插值多项式为:
ϕn(x)=i=0∑nyili(x)
其中插值基函数 li(x) 为:
li(x)=(xi−x0)...(xi−xi−1)(xi−xi+1)...(xi−xn)(x−x0)...(x−xi−1)(x−xi+1)...(x−xn),i=0,1,2,...,n
li(x) 还有另一种形式:
li(x)=i=0∑n(x−xi)ωn′(xi)ωn(x)
其中,
ωn(x)=(x−x0)(x−x1)...(x−xn)ωn′(xi)=(xi−x0)...(xi−xi−1)(xi−xi+1)...(xi−xn)
n 次 Newton 插值
n 次牛顿插值多项式需要先构造均差表(差商表):
x |
y |
f[xi,xj] |
f[xi,xj,xk] |
... |
f[x0,x1,...,xn] |
x0 |
y0 |
|
|
|
|
x1 |
y1 |
f[x0,x1] |
|
|
|
x2 |
y2 |
f[x1,x2] |
f[x0,x1,x2] |
|
|
x3 |
y3 |
f[x2,x3] |
f[x1,x2,x3] |
... |
|
... |
... |
... |
... |
... |
|
xn |
yn |
f[xn−1,xn] |
f[xn−2,xn−1,xn] |
... |
f[x0,x1,...,xn] |
其中 f[x0,x1,...,xn] 是 n 阶均差,它的表达式为:
f[x0,x1,...,xn]=x0−xnf[x0,x1,...,xn−1]−f[x1,x2,...,xn]
利用均差表,可以写出 n 次牛顿插值多项式:
n 次牛顿插值多项式中的所含均差都是均差表中对角线上的项。
ϕn(x)=f(x0)+(x−x0)f[x0,x1]+(x−x0)(x−x1)f[x0,x1,x2]+...+(x−x0)(x−x1)...(x−xn−1)f[x0,x1,...,xn]
4. Hermite 插值
若给定 n+1 个结点和相应的函数值与微商值,可以构造 2n+1 次的 Hermite 插值多项式 H(x) :
- H(x) 是不超过 2n+1 次的插值多项式;
- H(xi)=yi , H′(x)=yi′(i=0,1,2,...,n) .
H(x)=∑i=0n[yihi(x)+yi′Hi(x)]
由上述条件可知:
hi(xj)={1,0,i=ji=j(j=0,1,2,...,n)
hi′(xj)=0,j=0,1,2,...,n
Hi′(xj)={1,0,i=ji=j(j=0,1,2,...,n)
Hi(xj)=0,j=0,1,2,...,n
第三章 数据拟合法
1. 正交多项式
Legendre 多项式
Pn(x)=2nn!1dxndn(x2−1)n,n=0,1,2,⋯
Laguerre 多项式
Ln(x)=exdxndn(xne−x),n=0,1,2,⋯
Chebyshev 多项式
Tn(x)=cos(narccosx)=21[(x+x2−1)n+(x−x2−1)n],∣x∣≤1
第五章 数值积分
1. 梯形求积公式
梯形求积公式就是过 (a,f(a)) 和 (b,f(b)) 两点做直线 P1(x) ,用 P1(x) 来代替 f(x) :
∫abf(x)dx≈∫abP1(x)dx=2b−a[f(a)+f(b)]
2. 抛物线求积公式(Simpson 公式)
将 [a,b] 区间二等分,过点 (a,f(a)) , (2a+b,f(2a+b)) 和 (b,f(b)) 三点做抛物线 P2(x) ,用 P2(x) 来代替 f(x) :
∫abf(x)dx≈∫abP2(x)dx=6b−a[f(a)+4f(2a+b)+f(b)]
3. Newton-Cotes 公式
把区间 [a,b] 作 n 等分,分点为:
xi=a+ih,i=0,1,2,...,n,h=na+b
过这 n+1 个节点,构造一个 n 次多项式:
Pn(x)=i=0∑n(x−xi)ω′(xi)ω(x)f(xi)
其中 ω(x)=(x−x0)(x−x1)...(x−xn) ,用 Pn(x) 代替被积函数 f(x) ,有:
∫abf(x)dx≈∫abPn(x)dx=i=0∑nAif(xi)=(b−a)i=0∑nci(n)f(xi)
其中 ci(n) 是不依赖于函数 f(x) 和区间 [a,b] 的常数,叫做 Newton-Cotes 系数,它的值如下表所示:
期末考试只要求掌握到 n=4 的情况即可.
n |
c0(n) |
c1(n) |
c2(n) |
c3(n) |
c4(n) |
1 |
21 |
21 |
|
|
|
2 |
61 |
64 |
61 |
|
|
3 |
81 |
83 |
83 |
81 |
|
4 |
907 |
4516 |
152 |
4516 |
907 |
Newton-Cotes 公式的代数精度
对一个一般求积公式
∫abf(x)dx≈k=0∑nAkf(xk)
若 f(x) 为一个次数不高于 m 次的代数多项式时,上式等号成立,但当 f(x) 为 m+1 次多项式时,上式不能精确成立,说明该求积公式具有 m 次代数精度.
- 若 f(x) 是 n 次多项式,则 f(n+1)≡0 ,所以 f(x)=Pn(x) ,Newton-Cotes 公式代数精度至少为 n.
- 当 n 为偶数时,Newton-Cotes 公式的代数精度可达到 n+1.
4. 复化梯形公式
将区间 [a,b] 作 n 等分,节点 xk=a+kh(k=0,1,2,...,n,h=nb−a) .对每个小区间 [xk,xk+1] 使用梯形求积公式,有:
I=∫abf(x)dx=k=0∑n∫xkxk+1f(x)dx≈k=0∑n2xk+1−xk[f(xk)+f(xk+1)]=2h[f(a)+f(b)+2k=1∑n−1f(a+kh)]
记复化梯形公式 Tn 为:
Tn=2h[f(a)+f(b)+2k=1∑n−1f(a+kh)]
5. 复化抛物线公式
由于抛物线求积公式用到了区间的中点,所以在构造复化抛物线公式时必须将区间 [a,b] 进行 2n 等分,在每个小区间 [x2k−2,x2k] 上使用抛物线求积公式:
∫x2k−2x2kf(x)dx≈k=1∑n62h[f(x2k−2)+4f(x2k−1)+f(x2k)],h=2nb−a
于是有:
I=∫abf(x)dx=k=1∑n∫x2k−2x2kf(x)dx≈k=1∑n3h[f(x2k−2)+4f(x2k−1)+f(x2k)]=3h[f(a)+f(b)+4k=1∑nf(x2k−1)+2k=1∑n−1f(x2k)]
记复化抛物线公式 Sn 为:
Sn=3h[f(a)+f(b)+4k=1∑nf(x2k−1)+2k=1∑n−1f(x2k)]
第六章 解线性代数方程组的直接法
1. LU 分解法
当矩阵 A 的前 n-1 个顺序主子式都不为零时,矩阵 A 可以唯一地分解为两个三角矩阵的乘积:
A=LU
其中 L 是单位下三角矩阵, U 是上三角矩阵。
如何求 LU 分解矩阵:
- 利用初等行变换将矩阵 A 化为上三角矩阵 U;
- 有下三角可逆矩阵 P,使得 PA=U,从而有 LU 分解: A=P−1U(L=P−1) .
原方程 Ax=b 等价于 LUx=b ,令 Ux=y ,有
Ly=b
从 Ly=b 中解出 y ,再将 y 代入 Ux=y 解出 x 即可.
2. 向量范数
向量范数
任一向量 x∈Rn ,对应一个非负实数 ∥x∥ ,具有下面三个性质:
- 正定性:对所有的 x∈Rn 有 ∥x∥≥0 ,而且 ∥x∥=0 当且仅当 x=0 .
- 齐次性:对所有的 x∈Rn 和 α∈R ,有 ∥αx∥=∣α∣⋅∥x∥ .
- 三角不等式:对所有的 x,y∈Rn ,有: ∥x+y∥≤∥x∥+∥y∥ .
则称 ∥x∥ 为向量 x 的范数.
常见向量范数
常见的向量范数有:
- 1 范数: ∥x∥1=∑i=1n∣xi∣
- 2 范数: ∥x∥2=(∑i=1nxi2)21
- ∞ 范数: ∥x∥∞=max(∣x1∣,∣x2∣,...,∣xn∣)
- p 范数: ∥x∥p=(∑i=1n∣xi∣p)p1,p≥1
3. 矩阵范数
矩阵范数
设 A 是一个 n × n 的实矩阵,按一定规则对应一个非负实数 ∥A∥ ,称为矩阵 A 的范数,必须满足以下四个性质:
- 正定性:对所有的 A∈Rn×n 有 ∥A∥≥0 ,而且 ∥A∥=0 当且仅当 A=0 .
- 齐次性:对所有的 A∈Rn×n 和 α∈R 有 ∥αA∥=∣α∣⋅∣A∣ .
- 三角不等式:对所有的 A,B∈Rn×n 有 ∥A+B∥≤∥A∥+∥B∥ .
- 相容性:对所有的 A,B∈Rn×n 有 ∥AB∥≤∥A∥⋅∥B∥ .
常见矩阵范数
常见的矩阵范数有:
- 1 范数(列和范数): ∥A∥1=max∑i=1n∣aij∣(1≤j≤n)
- 2 范数: ∥A∥2=λ1 , λ1 为矩阵 ATA 的最大特征值
- ∞ 范数(行和范数): ∥A∥∞=max∑j=1n∣aij∣(1≤i≤n)
- F 范数: ∥A∥F=(∑i,j=1n∣aij2∣)21
4. 谱半径
设 n × n 阶矩阵 A 的特征值为 λi(i=1,2,...,n) ,则称
ρ(A)=max∣λi∣(1≤i≤n)
为矩阵 A 的谱半径.
5. 条件数
条件数
数 ∥A∥⋅∥A−1∥ 称为矩阵 A 的条件数,记为 Cond(A) 。
当线性方程组的系数矩阵 A 的条件数 Cond(A) 很大时,说明在系数矩阵或右端项产生微小变化时会引起解的巨大变化,则称此方程组是“病态”方程组,否则称方程组为“良态”方程组。
条件数和范数有关,可以在条件数上加下标,对应的范数也应加相同的下标:
Cond(A)∞=∥A∥∞⋅∥A−1∥∞Cond(A)2=∥A∥2⋅∥A−1∥2=λ1/λn
其中, λ1 , λn 是矩阵 ATA 的最大和最小特征值,故 Cond(A)2 又称谱条件数。
条件数的性质
- Cond(A)≥1 .
- 单位矩阵、置换矩阵和正交矩阵的谱条件数都为 1.
- 对任意非零实数 α ,有 Cond(αA)=Cond(A) .
第八章 解线性方程组的迭代法
1. Jacobi 迭代
设有方程组
⎩⎨⎧a11x1+a12x2+...+a1nxn=b1a21x1+a22x2+...+a2nxn=b2............an1x1+an2x2+...+annxn=bn
用矩阵表示为
Ax=b
假设 aii=0 ,令
{bij=−aij/aii,i=jgi=bi/aii,i=1,2,...,n
方程组可改写成
⎩⎨⎧x1=b12x2+b13x3+...+b1nxn+g1x2=b21x1+b23x3+...+b2nxn+g2............xn=bn1x1+bn2x2+bn3x3+...+bn,n−1xn−1+gn
若令
B=0b21⋮bn1b120⋮bn2b13b23⋮bn3⋯⋯⋯b1nb2n⋮0
D=a11a22⋱ann,g=g1g2⋮g3
则
B=D−1(D−A)=I−D−1A,g=D−1b
方程可用矩阵表示为
x=Bx+g
选取初始向量 x(0)=(x1(0),x2(0),⋯,xn(0))T ,代入 x(1)=Bx(0)+g 得到一个新向量 x(1)=(x1(1),x2(1),⋯,xn(1))T ,再将 x(1) 代入 x(2)=Bx(1)+g ,可以得到 x(2) ,依此类推,可得到迭代格式
⎩⎨⎧x1(k+1)=b12x2(k)+b13x3(k)+...+b1nxn(k)+g1x2(k+1)=b21x1(k)+b23x3(k)+...+b2nxn(k)+g2............xn(k+1)=bn1x1(k)+bn2x2(k)+bn3x3(k)+...+bn,n−1xn−1(k)+gn
即
x(k+1)=Bx(k)+g,k=0,1,2,⋯
通过上式的计算,可得到向量序列 {x(k)} ,当 k→+∞ 时,若序列 {x(k)} 收敛到 x∗ , x∗ 就是方程组的解. 以上计算过程过程称为 Jacobi 迭代法,矩阵 B 为 jacobi 迭代法的迭代矩阵。
2. Gauss-Seidel 迭代
Gauss-Seidel 迭代法和 Jacobi 迭代法相似,但不同点是:在计算 xi(k+1) 时,Jacobi 迭代法用 (x1(k),x2(k),...,xn(k))T 代入迭代公式,而 Gauss-Seidel 迭代法会利用之前已经计算出的结果,用 (x1(k+1),x2(k+1),...,xi−1(k+1),xi+1(k),...,xn(k))T 代入迭代公式进行计算.
其迭代过程为:
⎩⎨⎧x1(k+1)=b12x2(k)+b13x3(k)+...+b1nxn(k)+g1x2(k+1)=b21x1(k+1)+b23x3(k)+...+b2nxn(k)+g2............xn(k+1)=bn1x1(k+1)+bn2x2(k+1)+bn3x3(k+1)+...+bn,n−1xn−1(k+1)+gn
令
L=0b21b31⋮bn10b32⋮bn20⋯⋱0,U=0b120b13b230⋯⋯⋱b1nb2n⋮bn−1,n0
迭代过程用矩阵表示为
x(k+1)=Lx(k+1)+Ux(k)+g,k=0,1,2,⋯
因 (I−L) 存在,所以上述迭代格式可表示为
x(k+1)=(I−L)−1Ux(k)+(I−L)−1g
称 B1=(I−L)−1U 为 Gauss-Seidel 迭代法的迭代矩阵.
注意:
交换方程和未知数的次序都会影响 Gauss-Seidel 迭代法的计算结果,但这种交换对 Jacobi 迭代法没有影响.
3. 迭代法的收敛性判别
定理 1
Jacobi 迭代法和 Gauss-Seidel 迭代法收敛的充分必要条件是迭代矩阵的谱半径小于 1.
定理 2
若迭代矩阵 M 的范数 ∥M∥<1 ,则 Jacobi 迭代和 Gauss-Seidel 迭代一定收敛,但这只是迭代收敛的充分条件(因为 ρ(M)≤∥M∥ ).
定理 3
若方程组 Ax=b 的系数矩阵 A 按行严格对角占优或按列严格对角占优,即满足条件
aii>j=1,i=j∑naij,i=1,2,⋯,n
或
aii>i=1,i=j∑naij,j=1,2,⋯,n
则 Jacobi 迭代法和 Gauss-Seidel 迭代法都收敛.
定理 4
若方程组 Ax=b 的系数矩阵 A 为对称正定矩阵,则 Gauss-Seidel 迭代法收敛.
注意:
通常判断 Jacobi 或 Gauss-Seidel 迭代法是否收敛,先看方程组的系数矩阵 A 是否按行严格对角占优或按列严格对角占优,若严格对角占优,则收敛;否则,继续判断对应迭代矩阵的谱半径是否小于 1,小于 1 则收敛,否则不收敛.
第十章 非线性方程组及非线性方程组解法
1. 二分法
- 找出 f(x)=0 的根所在区间 (a,b) ,并计算出端点的函数值 f(a),f(b) .
- 计算 f(x) 在区间中点的值 f(2a+b) .
- 若 f(2a+b)≈0 ,则停止迭代. 否则,若 f(2a+b) 与 f(a) 异号,则根位于 (a,2a+b) 中,用 2a+b 代替 b ; 若 f(2a+b) 与 f(b) 异号,则根位于 (2a+b,b) 中,用 2a+b 代替 a .
- 重复上述过程中的第二步和第三步,直到区间缩小到容许误差范围之内.
2. 等步长扫描法
设 h 是给定的步长,方程 f(x)=0 的有根区间为 [a,b] ,一般初始时 h 取 0.1,取 x0=a,x1=a+h ,若 f(x0)f(x1)<0 表明扫描成功;否则令 x0=x1,x1=x0+h ,继续上述方法,直到成功. 若 x1>b 表明扫描失败,将 h 缩小(一般 h 按照 10 的倍数进行缩小,从 0.1 到 0.01 再到 0.001 等等),重新开始扫描.
3. 简单迭代法
若给定方程 f(x)=0 后,把它改写成等价形式:
x=ϕ(x)
再作迭代
xn+1=ϕ(xn)
简单迭代法敛散性判别
- 若 ∣ϕ′(x)∣<1 ,则简单迭代法收敛.
- 若 ϕ′(ξ)=⋯=ϕ(p−1)(ξ)=0,ϕ(p)(ξ)=0, ,则迭代在 ξ 处 p 阶收敛.
4. 牛顿法
xn+1=xn−f′(xn)f(xn)
5. 弦截法
xn+1=xn−f(xn)−f(xn−1)f(xn)(xn−xn−1)
第十一章 常微分方程初值问题的数值解法
1. Euler 方法(显示欧拉法)
⎩⎨⎧yn+1=yn+hf(xn,yn)n=0,1,2,⋯,N−1y(x0)=y0y′=f(x,y)
2. 向后 Euler 方法(隐式欧拉法)
⎩⎨⎧yn+1=yn+hf(xn+1,yn+1)n=0,1,2,⋯y(x0)=y0y′=f(x,y)
3. 改进 Euler 方法
⎩⎨⎧yn+1=yn+2h[f(xn,yn)+f(xn+1,yn+hf(xn,yn))]n=0,1,2,⋯y(x0)=y0y′=f(x,y)
4. 梯形公式
⎩⎨⎧yn+1(0)=yn+hf(xn,yn)yn+1(k+1)=yn+2h[f(xn,yn)+f(xn+1,yn+1(k))]k=0,1,2,⋯y′=f(x,y)
注意:
- 使用改进 Euler 方法进行迭代时,需要解隐式方程.
- 若题中不给出迭代步长 h,则 h=0.1.
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于