Piecewise quadratic bounding functions for finding real roots of polynomials

Djamel Aaid; Amel Noui; Özen Özer

doi:10.3934/naco.2020015

Article Contents

2021, Volume 11, Issue 1: 63-73. Doi: 10.3934/naco.2020015

This issue Previous Article On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization Next Article Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C

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

^* Corresponding author: Djamel Aaid
^* Corresponding author: Djamel Aaid

Received: May 31, 2019

Revised: August 31, 2019

Early access: October 2021

Published: March 2021

Abstract Full Text(HTML) Figure(3) / Table(4) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 26C10, 90C20, 90C25, 90C90.

Citation:

Full Text(HTML)

Figure 1. The underestimator in ($ BB $) and ($ BR $)

Download: Full-size image PowerPoint slide

Figure 2. The underestimator in our method ($ BBR $)

Download: Full-size image PowerPoint slide

Figure 3. Tightness of our underestimator $ p(x) $ than the $ q(x) $ used in the classical methods ($ BB $) and ($ BR $)

Download: Full-size image PowerPoint slide

Table 1. Numerical results of Example 1

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

| Show Table

DownLoad: CSV

Table 2. Numerical results of Example 2

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

| Show Table

DownLoad: CSV

Table 3. Numerical results of Example 3

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

| Show Table

DownLoad: CSV

Table 4. Numerical results of Example 4

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.