Chapitre 4 : Suites numériques et domination

On cherche des moyens pour décrire une suite infinie de nombres.

Exemple de suite : 1 2 4 8 16 32

Definition formelle : suite numérique

Une suite numérique est une application de \(\mathbb{N}\) vers \(\mathbb{R}\)

On peut (entre autres) définir une suite :

On préfère, quand c’est possible, des expressions directes.

Habituellement \(n\) est le nom de la variable.

Suite constante : \(V(n) = 4 ; V : 4\; 4\; 4\; 4\; 4…\)
Suite quadratique : \(H(n) = n^2 = n \times n ; H : 0\; 1\; 4\; 9\; 16\; 25\; 36…\)
Suite factorielle : \(N(n) = n! = n \times (n-1) \times (n-2)… 3 \times 2 \times 1 \;;\;N :1(par\; convention)\; 1\; 2\; 6\; 24\; 120\; 720…\)
Suite geometrique : \(U(n) = 2^n = 2 \times 2 \times 2 \times … \times 2\; ; \; U : 1\; 2\; 8\; 16\; 32…\)
Suite logarithmique : \(K(n) = log_2(n)\; ; \; K : Nan\; 0\; 1\; 1,58…\; 2\; 2,32…\; 2,58…\; 2,80…\; 3…\)
Suite racine carré : \(L(n) = \sqrt{n}\;;\; L : 0\; 1\; 1,41…\; 1,73…\; 2\; 2,23…\; 2,64…\; 2,82…\; 3 …\)

Les algorithmes les plus performants sont ceux dont la complexité croît le plus lentement (\(log_2(n)\))

Soient \((V_n)\) et \((D_n)\) deux suites numériques. On dit que \(D\) domine \(V\) si

\(\exists M \in \mathbb{R}, \exists N_0 \in N, \forall n > N_0, |V_n| \leq M |Dn|\)

Où \(|x|\) represente la valeur absolue de \(x\)

Si la suite \(D\) ne s’annule plus au bout d’un certain terme, on a : \(D\) domine \(V\) si et seulement la suite \(n \rightarrow \frac{(V_n)}{(D_n)}\) est bornée.
Pour 2 suites quelconques, on n’a pas forcément que l’une domine l’autre.

Si \(D\) est une suite on note \(O(D)\) l’ensemble des suites dominées par \(D\).
Si \(U\) est une suite on note \(\Omega(U)\) l’ensemble des suites qui dominent \(U\). (Attention \(\Omega\) signifie autre chose en théorie des nombres)
Par convention on écrit \(U = O(D)\) plutôt que \(U \in O(D)\)
Pour indiquer que \(U\) est dominée par \(D\) on peut écrire \(U<<D\), ou \(U= O(D)\) ou \(D = \Omega(U)\) (ou \(D>>U\)).

Exemple :

\(n = O(n^2)\) \(n<<n^2\)

Soient \(U,V,W\) des suites (quelconques) et \(m\), \(w\) des nombres réels (quelconques) alors :

Si \(U<<V\) et \(V<<W\) alors \(U<<W\)
Si \(U, V<< W\) alors \(mU + V <<W\)
Si pour tout \(n \in \mathbb{N}, |V_n| \leq |m| |W_n|\) alors \(V<<W\)
L’ensemble \(O(1)\) est l’ensemble des suites bornées
L’ensemble \(O(V)\) est égale à l’ensemble \(|V|\). \(O(1)\) (\(= \{(v_n \times U_n)_{(n \in \mathbb{N})} /U\) suite bornée\(\}\))

Remarque : Si \(U, F, W\) sont des suites alors - \(U<<U\) - \(O(U) O(F) = O(F.U)\) - Si \(U<<W\) alors \(U.V<<M.V.\)

Si \(U\) et \(V\) sont des suites et que on a \(U<<V\) et \(V<<U\) on note \(U = \Theta(V)\) (ou \(V = \Theta(U)\) c’est une relation d’équivalence).

Dans la suite la variable est \(n\) et \(a,b,c\) sont des nombres positifs non nuls avec \(c>1\)