一种牛顿迭代法的改进——牛顿弦割迭代法

An Improvement of Newton’s Method —Newton’s Chord Secant Method

摘要: 牛顿迭代法是非线性方程求根的一个常用的方法，它具有至少二阶的收敛速度，但是需要计算一阶导数值。本文针对牛顿迭代法进行改进，以弦割代替导数，只需计算函数值，不需计算一阶导数值，同样也具有至少二阶的收敛速度，并且形式简单，计算量小，数值试验表明该迭代公式十分有效。

Abstract: Newton’s method is a commonly used way to find roots of nonlinear equations. It has at least the second-order convergence rate, but it needs to calculate the first-order derivative value. In this paper, the Newton method is improved. The derivative is replaced by a chord secant. It only needs to calculate the value of the function and does not need to calculate the value of the first derivative. It also has at least the second order of convergence speed, and the form is simple and the calculation amount is small. Numerical experiments show that the iterative formula is very effective.

1. 引言

非线性方程 $f\left(x\right)=0$ 的解法是数值分析 [1] 研究的重要课题之一，其解法多种多样，有不动点迭代法 [2]，牛顿迭代法 [3] [4] [5]。最经典的牛顿迭代法具有二阶的收敛速度，但需计算一阶导数值。本文给出了避免一阶导数计算的一个新的迭代公式，它无需计算导数值，只需计算函数值，但也能和经典的牛顿迭代法一样，达到二阶的收敛速度。

2. 非线性方程的求根方法

2.1. 牛顿迭代法

广泛使用的牛顿迭代法公式：

$x_{n+1}=x_n-\frac{f\left(x_n\right)}{f^{\prime }\left(x_n\right)}$ (1)

在公式(1)中，需要计算一阶导数值，在函数本身复杂的情况下是十分不利的。

2.2. 牛顿弦割迭代法

若考虑到函数的表达式十分复杂，那么为了避免导数值繁杂的计算，本文提出用弦割

$\frac{f\left(x_n+\lambda f\left(x_n\right)\right)-f\left(x_n\right)}{\lambda f\left(x_n\right)}0<\lambda <1$ (2)

来近似代替导数值。可以看到，这个弦割线只包括函数值和参数 $\lambda$ ，形式简单，摒弃导数值，保留函数值。因此，本文给出牛顿弦割迭代公式：

$x_{n+1}=x_n-\frac{f\left(x_n\right)}{\frac{f\left(x_n+\lambda f\left(x_n\right)\right)-f\left(x_n\right)}{\lambda f\left(x_n\right)}}0<\lambda <1$

即

$x_{n+1}=x_n-\frac{\lambda f^2\left(x_n\right)}{f\left(x_n+\lambda f\left(x_n\right)\right)-f\left(x_n\right)}0<\lambda <1$ (3)

选取适当的 $\lambda$ ，牛顿割线迭代法具有至少二阶的收敛速度。

3. 相关定义、定理

3.1. 定义1

设迭代关系式 $x_{n+1}=x_n-\phi \left(x_n\right)$ ，在 $n\to \infty$ 时，极限为方程 $x=\phi \left(x\right)$ 的一个根 $x^{*}$ ，记每次它的迭代误差为 $e_n=x_n-x^{*}$ ，在 $n\to \infty$ 时，有 ${\lim }_{n\to \infty }\frac{e_{n+1}}{e_n^p}=c\left(c\ne 0\right)$ ，就称 $x_{n+1}=x_n-\phi \left(x_n\right)$ 为p阶收敛。

3.2. 定理1

设非线性函数 $f\left(x\right)$ 的零点为 $x^{*}$ ，在 $x^{*}$ 的某邻域二阶导数存在，且 $f^{\prime }\left(x\right)\ne 0,f^{″}\left(x\right)\ne 0$ ，则(3)在 $x^{*}$ 的领域附近至少达到二阶收敛。

证 把 $f\left(x_n\right)$ 在 $x^{*}$ 点泰勒展开

$f\left(x_n\right)=f^{\prime }\left(x^{*}\right)e_n+\frac{f^{″}\left(x^{*}\right)}{2}{e}_n^2+o\left(e_n^2\right)$ (4)

$x_n+\lambda f\left(x_n\right)-x^{*}=\left(1+\lambda f^{\prime }\left(x^{*}\right)\right)e_n+\frac{\lambda f^{″}\left(x^{*}\right)}{2}{e}_n^2+o\left(e_n^2\right)$ (5)

${\left(x_n+\lambda f\left(x_n\right)-x^{*}\right)}^2={\left(1+\lambda f^{\prime }\left(x^{*}\right)\right)}^2{e}_n^2+o\left(e_n^2\right)$ (6)

把 $f\left(x_n+\lambda f\left(x_n\right)\right)$ 在 $x^{*}$ 点泰勒展开，带入(4)和(5)

$f\left(x_n+\lambda f\left(x_n\right)\right)=f^{\prime }\left(x^{*}\right)\left(1+\lambda f^{\prime }\left(x^{*}\right)\right)e_n+\frac{f^{″}\left(x^{*}\right)}{2}\left({\lambda }^2{f^{\prime }}^2\left(x^{*}\right)+3\lambda f^{\prime }\left(x^{*}\right)+1\right)e_n^2+o\left(e_n^2\right)$ (7)

由(4)和(7)

$f\left(x_n+\lambda f\left(x_n\right)\right)-f\left(x_n\right)=\lambda {f^{\prime }}^2\left(x^{*}\right)e_n+\frac{f^{″}\left(x^{*}\right)f^{\prime }\left(x^{*}\right)}{2}\left({\lambda }^2{f}^{\prime }\left(x^{*}\right)+3\lambda \right)e_n^2+o\left(e_n^2\right)$ (8)

所以

$\begin{array}{c}{x}_{n+1}=x_n-\frac{\lambda f^2\left(x_n\right)}{f\left(x_n+\lambda f\left(x_n\right)\right)-f\left(x_n\right)}\\ =x_n-\frac{\lambda \left({f^{\prime }}^2\left(x^{*}\right)e_n^2+f^{\prime }\left(x^{*}\right)f^{″}\left(x^{*}\right)e_n^3\right)+o\left(e_n^3\right)}{\lambda {f^{\prime }}^2\left(x^{*}\right)e_n+\frac{f^{″}\left(x^{*}\right)f^{\prime }\left(x^{*}\right)}{2}\left({\lambda }^2{f}^{\prime }\left(x^{*}\right)+3\lambda \right)e_n^2+o\left(e_n^2\right)}\\ =x_n-\frac{e_n+\frac{f^{″}\left(x^{*}\right)}{f^{\prime }\left(x^{*}\right)}{e}_n^2+o\left(e_n^2\right)}{1+\frac{f^{″}\left(x^{*}\right)}{2f^{\prime }\left(x^{*}\right)}\left(\lambda f^{\prime }\left(x^{*}\right)+3\right)e_n+o\left(e_n\right)}\\ =x_n-\left(e_n+\frac{f^{″}\left(x^{*}\right)}{f^{\prime }\left(x^{*}\right)}{e}_n^2+o\left(e_n^2\right)\right)\left(1-\frac{f^{″}\left(x^{*}\right)}{2f^{\prime }\left(x^{*}\right)}\left(\lambda f^{\prime }\left(x^{*}\right)+3\right)e_n+o\left(e_n\right)\right)\\ =x_n-e_n+\frac{f^{″}\left(x^{*}\right)}{2f^{\prime }\left(x^{*}\right)}\left(\lambda f^{\prime }\left(x^{*}\right)+1\right)e_n^2+o\left(e_n^2\right)\end{array}$ (9)

两边同时减去 $x^{*}$ 有

$x_{n+1}-x^{*}=x_n-x^{*}-e_n+\frac{f^{″}\left(x^{*}\right)}{2f^{\prime }\left(x^{*}\right)}\left(\lambda f^{\prime }\left(x^{*}\right)+1\right)e_n^2+o\left(e_n^2\right)$

$e_{n+1}=\frac{f^{″}\left(x^{*}\right)}{2f^{\prime }\left(x^{*}\right)}\left(\lambda f^{\prime }\left(x^{*}\right)+1\right)e_n^2+o\left(e_n^2\right)$ (10)

$\underset{n\to \infty }{\lim }\frac{e_{n+1}}{e_n^2}=\frac{f^{″}\left(x^{*}\right)}{2f^{\prime }\left(x^{*}\right)}\left(\lambda f^{\prime }\left(x^{*}\right)+1\right)\ne 0$ (11)

一定存在一个 $\lambda$ ，使得上式不等于0，得证。

4. 数值检验

实例1 设 $f\left(x\right)={\text{e}}^x-1$ ，求 $f\left(x\right)$ 在 $\left[-\text{1},\text{1}\right]$ 上的零点，见表1，精确零点： $x^{*}=0$ 。

Table 1. Numerical experiment about zeros of the function: f ( x ) = e x − 1

表1. $f\left(x\right)={\text{e}}^x-1$ 的零点数值检验

实例2 设 $f\left(x\right)=x-{\text{e}}^{-x}$ ，求 $f\left(x\right)$ 在 $\left[0,\text{1}\right]$ 上的零点，见表2，精确零点： $x^{*}=0.567143\cdots$ 。

Table 2. Numerical experiment about zeros of the function: f ( x ) = x − e − x

表2. $f\left(x\right)=x-{\text{e}}^{-x}$ 的零点数值检验

从上述实例数值检验结果看到，牛顿弦割迭代法形式优美，计算简单，充分挖掘函数值的信息价值，从而避免计算复杂的导数值，并且这种方法具有至少二阶的收敛迭代速度。另外，由于 $\lambda$ 取值的不同，使得本文公式求解非线性函数的零点也具有更多的灵活性和泛化性。

参考文献