Un algorithme pour mettre en rang une équipe de football

1. Aligner des joueurs sur un terrain

Lors de la coupe du monde de football 2010, l’équipe d’Allemagne a chuté en demi-finale mais a impressionné par sa qualité de jeu et par sa rigueur. Le sélectionneur avait mis au point une méthode infaillible pour aligner les joueurs avant d’écouter l’hymne national. Comme il n’a pas utilisé cet algorithme pour les matches, on n’a pas pu en admirer l’efficacité : merci au professeur Ulrich Rüde et à Christoph Freundl, de l’Université d’Erlangen, de nous l’avoir communiqué.

Tous les joueurs sont sur le terrain, en train de s’échauffer, et peuvent se déplacer sur toute la surface. Puis ils doivent former une ligne droite, matérialisée par des drapeaux aux extrémités. Ces drapeaux sont bien sûr retirés avant de jouer et l’alignement ne sert pas pendant la phase de jeu.

Les joueurs doivent se placer entre les deux drapeaux, pour former une ligne, et se positionner à intervalles réguliers. Ils portent un maillot avec un numéro de 1 à 11. Le joueur 1 doit se trouver près du drapeau de gauche, puis le joueur 2 à côté, et ainsi de suite, jusqu’au joueur 11, avant le drapeau de droite.

La méthode allemande

Au départ, les joueurs sont éparpillés sur le terrain. Intuitivement, la ligne sera réalisée si chaque joueur portant le maillot i est au milieu des joueurs voisins, avec les maillots (i-1) et (i+1), pour i variant de 2 à 10. Par exemple, le joueur 4 est au milieu des joueurs 3 et 5. Le joueur 1 est entre le drapeau de gauche et le joueur 2 ; le joueur 11 est entre le joueur 10 et le drapeau de droite.

Le sélectionneur agit du bord du terrain. Il appelle, avec son sifflet, les joueurs l’un après l’autre et leur dit de se placer au milieu des joueurs voisins : le joueur avec le maillot 1 se place au milieu du drapeau de gauche et du joueur 2, puis le joueur 2 se place au milieu des joueurs 1 et 3 ; ainsi de suite, jusqu’au joueur 11 qui se place au milieu du joueur 10 et du drapeau de droite. Les joueurs ne sont pas encore alignés, loin de là. Alors le sélectionneur recommence les déplacements. Il utilise ainsi un algorithme itératif. Chaque itération consiste à placer les 11 joueurs l’un après l’autre et nécessite ainsi 11 déplacements de joueurs.

Au bout de plusieurs itérations, les joueurs forment plus ou moins un rang. S’ils pouvaient continuer à se déplacer indéfiniment, ils finiraient par être tout à fait alignés. L’algorithme converge vers le résultat voulu, qui est une ligne droite. La convergence est garantie, quelle que soit la position de départ des joueurs. Le sélectionneur arrête de déplacer ses joueurs quand il considère que l’alignement est assez bon. Il utilise un critère d’arrêt de l’algorithme itératif.

Chaque itération prend un peu de temps, car chaque joueur i attend que le joueur (i-1) ait bougé pour se déplacer à son tour. C’est pourquoi le sélectionneur a imaginé une autre version. Il déplace d’abord les joueurs avec un numéro pair, puis les joueurs avec un numéro impair. Du coup, tous les joueurs pairs peuvent se déplacer ensemble, puisqu’ils se placent au milieu de joueurs impairs qui bougeront après eux. Ainsi, le joueur 2 se positionne entre le joueur 1 et le joueur 3, en même temps que le joueur 4 entre le joueur 3 et le joueur 5, etc. Puis tous les joueurs impairs peuvent se déplacer ensemble, puisqu’ils se placent au milieu de joueurs pairs qui ont fini de bouger. Les itérations peuvent également continuer jusqu’à former une ligne presque droite. On observe qu’il faut un peu plus d’itérations. Par contre, chaque itération prend moins de temps, parce que les joueurs peuvent se déplacer simultanément. Il y a ainsi un compromis à trouver entre la vitesse d’exécution de chaque itération et la vitesse de convergence de l’algorithme.

Pour accéder à l’applet Java, autorisez les applets du domaine https://interstices.info. Si votre navigateur n’accepte plus le plug-in Java, mais que Java est installé sur votre ordinateur, vous pouvez télécharger le fichier JNLP, enregistrez-le avant de l’ouvrir avec Java Web Start.

Applet réalisée par Régis Monte, d’après Christoph Freundl.

Tout le monde sait que l’équipe de France n’a pas brillé à la coupe du monde 2010. Le nouveau sélectionneur décide de prendre les choses en main et de tester l’algorithme des Allemands. Pour un stage d’entraînement, il a sélectionné 31 joueurs avec les maillots numérotés de 1 à 31. La règle du jeu est la même, il faut former une ligne entre deux drapeaux, avec les joueurs espacés régulièrement. Les joueurs sont placés au hasard sur le terrain puis, au coup de sifflet, chacun doit se placer au milieu de ses voisins. Le sélectionneur choisit d’appeler les joueurs un par un, dans l’ordre de 1 à 31. On observe qu’il faut beaucoup d’itérations pour obtenir un alignement acceptable. L’algorithme converge toujours, mais beaucoup plus lentement. Pourtant, les Français ont obéi au sélectionneur. Mais ils sont plus nombreux que les Allemands. La vitesse de convergence de l’algorithme dépend du nombre de joueurs : plus les joueurs sont nombreux, plus il faut d’itérations.

La méthode espagnole

L’équipe d’Espagne est championne du monde en 2010. Est-ce parce que leur sélectionneur a adopté une méthode différente ?

Pour simplifier, on va supposer que les drapeaux sont sur la ligne de touche, qui est donc tracée. Le sélectionneur utilise des outils : avec un mètre, il mesure la longueur L de cette ligne, puis, avec une calculatrice, il calcule la distance d entre deux joueurs. Lorsqu’il y a 11 joueurs, on a d = L/12; lorsqu’il y a 31 joueurs, on a d = L/32. Ensuite, le sélectionneur prend un bâton, fait une marque sur le bâton à la distance d.

Au coup de sifflet, le joueur 1 prend le bâton, va se placer sur la ligne, près du drapeau de gauche; il mesure sa place grâce au bâton, il est ainsi à la distance d du drapeau. Au coup de sifflet suivant, le joueur 2 prend le bâton et va se placer sur la ligne, près du joueur 1, à une distance d. Ainsi de suite, jusqu’au joueur 11. Ainsi, tous les joueurs sont sur la ligne, matérialisée sur le terrain, et sont espacés régulièrement avec une distance d entre les joueurs. Si les mesures sont justes et si les joueurs ont bien utilisé le bâton, le joueur 11 est à une distance d du drapeau de droite.

Le sélectionneur espagnol a utilisé un algorithme direct : il n’y a pas d’itérations. Grâce au bâton étalonné, chaque joueur ne se déplace qu’une seule fois, soit au total 11 déplacements, pour obtenir un alignement parfait. Avec 31 joueurs, il y a au total 31 déplacements.

La méthode du XV de France

Le XV de France rend visite à l’équipe de foot. Les joueurs de rugby font le pari qu’ils peuvent s’aligner entre les drapeaux, sans faire de mesure, avec 15 déplacements de joueurs, mais en seulement 4 étapes. Pari tenu, les joueurs de rugby font la démonstration.

Le joueur 8 se place au milieu des drapeaux. Ensuite, le joueur 4 va se placer au milieu du drapeau de gauche et du joueur 8, tandis que le joueur 12 va se placer en même temps au milieu du joueur 8 et du drapeau de droite. Troisième étape, les joueurs 2, 6, 10 vont se positionner à leur place, en même temps, au milieu des joueurs déjà placés (par exemple, le 6 au milieu du 4 et du 8). Quatrième et dernière étape, les joueurs impairs vont se placer au milieu des joueurs pairs, tous en même temps.

Pour accéder à l’applet Java, autorisez les applets du domaine https://interstices.info. Si votre navigateur n’accepte plus le plug-in Java, mais que Java est installé sur votre ordinateur, vous pouvez télécharger le fichier JNLP, enregistrez-le avant de l’ouvrir avec Java Web Start.

Applet réalisée par Régis Monte.

Le XV de France a donc gagné son pari. L’équipe de rugby a utilisé un algorithme direct parallèle. Comme avec l’algorithme espagnol, il y a 15 déplacements, mais ces déplacements peuvent se faire simultanément, ce qui permet d’aligner parfaitement les joueurs en 4 étapes.

Le sélectionneur de foot veut essayer l’algorithme, encore mieux, avec 31 joueurs. En 5 coups de sifflet, le tour est joué :

• 1^er coup de sifflet : joueur 16 au milieu des drapeaux.
• 2^e coup de sifflet : joueurs 8 et 24 à leur place.
• 3^e coup de sifflet : joueurs 4, 12, 20, 28 en poste.
• 4^e coup de sifflet : joueurs 2, 6, 10, 14, 18, 22, 26, 30 sur la ligne.
• 5^e coup de sifflet : joueurs impairs pour finir.

Le capitaine de rugby lance alors un nouveau défi : utiliser l’algorithme avec seulement une équipe de 11 joueurs. C’est parti :

• 1^er coup de sifflet : joueur 6 au milieu.
• 2^e coup de sifflet : joueurs 3 et 9 de chaque côté du joueur 6.
• 3^e coup de sifflet : cela coince ! il faut utiliser un algorithme permettant de placer 2 joueurs entre 2 autres. Admettons que 2 joueurs sachent faire cela, avec un algorithme direct comme celui des Espagnols. Alors, les joueurs 1 et 2 vont se placer entre le drapeau et le joueur 3. En même temps, les joueurs 4 et 5 se positionnent, ainsi que les joueurs 7 et 8, et les joueurs 10 et 11.

Au prix d’une petite modification de l’algorithme, il fonctionne ainsi avec un nombre quelconque de joueurs. Il faut savoir placer un joueur au milieu de deux autres et aussi placer deux joueurs ensemble, chacun à une distance d/2 du milieu (d étant la distance entre deux joueurs). Ainsi, l’équipe de France de foot va se déplacer très rapidement sur le terrain et — qui sait ? — réaliser des prouesses.

2. Du sport de ballon au sport cérébral

Mais ne nous égarons pas et revenons aux algorithmes.

Les joueurs de foot mis en équations

Essayons de modéliser l’exercice précédent, avec un peu de formules mathématiques et quelques notations. L’équipe contient n joueurs. Les positions des joueurs sont repérées par leurs coordonnées (x_i,y_i), i = 1, 2… n. x_i est la position horizontale du joueur i et y_i sa position verticale. Les positions des drapeaux sont connues et sont aussi repérées par leurs coordonnées : (x₀, y₀) et (x_n+1, y_n+1). Mettre les joueurs au milieu de leurs voisins se traduit par les équations suivantes :

x_i = (x_i-1 + x_i+1)/2,
y_i = (y_i-1 + y_i+1)/2,

avec i qui varie de 1 à n. On a donc deux systèmes de n équations à n inconnues, dont les équations sont presque les mêmes. Ces deux systèmes ont une solution unique : il n’y a qu’une façon d’aligner les joueurs.

Pour simplifier, nous étudions maintenant seulement les positions horizontales. On a donc 2 données connues x₀ et x_n+1 et n inconnues x₁, x₂… x_n, avec les n équations :

x₁ = (x₀ + x₂)/2,
x₂ = (x₁ + x₃)/2,
…,
x_n = (x_n-1 + x_n+1)/2.

Si on connaissait x₂, on pourrait calculer x₁. Si on connaissait x₁ et x₃, on pourrait calculer x₂. Il faut réussir à calculer ensemble x₁, x₂… x_n, c’est-à-dire résoudre le système d’équations.

Il s’agit d’un système linéaire : chaque équation traduit des proportions entre les inconnues et les données. Ici, une inconnue est au milieu des deux autres. Par comparaison, l’équation x₂ = (x₁² + x₃²)/2 par exemple, n’est pas linéaire : x₂ n’est pas proportionnel à x₁ et x₃.

Ce système linéaire est particulier, car chaque équation ne fait jouer que trois inconnues consécutives : l’équation i traduit une proportion (le milieu) entre les positions x_i, x_i-1, x_i+1. On appelle ce système un système tridiagonal.

Comment résoudre un système tridiagonal ?

Premier point important : le problème des joueurs considéré ici a une solution et une seule. Certains systèmes ont aussi une solution unique. Par contre, il existe des systèmes qui n’ont pas de solution, d’autres qui ont une infinité de solutions.

Nous avons vu trois algorithmes :

• l’algorithme des Allemands. Cette technique itérative s’appelle l’algorithme de Gauss-Seidel, du nom de ses inventeurs. Il a d’abord été inventé en 1823 par Carl Friedrich Gauss, un très grand mathématicien allemand. Il a ensuite été développé par un de ses collègues, Ludwig Seidel. L’algorithme fonctionne pour tout système tridiagonal. Le nombre d’opérations (les déplacements des joueurs) à chaque itération est proportionnel à n. La solution trouvée est une approximation. L’algorithme converge vers la solution exacte et le nombre d’itérations varie avec n, sous certaines hypothèses sur le système tridiagonal. La version pair-impair permet de déplacer des joueurs en parallèle, par contre, elle augmente le nombre d’itérations. Nous allons y revenir plus loin.
• l’algorithme des Espagnols. La technique présentée ici est spécifique du système tridiagonal considéré. Elle ne peut pas se généraliser à un système tridiagonal quelconque. Mais on peut définir un algorithme direct pour tout système tridiagonal et pour tout système linéaire. L’algorithme direct le plus utilisé s’appelle l’algorithme de Gauss, du nom du même mathématicien allemand. Avec cet algorithme direct, il n’y a pas d’itération et la solution trouvée est exacte (aux erreurs d’arrondi près). Pour un système tridiagonal, le nombre d’opérations est proportionnel à n ; si on multiplie le nombre d’inconnues par 10, on multiplie aussi le nombre d’opérations par 10 : la complexité est linéaire. L’algorithme est séquentiel : les joueurs se placent l’un après l’autre.
• l’algorithme des rugbymen. C’est un algorithme direct, avec une complexité linéaire, comme l’algorithme des Espagnols ; la solution est exacte et le nombre d’opérations est proportionnel à n. Mais il est aussi parallèle. Il positionne (2^p – 1) joueurs en p étapes (p = 4 pour n = 15 et p = 5 pour n = 31).

Les deux algorithmes directs vont très vite. Pourquoi alors utiliser l’algorithme de Gauss-Seidel ?

La version parallèle (l’algorithme des rugbymen) ne fonctionne que pour les systèmes tridiagonaux. Il existe plusieurs variantes parallèles, assez similaires (réduction cyclique, etc). Mais il est difficile de généraliser cet algorithme à un système non tridiagonal.

L’algorithme direct de Gauss fonctionne pour tout système qui possède une solution unique, à condition de permuter parfois les équations (stratégie du pivot de Gauss). Mais le nombre d’opérations pour un système général (non tridiagonal) n’est plus proportionnel à n. Dans le cas d’un système général, chaque équation fait intervenir toutes les inconnues et on montre que le nombre d’opérations de l’algorithme direct de Gauss est proportionnel à n³ ; donc, si on multiplie par 10 le nombre d’inconnues, on multiplie par 1000 le nombre d’opérations : la complexité est cubique.

L’algorithme de Gauss-Seidel fonctionne aussi pour tout système qui possède une solution unique, à condition qu’on ne fasse pas de division par 0 (ce qui est bien sûr interdit). Par contre, il ne converge pas à tous les coups et il converge plus ou moins vite. Dans le cas général, le nombre d’opérations à chaque itération est proportionnel à n². Au total, avec m itérations, l’algorithme nécessite donc un nombre d’opérations proportionnel à n²m. Donc si m < n, l’algorithme de Gauss-Seidel nécessite moins d’opérations que celui de Gauss (on considère un nombre égal à n³ et à n²m, en négligeant les constantes de proportionnalité).

3. L’algorithme de Gauss et ses variantes

L’algorithme des Espagnols

L’algorithme des Espagnols utilise une transformation du problème, qui est ici basée sur un argument géométrique : on sait que tous les joueurs sont équidistants, et que la distance entre deux joueurs vaut d = L/(n+1). On obtient le système d’équations suivant, qui est équivalent au système tridiagonal de départ :

x₁ = x₀ + d,
x₂ = x₁ + d,
…,
x_n = x_n-1 + d.

Ce système est très particulier, car on peut le résoudre pas à pas. En effet, avec la première équation, on calcule x₁; ensuite, avec la deuxième équation, puisqu’on connaît x₁, on peut calculer x₂; et ainsi de suite. Le système est bidiagonal.

L’algorithme utilise un principe de base : par une transformation, on aboutit à un problème équivalent, plus simple, que l’on sait résoudre. C’est le principe appliqué dans l’algorithme de Gauss. La transformation utilise ici un argument géométrique, alors que l’algorithme de Gauss utilise des calculs algébriques, mais le résultat est aussi un système bidiagonal.

L’algorithme des rugbymen

L’algorithme des rugbymen utilise une autre transformation du problème, elle aussi basée sur un argument géométrique : lorsque n = 2^p – 1, le joueur m = (n+1)/2 est exactement au milieu des drapeaux. On calcule donc x_m = (x₀ + x_n+1)/2, on sépare l’équipe des joueurs en deux et on obtient les deux systèmes suivants :

On a ainsi deux systèmes indépendants à résoudre, qui sont des systèmes tridiagonaux avec m-1 équations et m-1 inconnues. Pour obtenir l’équation avec x_m dans le cas général, il faut utiliser la transformation algébrique de l’algorithme de Gauss.

L’algorithme utilise un autre principe de base : la récursivité. Il suffit d’appliquer le même procédé aux systèmes tridiagonaux et le tour est joué. En effet, m-1 = (n+1)/2 -1 = 2^p-1 -1, donc on peut appliquer la récursion en remplaçant n par m-1. On aboutit finalement à un système d’une équation à une inconnue que l’on sait résoudre. En déroulant la récursion, on obtient bien l’algorithme des rugbymen : on place d’abord le joueur du milieu, puis les deux joueurs du milieu de chaque côté, puis les quatre joueurs du milieu dans les quatre intervalles, etc.

De plus, l’algorithme est parallèle ; il utilise encore un principe de base : diviser pour régner. Les deux systèmes indépendants peuvent être résolus en parallèle. En déroulant la récursion, on place un joueur, puis deux en même temps, puis quatre en même temps, etc.

4. L’algorithme de Gauss-Seidel

L’algorithme de Gauss-Seidel utilise des approximations et procède par itérations. Bien qu’il fonctionne pour tout système général, nous le présenterons ici pour le système tridiagonal des joueurs. Au début, les joueurs ne sont pas en ligne, aux positions x₁(0), x₂(0)… x_n(0). À la première itération, le joueur 1 se place entre le drapeau de gauche et le joueur 2, puis le joueur 2 se place entre le joueur 1 et le joueur 3. Les nouvelles positions sont notées x₁(1); x₂(1)… x_n(1) et sont calculées par les formules :

x₁(1) = (x₀ + x₂(0))/2,
x₂(1) = (x₁(1) + x₃(0))/2,
…
x_i(1) = (x_i-1(1) + x_i+1(0))/2,
…
x_n(1) = (x_n-1(1) + x_n+1)/2.

Rappelons que x₀ et x_n+1 sont connus, puisque ce sont les coordonnées des drapeaux. À présent, on n’a plus d’équation à résoudre, mais une formule à calculer : on connaît x_i-1(1) et x_i+1(0), donc on peut calculer x_i(1). On peut entrer cette formule dans l’ordinateur qui va faire les opérations.

À la deuxième itération, on calcule :

x₁(2) = (x₀ + x₂(1))/2,
x₂(2) = (x₁(2) + x₃(1))/2,
…
x_i(2) = (x_i-1(2) + x_i+1(1))/2,
…
x_n(2) = (x_n-1(2) + x_n+1)/2.

Et ainsi de suite. À l’itération k, on calcule :

x₁(k) = (x₀ + x₂(k-1))/2,
x₂(k) = (x₁(k) + x₃(k-1))/2,
…
x_i(k) = (x_i-1(k) + x_i+1(k-1))/2,
…
x_n(k) = (x_n-1(k) + x_n+1)/2.

On poursuit ce processus itératif jusqu’à obtenir un alignement correct.

Convergence de l’algorithme de Gauss-Seidel

Pour étudier la convergence de l’algorithme, on introduit l’erreur commise par l’approximation. Il faut encore quelques notations. Soit a₁, a₂… a_n l’unique solution du système (les positions des joueurs sur la ligne). On définit les erreurs e_i(k) à l’itération k par e_i(k) = x_i(k)-a_i. Pour n’avoir qu’un seul nombre à manipuler, on définit l’erreur globale par e(k)² = e₁(k)² +e₂(k)² +…+ e_i(k)² +…+ e_n(k)². On utilise des carrés pour être sûr qu’on n’ajoute que des nombres positifs. On démontre qu’il existe un nombre r, qui dépend du système et de sa taille, tel que e(k + 1) ≤ re(k).

Autrement dit, à chaque itération, l’erreur est multipliée par r. De proche en proche (par récurrence), on obtient donc e(k) ≤ r^ke(0). Autrement dit, l’erreur à l’itération k est plus petite que l’erreur du début multipliée par le nombre r élevé à la puissance k.

Si r < 1 alors r^k devient de plus en plus petit quand k augmente et converge vers 0. Donc, une condition suffisante pour que l’algorithme de Gauss-Seidel converge est que r soit strictement plus petit que 1. L’algorithme converge alors quel que soit le point de départ. Dans ce cas, on voit que l’erreur à l’itération k + 1 est plus petite que l’erreur à l’itération k : la convergence est monotone. Si on revient à l’exemple des joueurs de foot, on peut démontrer que r < 1. Donc l’algorithme converge, quelle que soit la position de départ des joueurs ; les joueurs se rapprochent de la ligne à chaque itération.

Grâce à cette convergence monotone, on peut définir un critère d’arrêt. En effet, l’idéal serait de dire qu’on s’arrête lorsque l’erreur est assez petite. Mais si on savait calculer l’erreur, alors on saurait calculer la solution. Si le problème était résolu, pourquoi essayer de le résoudre ?!

Donc, définissons un critère d’arrêt avec les approximations calculées. En fait, on va définir l’écart entre deux approximations successives par d_i(k) = x_i(k)-x_i(k-1) et globalement par d(k)² = d₁(k)² + d₂(k)² +…+ d_i(k)² +…+ d_n(k)². On montre qu’on a aussi d(k + 1) ≤ rd(k).

Le critère d’arrêt est alors simple : on arrête lorsque d(k) est assez petit. En effet, on sait que si on continue, les écarts entre les approximations vont être de plus en plus petits. Ce critère est ici justifié. Mais pour d’autres algorithmes itératifs, on n’a pas cette convergence monotone. On ne sait donc pas si, par hasard, l’écart est devenu petit mais va augmenter à nouveau. Il est alors plus difficile de définir un critère d’arrêt.

On a ainsi déterminé une condition suffisante de convergence. Si r > 1, on ne sait pas conclure sur la convergence. La condition r < 1 n’est pas nécessaire. Mais on peut trouver des systèmes avec r > 1 pour lesquels l’algorithme ne converge pas.

Lorsque r est très petit, r^k converge très vite vers 0, donc l’erreur e(k) aussi. Mais lorsque r est proche de 1, r^k converge très lentement et on observe souvent que l’algorithme de Gauss-Seidel converge aussi lentement. Pour le système tridiagonal des joueurs de foot, le nombre r augmente avec le nombre de joueurs. C’est pour cela qu’il faut plus d’itérations avec 31 joueurs qu’avec 11 joueurs.

De l’algorithme de Gauss-Seidel à l’algorithme multigrille

En pratique, on observe donc que le nombre d’itérations augmente rapidement avec le nombre n d’inconnues. De nos jours, ce sont des systèmes d’équations avec des millions d’inconnues qui doivent être résolus. Malgré l’accroissement de la puissance de calcul des ordinateurs, l’algorithme de Gauss-Seidel prendrait trop de temps, c’est pourquoi il n’est plus utilisé tel quel.

Il sert d’ingrédient de base dans la composition d’un autre algorithme, qu’on appelle multigrille. Le principe qui gouverne l’algorithme multigrille consiste à définir plusieurs niveaux imbriqués, de l’ordre de quelques dizaines, en associant à chaque niveau un système linéaire. Les niveaux étant classés du plus grand système au plus petit, on considère tout d’abord le niveau le plus élevé et celui immédiatement inférieur, et le petit système sert à corriger l’erreur commise dans le grand système. On descend ensuite d’un niveau, et ainsi de suite, jusqu’à arriver au niveau le plus bas. On remonte alors en sens inverse, puis on enchaîne les cycles, jusqu’à ce que l’algorithme converge. Les mathématiciens démontrent, toujours sous certaines hypothèses et pour certains systèmes, que l’algorithme multigrille converge très vite. De plus, le nombre d’itérations ne dépend alors pratiquement pas du nombre d’inconnues.

L’idée d’illustrer l’algorithme de Gauss-Seidel par une équipe de football vient de Ulrich Rüde et Christoph Freundl, dans leur article Gauß-Seidel Iteration zur Berechnung physikalischer Probleme paru en allemand dans la série Algorithmus der Woche publiée à l’occasion de l’Année de l’informatique (Informatikjahr) 2006.
L’adaptation et la programmation des applets en français a été réalisée par Régis Monte.