求解非线性方程含参数的八阶迭代算法

期刊菜单

求解非线性方程含参数的八阶迭代算法
An Eighth-Order Iterative Algorithm for Solving Nonlinear Equations with Parameters

DOI:10.12677/AAM.2022.1112955,PDF,HTML,XML,下载: 313浏览: 528科研立项经费支持
作者:张思平^*,黄丝引^*,曾光^#,雷莉,苏国腾：东华理工大学理学院，江西南昌
关键词:非线性方程；Steffensen迭代法；八阶收敛；Nonlinear Equations；Steffensen Iterative Method；Eighth-Order Convergence

摘要:本文基于Steffensen迭代法和King迭代法提出了求解非线性方程的一类新的含参数八阶迭代算法，该迭代算法利用中心差分思想减少了导数值的计算，提高了效率指数，并且通过收敛性分析证明了该迭代算法的收敛阶是八阶。与其他迭代法相比，收敛阶和效率指数均有提高。最后，数值实验验证了算法的有效性和优越性。

Abstract:Based on Steffensen’s iterative method and King iterative method, a new class of eighth-order itera-tive algorithms with parameters is proposed to solve nonlinear equations, which uses the central difference idea to reduce the calculation of derivative values and improve the efficiency index, and convergence analysis proves that the convergence order of such iterative algorithms is eighth. Compared with other iteration methods, the convergence order and efficiency index are improved. Finally, numerical experiments verify the effectiveness and superiority of the algorithm.

文章引用：张思平, 黄丝引, 曾光, 雷莉, 苏国腾. 求解非线性方程含参数的八阶迭代算法[J]. 应用数学进展, 2022, 11(12): 9058-9065. https://doi.org/10.12677/AAM.2022.1112955

1. 引言

科学与工程计算问题在很多情况下最终可转化为非线性方程的数值计算，例如交通轨道设计、投资优化问题、航空航天领域和高科技救援等方面 [1] - [6]。在精密仪器设计和铁路轨道设计问题中，对于计算精度的要求非常高；在信息化援救方面，尽可能缩短救援时间尤为重要。因此构造一个理想的数值算法处理非线性问题显得尤为重要。

牛顿迭代法是数值求解非线性方程的经典数值方法之一，不过牛顿迭代法由于其迭代格式中需要求解函数的导数，而实际问题中大量函数的导数求解是非常复杂的一项工作，很多计算数学家们为了避免求导运算，做了很多有意义的工作，比如Steffensen在牛顿迭代法的基础上构造了一种无导数迭代法——Steffensen型迭代法 [7]

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

King在 [8] 中提出了一类含参数的两步四阶迭代格式，其格式为

$\begin{array}{l} y_{k} = x_{k} - \frac{f (x_{k})}{f^{'} (x_{k})} \\ x_{k + 1} = y_{k} - \frac{f (x_{k}) + β f (y_{k})}{f (x_{k}) + (β - 2) f (y_{k})} \cdot \frac{f (y_{k})}{f^{'} (x_{k})} \end{array}$ (1)

其中， $β \in R$ 。

定义1 [9] 设迭代向量序列 ${x^{(k)}}$ 是以p阶收敛速度趋于 $x^{*}$ ，每次迭代所需计算的函数值次数为k，记EI为迭代格式的效率指数，其计算公式为

$E I = p^{\frac{1}{k}}$

由于King迭代法的收敛阶是4阶的，每次迭代需要计算一个导数值和两个函数值，根据定义1，该迭代格式的效率指数为 $E I = \sqrt[3]{4} = 1.5874$ 。为了改善迭代法的收敛阶和提高效率指数，本文基于Steffensen迭代法和King迭代法构造了一种新的含参数八阶迭代算法。

定义2 [9] 若 $e_{k} = x_{k} - x^{*}$ 为某迭代法的第k次迭代误差值，M是常数，则

$e_{k + 1} = M e_{k}^{p} + ο (‖ e_{k}^{p + 1} ‖),$

且该迭代法的收敛阶为p阶。

2. 八阶迭代格式的构造

首先基于迭代格式(1)，结合Newton迭代格式提出了一种新的含参数的三步Newton型迭代格式，其格式为

$\begin{array}{l} y_{k} = x_{k} - \frac{f (x_{k})}{f^{'} (x_{k})} \\ z_{k} = y_{k} - \frac{f (x_{k}) + β f (y_{k})}{f (x_{k}) + (β - 2) f (y_{k})} \cdot \frac{f (y_{k})}{f^{'} (x_{k})} \\ x_{k + 1} = z_{k} - \frac{f (z_{k})}{f^{'} (z_{k})} \end{array}$ ( $β \in R$ )(2)

在迭代格式(2)中，该格式的收敛阶是八阶，且每次迭代需要计算两个导数值和三个函数值，因此其效率指数 $E I = \sqrt[5]{8} = 1.5157$ 。该迭代格式的效率指数比经典Newton迭代格式的效率指数更高，但是低于格式(1)的效率指数。因此，为了保持高收敛阶且进一步提高迭代格式的效率指数，考虑在迭代格式(2)的基础上，拟采用一阶中心差分格式近似一阶导数，即

$f^{'} (z_{k}) \approx \frac{f (z_{k} + f (z_{k})) - f (z_{k} - f (z_{k}))}{2 f (z_{k})}$ (3)

将式(3)代入迭代格式(2)，得到一个新的含有参数的三步Steffensen迭代格式

$\begin{array}{l} y_{k} = x_{k} - \frac{f (x_{k})}{f^{'} (x_{k})} \\ z_{k} = x_{k} - \frac{f (x_{k}) + β f (y_{k})}{f (x_{k}) + (β - 2) f (y_{k})} \cdot \frac{f (y_{k})}{f^{'} (x_{k})} \\ x_{k + 1} = z_{k} - \frac{2 f^{2} (z_{k})}{f (z_{k} + f (z_{k})) - f (z_{k} - f (z_{k}))} \end{array}$ ( $β \in R$ )(4)

3. 收敛性分析

定理1. 设 $f (x) = 0$ 有一单根为a， $f (x)$ 在包含a的开区间I内充分光滑，则当 $x_{0} \in U (a)$ 时由迭代格式(4)所定义的迭代法得到的数值解在I内八阶收敛于a，且

$e_{k + 1} = \frac{A_{2}}{A_{1}} {[(2 β + 1) c_{2}^{3} - c_{2} c_{3}]}^{2} e_{k}^{8} + o (e_{k}^{9})$

其中 $e_{k} = x_{k} - a, c_{k} = \frac{f^{k} (a)}{k! f^{'} (a)}, A_{k} = \frac{1}{k!} f^{k} (a)$ 。

证明：设 $e_{k} = x_{k} - a, ξ_{k} = y_{k} - a, η_{k} = z_{k} - a$ ，则 $f (x_{k})$ 在a处进行泰勒级数展开得

$f (x_{k}) = f^{'} (a) [e_{k} + c_{2} e_{k}^{2} + c_{3} e_{k}^{3} + c_{4} e_{k}^{4} + c_{5} e_{k}^{5} + o (e_{k}^{6})]$ (5)

$f^{'} (x_{k}) = f^{'} (a) [1 + 2 c_{2} e_{k} + 3 c_{3} e_{k}^{2} + 4 c_{4} e_{k}^{3} + 5 c_{5} e_{k}^{4} + o (e_{k}^{5})]$ (6)

由式(5)和式(6)得到

$\begin{array}{l} \frac{f (x_{k})}{f^{'} (x_{k})} = e_{k} - c_{2} e_{k}^{2} - 2 (c_{3} - c_{2}^{2}) e_{k}^{3} - (3 c_{4} - 7 c_{2} c_{3} + 4 c_{2}^{3}) e_{k}^{4} \\ + (8 c_{2}^{4} - 20 c_{2}^{2} c_{3} + 6 c_{3}^{2} + 10 c_{2} c_{4} - 4 c_{5}) e_{k}^{5} + o (e_{k}^{6}) \end{array}$ (7)

$\begin{array}{l} ξ_{k} = c_{2} e_{k}^{2} + (2 c_{3} - 2 c_{2}^{2}) e_{k}^{3} + (4 c_{2}^{3} - 7 c_{2} c_{3} + 3 c_{4}) e_{k}^{4} \\ + (- 8 c_{2}^{4} + 20 c_{2}^{2} c_{3} - 6 c_{3}^{2} - 10 c_{2} c_{4} + 4 c_{5}) e_{k}^{5} + o (e_{k}^{6}) \end{array}$ (8)

则 $f (y_{k})$ 在a处进行泰勒级数展开得

$\begin{array}{l} f (y_{k}) = f^{'} (a) [ξ_{k} + c_{2} ξ_{k}^{2} + o (ξ_{k}^{3})] \\ = f^{'} (a) [c_{2} e_{k}^{2} + (2 c_{3} - 2 c_{2}^{2}) e_{k}^{3} + (3 c_{4} + 5 c_{2}^{3} - 7 c_{2} c_{3}) e_{k}^{4} \\ + (- 12 c_{2}^{4} + 24 c_{2}^{2} c_{3} - 10 c_{2} c_{4} + 4 c_{5}) e_{k}^{5} + o (e_{k}^{6})] \end{array}$ (9)

由(5)和(9)式，有

$\begin{matrix} \frac{f (x_{k}) + β f (y_{k})}{f (x_{k}) + (β - 2) f (y_{k})} = 1 + 2 \frac{B_{2}}{B_{1} + (β - 2) B_{2}} \\ = 1 + 2 c_{2} e_{k} + [4 c_{3} - 2 (β + 1) c_{2}^{2}] e_{k}^{2} \\ + 2 [(β (β + 2) c_{2}^{3} - 2 (1 + 2 β) c_{2} c_{3}) + 3 c_{4}] e_{k}^{3} + o (e_{k}^{4}) \end{matrix}$ (10)

其中，

$B_{1} = e_{k} + c_{2} e_{k}^{2} + c_{3} e_{k}^{3} + c_{4} e_{k}^{4} + o (e_{k}^{5})$ ， $B_{2} = c_{2} e_{k}^{2} + (2 c_{3} - 2 c_{2}^{2}) e_{k}^{3} + (3 c_{4} + 5 c_{2}^{3} - 7 c_{2} c_{3}) e_{k}^{4} + o (e_{k}^{5})$

根据(6)和(9)式

$\begin{array}{l} \frac{f (y_{k})}{f^{'} (x_{k})} = c_{2} e_{k}^{2} + [2 c_{3} - 4 c_{2}^{2}] e_{k}^{3} + [13 c_{2}^{3} - 14 c_{2} c_{3} + 3 c_{4}] e_{k}^{4} \\ + [- 38 c_{2}^{4} + 64 c_{2}^{2} c_{3} - 12 c_{3}^{2} - 20 c_{2} c_{4} + 4 c_{5}] e_{k}^{5} + o (e_{k}^{6}) \end{array}$ (11)

$\begin{matrix} η_{k} = ξ_{k} - \frac{f (x_{k}) + β f (y_{k})}{f (x_{k}) + (β - 2) f (y_{k})} \cdot \frac{f (y_{k})}{f^{'} (x_{k})} \\ = [(2 β + 1) c_{2}^{3} - c_{2} c_{3}] e_{k}^{4} + [- 2 (β^{2} + 6 β + 2) c_{2}^{4} \\ + 4 (3 β + 2) c_{2}^{2} c_{3} - 2 c_{2} c_{4} - 2 c_{3}^{2}] e_{k}^{5} + o (e_{k}^{6}) \end{matrix}$ (12)

将 $f (z_{k})$ 在点a进行泰勒级数展开得

$f (z_{k}) = A_{1} η_{k} + A_{2} η_{k}^{2} + A_{3} η_{k}^{3} + A_{4} η_{k}^{4} + A_{5} η_{k}^{5} + o (η_{k}^{6})$ (13)

将(13)代入 $f (z_{k} + f (z_{k}))$ 和 $f (z_{k} - f (z_{k}))$ 在 $x = a$ 处泰勒展开式中，分别为

$f (z_{k} + f (z_{k})) = A_{1} (1 + A_{1}) η_{k} + (A_{1}^{2} A_{2} + 3 A_{1} A_{2} + A_{2}) η_{k}^{2} + o (η_{k}^{3})$ (14)

$f (z_{k} - f (z_{k})) = A_{1} (1 - A_{1}) η_{k} + (A_{1}^{2} A_{2} - 3 A_{1} A_{2} + A_{2}) η_{k}^{2} + o (η_{k}^{3})$ (15)

于是

$\begin{matrix} x_{k + 1} - a = η_{k} - \frac{2 f^{2} (z_{k})}{f (z_{k} + f (z_{k})) - f (z_{k} - f (z_{k}))} \\ = \frac{A_{2}}{A_{1}} η_{k}^{2} + \frac{A_{1}^{3} A_{3} + 2 A_{1} A_{3} - 2 A_{2}^{2}}{A_{1}^{2}} η_{k}^{3} + o (η_{k}^{4}) \end{matrix}$ (16)

将(12)代入(16)中，得

$x_{k + 1} - a = \frac{A_{2}}{A_{1}} {[(2 β + 1) c_{2}^{3} - c_{2} c_{3}]}^{2} e_{k}^{8} + o (e_{k}^{9})$ (17)

$e_{k + 1} = \frac{A_{2}}{A_{1}} {[(2 β + 1) c_{2}^{3} - c_{2} c_{3}]}^{2} e_{k}^{8} + o (e_{k}^{9})$ (18)

故而证明完毕。

4. 数值实验

为验证本文所构造迭代格式的有效性和优越性，将本文所构造的迭代格式( $β = 2$ ，记为H₀)分别与以下三种迭代格式数值求解同一个非线性方程并进行对比。一是基于Jarratt迭代法的八阶迭代格式 [10] (简记为H₁)，二是四阶收敛的Steffensen型无记忆迭代格式 [11] (简记为H₂)，三是含参数的七阶收敛的Steffensen迭代格式 [12] (简记为H₃)。

三种用于对比的格式具体如下：

H₁：

${\begin{array}{l} y_{k} = x_{k} - \frac{2 f (x_{k})}{3 f^{'} (x_{k})} \\ z_{k} = x_{k} - \frac{3 f^{'} (y_{k}) + f^{'} (x_{k})}{6 f^{'} (y_{k}) - 2 f^{'} (x_{k})} \frac{f (x_{k})}{f^{'} (x_{k})} \\ x_{k + 1} = z_{k} - \frac{f (z_{k})}{f^{'} ( z k )} \end{array}$

H₂：

${\begin{cases} y_{k} = x_{k} - \frac{f (x_{k})}{f [w_{k}, x_{k}]} \\ x_{k + 1} = y_{k} - \frac{f [w_{k}, y_{k}] + f [w_{k}, y_{k}] - f [x_{k}, y_{k}]}{f {[w_{k}, y_{k}]}^{2}} f ( y k ) \end{cases}$

H₃：

${\begin{cases} y_{k} = x_{k} - \frac{2 f^{2} (x_{k})}{f (x_{k} + f (x_{k})) - f (x_{k} - f (x_{k}))} \\ z_{k} = y_{k} - \frac{f (x_{k}) f (y_{k})}{f (x_{k} + f (x_{k})) - f (x_{k} - f (x_{k}))} \frac{f (x_{k})}{f (x_{k}) - 2 f (y_{k})} \\ x_{k + 1} = z_{k} - \frac{2 f (x_{k}) f (z_{k})}{f (x_{k} + f (x_{k})) - f (x_{k} - f (x_{k}))} [{(1 + \frac{f (y_{k})}{f (x_{k}) - 2 f (y_{k})})}^{2} + \frac{f (z_{k})}{f (y_{k}) - α f (y_{k})}] \end{cases}$

注：本文涉及的数值实验均在MATLAB R2017b中进行，且设定停机准则为 $| x_{k} - x_{k - 1} | < 10^{- 15}$ 。

考虑如下非线性方程：

$f_{1} (x) = - \sin^{2} x - x^{3} + 1 = 0;$

$f_{2} (x) = (x + 2) e^{x} - 1 = 0;$

$f_{3} (x) = x e^{x^{2}} - \sin^{2} x + 3 \cos x + 5 = 0;$

$f_{4} (x) = \sqrt{x^{2} + 2 x + 5} - 2 \sin x - x^{2} + 3 = 0.$

以上非线性方程的准确解分别为

$x_{1}^{*} = 0.7908208; x_{2}^{*} = - 0.4428544; x_{3}^{*} = - 1.2076478; x_{4}^{*} = 2.331968.$

数值结果在表1~4所示， $α$ 表示迭代初值，k表示迭代次数， $ρ$ 表示近似收敛阶，具体表达式为：

$ρ = \frac{\ln (‖ x^{(k + 1)} - x^{(k)} ‖ / ‖ x^{(k)} - x^{(k - 1)} ‖)}{\ln (‖ x^{(k)} - x^{(k - 1)} ‖ / ‖ x^{(k - 1)} - x^{(k - 2)} ‖)} .$

Table 1. Calculate the number of iterations of f 1 ( x ) = 0 and the approximate convergence order

表1. 计算 $f_{1} (x) = 0$ 的迭代次数与近似收敛阶

Table 2. Calculate the number of iterations of f 2 ( x ) = 0 and the approximate convergence order

表2. 计算 $f_{2} (x) = 0$ 的迭代次数与近似收敛阶

Table 3. Calculate the number of iterations of f 3 ( x ) = 0 and the approximate convergence order

表3. 计算 $f_{3} (x) = 0$ 的迭代次数与近似收敛阶

Table 4. Calculate the number of iterations of f 4 ( x ) = 0 and the approximate convergence order

表4. 计算 $f_{4} (x) = 0$ 的迭代次数与近似收敛阶

在表1和表2中，可以观察到4种迭代格式均可用于求解方程 $f_{1} (x) = 0$ ， $f_{2} (x) = 0$ ，当取3个不同的初始值时，H₀迭代法在求解 $f_{1} (x) = 0$ ， $f_{2} (x) = 0$ 所需要的迭代次数少于其他三种迭代法，特别地当初始值 $x_{0}$ 的取值接近零点时在精度固定前提下需要的迭代次数越少，并且迭代格式的近似收敛阶非常接近理论收敛阶。

表3中，NaN表示该迭代格式在求解非线性方程时并不收敛，因此也不能通过计算得到该迭代格式的近似收敛阶。这说明迭代格式H₁中过多的求导计算影响了迭代格式的求解。同时也可以看出，当取不同的迭代初始值时，相对于其他两种迭代法，H₀迭代法都不同程度的减少了迭代次数。

在表4中，迭代格式H₁和H₃在求解该方程时均不收敛，迭代法H₀在求解该方程明显更优于迭代法H₂。在对方程 $f_{3} (x) = 0$ ， $f_{4} (x) = 0$ 的求解结果，说明本文提出的迭代法H₀的有效性比迭代格式H₁和H₃更佳，同时也比迭代法H₂收敛更快。

综上所述，我们构造的迭代格式的收敛阶和效率指数相比文中提到的H₁、H₂及H₃均有不同程度地提高，这也验证了理论的有效性和准确性。

5. 总结

本文提出了一个有效的含参数八阶收敛的方法求解非线性方程。新方法具有更快的收敛速度，并且在提高收敛速度的同时，仅增加了很小的计算成本，具有一定的优越性。数值实验表明，新算法比经典的牛顿法和其他一些改进迭代法效率更高，性能更好。此外，该方法也可以应用于线性互补问题、非线性两点边值问题和投资组合优化模型。

基金项目

江西省教育厅科学技术研究项目(GJJ200757)；江西省研究生学位与教学改革项目(JXYJG-2020-118)；东华理工大学教学改革项目(1310101210)及江西省大学生创新创业训练计划(S202210405050)。

NOTES

^*共一作者。

^#通讯作者。

参考文献

[1]	汪慧玲. 基于两机并联非线性数学模型的舰船电力系统自适应控制器设计[J]. 舰船科学技术, 2019, 41(16): 88-90.
[2]	Zhou, S.H. and Wang, C.Z. (2019) A Pneumatically-Powered Body Weight Support System: Nonlinear Mathematical Model. Proceeding of the 2019 World Congress on Computational Intelligence, Engineering and Infor-mation Technology (WCEIT 2019), Shanghai, 332-346.
[3]	Elloumi, M. and Kamoun, S. (2016) Parametric Estimation of Interconnected Nonlinear Systems Described by Input-Output Mathematical Models. International Journal of Auto-mation and Computing, 3, 364-381. https://doi.org/10.1007/s11633-016-0956-8
[4]	Zhu Zrchai, Y. (2017) Adaptive Controller Design of a Kind of Nonlinear System Based on the Improved Mathematical Model from CSTR. Proc. of the 28th China Process Control Conference (CPCC 2017) and the Summary Collection Commemorating the 30th Anniversary of China Process Control Conference, 5, 112-116.
[5]	王靖岳, 郭胜, 鄂加强. 非线性空气弹簧数学模型的研究[J]. 机械设计, 2019, 36(6): 20-23.
[6]	Adomian, G. (1989) Nonlinear Stochastic Systems Theory and Applications to Physics. Springer, Dor-drecht, 48-80.
[7]	Steffensen, J.F. (1933) Remark on Iteration. Scandinavian Actuarial Journal, 1933, 64-72. https://doi.org/10.1080/03461238.1933.10419209
[8]	King, R.F. (1973) A Family of Fourth Order Methods for Nonlinear Equations. SIAM Journal on Numerical Analysis, 10, 876-879. https://doi.org/10.1137/0710072
[9]	易达义, 沈云宝, 李有法. 计算方法[M]. 第2版. 杭州: 浙江大学出版社, 2002.
[10]	李小武. 非线性方程Newton型迭代解法与几何迭代算法[D]: [博士学位论文]. 重庆: 重庆大学, 2011.
[11]	吴江. 求解非线性方程的八阶收敛迭代法[J]. 大庆师范学院学报, 2018, 38(6): 93-95.
[12]	王晓锋, 范倩楠. 一种用于求解非线性方程组的无导数四阶迭代法[J]. 数学的实践与认识, 2021, 51(20): 203-207.

为你推荐

友情链接