笔记5-《程序员的数学3：线性代数》恶性问题

目录

1. 恶性问题
2. 秩决定解的数量
3. 秩-零化度定理
4. 用 Ruby 验证

恶性问题

• 2.3 恶性问题

  • 压缩带来的后果

    • 压缩使空间被「压扁」，原空间不能被全部映射到
    • 和「线索过剩」的情况相同，对某些 $\mathbf{y}$ 可能根本找不到原来的出发点
    • 总结起来：可能出现不能把目标确定在唯一的点，或者根本不存在这样一点的情况

  • 单射、满射、双射

    • 无论什么样的结果 $\mathbf{y}$ 都可以找到导致它的原因吗 → 满射
    • 对于一个结果 $\mathbf{y}$，能不能确定唯一的出发点 → 单射
    • 两者同时成立 → 双射
    • $\mathrm{Ker} A$ 仅包含原点 $o$ → 映射为单射
    • $\mathrm{Im} A$ 覆盖目标空间全体 → 映射为满射

  • 用 $\mathrm{Ker} A$ 和 $\mathrm{Im} A$ 正式表述

    • $\mathrm{Ker} A$ 是原空间（定义域，$\mathbf{x}$ 所在空间）的一部分
    • $\mathrm{Im} A$ 是目标空间（值域，$\mathbf{y}$ 所在空间）的一部分
    • 单射 ⟺ $\mathrm{Ker} A = \{o\}$
    • 满射 ⟺ $\mathrm{Im} A$ = 目标空间全体

  • 「压缩扁平化」的判定

    • 某一列能表达成其他各列的若干倍加和 → 一定对应「压缩扁平化」的映射
    • 反过来，不满足这个条件的话，各列是线性无关的

  • 秩的本质：瓶颈型分解

    • 根据 $A$ 的秩，可以把它分解成两个「瘦矩阵」的乘积：$A = BC$
      • $B$ 是宽仅为 $r$ 的矩阵，$C$ 是高仅为 $r$ 的矩阵
    • 变换过程分成两步
      • $n$ 维向量 $\mathbf{x}$「压缩」成 $r$ 维向量 $\mathbf{z} = B\mathbf{x}$
      • $r$ 维向量「扩张」成 $m$ 维向量 $\mathbf{y} = C\mathbf{z}$
    • 秩为 1 的极端情况：$A$ 写成列向量和行向量的乘积
    • 反过来，能做这种分解则秩不超过 $r$
      • 丢失的信息就找不回来了

  • 2.5 针对恶性问题的对策

    • 解存在的充分必要条件：$\mathbf{y}$ 属于 $\mathrm{Im} A$
      • 因为 $\mathrm{Im} A$ 就是「在 $A$ 的作用下得到的目标点的全体集合」
    • 「方程的解」的最原始定义：代入之后使方程成立的值
      • 「若 $A$ 可逆则解是 $A^{-1}\mathbf{y}$」只是在此基础上推导出的性质
      • $A$ 奇异时这条性质不能用，不能因此说「无解」
    • 找出所有解：只要找到 1 个解，加上 $\mathrm{Ker} A$ 里的任意向量就得到全部解
      • 即 $\mathbf{x} = \mathbf{x}_0 + \mathrm{Ker} A$ 中的任意元素

  • 2.6 现实中的恶性问题（接近奇异的矩阵）

    • 数学上可逆与奇异天壤之别，但工程中常把极其接近奇异的可逆矩阵当作奇异矩阵处理
    • 原因：压缩厉害的矩阵，其逆矩阵的放大效果很厉害，噪声也被同步放大
    • 失焦图像修复是典型例子
    • 实际中用的对策标准
      • 无解时：给出一个答案使 $A\mathbf{x}$ 尽量「接近」$\mathbf{y}$
      • 有多解时：从中选一个最「合理」的解
    • 常用标准：$\|A\mathbf{x} - \mathbf{y}\|$ 越小越接近，$\|\mathbf{x}\|$ 越小越合理
    • 这套方法叫最小二乘法，在奇异值分解、广义逆矩阵的计算中作用重要
    • 注意：单讲线性空间没有长度和角度的概念，需要额外引入（本书附录 E）

秩决定解的数量

把上面的结论压成一张表：

条件	$\mathrm{Ker} A$	$\mathrm{Im} A$	$A\mathbf{x} = \mathbf{y}$ 的解
$A$ 可逆（$\mathrm{rank} A = n$）	$\{o\}$	目标空间全体	唯一解 $\mathbf{x} = A^{-1}\mathbf{y}$
$A$ 奇异，$\mathbf{y} \notin \mathrm{Im} A$	非平凡	目标空间真子集	无解
$A$ 奇异，$\mathbf{y} \in \mathrm{Im} A$	非平凡	目标空间真子集	无穷多解

所以判断一个逆问题能不能解，只需问两句：

• $\mathbf{y}$ 在 $\mathrm{Im} A$ 里吗？

• $\mathrm{Ker} A$ 里除了原点还有别的吗？

秩-零化度定理

$\mathrm{Ker} A$ 的维数叫 $A$ 的零化度（nullity）。可以证明：

$\mathrm{rank} A + \mathrm{nullity}(A) = n$

这是「秩-零化度定理」。它说的是：矩阵 $A$ 作为映射，把 $n$ 维空间压缩之后：

• 幸存下来的维数是 $\mathrm{rank} A$（也就是 $\mathrm{Im} A$ 的维数）

• 被压扁掉的维数是 $\mathrm{nullity}(A)$（也就是 $\mathrm{Ker} A$ 的维数）

两者加起来正好是原来的维数，一分不多一分不少。

这个定理的实际意义是：信息损失和信息保留是同一件事的两面。想知道压缩之后还剩多少信息，查一下零化度就行。

用 Ruby 验证

# 验证 rank A + nullity A = n
def rref(a)
  m = a.map { |row| row.map(&:to_f) }
  rows = m.size
  cols = m[0].size
  r = 0
  cols.times do |c|
    piv = (r...rows).find { |i| m[i][c].abs > 1e-10 }
    next unless piv
    m[r], m[piv] = m[piv], m[r]
    (0...rows).each do |i|
      next if i == r
      f = m[i][c] / m[r][c]
      cols.times { |k| m[i][k] -= f * m[r][k] }
    end
    r += 1
  end
  [m, r]
end

def nullity(a)
  m, rank = rref(a)
  m.size - rank
end

samples = [
  [[2, 1], [1, 1]],          # 满秩，零化度 0
  [[1, 2], [2, 4]],          # 第2行是第1行的2倍，零化度 1
  [[1, 0, 2], [0, 1, 3], [1, 1, 5]],  # 第3行=第1行+第2行，零化度 1
  [[1, 2, 3], [4, 5, 6]]     # 秩 2，零化度 1
]

samples.each do |a|
  n = a.size
  m, rank = rref(a)
  puts "n=#{n} rank=#{rank} nullity=#{nullity(a)} 和=#{rank + nullity(a)}"
end

输出：

n=2 rank=2 nullity=0 和=2
n=2 rank=1 nullity=1 和=2
n=3 rank=2 nullity=1 和=3
n=2 rank=2 nullity=0 和=2