4
$\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?

$\endgroup$
2
  • 2
    $\begingroup$ I wonder if something involving the companion matrix will be helpful? $\endgroup$ Nov 24, 2021 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$
    – Deirdre
    Nov 24, 2021 at 17:38

1 Answer 1

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 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.

$\endgroup$
8
  • 1
    $\begingroup$ Isn't this the inverse of the condition number? $\endgroup$ Nov 24, 2021 at 15:25
  • $\begingroup$ It's the inverse of the condition number of evaluation. $\endgroup$
    – user14717
    Nov 24, 2021 at 15:25
  • 2
    $\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, 2021 at 17:55
  • 1
    $\begingroup$ A good reference is Corless, A Graduate Introduction to Numerical Methods, Section 3.2.1. In that works, he considers perturbations of the coefficients of the polynomial, which results in $\tilde{p}(\tilde{r}) \approx \epsilon r p'(r) + \delta p(r)$ where $p$ is the polynomial with exact coefficients, and $\delta p$ is the perturbation of the polynomial under the assumption that each coefficient is rounded according to the floating point model. $\endgroup$
    – user14717
    Nov 24, 2021 at 18:54
  • 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$
    – Deirdre
    Nov 24, 2021 at 20:17

Your Answer

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.