- 绪论
- 有效数字判断
- 有效数字 d 是满足 Ep<2101−d(1st) 或 Rp<2101−d(2nd) 的最大正整数。
- 0.005<2101−2,有效数字 2 位;0.0015<2101−3,有效数字 3 位。
- 非线性方程解法
- 收敛阶
- 设迭代 xk+1=g(xk) 收敛到不动点 x∗,记绝对误差 ek=xk−x∗,若 k→∞limekpek+1=C=0,则收敛阶为 p。
- p=1 为线性收敛,此时必有 C<1;p=2 为二次收敛;p>1 称为超线性收敛。
- 不动点迭代
- 将 f(x)=0 等价变换为 x=g(x),利用不动点迭代 xk+1=g(xk) 找到不动点,不动点就是根。
- 若 a≤g(x)≤b 对一切 x∈[a,b] 成立,则存在不动点;同时又有 0≤L<1,使得 ∣g′(x)∣≤L 对一切 x∈[a,b] 成立,则存在唯一不动点。
- ek+1=xk+1−x∗=g(xk)−g(x∗)=g′(ξ)ek,其中 ξ 在 xk 和 xk+1 之间;若 g(x∗)=0,取极限得 k→∞lim=ekek+1=g′(x∗),线性收敛。
- 二分法
- f(a)f(b)<0,有根。
- 二等分区间长度,直到满足精度为止。
- 终止条件 ∣xk+1−xk∣<ε。
- ∣x∗−xk∣=2bk+ak−x∗≤2bk−ak=2k+1b−a≤ε,满足精度的 k=⌈log2εb−a⌉−1。
- 试值法
- 令 c=b−f(b)−f(a)f(b)(b−a),根据零点存在定理判断根的位置。
- 缺点:尽管区间宽度越来越小,但它可能不趋近于0。
- 牛顿迭代
- 用Taylor展开近似 f(xk)+f′(xk)(x−xk)≈0,得到迭代 xk+1=xk−f′(xk)f(xk)。
- 牛顿迭代对初值要求比较高,x0 必须充分靠近 x∗,才能保证局部收敛。
- 根据Taylor展开式,f(x∗)=f(xk)+f′(xk)(x∗−xk)+21f′′(ξ)(x∗−xk)2=0,可得 xk−x∗−f′(xk)f(xk)=2f′(xk)f′′(ξ)(x∗−xk)2,即 k→∞limek2ek+1=2f′(x∗)f′′(x∗),牛顿迭代的收敛阶至少为2。
- 割线法
- 计算导数不方便,因此用 xk−xk−1f(xk)−f(xk−1) 近似 f′(xk)。
- 迭代式 xk+1=xk−f(xk)−f(xk−1)f(xk)(xk−xk−1)。
- 收敛阶 25+1≈1.618。
- 方程组的数值解法
- 向量范数
- ∣∣x∣∣1=i=1∑n∣xi∣
- ∣∣x∣∣2=i=1∑nxi2
- ∣∣x∣∣∞=1≤i≤nmax∣xi∣
- 矩阵范数
- ∣∣A∣∣1=1≤j≤nmaxi=1∑n∣aij∣,列和范数。
- ∣∣A∣∣∞=1≤i≤nmaxj=1∑n∣aij∣,行和范数。
- ∣∣A∣∣2=ρ(ATA),谱范数。
- 高斯消元
- 消去运算量:共需要消去 n−1 次,每次消去时选择第 k 行共 n−k+1 个数与下方 n−k 行相减,k=1∑n−1(n−k)(n−k+1)=3n3−n。
- 回带运算量:第 k 行需要回代 xn,xn−1⋯,xk+1,再求出 xk,共需要 k=1∑n(n−k+1)=2n(n+1)。
- 选主元策略:在剩余行中选择开头绝对值最大的非零元素座位主元,然后初等行变换到对角线上。
- LU分解
- L 为下三角矩阵,且对角线为 1,U 为上三角矩阵。
- 求 Ax=b,首先令 A=LU,那么有 LUx=b;令 y=Ux,问题转化为求两个方程 Ly=b、Ux=y。
- 首先令 L=E,U=A,可逐渐构造出分解形式。
- 雅可比迭代
- xi(k+1)=aiibi−j=1∑i−1aijxj(k)−j=i+1∑naijxj(k)
- 高斯-赛德尔迭代
- xi(k+1)=aiibi−j=1∑i−1aijxj(k+1)−j=i+1∑naijxj(k)
- 插值
- 拉格朗日插值
- 拉格朗日插值多项式 Ln(x)=i=0∑nyij=ij=0∏nxi−xjx−xj
- 余项 Rn(x)=(n+1)!f(n+1)(ξ)i=0∏n(x−xi)ξ∈(a,b)
- 牛顿插值
- 定义 0 阶均差 f[xi]=f(xi),则定义了 m−1 阶均差后,m 阶均差 f[x0,x1,⋯,xm]=xm−x0f[x1,x2,⋯,xm]−f[x0,x1,⋯,xm−1],这类似多阶差分的概念。
- 牛顿插值多项式 Nn(x)=f(x0)+i=1∑nf[x0,x1,⋯,xi]j=0∏i−1(x−xj)
- 余项 Rn(x)=(n+1)!f(n+1)(ξ)i=0∏n(x−xi)=f[x,x0,x1,⋯,xn]i=0∏n(x−xi)
- 埃尔米特插值
- 共有 n+1 个互异点,要求 H(xi)=f(xi) 且 H′(xi)=f′(xi);于是有 2n+2 个方程,可构造 2n+1 次埃尔米特插值多项式 H2n+1(x)。
- 一般直接设多项式的系数,列方程求解系数。
- 余项 R2n+1(x)=(2n+2)!f(2n+2)(ξ)[i=0∏n(x−xi)]2
- 分段线性插值
- 每一小段都用直线拟合。
- S(x)=i=0∑nli(x)f(xi),其中 li(x)=⎩⎨⎧xi−xi−1x−xi−1xi−xi+1x−xi+10xi−1≤x≤xixi≤x≤xi+10≤x<xi−1或xi<x≤b。
- 当 x∈[xi,xi+1],只有 li(x) 在区间 [xi,xi+1] 和 li+1(x) 在区间 [xi,xi+1] 不为零,正好是区间内的线性插值 xi−xi+1x−xi+1f(xi)+xi+1−xix−xif(xi+1)。
- 三次样条插值 S(x) 定义
- 函数 S(x) 定义在区间 [a,b] 上,给定 n+1 个节点 a=x0<x1<⋯<xn=b,和与之对应的 f(x0),f(x1),⋯,f(xn)。
- 在每个节点上满足 S(xi)=f(xi)(i=1,2,⋯,n)。
- 在 [a,b] 上有连续的零阶、一阶、二阶导数。
- 在每个小区间 [xi,xi+1](i=0,1,⋯,n−1) 上是三次多项式。
- 拟合
- 实际函数 f(x),拟合函数 φ(x),对于参考点 xi,有残差 εi=φ(xi)−f(xi)。
- 最小二乘法
- 要求 i=1∑nεi2 最小。
- 线性拟合
- 对于给定点 (xi,yi) (i=1,2,⋯,n),设拟合函数 y(x)=a0+a1x,则要求 F(a0,a1)=i=1∑n(a0+a1xi−yi)2 最小。
- 令 F 各个方向偏导数为 0,可解得系数。
- 多项式拟合
- 令拟合的多项式为 y(x)=a0+a1x+⋯anxm。
- 有方程组 ⎩⎨⎧a0n+a1i=1∑nxi+⋯+ami=1∑nxim=i=1∑nyia0i=1∑nxi+a1i=1∑nxi2+⋯+ami=1∑nxim+1=i=1∑nxiyi⋮a0i=1∑nxim+a1i=1∑nxim+1+⋯+ami=1∑nxi2m=i=1∑nximyi
- 将非线性拟合转化为多项式拟合
- y=axb→lny=blnx+lna
- y=axμ+c
- y=ax+bx→y1=bx1+a
- y=ax+b1→y1=ax+b
- 数值积分
- 代数精度:使得 I(pm)=Q(pm) 的最高 m 次多项式。验证求积公式有 m 次代数精度,只需验证 ∀f(x)=1,x,x2,⋯,xm 有 I(f)=Q(f) 精确成立,但 I(xm+1)=Q(xm+1)。
- Newton-Cotes公式
- 原积分式 I(f)=∫abf(x)dx,用 f(x)≈i=0∑nli(x)f(xi) 近似,得到近似值 Q(f)=∫ab[i=0∑nli(x)f(xi)]=i=0∑n[∫abli(x)]f(xi)。
- n 次插值型求积公式代数精度至少为 n 次。
- 梯形求积公式 Q(f)=2b−a[f(a)+f(b)],代数精度1。
- 辛普森求积公式 Q(f)=6b−a[f(a)+4f(2a+b)+f(b)],代数精度3。
- 辛普森 83 求积公式 Q(f)=8b−a[f(a)+3f(32a+b)+3f(3a+2b)+f(b)],代数精度3。
- 科特斯求积公式 Q(f)=90b−a[7f(a)+32f(43a+b)+12f(2a+b)+32f(4a+3b)+7f(b)],代数精度5。
- 复化求积公式
- 定步长:将 [a,b] 分成 n 等分 [xi,xi+1],其中 xi=a+ih,h=nb−a,$ (i=0,1,\cdots,n)$。
- 复化梯形公式 I=2h[f(a)+2i=1∑n−1f(xi)+f(b)]
- 复化辛普森公式 I=6h[f(a)+4i=0∑n−1f(xi+21)+2i=1∑n−1f(xi)+f(b)]
- 变步长算法,将区间不断对分,取区间数 n=2k,设区间数为 n 时的积分值为 In,当 ∣I2n−In∣<ε 时停止计算。
- 变步长梯形公式
- Tn=2h[f(a)+2i=1∑n−1f(xi)+f(b)],h=nb−a。
- T2n=21Tn+2hi=0∑n−1f(xi+21)。
- 变步长辛普森公式 Sn=4−14T2n−Tn
- 变步长科特斯公式 Cn=42−142S2n−Sn
- 变步长龙贝格公式 Rn=43−143C2n−Cn
- 自动选步长,求余项 maxR≤ε。
- 高斯求积公式
- 若存在 n+1 个节点 xi∈[a,b] 及求积系数 Ai,使求积公式 i=0∑nAif(xi) 有 2n+1 次代数精度,则成 xi 为高斯点,Ai 为高斯系数,求积公式为高斯求积公式。
- 区间 [−1,1] 上几个简单的高斯求积公式
- n=02f(0)
- n=1f(−31)+f(31)
- n=295f(−515)+98f(0)+95f(515)
- 数值优化
- 搜索的核心是找到 [a,b] 区间上下凸函数 f(x) 的极小值。
- 黄金分割搜索
- 取 c=0.382(b−a),取 f1=f(c)。
- 取 d=0.618(b−a),取 f2=f(d)。
- 若 ∣a−b∣<ε,则取极小值点 ans=2a+b,停止,否则继续搜索。
- 若 f1<f2,则压缩右边区间,令 b=d,d=c,f2=f1,重新计算 c、f1;若 f1>f2,则压缩左边区间,令 a=c,c=d,f1=f2,重新计算 d、f2;若 f(c)=f(d),则令 a=c,b=d,重新计算 c、d、f1、f2。
- 斐波那契搜索
- 第 i 次迭代的区间为 [ai,bi],参考点 ci=ai+(1−Fn−iFn−i−1)(bi−ai)、di=ai+Fn−iFn−i−1(bi−ai),其中 ri=Fn−iFn−i−1。
- 要求精度 Fn>εb0−a0。
- 微分方程求解
- 欧拉法
- 考查初值问题 {dxdy=f(x,y)y(x0)=y0,x≥x0,将区间 [a,b] 划分为 n 个等距子区间,并选择网格点 xi,i=0,1,⋯,n,步长 h=nb−a。
- 欧拉格式 {y0=y(x0)yi+1=yi+hf(xi,yi)
- 几何意义:用一条折线近似代替积分曲线。
- 欧拉法具有1阶精度。
- 休恩方法
- yi+1=yi+2h[f(xi,yi)+f(xi+1,yi+hf(xi,yi))]
- 休恩方法有2阶精度,实际上就是2阶龙格-库塔公式。
- 两步欧拉格式
- yi+1=yi−1+2hf(xi,yi)
- 两步欧拉格式有2阶精度。
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 11D_Beyonder's Blog!