From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik) Subject: Re: Polynomials and real roots Date: 27 Jan 2001 15:03:48 -0500 Newsgroups: sci.math Summary: Roots of polynomials in orthogonal families are real and distinct In article <3a72f94a.4808023@nntp.sprynet.com>, David C. Ullrich wrote: :On 26 Jan 2001 11:35:13 -0500, kovarik@mcmail.cis.McMaster.CA :(Zdislav V. Kovarik) wrote: : :>In article <3a717426$1@ensae.fr>, :>Sebastian Perez-Duarte wrote: :>:Is there a way (without actually finding the roots) to know :>:if a polynomial (of any degree) has all its roots on the real :>:line ? (like the bē-4ac of 2nd degree polynomials) :>: :> :>In other posts, Schur method Embarrassing confusion of names: Sturm was intended, not Schur. :>was mentioned; [...] :>There is a sufficient condition applicable in special :>situations: every orthogonal polynomial has all roots :>real and distinct, and within the smallest interval :>containing the support of the measure with respect to :>which the polynomials are constructed. : :??? You must be leaving out hypotheses or something... :One can easily concoct a measure with bounded support :with respect to which 1, x, and x^2+1 are orthogonal. :Then one could apply Gram-Schmidt to the sequence :1, x, x^2+1, x^3, x^4, x^5, x^6... to get a sequence of :orthogonal polynomials wrt to this measure. What measure allows x^2+1 to be orthogonal to 1 ? That is, what assumptions from the theorem below have to be dropped? :I hesitate to ask because whatever the actual :theorem is it's a classical result I should know :very well. What is the actual theorem? (Or what's :the error above?) Theorem. Let m be a non-negative Borel measure on a closed interval J within the real line, such that all polynomials belong to L^2(m) and every nonzero polynomial has positive norm. Then the orthogonal polynomial p_n (p_n of degree n, orthogonal to every polynomial of lower degree) has n distinct real roots in J. Proof. (For simplicity, assume that non-zero polynomials used below are monic.) Let r be the divisor of p_n whose roots are those roots of odd multiplicity of p_n which lie in J, each used exactly once. Let q be the quotient, so that p_n = q * r. Then q>=0 in J (has only roots in J of even multiplicity together with roots of any multiplicity which lie outside J, including hypothetically complex conjugate pairs). We want to show that r is of degree n (so q is constant). Also, q is monic, so > 0. We have q*r^2 = p_n*r; suppose deg(r) < n, then 0 = = , forcing the non-negative polynomial q*r^2 to be 0 everywhere, but this is impossible. Hence, deg(r)=n, and r=p_n has the roots as claimed. Remarks. J need not be bounded (e.g. for Laguerre and Hermite polynomials). If m is a non-atomic measure, J can be replaced by its interior for locating the roots. A version of the theorem can be formulated where the degrees of polynomials are bounded, allowing measures with finite supports (useful in least-squares fitting). Interlacing property for the roots of p_n and p_(n+1) can be proved by identifying the Gram-Schmidt process as representation of the coordinate operator f |-> X*f, X*f(x) = x*f(x) in the basis {p_k} (leading to the three-term relation and tridiagonal symmetrizable matrix). Hope I did not leave out any more assumptions. Cheers, ZVK(Slavek). ============================================================================== From: ullrich@math.okstate.edu (David C. Ullrich) Subject: Re: Polynomials and real roots Date: Sun, 28 Jan 2001 15:20:57 GMT Newsgroups: sci.math On 27 Jan 2001 15:03:48 -0500, kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik) wrote: Just to prove I'm paying attention after yesterday's idiocies: >Theorem. > Let m be a non-negative Borel measure on a closed >interval J within the real line, such that all >polynomials belong to L^2(m) and every nonzero >polynomial has positive norm. > Then the orthogonal polynomial p_n (p_n of degree n, >orthogonal to every polynomial of lower degree) >has n distinct real roots in J. > >Proof. >(For simplicity, assume that non-zero polynomials used >below are monic.) > >Let r be the divisor of p_n whose roots are those roots >of odd multiplicity of p_n which lie in J, each used >exactly once. >Let q be the quotient, so that p_n = q * r. > >Then q>=0 in J (has only roots in J of even >multiplicity together with roots of any multiplicity >which lie outside J, including hypothetically complex >conjugate pairs). I don't see why q>=0 here. Well I do see why, because I see why the theorem is true and the theorem implies that q=1. But I don't see why it's immediate that q>=0 at this point. Any zeroes of q in J have even order, and so q cannot change sign in J, so either q>=0 in J or q<=0 in J. Doesn't matter, the proof works in either case (or we could abandon monicity and replace r by -r if necessary to get q>=0). > We want to show that r is of degree >n (so q is constant). Also, q is monic, so > 0. Or one could say that q is non-zero, and hence the hypothesis states explictly that > 0. (Not that I see where we use this fact below anyway...) >We have q*r^2 = p_n*r; suppose deg(r) < n, then >0 = = , forcing the non-negative >polynomial q*r^2 to be 0 everywhere, This is the bit that took me a second. q*r^2 is non-negative on J; I don't see why it's non-negative elsewhere. It being non-negative on J shows that q*r^2 = 0 _almost_ _everywhere_ [m]. And this is where we use the hypothesis that the norm of any non-zero polynomial is positive: It follows that m does not have finite support, and _that_ shows that q*r^2 has infinitely many zeroes and hence must be the zero polynomial. (The hypothesis that every non-zero polynomial has positive norm has to be used somewhere, and I don't see it used anywhere else, since I don't see where the fact that > 0 was used.) > but this is >impossible. >Hence, deg(r)=n, and r=p_n has the roots as claimed. Yup. Very interesting. The sort of thing that makes me wish I knew some math. (Anyone know any web sites?) >Remarks. > > J need not be bounded (e.g. for Laguerre and Hermite >polynomials). > > If m is a non-atomic measure, J can be replaced by its >interior for locating the roots. > > A version of the theorem can be formulated where the >degrees of polynomials are bounded, allowing measures >with finite supports (useful in least-squares fitting). Seems like finite measures would be useful in any various sorts of numerical application. If we say that m has support containing exactly N points (there are N atoms, each with strictly positive measure, and nothing else) then it seems at first we get the argument working for polynomials of degree up to N/2: q*r^2=p_n*r has degree <= 2*n, and so if it has N zeroes and N > 2*n it must vanish identically. But hmm, the atoms of m are actually N distinct points, and every zero of r is a zero of p_n as well. So if p_n*r vanishes ae[m] then p_n actually has N distinct zeroes and hence N zeroes, which is a contradiction if n <= N. So the result holds for polynomials of degree <= N, if m has support containing exactly N points(?) > Interlacing property for the roots of p_n and p_(n+1) >can be proved by identifying the Gram-Schmidt process >as representation of the coordinate operator > f |-> X*f, X*f(x) = x*f(x) in the basis {p_k} >(leading to the three-term relation and tridiagonal >symmetrizable matrix). > >Hope I did not leave out any more assumptions. > >Cheers, ZVK(Slavek).