B. Compléments

B.1 Quelques rappels sur les symboles de Landau

Cette annexe a pour objectif de rappeler quelques propriétés des quatre symboles de Landau : $\mathbf{O}\left(f\right)$, $\mathrm{o}\left(f\right)$, $\sim$ et $\Theta$.

Remark B.1.1   Les notations de Landau (qui se sont imposées comme standard de fait) ne sont pourtant pas des plus heureuses. En effet les deux relations $g_{1}=f+\mathrm{o}\left(f\right)$ et $g_{2}=f+\mathrm{o}\left(f\right)$ n'impliquent pas que $g_{1}=g_{2}$. Il vaut mieux les lire et les comprendre comme $g_{1}-f\in\mathrm{o}\left(f\right)$ et $g_{2}-f\in\mathrm{o}\left(f\right)$, avec pour conséquence $g_{2}-g_{1}\in\mathrm{o}\left(f\right)$.

Definition B.1.2 (equivalence)   La relation "$f\sim g$ quand $x\rightarrow0$" est définie par :

$$\forall x\,:\,\left(f\left(x\right)=0\,\Leftrightarrow\, g\left(x... ...ht)}{g\left(x\right)}\right/\mid x\rightarrow0,\, f\left(x\right)\neq0\right]=1$$

Exercise B.1.3   Quelles sont les fonctions telles que $f\sim0$ ?

Exercise B.1.4   Montrer que la définition de $f\sim g$ équivaut à l'existence d'une fonction $q$ telle que $f\left(x\right)=g\left(x\right)\times q\left(x\right)$ avec $q\left(x\right)\rightarrow1$.

Definition B.1.5   Une relation d'équivalence est une relation réflexive, symétrique et transitive, i.e. :

$$R\,: \forall x x\sim x$$

$$S\,: \forall x,\, y x\sim y\,\implies y\sim x$$

$$T\,: \forall x,\, y,\, z \left(x\sim y\,\mathrm{et}\, y\sim z\right)\implies x\sim z$$

Definition B.1.6   Dire qu'une relation d'équivalence est compatible avec une opération $\perp$ est :

$$\left(a\sim c\,\mathrm{et}\, b\sim d\right)\implies\left(a\perp b\,\sim\, c\perp d\right)$$

Autrement dit, on peut remplacer des équivalents par des équivalents.

Theorem B.1.7   La relation $\sim$ est une équivalence, et elle est compatible avec le produit.

Definition B.1.8 (grand O)   Définition $\mathbf{O}\left(f\right)$. La relation "$f$ contrôle $g$", notée $g\in\mathbf{O}\left(f\right)$, est définie par l'existence d'un facteur de contrôle, i.e.

$$\forall x\,:\,\left\vert g\left(x\right)\right\vert\leq k\,\left\vert f\left(x\right)\right\vert$$

Exercise B.1.9   Montrer que cette relation est RT, mais pas S.

Definition B.1.10 (même ordre)   On dit que deux fonctions sont du même ordre lorsque $f\in\mathbf{O}\left(g\right)$ et $g\in\mathbf{O}\left(f\right)$. Ceci ce note par $f\,\Theta\, g$.

Exercise B.1.11   Montrer que cette relation est RST, i.e. est une équivalence.

Definition B.1.12   La relation "$g$ est négligeable devant $f$", notée $g\in\mathrm{o}\left(f\right)$, est définie par l'existence d'une fonction de "négligeabilité" $\varepsilon$, i.e.

$$\forall x\,:\, g\left(x\right)=f\left(x\right)\times\varepsilon\left(x\right)\;\mathrm{et}\;\varepsilon\left(x\right)\rightarrow0$$

Exercise B.1.13   Cette relation est elle R, S ou T ?

Theorem B.1.14   Les ensembles $\mathbf{O}\left(f\right)$ et $\mathrm{o}\left(f\right)$ sont clos par combinaisons linéaires.