
-
Previous Article
Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C
- NACO Home
- This Issue
-
Next Article
On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization
Piecewise quadratic bounding functions for finding real roots of polynomials
1. | Department of the Common Base Natural and Life Sciences, Batna 2 University, Algeria |
2. | Faculty of Mathematics and Computer Science, Batna 2 University, Algeria |
3. | Department of Mathematics, Faculty of Science and Arts, Kirklareli University, 39100, Kirklareli, Turkey |
In this paper, our main interest is to create/ construct a new useful and outstanding algorithm to obtain roots of the real polynomial represented by $ f(x) = c_{0}+c_{1}x+...+c_{i}x^{i}+...+c_{n}x^{n} $ where coefficients of the polynomials are real numbers and $ x $ is a real number in the closed interval of $ \mathbb{R} $. Also, our results are supported by numerical examples. Then, a new algorithm is compared with the others (writer classical methods) and this algorithm is more useful than others.
References:
[1] |
D. Aaid, A. Noui and M. Ouanes, New technique for solving univariate global optimization, Archivum Mathematicum, 53 (2017), 19-33. Google Scholar |
[2] |
C. S. Adjiman, I. P. Androulakis and C. A. Floudas, A global optimization method, $\alpha$bb, for general twice-differentiable constrained nlpsii. implementation and computational results, Computers & Chemical Engineering, 22 (1998), 1159-1179. Google Scholar |
[3] |
X.-D. Chen and W. Ma, A planar quadratic clipping method for computing a root of a polynomial in an interval, Computers & Graphics, 46 (2015), 89-98. Google Scholar |
[4] |
X.-D. Chen and W. Ma,
Rational cubic clipping with linear complexity for computing roots of polynomials, Applied Mathematics and Computation, 273 (2016), 1051-1058.
doi: 10.1016/j.amc.2015.10.054. |
[5] |
X.-D. Chen, W. Ma and Y. Ye,
A rational cubic clipping method for computing real roots of a polynomial, Computer Aided Geometric Design, 38 (2015), 40-50.
doi: 10.1016/j.cagd.2015.08.002. |
[6] |
C. De Boor, Applied mathematical sciences, in A Practical Guide To Splines, Vol. 27, (1978), Spriger-Verlag. |
[7] |
A. Djamel, N. Amel, Z. Ahmed, O. Mohand and L. T. H. An, A quadratic branch and bound with alienor method for global optimization, in XII Global Optimization Workshop, (2014), 41–44. Google Scholar |
[8] |
A. Djamel, N. Amel and O. Mohand, A piecewise quadratic underestimation for global optimization, in The Abstract Book, (2013), 138. Google Scholar |
[9] |
P. Jiang, X. Wu and Z. Liu,
Polynomials root-finding using a slefe-based clipping method, Communications in Mathematics and Statistics, 4 (2016), 311-322.
doi: 10.1007/s40304-016-0086-1. |
[10] |
H. A. Le Thi and M. Ouanes,
Convex quadratic underestimation and branch and bound for univariate global optimization with one nonconvex constraint, Rairo-Operations Research, 40 (2006), 285-302.
doi: 10.1051/ro:2006024. |
[11] |
H. A. Le Thi, M. Ouanes and A. Zidna, An adapted branch and bound algorithm for approximating real root of a ploynomial, in International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences, Springer, (2008), 182–189. Google Scholar |
[12] |
H. A. Le Thi, M. Ouanes and A. Zidna, Computing real zeros of a polynomial by branch and bound and branch and reduce algorithms, Yugoslav Journal of Operations Research, 24.
doi: 10.2298/YJOR120620004L. |
[13] |
M. Ouanes, H. A. Le Thi, T. P. Nguyen and A. Zidna,
New quadratic lower bound for multivariate functions in global optimization, Mathematics and Computers in Simulation, 109 (2015), 197-211.
doi: 10.1016/j.matcom.2014.04.013. |
[14] |
A. Shpak,
Global optimization in one-dimensional case using analytically defined derivatives of objective function, The Computer Science Journal of Moldova, 3 (1995), 168-184.
|
show all references
References:
[1] |
D. Aaid, A. Noui and M. Ouanes, New technique for solving univariate global optimization, Archivum Mathematicum, 53 (2017), 19-33. Google Scholar |
[2] |
C. S. Adjiman, I. P. Androulakis and C. A. Floudas, A global optimization method, $\alpha$bb, for general twice-differentiable constrained nlpsii. implementation and computational results, Computers & Chemical Engineering, 22 (1998), 1159-1179. Google Scholar |
[3] |
X.-D. Chen and W. Ma, A planar quadratic clipping method for computing a root of a polynomial in an interval, Computers & Graphics, 46 (2015), 89-98. Google Scholar |
[4] |
X.-D. Chen and W. Ma,
Rational cubic clipping with linear complexity for computing roots of polynomials, Applied Mathematics and Computation, 273 (2016), 1051-1058.
doi: 10.1016/j.amc.2015.10.054. |
[5] |
X.-D. Chen, W. Ma and Y. Ye,
A rational cubic clipping method for computing real roots of a polynomial, Computer Aided Geometric Design, 38 (2015), 40-50.
doi: 10.1016/j.cagd.2015.08.002. |
[6] |
C. De Boor, Applied mathematical sciences, in A Practical Guide To Splines, Vol. 27, (1978), Spriger-Verlag. |
[7] |
A. Djamel, N. Amel, Z. Ahmed, O. Mohand and L. T. H. An, A quadratic branch and bound with alienor method for global optimization, in XII Global Optimization Workshop, (2014), 41–44. Google Scholar |
[8] |
A. Djamel, N. Amel and O. Mohand, A piecewise quadratic underestimation for global optimization, in The Abstract Book, (2013), 138. Google Scholar |
[9] |
P. Jiang, X. Wu and Z. Liu,
Polynomials root-finding using a slefe-based clipping method, Communications in Mathematics and Statistics, 4 (2016), 311-322.
doi: 10.1007/s40304-016-0086-1. |
[10] |
H. A. Le Thi and M. Ouanes,
Convex quadratic underestimation and branch and bound for univariate global optimization with one nonconvex constraint, Rairo-Operations Research, 40 (2006), 285-302.
doi: 10.1051/ro:2006024. |
[11] |
H. A. Le Thi, M. Ouanes and A. Zidna, An adapted branch and bound algorithm for approximating real root of a ploynomial, in International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences, Springer, (2008), 182–189. Google Scholar |
[12] |
H. A. Le Thi, M. Ouanes and A. Zidna, Computing real zeros of a polynomial by branch and bound and branch and reduce algorithms, Yugoslav Journal of Operations Research, 24.
doi: 10.2298/YJOR120620004L. |
[13] |
M. Ouanes, H. A. Le Thi, T. P. Nguyen and A. Zidna,
New quadratic lower bound for multivariate functions in global optimization, Mathematics and Computers in Simulation, 109 (2015), 197-211.
doi: 10.1016/j.matcom.2014.04.013. |
[14] |
A. Shpak,
Global optimization in one-dimensional case using analytically defined derivatives of objective function, The Computer Science Journal of Moldova, 3 (1995), 168-184.
|


Zeros of polynom | Zeros found with BR | Zeros found with BB | Zeros found with BBR |
0.100000000 | 0.100000000 | 0.100000000 | 0.100000000 |
0.200000000 | 0.199999999 | 0.199999999 | 0.199999999 |
0.300000000 | 0.300000000 | 0.299999999 | 0.300000000 |
0.400000000 | 0.400000000 | 0.400000000 | 0.400000000 |
0.500000000 | 0.500000000 | 0.500000000 | 0.500000000 |
0.600000000 | 0.600000000 | 0.600000000 | 0.600000000 |
0.700000000 | 0.700000000 | 0.700000000 | 0.700000000 |
0.800000000 | 0.800000000 | 0.800000000 | 0.800000000 |
0.900000000 | 0.899999999 | 0.899999999 | 0.900000000 |
Relative Error | 0.000000002 | 0.000000003 | 0.000000001 |
number of iterations | 25 | 22 | 06 |
Time (second) | 0.082000000 | 0.010000000 | 0.000000000 |
Zeros of polynom | Zeros found with BR | Zeros found with BB | Zeros found with BBR |
0.100000000 | 0.100000000 | 0.100000000 | 0.100000000 |
0.200000000 | 0.199999999 | 0.199999999 | 0.199999999 |
0.300000000 | 0.300000000 | 0.299999999 | 0.300000000 |
0.400000000 | 0.400000000 | 0.400000000 | 0.400000000 |
0.500000000 | 0.500000000 | 0.500000000 | 0.500000000 |
0.600000000 | 0.600000000 | 0.600000000 | 0.600000000 |
0.700000000 | 0.700000000 | 0.700000000 | 0.700000000 |
0.800000000 | 0.800000000 | 0.800000000 | 0.800000000 |
0.900000000 | 0.899999999 | 0.899999999 | 0.900000000 |
Relative Error | 0.000000002 | 0.000000003 | 0.000000001 |
number of iterations | 25 | 22 | 06 |
Time (second) | 0.082000000 | 0.010000000 | 0.000000000 |
Zeros of polynom | Zeros found with BR | Zeros found with BB | Zeros found with BBR |
0.020600000 | 0.020599999 | 0.020600000 | 0.020600000 |
0.056600000 | 0.056600000 | 0.056600000 | 0.056600000 |
0.079900000 | 0.079900000 | 0.079899999 | 0.079899999 |
0.210000000 | 0.210000000 | 0.209999999 | 0.210000000 |
0.397300000 | 0.397300000 | 0.397299999 | 0.397300000 |
0.446600000 | 0.446599999 | 0.446600000 | 0.446599999 |
0.577600000 | 0.577600000 | 0.577599999 | 0.577600000 |
0.955100000 | 0.955100000 | 0.955099999 | 0.955100000 |
0.979100000 | 0.979100000 | 0.979099999 | 0.979100000 |
0.983500000 | 0.983499999 | 0.983500000 | 0.983500000 |
Relative Error | 0.000000003 | 0.000000006 | 0.000000002 |
number of iterations | 27 | 32 | 12 |
Time (second) | 0.076100000 | 0.052000000 | 0.016000000 |
Zeros of polynom | Zeros found with BR | Zeros found with BB | Zeros found with BBR |
0.020600000 | 0.020599999 | 0.020600000 | 0.020600000 |
0.056600000 | 0.056600000 | 0.056600000 | 0.056600000 |
0.079900000 | 0.079900000 | 0.079899999 | 0.079899999 |
0.210000000 | 0.210000000 | 0.209999999 | 0.210000000 |
0.397300000 | 0.397300000 | 0.397299999 | 0.397300000 |
0.446600000 | 0.446599999 | 0.446600000 | 0.446599999 |
0.577600000 | 0.577600000 | 0.577599999 | 0.577600000 |
0.955100000 | 0.955100000 | 0.955099999 | 0.955100000 |
0.979100000 | 0.979100000 | 0.979099999 | 0.979100000 |
0.983500000 | 0.983499999 | 0.983500000 | 0.983500000 |
Relative Error | 0.000000003 | 0.000000006 | 0.000000002 |
number of iterations | 27 | 32 | 12 |
Time (second) | 0.076100000 | 0.052000000 | 0.016000000 |
Zeros of polynom | Zeros found with BR | Zeros found with BB | Zeros found with BBR |
0.500000000 | 0.499999999 | 0.500000000 | 0.500000000 |
0.250000000 | 0.249999999 | 0.249999999 | 0.250000000 |
0.125000000 | 0.124999999 | 0.125000000 | 0.124999999 |
0.062500000 | 0.062500000 | 0.062499999 | 0.062500000 |
0.031250000 | 0.031249999 | 0.031250000 | 0.031249999 |
0.015625000 | 0.015625000 | 0.015624999 | 0.015624999 |
0.007812500 | 0.007812500 | 0.007812500 | 0.007812500 |
0.003906250 | 0.003906250 | 0.003906250 | 0.003906250 |
Relative Error | 0.000000004 | 0.000000003 | 0.000000003 |
number of iterations | 36 | 27 | 11 |
Time (second) | 0.096200000 | 0.027300000 | 0.036100000 |
Zeros of polynom | Zeros found with BR | Zeros found with BB | Zeros found with BBR |
0.500000000 | 0.499999999 | 0.500000000 | 0.500000000 |
0.250000000 | 0.249999999 | 0.249999999 | 0.250000000 |
0.125000000 | 0.124999999 | 0.125000000 | 0.124999999 |
0.062500000 | 0.062500000 | 0.062499999 | 0.062500000 |
0.031250000 | 0.031249999 | 0.031250000 | 0.031249999 |
0.015625000 | 0.015625000 | 0.015624999 | 0.015624999 |
0.007812500 | 0.007812500 | 0.007812500 | 0.007812500 |
0.003906250 | 0.003906250 | 0.003906250 | 0.003906250 |
Relative Error | 0.000000004 | 0.000000003 | 0.000000003 |
number of iterations | 36 | 27 | 11 |
Time (second) | 0.096200000 | 0.027300000 | 0.036100000 |
Zeros of polynom | Zeros found with BR | Zeros found with BB | Zeros found with BBR |
0.137793470 | 0.137793487 | 0.137793487 | 0.137793486 |
0.729454549 | 0.729454566 | 0.729454566 | 0.729454565 |
1.808342901 | 1.808342880 | 1.808342880 | 1.808342881 |
3.401433697 | 3.401433705 | 3.401433705 | 3.401433705 |
5.552496140 | 5.552496161 | 5.552496160 | 5.552496160 |
8.330152746 | 8.330152734 | 8.330152735 | 8.330152735 |
11.843785837 | 11.843785821 | 11.843785821 | 11.843785821 |
16.279257831 | 16.279257837 | 16.279257837 | 16.279257837 |
21.996585811 | 21.996585793 | 21.996585792 | 21.996585792 |
29.920697012 | 29.920697000 | 29.920697001 | 29.920697002 |
Relative Error | 0.000000001 | 0.000000001 | 0.000000001 |
number of iterations | 23 | 13 | 07 |
Time (second) | 0.001200000 | 0.020000000 | 0.000000000 |
Zeros of polynom | Zeros found with BR | Zeros found with BB | Zeros found with BBR |
0.137793470 | 0.137793487 | 0.137793487 | 0.137793486 |
0.729454549 | 0.729454566 | 0.729454566 | 0.729454565 |
1.808342901 | 1.808342880 | 1.808342880 | 1.808342881 |
3.401433697 | 3.401433705 | 3.401433705 | 3.401433705 |
5.552496140 | 5.552496161 | 5.552496160 | 5.552496160 |
8.330152746 | 8.330152734 | 8.330152735 | 8.330152735 |
11.843785837 | 11.843785821 | 11.843785821 | 11.843785821 |
16.279257831 | 16.279257837 | 16.279257837 | 16.279257837 |
21.996585811 | 21.996585793 | 21.996585792 | 21.996585792 |
29.920697012 | 29.920697000 | 29.920697001 | 29.920697002 |
Relative Error | 0.000000001 | 0.000000001 | 0.000000001 |
number of iterations | 23 | 13 | 07 |
Time (second) | 0.001200000 | 0.020000000 | 0.000000000 |
[1] |
Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104 |
[2] |
Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117 |
[3] |
Bing Yu, Lei Zhang. Global optimization-based dimer method for finding saddle points. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 741-753. doi: 10.3934/dcdsb.2020139 |
[4] |
Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 |
[5] |
Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020374 |
[6] |
Rim Bourguiba, Rosana Rodríguez-López. Existence results for fractional differential equations in presence of upper and lower solutions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1723-1747. doi: 10.3934/dcdsb.2020180 |
[7] |
Alessandro Fonda, Rodica Toader. A dynamical approach to lower and upper solutions for planar systems "To the memory of Massimo Tarallo". Discrete & Continuous Dynamical Systems - A, 2021 doi: 10.3934/dcds.2021012 |
[8] |
Mark F. Demers. Uniqueness and exponential mixing for the measure of maximal entropy for piecewise hyperbolic maps. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 217-256. doi: 10.3934/dcds.2020217 |
[9] |
Meilan Cai, Maoan Han. Limit cycle bifurcations in a class of piecewise smooth cubic systems with multiple parameters. Communications on Pure & Applied Analysis, 2021, 20 (1) : 55-75. doi: 10.3934/cpaa.2020257 |
[10] |
Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296 |
[11] |
Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067 |
[12] |
Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020169 |
[13] |
Wei-Chieh Chen, Bogdan Kazmierczak. Traveling waves in quadratic autocatalytic systems with complexing agent. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020364 |
[14] |
Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, 2021, 20 (1) : 339-358. doi: 10.3934/cpaa.2020269 |
[15] |
Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020443 |
[16] |
Huanhuan Tian, Maoan Han. Limit cycle bifurcations of piecewise smooth near-Hamiltonian systems with a switching curve. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020368 |
[17] |
Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070 |
[18] |
Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems - A, 2021 doi: 10.3934/dcds.2021011 |
[19] |
Madhurima Mukhopadhyay, Palash Sarkar, Shashank Singh, Emmanuel Thomé. New discrete logarithm computation for the medium prime case using the function field sieve. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020119 |
[20] |
Kateřina Škardová, Tomáš Oberhuber, Jaroslav Tintěra, Radomír Chabiniok. Signed-distance function based non-rigid registration of image series with varying image intensity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1145-1160. doi: 10.3934/dcdss.2020386 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]