数值解和优化问题(02)：Aitken 算法, Steffensen 算法

Aitken - Δ² 加速算法

如果我们已经有了一个收敛于函数\(f(x)\)的根\(\xi\)的一个迭代序列\(\{x_i\}\), 希望构造一个收敛速度更快的迭代序列\(\{x_i'\}\). 为此, 引入新参数\(k\): \[ k:=\frac{x_{i+1}-\xi}{x_i-\xi} \] 假定\(k\)和\(\xi\)是不依赖于\(i\)的常数(基本不可能), 那么它们可以用相邻的三个元素表示出来: \[ \begin{aligned} k &= \frac{x_{i+2}-x_{i+1}}{x_{i+1}-x_i} \\ \xi &= \frac{x_ix_{i+2}-x_{i+1}^2}{x_{i+2}-2x_{i+1}+x_i} \end{aligned} \] 引入差分算符\(\Delta x_i := x_{i+1}-x_i\), 则 \[ \xi=x_i-\displaystyle\frac{(\Delta x_i)^2}{\Delta^2 x_i} \] 直接拿它构造新序列, 得到 \[ \boxed{x_i'=x_i-\frac{(\Delta x_i)^2}{\Delta^2 x_i}=x_i-\frac{(x_{i+1}-x_i)^2}{x_{i+2}-2x_{i+1}+x_i}} \] 这就是所谓的 Aitken-Δ² 加速算法, 按照这个算法得到的新序列必然收敛得更快.

Steffensen 算法

我们使用迭代函数的形式描述迭代过程 \[ x_{i+1}=\Phi(x_i)\ ;\qquad\xi=\Phi(\xi) \] 相应地, Aitken 算法的形式可以改写为 \[ \begin{aligned} x_i'&= x_i-\frac{(\Phi(x_i)-x_i)^2}{\Phi[\Phi(x_i)]-2\Phi(x_i)+x_i} \\&= \frac{x_i\Phi[\Phi(x_i)]-[\Phi(x_i)]^2}{\Phi[\Phi(x_i)]-2\Phi(x_i)+x_i} \end{aligned} \] 进一步引入新函数 \[ \Psi(x):=\frac{x\Phi[\Phi(x)]-[\Phi(x)]^2}{\Phi[\Phi(x)]-2\Phi(x)+x} \\ x'_i=\Psi(x_i) \] 我们已知\(x_i'\)比\(x_i\)更快, 不如把它定义成所谓的\(x_{i+1}\), 则新迭代方法告诉我们 \[ x_{i+1}=\Psi(x_i) \]