Re: Orthogonal polynomials (was Chebyshv, etc.)

Denis Feldmann wrote:
Angus Rodgers a écrit :
On Sun, 31 May 2009 04:49:03 -0500, David C. Ullrich
<dullrich@xxxxxxxxxxx> wrote:

On Sat, 30 May 2009 13:25:33 +0200, Denis Feldmann
<feldmann.denis.asupprimer@xxxxxxx> wrote:

David C. Ullrich a écrit :
On Fri, 29 May 2009 23:36:32 +0100, Angus Rodgers
<twirlip@xxxxxxxxxxx> wrote:

On Fri, 29 May 2009 18:15:49 +0200, Denis Feldmann
<denis.feldmann.sansspam@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
.

Relevant Pages

  • Re: Orthogonal polynomials (was Chebyshv, etc.)
    ... Legendre, Chebyshev, Hermite, etc.) have n real roots in the ... This general property of orthogonal polynomials is proved as ... you can simply ignore any zeros ... If alpha is a real root of phi_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 ... 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.)
    ... Legendre, Chebyshev, Hermite, etc.) have n real roots in the ... This general property of orthogonal polynomials is proved as ... of the orthogonality properties of phi_k, r is not less than k. ...
    (sci.math)