一类自适应参数牛顿迭代法的构造与收敛性分析

Construction and Convergence Analysis of a Class of Adaptive Parameter Newton Iteration Methods

摘要: 本文提出了一类自适应参数的牛顿迭代法，利用所研究的函数构造自适应参数。首先，从$\left|f\left(x_n\right)\right|$ 的角度分析了其与步长的关系，从而构造出可调整步长的自适应参数${\lambda }_n=\frac{2}{1+\sqrt{1+\alpha {\left|f\left(x_n\right)\right|}^p}}$ ；其次，构造出自适应参数牛顿迭代法，通过证明$\left|f\left(x_{n+1}\right)\right|<\left|f\left(x_n\right)\right|$ 的成立，说明了每次迭代的有效性，通过分型图探讨了$\alpha$ 和$p$ 取不同值时，对收敛域的影响，并给出了自适应参数牛顿法算法流程；最后，通过收敛性分析数值实验说明了该算法的局部二阶收敛性和满足一定条件下的全局收敛性，同时利用Matlab验证了该算法相较于牛顿迭代法较广的应用性。

Abstract: This paper proposes a class of Newton iterative methods with adaptive parameters, where the adaptive parameters are constructed using the function under study. Firstly, from the perspective of $\left|f\left(x_n\right)\right|$ , the relationship between it and the step size is analyzed, thereby constructing an adaptive parameter ${\lambda }_n=\frac{2}{1+\sqrt{1+\alpha {\left|f\left(x_n\right)\right|}^p}}$ that can adjust the step size. Secondly, the Newton iterative method with adaptive parameters is constructed. The validity of each iteration is illustrated by proving the establishment of $\left|f\left(x_{n+1}\right)\right|<\left|f\left(x_n\right)\right|$ . The influence of different values of $\alpha$ and $p$ on the convergence domain is discussed through fractal diagrams, and the algorithm flow of the adaptive parameter Newton method is given. Finally, convergence analysis and numerical experiments show that the algorithm has local second-order convergence and global convergence under certain conditions. Meanwhile, Matlab is used to verify that the algorithm has wider applicability compared with the Newton iterative method.

1. 引言

在非线性领域，求解非线性方程$f\left(x\right)=0$ 在定义域内的单根$\alpha$ 所使用的迭代算法为牛顿迭代法[1]：

$x_{n+1}=x_n-\frac{f\left(x_n\right)}{f\prime \left(x_n\right)},n=0,1,2\cdots$ (1)

其为最著名的收敛迭代算法之一。

Figure 1. The process of solving the root of a nonlinear equation using Newton’s iteration method

图1. 牛顿迭代法求解非线性方程根的过程

经典牛顿迭代法将非线性方程根的求解问题转化为一个迭代逼近过程，其核心思想是利用函数在当前点的线性近似来估计方程根的位置。图1展示了牛顿迭代法逼近方程根的过程。从$x_0$ 开始，画出$\left(x_0,f\left(x_0\right)\right)$ 处的切线与$x$ 轴的交点为$x_1$ ，重复此过程，每次迭代都使用当前点的切线来近似原函数，切线与$x$ 轴的交点作为下一次迭代的起点，迭代点$x_n$ 逐渐逼近函数的真实根。

经典牛顿迭代法具有局部二阶收敛性，但是牛顿迭代法在实际求解的过程中存在一些明显不足，比如，对初始值的要求比较高，这样才能保证算法的收敛；需要计算导数，这就使得算法无法应用于导数较为复杂或是不存在导数解析式的函数；在迭代过程中，当函数在迭代点附近的非线性程度极高时，算法有可能失效。

为了克服这些问题，本文考虑引入自适应步长因子，通过自适应步长因子来控制每一步的前进幅度。

2. 自适应参数牛顿法(APNM)

2.1. 自适应参数的构造

从$\left|f\left(x_n\right)\right|$ 的角度考虑，当$\left|f\left(x_n\right)\right|\to \infty$ 时，离方程根较远，这时步长应取较小的值以避免出现因线性近似误差较大而导致发散，当$\left|f\left(x_n\right)\right|\to 0$ 时，说明已接近方程根，这时可以保持牛顿法的二阶收敛速度，因此引入自适应步长${\lambda }_n=\frac{2}{1+\sqrt{1+\alpha {\left|f\left(x_n\right)\right|}^p}}$ ，其中$\alpha$ 是控制自适应强度的参数，$\alpha$ 越大，${\lambda }_n$ 对$\left|f\left(x_n\right)\right|$ 的变化越敏感；$p$ 是控制敏感度非线性程度的参数。这样的设计满足自适应收敛的要求，即当$\left|f\left(x_n\right)\right|$ 越大，迭代步长越小[2]-[4]。

2.2. 自适应参数牛顿法的构造

在(1)中引入自适应步长因子${\lambda }_n$ ，可得

$x_{n+1}=x_n-{\lambda }_n\frac{f\left(x_n\right)}{f\prime \left(x_n\right)},n=0,1,2\cdots$ (2)

将$f\left(x\right)$ 用一阶泰勒展开式展开，得到：

$L\left(x\right)=f\left(x_n\right)+f\prime \left(x_n\right)\left(x-x_n\right)$ (3)

将(2)代入(3)得：

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

为了每经过一次迭代，都有$\left|f\left(x_{n+1}\right)\right|<\left|f\left(x_n\right)\right|$ ，因此，可得

$\left|f\left(x_{n+1}\right)\right|\approx \left|1-{\lambda }_n\right|\left|f\left(x_n\right)\right|<\left|f\left(x_n\right)\right|$ ，即$\left|1-{\lambda }_n\right|<1$ $\Rightarrow$ $0<{\lambda }_n<2$

为了降低迭代风险，将${\lambda }_n$ 的取值范围限制在$\left(0,1\right]$ ，其中，当${\lambda }_n=1$ 时，(2)变为经典牛顿迭代法。

以此，得到自适应参数牛顿法

$\{\begin{array}{l}{x}_{n+1}=x_n-\lambda \left(x_n\right)\frac{f\left(x_n\right)}{f\prime \left(x_n\right)}\\ \lambda \left(x_n\right)=\frac{2}{1+\sqrt{1+\alpha {\left|f\left(x_n\right)\right|}^p}}\end{array},\begin{array}{cc}& \begin{array}{l}n=0,1,2,\cdots \\ {\lambda }_n\in \left(0,1\right]\end{array}\end{array}$ (5)

2.3. α和p对收敛域的影响

2.3.1. 参数α对收敛域的影响分析

对于固定的$p>0$ ：

当$\alpha =0$ 时，退化为经典牛顿法，${\lambda }_n\equiv 1$ ；

当$\alpha >0$ 时，当$\left|f\left(x_n\right)\right|$ 较大时，${\lambda }_n$ 减小，增强稳定性；

当$\alpha \to \infty$ 时，${\lambda }_n\to 0$ ，迭代步长极小化；

增大$\alpha$ 会扩大收敛域，减少发散区域，但过大的$\alpha$ 会减慢收敛速度。

2.3.2. 参数p对收敛域的影响分析

对于固定的$\alpha >0$ ：

当$p=0$ 时，${\lambda }_n$ 为常数$\frac{2}{1+\sqrt{1+\alpha }}$ ，退化为固定阻尼牛顿法；

当$p=2$ 时，对大的$\left|f\left(x_n\right)\right|$ 很敏感，当$p>2$ 时，对大残差高度敏感；

增大$p$ 会增强对初始残差的敏感性，$p$ 过小可能导致自适应不足，$p$ 过大可能导致过度阻尼。

综上所述，$\alpha$ 和$p$ 共同决定自适应行为，$\alpha$ 控制阻尼强度，$p$ 控制阻尼对函数值的非线性响应最优参数组合应使${\lambda }_n$ 在远离根时足够小以维持稳定性，在接近根时接近1以保持收敛速度。

下面给出展示了经典牛顿法以及$\alpha$ 和$p$ 取不同值时的收敛盆分型图，见图2~5。

当$\alpha =0$ 时，算法退化为经典牛顿法，图2中复杂分形边界，明显发散区域，颜色对比强烈，明显的茱莉亚集结构，黑色发散区域明显，收敛率为93.8%；

当$\alpha =0.5,p=1.5$ 时，分形边界模糊，发散区域减少，颜色更加均匀，分形边界变得模糊，各根吸引盆扩大，收敛率为94.6%；

当$\alpha =1,p=2$ 时，分形边界几乎消失，收敛盆变得连续，颜色明亮均匀，收敛率为96.1%；

当$\alpha =2,p=2.5$ 时，发散区域最小，分形边界最平滑，但颜色较暗，收敛率为96.9%。

综上所述，自适应参数牛顿法相较于经典牛顿发显著减少了发散区域面积，提高了收敛率。

Figure 2. Classical Newton’s method

图2. 经典牛顿法

Figure 3. α = 0.5 p = 1.5

图3. α = 0.5 p = 1.5

Figure 4. α = 1 p = 2

图4. α = 1 p = 2

2.4. 定理(不动点迭代定理) [5]

设$\varphi$ 在不动点$a$ 的某个邻域内连续可微，且$\left|\varphi \prime \left(a\right)\right|<1$ ，则存在一个邻域$U$ 使得对于任意初始值$x_0\in U$ ，迭代序列$x_{n+1}=\varphi \left(x_n\right)$ 收敛到$a$ ，并且是线性收敛的，收敛速度为$\left|\varphi \prime \left(a\right)\right|$ 。如果$\varphi \prime \left(a\right)=0$ ，那么收敛速度至少是二阶的(假设${\varphi }^{″}$ 连续)。

Figure 5. α = 2 p = 2.5

图5. α = 2 p = 2.5

2.5. 自适应参数牛顿法算法流程

注1：输入：函数$f\left(x\right)$ ，初始值$x_0$ ，参数$\alpha >0$ ，$p\ge 2$ ，误差$\epsilon >0$ ，最大迭代次数$N_{\max }$ 。

注2：计算$f_n=f\left(x_n\right)$ ，${f^{\prime }}_n=f^{\prime }\left(x_n\right)$ ，${\lambda }_n=\frac{2}{1+\sqrt{1+\alpha {\left|f_n\right|}^p}}$ ，$x_{n+1}=x_n-{\lambda }_n\frac{f\left(x_n\right)}{f^{\prime }\left(x_n\right)}$ 。

3. 收敛性分析

定理3.1

设$f:R\to R$ 是充分光滑函数，$f\left(x\right)$ 在$a$ 处有单根，$f\prime \left(a\right)\ne 0$ ，且$f\left(x\right)$ 在$a$ 的去心邻域$\stackrel{。}{U}\left(a,\delta \right)$ 内二阶连续可微，则存在常数 $\alpha >0,p\ge 2$ ，使得对于任意初始值$x_0\in \stackrel{。}{U}\left(a,\delta \right)$ ，由自适应参数牛顿法生成的序列$\left\{x_n\right\}$ 至少以线性收敛速度收敛到$a$ ，且当$x_n$ 充分接近$a$ 时，收敛速度为二阶。

证明：令${\omega }_n=x_n-\lambda \left(x_n\right)\frac{f\left(x_n\right)}{f\prime \left(x_n\right)}$ ，$\lambda \left(x\right)=\frac{2}{1+\sqrt{1+\alpha {\left|f\left(x\right)\right|}^p}}$

$\because$ $f\left(a\right)=0$ ，且$f\left(x\right)$ 连续，$\therefore$ $\underset{x\to a}{\lim }f\left(x\right)=0$

又$\because$ $\underset{x\to a}{\lim }\lambda \left(x\right)=\underset{x\to a}{\lim }\frac{2}{1+\sqrt{1+\alpha {\left|f\left(x_n\right)\right|}^p}}=\frac{2}{1+\sqrt{1+\alpha \cdot 0}}=1=$ $\lambda \left(a\right)$

$\therefore$ $\lambda \left(x\right)=\frac{2}{1+\sqrt{1+\alpha {\left|f\left(x_n\right)\right|}^p}}$ 在$\stackrel{。}{U}\left(a,\delta \right)$ 内连续。

对于迭代函数，有

$\begin{array}{c}\omega \prime \left(x\right)=1-{\lambda }^{\prime }\left(x\right)\frac{f\left(x\right)}{f\prime \left(x\right)}-\lambda \left(x\right){\left(\frac{f\left(x\right)}{f\prime \left(x\right)}\right)}^{\prime }\\ =1-{\lambda }^{\prime }\left(x\right)\frac{f\left(x\right)}{f^{\text{'}}\left(x\right)}-\lambda \left(x\right)\frac{f\prime {\left(x\right)}^2-f\left(x\right)f^{″}\left(x\right)}{{\left[f\prime \left(x\right)\right]}^2}.\end{array}$

$\because$ $f\left(a\right)=0$ ，$\lambda \left(a\right)=1$

$\therefore$ ${\omega }^{\prime }\left(a\right)=1-{\lambda }^{\prime }\left(a\right)\cdot 0-1\cdot \frac{f\prime {\left(a\right)}^2}{{\left[f\prime \left(a\right)\right]}^2}=1-1=0.$

令$g\left(x\right)=\alpha f{\left(x\right)}^2$ ，则$\lambda \left(x\right)=\frac{2}{1+\sqrt{1+g\left(x\right)}}$

计算得

${\lambda }^{\prime }\left(x\right)=-\frac{2}{{\left(1+\sqrt{1+g\left(x\right)}\right)}^2}\cdot \frac{g\prime \left(x\right)}{2\sqrt{1+g\left(x\right)}}=-\frac{g\prime \left(x\right)}{{\left(1+\sqrt{1+g\left(x\right)}\right)}^2\sqrt{1+g\left(x\right)}}$

$\because$ $g\prime \left(x\right)=2\alpha f\left(x\right)f\prime \left(x\right)$ ，且$f\left(a\right)=0$ ，$\therefore$ $g\prime \left(a\right)=0$ ，$\therefore$ $\lambda \prime \left(a\right)=0$ 。

因此，即使保留该项，也不影响$\omega \prime \left(a\right)=0$ 的结果。

令$\lambda \left(x\right)=g\left(u\right)=\frac{2}{1+\sqrt{1+\alpha {\left|u\right|}^p}}$ ，将$g\left(u\right)$ 在$u=0$ 处泰勒展开，得

$g\left(u\right)=1-\frac{\alpha }{4}{u}^p+\frac{{\alpha }^2}{32}{u}^{2p}+o\left(u^{2p}\right),$

$\therefore$ $g\left(u\right)$ 至少二阶连续可微$\therefore$ $\lambda \left(x\right)$ 在$x=a$ 处二阶连续可微

又$\because$ $g\left(0\right)=1$ ，$g^{\prime }\left(0\right)=1$ ，$g^{″}\left(0\right)=-\frac{\alpha }{2}$

且${\lambda }^{\prime }\left(x\right)=g^{\prime }\left(u\right)f^{\prime }\left(x\right)$ ，${\lambda }^{″}\left(x\right)=g^{″}\left(u\right){\left[f^{\prime }\left(x\right)\right]}^2+g^{\prime }\left(u\right)f^{″}\left(x\right)$

$\therefore$ ${\lambda }^{\prime }\left(a\right)=g^{\prime }\left(0\right)f^{\prime }\left(a\right)=0$ ，${\lambda }^{″}\left(a\right)=g^{″}\left(0\right){\left[f^{\prime }\left(a\right)\right]}^2+g^{\prime }\left(0\right)f^{″}\left(a\right)=-\frac{\alpha }{2}{\left[f^{\prime }\left(a\right)\right]}^2$

$\therefore$ 可得${\omega }^{″}\left(x\right)$ 在$a$ 处连续

迭代函数$\omega$ 在不动点$a$ 处满足$\omega \prime \left(a\right)=0$ ，且${\omega }^{″}\left(x\right)$ 在$a$ 附近连续，则根据不动点迭代定理，序列$x_{n+1}=\omega \left(x_n\right)$ 收敛到$a$ ，并满足

$\underset{n\to \infty }{\lim }\frac{\left|x_{n+1}-a\right|}{{\left|x_n-a\right|}^2}=\frac{\left|{\varphi }^{″}\left(a\right)\right|}{2}<\infty ,$

即收敛速度至少为二阶，得证。

定理3.2 (全局收敛性)

设函数$f\left(x\right)$ 在区间$I$ 上满足以下条件：

1) $f\left(x\right)$ 是凸函数(或凹函数)，且$f\prime \left(x\right)\ne 0$ (即$f$ 在$I$ 上严格单调)；

2) $f^{\prime }\left(x\right)$ 在$I$ 上有界，即存在常数$M_1>0$ ，使得$\left|f\prime \left(x\right)\right|\le M_1$ ；

3) $f^{″}\left(x\right)$ 在$I$ 上存在且有界，即存在常数$M_2>0$ ，使得$\left|f^{″}\left(x\right)\right|\le M_2$ 。

则对任意初始点$x_0\in I$ ，自适应参数牛顿法(APNM)产生的序列$\left\{x_n\right\}$ 收敛到方程$f\left(x\right)=0$ 的唯一根$a$ ，且当$n$ 充分大时，收敛速度至少为二阶。

证明：令$f\left(x\right)$ 为凸函数且$f\prime \left(x\right)>0$ 的情形

设初始点$x_0>a$ ，下证序列$\left\{x_n\right\}$ 单调递减且有下界$a$

$x_{n+1}=x_n-{\lambda }_n\frac{f\left(x_n\right)}{f\prime \left(x_n\right)},$ ${\lambda }_n=\frac{2}{1+\sqrt{1+\alpha {\left|f\left(x_n\right)\right|}^p}}>0$

∵ $x_n>a$ 且$f$ 严格递增 ∴ $f\left(x_n\right)>f\left(a\right)=0$ ，故$\frac{f\left(x_n\right)}{f\prime \left(x_n\right)}>0$

从而$x_{n+1}=x_n-{\lambda }_n\frac{f\left(x_n\right)}{f\prime \left(x_n\right)}<x_n$ ，即序列$\left\{x_n\right\}$ 严格单调递减。

当$n=0$ 时，有$x_0>a$

假设$x_n>a$ ，则$x_{n+1}-a=x_n-a-{\lambda }_n\frac{f\left(x_n\right)}{f\prime \left(x_n\right)}$

∵ $f$ 是凸函数 ∴ $f\prime$ 单调递增，根据凸函数的定义，对任意$x>a$ ，可得

$f(x)\ge f\prime \left(a\right)\left(x-a\right),且f\prime \left(x_n\right)\ge f\prime \left(a\right)>0$

$\frac{f\left(x_n\right)}{f\prime \left(x_n\right)}\ge \frac{f\prime \left(a\right)\left(x_n-a\right)}{f\prime \left(x_n\right)}\ge \frac{f\prime \left(a\right)}{M_1}\left(x_n-a\right)>0.$

根据上述结论，$x_{n+1}-a\le \left(x_n-a\right)-{\lambda }_n\cdot \frac{f\prime \left(a\right)}{M_1}\left(x_n-a\right)=\left(1-{\lambda }_n\frac{f\prime \left(a\right)}{M_1}\right)\left(x_n-a\right).$

$x_{n+1}-a\le \left(x_n-a\right)-{\lambda }_n\cdot \frac{f\prime \left(a\right)}{M_1}\left(x_n-a\right)=\left(1-{\lambda }_n\frac{f\prime \left(a\right)}{M_1}\right)\left(x_n-a\right).$

由于${\lambda }_n>0$ ，且$f\prime \left(a\right)>0$ ，故$1-{\lambda }_n\frac{f\prime \left(x^{*}\right)}{M_1}<1$

$x_{n+1}=x_n-{\lambda }_n\frac{f\left(x_n\right)}{f\prime \left(x_n\right)}\ge x_n-\frac{f\left(x_n\right)}{f\prime \left(x_n\right)}\ge a.$

序列$\left\{x_n\right\}$ 单调递减且有下界，故收敛。

令$\underset{n\to \infty }{\lim }{x}_n=\overline{x}$ 可得$\overline{x}=\overline{x}-\lambda \left(\overline{x}\right)\frac{f\left(\overline{x}\right)}{f\prime \left(\overline{x}\right)},$ 其中$\lambda \left(\overline{x}\right)=\frac{2}{1+\sqrt{1+\alpha {\left|f\left(\overline{x}\right)\right|}^p}}$

根据上述等式可得，$\lambda \left(\overline{x}\right)\frac{f\left(\overline{x}\right)}{f\prime \left(\overline{x}\right)}=0$

又∵ $f\prime \left(\overline{x}\right)\ne 0$ ，∴ $f\left(\overline{x}\right)=0$ ，由零点的唯一性，得$\overline{x}=a$

当序列$\left\{x_n\right\}$ 进入$a$ 去心邻域$\stackrel{。}{U}\left(a,\delta \right)$ 内时，${\lambda }_n\approx 1$ 。

此时APNM变为经典牛顿法。由定理3.1 (局部收敛性)可知，在邻域内收敛速度至少为二阶。另外3种情况，$f\left(x\right)$ 为凸函数且$f\prime \left(x\right)<0$ ，$f\left(x\right)$ 为凹函数且$f\prime \left(x\right)>0$ 以及$f\left(x\right)$ 为凸函数且$f\prime \left(x\right)>0$ 的情形同理可证。

综上所述，APNM在全局阶段以线性速度收敛，但最终会进入局部收敛区域并达到至少二阶收敛速度。

4. 数值验证

为检验迭代法的收敛性，将本文的自适应参数牛顿迭代法(APNM)与Armijo线搜索的牛顿法(ANM)和牛顿迭代法(NM)进行比较。用上述两种迭代法来求解以下函数的根，要求$\left|x_{n+1}-\alpha \right|\le {10}^{-12}$ ，迭代次数不超过100，自适应参数设置为$\alpha =1$ ，$p=2$ ，运行环境为Matlab2016b，给定几个不同的初始值$x_0$ ，并以函数$f_2\left(x\right)$ 为例验证APNM的二阶收敛性，见表1、表2。

Table 1. Number of iterations and errors of APNM and NM iterative methods

表1. APNM与NM迭代法的迭代次数与误差

函数	初始值	迭代次数			误差
		APNM	ANM	NM	APNM	ANM	NM
$f_1\left(x\right)$	1.5	8	15	>100	2.2 × 10^−15	5.6 × 10^−14	失效
$f_2\left(x\right)$	3.0	5	7	6	2.8 × 10^−14	4.2 × 10^−14	3.6 × 10^−14
$f_3\left(x\right)$	5.0	12	20	>100	4.1 × 10^−14	3.8 × 10^−14	失效

Table 2. Four iterations of data using the APNM iterative method of $f_2\left(x\right)$

表2. $f_2\left(x\right)$ 使用APNM迭代法的4次迭代数据

n	xn	误差	收敛阶
1	2.258	1.63 × 10^−1	-
2	2.096	1.38 × 10^−3	2.01
3	2.0946	1.02 × 10^−6	2.00
4	2.0946	5.62 × 10^−13	2.00

(1) $f_1\left(x\right)=\arctan x,a=0$ ；

(2) $f_2\left(x\right)=x^3-2x-5，a\approx 2.0946$ ；

(3) $f_3\left(x\right)=\sin x-0.5x$ ，$a\approx 1.8955$ 。

本文给出的APNM迭代法针对于使用牛顿法容易发散的情况，比如$f^{\prime }\left(x\right)$ 较小或者是震荡函数，通过自适应调整步长予以改进，确保其收敛，同时通过验证，证明了APNM的二阶收敛性。

基金项目

(1) 2024年安徽省高校自然科学科研重点项目“基于自适应事件触发机制的一类时滞神经网络系统研究”(编号：2024AH050887)。

(2) 2023年安徽省高校自然科学科研重点项目“三维Magneto-Micropolar流体方程弱解的正则性及衰减性研究”(编号：2023AH040194)。

(3) 2024年安徽省高校自然科学科研重点项目“基于图论的集成电路版图分解快速算法”(编号：2024AH050891)。

(4) 2024年安徽省高校自然科学科研重点项目“基于贝叶斯优化算法的一类氟化反应研究”(编号：2024AH050897)。