本文考虑如下的线性方程组, 寻找一个向量$ x $使得

(1.1) $ \begin{eqnarray} f(x) = 0, \end{eqnarray} $

其中$ x = (x_1, x_2, \cdots, x_n)^T \in {{\Bbb R}} ^{n} $, $ f = (f_1, f_2, \cdots, f_n)^T: S\subseteq{{\Bbb R}} ^n \rightarrow {{\Bbb R}} ^{n} $是连续可微函数.

非线性方程组(1.1) 广泛地应用于各类科学与工程问题^{[2-3, 6, 19-21]}. 一般情况, 当方程规模较大时很难求得其精确解. 基于问题的重要性和应用性, 近些年关于快速有效构造求其近似解法引起许多学者广泛关注, 也出现了许多有效迭代算法. 最经典方法之一是利用牛顿迭代格式来求非线性方程组(1.1)

(1.2) $ \begin{eqnarray} x^{k+1} = x^{k}-(f'(x^k))^{-1}f(x^k), k = 1, 2, \cdots, \end{eqnarray} $

其中$ f'(x^k) $是函数$ f $在$ x^k $步的Jacobian矩阵. 另外, 一些高阶收敛速率的迭代法也十分盛行. 为了避免在Halley方法中计算二阶导数, Levin提出了一种具有三阶收敛速度的Halley型方法, 从而一种带有多函数算子的拟Halley算法被构造^[8]. 通过利用分解技术, 近来Shah也提出了一个带有高精度的迭代方法^[14]. 文献[9] 中Narang等人提出了一种求解非线性方程组(1.1) 的新的双参数Chebyshev-Halley类高精度迭代方法.

众所周知, 当方程组(1.1) 的根$ x^* $为重根时, 牛顿迭代格式(1.2) 可能不再适用或失效. Nedzhibov提出了一族多点迭代格式^[10]来求解非线性方程组(1.1) 的多重根问题. 文献[16] 通过间接求解一个变换函数$ g(x) = \frac{f(x)}{f'(x)} = 0 $从而求得原非线性方程组$ f(x) = 0 $的根.

基于以上分析, 本文引入适当的松弛参数, 推广了Halley-Newton型方法, 提出了求解(1.1)式的一类新的牛顿型迭代格式. 这类新的迭代方法如下

(1.3) $ \begin{eqnarray} x^{k+1} = x^{k}-\big(\beta f'(x^k)(f'(x^k))^T-\gamma f(x^k)\nabla ^2 f(x^k)\big)^{-1}\big(\alpha f(x^k)f'(x^k)\big). \end{eqnarray} $

事实上, 参数$ \alpha = 2 $, $ \beta = 2 $且$ \gamma = -1 $时即为Halley方法^{[8, 11-12, 18]}, 当参数$ \alpha = 1 $, $ \beta = 0 $且$ \gamma = -1 $其退化为经典牛顿法. 鉴于在适当范围内, 参数能更灵活有效地被选取, 从而可望所提出的算法有更高效的收敛性. 进一步, 我们通过引入了Armijo线搜索技术来加速其收敛性能. 在适当条件下, 给出上述迭代方法的收敛性分析.

本文剩余部分组织如下. 在第二节, 具体给出新的修正Halley-Newton算法来求解非线性方程组(1.1). 第三节详细分析了其收敛性能. 第四节数值实验部分充分说明了所提出的两种修正Halley-Newton迭代格式的有效性. 最后一节是结论部分.

本节, 在一些必要性假设下, 我们给出两种修正Halley-Newton法. 为了方便, 通篇文章我们利用了如下的一些符号: 假设$ x\in {{\Bbb R}} ^n $, $ A\in {{\Bbb R}} ^{n\times m} $, $ F(x)\in {{\Bbb R}} $. $ A^T $及$ A^{-1} $分别表示矩阵$ A $的转置和逆. $ \nabla F $和$ \nabla^2 F $分别表示可微函数$ F $的梯度和Hessian矩阵. $ F_k $, $ \nabla F_k $, $ \nabla^2 F_k $分别表示其在第$ k $步迭代的函数值$ F(x^k) $, $ \nabla F(x^k) $, $ \nabla^2 F(x^k) $. $ \|\cdot\| $表示欧式范数.

显然, 非线性方程组(1.1) 等价于如下优化问题

(2.1) $ \begin{eqnarray} \min\limits_{x\in S} F(x): = \|f(x)\|^2 = \sum\limits_{i = 1}^{n} f_{i}^2(x), S \subset {{\Bbb R}} ^n. \end{eqnarray} $

在提出求解问题(2.1) 的算法之前, 先给出如下一些必要性假设.

假设 2.1    假设$ F(x) $为二次连续可微的函数, 且如下定义的水平集有界

(2.2) $ \begin{eqnarray} {\mathbb L}(x_0) = \{x:x\in S \mid F(x)\leq F(x_0)\}. \end{eqnarray} $

假设 2.2    假设函数$ F(x) $的Hessian阵$ \nabla^2 F(x) $为Lipschitz连续的, 即存在Lipschitz系数$ L_1>0 $使得不等式

(2.3) $ \begin{eqnarray} \|\nabla^2 F(x)-\nabla^2 F(y)\|\leq L_1 \|x-y\| \end{eqnarray} $

成立.

易知, $ \nabla F(x) $也是Lipschitz连续的, 因此下面的不等式亦成立

(2.4) $ \begin{eqnarray} \|\nabla F(x)-\nabla F(y)\|\leq L_2 \|x-y\|, \end{eqnarray} $

其中$ L_2 $是Lipschitz常数.

鉴于在适当范围内通过选取更灵活且有效的参数有望能提高算法的收敛性. 因此, 构造了如下修正Halley-Newton法.

算法2.1(修正的Halley-Newton法1 (MHN1))

步1  给定初始点$ x^0 $及参数$ \alpha, \beta, \gamma. $设$ \mu \in(0, 1) $且$ \varepsilon $为任意小的正数. 令$ k: = 0 $.

步2  若$ \|\nabla F_k\|<\varepsilon $, 终止.

步3  解如下线性方程组

$ (\beta \nabla F_k\nabla F_{k}^{T}-\gamma F_k \nabla^2 F_{k})p^k = -\alpha F_k\nabla F_{k}. $

若系数矩阵$ \beta \nabla F_k\nabla F_{k}^{T}-\gamma F_k \nabla^2 F_{k} $为奇异阵, 则求解

$ (\beta \nabla F_k\nabla F_{k}^{T}-\gamma F_k \nabla F_{k}^2+\mu I)p^k = -\alpha F_k\nabla F_{k}. $

步4  更新迭代序列

$ x^{k+1} = x^{k}+p^k. $

令$ k: = k+1 $, 返回步$ 2 $.

事实上, 算法$ 2.1 $的迭代步长恒为$ 1 $. 若初始点选取不够理想, 可能导致无法获得良好收敛性效果. 因此我们进一步引入Armijo线搜索技术并给出如下算法.

算法2.2(修正的Halley-Newton法2 (MHN2))

步1  给定初始点$ x^0 $及参数$ \sigma\in (0, 0.5), \rho \in (0, 1), \beta, \gamma. $设$ \mu \in(0, 1) $且$ \varepsilon $为任意小的正数. 令$ k: = 0 $.

步2  若$ \|\nabla F_k\|<\varepsilon $, 终止.

步3  解如下线性方程组

$ (\beta \nabla F_k\nabla F_{k}^{T}-\gamma F_k \nabla^2 F_{k})p^k = - F_k\nabla F_{k}. $

若系数矩阵$ \beta \nabla F_k\nabla F_{k}^{T}-\gamma F_k \nabla^2 F_{k} $为奇异阵, 则求解

$ (\beta \nabla F_k\nabla F_{k}^{T}-\gamma F_k \nabla F_{k}^2+\mu I)p^k = -F_k\nabla F_{k}. $

步4  寻找最小的正整数$ m $使得下列不等式成立

(2.5) $ \begin{eqnarray} F(x^{k}+\rho^m p^k)\leq F(x^k)+\sigma \rho^m\nabla F_{k}^Tp^k. \end{eqnarray} $

令$ m_k: = m $.

步5  更新迭代序列

$ x^{k+1} = x^{k}+\rho^{m_k}p^k. $

令$ k: = k+1 $, 返回步$ 2 $.

本节是关于算法收敛性的分析. 首先, 我们给出著名的Sherman-Morrison-Woodbury矩阵求逆公式以及它的推广和变型^{[7, 17]}.

引理 3.1    假设$ U, V\in {{\Bbb R}} ^{n\times m} $且$ W \in {{\Bbb R}} ^{n\times n} $为非奇异矩阵. 若$ I+VW^{-1}U \in {{\Bbb R}} ^{n\times n} $非奇异, 则$ W+UV $亦是非奇异的. 且有

(3.1) $ \begin{eqnarray} (W+UV^T)^{-1} = W^{-1}-W^{-1}U(I+V^TW^{-1}U)^{-1}V^TW^{-1}, \end{eqnarray} $

其中$ I $表示适当维数的单位矩阵.

引理 3.2    假设向量$ u, v \in {{\Bbb R}} ^{n} $且$ W \in {{\Bbb R}} ^{n\times n} $为非奇异矩阵. 若$ 1+v^TW^{-1}u $为非零数, 则$ W+uv^T $是非奇异的. 且有

(3.2) $ \begin{eqnarray} (W+uv^T)^{-1} = W^{-1}-\frac{1}{1+v^TW^{-1}u}W^{-1}uv^T W^{-1}, \end{eqnarray} $

其中$ I $表示适当维数的单位矩阵.

引理 3.3    若假设2.1–2.2成立. 参数$ \beta $, $ \gamma $满足

(3.3) $ \begin{eqnarray} \frac{\beta}{\gamma}(\nabla F_{k}^{T}(F_{k}\nabla^2F_{k})^{-1}\nabla F_{k})\leq \frac{1}{2}, \end{eqnarray} $

则

(a) $ \Big|\frac{\beta \nabla F_{k}^{T}(\gamma F_{k}\nabla^2F_{k})^{-1}\nabla F_{k}}{\beta \nabla F_{k}^{T}(\gamma F_{k} \nabla^2F_{k})^{-1}\nabla F_{k}-1}\Big|<1; $

(b) $ (\frac{-\gamma F_{k}}{\beta}\nabla^2F_{k}+\nabla F_{k}\nabla F_{k}^{T})^{-1} = \frac{-\beta}{\gamma F_{k}}(\nabla^2F_{k})^{-1}\Big(I-\frac{\nabla F_{k}\nabla F_{k}^{T} (\frac{-\gamma F_{k}}{\beta}\nabla^2F_{k})^{-1}}{1+\nabla F_{k}^{T}(\frac{-\gamma F_{k}} {\beta}\nabla^2F_{k})^{-1}\nabla F_{k}}\Big). $

证    首先由(3.3) 式可得

(3.4) $ \begin{eqnarray} \beta(\nabla F_{k}^{T}(-\gamma F_{k}\nabla^2F_{k})^{-1}\nabla F_{k})\geq -\frac{1}{2}, \end{eqnarray} $

经过简单运算即可得第一个结论.

现令$ W = \frac{-\gamma F_{k}}{\beta}\nabla^2F_{k} $, $ u = v = \nabla F_{k}. $由引理3.1–3.2及(3.4) 式可得

(3.5) $ \begin{eqnarray} 1+v^TW^{-1}u = 1+\beta(\nabla F_{k}^{T}(-\gamma F_{k}\nabla^2F_{k})^{-1}\nabla F_{k})\geq \frac{1}{2}\neq 0. \end{eqnarray} $

这意味着$ W+uv^T $可逆, 因此有

(3.6) $ \begin{eqnarray} (W+uv^T)^{-1}& = &\big(\frac{-\gamma F_{k}}{\beta}\nabla^2F_{k}+\nabla F_{k} \nabla F_{k}^T\big)^{-1}\\ & = &\big(\frac{-\gamma F_{k}}{\beta}\nabla^2F_{k}\big)^{-1}-\big(\frac{-\gamma F_{k}}{\beta}\nabla^2F_{k}\big)^{-1}\\ &&\cdot\nabla F_{k}\Big(1+\nabla F_{k}^T\big(\frac{-\gamma F_{k}}{\beta}\nabla^2F_{k}\big)^{-1}\nabla F_{k}\Big)^{-1}\nabla F_{k}^T\big(\frac{-\gamma F_{k}}{\beta}\nabla^2F_{k}\big)^{-1}\\ & = &\frac{-\beta}{\gamma F_{k}}(\nabla^2F_{k})^{-1}\Big(I-\frac{\nabla F_{k}\nabla F_{k}^{T}(\frac{-\gamma F_{k}}{\beta}\nabla^2F_{k})^{-1}}{1+\nabla F_{k}^{T}(\frac{-\gamma F_{k}}{\beta}\nabla^2F_{k})^{-1}\nabla F_{k}}\Big). \end{eqnarray} $

引理3.3证毕.

定理 3.1    若假设2.1–2.2成立. 设序列$ p^{k} $由算法2.1产生, 即

(3.7) $ \begin{eqnarray} p^{k} = \alpha(\beta\nabla F_{k}\nabla F_{k}^T-\gamma \nabla F_{k}\nabla^2\nabla F_{k})^{-1}(-F_{k}\nabla F_{k}). \end{eqnarray} $

令

(3.8) $ \begin{eqnarray} \xi_1: = \frac{\delta}{2}+\delta|\alpha+\gamma|+\delta|\alpha|<1, \end{eqnarray} $

其中$ \delta: = \frac{\varrho L}{\gamma} $, $ L: = \max\{L_1, L_2\} $, $ \varrho: = \|(\nabla^2 F_0)^{-1}\| $. 则迭代

(3.9) $ \begin{eqnarray} x^{k+1} = x^{k}+p^{k}, k = 0, 1\cdots, \end{eqnarray} $

局部收敛到方程组$ (1) $的解$ x^* $.

证    由(3.7) 式以及引理3.3 (b) 可得

(3.10) $ \begin{eqnarray} p^{0}& = &\frac{\alpha}{\beta}(\nabla F_{0}\nabla F_{0}^T-\frac{\gamma \nabla F_{0}}{\beta}\nabla^2 F_{0})^{-1}(-F_{0}\nabla F_{0}){}\\ & = &\frac{\alpha}{\gamma}(\nabla^2F_{0})^{-1}\Big(I-\frac{\nabla F_{0}\nabla F_{0}^{T}(\frac{-\gamma F_{0}}{\beta}\nabla^2F_{0})^{-1}}{1+\nabla F_{0}^{T}(\frac{-\gamma F_{0}}{\beta}\nabla^2F_{0})^{-1}\nabla F_{0}}\Big)\nabla F_{0}. \end{eqnarray} $

利用引理3.3 (a), 假设2.1–2.2以及$ \|(\nabla^2F_{0})^{-1}\| $的有界性, 不难验证

(3.11) $ \begin{eqnarray} \|p^{0}\|&\leq&\big|\frac{\alpha}{\gamma}\big|\|(\nabla^2F_{0})^{-1}\|\bigg\|\nabla F_{0}-\nabla F_{0}\frac{\nabla F_{0}^{T}(\frac{-\gamma F_{0}}{\beta}\nabla^2F_{0})^{-1}\nabla F_{0}}{1+\nabla F_{0}^{T}(\frac{-\gamma F_{k}}{\beta}\nabla^2F_{0})^{-1}\nabla F_{k}}\bigg\|\\ &\leq&\big|\frac{2\alpha}{\gamma}\big|\varrho \|\nabla F_0\| \leq\big|\frac{2\alpha}{\gamma}\big|\varrho L\|x^0-x^*\|, \end{eqnarray} $

其中$ \varrho: = \|(\nabla^2 F_0)^{-1}\| $. 则我们进一步可得

(3.12) $ \begin{eqnarray} x^{1}-x^*& = &x^{0}+p^0-x^*\\ & = &x^{0}-x^*+\frac{\alpha}{\gamma}(\nabla^2F_{0})^{-1}\Big(I-\frac{\nabla F_{0}\nabla F_{0}^{T}(\frac{-\gamma F_{0}}{\beta}\nabla^2F_{0})^{-1}}{1+\nabla F_{0}^{T}(\frac{-\gamma F_{0}}{\beta}\nabla^2F_{0})^{-1}\nabla F_{0}}\Big)\nabla F_{0}\\ & = &(\nabla^2F_{0})^{-1}\Big(\nabla^2F_{0}(x^{k}-x^*)+\frac{\alpha}{\gamma}\Big(I-\frac{\nabla F_{0}\nabla F_{0}^{T}(\frac{-\gamma F_{0}}{\beta}\nabla^2F_{0})^{-1}}{1+\nabla F_{0}^{T}(\frac{-\gamma F_{0}}{\beta}\nabla^2F_{0})^{-1}\nabla F_{0}}\Big)\nabla F_{0}\Big)\\ & = &(\nabla^2F_{0})^{-1}\Big(\nabla^2F_{0}(x^{0}-x^*)+\frac{\alpha}{\gamma}\nabla F_{0}-\frac{\alpha}{\gamma}\frac{\nabla F_{0}\nabla F_{0}^{T}(\frac{-\gamma F_{0}}{\beta}\nabla^2F_{0})^{-1}\nabla F_{0}}{1+\nabla F_{0}^{T}(\frac{-\gamma F_{0}}{\beta}\nabla^2F_{0})^{-1}\nabla F_{0}}\Big). \end{eqnarray} $

注意到$ \nabla F^{*} = \nabla F(x^*) = 0 $, 则有

(3.13) $ \begin{eqnarray} \|x^{1}-x^*\|& = &\frac{1}{\gamma}\bigg\|(\nabla^2F_{0})^{-1}\Big(\gamma\nabla^2F_{0}(x^{0}-x^*)+\alpha\nabla F_{0} -\alpha\frac{\nabla F_{0}\nabla F_{0}^{T}(\frac{-\gamma F_{0}}{\beta}\nabla^2F_{0})^{-1}\nabla F_{0}}{1+\nabla F_{0}^{T}(\frac{-\gamma F_{0}}{\beta}\nabla^2F_{0})^{-1}\nabla F_{0}}\Big)\bigg\|\\ &\leq&\frac{1}{\gamma}\big\|(\nabla^2F_{0})^{-1}\big\|\bigg\|\gamma\nabla^2F_{0}(x^{0}-x^*)+\alpha\nabla F_{0} -\alpha\frac{\nabla F_{0}\nabla F_{0}^{T}(\frac{-\gamma F_{0}}{\beta}\nabla^2F_{0})^{-1}\nabla F_{0}}{1+\nabla F_{0}^{T}(\frac{-\gamma F_{0}}{\beta}\nabla^2F_{0})^{-1}\nabla F_{0}}\bigg\|\\ &\leq&\frac{1}{\gamma}\big\|(\nabla^2F_{0})^{-1}\big\|\bigg\|\gamma\nabla^2F_{0}(x^{0}-x^*)-\gamma(\nabla F_{0}-\nabla F^*)+(\alpha+\gamma)(\nabla F_{0}-\nabla F^*)\\ &&-\alpha\frac{\nabla F_{0}\nabla F_{0}^{T}(\frac{-\gamma F_{0}}{\beta}\nabla^2F_{0})^{-1}\nabla F_{0}}{1+\nabla F_{0}^{T}(\frac{-\gamma F_{0}}{\beta}\nabla^2F_{k})^{-1}\nabla F_{0}}\bigg\|\\ &\leq&\frac{1}{\gamma}\big\|(\nabla^2F_{0})^{-1}\big\|\bigg[\|\gamma\nabla^2F_{k}(x^{0}-x^*)-\gamma(\nabla F_{0}-\nabla F^*)\|+|\alpha+\gamma|\|\nabla F_{0}-\nabla F^*\|\\ &&+|\alpha|\|\nabla F_{0}\|\Big|\frac{\beta\nabla F_{0}^{T}(\gamma F_{0} \nabla^2F_{0})^{-1}\nabla F_{0}} {\beta \nabla F_{0}^{T}(\gamma F_{0} \nabla^2F_{0})^{-1}\nabla F_{0}-1}\Big|\bigg]. \end{eqnarray} $

由积分中值定理可得

(3.14) $ \begin{eqnarray} \nabla F_{0}-\nabla F^{*} = -\int^{1}_{0}\nabla^2F(x^0+\tau(x^*-x^0))(x^*-x^0){\rm d}\tau. \end{eqnarray} $

这意味着

(3.15) $ \begin{eqnarray} &&\|\nabla^2F_{0}(x^{0}-x^*)-(\nabla F_{0}-\nabla F^*)\|\\ & = &\bigg\|\int^{1}_{0}\Big(\nabla^2F_{0}-\nabla^2F\big(x^0+\tau(x^*-x^0)\big)\Big)(x^{0}-x^*){\rm d}\tau\bigg\|\\ &\leq&\int^{1}_{0}\big\|\big(\nabla^2F_{0}-\nabla^2F(x^0+\tau(x^*-x^0)\big)\big\|\|x^{0}-x^*\|{\rm d}\tau {}\\ &\leq&\frac{1}{2}L\|x^{0}-x^*\|^2. \end{eqnarray} $

若初始点$ x^{0} $靠近$ x^* $, 即$ \|x^{0}-x^*\|\rightarrow0 $, 由$ \|\nabla F_{0}\|\leq L\|x^{0}-x^*\| $, 引理3.3 (a), (3.13) 式及上面的不等式, 可得

$ \begin{eqnarray*} \|x^{1}-x^*\|&\leq&\frac{1}{\gamma}\|(\nabla^2F_{0})^{-1}\|\big(\frac{1}{2}L\|x^{0}-x^*\|^2+|\alpha+\gamma|L \|x^{0}-x^*\|+|\alpha|L\|x^{0}-x^*\|\big)\\ \nonumber &\leq&\frac{1}{\gamma}\varrho L\big(\frac{1}{2}\|x^{0}-x^*\|+|\alpha+\gamma| +|\alpha|\big)\|x^{0}-x^*\|\\ \nonumber & = &\delta\big(\frac{1}{2}\|x^{0}-x^*\|+|\alpha+\gamma| +|\alpha|\big)\|x^{0}-x^*\|\\ \nonumber &<&1, \end{eqnarray*} $

其中$ \delta = \frac{1}{\gamma}\varrho L $.

由归纳法, 可得$ \|x^{k}-x^*\|<1 $且

$ \begin{eqnarray*} \|x^{k+1}-x^*\|&\leq&\delta\big(\frac{1}{2}\|x^{k}-x^*\|+|\alpha+\gamma| +|\alpha|\big)\|x^{k}-x^*\|\\ \nonumber &\leq&\delta\big(\frac{1}{2}+|\alpha+\gamma| +|\alpha|\big)\|x^{k}-x^*\|\\ \nonumber &\leq&\big(\frac{\delta}{2}+\delta|\alpha+\gamma| +\delta|\alpha|\big)^{k+1}\|x^{0}-x^*\|\\ \nonumber & = &\xi_{1}^{k+1}\|x^{0}-x^*\|, \end{eqnarray*} $

其中$ \xi_{1}: = \frac{\delta}{2}+\delta|\alpha+\gamma|+\delta|\alpha|<1 $. 因此序列$ \{x^k\} $收敛到$ x^* $, 当$ k\rightarrow \infty $时. 证毕.

接下来, 我们将分析算法2 (MHN2) 的收敛性结果.

定理 3.2    假设迭代序列$ \{x^{k}\} $是由算法2产生. 梯度函数$ \nabla F(x) $在如下的水平集上是一致连续的

(3.16) $ \begin{eqnarray} {\mathbb L}(x_0) = \{x:x\in {{\Bbb R}} ^n \mid F(x)\leq F(x^0)\}. \end{eqnarray} $

若矩阵$ Q: = \beta\nabla F_{k}\nabla F_{k}^{T} -\gamma F_k\nabla ^2F_k $是正定的, 则$ \nabla F(x^*) = 0 $, 即$ x^* $为函数$ F(x) $的稳定点, 其中$ x^* $表示序列$ \{x^{k}\} $的聚点.

证    反证法. 假设$ x^* $为迭代序列$ \{x^{k}\} $的聚点且$ \nabla F(x^*)\neq0 $. 由于迭代序列$ \{x^{k}\} $在水平集上是有界的, 则必有收敛子列. 不是一般性仍然记为$ \{x^{k}\} $. 因此$ x^{k}\rightarrow x^* $, $ F(x^{k})\rightarrow F(x^*) $及$ F(x^{k})-F(x^{k+1})\rightarrow 0 $. 进一步, 由算法$ 2.2 $的Armijo线搜索准则可得

(3.17) $ \begin{eqnarray} -\sigma \nabla F_{k}^Ts^k< F(x^k)-F(x^{k+1})\rightarrow0, \nabla F_{k}^Ts^k\rightarrow0, \end{eqnarray} $

其中$ s^k: = \rho^{m_k}p^k $.

若$ \nabla F_{k}^T\nrightarrow0 $, 则由(3.17)式可得$ \|s^k\|\rightarrow0 $. 由于$ m_k $是使得不等式(2.5) 成立的最小正整数, 因此对于$ \rho^{m_k-1} = \frac{\rho^{m_k}}{\rho} $, 下列不等式成立

(3.18) $ \begin{eqnarray} F(x^k+\rho^{m_k-1}p^k)-F(x^{k}) >\sigma\rho^{m_k-1}\nabla F_{k}^Tp^k. \end{eqnarray} $

注意到$ \rho^{m_k-1}p^k = \frac{s^k}{\rho} $以及(3.18)式, 我们有

(3.19) $ \begin{eqnarray} F(x^k+\frac{s^k}{\rho})-F(x^{k}) >\sigma\nabla F_{k}^T(\frac{s^k}{\rho}). \end{eqnarray} $

令$ d^k = \frac{s^k}{\|s^k\|} $, 则$ \frac{s^k}{\rho} = \frac{\|s^k\|}{\rho}d^k $. 由(3.19) 式和$ \|s^k\|\rightarrow0 $, 可得

$ \alpha_{k}^{\prime}: = \frac{\|s^k\|}{\rho}\rightarrow 0 $

及

(3.20) $ \begin{equation} \frac{F(x^k+\alpha_{k}^{\prime}d^k)-F(x^{k})}{\alpha_{k}^{\prime}} >\sigma\nabla F_{k}^Td^k. \end{equation} $

注意到$ \{\|d^k\|\} $是有界的, 故存在一个收敛的子列. 不失一般性我们仍记$ \|d^{k}\| (\rightarrow \|d^*\|) $, 其中$ \|d^{*}\| = 1 $. 对(3.20) 式两边取极限可得

(3.21) $ \begin{eqnarray} \nabla F(x^*)^Td^*\geq \sigma\nabla F(x^*)^Td^*. \end{eqnarray} $

再由$ \sigma<1 $, 可得

(3.22) $ \begin{eqnarray} \nabla F(x^*)^Td^*\geq 0. \end{eqnarray} $

另一方面, 由于$ d^k = \frac{s^k}{\|s^k\|} = \frac{p^k}{\|p^k\|} $. 若$ Q: = \beta\nabla F_{k}\nabla F_{k}^{T} -\gamma F_k\nabla ^2F_k $为正定矩阵, 必有

(3.23) $ \begin{eqnarray} -\nabla F_{k}^{T}d^k& = &-\nabla F_{k}^{T}\frac{p^k}{\|p^k\|}\\ & = &\frac{(p^k)^T(\beta\nabla F_{k}\nabla F_{k}^{T}-\gamma F_k\nabla ^2F_k)^Tp^k}{F_k\|p^k\|}\\ & = &\frac{(p^k)^TQ^Tp^k}{F_k\|p^k\|}\, >\, 0. \end{eqnarray} $

若$ P $为非正定的, 由算法2.2可取适当的参数$ \tau>0 $使得$ \widehat{Q}: = \beta\nabla F_{k}\nabla F_{k}^{T} -\gamma F_k\nabla ^2F_k+\tau I $为正定的, 则

(3.24) $ \begin{eqnarray} -\nabla F_{k}^{T}d^k& = &-\nabla F_{k}^{T}\frac{p^k}{\|p^k\|}\\ & = &\frac{(p^k)^T(\beta\nabla F_{k}\nabla F_{k}^{T}-\gamma F_k\nabla ^2F_k+\tau I)^Tp^k}{F_k\|p^k\|}\\ & = &\frac{(p^k)^T(\widehat{Q})^Tp^k}{F_k\|p^k\|}\, >\, 0. \end{eqnarray} $

由(3.23) 或(3.24) 式可得

(3.25) $ \begin{equation} \nabla F(x^*)^Td^*< 0, \end{equation} $

这与(3.22) 式矛盾. 证毕.

定理 3.3    假设定理3.2条件成立. 对任意$ p\in {{\Bbb R}} ^{n}, x\in {\mathbb L}(x_0) $, 若满足以下两种情况之一

1) $ Q: = \beta\nabla F_{k}\nabla F_{k}^{T}-\gamma F_k\nabla ^2F_k $为正定的且

(3.26) $ \begin{equation} p^TQp\geq \varsigma_1 \|p\|^2; \end{equation} $

2) $ Q $非正定但$ Q+\tau I $为正定的且

(3.27) $ \begin{eqnarray} p^T(Q+\tau I)p\geq \varsigma_2 \|p\|^2. \end{eqnarray} $

则函数$ F(x) $的稳定点$ x^* $为全局极小点, 其中$ \varsigma_1, \varsigma_2, \tau>0 $.

证    由(3.26) 或(3.27) 式, 函数$ F(x) $在水平集$ {\mathbb L}(x_0) $上为一致凸的. 因此, 存在一个唯一的极小点$ x^* $. 进而$ x^* $为$ \nabla F(x) = 0 $的唯一极小值点. 因此任何的聚点$ x^* $为全局极小点, 也就是算法的迭代序列$ \{x^k\} $收敛到全局极小点$ x^* $.

注 3.1    由于当参数$ \alpha = 2 $, $ \beta = 2 $且$ \gamma = -1 $或者当参数$ \alpha = 1 $, $ \beta = 0 $且$ \gamma = -1 $, 算法退化为Hally算法或经典牛顿法, 故只要以上两种情形的参数选取并非最优, 则该算法将在适当的范围内寻找到比前两个算法更好的收敛性效果, 这一点将在数值实验部分加以说明. 另一个值得研究且具有一定挑战性的问题是算法收敛阶问题, 未来工作将进一步分析修正Hally-Newton的高阶收敛性结果.

本节给出一些数值测试例子来验证算法的有效性, 这些算例分别来自一些常用的非线性方程组测试问题. 数值测试的PC机环境为: Intel(R) Core(TM) i7-2670QM, CPU 2.20GHZ, 内存8 GB的Windows 10操作系统, 利用软件MATLAB R2017a进行测试. 为方便, 所给出两种算法的符号分别记为MHN1及MHN2. 我们通过与牛顿法(记"NM") 及Halley法(记"Halley") 在迭代步数(记"IT"), CPU时间(记"CPU") 以及目标函数值(记"Val") 等性能进行详细比较. 具体实验中, 终止准则采取如下形式

$ {\rm Val}: = \|F(x^k)\|<10^{-6} $

或者当迭代步超过最大迭代数$ k_{\max} = 100 $, 其中$ F(x^k) = \sum\limits_{i = 1}^{n} f_{i}^2(x^k) $, $ x = (x_1, x_2, \cdots, x_n)^T $, $ x^k $表示算法$ 2.1 $或算法$ 2.2 $的第$ k $步迭代点.

所有测试结果均列在表 4.1–4.5. 通过不同的初始点进行迭代得到的结果显示在表 4.1–4.3. 显然, 当我们选取参数$ \alpha = 1, \beta = 0, \gamma = -1 $算法 2.1 退化为经典的牛顿法. 同时若选取参数$ \alpha = 2, \beta = 2, \gamma = 1 $算法 2.1 退化为Halley方法.

在表 4.4中, 我们呈现了从例4到例9六个不同测试例子的不同性能, 测试函数分别记为E4–E9. 在E4中, 初始点选为$ (0.5, -2)^T $, MHN1的参数$ \alpha = 3, \beta = 3, \gamma = 1.8 $, MHN2的参数为$ \beta = 3, \gamma = 0.9 $. 在E5中, 初始点选为$ (-1, 10)^T $, MHN1的参数$ \alpha = 3, \beta = 3, \gamma = 3 $, MHN2的参数为$ \beta = 3, \gamma = 3 $. 在E6中, 初始点选为$ (2, 3, 3)^T $, MHN1的参数$ \alpha = 3, \beta = 3, \gamma = 2.9 $, MHN2的参数为$ \beta = 3, \gamma = 2.9 $. 在E7中, 初始点选为$ 10^4\cdot(-10, -2, -3, -0.2)^T $, MHN1的参数$ \alpha = 3, \beta = 3, \gamma = 2 $, MHN2的参数为$ \beta = 3, \gamma = 1.9 $. 在E8中, 初始点选为$ (10, 10, 10)^T $, MHN1的参数$ \alpha = 3, \beta = 3, \gamma = 2.9 $, MHN2的参数为$ \beta = 3, \gamma = 2.8 $. 在E9中, 初始点选为$ 5\cdot ones(n, 1) $, MHN1的参数$ \alpha = 3, \beta = 3, \gamma = 2.7 $, MHN2的参数为$ \beta = 3, \gamma = 2.9 $. 在表 4.5中, 我们发现在维数较大的情形下, 从CPU时间上看, MHN2比Halley方法的收敛速度快了许多, 同时发现牛顿法因系数矩阵出现奇异情形而失效. 表格中符号'-' 表示算法是发散的, 即无法得到近似解而失效.

从这些数据结果表明, 无论在算法的迭代次数或所消耗的CPU时间等性能上, MHN1及MHN2都优于牛顿法和Halley法. 事实上, 所提出的这两种方法在参数的选取上是更加松弛与灵活的, 故有更大的空间来改善算法的收敛效率.

例 4.1^[10]    考虑非线性方程组(1.1) 有如下具体形式

$ \begin{eqnarray*} f(x) = \left\{ \begin{array}{l} x^{3}_{1}-3x_{1}x^{2}_{2}-1 = 0, \\ 3x_{2}x^{2}_{1}-x^{3}_{2}+1 = 0.\\ \end{array} \right. \end{eqnarray*} $

其精确解$ x^* = (-0.290514555507, 1.0842150814913)^T $.

例 4.2^[4]     考虑非线性方程组(1.1) 有如下具体形式

$ \begin{eqnarray*} f(x) = \left\{ \begin{array}{ll} 3x_{1}-\cos(x_{2}x_{3})-5 = 0, \\ x^{3}_{1}-81(x_{2}+0.1)^2+\sin x_3+1.06 = 0, \\ { } {\rm e}^{-x_2x_3}+20x_3+\frac{10\pi-3}{3} = 0, \\ \end{array} \right. \end{eqnarray*} $

精确解为: $ x^* = (1.998779542323100, 0.161973550312679, -0.528065506910533)^T $.

例 4.3^[15]    考虑非线性方程组(1.1) 有如下具体形式

$ \begin{eqnarray*} f(x) = \left\{ \begin{array}{ll} (x_{1}-5x_2)^2+40\sin^2(10x_3) = 0, \\ (x_{2}-2x_3)^2+40\sin^2(10x_1) = 0, \\ (3x_{1}+x_2)^2+40\sin^2(10x_2) = 0, \\ \end{array} \right. \end{eqnarray*} $

精确解为: $ x^* = (0, 0, 0)^T $.

例 4.4^[18]    考虑非线性方程组(1.1) 有如下具体形式

$ \begin{eqnarray*} f(x) = \left\{ \begin{array}{l} -13+x_{1}+((5-x_2)x_2-2)x_2 = 0, \\ -29+x_{1}+((x_2+1)x_2-14)x_2 = 0, \\ \end{array} \right. \end{eqnarray*} $

精确解为: $ x^* = (5, 4)^T $.

例 4.5^[18]    考虑非线性方程组(1.1) 有如下具体形式

$ \begin{eqnarray*} f(x) = \left\{ \begin{array}{l} x_{1}-{\rm e}^{x_2}+1 = 0, \\ x_{1}-\cos x_2-2 = 0, \\ \end{array} \right. \end{eqnarray*} $

精确解为: $ x^* = (1.341176629595537, 0.850614425996447)^T $.

例 4.6^[5]    考虑非线性方程组(1.1) 有如下具体形式

$ \begin{eqnarray*} f(x) = \left\{ \begin{array}{l} (x_{1}-1)^4{\rm e}^{x_2} = 0, \\ (x_{2}-2)^2(x_1x_2-1) = 0, \\ (x_3+4)^6 = 0, \end{array} \right. \end{eqnarray*} $

精确解为: $ x^* = (1, 2, -4)^T $.

例 4.7^[13]    考虑非线性方程组(1.1) 有如下具体形式

$ \begin{eqnarray*} f(x) = \left\{ \begin{array}{l} 10(x_{2}-x^{2}_{1}) = 0, \\ 1-x_{1} = 0, \\ 90^{\frac{1}{2}}(x_4-x^{2}_{3}) = 0, \\ 1-x_{3} = 0, \\ 10^{\frac{1}{2}}(x_4+x_{2}-2) = 0, \\ 10^{-\frac{1}{2}}(x_2-x_{4}) = 0, \\ \end{array} \right. \end{eqnarray*} $

精确解为: $ x^* = (1, 1, 1, 1)^T $.

例 4.8^[18]    考虑非线性方程组(1.1) 有如下具体形式

$ \begin{eqnarray*} f(x) = \left\{ \begin{array}{l} x_{1}^{2}+x_{2}^{2}+x_{2}^{3}-x_3-x_{3}^{2} = 0, \\ 2x_1+x_{2}^{2}-x_3 = 0, \\ 1+x_1-x_2x_3 = 0, \end{array} \right. \end{eqnarray*} $

精确解为: $ x^* = (-0.717138270295964, -0.203233278645136, -1.393059942219910)^T $.

例 4.9^[18]    考虑非线性方程组(1.1) 有如下具体形式

$ \begin{eqnarray*} f(x) = \left\{ \begin{array}{l} x_{i}\sin(x_{i+1})-1 = 0, \\ x_{n}\sin(x_{1})-1 = 0, \\ \end{array} \right. \end{eqnarray*} $

其中$ n = 16 $, $ i = 1, 2, \cdots, 15 $. 精确解为: $ x^* = -1.114157\cdot(1, 1, \cdots, 1)^T \in {{\Bbb R}} ^{16} $.

例 4.10^[1]    考虑非线性方程组(1.1) 有如下具体形式$ f(x) = \sum\limits_{i = 1}^{n} (\exp( x_{i})-\sqrt{i}x_i), $其中$ n = 5000. $$ f(x) $是所谓的Hager函数.

本文通过引入适当的参数和搜索技术, 提出了一类求解非线性方程组的有效修正Halley-Newton算法. 同时给出这类方法的两种具体修正迭代格式. 理论和数值实验部分都充分验证了算法的可行性和有效性. 未来的工作将在最优参数的选取以及算法的收敛阶问题深入探究, 期待在算法收敛效率改善和性能提高等方面有进一步发现.