vendredi 12 mars 2010

Interpolation linéaire


Aujourd'hui un sujet qui me tient particulièrement à coeur: l'interpolation linéaire. Oh là là me direz-vous, ça a l'air bien barbant comme truc, et puis qu'est-ce qu'il peut bien avoir à raconter là-dessus, il tiendra même pas deux minutes. Wait and see !

Un tout petit peu d'histoire (personnelle) tout d'abord: c'est vers l'âge de 5 ans que j'ai du découvrir la règle de trois. Ou proportionnalité. Mais si, vous savez bien: s'il faut deux oeufs pour préparer un gâteau pour trois personnes, alors il faudra quatre oeufs pour préparer le même gâteau pour six personnes. Jusque là, rien d'extraordinaire. Je m'en souviens très bien, c'est mon papa qui m'a expliqué ça un matin au petit-déjeuner. Ce n'est que plus tard que j'ai compris que les règles de la proportionnalité ne sont qu'un cas particulier de linéarité. Avec l'exemple des oeufs et des gâteaux, la courbe du nombre d'oeufs en fonction du nombre de parts est une droite certes, mais qui passe par l'origine du repère: pas d'invités, pas d'oeufs ! Prenons un autre exemple: c'est un gars (appelons-le Bob) qui roule sur une autoroute. Sans s'arrêter, à l'horizontale (la voiture), sans bouger son pied de l'accélérateur. La distance qu'il parcourt évolue linéairement avec le temps: si Bob parcourt 120km en une heure, alors il parcourra 240km en deux heures, deux kilomètres par minute, un kilomètre toutes les trente secondes, cent mètres toutes les trois secondes... le rapport (distance)/(temps) est une constante, que l'on appelle "vitesse". Si on trace la distance parcourue en fonction du temps, c'est encore une fois une droite, qui passe par l'origine (au départ, Bob est au point de départ).

Mettons maintenant que Bob n'ait pas parcouru une distance nulle à l'origine des temps; par exemple, on sait qu'à t=0, il en est déjà à 20km au compteur. Dans ce cas, pour calculer la distance totale parcourue en fonction du temps, il faut rajouter 20km partout: au bout d'une heure à 120km par heure, le compteur de Bob affiche 120km (parcouru en une heure) + 20km (valeur à t=0)=140km, etc. La courbe d'évolution de la distance totale en fonction du temps est toujours une droite de pente (vitesse) 120km/h, mais qui ne passe pas par l'origine. Okay, c'est niveau CM1, mais ne décrochez pas tout de suite, je vais montrer dans ce qui suit que c'est là le summum de la connaissance humaine.

Au cours de mes études d'ingé, je me suis rapidement rendu compte que, bien que les cours de maths faisaient appel à des notions bien plus avancées, en pratique dans la vie réelle de tous les jours, on n'utilisait jamais rien de plus compliqué que la linéarité. Elle est partout, elle sert à tout, et vous pouvez aller voir dans n'importe quelle entreprise qui s'occupe de choses de la vie réelle (c'est-à-dire produire et vendre des choses), jamais une calculatrice n'aura entendu parler de quelque chose de plus avancé qu'une règle de trois. A croire que l'évolution d'Homo Sapiens Entreprisis s'est arrêtée là. A la fin de l'école d'ingé, je me dis nom d'un p'tit bonhomme en mousse, c'est pas possible, il doit y avoir des gens qui font des choses un peu plus compliquées et intéressantes, et ni une ni deux je me lance dans une thèse en physique. Persuadé, alors j'étais, que j'allais évoluer dans des sphères où la règle de trois ne serait qu'un jouet pour bébé, et qu'on n'y ferait plus jamais allusion.

Alors certes, dans lesdites sphères de la recherche, on a souvent le temps de faire des choses plus compliquées qu'une bête linéarité. Reprenons l'exemple de Bob conduisant sa voiture sur l'autoroute, maintenant vu par l'oeil du chercheur: ne nous contentons pas d'une vitesse constante, admettons que Bob peut changer de vitesse. De façon très générale, donnons-nous un certain nombre de points (temps/position) connus, et cherchons une façon de calculer la position de Bob en tout instant, ou inversement le temps écoulé pour chaque position. Je vous parie tous les milliards de dollars que je n'ai pas, que le premier réflexe, de n'importe quel chercheur, sera de faire passer des droites entre deux points consécutifs ! Autrement dit, de supposer que la vitesse de Bob sera constante entre deux points de référence. On retrouve une loi d'évolution linéaire, par morceaux certes, mais linéaire. Et le pire dans cette histoire c'est que, bien entendu, une telle approche sera excellente, pourvu que l'on dispose de suffisamment de points de référence (connus). Et ça ne vaut pas que pour Bob: toute loi de comportement, de n'importe quel phénomène physique, peut être représentée en première approximation par un comportement linéaire par morceaux. Je parie mon T-shirt préféré (à défaut de milliards de dollars) que dans la grande majorité des cas, si on fait attention (si on a assez de points), le linéaire est largement suffisant.

Si je regarde sur les domaines d'application auxquels je me suis intéressé sur les dernières années, je peux citer en vrac:
- Connaissant un certain nombre de valeurs de l'altitude pour des positions en longitude/latitude, quelle fonction surface utiliser pour calculer au mieux l'altitude en tout point de la planète ?
- Connaissant la valeur de la température de l'atmosphère pour un certain nombre de positions longitude/latitude/altitude, quelle fonction utiliser pour calculer la valeur de la température en n'importe quelle position ?
- Peut-on utiliser autre-chose que le linéaire pour représenter l'évolution du coefficient d'absorption en fonction de la fréquence dans le but d'accélérer la vitesse de calcul de mon spectre ?
- Et tout récemment, comment représenter au mieux l'évolution du coefficient d'absorption, à une fréquence donnée, dans un espace comportant autant de dimensions que l'on veut ? (pression, température, concentration*nombre d'espèces chimiques).

A chaque fois, bien entendu, j'ai fait des choses: méthode de pondération, racines de polynômes d'ordre 4, qui peuvent éventuellement être toutes imaginaires, etc. J'utilise maintenant des splines, qui consistent à faire passer non plus une droite entre deux points consécutifs, mais un polynôme d'ordre 3 entre 4 points consécutifs. Ce qui demande de résoudre un système linéaire tridiagonal qui a la dimension du nombre de points de référence dont on dispose (ce qui peut atteindre plusieurs centaines de milliers de valeurs). Et donc même si les méthodes numériques sous-jacentes sont bien maitrisées, il est toujours possible de tomber sur un cas où la résolution plante (division par zéro dans des cas exceptionnels, etc). Sans parler qu'avec des centaines de milliers de polynômes, on a plutôt intérêt à se taper vite fait l'écriture d'une méthode d'accélération fait-maison, sinon on ne s'en sort pas au niveau temps de calcul. Et on se trompe vingt fois avant d'avoir un algorithme d'accélération qui tienne la route.

J'en arrive donc à la conclusion que, même si ce n'est pas toujours optimal côté précision, utiliser une loi d'évolution linéaire, même par morceaux, est toujours le plus simple. Disons plutôt que le meilleur compromis du produit (compréhension)*(fiabilité)*(précision)/(temps de mise en oeuvre) est atteint... par le linéaire ! Une méthode plus facile à comprendre et plus rapide à utiliser n'existe pas (à part utiliser une valeur constante...), même si ce n'est pas le plus précis. A l'inverse, des méthodes plus précises existent, mais elles sont infiniment plus complexes à utiliser, et même si c'est amusant d'utiliser un truc complexe, il existera toujours un cas où ce n'est pas fiable.

Bon je n'en rajoute pas des tonnes, mais dans un autre domaine, si on regarde les méthodes de résolution d'équations ou de systèmes d'équations non linéaires, le top du top en la matière est la méthode de Newton-Raphson, qui consiste à utiliser... les dérivées partielles de chaque fonction par-rapport à chaque variable (la matrice jacobienne du système), et donc encore une fois, des lois d'évolution linéaires, ne serait-ce que localement.

J'en arrive à la conclusion que, même si on sait faire beaucoup plus compliqué, le linéaire est encore ce qui fonctionne le mieux dans la majorité des cas, et ce n'est pas prêt de changer ! Ca me désespère un peu, mais je dois bien me rendre à l'évidence.

Aucun commentaire:

Enregistrer un commentaire