Langage de programmation - Mathématiques appliquées

Suites et séries numériques

Les suites numériques et les séries numériques constituent des notions fondamentales des mathématiques appliquées et de l'informatique. Une suite permet de représenter une succession ordonnée de valeurs, tandis qu'une série correspond à l'addition progressive des termes d'une suite. Ces deux concepts apparaissent dans l'analyse des algorithmes, les méthodes numériques, les probabilités, les simulations, les calculs financiers, le traitement du signal et l'étude des phénomènes évoluant par étapes.

En programmation, une suite peut être produite par une boucle, une relation de récurrence, une formule explicite ou un générateur. Elle peut représenter les valeurs successives d'un calcul, les résultats d'une simulation, les mesures d'un phénomène ou les états d'un algorithme. Une série peut servir à approximer une fonction, à calculer une somme infinie, à analyser une erreur numérique ou à déterminer la convergence d'un processus.

L'étude des suites et des séries permet de comprendre comment une quantité évolue lorsque son indice augmente. Elle introduit notamment les notions de limite, de convergence, de divergence, de monotonie, de bornes, de sommes partielles et de vitesse de convergence.

Suite numérique

Une suite numérique est une fonction définie sur les entiers naturels et prenant ses valeurs dans un ensemble numérique.

Une suite réelle peut être décrite par :

u : ℕ → ℝ

À chaque entier naturel n, la suite associe un nombre réel :

u(n) = u_n

Les valeurs :

u₀, u₁, u₂, u₃, ...

sont appelées les termes de la suite.

L'entier n est appelé l'indice du terme.

Notation

Une suite est généralement notée :

(u_n)

ou :

(u_n)_n∈ℕ

Le terme d'indice n est noté :

u_n

Par exemple :

u_n = 2n + 1

définit la suite :

1, 3, 5, 7, 9, ...

si l'indexation commence à :

n = 0

La convention d'indexation doit toujours être précisée, car certaines suites commencent à 0 et d'autres à 1.

Définition explicite

Une suite possède une définition explicite lorsque son terme général peut être calculé directement à partir de son indice.

Par exemple :

u_n = n²

donne :

u₀ = 0
u₁ = 1
u₂ = 4
u₃ = 9
u₄ = 16

La formule explicite permet de calculer n'importe quel terme sans devoir calculer les termes précédents.

Définition par récurrence

Une suite est définie par récurrence lorsqu'un terme dépend d'un ou de plusieurs termes précédents.

Par exemple :

u₀ = 2

et :

u_n+1 = u_n + 3

Cette définition produit :

2, 5, 8, 11, 14, ...

Pour calculer u₄, il faut normalement connaître les termes précédents, sauf si une formule explicite équivalente est trouvée.

Suite finie

Une suite est finie lorsqu'elle contient un nombre limité de termes.

Par exemple :

3, 6, 9, 12

peut être décrite comme une suite définie pour :

0 ≤ n ≤ 3

En programmation, les suites sont souvent représentées par des tableaux ou des listes de taille finie.

Suite infinie

Une suite est infinie lorsqu'elle est définie pour une quantité illimitée d'indices.

Par exemple :

1, 1/2, 1/3, 1/4, ...

est une suite infinie définie par :

u_n = 1/(n+1)

Une suite infinie ne peut pas être entièrement stockée en mémoire. Elle doit être décrite par une règle de calcul ou produite progressivement.

Suite arithmétique

Une suite arithmétique est une suite dans laquelle la différence entre deux termes consécutifs est constante.

Cette constante est appelée la raison arithmétique.

La relation de récurrence est :

u_n+1 = u_n + r

où r représente la raison.

Par exemple :

2, 5, 8, 11, 14, ...

est une suite arithmétique de raison :

r = 3

Terme général d'une suite arithmétique

Si le premier terme est :

u₀

alors :

u_n = u₀ + nr

Si l'indexation commence à 1, on écrit généralement :

u_n = u₁ + (n-1)r

Par exemple, pour :

u₀ = 2

et :

r = 3

on obtient :

u_n = 2 + 3n

Ainsi :

u₄ = 2 + 3 × 4 = 14

Somme d'une suite arithmétique

La somme des termes allant de u_{0 à u_n est :}

S_n =
(n+1)(u₀+u_n)/2

Si la suite commence à u₁, la somme des n premiers termes est :

S_n =
n(u₁+u_n)/2

On peut également écrire :

S_n =
n(2u_{1_+(n-1)r)/2}

Exemple de somme arithmétique

Considérons :

1 + 2 + 3 + ... + 100

Il s'agit d'une suite arithmétique dont :

u₁ = 1
u₁₀₀ = 100
n = 100

La somme vaut :

S₁₀₀ =
100(1+100)/2

soit :

S₁₀₀ = 5050

Suite géométrique

Une suite géométrique est une suite dans laquelle chaque terme est obtenu en multipliant le terme précédent par une constante.

Cette constante est appelée la raison géométrique.

La relation de récurrence est :

u_n+1 = q × u_n

où q représente la raison.

Par exemple :

3, 6, 12, 24, 48, ...

est une suite géométrique de raison :

q = 2

Terme général d'une suite géométrique

Si la suite commence à l'indice 0, alors :

u_{n = u₀qⁿ}

Si elle commence à l'indice 1, on utilise :

u_n = u₁q^n-1

Par exemple, pour :

u₀ = 3

et :

q = 2

on obtient :

u_n = 3 × 2ⁿ

Ainsi :

u₄ = 3 × 2⁴ = 48

Somme d'une suite géométrique finie

Pour :

q ≠ 1

la somme :

u₀ + u₁ + ... + u_n

vaut :

S_n =
u₀(1-qⁿ⁺¹)/(1-q)

Une forme équivalente est :

S_n =
u₀(qⁿ⁺¹-1)/(q-1)

Lorsque :

q = 1

tous les termes sont égaux et :

S_n = (n+1)u₀

Exemple de somme géométrique

Considérons :

1 + 2 + 4 + 8 + 16

On a :

u₀ = 1
q = 2
n = 4

La somme vaut :

S₄ =
(1-2⁵)/(1-2)

soit :

S₄ = 31

Suite constante

Une suite est constante lorsque tous ses termes possèdent la même valeur.

Elle est définie par :

u_n = c

pour tout n.

Par exemple :

5, 5, 5, 5, ...

est une suite constante.

Une suite constante est à la fois arithmétique de raison **0** et géométrique de raison **1**, sauf dans certains cas particuliers liés au terme nul.

Suite croissante

Une suite est croissante lorsque :

u_n+1 ≥ u_n

pour tout indice considéré.

Elle est strictement croissante lorsque :

u_n+1 > u_n

Par exemple :

1, 2, 4, 7, 11, ...

est strictement croissante.

Une suite croissante peut contenir des termes égaux si elle n'est pas strictement croissante.

Suite décroissante

Une suite est décroissante lorsque :

u_n+1 ≤ u_n

Elle est strictement décroissante lorsque :

u_n+1 < u_n

Par exemple :

1, 1/2, 1/3, 1/4, ...

est strictement décroissante.

Les suites croissantes et décroissantes sont regroupées sous le terme de suites monotones.

Suite monotone

Une suite est monotone lorsqu'elle est entièrement croissante ou entièrement décroissante.

Elle peut être :

croissante ;
strictement croissante ;
décroissante ;
strictement décroissante.

Les suites monotones sont importantes dans l'étude de la convergence, car une suite monotone et bornée est convergente.

Suite majorée

Une suite est majorée lorsqu'il existe un nombre M tel que :

u_n ≤ M

pour tout n.

Le nombre M est appelé un majorant.

Par exemple :

u_n = 1 - 1/(n+1)

est majorée par :

Suite minorée

Une suite est minorée lorsqu'il existe un nombre m tel que :

u_n ≥ m

pour tout n.

Le nombre m est appelé un minorant.

Par exemple :

u_n = 1/(n+1)

est minorée par :

Suite bornée

Une suite est bornée lorsqu'elle est à la fois majorée et minorée.

Il existe donc deux nombres m et M tels que :

m ≤ u_n ≤ M

pour tout n.

Une définition équivalente consiste à dire qu'il existe une constante positive K telle que :

|u_n| ≤ K

Limite d'une suite

Une suite u_n converge vers une limite L lorsque ses termes deviennent aussi proches que souhaité de L lorsque n devient grand.

On écrit :

lim u_n = L
n→∞

ou :

u_n → L

Par exemple :

u_n = 1/n

converge vers :

On écrit :

lim 1/n = 0
n→∞

Définition formelle de la convergence

Une suite u_n converge vers L si, pour tout nombre positif ε, il existe un entier N tel que :

n ≥ N

implique :

|u_n-L| < ε

Cette définition signifie qu'à partir d'un certain indice, tous les termes sont contenus dans un intervalle arbitrairement petit autour de L.

Unicité de la limite

Une suite convergente possède une seule limite.

Elle ne peut pas converger simultanément vers deux nombres distincts.

Cette propriété permet de déterminer une limite en utilisant différentes méthodes sans ambiguïté.

Suite divergente

Une suite est divergente lorsqu'elle ne possède pas de limite réelle finie.

Plusieurs comportements sont possibles :

elle tend vers l'infini ;
elle tend vers moins l'infini ;
elle oscille ;
elle présente un comportement irrégulier.

Par exemple :

u_n = n

diverge vers :

+∞

Divergence par oscillation

La suite :

u_n = (-1)ⁿ

produit :

1, -1, 1, -1, ...

Elle ne se rapproche d'aucune valeur unique.

Elle est donc divergente par oscillation.

Elle reste toutefois bornée entre :

-1

et :

Une suite bornée n'est donc pas nécessairement convergente.

Théorème de convergence monotone

Toute suite croissante et majorée est convergente.

De même, toute suite décroissante et minorée est convergente.

Ce résultat est souvent appelé le théorème de convergence monotone.

Il fournit un moyen de démontrer la convergence sans connaître immédiatement la valeur exacte de la limite.

Opérations sur les limites

Si :

u_n → a

et :

v_n → b

alors :

u_n + v_n → a+b

u_n - v_n → a-b

u_nv_n → ab

Si :

b ≠ 0

et si v_n ne s'annule pas à partir d'un certain rang :

u_n/v_n → a/b

Ces règles permettent de calculer de nombreuses limites à partir de limites connues.

Limites classiques

Quelques limites courantes sont :

lim 1/n = 0
n→∞

lim 1/n^p = 0
n→∞

pour :

p > 0

lim qⁿ = 0
n→∞

lorsque :

|q| < 1

et :

lim (1+1/n)ⁿ = e
n→∞

Comparaison des croissances

Lorsque n devient grand, plusieurs fonctions possèdent des vitesses de croissance différentes.

Un ordre classique est :

1
«
log n
«
n^a
«
bⁿ
«
n!

pour :

a > 0

et :

b > 1

Cette comparaison est fondamentale en analyse asymptotique et dans l'étude de la complexité des algorithmes.

Suite définie par une moyenne

Certaines suites sont définies par une opération de moyenne.

Par exemple :

u_n+1 =
(u_n + a/u_n)/2

Cette relation est utilisée dans la méthode de Héron pour approximer :

√a

Sous certaines conditions, la suite converge rapidement vers la racine carrée recherchée.

Exemple de méthode de Héron

Pour calculer :

√2

on peut choisir :

u₀ = 1

puis appliquer :

u_n+1 =
(u_n + 2/u_n)/2

On obtient approximativement :

u₀ = 1
u₁ = 1,5
u₂ = 1,416666...
u₃ = 1,414215...
u₄ = 1,414213...

La suite converge vers :

√2

Algorithme de génération d'une suite explicite

MODULE GénérerSuite(n)

   Créer tableau u[0..n]

   POUR i ← 0 JUSQU'A n
      u[i] ← i × i
   FIN POUR

   RETOURNER u

Cet algorithme génère les premiers termes de la suite :

u_i = i²

Sa complexité temporelle est :

O(n)

et sa mémoire est :

O(n)

si tous les termes sont conservés.

Algorithme de génération par récurrence

MODULE GénérerSuiteArithmétique(premier,raison,n)

   Créer tableau u[0..n]

   u[0] ← premier

   POUR i ← 1 JUSQU'A n
      u[i] ← u[i-1] + raison
   FIN POUR

   RETOURNER u

Cet algorithme produit une suite arithmétique sans recalculer chaque terme par une multiplication.

Générateur paresseux

Une suite infinie peut être produite par un générateur paresseux.

Le générateur calcule un terme uniquement lorsqu'il est demandé.

MODULE GénérateurEntiers()
   n ← 0
   BOUCLE INFINIE
      PRODUIRE n
      n ← n + 1
   FIN BOUCLE

Cette approche évite de stocker une quantité infinie de valeurs.

Elle est utilisée dans les itérateurs, les flux et la programmation fonctionnelle.

Exemple en Java

L'exemple suivant génère les premiers termes d'une suite arithmétique :


import java.util.Arrays;
 
public class SuitesSample {
 
    public static long[] suiteArithmetique(
        long premier,
        long raison,
        int nombreDeTermes
    ) {
        if (nombreDeTermes < 0) {
            throw new IllegalArgumentException(
                "Le nombre de termes doit être positif ou nul."
            );
        }
 
        long[] resultat =
            new long[nombreDeTermes];
 
        if (nombreDeTermes == 0) {
            return resultat;
        }
 
        resultat[0] = premier;
 
        for (int i = 1; i < nombreDeTermes; i++) {
            resultat[i] =
                resultat[i - 1] + raison;
        }
 
        return resultat;
    }
 
    public static void main(String[] args) {
        long[] valeurs =
            suiteArithmetique(2, 3, 6);
 
        System.out.println(
            Arrays.toString(valeurs)
        );
    }
}

Le programme affiche :

[2, 5, 8, 11, 14, 17]

Série numérique

Une série numérique est obtenue en additionnant les termes d'une suite.

À partir de la suite :

u₀, u₁, u₂, ...

on forme la série :

u₀ + u₁ + u₂ + ...

Elle est notée :

∑_n=0∞ u_n

Une série infinie n'est pas interprétée comme une addition effectuée en une seule étape. Elle est étudiée à travers la suite de ses sommes partielles.

Somme partielle

La somme partielle d'ordre N est définie par :

S_N =
∑_n=0^N u_n

soit :

S_N =
u₀ + u₁ + ... + u_N

La série converge lorsque la suite des sommes partielles S_N converge vers une limite finie.

Convergence d'une série

La série :

∑_n=0∞ u_n

converge vers S lorsque :

lim S_N = S
N→∞

On écrit alors :

∑_n=0∞ u_n = S

La valeur S est appelée la somme de la série.

Si les sommes partielles ne possèdent pas de limite finie, la série diverge.

Condition nécessaire de convergence

Si la série :

∑ u_n

converge, alors :

u_n → 0

Cette condition est nécessaire, mais elle n'est pas suffisante.

Par exemple, dans la série harmonique :

∑_n=1∞ 1/n

les termes tendent vers zéro, mais la série diverge.

Série géométrique infinie

La série géométrique :

a + aq + aq² + aq³ + ...

est notée :

∑_n=0∞ aqⁿ

Elle converge si :

|q| < 1

Sa somme est alors :

a/(1-q)

Si :

|q| ≥ 1

la série diverge, sauf certains cas particuliers triviaux comme a = 0.

Exemple de série géométrique

Considérons :

1 + 1/2 + 1/4 + 1/8 + ...

On a :

a = 1
q = 1/2

La somme vaut :

1/(1-1/2)

donc :

Ainsi :

1 + 1/2 + 1/4 + 1/8 + ... = 2

Série harmonique

La série harmonique est :

1 + 1/2 + 1/3 + 1/4 + ...

ou :

∑_n=1∞ 1/n

Elle diverge, bien que ses termes tendent vers zéro.

Ses sommes partielles sont les nombres harmoniques :

H_N =
∑_n=1^N 1/n

Leur croissance est approximativement logarithmique :

H_N ≈ ln(N) + γ

Série de Riemann

Une série de Riemann, également appelée p-série, est de la forme :

∑_n=1∞ 1/n^p

Elle converge si :

p > 1

Elle diverge si :

p ≤ 1

Par exemple :

∑ 1/n²

converge, tandis que :

∑ 1/n

diverge.

Série alternée

Une série alternée possède des termes dont les signes alternent.

Elle peut prendre la forme :

u₀ - u₁ + u₂ - u₃ + ...

ou :

∑_n=0∞ (-1)ⁿu_n

Un exemple classique est :

1 - 1/2 + 1/3 - 1/4 + ...

Cette série converge vers :

ln(2)

Critère des séries alternées

Une série alternée :

∑ (-1)ⁿu_n

converge si, à partir d'un certain rang :

les termes u_n sont positifs ;
la suite u_n est décroissante ;
u_n tend vers zéro.

Ce résultat est appelé le critère de Leibniz.

Convergence absolue

Une série :

∑ u_n

est absolument convergente lorsque :

∑ |u_n|

converge.

Toute série absolument convergente est convergente.

La réciproque n'est pas toujours vraie.

Convergence conditionnelle

Une série est conditionnellement convergente lorsqu'elle converge, mais que la série des valeurs absolues diverge.

Par exemple :

1 - 1/2 + 1/3 - 1/4 + ...

converge, tandis que :

1 + 1/2 + 1/3 + 1/4 + ...

diverge.

La série harmonique alternée est donc conditionnellement convergente.

Critère de comparaison

Supposons que :

0 ≤ u_n ≤ v_n

à partir d'un certain indice.

Alors :

si ∑v_n converge, ∑u_n converge ;
si ∑u_n diverge, ∑v_n diverge.

Ce critère permet de comparer une série inconnue à une série de référence.

Critère de comparaison par équivalence

Si :

u_n/v_n → 1

et si les termes sont positifs à partir d'un certain rang, alors les séries :

∑u_n

et :

∑v_n

possèdent la même nature.

Elles convergent toutes les deux ou divergent toutes les deux.

Critère du rapport

Pour une série à termes positifs, on peut étudier :

L =
lim |u_n+1/u_n|

Si :

L < 1

la série converge absolument.

Si :

L > 1

ou si la limite est infinie, la série diverge.

Si :

L = 1

le critère ne permet pas de conclure.

Critère de la racine

On peut également calculer :

L =
lim ⁿ√|u_n|

Si :

L < 1

la série converge absolument.

Si :

L > 1

la série diverge.

Si :

L = 1

le critère est indéterminé.

Critère intégral

Si une fonction f est positive, continue et décroissante à partir d'une certaine valeur, alors la série :

∑ f(n)

et l'intégrale impropre :

∫ f(x)dx

possèdent généralement la même nature.

Ce critère permet notamment de démontrer le comportement des p-séries.

Reste d'une série

Si une série converge vers S, le reste après N termes est :

R_N =
S - S_N

Il représente l'erreur commise lorsqu'on remplace la somme infinie par la somme partielle.

L'estimation du reste est essentielle en calcul numérique.

Reste d'une série géométrique

Pour une série géométrique convergente :

∑_n=0∞ aqⁿ

le reste après le terme d'indice N vaut :

R_N =
aq^N+1/(1-q)

Cette formule permet de déterminer combien de termes doivent être calculés pour atteindre une précision donnée.

Reste d'une série alternée

Pour une série alternée satisfaisant le critère de Leibniz, l'erreur commise en s'arrêtant au terme d'indice N est inférieure ou égale à la valeur absolue du premier terme omis.

On a :

|R_N| ≤ u_N₊₁

Cette propriété rend les séries alternées utiles pour les approximations numériques.

Séries entières

Une série entière est une série de la forme :

∑_n=0∞ a_n(x-c)ⁿ

où :

a_n représente les coefficients ;
c représente le centre de la série ;
x représente la variable.

Les fonctions génératrices ordinaires sont des séries entières centrées en zéro.

Rayon de convergence

Une série entière converge généralement dans un intervalle déterminé par un rayon R.

Elle converge pour :

|x-c| < R

et diverge pour :

|x-c| > R

Le comportement aux extrémités doit être étudié séparément.

Séries de Taylor

Une fonction suffisamment régulière peut être représentée autour d'un point a par une série de Taylor :

f(x) =
∑_n=0∞
f⁽ⁿ⁾(a)/n!
×
(x-a)ⁿ

Lorsque :

a = 0

on parle de série de Maclaurin.

Ces séries permettent d'approximer des fonctions par des polynômes.

Développements classiques

Quelques développements de Maclaurin sont :

e^x =
1 + x + x²/2! + x³/3! + ...

sin(x) =
x - x³/3! + x⁵/5! - ...

cos(x) =
1 - x²/2! + x⁴/4! - ...

1/(1-x) =
1 + x + x² + x³ + ...

pour les valeurs de **x** appartenant à leurs domaines de convergence respectifs.

Approximation de l'exponentielle

L'exponentielle peut être approximée par :

e^x ≈
∑_n=0^N xⁿ/n!

Un algorithme naïf pourrait recalculer chaque puissance et chaque factorielle.

Une méthode plus efficace calcule chaque terme à partir du précédent :

terme₀ = 1

et :

terme_n =
terme_n-1 × x/n

Algorithme d'approximation de l'exponentielle

MODULE Exponentielle(x,N)
   somme ← 1
   terme ← 1

   POUR n ← 1 JUSQU'A N
      terme ← terme × x / n
      somme ← somme + terme
   FIN POUR

   RETOURNER somme

Cette méthode évite de recalculer les puissances et les factorielles depuis le début.

Sa complexité temporelle est :

O(N)

et sa mémoire supplémentaire est :

O(1)

Exemple en Java


public class SeriesSample {
 
    public static double exponentielle(
        double x,
        int nombreTermes
    ) {
        if (nombreTermes < 1) {
            throw new IllegalArgumentException(
                "Le nombre de termes doit être positif."
            );
        }
 
        double somme = 1.0;
        double terme = 1.0;
 
        for (int n = 1; n < nombreTermes; n++) {
            terme *= x / n;
            somme += terme;
        }
 
        return somme;
    }
 
    public static void main(String[] args) {
        double approximation =
            exponentielle(1.0, 15);
 
        System.out.println(
            "Approximation de e : "
            + approximation
        );
 
        System.out.println(
            "Valeur Java : "
            + Math.exp(1.0)
        );
    }
}

Le résultat obtenu se rapproche de :

2,718281828...

Critère d'arrêt basé sur la précision

Dans un calcul numérique, il est parfois préférable d'arrêter la sommation lorsque le terme ajouté devient suffisamment petit.

MODULE SommeJusquÀPrécision(epsilon)

   somme ← 0
   n ← 1

   RÉPÉTER
      terme ← 1/(n×n)
      somme ← somme + terme
      n ← n + 1
   JUSQU'À |terme| < epsilon

   yRETOURNER somme

Cette méthode adapte le nombre d'itérations à la précision demandée.

Il faut toutefois vérifier que le terme constitue une estimation valable de l'erreur restante.

Accumulation des erreurs d'arrondi

Lorsqu'une série est calculée en virgule flottante, les erreurs d'arrondi peuvent s'accumuler.

Les petits termes peuvent perdre leur contribution lorsqu'ils sont ajoutés à une somme beaucoup plus grande.

Par exemple, l'addition :

grandeValeur + trèsPetiteValeur

peut produire exactement :

grandeValeur

si la petite valeur est inférieure à la précision du type numérique.

Ordre de sommation

Pour une série de termes positifs, il est généralement préférable d'additionner d'abord les termes de plus petite valeur.

Une sommation décroissante peut ainsi être plus précise qu'une sommation croissante.

Cependant, pour les séries comportant des signes différents, l'ordre de sommation peut avoir des effets plus complexes.

Dans le cas d'une série conditionnellement convergente, une réorganisation des termes peut même modifier la somme ou provoquer une divergence.

Sommation de Kahan

La sommation de Kahan est une méthode permettant de réduire les erreurs numériques.

Elle conserve une variable de compensation représentant une partie de l'erreur perdue lors des additions précédentes.

MODULE SommeKahan(valeurs)

   somme ← 0
   correction ← 0

   POUR CHAQUE valeur DANS valeurs

      y ← valeur - correction
      temporaire ← somme + y

      correction ← (temporaire-somme)-y

      somme ← temporaire

   FIN POUR

   RETOURNER somme

Cette méthode améliore la précision sans modifier la complexité asymptotique.

Suites et complexité algorithmique

Les suites apparaissent fréquemment dans l'analyse des algorithmes.

Par exemple, le nombre d'opérations d'une boucle peut former une suite :

1, 2, 3, ..., n

La somme correspondante est :

n(n+1)/2

et possède une croissance :

θ(n²)

De même, la suite :

n, n/2, n/4, n/8, ...

forme une progression géométrique dont la somme est de l'ordre de :

θ(n)

Boucle à croissance géométrique

Considérons :

i ← 1

TANT QUE i ≤ n
Traitement
i ← i × 2
FIN TANT QUE

Les valeurs de i forment la suite :

1, 2, 4, 8, ...

Le nombre d'itérations est approximativement :

log₂(n)

La complexité temporelle est donc :

O(log n)

Boucles imbriquées et séries

Considérons :

POUR i ← 1 JUSQU'A n
   POUR j ← 1 JUSQU'A i
      Traitement
   FIN POUR
FIN POUR

Le nombre total d'exécutions est :

1 + 2 + 3 + ... + n

soit :

n(n+1)/2

La complexité est donc :

O(n²)

Séries et méthodes numériques

Les séries servent à approximer de nombreuses fonctions :

exponentielle ;
logarithme ;
sinus ;
cosinus ;
fonctions hyperboliques ;
fonctions spéciales ;
solutions d'équations différentielles.

Elles sont également utilisées pour :

estimer des intégrales ;
résoudre des équations ;
approximer des probabilités ;
analyser les erreurs ;
produire des développements asymptotiques.

Suites dans les simulations

Une simulation produit souvent une suite d'états :

état₀,
état₁,
état₂,
...

Chaque nouvel état dépend du précédent :

état_n+1 =
Transition(état_n)

Ce modèle apparaît dans :

les automates cellulaires ;
les simulations physiques ;
les modèles économiques ;
les systèmes dynamiques ;
les chaînes de Markov ;
les jeux et animations.

Suites périodiques

Une suite est périodique lorsqu'il existe un entier positif p tel que :

u_n+p = u_n

pour tout indice suffisamment grand ou pour tout indice du domaine.

Le plus petit entier positif satisfaisant cette propriété est appelé la période.

Par exemple :

1, 0, -1, 0, 1, 0, -1, 0, ...

est périodique de période :

Suite ultimement périodique

Une suite est ultimement périodique lorsqu'elle devient périodique après un certain nombre de termes.

Par exemple :

2, 5, 7, 1, 3, 1, 3, 1, 3, ...

devient périodique après les premiers termes.

Les suites calculées modulo un entier sont souvent ultimement périodiques lorsqu'elles sont produites par un système déterministe à nombre fini d'états.

Sous-suite

Une sous-suite est obtenue en sélectionnant certains termes d'une suite tout en conservant leur ordre.

Si :

n₀ < n₁ < n₂ < ...

alors :

u_n0, u_n1, u_n2, ...

forme une sous-suite.

Par exemple, les termes d'indices pairs :

u₀, u₂, u₄, ...

forment une sous-suite.

Valeur d'adhérence

Une valeur d'adhérence est une limite atteinte par au moins une sous-suite.

Pour :

u_n = (-1)ⁿ

les sous-suites d'indices pairs convergent vers :

et celles d'indices impairs convergent vers :

-1

La suite possède donc deux valeurs d'adhérence, mais elle ne converge pas.

Suite de Cauchy

Une suite est une suite de Cauchy lorsque ses termes deviennent arbitrairement proches les uns des autres.

Pour tout :

ε > 0

il existe un entier N tel que :

m ≥ N

et :

n ≥ N

impliquent :

|u_n-u_m| < ε

Dans l'ensemble des nombres réels, une suite converge si et seulement si elle est de Cauchy.

Comparaison des principales suites

Type de suite	Relation ou formule
Constante	u_n = c
Arithmétique	u_n = u₀ + nr
Géométrique	u_n = u₀qⁿ
Harmonique	u_n = 1/n
Fibonacci	F_n = F_n-1 + F_n-2
Factorielle	u_n = n!
Alternée	u_n = (-1)ⁿa_n
Polynômiale	u_n = P(n)
Exponentielle	u_n = aⁿ

Comparaison des séries courantes

Série	Nature
∑qⁿ, avec `	q	<1`	Convergente
∑qⁿ, avec `	q	≥1	Divergente dans le cas général
∑1/n	Divergente
∑1/n^p, avec p>1	Convergente
∑1/n^p, avec p≤1	Divergente
∑(-1)ⁿ/n	Convergente conditionnellement
∑1/n!	Convergente
∑xⁿ/n!	Convergente pour tout réel x

Applications

Les suites et les séries numériques sont utilisées dans de nombreux domaines :

analyse des algorithmes ;
complexité asymptotique ;
calcul scientifique ;
approximation de fonctions ;
méthodes itératives ;
résolution d'équations ;
simulations ;
traitement du signal ;
probabilités ;
statistiques ;
finances ;
physique numérique ;
intelligence artificielle ;
apprentissage automatique ;
génération procédurale ;
analyse d'erreurs.

Avantages

Les suites et les séries présentent plusieurs avantages :

elles permettent de modéliser une évolution discrète ;
elles décrivent naturellement les calculs itératifs ;
elles facilitent l'étude des limites ;
elles permettent d'approximer des fonctions complexes ;
elles interviennent dans l'analyse de complexité ;
elles fournissent des méthodes de contrôle de l'erreur ;
elles permettent de représenter des processus infinis par des calculs finis ;
elles relient les mathématiques discrètes à l'analyse continue.

Limites et précautions

Plusieurs précautions doivent être prises :

la convention d'indexation doit être précisée ;
une suite bornée n'est pas nécessairement convergente ;
le fait que les termes d'une série tendent vers zéro ne garantit pas sa convergence ;
une somme infinie ne peut pas être calculée directement ;
les erreurs d'arrondi peuvent s'accumuler ;
l'ordre de sommation peut influencer le résultat numérique ;
certaines séries convergent très lentement ;
les critères de convergence doivent respecter leurs hypothèses ;
les formules fermées peuvent provoquer des dépassements de capacité ;
les suites infinies doivent être produites de manière paresseuse ou symbolique.

Remarque

Les suites numériques permettent de formaliser une succession de valeurs produites par une formule, une récurrence ou un processus itératif. Les séries numériques étudient l'accumulation de ces valeurs et permettent de déterminer si une somme infinie possède une valeur finie.

En programmation, ces notions apparaissent dans les boucles, les générateurs, les algorithmes récursifs, les simulations et les méthodes d'approximation. Elles sont également indispensables pour comprendre les nombres harmoniques, les nombres de Fibonacci, les fonctions génératrices, les relations de récurrence et l'analyse asymptotique des algorithmes.

Dernière mise à jour : Jeudi, le 16 juillet 2026