Quadratic interval refinement for real roots

DOI10.1145/2644288.2644291MaRDI QIDQ5255832zbMATH OpenOpenAlexFDO

Authors John Abbott

Publication date 19 June 2015

Published in ACM Communications in Computer Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.1227

Mathematics Subject Classification ID

Numerical computation of roots of polynomial equations (65H04) Symbolic computation and algebraic computation (68W30)

Abstract: We present a new algorithm for refining a real interval containing a single real root: the new method combines characteristics of the classical Bisection algorithm and Newton's Iteration. Our method exhibits quadratic convergence when refining isolating intervals of simple roots of polynomials (and other well-behaved functions). We assume the use of arbitrary precision rational arithmetic. Unlike Newton's Iteration our method does not need to evaluate the derivative.

Recommendations

• Root refinement for real polynomials using quadratic interval refinement
• Nearly optimal refinement of real roots of a univariate polynomial
• A new method for real root isolation of univariate polynomials
• Efficient real root approximation
• On the Boolean complexity of real root refinement

Cited in

(20)

• On the asymptotic and practical complexity of solving bivariate systems over the reals
• A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration
• A new trigonometrical algorithm for computing real root of non-linear transcendental equations
• Accelerated subdivision for clustering roots of polynomials given by evaluation oracles
• Piecewise quadratic bounding functions for finding real roots of polynomials
• Near optimal subdivision algorithms for real root isolation
• Quadric arrangement in classifying rigid motions of a 3D digital image
• On the Boolean complexity of real root refinement
• Koszul algebras and computations
• Real roots of quadratic interval polynomials
• Exact symbolic-numeric computation of planar algebraic curves
• Root refinement for real polynomials using quadratic interval refinement
• Computing real roots of real polynomials
• New algorithms for computing a root of non-linear equations using exponential series
• scientific article; zbMATH DE number 4182705 (Why is no real title available?)
• New algorithms to estimate the real roots of differentiable functions and polynomials on a closed finite interval
• A complete, exact and efficient implementation for computing the edge-adjacency graph of an arrangement of quadrics
• msolve. A library for solving polynomial systems
• On arrangements of quadrics in decomposing the parameter space of 3D digitized rigid motions
• Nearly optimal refinement of real roots of a univariate polynomial

This page was built for publication: Quadratic interval refinement for real roots

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5255832)