Propriétés de la constante de Lebesgue

Discussions générales concernant les mathématiques et n'entrant pas dans les catégories suivantes.
[participation réservée aux utilisateurs inscrits]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
surjay

Propriétés de la constante de Lebesgue

Message non lu par surjay »

Bonjour,

En ce moment je suis sur un projet d'analyse numérique sur la constante de Lebesgue, et j'aurai besoin d'aide pour démontrer 2 résultats.
Je donne ici le début de mon rapport (en anglais) pour ceux qui se demandent ce qu'est la constante de Lebesgue mais n'ai besoin d'aide que pour finir les preuves des 2 propositions.

Let $\mathscr{L}_{T}^{n}\::\: C([-1,1])\rightarrow P^{n}([-1,1])$ be the linear projection operator that, for any $f\in C([-1,1])$, gives a $n\text{-degree}$ polynomial $p_{n}$ such that $\forall x_{i}\in T,p_{n}(x_{i})=f(x_{i})$ with $0\le i\le n$.

Lebesgue's inequality
$\left\Vert f-\mathscr{L}_{T}^{n}f\right\Vert \leq\left\Vert f-p^{*}\right\Vert \left(1+\left\Vert \mathscr{L}_{T}^{n}\right\Vert \right)$ where $p*$ is the closest n-degree polynomial to $f$ in the sense of $\left\Vert .\right\Vert $

Because of the triangle inequality, we have $\left\Vert f-\mathscr{L}_{T}^{n}f\right\Vert \leq\left\Vert f-p^{*}\right\Vert +\left\Vert p^{*}-\mathscr{L}_{T}^{n}f\right\Vert $
Therefore $\left\Vert f-\mathscr{L}_{T}^{n}f\right\Vert \leq\left\Vert f-p^{*}\right\Vert \left(1+\frac{\left\Vert p^{*}-\mathscr{L}_{T}^{n}f\right\Vert }{\left\Vert f-p^{*}\right\Vert }\right)$ and as $\mathscr{L}_{T}^{n}$ is a linear projector, we get $\frac{\left\Vert p^{*}-\mathscr{L}_{T}^{n}f\right\Vert }{\left\Vert f-p^{*}\right\Vert }=\frac{\left\Vert \mathscr{L}_{T}^{n}(p^{*}-f)\right\Vert }{\left\Vert f-p^{*}\right\Vert }\leq\max_{\left\Vert f-p*\right\Vert \neq0}\frac{\left\Vert \mathscr{L}_{T}^{n}(p^{*}-f)\right\Vert }{\left\Vert f-p^{*}\right\Vert }=\left\Vert \mathscr{L}_{T}^{n}\right\Vert $

As a consequence $\left\Vert f-\mathscr{L}_{T}^{n}f\right\Vert \leq\left\Vert f-p^{*}\right\Vert \left(1+\left\Vert \mathscr{L}_{T}^{n}\right\Vert \right)$.

Definition :
$\lambda(T)=\left\Vert \mathscr{L}_{T}^{n}\right\Vert _{\infty}$ denotes the Lebesgue constant.

Proposition :
$\lambda(T)=\max_{x\in[-1,1]}\sum_{i}\left|L_{i}^{T}(x)\right|$ where $L_{i}^{T}$ denotes the lagrange functions, such that $L_{i}^{T}(x_{j})=\delta_{ij}$.

$\lambda(T)=\left\Vert \mathscr{L}_{T}^{n}\right\Vert _{\infty}=\max_{\left\Vert f\right\Vert _{\infty}=1,x\in[-1,1]}\left|\mathscr{L}_{T}f\right|=\max_{\left\Vert f\right\Vert _{\infty}=1,x\in[-1,1]}\left|\sum_{i}f(x_{i})L_{i}^{T}(x)\right|$
And because $\left\Vert f\right\Vert _{\infty}=1\Rightarrow\left|f(x_{i})\right|\le1$, we get $\lambda(T)\le\max_{x\in[-1,1]}\sum_{i}\left|L_{i}^{T}(x)\right|$
Now we have to show that $\lambda(T)\ge\max_{x\in[-1,1]}\sum_{i}\left|L_{i}^{T}(x)\right|$

Proposition :
The Lebesgue constant is the condition of $\mathscr{L}_{T}^{n}$, i.e.
$\frac{\left\Vert p-\hat{p}\right\Vert }{\left\Vert p\right\Vert }\le\left\Vert \mathscr{L}_{T}^{n}\right\Vert \frac{\left\Vert f-\hat{f}\right\Vert }{\left\Vert \hat{f}\right\Vert }$ with $p=\mathscr{L}_{T}^{n}f$ and $\hat{p}=\mathscr{L}_{T}^{n}\hat{f}$

Because $\left\Vert \mathscr{L}_{T}^{n}f\right\Vert \le\left\Vert \mathscr{L}_{T}^{n}\right\Vert \left\Vert f\right\Vert $, we have $\left\Vert p-p\right\Vert \le\left\Vert \mathscr{L}_{T}^{n}\right\Vert \left\Vert f-f\right\Vert $
But the proposition seems to be equivalent to $\left\Vert \mathscr{L}_{T}^{n}\right\Vert \le1$ and I don't know why it would be true.
OG
Modérateur spécialisé
Modérateur spécialisé
Messages : 2293
Inscription : lundi 12 mars 2007, 11:20
Localisation : Rouen

Re: Propriétés de la constante de Lebesgue

Message non lu par OG »

Pour la 1ère question, comme $p^*(x)=\sum_{i=0}^n f(x_i) L_i^T(x)$ en considérant que le max de $\sum |L_i^T(x)|$ est atteint en un certain point $y$, on va prendre une fonction $f$ qui vaut $\pm 1$ en les $x_i$ de façon à avoir $p^*(y)=\sum |L_i^T(y)|$. Si ce n'est pas clair dis le moi.

Pour la 2nde question, ça ressemble au conditionnement pour les matrices, en fait cette constante de Lebesgue mesure effectivement la sensibilité de l'interpolation par rapport aux erreurs (par exemple si tu fais l'interpolation de Lagrange aux points de Tchebychev sur Scilab/Matlab sur beaucoup de points ton polynôme explose sur le bord car cette constante de Lebesgue est très grande alors qu'en théorie il y a convergence uniforme dès que $f$ est Lipschitz). Donc il faut revoir ce que tu as fait car $\Lambda_T$ n'est pas inférieure à 1.

O.G.
surjay

Re: Propriétés de la constante de Lebesgue

Message non lu par surjay »

Merci O.G., je crois avoir compris comment terminer les preuves :

1) J'utilise $\lambda(T)=\max_{\left\Vert f\right\Vert _{\infty}=1,x\in[-1,1]}\left|\sum_{i}f(x_{i})L_{i}^{T}(x)\right|$ avec y tq $\sum_{i}\left|L_{i}^{T}(y)\right|=\max_{x\in[-1,1]}\sum_{i}\left|L_{i}^{T}(x)\right|$ et $f(x_{i})=\frac{L_{i}^{T}(y)}{\left|L_{i}^{T}(y)\right|}$

2) En fait c'est $\left\Vert \mathscr{L}_{T}^{n}\right\Vert \ge1$, une condition suffisante pour montrer la proposition.
Elle est vraie pour $\left\Vert .\right\Vert _{\infty}$, après je ne sais pas si c'est vrai pour les autres normes ni si c'est intéressant à montrer.
OG
Modérateur spécialisé
Modérateur spécialisé
Messages : 2293
Inscription : lundi 12 mars 2007, 11:20
Localisation : Rouen

Re: Propriétés de la constante de Lebesgue

Message non lu par OG »

1) il faut tout de même dire qu'une telle fonction existe (affine même)

2) bizarrrrre je ne suis pas convaincu qua fais-tu des terme $\|f\|$ et $\|p \|$ ?

Dans la suite de ton problème as-tu des équivalents à démontrer pour
les points de Tchebychev ou les points équidistants ?

O.G.
surjay

Re: Propriétés de la constante de Lebesgue

Message non lu par surjay »

1) Une telle fonction existe, définie nulle part sauf pour les $x_i$ :P

2) La démo complète :
Because $\left\Vert \mathscr{L}_{T}^{n}f\right\Vert \le\left\Vert \mathscr{L}_{T}^{n}\right\Vert \left\Vert f\right\Vert$ , we have $\left\Vert p-\hat{p}\right\Vert \le\left\Vert \mathscr{L}_{T}^{n}\right\Vert \left\Vert f-\hat{f}\right\Vert $

As $\frac{\left\Vert p-\hat{p}\right\Vert }{\left\Vert p\right\Vert }\le\left\Vert \mathscr{L}_{T}^{n}\right\Vert \frac{\left\Vert f-\hat{f}\right\Vert }{\left\Vert f\right\Vert }\Leftrightarrow\left\Vert p-\hat{p}\right\Vert \left\Vert f\right\Vert \le\left\Vert \mathscr{L}_{T}^{n}\right\Vert \left\Vert f-\hat{f}\right\Vert \left\Vert p\right\Vert \Leftarrow\left\Vert f\right\Vert \le\left\Vert \mathscr{L}_{T}^{n}f\right\Vert \leq\left\Vert \mathscr{L}_{T}^{n}\right\Vert \left\Vert f\right\Vert $

We have the sufficient condition $\left\Vert \mathscr{L}_{T}^{n}\right\Vert \ge1$, which is true for $\left\Vert .\right\Vert _{\infty}$ :
$\left\Vert \mathscr{L}_{T}^{n}\right\Vert _{\infty}=\max_{x\in[-1,1]}\sum_{i}\left|L_{i}^{T}(x)\right|\ge\sum_{i}\left|L_{i}^{T}(x_{j})\right|=1$

Je n'ai pas vraiment de problème à proprement parler, juste 2 articles en anglais où j'ai trouvé l'équivalent de la constante pour des points équidistant et un encadrement pour Chebyshev.
Ca pourrait être intéressant de les démontrer, je posterai probablement là dessus vu que je n'ai pas l'article dans lequel c'est démontré.

Edit : ce dont je suis sur c'est qu'il faut que je calcule la constante de Lebesgue pour les grilles de Lobatto et de Fekete.
Ca n'a pas l'air simple :?
OG
Modérateur spécialisé
Modérateur spécialisé
Messages : 2293
Inscription : lundi 12 mars 2007, 11:20
Localisation : Rouen

Re: Propriétés de la constante de Lebesgue

Message non lu par OG »

vbnul a écrit : Je n'ai pas vraiment de problème à proprement parler, juste 2 articles en anglais où j'ai trouvé l'équivalent de la constante pour des points équidistant et un encadrement pour Chebyshev.
Ca pourrait être intéressant de les démontrer, je posterai probablement là dessus vu que je n'ai pas l'article dans lequel c'est démontré.

Edit : ce dont je suis sur c'est qu'il faut que je calcule la constante de Lebesgue pour les grilles de Lobatto et de Fekete.
Ca n'a pas l'air simple :?
Pour les équivalents on peut les trouver dans certains livres français ou encore dans des fiches
de TD (je faisais cela il y a quelques années). C'est juste un peu d'analyse...

Pour tes grilles, c'est une valeur exacte ou une valeur approchée ?
bon courage
O.G.
surjay

Re: Propriétés de la constante de Lebesgue

Message non lu par surjay »

Si tu as de la doc sur les équivalents, les grilles ou la constante de Lebesgue en général, ca m'intéresse :D
Tout ce que je trouve ce sont des articles sur des sites genre « Springerlink » qui demandent un abonnement.

Je dois trouver des valeurs approchées des constantes pour les grilles de Lobatto et Fekete, mais pour le moment je ne sais pas comment elles sont définies ni comment trouver des polynômes de Lagrange quand les points sont sur un triangle.

Par contre j'ai fait l'interpolation avec beaucoup de points de Chebyshev et en effet le polynôme explose sur les bords.
Pièces jointes
chebychev.png
chebychev.png (11.16 Kio) Consulté 3290 fois
OG
Modérateur spécialisé
Modérateur spécialisé
Messages : 2293
Inscription : lundi 12 mars 2007, 11:20
Localisation : Rouen

Re: Propriétés de la constante de Lebesgue

Message non lu par OG »

vbnul a écrit :Si tu as de la doc sur les équivalents, les grilles ou la constante de Lebesgue en général, ca m'intéresse :D
Tout ce que je trouve ce sont des articles sur des sites genre « Springerlink » qui demandent un abonnement.

Je dois trouver des valeurs approchées des constantes pour les grilles de Lobatto et Fekete, mais pour le moment je ne sais pas comment elles sont définies ni comment trouver des polynômes de Lagrange quand les points sont sur un triangle.

Par contre j'ai fait l'interpolation avec beaucoup de points de Chebyshev et en effet le polynôme explose sur les bords.
Quand tu parles de triangle tu fais de la 2D ? Sinon je ne connais pas ces grilles...

Ce n'est pas le polynôme qui explose sur les bords : c'est un phénomène numérique du à la précision
de ta machine et l'accumulation d'erreur dans les calculs successifs (la constante de Lebesgue
tend vers l'infini). Si tu disposais d'une précision suffisante tu aurais deux courbes qui se superposent.
Par contre l'effet de Runge pour les points équidistants est quant à lui un résultat mathématique.

Pour les équivalents j'ai mis une fiche de TD qui trainait...
O.G.
Pièces jointes
fichen2.pdf
(132 Kio) Téléchargé 390 fois
surjay

Re: Propriétés de la constante de Lebesgue

Message non lu par surjay »

Oui, le triangle c'est pour l'interpolation de fonctions de deux variables par des polynômes, aussi à deux variables donc.
OG a écrit :par exemple si tu fais l'interpolation de Lagrange aux points de Tchebychev sur Scilab/Matlab sur beaucoup de points ton polynôme explose sur le bord car cette constante de Lebesgue est très grande…
OG a écrit :Ce n'est pas le polynôme qui explose sur les bords
Si si :mrgreen: . J'ai bien vu la différence, question de vocabulaire.

Le projet est presque terminé, je met mon rapport en PJ, toute correction ou critique est bienvenue :)
Pièces jointes
interpolation project report.pdf
(408.98 Kio) Téléchargé 437 fois
OG
Modérateur spécialisé
Modérateur spécialisé
Messages : 2293
Inscription : lundi 12 mars 2007, 11:20
Localisation : Rouen

Re: Propriétés de la constante de Lebesgue

Message non lu par OG »

j'ai lu pendant 40 secondes ton document, je ferai un effort plus tard.
Et les différences divisées de Newton elles comptent pour du beurre ?
(au moins en dimension 1)

O.G.
surjay

Re: Propriétés de la constante de Lebesgue

Message non lu par surjay »

Pour du beurre, parfaitement :P
La première partie n'est là que pour occuper l'incapable démotivé qui me sert de binome :roll: . En plus c'est dans les cours de l'an dernier… donc aucun intérêt.

J'ai compris pourquoi je ne trouvais rien dans la littérature, les mathématiciens publient leurs articles dans des revues qui les revendent à un prix honteux sur internet.
Faudra que je me renseigne là dessus, je sais que la recherche n'est pas bien payée, mais quand même :?
OG
Modérateur spécialisé
Modérateur spécialisé
Messages : 2293
Inscription : lundi 12 mars 2007, 11:20
Localisation : Rouen

Re: Propriétés de la constante de Lebesgue

Message non lu par OG »

Cher vbnul
vbnul a écrit :Pour du beurre, parfaitement :P
La première partie n'est là que pour occuper l'incapable démotivé qui me sert de binome :roll: . En plus c'est dans les cours de l'an dernier… donc aucun intérêt.
Tu voulais un avis ?
Donc tu peux virer Vandermonde et les polynômes de Lagrange qui ont encore moins d'intérêt que la méthode des différences divisées de Newton.
D'autant plus que tu pourrais signaler qu'avec les polynômes de base de Lagrange on peut faire quelques améliorations quant à la complexité de calcul.
Revoir l'anglais aussi.
C'est bizarre dans ton exemple (du site et de ton document) ton polynôme d'interpolation ne passe pas les points (d'interpolation),
le nombre de points n'est pas si grand (une quarantaine). Quelle méthode utilises-tu pour calculer ton polynôme d'interpolation
et pour l'évaluer ?
vbnul a écrit : J'ai compris pourquoi je ne trouvais rien dans la littérature, les mathématiciens publient leurs articles dans des revues qui les revendent à un prix honteux sur internet.
Faudra que je me renseigne là dessus, je sais que la recherche n'est pas bien payée, mais quand même :?
Je ne comprends pas bien ce que tu as compris. Les revues actuelles sont issues de l'ancien modèle : avant il y avait
un véritable travail pour les revues de mise en forme des articles (pas de LaTeX puis un peu). Aujourd'hui on envoie directement
la source et il y a donc peu de travail pour ces revues. Les sources sont souvent retravaillées et pour certains éditeurs
dans des pays où la main d'oeuvre est bon marché. Mais comme il y a toujours une version papier tout abonnement
est payant et même les articles sur les sites de ces revues. Enfin il y a certain monopole des éditeurs (Elsevier, Springer, etc).

Actuellement il existe quelques revues gratuites, d'autres avec un mode de fonctionnement étrange (à mes yeux) où
la personne qui publie paie une somme en fonction du nombre de pages mais les articles sont lisibles gratuitement.
Il faudrait tout de même que tu saches que lorsqu'un mathématicien publie un article il ne touche rien du tout
il est juste content que son article soit accepté pour pubication. D'autre part les articles sont examinés par
des "référés" pour savoir si le papier vaut la peine d'être publié, bien sûr le travail de "referee" n'est pas rémunéré.
Pour les articles récents il arrive que le fichier soit disponible sur la page de l'auteur, sur arxiv ou encore
hal (développé par le cnrs donc auteurs dans des labos français). Un mail poli peut même faire l'affaire.
Avant d'acheter un article mathématique fais attention tout de même tu pourrais ne pas comprendre et
donc jeter ton argent par les fenêtres.
N'oublie les bibiliothèques. Ce que tu cherches est plutôt fait par des mécaniciens, des personnes qui programment
(pour de vrai) les méthodes.


O.G.
surjay

Re: Propriétés de la constante de Lebesgue

Message non lu par surjay »

Les différences divisées sont certes plus performantes que les polynômes de Lagrange, cependant le sujet du projet c'est la constante de Lebesgue et les ensembles de points qui permettent de la minimiser. Or on ne connait l'expression de cette constante qu'en fonction des polynômes de Lagrange, la matrice de Vandermonde a donc sa place dans le rapport à mon avis, surtout qu'on utilise pas toujours la base canonique.
Enfin même si on pourrai virer quelques trucs, c'est du travail effectué pendant le projet donc autant le rendre aussi.

L'anglais n'est pas terrible c'est vrai, j'aurai aimé lire plus d'articles dans cette langue avant d'en rédiger un moi même.

Pour le polynôme qui ne passe pas par tous les points, j'ai cru que tu m'avais désigné ce phénomène comme une erreur sur le polynôme due à la condition de l'interpolation. J'ai calculé les polynômes de Lagrange avec leur expression analytique et les ait évalués avec polyeval() et les bons coefficients pour tracer l'interpolant.
OG
Modérateur spécialisé
Modérateur spécialisé
Messages : 2293
Inscription : lundi 12 mars 2007, 11:20
Localisation : Rouen

Re: Propriétés de la constante de Lebesgue

Message non lu par OG »

Re

Disons que si une section se nomme "How to find them ?" écrire que "there are two ways to find them"
me semble exagérer ; et les différences divisées ! (ok j'insiste lourdement)
Je ne connais pas le cadre de ce travail et ce n'est pas moi qui examine le travail.

Voici un exemple avec 72 points de Tchebychev, le polynôme passe tout de même
par les points d'interpolation. C'est fait avec les différences divisées de Newton
en précision style C + algo de Horner pour l'évaluation.
En les points d'interpolation (sauf valeur plus grande de $n$) le polynôme
prend la bonne valeur, c'est en dehors que cela se passe moins bien
et cela est uniquement du aux imprécisions machines + constante de Lebesgue.
C'est peut-être du à la méthode que tu utilises.
Quel langage utilises-tu ?
Pour illustrer ton "histoire de constante de Lebesgue" je mettrai pour des points
de Tchebychev ou autre, une fonction $f$, une perturbation aléatoire (de petite amplitude)
à chaque point d'interpolation et les deux polynômes d'interpolation associés.
Ceci pour 5, 10, 15, 20, etc (des valeurs où le polynôme colle bien la fonction).
A priori plus $n$ est grand plus le polynôme d'interpolation de la perturbation
"décroche"...

O.G.
Pièces jointes
runge4.gif
surjay

Re: Propriétés de la constante de Lebesgue

Message non lu par surjay »

Tu veux dire qu'on peut calculer les polynômes de Lagrange via les différences divisées ?

J'utilise octave pour calculer le graphique, le programme associé est joint.
Pièces jointes
condition.zip
(735 octets) Téléchargé 242 fois
OG
Modérateur spécialisé
Modérateur spécialisé
Messages : 2293
Inscription : lundi 12 mars 2007, 11:20
Localisation : Rouen

Re: Propriétés de la constante de Lebesgue

Message non lu par OG »

vbnul a écrit :Tu veux dire qu'on peut calculer les polynômes de Lagrange via les différences divisées ?

J'utilise octave pour calculer le graphique, le programme associé est joint.
Pour éviter le quipropos, vous avez vu les différences divisées de Newton : pour quoi faire ?
Qu'entends tu précisément par ta question.

J'utilise plutôt Scilab. Je regarderai peut-être ton programme...

O.G.
surjay

Re: Propriétés de la constante de Lebesgue

Message non lu par surjay »

Je sais que les différences divisées sont utilisées pour calculer un interpolant, elles ont l'avantage de demander moins de calculs lors de l'ajout d'un point à interpoler.
OG a écrit :Disons que si une section se nomme "How to find them ?" écrire que "there are two ways to find them"
me semble exagérer ; et les différences divisées ! (ok j'insiste lourdement)
Tu veux bien dire qu'il y a d'autres manières de trouver les polynomes de Lagrange ? Sinon je ne vois pas pourquoi ma rédaction te semble exagérée.

Octave est compatible avec matlab, il est possible que le programme fonctionne aussi avec ce dernier.
OG
Modérateur spécialisé
Modérateur spécialisé
Messages : 2293
Inscription : lundi 12 mars 2007, 11:20
Localisation : Rouen

Re: Propriétés de la constante de Lebesgue

Message non lu par OG »

Re

Pour être clair j'ai mis un pdf sur une activité Scilab. Le polynôme d'interpolation s'écrit
$f[x_0]+(x-x_0)f[x_0,x_1]+\cdots +(x-x_0)\cdots(x-x_{n-1})f[x_0,\ldots,x_n]$
J'espère que c'est clair et que ça fait avance le schmilblik.

Oui Octave est compatible avec Matlab mais j'utilise Scilab avec mes étudiants
depuis quelques années. Si j'ai le temps je regarde...

O.G.
Pièces jointes
tdscilab2a.pdf
(92.79 Kio) Téléchargé 480 fois
surjay

Re: Propriétés de la constante de Lebesgue

Message non lu par surjay »

C'est très clair tout ca, mais je ne vois pas pourquoi tu me suggère de parler des différences divisées.
Le sujet du projet étant la constante de Lebesgue et les ensembles de points d'interpolation… quel est le rapport ?
OG
Modérateur spécialisé
Modérateur spécialisé
Messages : 2293
Inscription : lundi 12 mars 2007, 11:20
Localisation : Rouen

Re: Propriétés de la constante de Lebesgue

Message non lu par OG »

C'est une question de base de polynômes. Tu peux aussi t'amuser
à faire les différences divisées pour le polynôme d'interpolation
et donc obtenir les coefficients dans la base 1, $(x-x_0)$, etc.
et bien sûr jouer avec Horner.
Derrière tout cela c'est question de stabilité numérique et je ne sais pas
ce qui est le mieux. Mais numériquement ces trois méthodes (donnant
mathématiquement le même polynôme) ne donnent pas le même
résultat pour de grandes valeurs de $n$.
De la même façon la méthode de Horner est intéressante dans l'évaluation
d'un polynôme dans la base canonique.


O.G.
Répondre