首页课程笔记电子工程系数据与算法

# 基本概念

# 数值问题

  • 问题的适定性 (Well-Posed Problem)
    • 解存在。
    • 解唯一。
    • 解连续依赖于问题数据。
  • 问题的良态性 (Well-Conditioned Problem)
    • 解对输入数据不敏感。
    • 在实际应用中，通常认为病态（Ill-Conditioned）问题是适定的。
  • 算法的稳定性 (Stable Algorithm)
    • 解对计算误差不敏感。
    • 如果一个算法产生的解是其邻近问题的精确解，即计算过程中的扰动不超过输入数据扰动的影响，则称该算法是稳定的。
    • 如果问题本身是病态的，即使使用稳定的算法，也不一定能得到问题的精确解，因为相邻问题的解也可能差异很大。
    • 只有对良态问题采用稳定算法，才能保证得到精确解。

# 误差分析

  • 绝对误差与相对误差
    • 绝对误差：Δx=x^−x\Delta x = \hat{x} - x
    • 相对误差：Er(x)=x^−xxE_r(x) = \frac{\hat{x} - x}{x}
  • 计算误差与传播误差
    • 计算误差：算法本身引起的误差。
    • 传播误差：由输入数据误差引起的误差。
    • 算法的优劣影响计算误差，但不影响传播误差。
  • 截断误差与舍入误差
    • 计算误差 = 截断误差 + 舍入误差。
    • 截断误差 (Truncation Error)：理论上的真实结果与用给定算法经过精确计算得到的结果之间的差异。通常由无穷级数截断、有限差分代替导数或提前终止迭代等近似造成。
    • 舍入误差 (Round-off Error)：用给定算法经过精确计算得到的结果与用同样算法经有限精度运算得到结果之间的差异。由实数的不精确表示及对它们的运算引起。
    • 有限差分近似误差分析：例。
  • 前向误差与后向误差
    • 前向误差：Δy=y^−y\Delta y = \hat{y} - y
    • 后向误差：Δx=x^−x=f−1(y^)−x\Delta x = \hat{x} - x = f^{-1}(\hat{y}) - x
  • 条件数 (Condition Number)

    cond=相对前向误差相对后向误差=∣xf′(x)f(x)∣=∣∂y/∂xy/x∣cond = \frac{\text{相对前向误差}}{\text{相对后向误差}} = \left|\frac{xf'(x)}{f(x)}\right| = \left|\frac{\partial y/\partial x}{y/x}\right|

    • cond≤1cond \le 1：良态。
    • cond≫1cond \gg 1：病态。
    • 通常只能估计条件数，并根据条件数和相对后向误差来估计相对前向误差。
    • 反函数与原函数的条件数互为倒数，因此函数求值和方程求解问题的敏感性是相反的。
  • 绝对条件数 (Absolute Condition Number)

    condabs=前向误差后向误差=∣f′(x)∣=∣∂y∂x∣cond_{abs} = \frac{\text{前向误差}}{\text{后向误差}} = |f'(x)| = \left|\frac{\partial y}{\partial x}\right|

# 计算机运算

  • 浮点数表示

    x=±(d0+d1/β+d2/β2+...+dp−1/βp−1)βEx = \pm(d_0 + d_1/\beta + d_2/\beta^2 + ... + d_{p-1}/\beta^{p-1})\beta^E

    • β\beta：基数；pp：精度；[L,U][L, U]：指数范围。
  • 正规化 (Normalization)
    • 除非所表示的数为 0，否则尾数的首位 d0d_0 不为 0。
    • 尾数 mm 满足 1≤m<β1 \le m < \beta。
    • 在基数 β=2\beta=2 时，要求 d0=1d_0=1。
    • 任何浮点数的正规化表示方法是唯一的。
  • 浮点数系统
    • 正规化浮点数总数：2(β−1)βp−1(U−L+1)+12(\beta-1)\beta^{p-1}(U-L+1)+1。
    • 下溢界 (Underflow Limit, UFL)：βL\beta^L。
    • 上溢界 (Overflow Limit, OFL)：β(U+1)(1−β−p)\beta(U+1)(1-\beta^{-p})。
    • 次正规化 (Subnormal)：在指数域达到最小值时，允许尾数首位为 0，以降低精度为代价实现逐渐下溢 (Gradual Underflow)，使下溢界变为 βU−p+1\beta^{U-p+1}。
  • IEEE 浮点数
    • 32 位：符号位(1) + 指数位(8) + 规范尾数(23)。
    • 64 位：符号位(1) + 指数位(11) + 规范尾数(52)。
    • 指数用固定偏移值（32位为127）的无符号数表示有符号数。
    • 正规化浮点数的指数域范围为 -126~127。
    • 支持次正规化和逐渐下溢，指数位为 0 时表示 -127。
    • 特殊值（指数位全为1）：
      • INF (Infinity)：小数部分为 0，表示无穷。
      • NAN (Not a Number)：小数部分不为 0，表示非数。
  • 舍入原则 (Rounding Rule)
    • 截断：将 xx 的 β\beta 基底展开的第 p−1p-1 位后截去（也称向零舍入法）。
    • 最近舍入：取与 xx 最接近的浮点数，相等时取最后一个为偶数。
  • 有效数字 (Significant Digits)
    • 称有效数字为 n 个，若 ∣x−x^∣≤0.5×βE−n+1\left|x - \hat{x}\right| \le 0.5 \times \beta^{E-n+1}。
    • 若保留 n 位有效数字，则相对误差 ∣Er(x)∣≤12d0β−(n−1)\left|E_r(x)\right| \le \frac{1}{2d_0}\beta^{-(n-1)}。
  • 机器精度 (Machine Epsilon)
    • 一个非零实数最大可能的相对误差。
    • 在最近舍入原则下，εmach=0.5β1−p\varepsilon_{mach} = 0.5\beta^{1-p}。
    • 机器精度由尾数位决定，下溢界由指数位决定，通常后者小于前者。
  • 浮点运算问题
    • 大数吃小数：在加法运算中，如果小数的绝对值小于大数的绝对值与机器精度的乘积，则小数的精度会完全损失。
    • 抵消：两个相近的数相减会造成有效数字的损失。应避免相近的大数相减。
    • 一元二次方程求根公式例：
      • 所有系数除以最大值，避免上溢或下溢。
      • 当根接近 0 时，将根号置于分母，缓解抵消。

# 线性方程组

# 线性方程组的特性

  • 解的存在性和唯一性
    • 相容性 (Consistency)：若 bb 属于 AA 的列向量张成的空间，则方程组 Ax=bAx=b 是相容的。
    • 奇异性 (Singularity)：矩阵 AA 亏秩或行列式为 0。
    • 若奇异且相容，则有无穷多解。
    • 若奇异但不相容，则无解。
  • 向量范数和矩阵范数
    • 常用向量范数：
      • ∣∣x∣∣1=∑i=1n∣xi∣||x||_1 = \sum_{i=1}^n|x_i|
      • ∣∣x∣∣2=∑i=1n∣xi∣2||x||_2 = \sqrt{\sum_{i=1}^n|x_i|^2}
      • ∣∣x∣∣∞=max⁡i∣xi∣||x||_\infty = \max_i|x_i|
    • 矩阵范数：
      • ∣∣A∣∣p=max⁡x≠0∣∣Ax∣∣p∣∣x∣∣p||A||_p = \max_{x \ne 0}\frac{||Ax||_p}{||x||_p}
    • 常用矩阵范数：
      • ∣∣A∣∣1=max⁡j∑i=1n∣aij∣||A||_1 = \max_j\sum_{i=1}^n|a_{ij}|（列向量求和最大）。
      • ∣∣A∣∣∞=max⁡i∑j=1n∣aij∣||A||_\infty = \max_i\sum_{j=1}^n|a_{ij}|（行向量求和最大）。
  • 问题的敏感性和病态性
    • 矩阵条件数：
      • cond(A)=∣∣A∣∣⋅∣∣A−1∣∣cond(A) = ||A|| \cdot ||A^{-1}||。
      • 矩阵条件数不小于 1。
      • 奇异矩阵的条件数为无穷大。
      • 单位矩阵的条件数为 1。
      • 矩阵乘以标量，条件数不变。
      • 对角阵的条件数为最大对角元除以最小对角元。
    • 线性方程组计算解的相对误差：
      • 若输入数据精度达到机器精度，则 ∣∣x^−x∣∣∣∣x^∣∣≤cond(A)⋅εmach\frac{||\hat{x} - x||}{||\hat{x}||} \le cond(A) \cdot \varepsilon_{mach}。
      • 精度损失了 log10(cond(A))log_{10}(cond(A)) 个十进制位。

# 线性方程组的直接解法

  • 高斯消去法
    • 高斯消去：将矩阵变换为上三角矩阵。
    • 回代求解：从下往上求解方程组。
    • 复杂度：O(n3)O(n^3)。
    • 选主元：为保证数值稳定性，需要进行列选主元或全选主元。
  • LU 分解
    • 将矩阵 AA 分解为下三角矩阵 LL 和上三角矩阵 UU，即 A=LUA=LU。
    • 求解 Ax=bAx=b 可分为两步：
      • 求解 Ly=bLy=b。
      • 求解 Ux=yUx=y。
    • 复杂度：O(n3)O(n^3)。
    • LU 分解后，若需要用 A 求解其他方程，无需再次分解，只需进行两次回代求解，复杂度为 O(n2)O(n^2)。
    • 引入列选主元后，初等消去阵中会包含初等交换阵，需要注意矩阵相乘的顺序。
  • 高斯-约当法
    • 将矩阵 AA 变换为对角矩阵。
    • 复杂度：O(n3)O(n^3)，比高斯消去法慢。
  • 乔列斯基分解 (Cholesky Decomposition)
    • 适用于对称正定矩阵，将其分解为 A=LLTA = LL^T，其中 LL 为下三角矩阵。
    • 对角线上的元素都是正的平方根，保证算法是良态的，因此不需要选主元。
    • 复杂度：O(n3)O(n^3)，是求解对称正定线性方程组最快的直接方法。
  • 解的精度
    • 残差 (Residual)：r=b−Ax^r = b - A\hat{x}。
    • 相对误差：∣∣Δx∣∣∣∣x^∣∣≤cond(A)⋅∣∣r∣∣∣∣A∣∣⋅∣∣x^∣∣\frac{||\Delta x||}{||\hat{x}||} \le cond(A) \cdot \frac{||r||}{||A|| \cdot ||\hat{x}||}。
    • 如果矩阵 A 是病态的，稳定的算法可以得到小的残差，但解的精度不一定高。

# 线性方程组的迭代求解

  • 不动点迭代
    • 运算复杂度：不超过 O(kn2)O(kn^2)，其中 kk 为迭代步数。
    • 适用于稀疏高维线性方程组求解。
    • 标准形式：xk+1=Gxk+cx_{k+1} = Gx_k + c。
    • 收敛条件：若迭代矩阵 GG 的谱半径 ρ(G)\rho(G)（所有特征值绝对值的最大值）满足 ρ(G)<1\rho(G) < 1，则迭代收敛。
    • 常用构造方法：将矩阵 AA 分解为 A=M−NA = M-N，则 G=M−1N,c=M−1bG = M^{-1}N, c = M^{-1}b。
  • 雅可比方法 (Jacobi Method)
    • 分解：A=D+L+UA = D+L+U。
    • 迭代：xk+1=D−1(b−(L+U)xk)x^{k+1} = D^{-1}(b - (L+U)x^k)。
  • 高斯-赛德方法 (Gauss-Seidel Method)
    • 分解：A=(D+L)+UA = (D+L)+U。
    • 迭代：xk+1=(D+L)−1(b−Uxk)x^{k+1} = (D+L)^{-1}(b-Ux^k)。
    • 在实际迭代中，由于 D+LD+L 是下三角矩阵，可直接利用更新后的分量进行下一步计算，因此收敛速度通常比雅可比方法快一倍。
  • 逐次超松弛技术 (SOR)
  • 最速下降法 (Steepest Descent)
  • 共轭梯度法 (Conjugate Gradient, CG)

# 非线性方程

# 非线性方程的特性

  • 存在性和唯一性
  • 敏感性和病态性
    • 绝对条件数：condabs=1/∣f′(x∗)∣cond_{abs} = 1/|f'(x^*)|。
    • 衡量解的精确性：
      • 残差：∣∣f(x^)∣∣≈0||f(\hat{x})|| \approx 0。
      • 误差：∣∣x^−x∗∣∣≈0||\hat{x} - x^*|| \approx 0。后者更精确。
    • 只有在问题良态的情况下，残差小才意味着解是精确的。
    • 具有重根的问题是病态的。

# 非线性方程的求解

  • 迭代法
    • 误差：ek=xk−x∗e_k = x_k - x^*。
    • 收敛速度 rr：

      • lim⁡k→∞∣∣ek+1∣∣∣∣ek∣∣r=C \lim_{k \to \infty} \frac{||e_{k+1}||}{||e_k||^r} = C

      • r=1,C<1r=1, C<1：线性收敛，每步迭代增加的有效数字是个常数。
      • r>1r>1：超线性收敛，每步迭代增加的有效数字数量递增。
      • r=2r=2：平方收敛，每步迭代增加的有效数字个数增加一倍。
    • 收敛速度只与算法效率有关，不能反映解的质量。
  • 不动点迭代
    • 迭代公式：xk+1=g(xk)x_{k+1} = g(x_k)。
    • 线性收敛：lim⁡k→∞∣∣ek+1∣∣∣∣ek∣∣=∣g′(x∗)∣\lim_{k \to \infty}\frac{||e_{k+1}||}{||e_k||} = |g'(x^*)|。
    • 收敛条件：
      • 0<∣g′(x∗)∣<10 < |g'(x^*)| < 1：存在一个包含 x∗x^* 的区间，若初值在该区间内，则迭代线性收敛。
      • ∣g′(x∗)∣>1|g'(x^*)| > 1：迭代发散。
      • ∣g′(x∗)∣=0|g'(x^*)| = 0：存在一个包含 x∗x^* 的区间，若初值在该区间内，则迭代至少是超线性收敛。
  • 二分法 (Bisection Method)
    • 收敛速度：线性收敛，C=0.5C = 0.5。
    • 迭代次数与函数具体形式无关，只取决于初始区间长度和收敛阈值。
    • 是一种安全的求根方法。
  • 牛顿法 (Newton's Method)
    • 迭代公式：xk+1=xk−f(xk)/f′(xk)x_{k+1} = x_k - f(x_k)/f'(x_k)。
    • 若为单根，收敛速度是平方收敛。

      • lim⁡k→∞ek+1ek2=f′′(x∗)2f′(x∗) \lim_{k \to \infty}\frac{e_{k+1}}{e_k^2} = \frac{f''(x^*)}{2f'(x^*)}

    • 若为m重根，收敛速度退化为线性。
    • 要求初值与真解足够接近，否则可能不收敛。
  • 割线法 (Secant Method)
    • 迭代公式：xk+1=xk−f(xk)⋅xk−xk−1f(xk)−f(xk−1)x_{k+1} = x_k - f(x_k) \cdot \frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}。
    • 收敛速度为超线性，r≈1.618r \approx 1.618。
  • 反插法 (Inverse Interpolation)
    • 利用前 3 次迭代值，反向拟合一个二次多项式 x=p(y)x=p(y)，下一次迭代值为 p(0)p(0)。
    • 收敛速度为超线性，r≈1.839r \approx 1.839。
  • 保护法
    • 在一个较大的有根区间外采用安全的二分法，在区间内采用高效的迭代方法。

# 数据逼近

# 拟合 (Fitting)

  • 超定方程 (Overdetermined System)
    • 方程的数目多于未知数的数目。
  • 最小二乘问题 (Least Squares Problem)
    • 求解满足 min⁡x∣∣r∣∣22=min⁡x∣∣b−Ax∣∣22\min_x ||r||_2^2 = \min_x ||b-Ax||_2^2 的 xx。
    • 如果系数矩阵 AA 的各列线性独立，则解唯一，否则解不唯一。
  • 正规方程方法 (Normal Equation Method)
    • 通过使残差最小化，得到正规方程：ATAx=ATbA^TAx = A^Tb。
    • 求解时，由于 ATAA^TA 对称正定，可使用乔列斯基分解。
    • 复杂度：mn2/2+n3/6mn^2/2 + n^3/6。
    • 算法敏感性：cond(ATA)=[cond(A)]2cond(A^TA) = [cond(A)]^2。正规方程方法会恶化问题的敏感性。
  • QR 分解
    • 利用Household 变换将超定方程组 Ax=bAx=b 变换为上三角方程组，即

      [R0]x=[b1b2]\begin{bmatrix} R \\ 0 \end{bmatrix} x = \begin{bmatrix} b_1 \\ b_2 \end{bmatrix}

      求解 Rx=b1Rx=b_1 即可得到最小二乘解。
    • 复杂度：mn2−n3/3mn^2 - n^3/3。
    • 当 m≈nm \approx n 时，与正规方程方法复杂度相当；当 m≫nm \gg n 时，约为其两倍。
    • 对于病态问题，QR 分解算法优于正规方程方法。

# 插值 (Interpolation)

  • 基底与系数矩阵
    • 插值函数是基底函数的线性组合。
    • 敏感性取决于系数矩阵的条件数，与基底函数的选择有很大关系。
  • 单项式基底的多项式插值
    • 插值多项式：Pn−1(x)=t1+t2x+⋯+tnxn−1P_{n-1}(x) = t_1 + t_2x + \cdots + t_nx^{n-1}。
    • 系数矩阵：范德蒙矩阵，通常是病态的。
    • 插值多项式对给定数据点的拟合情况很好，但系数不稳定。
    • 霍纳法则 (Horner's Rule) 可将求值复杂度从 O(n2)O(n^2) 降低到 O(n)O(n)。
  • 拉格朗日插值 (Lagrange Interpolation)
    • 直接构建插值多项式，避免求解线性方程组。
  • 牛顿插值 (Newton Interpolation)
    • 使用差商来构建插值多项式，具有增量计算的优点。
  • 正交多项式插值
  • 分段多项式插值
    • 样条插值 (Spline Interpolation)：如三次样条插值，通过分段低阶多项式保证平滑性。

# 最优化初步

  • 最优化问题的定义和特性
    • 目标：通常是求解函数的最小值。
    • 分类：
      • 连续优化问题：函数为连续函数。
      • 离散优化问题：如组合优化问题。
    • 形式：min⁡xf(x),s.t. g(x)=0 and h(x)<0\min_x f(x), \text{s.t. } g(x)=0 \text{ and } h(x)<0。
    • 线性规划：当 f,g,hf, g, h 都是线性函数时。
    • 局部最小值与全局最小值：
      • 一般算法只寻求局部最小值。
      • 凸函数在凸集上的所有局部最小值都是全局最小值。
  • 无约束优化
    • 临界点：梯度为 0 的点。局部最小值必是临界点。
    • 海森矩阵 (Hessian Matrix)：若在临界点处海森矩阵正定，则该点是严格局部最小值；负定，严格局部最大值；不定，鞍点；奇异，病态。
    • 敏感性：解的绝对条件数为 1/∣f′′(x∗)∣1/|f''(x^*)|。
  • 等式约束优化
    • 利用拉格朗日乘子将问题转化为无约束优化问题。
  • 一维优化
    • 适用于单峰函数。
    • 黄金分割搜索 (Golden Section Search)
      • 收敛速度：线性收敛，C≈0.618C \approx 0.618。
    • 逐次抛物插值 (Parabolic Interpolation)
      • 利用三点拟合抛物线，取其极值点作为新的近似。
      • 收敛速度：超线性收敛，r≈1.324r \approx 1.324。
    • 牛顿法：求解非线性方程 f′(x)=0f'(x)=0。
      • 迭代公式：xk+1=xk−f′(xk)/f′′(xk)x_{k+1} = x_k - f'(x_k)/f''(x_k)。
      • 收敛速度：平方收敛。
    • 保护法：结合安全算法（如黄金分割搜索）和高效算法（如逐次抛物插值）。
  • 多维优化
    • 梯度方法：xk+1=xk+αkdkx_{k+1} = x_k + \alpha_k d_k，其中 dkd_k 为下降方向。
    • 最速下降法
      • 方向：dk=−∇f(xk)d_k = -\nabla f(x_k)。
      • 收敛速度：线性收敛，收敛路径呈之字形，对初值敏感。
    • 牛顿法
      • 迭代公式：xk+1=xk−Hf−1(xk)∇f(xk)x_{k+1} = x_k - H_f^{-1}(x_k)\nabla f(x_k)。
      • 收敛速度：平方收敛。
      • 复杂度：高，每次迭代需计算海森矩阵并求解线性方程组。
    • 拟牛顿法 (Quasi-Newton Method)
      • 寻找海森矩阵的近似，并引入线性搜索参数。
      • 优点：保持超线性收敛的同时，降低了每次迭代的成本。
      • 例子：共轭梯度法、BFGS 方法。
  • 离散优化问题
    • 组合优化：如八皇后问题、旅行商问题、背包问题。