Re: Orthogonal polynomials (was Chebyshv, etc.)

alainverghote@xxxxxxxxx wrote:
On 1 juin, 05:14, David Bernier <david...@xxxxxxxxxxxx> wrote:
Denis Feldmann wrote:
Angus Rodgers a écrit :
On Sun, 31 May 2009 04:49:03 -0500, David C. Ullrich
<dullr...@xxxxxxxxxxx> wrote:
On Sat, 30 May 2009 13:25:33 +0200, Denis Feldmann
<feldmann.denis.asuppri...@xxxxxxx> wrote:
David C. Ullrich a écrit :
On Fri, 29 May 2009 23:36:32 +0100, Angus Rodgers
<twir...@xxxxxxxxxxx> wrote:
On Fri, 29 May 2009 18:15:49 +0200, Denis Feldmann
<denis.feldmann.sanss...@xxxxxxx> wrote:
Checkiong Wikipedia, I realized there are many more mysteries on
those. For instance , all those polynomials (of degree n) (like
Legendre, Chebyshev, Hermite, etc.) have n real roots in the
interval of integration. Any simple proof?
This general property of orthogonal polynomials is proved as
Theorem 12.2 in M. J. D. Powell, /Approximation Theory and
Methods/ [...] It has something
to do with considering how often the polynomial changes sign
in the interval, multiplying it by another non-zero polynomial
which changes sign at the same points, so that the product is
non-negative, integrating this, and getting a non-zero scalar
product [...]
That's a proof. More formally, if (P_n) is a family of
polynomials, deg(P_n) = n, and the P_n are orthogonal
with respect to some weight on the interval I, then
P_n is orthogonal to every polynomial of degree less
than n. Hence P_n has at least (and hence exactly) n
zeroes on I, because if not then there exists a polyomial
Q with deg(Q) < n such that P_n and Q have the same
zeroes on I, and hence the inner product of P_n and Q
is non-zero.
Well, it is not exactly a proof, because you must first eliminate
multiple roots of P_n.
I don't see why... Ok. Seems to me it _is_ a proof that T_n
has n roots in the interval [-1,1], counted with multiplicity.
It's not a complete proof that there are n distinct roots.
The fact that the zeroes are simple follows from the
fact that T_n satisfies a second-order linear differential
equation. No doubt it's also a general property of
orthogonal polynomials... Ok, cheating: at
http://en.wikipedia.org/wiki/Orthogonal_polynomials
we see that the recurrence for T_n leads to the
inequality
T_{n+1}' T_n > T_{n+1} T_n' ,
which implies that there are no double roots.
The fact that P_n changes sign n times implies that the n zeros
of P_n are distinct. In the proof, you can simply ignore any zeros
where P_n doesn't change sign. Here's the proof exactly
as it is given in the aforementioned book:
Theorem 12.2
Let phi_k be a non-zero polynomial that is in P_k [the real vector
space of polynomials of degree at most k], and that is orthogonal
to the elements of P_{k-1}. Then phi_k has exactly k real and distinct
zeros in the open interval a < x < b. [The scalar product
has been defined as (f, g) = int_a^b w(x)f(x)g(x) dx, for a given
"weight function" w on [a, b], which seems - it's not quite clear
- to be assumed to be strictly positive except at a finite subset
of the interval [a, b]).
Proof. Let r be the number of sign changes of the function {phi_k(x):
a <= x <= b}. [His notation, not mine!] There is a non-zero
polynomial in P_r, psi_r, say, such that the inequality
phi_k(x)*psi_r(x) >= 0, a <= x <= b
holds, the product phi_k(x)*psi_r(x) being zero if and only if x is a
zero of phi_k. It follows from the definition [...] of the
scalar product that (phi_k, psi_r) is positive. Therefore, because
of the orthogonality properties of phi_k, r is not less than k.
Hence phi_k has at least k distinct zeros in the open interval
a < x < b. The number of zeros cannot exceed k because phi_k is a
non-zero element of P_k. Therefore the theorem is true.
(That seems OK to me - although I'm not quite awake enough to feel
very sure of anything. When I'm more awake, I might also type out a
solution to Exercise 12.1 in the book, which proves the property
that there is a zero of phi_{k-1} between each pair of successive
zeros of phi_k. This is stated, but not proved, on the Wikipedia
page ... Does it take long to learn how to edit Wikipedia? I've
never tried.)
Just for your la st question : no, it is very easy (as long as you
know some Latex to be able to type formulas, but usually, even if you
don't, you can just cut and paste some previous formula, and edit it)
Feel free to try, using the previsualisation function first...
I'm trying to see if I've got the details right:

x (x -1) has 2 sign changes,
x^2 (x - 1) has 1 sign change, (e.g. psi(x) could be (x - 1) )
x^3 (x - 1) has 2 sign changes (e.g. psi(x) could be x(x-1) )
x^4 (x -1) has 1 sign change (e.g. psi(x) could be (x - 1) )
etc.

So I'd think psi_r can be chosen to have as roots all real roots of
phi_k(x) of odd order (orders 1, 3, 5, 7, ... ),
where psi_r has only real roots of multiplicity 1 (by definition).

This is to try to take into account that we don't assume
phi_k has only simple roots, of order 1 ...

Does that seem ok ?

David Bernier- Masquer le texte des messages précédents -

- Afficher le texte des messages précédents -

Bonjour David,

Good morning
There are two nice cheby1 parametrizations:
x = cos(t) , t=>2t, 3t , ...
x =(t+1/t)/2 , t=>t^2 , t^3 ...
the first constrains x values to belongs to [-1,1]
And gives P(n)(x) = cos(nt) .

Changing the second one into x =(t+1/t)/3
will yied P(1)(x) = x
P(2)(x) = 3x^2 -2/3
P(3)(x) = 9x^3 -3x
P(4)(x) = 27x^4 -12x^2 +2/3
...............
with similar properties ,

Bonjour Alain,

I hadn't looked at what David Ullrich and Angus wrote about
double roots.

Angus wrote:

"The fact that P_n changes sign n times implies that the n zeros
of P_n are distinct. In the proof, you can simply ignore any zeros
where P_n doesn't change sign. Here's the proof exactly
as it is given in the aforementioned book: [etc.] "

minor edit:
P_n is a vector space in the book to which Angus refers.

I suggest:
"In the proof, you can simply ignore any zeros
where phi_k doesn't change sign. Here's the proof exactly
as it is given in the aforementioned book: [etc.] "


To put more details on what Angus wrote:

If alpha is a real root of phi_k, and phi_k factors over C
as A(x) * (x - alpha)^(2k),
with A some product of the other irreducible terms and k>=1,
with x = alpha +/- epsilon , epsilon>0, epsilon smaller than any gap
between distinct real roots of phi_k, then

A(x) * (x - alpha)^(2k) where x:= alpha+epsilon and
A(x) * (x - alpha)^(2k) where x:= alpha-epsilon

are two real numbers with the same sign.

So there's no point in including 'alpha' in the polynomial

psi_r(x) , since
phi_k(x)*psi_r(x) >= 0, a <= x <= b
will still hold as phi_k(x) has the same
sign on either side of alpha [ double root, quadruple root, etc case].

Now the case where alpha is a root of
odd multiplicity of phi_k(x):

And if phi_k factors over C as
A(x) * (x - alpha)^(2k + 1) ,
there's a sign change of phi_k(x)
at alpha, so a simple zero of psi_r(x)
at alpha via including the factor (x - alpha) in
psi_r(x) will ensure that
phi_k(x)*psi_r(x) >= 0, a <= x <= b

Just to be more specific: let's
assume phi_k(x) > 0
for all sufficiently large x.

David Bernier


.

Relevant Pages

  • Re: Orthogonal polynomials (was Chebyshv, etc.)
    ... This general property of orthogonal polynomials is proved as ... multiple roots of P_n. ... The fact that P_n changes sign n times implies that the n zeros ... of the orthogonality properties of phi_k, r is not less than k. ...
    (sci.math)
  • Re: Orthogonal polynomials (was Chebyshv, etc.)
    ... This general property of orthogonal polynomials is proved as ... multiple roots of P_n. ... The fact that P_n changes sign n times implies that the n zeros ...
    (sci.math)
  • Re: Orthogonal polynomials (was Chebyshv, etc.)
    ... This general property of orthogonal polynomials is proved as ... multiple roots of P_n. ... The fact that P_n changes sign n times implies that the n zeros ... of the orthogonality properties of phi_k, r is not less than k. ...
    (sci.math)
  • Re: Orthogonal polynomials (was Chebyshv, etc.)
    ... For instance, all those polynomials have n real roots in the interval of integration. ... Then phi_k has exactly k real and distinct zeros in the open interval a < x < b. ... of the orthogonality properties of phi_k, r is not less than k. ...
    (sci.math)
  • Re: JSH: Keep it simple
    ... arbitrary rule that you take roots of monic polynomials with integer coefficients. ... integral root is divisible by something that is coprime to ... Your claim regarding rational roots of this polynomial cannot do that, since the standard theory makes no claims regarding common factors among such roots. ...
    (sci.math)