• 绪论
    • 有效数字判断
      • 有效数字 dd 是满足 Ep<101−d2(1st)E_p<\frac{10^{1-d}}{2}(\text{1st}) 或 Rp<101−d2(2nd)R_p<\frac{10^{1-d}}{2}(\text{2nd}) 的最大正整数。
      • 0.005<101−220.005<\frac{10^{1-2}}{2}，有效数字 22 位；0.0015<101−320.0015<\frac{10^{1-3}}{2}，有效数字 33 位。
  • 非线性方程解法
    • 收敛阶
      • 设迭代 xk+1=g(xk)x_{k+1}=g(x_k) 收敛到不动点 x∗x^\ast，记绝对误差 ek=xk−x∗e_k=x_k-x^\ast，若 lim⁡k→∞∣ek+1ekp∣=C≠0\lim\limits_{k\to\infty}\left|\frac{e_{k+1}}{e_k^p}\right|=C\neq 0，则收敛阶为 pp。
      • p=1p=1 为线性收敛，此时必有 C<1C<1；p=2p=2 为二次收敛；p>1p>1 称为超线性收敛。
    • 不动点迭代
      • 将 f(x)=0f(x)=0 等价变换为 x=g(x)x=g(x)，利用不动点迭代 xk+1=g(xk)x_{k+1}=g(x_k) 找到不动点，不动点就是根。
      • 若 a≤g(x)≤ba\le g(x)\le b 对一切 x∈[a,b]x\in[a,b] 成立，则存在不动点；同时又有 0≤L<10\le L<1，使得 ∣g′(x)∣≤L|g'(x)|\le L 对一切 x∈[a,b]x\in[a,b] 成立，则存在唯一不动点。
      • ek+1=xk+1−x∗=g(xk)−g(x∗)=g′(ξ)eke_{k+1}=x_{k+1}-x^\ast=g(x_k)-g(x^\ast)=g'(\xi)e_k，其中 ξ\xi 在 xkx_k 和 xk+1x_{k+1} 之间；若 g(x∗)≠0g(x^\ast)\neq 0，取极限得 lim⁡k→∞=∣ek+1ek∣=g′(x∗)\lim\limits_{k\to\infty}=\left|\frac{e_{k+1}}{e_k}\right|=g'(x^\ast)，线性收敛。
    • 二分法
      • f(a)f(b)<0f(a)f(b)<0，有根。
      • 二等分区间长度，直到满足精度为止。
      • 终止条件 ∣xk+1−xk∣<ε|x_{k+1}-x_k|<\varepsilon。
      • ∣x∗−xk∣=∣bk+ak2−x∗∣≤bk−ak2=b−a2k+1≤ε|x^\ast-x_k|=\left|\frac{b_k+a_k}{2}-x^\ast\right|\le\frac{b_k-a_k}{2}=\frac{b-a}{2^{k+1}}\le\varepsilon，满足精度的 k=⌈log⁡2b−aε⌉−1k=\left\lceil\log_2\frac{b-a}{\varepsilon}\right\rceil-1。
    • 试值法
      • 令 c=b−f(b)(b−a)f(b)−f(a)c=b-\frac{f(b)(b-a)}{f(b)-f(a)}，根据零点存在定理判断根的位置。
      • 缺点：尽管区间宽度越来越小，但它可能不趋近于0。
    • 牛顿迭代
      • 用Taylor展开近似 f(xk)+f′(xk)(x−xk)≈0f(x_k)+f'(x_k)(x-x_k)\approx0，得到迭代 xk+1=xk−f(xk)f′(xk)x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}。
      • 牛顿迭代对初值要求比较高，x0x_0 必须充分靠近 x∗x^\ast，才能保证局部收敛。
      • 根据Taylor展开式，f(x∗)=f(xk)+f′(xk)(x∗−xk)+12f′′(ξ)(x∗−xk)2=0f(x^\ast)=f(x_k)+f'(x_k)(x^\ast-x_k)+\frac{1}{2}f''(\xi)(x^\ast-x_k)^2=0，可得 xk−x∗−f(xk)f′(xk)=f′′(ξ)2f′(xk)(x∗−xk)2x_k-x^\ast-\frac{f(x_k)}{f'(x_k)}=\frac{f''(\xi)}{2f'(x_k)}(x^\ast-x_k)^2，即 lim⁡k→∞∣ek+1ek2∣=∣f′′(x∗)2f′(x∗)∣\lim\limits_{k\to\infty}\left|\frac{e_{k+1}}{e_k^2}\right|=\left|\frac{f''(x^\ast)}{2f'(x^\ast)}\right|，牛顿迭代的收敛阶至少为2。
    • 割线法
      • 计算导数不方便，因此用 f(xk)−f(xk−1)xk−xk−1\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}} 近似 f′(xk)f'(x_k)。
      • 迭代式 xk+1=xk−f(xk)f(xk)−f(xk−1)(xk−xk−1)x_{k+1}=x_k-\frac{f(x_k)}{f(x_k)-f(x_{k-1})}(x_k-x_{k-1})。
      • 收敛阶 5+12≈1.618\frac{\sqrt 5+1}{2}\approx1.618。
  • 方程组的数值解法
    • 向量范数
      • ∣∣x∣∣1=∑i=1n∣xi∣||x||_1=\sum\limits_{i=1}^n|x_i|
      • ∣∣x∣∣2=∑i=1nxi2||x||_2=\sqrt{\sum\limits_{i=1}^nx_i^2}
      • ∣∣x∣∣∞=max⁡1≤i≤n∣xi∣||x||_\infty=\max\limits_{1\le i\le n}|x_i|
    • 矩阵范数
      • ∣∣A∣∣1=max⁡1≤j≤n∑i=1n∣aij∣||A||_1=\max\limits_{1\le j\le n}\sum\limits_{i=1}^n|a_{ij}|，列和范数。
      • ∣∣A∣∣∞=max⁡1≤i≤n∑j=1n∣aij∣||A||_\infty=\max\limits_{1\le i\le n}\sum\limits_{j=1}^n|a_{ij}|，行和范数。
      • ∣∣A∣∣2=ρ(ATA)||A||_2=\sqrt{\rho(A^TA)}，谱范数。
    • 高斯消元
      • 消去运算量：共需要消去 n−1n-1 次，每次消去时选择第 kk 行共 n−k+1n-k+1 个数与下方 n−kn-k 行相减，∑k=1n−1(n−k)(n−k+1)=n3−n3\sum\limits_{k=1}^{n-1}(n-k)(n-k+1)=\frac{n^3-n}{3}。
      • 回带运算量：第 kk 行需要回代 xn,xn−1⋯ ,xk+1x_n,x_{n-1}\cdots,x_{k+1}，再求出 xkx_k，共需要 ∑k=1n(n−k+1)=n(n+1)2\sum\limits_{k=1}^n(n-k+1)=\frac{n(n+1)}{2}。
      • 选主元策略：在剩余行中选择开头绝对值最大的非零元素座位主元，然后初等行变换到对角线上。
    • LULU分解
      • LL 为下三角矩阵，且对角线为 11，UU 为上三角矩阵。
      • 求 Ax=bAx=b，首先令 A=LUA=LU，那么有 LUx=bLUx=b；令 y=Uxy=Ux，问题转化为求两个方程 Ly=bLy=b、Ux=yUx=y。
      • 首先令 L=EL=E，U=AU=A，可逐渐构造出分解形式。
    • 雅可比迭代
      • xi(k+1)=bi−∑j=1i−1aijxj(k)−∑j=i+1naijxj(k)aiix_i^{(k+1)}=\frac{b_i-\sum\limits_{j=1}^{i-1}a_{ij}x_j^{(k)}-\sum\limits_{j=i+1}^na_{ij}x_j^{(k)}}{a_{ii}}
    • 高斯-赛德尔迭代
      • xi(k+1)=bi−∑j=1i−1aijxj(k+1)−∑j=i+1naijxj(k)aiix_i^{(k+1)}=\frac{b_i-\sum\limits_{j=1}^{i-1}a_{ij}x_j^{(k+1)}-\sum\limits_{j=i+1}^na_{ij}x_j^{(k)}}{a_{ii}}
  • 插值
    • 拉格朗日插值
      • 拉格朗日插值多项式 Ln(x)=∑i=0nyi∏j=0j≠inx−xjxi−xjL_n(x)=\sum\limits_{i=0}^n y_i\prod\limits_{j=0\atop j\neq i}^n\frac{x-x_j}{x_i-x_j}
      • 余项 Rn(x)=f(n+1)(ξ)(n+1)!∏i=0n(x−xi)ξ∈(a,b)R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod\limits_{i=0}^n(x-x_i)\quad\xi\in(a,b)
    • 牛顿插值
      • 定义 00 阶均差 f[xi]=f(xi)f[x_i]=f(x_i)，则定义了 m−1m-1 阶均差后，mm 阶均差 f[x0,x1,⋯ ,xm]=f[x1,x2,⋯ ,xm]−f[x0,x1,⋯ ,xm−1]xm−x0f[x_0,x_1,\cdots,x_m]=\frac{f[x_1,x_2,\cdots,x_m]-f[x_0,x_1,\cdots,x_{m-1}]}{x_m-x_0}，这类似多阶差分的概念。
      • 牛顿插值多项式 Nn(x)=f(x0)+∑i=1nf[x0,x1,⋯ ,xi]∏j=0i−1(x−xj)N_n(x)=f(x_0)+\sum\limits_{i=1}^nf[x_0,x_1,\cdots,x_i]\prod\limits_{j=0}^{i-1}(x-x_j)
      • 余项 Rn(x)=f(n+1)(ξ)(n+1)!∏i=0n(x−xi)=f[x,x0,x1,⋯ ,xn]∏i=0n(x−xi)R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod\limits_{i=0}^n(x-x_i)=f[x,x_0,x_1,\cdots,x_n]\prod\limits_{i=0}^n(x-x_i)
    • 埃尔米特插值
      • 共有 n+1n+1 个互异点，要求 H(xi)=f(xi)H(x_i)=f(x_i) 且 H′(xi)=f′(xi)H'(x_i)=f'(x_i)；于是有 2n+22n+2 个方程，可构造 2n+12n+1 次埃尔米特插值多项式 H2n+1(x)H_{2n+1}(x)。
      • 一般直接设多项式的系数，列方程求解系数。
      • 余项 R2n+1(x)=f(2n+2)(ξ)(2n+2)![∏i=0n(x−xi)]2R_{2n+1}(x)=\frac{f^{(2n+2)(\xi)}}{(2n+2)!}\left[\prod\limits_{i=0}^n(x-x_i)\right]^2
    • 分段线性插值
      • 每一小段都用直线拟合。
      • S(x)=∑i=0nli(x)f(xi)S(x)=\sum\limits_{i=0}^nl_i(x)f(x_i)，其中 li(x)={x−xi−1xi−xi−1xi−1≤x≤xix−xi+1xi−xi+1xi≤x≤xi+100≤x<xi−1或xi<x≤bl_i(x)=\left\{\begin{matrix} \frac{x-x_{i-1}}{x_i-x_{i-1}} &x_{i-1}\le x\le x_i\\ \frac{x-x_{i+1}}{x_i-x_{i+1}} &x_i\le x\le x_{i+1}\\ 0&0\le x<x_{i-1}或x_i<x\le b \end{matrix}\right.。
      • 当 x∈[xi,xi+1]x\in[x_i,x_{i+1}]，只有 li(x)l_i(x) 在区间 [xi,xi+1][x_i,x_{i+1}] 和 li+1(x)l_{i+1}(x) 在区间 [xi,xi+1][x_i,x_{i+1}] 不为零，正好是区间内的线性插值 x−xi+1xi−xi+1f(xi)+x−xixi+1−xif(xi+1)\frac{x-x_{i+1}}{x_i-x_{i+1}}f(x_i)+\frac{x-x_i}{x_{i+1}-x_i}f(x_{i+1})。
    • 三次样条插值 S(x)S(x) 定义
      • 函数 S(x)S(x) 定义在区间 [a,b][a,b] 上，给定 n+1n+1 个节点 a=x0<x1<⋯<xn=ba=x_0<x_1<\cdots<x_n=b，和与之对应的 f(x0),f(x1),⋯ ,f(xn)f(x_0),f(x_1),\cdots,f(x_n)。
      • 在每个节点上满足 S(xi)=f(xi)(i=1,2,⋯ ,n)S(x_i)=f(x_i)\quad(i=1,2,\cdots,n)。
      • 在 [a,b][a,b] 上有连续的零阶、一阶、二阶导数。
      • 在每个小区间 [xi,xi+1](i=0,1,⋯ ,n−1)[x_i,x_{i+1}]\quad (i=0,1,\cdots,n-1) 上是三次多项式。
  • 拟合
    • 实际函数 f(x)f(x)，拟合函数 φ(x)\varphi(x)，对于参考点 xix_i，有残差 εi=φ(xi)−f(xi)\varepsilon_i=\varphi(x_i)-f(x_i)。
    • 最小二乘法
      • 要求 ∑i=1nεi2\sum\limits_{i=1}^n\varepsilon_i^2 最小。
      • 线性拟合
        • 对于给定点 (xi,yi) (i=1,2,⋯ ,n)(x_i,y_i)\ (i=1,2,\cdots,n)，设拟合函数 y(x)=a0+a1xy(x)=a_0+a_1x，则要求 F(a0,a1)=∑i=1n(a0+a1xi−yi)2F(a_0,a_1)=\sum\limits_{i=1}^n(a_0+a_1x_i-y_i)^2 最小。
        • 令 FF 各个方向偏导数为 00，可解得系数。
      • 多项式拟合
        • 令拟合的多项式为 y(x)=a0+a1x+⋯anxmy(x)=a_0+a_1x+\cdots a_nx^m。
        • 有方程组 {a0n+a1∑i=1nxi+⋯+am∑i=1nxim=∑i=1nyia0∑i=1nxi+a1∑i=1nxi2+⋯+am∑i=1nxim+1=∑i=1nxiyi⋮a0∑i=1nxim+a1∑i=1nxim+1+⋯+am∑i=1nxi2m=∑i=1nximyi\left\{\begin{array}{c} a_{0} n+a_{1} \sum\limits_{i=1}^n x_{i}+\cdots+a_{m} \sum\limits_{i=1}^n x_{i}^{m}=\sum\limits_{i=1}^n y_{i} \\ a_{0} \sum\limits_{i=1}^n x_{i}+a_{1} \sum\limits_{i=1}^n x_{i}^{2}+\cdots+a_{m} \sum\limits_{i=1}^n x_{i}^{m+1}=\sum\limits_{i=1}^n x_{i} y_{i} \\ \vdots \\ a_{0} \sum\limits_{i=1}^n x_{i}^{m}+a_{1} \sum\limits_{i=1}^n x_{i}^{m+1}+\cdots+a_{m} \sum\limits_{i=1}^n x_{i}^{2 m}=\sum\limits_{i=1}^n x_{i}^{m} y_{i} \end{array}\right.
      • 将非线性拟合转化为多项式拟合
        • y=axb→ln⁡y=bln⁡x+ln⁡ay=ax^b\to\ln y=b\ln x+\ln a
        • y=axμ+cy=ax^\mu+c
        • y=xax+b→1y=b1x+ay=\frac{x}{ax+b}\to\frac{1}{y}=b\frac{1}{x}+a
        • y=1ax+b→1y=ax+by=\frac{1}{ax+b}\to \frac{1}{y}=ax+b
  • 数值积分
    • 代数精度：使得 I(pm)=Q(pm)I(p_m)=Q(p_m) 的最高 mm 次多项式。验证求积公式有 mm 次代数精度，只需验证 ∀f(x)=1,x,x2,⋯ ,xm\forall f(x)=1,x,x^2,\cdots,x^m 有 I(f)=Q(f)I(f)=Q(f) 精确成立，但 I(xm+1)≠Q(xm+1)I(x^{m+1})\neq Q(x^{m+1})。
    • Newton-Cotes公式
      • 原积分式 I(f)=∫abf(x)dxI(f)=\displaystyle\int_a^b f(x)dx，用 f(x)≈∑i=0nli(x)f(xi)f(x)\approx\sum\limits_{i=0}^nl_i(x)f(x_i) 近似，得到近似值 Q(f)=∫ab[∑i=0nli(x)f(xi)]=∑i=0n[∫abli(x)]f(xi)Q(f)=\displaystyle\int_a^b\left[\sum\limits_{i=0}^nl_i(x)f(x_i)\right]=\sum\limits_{i=0}^n\left[\int_a^bl_i(x)\right]f(x_i)。
      • nn 次插值型求积公式代数精度至少为 nn 次。
      • 梯形求积公式 Q(f)=b−a2[f(a)+f(b)]Q(f)=\frac{b-a}{2}[f(a)+f(b)]，代数精度1。
      • 辛普森求积公式 Q(f)=b−a6[f(a)+4f(a+b2)+f(b)]Q(f)=\frac{b-a}{6}\left[f(a)+4f\left(\frac{a+b}{2}\right)+f(b)\right]，代数精度3。
      • 辛普森 38\frac{3}{8} 求积公式 Q(f)=b−a8[f(a)+3f(2a+b3)+3f(a+2b3)+f(b)]Q(f)=\frac{b-a}{8}\left[f(a)+3f\left(\frac{2a+b}{3}\right)+3f\left(\frac{a+2b}{3}\right)+f(b)\right]，代数精度3。
      • 科特斯求积公式 Q(f)=b−a90[7f(a)+32f(3a+b4)+12f(a+b2)+32f(a+3b4)+7f(b)]Q(f)=\frac{b-a}{90}\left[7f(a)+32f\left(\frac{3a+b}{4}\right)+12f\left(\frac{a+b}{2}\right)+32f\left(\frac{a+3b}{4}\right)+7f(b)\right]，代数精度5。
    • 复化求积公式
      • 定步长：将 [a,b][a,b] 分成 nn 等分 [xi,xi+1][x_i,x_{i+1}]，其中 xi=a+ihx_i=a+ih，h=b−anh=\frac{b-a}{n}，$ (i=0,1,\cdots,n)$。
      • 复化梯形公式 I=h2[f(a)+2∑i=1n−1f(xi)+f(b)]I=\frac{h}{2}\left[f(a)+2\sum\limits_{i=1}^{n-1}f(x_i)+f(b) \right]
      • 复化辛普森公式 I=h6[f(a)+4∑i=0n−1f(xi+12)+2∑i=1n−1f(xi)+f(b)]I=\frac{h}{6}\left[f(a)+4\sum\limits_{i=0}^{n-1}f(x_{i+\frac{1}{2}})+2\sum\limits_{i=1}^{n-1}f(x_i)+f(b) \right]
      • 变步长算法，将区间不断对分，取区间数 n=2kn=2^{k}，设区间数为 nn 时的积分值为 InI_n，当 ∣I2n−In∣<ε|I_{2n}-I_n|<\varepsilon 时停止计算。
      • 变步长梯形公式
        • Tn=h2[f(a)+2∑i=1n−1f(xi)+f(b)]T_n=\frac{h}{2}\left[f(a)+2\sum\limits_{i=1}^{n-1}f(x_i)+f(b) \right]，h=b−anh=\frac{b-a}{n}。
        • T2n=12Tn+h2∑i=0n−1f(xi+12)T_{2n}=\frac{1}{2}T_n+\frac{h}{2}\sum\limits_{i=0}^{n-1}f(x_{i+\frac{1}{2}})。
      • 变步长辛普森公式 Sn=4T2n−Tn4−1S_n=\frac{4T_{2n}-T_n}{4-1}
      • 变步长科特斯公式 Cn=42S2n−Sn42−1C_n=\frac{4^2S_{2n}-S_n}{4^2-1}
      • 变步长龙贝格公式 Rn=43C2n−Cn43−1R_n=\frac{4^3C_{2n}-C_n}{4^3-1}
      • 自动选步长，求余项 max⁡R≤ε\max R\le \varepsilon。
    • 高斯求积公式
      • 若存在 n+1n+1 个节点 xi∈[a,b]x_i\in[a,b] 及求积系数 AiA_i，使求积公式 ∑i=0nAif(xi)\sum\limits_{i=0}^nA_if(x_i) 有 2n+12n+1 次代数精度，则成 xix_i 为高斯点，AiA_i 为高斯系数，求积公式为高斯求积公式。
      • 区间 [−1,1][-1,1] 上几个简单的高斯求积公式
        • n=02f(0)n=0\quad 2f(0)
        • n=1f(−13)+f(13)n=1\quad f\left(-\frac{1}{\sqrt 3}\right)+f\left(\frac{1}{\sqrt 3}\right)
        • n=259f(−155)+89f(0)+59f(155)n=2\quad \frac{5}{9}f\left(-\frac{\sqrt{15}}{5} \right)+\frac{8}{9}f(0)+\frac{5}{9}f\left(\frac{\sqrt{15}}{5} \right)
  • 数值优化
    • 搜索的核心是找到 [a,b][a,b] 区间上下凸函数 f(x)f(x) 的极小值。
    • 黄金分割搜索
      1. 取 c=0.382(b−a)c=0.382(b-a)，取 f1=f(c)f_1=f(c)。
      2. 取 d=0.618(b−a)d=0.618(b-a)，取 f2=f(d)f_2=f(d)。
      3. 若 ∣a−b∣<ε|a-b|<\varepsilon，则取极小值点 ans=a+b2ans=\frac{a+b}{2}，停止，否则继续搜索。
      4. 若 f1<f2f_1<f_2，则压缩右边区间，令 b=db=d，d=cd=c，f2=f1f_2=f_1，重新计算 cc、f1f_1；若 f1>f2f_1>f_2，则压缩左边区间，令 a=ca=c，c=dc=d，f1=f2f_1=f_2，重新计算 dd、f2f_2；若 f(c)=f(d)f(c)=f(d)，则令 a=ca=c，b=db=d，重新计算 cc、dd、f1f_1、f2f_2。
    • 斐波那契搜索
      • 第 ii 次迭代的区间为 [ai,bi][a_i,b_i]，参考点 ci=ai+(1−Fn−i−1Fn−i)(bi−ai)c_i=a_i+\left(1-\frac{F_{n-i-1}}{F_{n-i}}\right)(b_i-a_i)、di=ai+Fn−i−1Fn−i(bi−ai)d_i=a_i+\frac{F_{n-i-1}}{F_{n-i}}(b_i-a_i)，其中 ri=Fn−i−1Fn−ir_i=\frac{F_{n-i-1}}{F_{n-i}}。
      • 要求精度 Fn>b0−a0εF_n>\frac{b_0-a_0}{\varepsilon}。
  • 微分方程求解
    • 欧拉法
      • 考查初值问题 {dydx=f(x,y)y(x0)=y0,x≥x0\left\{\begin{array}{l} \frac{d y}{d x}=f(x, y) \\ y\left(x_{0}\right)=y_{0}, x \geq x_{0} \end{array}\right.，将区间 [a,b][a,b] 划分为 nn 个等距子区间，并选择网格点 xix_i，i=0,1,⋯ ,ni=0,1,\cdots,n，步长 h=b−anh=\frac{b-a}{n}。
      • 欧拉格式 {y0=y(x0)yi+1=yi+hf(xi,yi)\left\{\begin{array}{l}y_0=y(x_0)\\y_{i+1}=y_i+hf(x_i,y_i)\end{array}\right.
      • 几何意义：用一条折线近似代替积分曲线。
      • 欧拉法具有1阶精度。
    • 休恩方法
      • yi+1=yi+h2[f(xi,yi)+f(xi+1,yi+hf(xi,yi))]y_{i+1}=y_i+\frac{h}{2}[f(x_i,y_i)+f(x_{i+1},y_i+hf(x_i,y_i))]
      • 休恩方法有2阶精度，实际上就是2阶龙格-库塔公式。
    • 两步欧拉格式
      • yi+1=yi−1+2hf(xi,yi)y_{i+1}=y_{i-1}+2hf(x_i,y_i)
      • 两步欧拉格式有2阶精度。