Quality of positive root bounds. (May 2016)

• Record Type: Journal Article
• Authors: Herman, Aaron; Hong, Hoon
• Is Part Of: Journal of symbolic computation. Volume 74(2016)
• Page Start: 592
• Page End: 602
• Publication Date: 2016-05
• Subjects: Polynomial roots -- Positive root bounds -- Absolute positiveness; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.09.006
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: In this paper, we study the quality of positive root bounds. A positive root bound of a polynomial is an upper bound on the largest positive root. Higher quality means that the relative over-estimation (the ratio of the bound and the largest positive root) is smaller. We report three findings. (1) Most known positive root bounds can be arbitrarily bad ; that is, the relative over-estimation can approach infinity, even when the degree and the coefficient size are fixed. (2) When the number of sign variations is the same as the number of positive roots, the relative over-estimation of a positive root bound due to Hong ( B H ) is at most linear in the degree, no matter what the coefficient size is. (3) When the number of sign variations is one, the relative over-estimation of B H is at most constant, in particular 4, no matter what the degree and the coefficient size are.