Algorithms for Polynomial Real Root-Finding

Real root finding of polynomials is a fundamental problem in mathematics with applications across various scientific and engineering disciplines. This article provides an overview of a common approach to solving this problem: real root isolation using interval bracketing. This method involves systematically partitioning the real number line into smaller and smaller intervals until each interval contains at most one root, effectively isolating all real roots. Core Idea: Interval Splitting and Arithmetic The core idea behind interval bracketing algorithms is to repeatedly subdivide an interval known to contain roots into smaller subintervals until we separated all roots into disjoint intervals....

In his video titled Cannons that Never Miss, YouTuber b2studios developed an algorithm for finding real roots of polynomials. Essentially, we are relying on the bisection method, but the main trick provided by b2studios is a simple and effective heuristic for identifying intervals isolating the roots. The way this is done is that we compute the derivative and the polynomial $ p’(x) $ of the original polynomial $ p(x) $. Then, the assumption is that each root of $ p’(x) $ lies between two consecutive roots of $ p(x) $....