Notations de Landau

Aide à la résolution d'exercices ou de problèmes de niveau supérieur au baccalauréat.

Modérateur : gdm_sco

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.
woodoo
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 125
Inscription : lundi 12 novembre 2012, 20:13

Notations de Landau

Message par woodoo »

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!

balf
Utilisateur chevronné
Utilisateur chevronné
Messages : 3925
Inscription : mercredi 02 janvier 2008, 23:18

Re: Notations de Landau

Message par balf »

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.

woodoo
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 125
Inscription : lundi 12 novembre 2012, 20:13

Re: Notations de Landau

Message par woodoo »

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!

balf
Utilisateur chevronné
Utilisateur chevronné
Messages : 3925
Inscription : mercredi 02 janvier 2008, 23:18

Re: Notations de Landau

Message par balf »

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.

kojak
Modérateur global
Modérateur global
Messages : 10380
Inscription : samedi 18 novembre 2006, 19:50

Re: Notations de Landau

Message par kojak »

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.

woodoo
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 125
Inscription : lundi 12 novembre 2012, 20:13

Re: Notations de Landau

Message par woodoo »

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.

balf
Utilisateur chevronné
Utilisateur chevronné
Messages : 3925
Inscription : mercredi 02 janvier 2008, 23:18

Re: Notations de Landau

Message par balf »

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.

woodoo
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 125
Inscription : lundi 12 novembre 2012, 20:13

Re: Notations de Landau

Message par woodoo »

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?

balf
Utilisateur chevronné
Utilisateur chevronné
Messages : 3925
Inscription : mercredi 02 janvier 2008, 23:18

Re: Notations de Landau

Message par balf »

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.