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 ϵ>0, can we perturb each coefficient of f by less than ϵ 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=x2, 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 x2+bx+c with b2>4c will be a perturbation that yields two real roots so we've solved 1) for f=x2.



I think this will not be difficult and can be done. Just consider f=c(xri)ki and reduce to the case of a single (xri)ki. Recenter root to be 0 so that we have xd 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 d1 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 dk 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<3k1 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)=x88x78x6+160x586x4872x3+768x2+720x675=0
which has double roots at x=3,x=1,x=5 and thus a deficiency of 3 real roots.




Now add
f(x)=180(x22x7)



ˉP(x)=x88x78x6+160x586x4872x3+6143980x2+2880140x5399380=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 limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...