Friday, 28 October 2016

approximation - Perturbing a polynomial with repeated real roots to get distinct real roots



Consider a real polynomial $f$ of degree $d$ which has $d$ real roots not necessarily distinct. In general, can we accomplish the following?





  1. For every $\epsilon>0$, can we perturb each coefficient of $f$ by less than $\epsilon$ and guarantee real, distinct roots?





I just need one such perturbation to work. I know that a priori, not every perturbation will be nice (read: the number of real roots does not vary continuously like it does in the separable case). For example if $f=x^{2}$, this has $0$ as a root of multiplicity $2$ but if every perturbation of the constant term in the positive direction, there won't be be any real roots at all. But any $x^2+bx+c$ with $b^2>4c$ will be a perturbation that yields two real roots so we've solved 1) for $f=x^2$.



I think this will not be difficult and can be done. Just consider $f=c\prod(x-r_i)^{k_i}$ and reduce to the case of a single $(x-r_i)^{k_i}$. Recenter root to be $0$ so that we have $x^d$ and do this directly. This last part needs argument but I think can be done.





  1. How many coefficients do I need to perturb to achieve objective 1?





For example, in most cases, it is not possible to do just by perturbing the
constant coefficients. The geometric intuition is that a degree $d$ real polynomial with distinct real roots will have $d-1$ local extrema none of which occur at roots. However for those with only $k

Thank you for any comments, solutions or references to the literature that you can provide.


Answer



You can always disambiguate $n$ double roots by perturbing $n$ coefficients.



In general, a perturbation that changes a polynomial of degree $d$ having $d-k$ roots (some of which have multiplicity of $2$ or more) to one that has $d$ distinct real roots requires perturbing $k$ coefficients, and these can always be chosen to be the last $k$ (the constant term, then the linear term, and so forth).




However, there are cases where fewer coefficients will suffice. In particular, whenever $d < 3k-1$ you can "remedy" a polynomial with a deficiency of $k$ roots, by perturbing fewer than $k$ coefficients.



The proof is constructive. For the case of $k$ roots of multiplicity $2$, choose for each double root a sufficiently small quantity having the same sign as the second derivative at that root. Then form a polynomial of degree $d$ passing through the chosen values at the respective roots. Add that polynomial to the original and you get a perturbed polynomial with $d$ real roots. If the perturbation is larger than the allowed change, then divide the added polynomial by some sufficiently large positive number.



For example, consider
$$
P(x) = x^8-8x^7-8x^6+160x^5-86x^4-872x^3+768x^2+720x-675=0
$$
which has double roots at $x=-3, x=1, x=5$ and thus a deficiency of $3$ real roots.




Now add
$$
f(x) = -\frac1{80}(x^2-2x-7)
$$



$$
\bar{P}(x) = x^8-8x^7-8x^6+160x^5-86x^4-872x^3+\frac{61439}{80}x^2+\frac{28801}{40}x-\frac{53993}{80}=0
$$
which has real roots at

$$
\{ -3.00285, -2.99715, -0.99998,+0.99012,+1.00988,+2.99998,+4.99715,+5.00285\}
$$


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...