Notations de Landau

Aide à la résolution d'exercices ou de problèmes de niveau Supérieur.

Modérateur: gdm_aidesco

Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Ne poster qu'un exercice (ou problème) par sujet et indiquer son niveau précis dans le titre du message.

Notations de Landau

Messagepar woodoo » Jeudi 30 Mai 2013, 22:04

Bonsoir,

j'ai toujours quelques soucis avec les notations de Landau. Dans un corrigé d'exercice j'ai:
$\qquad e^{x} - e^{-x} = (1 + x + \frac{x^{2}}{2} + O(x^{2}))$ $-(1 - x + \frac{x^{2}}{2} + O(x^{2})) = 2x + O(x^{2})$
Déjà là, je coince un peu, surtout au niveau de la définition. On fait un développement limité des fonctions $e^{x}$ et $e^{-x}$ d'ordre 2 au point 0, mais en fait je n'arrive pas à me représenter pourquoi on peut approximer le reste par $O(x^{2})$.

Ensuite le corrigé dit que $2x + O(x^{2}) \subseteq O(x)$.

Je ne comprend tout simplement pas pourquoi. Merci d'avance et bonne soirée!
woodoo
Kilo-utilisateur
 
Messages: 125
Inscription: Lundi 12 Novembre 2012, 20:13
Statut actuel: Post-bac | Licence

Publicité

Re: Notations de Landau

Messagepar balf » Jeudi 30 Mai 2013, 23:25

On devrait mettre +O(x³), et non O(x²), ce qui n'apporte rien puisque x² est O(x²). Cela vient de la formule de Taylor-Lagrange (ou de l'inégalité de Taylor-Lagrange pour le reste).

Pour la deuxième question, c'est tout simplement parce que 2x $\in$ O(x) par définition, que O( x²)$\subset$ O(x) (si |x| < 1, x² < |x|), et enfin que O(x) + O(x) = O(x).

B.A.
balf
Zetta-utilisateur
 
Messages: 3847
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Notations de Landau

Messagepar woodoo » Vendredi 31 Mai 2013, 18:07

balf a écrit:On devrait mettre +O(x³), et non O(x²), ce qui n'apporte rien puisque x² est O(x²).


Puisqu'on évalue $e^{x}$ au point 0, et bien dans ce cas $O(x^{3}) \in O(x^{2})$, non?

Sinon merci beaucoup, pour votre réponse!

Bonne soirée!
woodoo
Kilo-utilisateur
 
Messages: 125
Inscription: Lundi 12 Novembre 2012, 20:13
Statut actuel: Post-bac | Licence

Re: Notations de Landau

Messagepar balf » Vendredi 31 Mai 2013, 18:42

Certes, mais aussi x²/2 $\in$ O(x²), de sorte que ce terme n'a pas de sens (le veux dire n'apporte aucune information), et qu'on devrait donc écrire simplement e$^{\mathsf x}$ = 1 + x + O(x²). Retour à l'étage en dessous.

B.A.
balf
Zetta-utilisateur
 
Messages: 3847
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Notations de Landau

Messagepar kojak » Vendredi 31 Mai 2013, 19:37

Bonjour,

C'est pour ça que je n’aime pas ces notations de Landau : je préfère de loin les $x^n \varepsilon(x)$ comme ça, on sait ce qu'on manipule. Une fois qu'on a bien compris ceci, on peut éventuellement passer ensuite aux notations de Landau.

PS : fais tu bien la différence entre le petit $o$, $o(x^2)$ et un grand $O$, $O(x^2)$ ?
pas d'aide par MP
kojak
Modérateur
 
Messages: 10403
Inscription: Samedi 18 Novembre 2006, 19:50
Statut actuel: Actif et salarié | Enseignant

Re: Notations de Landau

Messagepar woodoo » Dimanche 02 Juin 2013, 07:59

balf a écrit:Certes, mais aussi x²/2 $\in$ O(x²), de sorte que ce terme n'a pas de sens (le veux dire n'apporte aucune information), et qu'on devrait donc écrire simplement e$^{\mathsf x}$ = 1 + x + O(x²). Retour à l'étage en dessous.


D'accord, merci beaucoup!

kojak a écrit:Bonjour,

C'est pour ça que je n’aime pas ces notations de Landau : je préfère de loin les $x^n \varepsilon(x)$ comme ça, on sait ce qu'on manipule. Une fois qu'on a bien compris ceci, on peut éventuellement passer ensuite aux notations de Landau.

PS : fais tu bien la différence entre le petit $o$, $o(x^2)$ et un grand $O$, $O(x^2)$ ?


Je dois avouer que la notation $x^n \varepsilon(x)$ ne m'évoque pas grand chose. Si on l'a vue en classe, on ne l'a pas utilisée en exercices. Quant aux notations de Landau, je ne les ai pas assez utilisées pour les avoir bien comprises. Je connais les définitions de $o(x)$ et $O(x)$, mais la différence me paraît toujours floue. Je n'ai pas fait assez d'exercices pour saisir complètement les différences.
woodoo
Kilo-utilisateur
 
Messages: 125
Inscription: Lundi 12 Novembre 2012, 20:13
Statut actuel: Post-bac | Licence

Re: Notations de Landau

Messagepar balf » Dimanche 02 Juin 2013, 09:26

f(x)=o(x) : le rapport f(x)/x tend vers 0 quand x tend vers 0. En gros, f(x) tend vers 0 « incomparablement » plus vite que x. Ex. x², x³, x √x, &c.
f(x)=O(x) ce rapport, en valeur absolue, est borné dans un voisinage de 0. Il est plus précis de savoir que f(x) est O(x²) que de savoir qu'il est o(x).

B.A.
balf
Zetta-utilisateur
 
Messages: 3847
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence

Re: Notations de Landau

Messagepar woodoo » Dimanche 02 Juin 2013, 14:37

Ah d'accord je pense que je vois mieux la différence!

balf a écrit:f(x)=o(x) : le rapport f(x)/x tend vers 0 quand x tend vers 0.


Je ne me trompe pas en disant que cette définition (et celle de $O$ aussi) est généralisable à n'importe quel point?
woodoo
Kilo-utilisateur
 
Messages: 125
Inscription: Lundi 12 Novembre 2012, 20:13
Statut actuel: Post-bac | Licence

Re: Notations de Landau

Messagepar balf » Dimanche 02 Juin 2013, 15:17

Oui, mais on dit que f(x) est o(x — a) ou O(x —a) au voisinage de a. Ce peut aussi être au voisinage de l'infini ; ce cas sert souvent pour décrire la complexité d'un algorithme — n étant la taille des données, on parle d'algorithme dont la complexité est en O(n²) ou en O(n log n), par exemple.

B.A.
balf
Zetta-utilisateur
 
Messages: 3847
Inscription: Mercredi 02 Janvier 2008, 23:18
Statut actuel: Actif et salarié | Maître de conférence


Retourner vers Exercices et problèmes : Supérieur

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 4 invités