Is there any way/any python function to calculate the condition number of the roots of a polynomial directly?

Question

I know that NumPy has linalg.cond(A) to find the condition number of a matrix A. But, if I want to find the condition numbers of the roots of a large polynomial with respect to a small perturbation (something like Wilkinson's polynomial), is there a function that can give me the condition numbers of the roots directly?

I was also thinking along the lines of expressing the polynomial above in the form of a diagonal matrix itself, so that the diagonal entries are then the eigenvalues anyway and they form this polynomial when the determinant is taken, but 1. I'm not sure if that's correct, and 2. I still don't know how I'll get the condition numbers of each root from that since the condition number calculated by cond(A) is for a matrix specifically?

I've also searched extensively on Google and StackOverflow/math.SE but I can't seem to find anything relevant that isn't completely mathematical. Can anyone help out?

Answer 1

The condition number of a root $r$ of a polynomial $p$ is

$$ \kappa := \frac{\left\| p \right\|}{|rp'(r)|} $$

There is some arbitrariness in the choice of norm which affects the definition of the condition number. This suggests taking the largest coefficient of the polynomial.

Corless considers perturbations of the coefficients of the polynomial under the rounding model of floating point arithmetic. This results in the condition number

$$ \kappa = \frac{1}{|rp'(r)|} \sum_{i} |c_{i}r^i| $$

These are all straightforward to compute, in Python or any language for that matter.

Note: After computing a root $\tilde{r}$, I prefer to use the residual $|p(\tilde{r})|$ rather than the condition number to evaluate the quality of the solve. To wit, I know the in the best case, I have $\tilde{r} = r(1+\epsilon)$, so then I Taylor expand to get $|p(\tilde{r})| \approx \epsilon |rp'(r)|$. If $|p(\tilde{r})| \gg \epsilon |\tilde{r}p'(\tilde{r})|$, then I know something is wrong.

Update: Since posting this, I have found another definition of the rootfinding condition number in the infinity norm, given by Higham. Given $p(z) = \sum_{i=0}^{n} c_i z^{i}$ and a simple root $r$, the condition number is

$$ \kappa_{\infty}(p, r) := \frac{\left\| \mathbf{c}\right\|_{\infty} \sum_{i=0}^{n} |r|^{i}}{|r p'(r)|} $$

This is can be generated by an easy inequality and is strictly larger than the condition number defined by Corless.