\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Piecewise quadratic bounding functions for finding real roots of polynomials

  • * Corresponding author: Djamel Aaid

    * Corresponding author: Djamel Aaid 
Abstract Full Text(HTML) Figure(3) / Table(4) Related Papers Cited by
  • 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.

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

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  The underestimator in ($ BB $) and ($ BR $)

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

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

    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
  • [1] D. AaidA. Noui and M. Ouanes, New technique for solving univariate global optimization, Archivum Mathematicum, 53 (2017), 19-33. 
    [2] C. S. AdjimanI. 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. ChenW. 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. JiangX. 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. OuanesH. A. Le ThiT. 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. 
  • 加载中

Figures(3)

Tables(4)

SHARE

Article Metrics

HTML views(409) PDF downloads(30) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return