Đang chuẩn bị liên kết để tải về tài liệu:
Computing real zeros of a polynomial by branch and bound and branch and reduce algorithms

In this paper we propose two algorithms based on branch and bound method and reduced interval techniques to compute all real zeros of a polynomial. Quadratic bounding functions are proposed which are better than the well known linear underestimator. Experimental result shows the efficiency of the two algorithms when facing ill-conditionned polynomials. | Yugoslav Journal of Operations Research 24 (2014) Number 1,53-69 DOI:10.2298/YJOR120620004L COMPUTING REAL ZEROS OF A POLYNOMIAL BY BRANCH AND BOUND AND BRANCH AND REDUCE ALGORITHMS Hoai An LE THI Laboratoire d’Informatique Th´eorique et Appliqu´ee (LITA) Universit´e de Lorraine, 57045 Metz cedex1-France hoai-an.le-thi@univ-lorraine.fr Mohand OUANES D´epartement de Math´ematiques, Facult´e des Sciences, Universit´e de Tizi-Ouzou, Alg´erie mohand.Ouanes@yahoo.fr Ahmed ZIDNA Laboratoire d’Informatique Th´eorique et Appliqu´ee (LITA) Universit´e de Lorraine, 57045 Metz cedex1-France ahmed.zidna@univ-lorraine.fr Received: June 2012 / Accepted: December 2013 Abstract: In this paper we propose two algorithms based on branch and bound method and reduced interval techniques to compute all real zeros of a polynomial. Quadratic bounding functions are proposed which are better than the well known linear underestimator. Experimental result shows the efficiency of the two algorithms when facing ill-conditionned polynomials. Keywords: Global optimization quadratic upper function quadratic lower function root-finding Bound and Reduce Branch and Bound w-subdivision MSC:26C10, 90C20, 90C25, 90C90. 54 H. An Le Thi, M. Ouanes, A. Zidna / Computing Real Zeros 1 INTRODUCTION Several fundamental geometrical problems that arise in the processing of curves and surfaces may be reduced computationally by isolating and approximating the distinct real roots of univariate polynomials on finite intervals. Many different approaches for solving a polynomial equation exist [1]. We briefly mention the methods based on deflation techniques [2]. Other ones proceed by subdividing the interval into a sequence of intervals such that each one contains one and only one zero of the polynomial [3]. In [7], the authors propose a method for finding real zeros of a polynomial in Bernstein basis. In recent years univariate global optimization problems have attracted common attention because they arise in many .