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

Steffensen 方法的推导

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

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

弦截法的定义及推导比较简单，这里不再赘述，然后我们来看如何将弦截法改造成 Steffensen 方法：若弦截法产生的迭代序列 \(\{ x_k \}\) 充分接近于精确解 \(x^*\)，则 \(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))}, \quad k = 1, 2,... \ .\]

证明 Steffensen 方法的二阶收敛性

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

证明：

由 Steffensen 迭代公式，有

\[\varphi(x) = x - \frac{f(x)}{f(x) - f(x - f(x))}\]

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

\[\displaystyle f(x - f(x)) = f(x) - f^{'}(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^{'}(x)f(x) - \frac{1}{2}f^{''}f^{2}(x)}{f(x)} = f^{'}(x) - \frac{1}{2} f^{''}(\xi) f(x) .\]

进而，

\[\varphi (x) = x - \frac{f^{2} (x)}{f(x) - f(x - f(x))} = x - \frac{f(x)}{f^{'} (x) - \frac{1}{2} f^{''} (\xi) f(x)}.\]

因此，

\[\frac{\varphi(x) - \varphi(x^*)}{x - x^*} = \frac{x - \frac{f(x)}{f^{'} (x) - \frac{1}{2} f^{''} (\xi) f(x)} - x^*}{x - x^*} = \frac{x - x^* - \frac{f(x)}{f^{'} (x) - \frac{1}{2} f^{''} (\xi) f(x)}}{x - x^*} = 1 - \frac{f(x) - f(x^*)}{x - x^*} \frac{1}{f^{'} (x) - \frac{1}{2} f^{''} (\xi) f(x)}\]

所以，

\[\varphi^{'} (x^*) = \lim_{x \to x^*} \frac{\varphi(x) - \varphi(x^*)}{x - x^*} = 1 - f^{'} (x^*) \frac{1}{f^{'} (x^*)} = 0.\]

因为 \(f^{'}(x^*) \neq 0\)，所以，Steffensen 方法至少是二阶收敛的。

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

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