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.

Seems right to me as well. Took a second to see why he's able
to get the better result by more or less the same argument. Aha:
I took psi_whatever to have the same zeroes as phi_k, uncluding
multiplicity. Instead he takes psi to have a simple zero at
points where phi_k has a zero of odd order and no other
zeroes.

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

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