Page 1 sur 1

Notations de Landau

MessagePosté: Jeudi 30 Mai 2013, 22:04
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!

Re: Notations de Landau

MessagePosté: Jeudi 30 Mai 2013, 23:25
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.

Re: Notations de Landau

MessagePosté: Vendredi 31 Mai 2013, 18:07
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!

Re: Notations de Landau

MessagePosté: Vendredi 31 Mai 2013, 18:42
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.

Re: Notations de Landau

MessagePosté: Vendredi 31 Mai 2013, 19:37
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)$ ?

Re: Notations de Landau

MessagePosté: Dimanche 02 Juin 2013, 07:59
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.

Re: Notations de Landau

MessagePosté: Dimanche 02 Juin 2013, 09:26
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.

Re: Notations de Landau

MessagePosté: Dimanche 02 Juin 2013, 14:37
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?

Re: Notations de Landau

MessagePosté: Dimanche 02 Juin 2013, 15:17
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.