
-
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.
|
[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.
|
[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.
|
[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. |
[8] |
A. Djamel, N. Amel and O. Mohand, A piecewise quadratic underestimation for global optimization, in The Abstract Book, (2013), 138. |
[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. |
[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.
|
[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.
|
[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.
|
[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. |
[8] |
A. Djamel, N. Amel and O. Mohand, A piecewise quadratic underestimation for global optimization, in The Abstract Book, (2013), 138. |
[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. |
[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, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2087-2102. doi: 10.3934/jimo.2019044 |
[2] |
Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial and Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647 |
[3] |
Z.Y. Wu, H.W.J. Lee, F.S. Bai, L.S. Zhang. Quadratic smoothing approximation to $l_1$ exact penalty function in global optimization. Journal of Industrial and Management Optimization, 2005, 1 (4) : 533-547. doi: 10.3934/jimo.2005.1.533 |
[4] |
Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177 |
[5] |
Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial and Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499 |
[6] |
Yulin Zhao. On the monotonicity of the period function of a quadratic system. Discrete and Continuous Dynamical Systems, 2005, 13 (3) : 795-810. doi: 10.3934/dcds.2005.13.795 |
[7] |
Michal Málek, Peter Raith. Stability of the distribution function for piecewise monotonic maps on the interval. Discrete and Continuous Dynamical Systems, 2018, 38 (5) : 2527-2539. doi: 10.3934/dcds.2018105 |
[8] |
Magnus Aspenberg, Viviane Baladi, Juho Leppänen, Tomas Persson. On the fractional susceptibility function of piecewise expanding maps. Discrete and Continuous Dynamical Systems, 2022, 42 (2) : 679-706. doi: 10.3934/dcds.2021133 |
[9] |
Yilei Tang. Global dynamics and bifurcation of planar piecewise smooth quadratic quasi-homogeneous differential systems. Discrete and Continuous Dynamical Systems, 2018, 38 (4) : 2029-2046. doi: 10.3934/dcds.2018082 |
[10] |
Yves Edel, Alexander Pott. A new almost perfect nonlinear function which is not quadratic. Advances in Mathematics of Communications, 2009, 3 (1) : 59-81. doi: 10.3934/amc.2009.3.59 |
[11] |
Eunice Mureithi. Effects of buoyancy on the lower branch modes on a Blasius boundary layer. Discrete and Continuous Dynamical Systems - B, 2007, 8 (3) : 613-622. doi: 10.3934/dcdsb.2007.8.613 |
[12] |
Anass Belcaid, Mohammed Douimi, Abdelkader Fassi Fihri. Recursive reconstruction of piecewise constant signals by minimization of an energy function. Inverse Problems and Imaging, 2018, 12 (4) : 903-920. doi: 10.3934/ipi.2018038 |
[13] |
Ábel Garab. Unique periodic orbits of a delay differential equation with piecewise linear feedback function. Discrete and Continuous Dynamical Systems, 2013, 33 (6) : 2369-2387. doi: 10.3934/dcds.2013.33.2369 |
[14] |
Zhichuan Zhu, Bo Yu, Li Yang. Globally convergent homotopy method for designing piecewise linear deterministic contractual function. Journal of Industrial and Management Optimization, 2014, 10 (3) : 717-741. doi: 10.3934/jimo.2014.10.717 |
[15] |
Jaume Llibre, Yilei Tang. Limit cycles of discontinuous piecewise quadratic and cubic polynomial perturbations of a linear center. Discrete and Continuous Dynamical Systems - B, 2019, 24 (4) : 1769-1784. doi: 10.3934/dcdsb.2018236 |
[16] |
Zongming Guo, Xuefei Bai. On the global branch of positive radial solutions of an elliptic problem with singular nonlinearity. Communications on Pure and Applied Analysis, 2008, 7 (5) : 1091-1107. doi: 10.3934/cpaa.2008.7.1091 |
[17] |
Laurent Imbert, Michael J. Jacobson, Jr., Arthur Schmidt. Fast ideal cubing in imaginary quadratic number and function fields. Advances in Mathematics of Communications, 2010, 4 (2) : 237-260. doi: 10.3934/amc.2010.4.237 |
[18] |
Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104 |
[19] |
Prof. Dr.rer.nat Widodo. Topological entropy of shift function on the sequences space induced by expanding piecewise linear transformations. Discrete and Continuous Dynamical Systems, 2002, 8 (1) : 191-208. doi: 10.3934/dcds.2002.8.191 |
[20] |
Hang Zheng, Yonghui Xia. Chaotic threshold of a class of hybrid piecewise-smooth system by an impulsive effect via Melnikov-type function. Discrete and Continuous Dynamical Systems - B, 2022 doi: 10.3934/dcdsb.2021319 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]