数值方法中初值不敏感的逆向递推

这是这学期学习数值算法中的一道作业题, 但感觉其中的思想很有意思. 原题是关于求积分 \(y_n \equiv \int_0^1\mathrm d x x^n e^x\) 的讨论. 这个积分有递推公式 $y_{n+1} = e - (n+1)y_n$. 简单的渐进分析可知, 由于 $\lim_{n\to\infty}y_n = 0$, $y_n\sim e/n$. 然而, 严格按照递推公示计算 $y_n$ 的话, 会很快由于数值误差的积累而发散. 其原因大体上是不太小的 $n$, 递推的每一项都是相近大小的两数相减, 恰好是相对数值误差被放大的情形.

为了减少这一数值误差, 一个很直接的想法就是改从 $y_0$ 递推到 $y_k$ 为从 $y_N$ 逆向递推到 $y_k$: $y_n = (e-y_{n+1})/(n+1)$. 误差分析得: \(\frac{\Delta y_k}{y_k} = \frac{1}{k+1}\frac{\Delta y_{k+1}}{y_k} < \frac{1}{k+1}\frac{\Delta y_{k+1}}{y_{k+1}} = \frac{k!}{N!}\delta_N\) 其中 $\delta_N = \Delta y_N/y_N$. 可以看到误差随着 $N$ 阶乘变小. 特别的, 即便 $\delta_N = 1$ 即完全没有关于 $y_N$ 的信息, 而代入初始值 $y_N=0$, 对于足够大的 $N$ 仍然可以得到相当任意精度的 $y_k$. 对于 $k$ 很大的情况, $N\sim\log\epsilon$ 是收敛很快的算法.

---

这个有趣的例子很容易让我联想到重整化的思想中, 高能的细节是不影响结果的, 或者准束缚态计算中, 边界外虽然发散, 但计算结果对边界仍然是不敏感的. 这个世界可以被理解, 是不是正是因为有很多量, 这样的看似依赖一个遥远的值, 但实际上这个遥远的值的影响, 很快就被过程抹掉了.