Re: Orthogonal polynomials (was Chebyshv, etc.)

On Sun, 31 May 2009 11:49:26 +0100, Angus Rodgers
<twirlip@xxxxxxxxxxx> wrote:

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 ...

It's immediate from something that _is_ proved, namely that

P_{k+1}' P_k > P_{k+1} P_k.

Does it take long to learn how to edit Wikipedia? I've
never tried.)

David C. Ullrich

"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)
.

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 ...
    (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)
  • Re: Orthogonal polynomials (was Chebyshv, etc.)
    ... This general property of orthogonal polynomials is proved as ... degree, because of the orthogonality properties, therefore the ... multiple roots of P_n. ... "Understanding Godel isn't about following his formal proof. ...
    (sci.math)