Exegesis. 数值微分的误差 [synthetic-differential-000A]

$\gdef\spaces#1{~ #1 ~}$ $\gdef\quads#1{\quad #1 \quad}$ $\gdef\eqq{\quads=}$

我们首先观察朴素的数值微分的计算过程. 待微分函数为 $(x+3)^2$, 此处不妨取 $x=-2$, $h=10^{-5}$, 这一位置的导数 $A$ 近似为

$$ A \quads\approx \frac{f(x+h)-f(x)}h \eqq \frac{(1 + 10^{-5})^2 - 1^2}{10^{-5}} \eqq 2.00001 $$

并且如果试图得到与预期的 $A=2$ 更接近的结果, 则须将无穷小近似 $h$ 选取为更靠近 $0$ 的数值, 这对于浮点精度有限的计算机来说极为不利.

而朴素的符号微分视表达式为树结构, 通过遍历树并对符合模式的节点应用求导规则 $(uv)' = u'v+uv'$. 即

$$ \begin{aligned} (x+3)^2 & \spaces\to (x+3)'(x+3) + (x+3)(x+3)' \\ & \spaces\to 1 \cdot (x+3) + (x+3) \cdot 1 \\ & \spaces\to 2x+6 \end{aligned} $$

此时再应用 $x=-2$ 得到 $A=2$. 这个做法在结果上可行, 但处理复杂的表达式时, 复合求导的中间过程本身会产生大量新的结点, 使递归遍历的实际时间达到指数级 $\mathcal{O}(2^N)$.

有没有方法可以既避免递归又减少中间结点呢? 我们先看一个涉及复数域的观察.