Combining binary search and Newton's method to compute real roots for a class of real functions

DOI10.1006/jcom.1994.1014zbMath0844.65045OpenAlexW1973917838MaRDI QIDQ1336478

Yinyu Ye

Publication date: 29 August 1996

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcom.1994.1014

zbMATH Keywords

complexityNewton's methodreal functionsreal rootsbisection methodhybrid algorithmbinary searchSmale type condition

Mathematics Subject Classification ID

Numerical computation of solutions to single equations (65H05) Complexity and performance of numerical algorithms (65Y20)

Related Items

On the complexity of approximating a KKT point of quadratic programming ⋮ On solving univariate sparse polynomials in logarithmic time ⋮ The trust region subproblem and semidefinite programming* ⋮ A new solution method for the finite-horizon discrete-time EOQ problem ⋮ Solving degenerate sparse polynomial systems faster ⋮ Some speed-ups and speed limits for real algebraic geometry