Calculatrice de convolution

(a * b)[k] = Σᵢ a[i] × b[k − i] longueur = m + n − 1

a, b

Les deux suites, saisies sous forme de nombres séparés par des points-virgules. Leur ordre n’a pas d’importance — la convolution est commutative, donc échanger les deux champs renvoie un résultat identique. Elles n’ont pas besoin d’avoir la même longueur, et l’une comme l’autre peut contenir des décimales ou des valeurs négatives. Chaque champ accepte jusqu’à deux cents nombres.

k

L’indice du terme en cours de calcul, qui va de 0 à la longueur du résultat moins un. Il n’est pas affiché à côté de chaque valeur, parce qu’une ligne séparée par des virgules a déjà un ordre : le premier nombre est celui d’indice k = 0, le deuxième celui d’indice k = 1. Le tableau de référence ci-dessous écrit les indices en clair pour le couple par défaut, une ligne par indice, et c’est là qu’il faut regarder si ce sont les positions que vous vérifiez.

a[i] × b[k − i]

Un produit de la somme. Pour chaque k, l’indice i parcourt toutes les positions où les deux suites ont un terme, si bien que le nombre de produits additionnés part de un aux extrémités et atteint la longueur de la plus courte des deux suites au milieu. Ce schéma de recouvrement est toute l’idée : une suite glisse devant l’autre et les produits se ramassent colonne par colonne.

Σᵢ

La somme de ces produits, qui forme un terme du résultat. Chaque terme est arrondi à six décimales, et la somme affichée à côté de la ligne est celle des termes arrondis et non des termes exacts — additionner les nombres affichés dans le panneau redonne donc exactement la somme affichée.

m + n − 1

La longueur du résultat, affichée comme une lecture à part entière. Deux suites de trois termes en donnent cinq ; un nombre seul convolé avec une suite de trois termes en donne trois. Ce sont ces termes supplémentaires, au-delà de la plus longue des deux suites, qui font de ce calcul la convolution complète plutôt que la variante qui ne garde que la partie où les suites se recouvrent entièrement.

Cette page sert quand deux suites doivent être combinées en une distribution : le nombre de façons dont deux dés peuvent donner chaque total, l’effet d’une fenêtre de moyenne mobile sur une série, les coefficients du produit de deux polynômes. Quand la question porte sur une seule suite — ses termes, sa somme, sa régularité —, c’est la calculatrice de suites qui y répond, et quand c’est le choix de la fenêtre d’une moyenne mobile qui est en jeu, la calculatrice de moyenne est la page qui la nomme.

1. Un, deux, trois contre quatre, cinq, six

   1. k = 0 : seuls les premiers termes se recouvrent, donc 1 × 4 = 4
   2. k = 1 : 1 × 5 + 2 × 4 = 5 + 8 = 13
   3. k = 2 : 1 × 6 + 2 × 5 + 3 × 4 = 6 + 10 + 12 = 28
   4. k = 3 : 2 × 6 + 3 × 5 = 12 + 15 = 27
   5. k = 4 : seuls les derniers termes se recouvrent, 3 × 6 = 18
   6. Le résultat est 4, 13, 28, 27, 18 et sa somme vaut 90, qui est aussi 6 × 15

   La dernière ligne est la vérification qui rend cette page facile à croire : la somme d’une convolution est toujours le produit des sommes des deux suites, ici 1 + 2 + 3 = 6 face à 4 + 5 + 6 = 15. Cela tombe de l’algèbre, parce que chaque produit du résultat est le produit d’un terme de chaque suite et que chaque couple possible apparaît exactement une fois.

2. Deux dés et la forme de leurs totaux

   1. Un dé a une seule façon de montrer chacune de ses six faces, chaque suite est donc une suite de six uns
   2. Les convoler compte les couples qui donnent chaque total : k = 0 donne 1 × 1 = 1 façon d’obtenir un total de 2
   3. k = 1 donne 1 + 1 = 2 façons d’obtenir un total de 3, et le compte continue de monter
   4. Le maximum vaut 6, au terme du milieu, qui correspond au total de 7
   5. Le résultat est 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1 et sa somme vaut 36

   C’est l’illustration classique du théorème central limite en miniature : deux lois uniformes convolées donnent une loi triangulaire, et y ajouter un troisième dé l’arrondirait encore vers une courbe en cloche. La somme de 36 est aussi la vérification — le produit des deux sommes vaut 6 × 6, soit tous les couples ordonnés de faces, une issue pour chacun.

3. Un nombre seul met toute la suite à l’échelle

   1. Une suite d’un seul terme n’a rien avec quoi se recouvrir : chaque terme du résultat est ce terme multiplié par un terme de l’autre suite
   2. k = 0 : 2 × 1 = 2
   3. k = 1 : 2 × 2 = 4
   4. k = 2 : 2 × 3 = 6
   5. Le résultat est 2, 4, 6 et la somme vaut 12, soit 2 × 6

   Ce cas dégénéré vaut la peine d’être essayé une fois, car il montre que l’image du glissement a un bout : avec une suite de longueur un, il n’y a jamais plus d’un produit à additionner et la convolution se réduit à une multiplication. C’est aussi pourquoi la formule de longueur m + n − 1 donne 1 + 3 − 1 = 3 et rien de plus grand.

Cette page calcule la convolution complète, et uniquement la convolution complète. Les deux variantes qui n’en gardent qu’une partie ne sont pas proposées : celle qui renvoie une suite de la longueur de la plus longue entrée, et celle qui ne renvoie que les positions où les suites se recouvrent entièrement. Ni l’une ni l’autre n’est bien définie pour deux suites de longueur paire, et le résultat complet est celui qui les contient toutes les deux — les variantes courtes en sont des tranches, pas d’autres calculs. Chaque suite peut contenir au plus deux cents termes, et chaque valeur est limitée à un ordre de grandeur de 1 000 000 : c’est une limite d’affichage, car une convolution multiplie puis additionne, si bien que de grands termes sortent de la plage lisible bien avant de faire déborder un nombre en double précision. Chaque terme du résultat est arrondi à six décimales, et la somme annoncée est celle des termes arrondis, de sorte qu’additionner à la main les nombres affichés reproduit la somme affichée et non une valeur légèrement différente. Le résultat est une ligne de nombres séparés par des virgules et il n’est pas localisé : dans cette ligne, la virgule sépare les termes et n’est donc pas le séparateur décimal du français, tandis qu’à l’intérieur d’un nombre le séparateur décimal reste le point, quelle que soit la langue dans laquelle la page est lue — lisez 4, 13, 28 comme trois nombres et non comme un seul nombre décimal. Les positions portent les indices et ne sont pas étiquetées une à une ; le tableau de référence donne les indices en clair pour le couple par défaut.

Comment convoler deux suites à la main ?

Faites glisser une suite devant l’autre et additionnez les produits à chaque position. Avec 1, 2, 3 et 4, 5, 6, le premier terme vaut 1 × 4 = 4, le deuxième 1 × 5 + 2 × 4 = 13, et ainsi de suite jusqu’à 3 × 6 = 18 à l’autre extrémité. Le résultat compte cinq termes, puisque deux suites de trois termes donnent une convolution de longueur 3 + 3 − 1.

Comment vérifier qu’une convolution est juste ?

Additionnez le résultat et comparez-le au produit des sommes des deux suites. Pour 1, 2, 3 face à 4, 5, 6, cela fait 90 face à 6 × 15, et les deux doivent coïncider. La raison est que chaque terme du résultat est une somme de produits deux à deux, et que chaque couple possible formé d’un terme de chaque suite apparaît dans exactement une de ces sommes.

Pourquoi le résultat compte-t-il plus de termes que chaque suite ?

Parce que la convolution complète conserve les positions où les suites ne se recouvrent que partiellement. Avec 1, 2, 3 face à 4, 5, 6, il y a cinq telles positions : une à chaque extrémité, où un seul couple se rencontre, et trois au milieu, où plusieurs se rencontrent. Les deux variantes courtes de l’opération — celle qui garde la longueur de la plus longue entrée et celle qui ne garde que les recouvrements complets — sont l’une et l’autre des tranches de ce résultat.

Quel rapport y a-t-il entre la convolution et la probabilité des dés ?

Elle compte les issues. Un dé seul est une suite de six uns, un par face, et convoler cette suite avec elle-même compte les couples ordonnés qui donnent chaque total : une façon de faire 2, deux façons de faire 3, jusqu’à six façons de faire 7, puis le compte redescend. La somme du résultat, 36, est le nombre de couples ordonnés, et c’est pourquoi diviser chaque terme par elle donne la probabilité.

Une moyenne mobile est-elle une convolution ?

Oui. Une moyenne mobile prend une fenêtre de poids égaux — cinq jours d’un cinquième chacun, par exemple — et la fait glisser le long de la série, ce qui est exactement une convolution avec cette fenêtre comme l’une des deux suites. C’est pourquoi l’opération se retrouve dans le lissage, dans les filtres et dans le traitement d’image : ce qui glisse est un jeu de poids, et ce qui est lissé est la suite.

• Convolution — the definition, the sum over overlapping products, and the length of the result — Wolfram MathWorld (United States)
• Cauchy Product — the same rule applied to the coefficients of two power series, which is what convolving two polynomial coefficient lists computes — Wolfram MathWorld (United States)
• Convolution Theorem — why the transform of a convolution is the product of the transforms, and where the operation is met in signal processing — Wolfram MathWorld (United States)