Approximating the lowest root of a degree-$N$ polyomial with a quadratic polynomial

57 Views Asked by At

It is known that for a sufficiently high degree polynomials, finding a closed form expression of one of its roots is impossible. To estimate the roots of high-degree polynomials, iterative algorithms are used.

I would like to know if there are non-iterative methods that leverage the structure of a polynomial to find an approximate root of a polynomial.

For example, I have a polynomial of degree $N = 2^n$ where $n \geq 2$. It is known that all roots are real, and the polynomial has the following form: $$ p(x) = \prod_{i=1}^N(r_i - x) + \mu \sum_{j=1}^N c_j \prod_{i \neq j}^N (r_i - x), $$ where $\mu, r_i \in \mathbb{R}$ and $c_j \geq 0$.

When $\mu$ is small, the roots of $p(x)$ will be close to $r_i$. But we can't make this assumption.

The approach I've tried with varying success is to "reduce" $p(x)$ to a quadratic polynomial $g(x)$ so that the new polynomial is close to $p(x)$ at its lowest root. That is, I throw away some of the factors from each summand of $p(x)$ to make it quadratic: $$ g(x) = (r_1 - x)(r_2 - x) + \mu c_2 (r_1 - x)(r_3 - x) + \mu c_3 (r_1 - x)(r_2 - x) + \cdots + \mu c_M(r_1 - x)(r_{M-1}-x). $$ The polynomial $g(x)$ is quadratic and has $M \ll N$ quadratic terms. $M$ should be as small as possible to keep the $g(x)$ relatively simple for analysis and intuition. Note that the number $r_1$ appears in every term of $g(x)$. This is because $r_1$ is the closest number to the lowest root of $p(x)$ for sufficiently small $\mu$.

The plots below show that the quadratic $g(x)$ approximates the first root of quartic $p(x)$ relatively well. The approximation gets worse as $\mu$ gets larger. enter image description here

Question: I would like to know if it is possible to do a better approximation of the first root of $p(x)$ by exploiting the structure of $p(x)$ so that the resulting approximation looks relatively simple and easy to parse for a human.

Also, in the described approach, the approximation quality near the first root of $p(x)$ depends on $\mu$ but also on coefficients $c_j$. It is possible to make the approximation much worse than on the plots by choosing specific $c_j$. On the other hand, $g(x)$ is just a quadratic polynomial and its roots could be found analytically.