艾特肯外推法 (Aitken’s Extrapolation) 用于加速一个数列的收敛速度。

证明公式

假设 \(\Delta X\) 是一个等比序列，公比为 r ( \(|r|<1\) )，因为我们基于数字的趋势，外推出 \(X\) 序列最终的值，推导过程如下。

\[ \begin{aligned} & r=\frac{\Delta X_i}{\Delta X_{i-1}}=\frac{X_{i+1}-X_i}{X_i-X_{i-1}}=\text { constant } \\ & \begin{aligned} 1-r & =\frac{\Delta X_{i-1}-\Delta X_i}{\Delta X_{i-1}} \\ X_{\infty} & =X_i+\Delta X_i+\Delta X_{i+1}+\Delta X_{i+2}+\ldots \\ & =X_i+\Delta X_i\left(1+r+r^2+\ldots\right) \\ & =X_i+\frac{\Delta X_i}{1-r} \\ & =\left(X_{i+1}-\Delta X_i\right)-\frac{\Delta X_i \Delta X_{i-1}}{\Delta X_i-\Delta X_{i-1}} \\ & =X_{i+1}-\frac{\Delta X_i\left(\Delta X_i-\Delta X_{i-1}\right)+\Delta X_i \Delta X_{i-1}}{\Delta X_i-\Delta X_{i-1}} \\ & =X_{i+1}-\frac{\left(\Delta X_i\right)^2}{\Delta X_i-\Delta X_{i-1}} \end{aligned} \end{aligned} \]

其中用到了等比数列求和公式 \(S_{n} = \frac{a_{1} \cdot (1-q^{n})}{1-q}\) 。

因此使用艾特肯外推法得到的值为

\[ \begin{aligned} X_{\infty} & =X_{i+1}-\frac{\left(\Delta X_i\right)^2}{\Delta X_i-\Delta X_{i-1}} \\ & =X_{i+1}-\frac{\left(X_{i+1}-X_{i}\right)^2}{\left(X_{i+1}-X_{i}\right)-\left(X_{i}-X_{i-1}\right)} \\ & =X_{i+1}-\frac{\left(X_{i+1}-X_{i}\right)^2}{\left(X_{i+1}-2X_{i}+X_{i-1}\right)} \end{aligned} \]

举例1

\(\sqrt{2} \approx 1.4142136\) 可以通过不断迭代以下数列进行估计 (\(n\) 越大，\(a_{n}\) 越接近 \(\sqrt{2}\) )

\[ a_{n+1} = \frac{a_{n}+2/a_{n}}{2}, \quad a_{0} = 1 \]

我通过实际测试发现这个数列不满足 \(\frac{\Delta X_i}{\Delta X_{i-1}}=\frac{X_{i+1}-X_i}{X_i-X_{i-1}}=\text { constant }\) 这个条件 ，但是 \(\Delta X\) 也是在不断变小的。

我们同时使用艾特肯外推法（下表中的 Ax 值，注意由于艾特肯外推法需要数列前两个数，因此这里是从 \(Ax_{3}\) 开始的 ），结果如下。

我们看到这里艾特肯外推法没有提升收敛速度，因为艾特肯外推法适用于 linear convergence ，而这里是 quadratic convergence 。

所谓的 linear convergence 定义如下，假设一个数列 \(\{x_{n}\}_{n=1}^{\infty}\) ，其收敛于 \(l\) ，如果存在一个 \(\mu \in (0,1)\) 使得下式成立，则称为 linear convergence

\[ \lim_{n \rightarrow \infty} \frac{|x_{n+1} - l|}{|x_{n} - l|} = \mu \]

参考文献

1. Aitken’s delta-squared process

2. Aitkens Extrapolation