Abstract
In this paper we study the convergence of a Newton-Steffensen type method for solving nonlinear equations in R, introduced by Sharma [J.R. Sharma, A composite third order Newton–Steffensen method for solving nonlinear equations, Appl. Math. Comput. 169 (2005), 242–246]. Under simplified assumptions regarding the smoothness of the nonlinear function, we show that the q-convergence order of the iterations is 3. The efficiency index of the method is \(\sqrt[3]{3}\) and is larger than \(I_2=\sqrt{2}\), which corresponds to the Newton method or the Steffensen method. Moreover, we show that if the nonlinear function maintains the same monotony and convexity on an interval containing the solution, and the initial approximation satisfies the Fourier condition, then the iterations converge monotonically to the solution. We also obtain a posteriori formulas for controlling the errors. The numerical examples confirm the theoretical results.
Authors
Keywords
Paper coordinates
I. Păvăloiu, E. Cătinaş, On a Newton-Steffensen type method, Appl. Math. Lett., 26 (2013) no. 6, pp. 659-663
doi: 10.1016/j.aml.2013.01.003
PDF-LaTeX file (freely available on the journal website).
About this paper
Print ISSN
0893-9659
Online ISSN
Google Scholar Profile
[1] M.A. Ostrowski, Solution of Equations in Euclidian and Banach Spaces Academic Press, New York and London (1973)
[2] M. Frontini, Hermite interpolation and a new iterative method for the computation of the roots of non-linear equations, Calcolo, 40 (2003), pp. 109-119 View Record in Scopus
[3] I.K. Argyros, A new convergence theorem for the Steffensen method in Banach space and applications, Rev. Anal. Numer. Theor. Approx., 29 (2) (2000), pp. 119-127
[4] S. Amat, J. Blanda, S. Busquier, A Steffensen type method with modified functions, Riv. Mat. Univ. Parma, 7 (2007), pp. 125-133
[5] E. Cătinaș E., On some Steffensen-type iterative methods for a class of nonlinear equations, Rev. Anal. Numer. Theor. Approx., 24 (1-2) (1995), pp. 37-43
[6] A. Cordero, J.R. Torregrosa, A class of Steffensen type methods with optimal order of convergence, Appl. Math. Comput., 217 (2011), pp. 7653-7659
[7] Hongmin Ren, Qingbiao Wu, Weihong Bi, A class of two-step Steffensen type methods with fourth-order convergence, Appl. Math. Comput., 209 (2009), pp. 206-210
[8] P. Jain, Steffensen type method for solving non-linear equations, Appl. Math. Comput., 194 (2007), pp. 527-533
[9] I. Păvăloiu I., Approximation of the root of equations by Aitken–Steffensen-type monotonic sequences, Calcolo, 32 (1995), pp. 69-82
[10] I. Păvăloiu, E. Cătinaș, On a Steffensen type method, Proceedings of SYNASC 2007, 9th International Symposium on Symbolic and Numeric Algoritms for Scientific Computing, Timișoara, Romania, September 26-29, IEEE Computer Society (2007), pp. 369-375
[11] J.R. Sharma, A composite third order Newton–Steffensen method for solving nonlinear equations, Appl. Math. Comput., 169 (2005), pp. 242-246, https://doi.org/10.1016/j.amc.2004.10.040
[12] Quan Zheng, Peng Zhao, Li Zhang, Wenchao Ma, Variants of Steffensen-secant method and applications, Appl. Math. Comput., 216 (12) (2010), pp. 3486-3496
[13] J.F. Traub, Iterative Method for Solution of Equations Prentice-Hall, Englewood Cliffs, New Jersey (1964)
[14] Shaohua Yu, Xiubin Xu, Jianqiu Li, Younghui Ling, Convergence behavior for Newton-Steffensen’s method under Lipschitz condition of second derivative Taiwanese, J. Math., 15 (6) (2011), pp. 2577-2600
Paper (preprint) in HTML form
On a Newton-Steffensen type method
Abstract
In this paper we study the convergence of a Newton-Steffensen type method for solving nonlinear equations in , introduced by Sharma [J.R. Sharma, A composite third order Newton-Steffensen method for solving nonlinear equations, Appl. Math. Comput. 169 (2005), 242–246].
Under simplified assumptions regarding the smoothness of the nonlinear function, we show that the q-convergence order of the iterations is 3. The efficiency index of the method is and is larger than which corresponds to the Newton method or the Steffensen method.
Moreover, we show that if the nonlinear function maintains the same monotony and convexity on an interval containing the solution, and the initial approximation satisfies the Fourier condition, then the iterations converge monotonically to the solution.
We also obtain a posteriori formulas for controlling the errors.
The numerical examples confirm the theoretical results.
keywords:
Nonlinear equations , Newton method , Steffensen method , convergence order.MSC:
65H051 Introduction
Consider the equation
| (1) |
and another equivalent equation:
| (2) |
The Steffensen type methods are interpolatory methods (see, e.g., [8], [5]), with the nodes controlled at each step by the auxiliary function [1]–[4], [6]–[7], [9]–[11], [14]. The method generates a sequence which approximates a solution of (1):
| (3) |
In the papers [9], [10] is studied the convergence of the Steffensen method when is given by
The parameter is determined such that the sequences and approximate bilaterally the solution, and the convergence order of these methods is 2.
In [11] Sharma introduces a Steffensen type method of order three, with given by
| (4) |
which we shall call as the Newton-Steffensen (N-S) method. Since it requires 3 function evaluations at each iteration step, its efficiency index is and is larger than which corresponds to the Newton method or the Steffensen method (see, e.g., [9], [8], [12]), and therefore the method is worth to be considered.
In this paper we shall show in Section 2 that the convergence order 3 can be obtained under some weaker smoothness assumptions on than in [11] and [13]. Moreover, in Section 3 we shall study the convergence of the (N-S) method in hypotheses regarding the monotony and convexity of on . Under some simple assumptions on , including the Fourier conditions, we shall show that the (N-S) method leads to monotonic sequences which approximate the solution. In Section 4 we illustrate the theory by some numerical examples, which confirm the theoretical results.
2 Local convergence of the method
Consider the following hypotheses:
equation (1) has a solution
on
Sharma proved the following result.
Theorem 1
[11]If satisfies – and moreover, there exists then the (N-S) method has the q-convergence order at least 3, with the asymptotic constant given by relation:
| (5) |
Of course that the fact that the sequence is well defined must be implicitly assumed.
We show that the requirement that is three times differentiable can be dropped.
In [13], the authors studied the semilocal and local convergence of the (N-S) iterates in the setting of Banach spaces. Local convergence with order 3 was established under the assumption of Lipschitz continuity of . We show here that even the Lipschitz continuity may be relaxed, and we consider the following assumption:
and , which is continuous at .
Theorem 2
If satisfies , the (N-S) method is well defined and converges to then the method has the q-convergence order at least 3, with the same asymptotic constant given in (5).
By and the Taylor formula we obtain
| (7) |
where belongs to the open interval determined by and
3 Monotone convergence of the method
As it is well known, when preserves its monotonicity and convexity on , if the initial approximation verifies the Fourier condition, then the Newton method yields a monotone sequence which converges to the solution We shall show that under same such hypotheses, we obtain the same conclusions, but for a method with superior efficiency index.
We assume that the initial approximation verifies the Fourier condition (see [8]):
We obtain the following results.
Theorem 3
If and verify and, moreover,
- i
-
- ii
-
then the elements of and generated by the (N-S) method remain in , converge to and obey
| (10) |
Proof. From and it follows that is a unique solution. Conditions and imply that Let such that From we get that and Conditions and (8) imply
Using the mean value formulas for divided differences and taking into account and (6), it follows that
It is obvious that the elements of and belong to It remains to show the convergence to the solution. Indeed, if then by (10) whence i.e.,
Proof. The result can be obtained as a consequence of Theorem 3, if instead of (1) we consider the equation with .
Theorem 5
If and verify and, moreover
- i
-
- ii
-
then the elements of and generated by the (N-S) method remain in , converge to and obey
| (12) |
Proof. Hypotheses and ensure that is a unique solution. Assumptions and lead to or Let for some By we get and By (8), and it follows Relation (3) implies and by (6) we get By (11) we get
Proof. This result can be obtained from Theorem 5 by taking instead of
Remark 1
4 Numerical examples
We consider four numerical examples, and we compute the iterations using double precision in Matlab.
Example 1
Consider the equation
One can verify that for all Also, for all Therefore the assumptions of Theorem 3 apply for .
We have
The obtained numerical results are shown in Table 1. The values of are rounded to two decimals, since we are interested only in the magnitude of these values.
| 0 | 1.000000000000000e+0 | 4.320688774181047e-1 | 4.5e+00 |
| 1 | 2.300692760447372e-1 | 1.070409169425782e-1 | 4.2e-01 |
| 2 | 9.915547164564892e-2 | 9.860719010016147e-2 | 1.6e-03 |
| 3 | 9.860703883247032e-2 | 9.860703879072202e-2 | 1.3e-10 |
| 4 | 9.860703879072187e-2 | 9.860703879072202e-2 | -4.4e-16 |
It can be seen that the (N-S) method generates decreasing iterates for .
Example 2
Consider the following equation
We have: which imply that
If , the assumptions of Theorem 4 are verified.
We obtain the results presented in Table 2. As expected, the (N-S) iterates are decreasing.
| 0 | 1.000000000000000e+0 | 7.246446975670946e-1 | -1.2e+00 |
| 1 | 6.607648584752154e-1 | 6.395167806664399e-1 | -5.3e-02 |
| 2 | 6.391602133769920e-1 | 6.391540963613613e-1 | -1.5e-05 |
| 3 | 6.391540963320078e-1 | 6.391540963320076e-1 | -6.7e-16 |
Example 3
Consider
We have while
Taking hypothesis of Theorem 5 apply.
The obtained results are presented in Table 3. The (N-S) iterates are increasing.
| 0 | 0.000000000000000e+0 | 6.666666666666666e-1 | -2.0e+00 |
| 1 | 6.831640060745233e-1 | 6.840365700507293e-1 | -2.4e-03 |
| 2 | 6.840366566692261e-1 | 6.840366566778295e-1 | -2.4e-11 |
| 3 | 6.840366566778295e-1 | 6.840366566778295e-1 | 0.0e+00 |
Example 4
Consider
We have while
Taking hypothesis of Theorem 6 apply.
The obtained results are presented in Table 4. The (N-S) iterates are increasing.
| 0 | 1.000000000000000e+0 | 1.524633113581329e+0 | 1.1e+00 |
| 1 | 1.593748766088184e+0 | 1.603527625548530e+0 | 1.6e-02 |
| 2 | 1.603545706091483e+0 | 1.603545739535836e+0 | 5.4e-08 |
| 3 | 1.603545739535836e+0 | 1.603545739535836e+0 | -2.2e-16 |
It is interesting to note that we get in Example 3, which suggests that . However, if instead of the standard double precision we use higher precision (e.g., variable precision arithmetic) for representing from Table 3, the computation of no longer yields (of course, we obtain values with the magnitude comparable to the machine epsilon from double precision, e). This means that from Table 3 is just a very good approximation (in double precision arithmetic) to the solution.
Acknowledgement. We are grateful to an anonymous referee for his constructive remarks in improving the presentation of our paper.
References
- [1] I.K. Argyros, A new convergence theorem for the Steffensen method in Banach space and applications, Rev. Anal. Numér. Théor. Approx., 29 (2000) 2 , 119–127.
- [2] S. Amat, J. Blanda and S. Busquier, A Steffensen type method with modified functions, Rev. Math. Univ. Parma 7 (2007) 125–133.
- [3] E. Cătinaş, On some Steffensen-type iterative methods for a class of nonlinear equations, Rev. Anal. Numér. Théor. Approx., 24 (1995) nos. 1-2, pp. 37–43.
- [4] A. Cordero, J.R. Torregrosa, A class of Steffensen type methods with optimal order of convergence, Appl. Math. Comput. 217 (2011), 7653–7659.
- [5] M. Frontini, Hermite interpolation and a new iterative method for the computation of the roots of non-linear equations, Calcolo, 40 (2003), 109–119.
- [6] Hongmin Ren, Qingbiao Wu, Weihong Bi, A class of two-step Steffensen type methods with fourth-order convergence, Appl. Math. Comput. 209 (2009), 206–210.
- [7] P. Jain, Steffensen type method for solving non-linear equations, Appl. Math. Comput. 194 (2007), 527–533.
- [8] M. A. Ostrowski, Solution of Equations in Euclidian and Banach Spaces, Academic Press, New York and London, 1973.
- [9] I. Păvăloiu, Approximation of the root of equations by Aitken-Steffensen-type monotonic sequences, Calcolo 32 (1995), 69–82.
- [10] I. Păvăloiu and E. Cătinas, On a Steffensen type method, IEEE Computer Society, Proceedings of SYNASC 2007, 9th International Symposium on Symbolic and Numeric Algoritms for Scientific Computing, Timişoara, Romania, September 26–29, 2007, pp. 369–375.
- [11] J. R. Sharma, A composite third order Newton-Steffensen method for solving nonlinear equations, Appl. Math. Comput. 169 (2005), 242–246.
- [12] J. F. Traub, Iterative Method for Solution of Equations, Prentice-Hall Englewood Cliffs, New Jersey, 1964.
- [13] Shaohua Yu, Xiubin Xu, Jianqiu Li and Younghui Ling, Convergence behavior for Newton-Steffensen’s method under Lipschitz condition of second derivative, Taiwanese J. Math., 15 (2011) no. 6, 2577–2600.
- [14] Quan Zheng, Peng Zhao, Li Zhang, Wenchao Ma, Variants of Steffensen-secant method and applications, Appl. Math. Comput. 216 (2010) 12, 3486–3496.