3
$\begingroup$

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?

New contributor
Diedre is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
2
  • 2
    $\begingroup$ I wonder if something involving the companion matrix will be helpful? $\endgroup$ Nov 24 at 16:32
  • $\begingroup$ Ohhh I didn't know this was a thing, but this looks interesting, I'll see if this helps. Thanks! $\endgroup$
    – Diedre
    Nov 24 at 17:38
6
$\begingroup$

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. This suggests taking the largest coefficient of the polynomial. This is straightforward to compute, in Python or any language for that matter. A more sophisticated norm considers perturbations of the coefficients of the polynomial under the rounding model of floating point arithmetic. This results in

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

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.

$\endgroup$
8
  • 1
    $\begingroup$ Isn't this the inverse of the condition number? $\endgroup$ Nov 24 at 15:25
  • $\begingroup$ It's the inverse of the condition number of evaluation. $\endgroup$
    – user14717
    Nov 24 at 15:25
  • $\begingroup$ Ahh I see, so I'd have to do it manually regardless. Thank you for this! I'll check and see what I can do then! Also, is there a difference between getting the condition number vs. getting the inverse of a condition number? I don't think I've heard of the second thing before, so I'm slightly confused. $\endgroup$
    – Diedre
    Nov 24 at 17:40
  • 1
    $\begingroup$ The condition number of rootfinding is what is specified above. Imagine it as follows: If the function is very steep ($|f'(x)| \gg 1$) then small changes in $x$ lead to large errors in evaluation of the function. But this means that rootfinding is well-conditioned, as a large slope makes it easy to recover the root accurately. $\endgroup$
    – user14717
    Nov 24 at 17:55
  • 1
    $\begingroup$ @user14717 ohhh this book looks good, and definitely very detailed. I'm mostly following the Trefethan & Bau book on Numerical LA, and I was having some difficulty understanding some things, so I'll definitely take a look at this. Also, thank you for your answer! $\endgroup$
    – Diedre
    Nov 24 at 20:17

Your Answer

Diedre is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.