Steffensen 方法的推导及其二阶收敛的证明

Steffensen 方法的推导

由于 Steffensen 方法是由弦截法改造来的，所以，这里先给出弦截法的迭代公式

$$x_{k+1}=x_k-\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}f(x_k),k=1,2,....$$

弦截法的定义及推导比较简单，这里不再赘述，然后我们来看如何将弦截法改造成 Steffensen 方法：若弦截法产生的迭代序列 $\{x_k\}$ 充分接近于精确解 $x^{\ast }$，则 $x_k-x_{k-1}$ 与 $f(x_k)$ 均充分接近于零。因此，我们可以近似地置 $x_k-x_{k-1}\approx f(x_k)$，然后将弦截法迭代公式中的 $x_{k-1}$ 给代换掉，就得到了 Steffensen 方法

$$x_{k+1}=x_k-\frac{f^2(x_k)}{f(x_k)-f(x_k-f(x_k))},k=1,2,....$$

证明 Steffensen 方法的二阶收敛性

给定条件：设 $f(x)=0$ 有根 $x_{\ast }$，其中 $f(x)$ 在 $x^{\ast }$ 的某邻域 $S(x^{\ast },\delta )$ 内二阶连续可微，且 $f^{{}^{\prime }}(x)\ne 0$.

证明：

由 Steffensen 迭代公式，有

$$\phi (x)=x-\frac{f(x)}{f(x)-f(x-f(x))}$$

对 $f(x-f(x))$ 进行泰勒展开，得

$${\displaystyle f(x-f(x))=f(x)-f^{{}^{\prime }}(x)f(x)+\frac{1}{2}{f}^{{}^{″}}(\xi )f^2(x)，}$$

其中，$\xi$ 是 $x$ 和 $x-f(x)$ 之间的一个值。

于是，有

$$g(x)=\frac{f(x)-f(x-f(x))}{f(x)}=\frac{f^{{}^{\prime }}(x)f(x)-\frac{1}{2}{f}^{{}^{″}}{f}^2(x)}{f(x)}=f^{{}^{\prime }}(x)-\frac{1}{2}{f}^{{}^{″}}(\xi )f(x).$$

进而，

$$\phi (x)=x-\frac{f^2(x)}{f(x)-f(x-f(x))}=x-\frac{f(x)}{f^{{}^{\prime }}(x)-\frac{1}{2}{f}^{{}^{″}}(\xi )f(x)}.$$

因此，

$$\frac{\phi (x)-\phi (x^{\ast })}{x-x^{\ast }}=\frac{x-\frac{f(x)}{f^{{}^{\prime }}(x)-\frac{1}{2}{f}^{{}^{″}}(\xi )f(x)}-x^{\ast }}{x-x^{\ast }}=\frac{x-x^{\ast }-\frac{f(x)}{f^{{}^{\prime }}(x)-\frac{1}{2}{f}^{{}^{″}}(\xi )f(x)}}{x-x^{\ast }}=1-\frac{f(x)-f(x^{\ast })}{x-x^{\ast }}\frac{1}{f^{{}^{\prime }}(x)-\frac{1}{2}{f}^{{}^{″}}(\xi )f(x)}$$

所以，

$${\phi }^{{}^{\prime }}(x^{\ast })=\underset{x\to x^{\ast }}{lim}\frac{\phi (x)-\phi (x^{\ast })}{x-x^{\ast }}=1-f^{{}^{\prime }}(x^{\ast })\frac{1}{f^{{}^{\prime }}(x^{\ast })}=0.$$

因为 $f^{{}^{\prime }}(x^{\ast })\ne 0$，所以，Steffensen 方法至少是二阶收敛的。

注意，Steffensen 方法是严格二阶收敛的，但是，证明这个所需的知识不在学习范围内，暂时不作证明。

按：本文给出的 Steffensen 方法是华科的计算方法课本上的。网上还有其他的形式，在符号上略有区别，但是证明方法相同，而且，英文的证明在网上比较多。