Introduction

Durant les deux dernières décennies, il s’est manifesté un intérêt croissant pour l’approximation des courbes et des surfaces dans les logiciels de CAO (conception assistée par ordinateur) en utilisant d’autres courbes ou surfaces de degrés moins élevés, d’expression plus simple, ou même qui nécessite moins de données pour les spécifiés. L’une des motivations de cette recherche est le besoin de portabilité des données issues de divers système de CAO/PAO. En effet bien qu’il existe différents systèmes CAO, éffectuant chacun des tâches bien spécifiques(calcul des canaux d’isolation sur les circuits éléctroniques, manipulation des formes géométriques, découpage industriel de précision…) tous ont une caractéristique commune : le besoin de portabilité, notamment d’importation ou d’exportation de données entre eux, donc sous plusieurs formats(Gerber,GerberX,DXF,HPGL…). Malgré la standarisation de ces derniers, avant cette nouvelle représentation des courbes paramétriques que constitue les courbes intervalles, la perte de données et parconséquent la mauvaise qualité de la modélisation sous-jacente des formes geométriques s’avèrait inhérente à ce transport. Ce problème de modélisation n’affecte pas les figures géométriques de base(cercle, polygones…) mais frappe les figures plus complexes. D’autrepart certains systèmes imposent des contraintes fondamentalement incompatibles sur leurs systèmes de représentation canonique. Notamment, certains systèmes se limitent à la forme polynomiale plutôt que d’adapter des formes rationnelles ou encore limitent les degrés des polynômes qu’ils utilisent. On s’attend à ce que la plupart des systèmes d’approximation garantissent au minimum certaine tolérance et satisfassent certaines recommandations, cependant aucun ne propose des informations détaillées sur l’approximation des erreurs. De telles informations peuvent être cruciales, par exemple, dans l’analyse de la résistance de certaines composantes mécaniques. Dans ce travail, nous décrivons les courbes-intervalles de Bézier qui peuvent être vecteurs de ces informations, et nous montrerons comment ces derniers intègrent facilement et naturellement la description complète de l’approximation des erreurs. Pour ce faire, nous allons introduire brièvement l’arithmétique des intervalles,la nécessité d’une telle arithmétique, ses forces et ses faiblesses et nous verrons aussi que nombreuses de ces faiblesses ne nous gêneront pas ici. Tout ceci suivi de la présentation des courbes-intervalles de Bézier en question où l’on verra l’importance des combinaisons affines dans la représentation de ces derniers ainsi que celle de sa forme centrée.
On lèvera ensuite, l’hypothèse de l’usage de l’arithmétique exacte pour introduire celui de l’arithmétique flottante et la propagation des erreurs qui en découlent. Nous aborderons suite à cela une brève révision de quelques méthodes d’approximation à la lumière de l’approximation par les polynômes suivi de quelques exemples. Et pour conclure, nous nous pencherons davantage sur l’approximation par les courbes intervalles de Bézier proprement dits.

Arithmétique des intervalles

Définition

L’arithmétique des intervalles est une arithmétique qui constitue une bonne approche pour répondre à l’exigence de fiabilité des calculs. En effet, elle repose sur le principe que tout calcul retourne un encadrement garanti de son résultat. Ceci étant car elle consiste à remplacer tout nombre par un intervalle le contenant et à effectuer les calculs sur les intervalles, les intervalles calculés contenant le résultat du calcul exact. Comme exemple, π sera représenté par [3.14; 3.15] sur une machine qui calcule en base 10 avec 3 chiffres de mantisse. Cet intervalle contient de façon garantie la valeur de π et tout calcul impliquant cet intervalle contiendra le résultat du calcul avec π. Ainsi cette arithmétique nous permet non seulement de manipuler sur machine, en utilisant le calcul flottant, des quantités qui ne sont pas exactement représentables mais aussi d’obtenir cette propriété de résultat garanti qui constitue l’avantage essentiel de cette arithmétique. Une autre propriété qui nous intéresse parmi celles qui sont propres à cette arithmétique, c’est la possibilité de pouvoir prendre en compte les incertitudes de mesures dans le cas où les données sont des valeurs expérimentales. Mais celle qui s’avère être un avantage imputable à l’utilisation de cette arithmétique est de pouvoir préserver ces propriétés avec une implémentation basée sur l’arithmétique flottante et le fait qu’elle soit effective. En effet, même si les données sont exactement représentées, les calculs intermédiaires sont arrondis et une bonne implémentation de l’arithmétique des intervalles prend en compte ces erreurs d’arrondis.

Opération sur les intervalles

Tout nombre est remplacé par un intervalle le contenant et représentable surordinateur. Il peut être représenté par ses extrémités qui sont des nombres flottants ou par son milieu et son rayon qui sont également des nombres flottants. Dans un premier temps, les notions essentielles de l’arithmétique des intervalles seront introduites sans se soucier d’une réalisation effective sur ordinateur, c’est-à-dire que toute opération sera considérée comme exacte.

Combinaison affine

Une opération cléf dans l’algorithme de DeCasteljau ainsi que dans l’algorithme d’élévation de degrés des courbes de Bézier s’avère être le calcul et l’implémentation de la combinaison affine de deux points p 0 et p1.

Propagation des erreurs des calculs flottants

Brève introduction des calculs en nombres flottants

L’incapacité des machines à prendre en compte les nombres réels dans ses opérations nous a conduit à créer et à utiliser une autre arithmétique, l’arithmétique flottante, où tous les nombres à virgules flottantes, plus communément appelés nombres flottants sont destinés à approcher les nombres réels. Ces nombres peuvent être de type simple précision, double précision ou de précision étendue. Le problème majeur du calcul flottant est la propagation des erreurs d’arrondis. Du fait du problème de cancélation(4), le résultat final d’un calcul comprenant plusieurs opérations peut être éloigné de la valeur exacte, voire de signe différent. Ainsi tout calcul avec de tel nombre est entaché d’erreur, erreur qu’il faut contrôler notamment en la bornant.
La propagation des erreurs dans les opérations sur les polynômes de Bernstein a été approfondie ailleurs[5]. Ici nous montrerons que la représentation des courbes intervalles de Bézier offre un cadre sans précédent, à travers lequel nous mêlerons approximation et erreur du calcul flottant. En outre, l’apport géométrique de la courbe-intervalle de Bézier nous renseigne sur de nouvelle conception pédagogiquesur la nature des erreurs en calcul flottant.
En premier lieu, nous revisiterons le problème lié à l’implémentation du plan affine de deux vecteurs intervalles comme illustré dans la figure 2.5. Quand nous utiliserons l’arithmétique simple précision (c’est-à-dire à 32bits), nous introduisons une certaine imprécision et incertitude . Pour représenter concrètement cette incertitude, nous élargissons l’intervalle considéré de ε(t)[i] comme l’illustre la figure 2.7 où le plan affine pour t = 1/2 est représenté avec l’arithmétique exacte en ligne continue et avec l’arithmétique flottante dont les bornes des erreurs flottantes sont représentées par des pointillés.

Rappels

Comme nous l’avons fait remarquer au début, la plupart des systèmes d’approximation garantissent seulement un certain niveau de tolérance aux erreurs, établi par convention. Aucun ne propose une description détaillée sur les erreurs d’approximation elles mêmes, et pourtant ces informations peuvent se révéler cruciales pour d’autres opérations géométriques. Pour surmonter ce problème, Sederberg et Farouki ont introduit un nouveau concept de paramétrisation d’une courbe- La courbe-intervalle de Bézier- qui lui, offre une complète description de ces erreurs d’approximation le long même de la courbe. Nous disons que nous contrôlons sur moniteur l’erreur. Mais son utilisation ne se limite pas à cela. Cette représentation a été directement utilisée pour la modélisation d’objet géométrique et en profitant de l’arithmétique par intervalle nous pouvons faire face au problème de manque de robustesse des systèmes de modélisation d’objet solide. Et dans un environnement à nombre flottant, la représentation des formes géométriques est imprécise et la modélisation numérique de ces objets ne sont que des approximations. Cette imprécision peut (1) rendre obsolète certain calcul, comme l’évaluation des bornes d’erreurs classique, et (2) entrainer la persistance de certaines inconsistances entre la géométrie et la topologie de la forme géométrique. Et c’est ici que l’arithmétique par intervalle entre en jeu. D’après l’étude faite par R.E.Moore [8] en rehaussant considérablement la stabilité numérique des calculs dans la modélisation, elle la rend en même temps plus stable.

Réduction des degrés des polynômes intervalles

Dans cette section, nous développerons un algorithme qui permettrait de borner une courbe intervalle de Bézier par une autre de degré plus petit. En d’autres termes, nous allons approximer une courbe-intervalle de Bézier par une autre, de degré inférieur. Nous ferons alors en sorte que les erreurs d’approximation soient les moindres possibles. De façon plus explicite, le problème se pose de la manière qui suit.

Interpolation d’Hermite

L’interpolation polynomiale, comme on le sait, n’est pas limitée à l’interpolation de point donné. Nous pouvons aussi interpoler d’autres informations, en l’occurrence les dérivées. Dans ce dernier cas, il est d’usage de l’appeler Interpolation d’Hermite.
L’ interpolation de Hermite implique l’interpolation des valeurs et des valeurs des dérivées de la fonction f (t) à interpoler, en des points spécifiques. En outre, nous pouvons  l’interpréter comme étant la limite de l’interpolation de Lagrange, dans laquelle une suite de (m + 1) points consécutifs k+m apparaît. Ainsi, il faut que Fn (t) prenne la même valeur que f (t) et ses m premiers dérivées f auxquels nous associons (r + 1) entiers (m0, …, mr ) tels que m0 + … + mr + r = n.
Ainsi l’unique polynôme Fn (t) satisfaisant le problème d’interpolation.
Nous tenons à signaler que l’utilisation de l’interpolation de Lagrange est purement pédagogique, afin d’illustrer l’interpolation par polynôme intervalle. Bien que ce système d’interpolation polynomiale offre un résultat simple, unique et une bonne interpretation géométrique il est trop sujet à l’oscillation et ne conserve pas les formes (n’est pas invariant par transformation géométrique). D’où le fait qu’elle n’est jamais utilisée en Design. Plus important, elle est très sensible au phénomène de Runge : phénomène inhérent à l’interpolation polynomiale, plus nous augmentons le degré de l’interpolant, plus celle-ci oscille autour de la courbe supposée échantillonnée en des paramètres t i à travers laquelle le polynôme interpolant passe, bien que nousattendions à ce que ce dernier converge vers la courbe.
Ces raisons nous ont poussé à rajouter des informations à l’interpolation, d’où l’interpolation d’Hermite vue plus haut, moins sensible à ce phénomène donc plus stable.
Cependant, la représentation sous la forme d’Hermite n’est pas invariante par transformation affine, propriété primordiale dans le Design, d’où l’on préfère la représentation sous la forme de Bézier. D’autre part la représentation de Hermite nécessite, par l’utilisateur, la donnée de plusieurs vecteurs tangents, ce qui s’avère d’autant plus complexe que le nombre de point à interpoler augmente alors que la formulation de Bézier utilise des points de contrôles auxiliaires pour définir les vecteurs tangents.
Notamment une courbe cubique est définie par 4 points : p 0 , …, p 3 sont les extrémités de la courbe, p 1 et p 3 sont les points de contrôles intérieurs qui déterminent les tangentes de début et de fin.

Approximation par une Courbe intervalle de Bézier

Nous nous limiterons ici à l’approximation d’une courbe dans le plan. Notons que la plupart des résultats que nous avons pu avoir précédemment, sur les fonctions scalaires s’appliquent également à l’interpolation des fonctions à valeur vectorielle c’est-à-dire des courbes paramétriques. Cependant nous devrions interpréter le terme
d’erreur différemment. Si p 0 , …, p n sont des suites de points correspondants à (n + 1) paramètres distincts de valeur t 0 , …, t nsur une courbe paramétrique, p(t) = {x(t), y (t)}. l’interpolation de Lagrange p n (t) sur ces points est simplement :

CONCLUSION

Nous avons pu constater à travers ce travail que l’arithmétique par intervalle et l’arithmétique flottante constituent les bases fondamentales des courbes-intervalles de Bézier outre les courbes de Bézier elles-mêmes. Ces dernières offrent une nette amélioration de l’appréciation des erreurs. Elles ont permis de mettre à jour l’approximation des erreurs et encore mieux, de les borner. Par ailleur elles ont résolu le problème de portabilité entre les divers logiciels de CAO. Cependant, l’idée que nous présentons dans ce travail est de nature générale. Dans d’autres applications, de meilleure méthode existe pour borner ces erreurs commises lors de l’approximation. Notamment, en utilisant une méthode [11] qui consiste en l’approximation d’une courbe de Bézier rationnelle, qui est déjà nettement plus précise qu’une courbe de Bézier classique, avec un polynôme courbe de Bézier, qui elle, débouche vers un intervalle d’erreur plus petit. D’autres méthodes, comme celle présenter dans [12] existent et offrent de meilleur résultat que celle proposée dans ce travail, d’ordreplus général.

Table des matières

1 Arithmétique des intervalles 
1.1 Définition
1.2 Opération sur les intervalles
1.3 Polynôme intervalle
2 Courbe intervalle de Bézier 
2.1 Rappels sur les courbes de Bézier
2.2 Intervalle à valeur vectorielle
2.3 Définition d’une courbe-intervalle de Bézier
2.4 Combinaison affine
2.5 Forme centrée
2.6 Propagation des erreurs des calculs flottants
2.6.1 Brève introduction des calculs en nombres flottants
2.6.2 Calcul avec les nombres flottants
2.7 Rappels
2.8 Définition
2.9 Réduction des degrés des polynômes intervalles
2.10 Réduction de degrés d’une courbe-intervalle de Bézier
2.11 Erreurs aux bornes
3 Approximation par des polynômes intervalles 
3.1 Rappel
3.2 Terme d’erreur et valeur approchée intervalle
3.3 Interpolation d’Hermite
3.4 Quelques simples exemples
4 Approximation par une Courbe intervalle de Bézier