RÉGRESSIONS ET INTERPOLATIONS



MÉTHODES NUMÉRIQUES

1. Complexité

1.1. NP-Complétude

2. Partie entière

3. Algorithme d'Héron

4. Algorithme d'Archimède

5. Calcul du nombre d'Euler

6. Systèmes d'équations linéaires

6.1. Une équation à une inconnue

6.2. Deux équations à deux inconnues

6.3. Trois équations à trois inconnues

6.4. N équations à n inconnues

7. Polynômes

8. Régressions et interpolations

8.1. Régression linéaire à une variable explicative

8.1.1. Droite de régression

8.1.2. Méthodes des moindres carrés

8.1.3. Analyse de la variance de la régression

8.2. Régression logistique

8.3. Interpolation polynômiale

8.3.1. Courbes de Bézier

8.3.2. Méthodes d'Euler

8.3.3. Polynôme de collocation

9. Recherche de racines

9.1. Méthodes des parties proportionnelles

9.2. Méthode de la bissection

9.3. Méthode de la sécante (Regula Falsi)

9.4. Méthode de Newton

10. Aires et sommes de riemann

10.1. Méthode des rectangles

10.2. Méthode des trapèzes

11. Programmation linéaire

11.1. Algorithme du simplexe

12. Méthode de Monte-Carlo

12.1. Calcul d'une intégrale

12.2. Calcul de PI

12.3. Dichotomie

13. Analyse en composantes principales (A.C.P.)

14. Analyse factorielle des correspondances (A.F.C.)

15. Khi-2

16. Méthode des différences finies

17. Réseaux de neurones formels

17.1. Modèle de neurone

17.2. Fonctions de transfert

17.3. Architecture de réseau

18. Algorithmes génétiques

18.1. Codage et population initiale

18.2. Les opérateurs

18.2.1. Opérateur de sélection

18.2.2. Opérateur de croisement

18.2.3. Opérateur de mutation

Les régressions (ou "interpolations") sont des outils très utiles aux statisticiens, ingénieurs, informaticiens souhaitant établir une loi de corrélation entre deux (ou plus) variables dans un contexte d'études et d'analyse ou d'extrapolation.

Il existe un grand nombre de méthodes d'interpolation : de la simple résolution d'équations du premier degré (lorsque uniquement deux points d'un mesure sont connus) aux équations permettant d'obtenir à partir d'un grand nombre de points des informations essentielles à l'établissement d'une loi (ou fonction) de régression linéaire, polynomiale ou encore logistique.

RÉGRESSION LINÉAIRE À UNE VARIABLE EXPLICATIVE

Nous présentons ici deux algorithmes (méthodes) utiles et connus dans les sciences expérimentales (nous en avons déjà parlé lors de notre étude des statistiques). L'objectif ici est de chercher à exprimer la relation linéaire entre deux variables x et y indépendantes :

- x est la variable indépendante ou "explicative". Les valeurs de x sont fixées par l'expérimentateur et sont supposées connues sans erreur

- y est la variable dépendante ou "expliquée" (exemple : réponse de l'analyseur). Les valeurs de y sont entachées d'une erreur de mesure. L'un des buts de la régression sera précisément d'estimer cette erreur.

Nous cherchons une relation de la forme:

equation   (57.75)

C'est l'équation d'une droite, d'où le terme de "régression linéaire".

DROITE DE RÉGRESSION

Il existe aussi une autre manière commune de faire une régression linéaire du type :

equation   (57.76)

qui consiste à se baser sur les propriétés de la covariance et de l'espérance (cf. chapitre de Statistiques) et très utilisée entre autres en finance (mais aussi dans n'importe quel domaine où on fait un peu de statistique).

Soit x, y deux variables dont l'une dépend de l'autre (souvent c'est y qui dépend de x) nous avons selon la propriété de linéarité de la covariance qui est rappelons-le :

equation   (57.77)

la relation suivante :

equation   (57.78)

Il vient donc pour la pente (nous réutiliserons cette relation lors de l'étude du rendement d'un portefeuille selon le modèle de Sharpe dans le chapitre d'Économétrie) :

equation   (57.79)

et pour l'ordonnée à l'origine nous utilisons les propriétés de l'espérance démontrées dans le chapitre de Statistiques:

equation   (57.80)

ce qui donne b sous la forme :

equation   (57.81)

MÉTHODE DES MOINDRES CARRÉS

Du fait de l'erreur sur y, les points expérimentaux, de coordonnées equation, ne se situent pas exactement sur la droite théorique. Il faut donc trouver l'équation de la droite expérimentale qui passe le plus près possible de ces points.

La "méthode des moindres carrés" consiste à chercher les valeurs des paramètres a, b qui rendent minimale la somme des carrés des écarts ei résiduels (SSr: Sum of Squared Residuals) entre les valeurs observées equation et les valeurs calculées théoriques de equation:

equation   (57.82)

n est le nombre de points et:

equation   (57.83)

d'où autrement écrit:

equation   (57.84)

Cette relation fait apparaître la somme des carrés des écarts comme une fonction des paramètres a,b. Lorsque cette fonction est minimale (extrêmale), les dérivées par rapport à ses paramètres s'annulent:

equation   (57.85)

Remarque: Cette méthode de recherche de minimum (optimisation) est nommée "méthode des multiplicateurs de Lagrange" dans le monde de l'économétrie. Dans notre exemple equation est la grandeur scalaire qui fait office de multiplicateur de Lagrange.

Soit après simplification :

equation   (57.86)

Le système ci-dessus est dit appelé "système des équations normales".

C'est un système linéaire de deux équations à deux inconnues. Notons pour simplifier:

equation   (57.87)

Le système devient :

equation   (57.88)

De la deuxième équation nous tirons :

equation  (57.89)

En remplaçant dans la première nous obtenons :

equation   (57.90)

De là nous avons :

equation   (57.91)

Ainsi, l'expression de la pente et de l'ordonnée à l'origine de l'équation recherchée est :

equation   (57.92)

Remarque: C'est la méthode utilisée par MS Excel lors de l'utilisation de la fonction REGRESSION( ).

Il faut remarquer que la pente a est le forme discrète de:

equation   (57.93)

Le terme b, soit l'ordonnée à l'origine peut être obtenu avec la fonction ORDONNEE.ORIGINE( ) de MS Excel et a avec la fonction PENTE( ) et l'ensemble avec la fonction DROITEREG( ).

ANALYSE DE LA VARIANCE DE LA RÉGRESSION

Nous avons donc maintenant pour la droite des moindres carrés:

equation   (57.94)

soit sous forme discrète:

equation   (57.95)

ainsi que par construction de la méthode la relation suivante:

equation   (57.96)

Maintenant, nous faisons l'hypothèse que chaque valeur mesurée est entachée d'un résidu tel que:

equation   (57.97)

Soit en soustrayant les deux dernières relations:

equation   (57.98)

Maintenant, passons par un résultat intermédiaire. Rappelons que nous avons obtenu plus haut:

equation   (57.99)

En remplaçant b par sa valeur:

equation   (57.100)

nous avons alors:

equation   (57.101)

Multipliant la deuxième relation ci-dessus par equation et retranchant de la première, nous obtenons:

equation   (57.102)

Soit après réarrangement:

equation   (57.103)

Revenons maintenant à:

equation   (57.104)

Si nous mettons le tout au carré et en sommant pour toutes les observations, nous avons:

equation   (57.105)

soit:

equation   (57.106)

Or, nous venons de montrer avant que le double produit était nul. Donc:

equation   (57.107)

Cette dernière relation est appelée "équation d'analyse de la variance". En fait, il s'agit de sommes de carrés. Il faudrait diviser par n pour obtenir des variances.

Cette dernière relation s'écrit aussi souvent:

equation   (57.108)

SCT est la "somme des carrés totale" (SSr en anglais), SCE la "somme des carrés expliquée" et SCR la "somme des carrés résiduelle".

Cette dernière relation se trouve également souvent sous la forme suivante dans la littérature:

equation   (57.109)

Notons maintenant les equation sans erreurs d'une manière différente et appelons cela le "modèle linéaire à priori":

equation   (57.110)

Il est effectivement important dans la pratique de différencier le modèle à priori qui ne prend pas en compte les erreurs du modèle réel entaché d'erreurs!

Nous avons alors:

equation   (57.111)

qui est une autre manière plus condensée et traditionnelle d'écrire:

equation   (57.112)

et il vient alors immédiatement la relation importante dans la pratique pour calculer les résidus (connaissant les valeurs calculées et les valeurs mesurées):

equation   (57.113)

Rappelons maintenant que dans la chapitre de Statistique nous avions déterminé que le coefficient de corrélation s'exprimait par:

equation   (57.114)

soit explicitement:

equation   (57.115)

Montrons que ceci est égal à (notation souvent utilisée dans la littérature spécialisée):

equation   (57.116)

Remarque: Cette formulation du coefficient de corrélation est extrêmement utile car, car contrairement à la formulation statistique, cette dernière se généralise immédiatement à la régression linéaire multiple que nous verrons un peu plus loin.

Démonstration:

Nous partons donc de:

equation   (57.117)

et puisque nous avons montré que:

equation   (57.118)

Donc:

equation   (57.119)

equationC.Q.F.D.

Nous admettrons que, pour un individu i prélevé au hasard dans la population, equation est connu sans erreur, et que equation est une réalisation d'une variable aléatoire que nous noterons dorénavant equation et la droite théorique des moindre carrés s'écrira maintenant :

equation   (57.120)

equation est par hypothèse un résidu identiquement distribué et indépendant pour chaque point i selon une loi normale centrée (de moyenne nulle et d'écart-type égal pour tout k) tel que:

equation et equation   (57.121)

donc:

equation   (57.122)

où nous avons le résidu qui est donc donné par la différence entre l'ordonnée théorique et l'ordonnée mesurée:

equation   (57.123)

Les hypothèses précédentes concernant les moments des résidus sont appelées "hypothèses de Gauss-Markov" et l'hypothèse particulière d'égalité des variances s'appelle comme nous l'avons vu dans le chapitre de Statistique "l'homoscédasticité".

Nous avons de par la propriété de l'espérance (cf. chapitre de Statistiques):

equation   (57.124)

Alors sous les hypothèses ci-dessus, nous allons montrer que a et b sont des estimateurs sans biais (cf. chapitre de Statistiques) de equation et equation et qu'il est possible d'estimer l'écart-type à partir de SCR! Ce qui est un résultat non négligeable et important.

Conformément au modèle adopté, a est à considérer maintenant comme une réalisation de la variable aléatoire donnée par :

equation   (57.125)

et b comme une réalisation de la variable aléatoire donnée par:

equation   (57.126)

Tenant compte de ce que:

equation   (57.127)

nous pouvons mettre A sous la forme:

equation   (57.128)

et B:

equation   (57.129)

Nous en déduisons les espérances pour A:

equation   (57.130)

et pour B:

equation   (57.131)

Donc A et B sont bien des estimateurs sans biais de equation.

Nous devons enfin calculer les variances de A et B en utilisant ses propriétés (cf. chapitre de Statistiques) et les hypothèses sur les résidus, nous avons:

equation   (57.132)

Comme par hypothèse nous avons tous les equation qui sont égaux nous pouvons alors écrire:

equation   (57.133)

Soit:

equation   (57.134)

et:

equation   (57.135)

En rappelant la relation de Huyghens (cf. chapitre de Statistiques) :

equation   (57.136)

Nous avons finalement:

equation   (57.137)

Le problème réside maintenant dans la détermination de equation. Evidemment pour ce faire nous allons être obligés de passer par un estimateur statistique.

Nous savons que nous pouvons écrire selon ce qui a été vu dans le chapitre de Statistique en ce qui concerne les estimateurs:

equation   (57.138)

puisque la loi normale est centrée pour les résidus donc equation... et que le résidu est une variable aléatoire implicitement dépendante de la somme de deux variables aléatoires que sont A et B d'où la minoration de deux fois l'erreur-standard.

Indiquons aussi que dans la pratique nous notons fréquemment ce dernier résultat en mélangeant les notations de l'aspect aléatoire et déterministe:

equation   (57.139)

SEE signifie en anglais "Standard Error of Estimate" (Erreur Standard de l'Estimation).

Nous avons donc les estimateurs non biaisés des variances de A et de B:

equation   (57.140)

Ce qui est sympa connaissant ces variances, c'est que nous pouvons aussi estimer la variance de la variable expliquée de notre régression facilement (en utilisant les propriétés de la variance vues dans le chapitre de Statistiques).

Il serait intéressant aussi de faire de l'inférence statistique sur l'espérance des paramètres A et B (donc la pente et l'ordonnée à l'origine) étant donné leur espérance empirique connue. Mais les développements nécessitent une hypothèse forte qui est l'indépendance des variables (equation) ce qui est peu acceptable en entreprise.

RÉGRESSION LOGISTIQUE

Bien souvent, les données statistiques disponibles sont relatives à des caractères qualitatifs. Or, comme nous allons le voir, les méthodes d'inférence traditionnelles ne permettent pas de modéliser et d'étudier ce type caractères. Des méthodes spécifiques doivent être utilisées tenant compte par exemple de l'absence de continuité des variables traitées ou de l'absence d'ordre naturel entre les modalités que peut prendre le caractère qualitatif. Ce sont ces méthodes spécifiques les plus usuelles qui seront l'objet du texte qui suit.

Comme nous l'avons vu plus haut, la régression linéaire simple a donc pour but de modéliser la relation entre une variable dépendante quantitative et une variable explicative quantitative.

Lorsque la "variable de classe" Y à expliquer est binaire (oui-non, présence-absence,0-1,etc.) nous approchons dans un premier temps celle-ci par une fonction de probabilité equation, qui nous donne à l'opposé la probabilité d'appartenir à la classe equation, que nous nommerons "régression logistique" ou encore "régression logit" (très souvent utilisée dans les cadre des réseaux de neurones formels). Ensuite, dans une deuxième étape, nous définissons pour un cas binaire une valeur "cutoff". Par exemple, si nous prenons un cutoff de 0.5 alors les cas pour lesquels equation appartiendront à la classe 1 (et inversement dans le cas contraire).

Remarques:

R1. Au fait, la régression logistique n'est qu'une simple loi de distribution de probabilités dans le cas qui nous intéresse (nous verrons une autre régression logistique dans le chapitre d'Économétrie lors de notre étude des séries temporelles).

R2. Il n'est évidemment pas possible d'appliquer systématiquement la régression logistique à n'importe quel type d'échantillon de données! Parfois il faut chercher ailleurs...

R3. Lorsque le nombre de modalités est égal à 2, nous parlons de "variable dichotomique" (oui-non) ou d'un "modèle dichotomique", s'il est supérieur à 2, nous parlons de "variables polytomiques" (satisfait-non satisfait-émerveillé).

Considérons par exemple la variable dichotomique : fin des études. Celle-ci prend deux modalités (en cours, a fini). L'âge est une variable explicative de cette variable et nous cherchons à modéliser la probabilité d'avoir terminé ses études en fonction de l'âge.

exempleExemple:

Pour construire le graphique suivant, nous avons calculé et représenté en ordonnées, pour des jeunes d'âge différent, le pourcentage de ceux qui ont arrêté leurs études.

equation
  (57.141)

Mais comment obtient-t-on pareil graphique avec une variable dichotomique??? Au fait c'est simple. Imaginez un échantillon de 100 individus. Pour ces 100 individus supposez pour un âge donné que 70% "a fini" et 30% "en cours". Eh bien la courbe représente simplement la proportion des deux classes pour l'âge donné. Il est même parfois indiqué les grosseurs des classes avec des cercles sur toute la longueur des asymptotes horizontales pour bien signifier qu'il s'agit d'une variable dichotomique.

Les points sont distribués selon une courbe en S (une sigmoïde) : il y a deux asymptotes horizontales car la proportion est comprise entre 0 et 1. Nous voyons immédiatement qu'un modèle linéaire serait manifestement inadapté.

Cette courbe évoqueront pour certains, à juste titre, une courbe cumulative représentant une fonction de répartition (d'une loi normale par exemple, mais d'autres lois continues ont la même allure). Ainsi, pour ajuster une courbe à cette représentative, nous pourrions nous orienter vers la fonction de répartition d'une loi normale, et au lieu d'estimer les paramètres a et b de la régression linéaire, nous pourrions estimer les paramètres equation de la loi Normale (qui est très similaire à la loi logistique comme nous le démontrerons plus loin). Nous parlons alors d'un "modèle Probit".

La loi qui nous intéresse cependant est donc la loi logistique. Contrairement à la loi Normale, nous savons calculer l'expression de sa fonction de répartition dichotomique (probabilité cumulée) qui est du type (c'est son premier avantage!):

equation   (57.142)

pour une variable de prédiction xP est donc la probabilité d'avoir un 1. Nous voyons immédiatement que cette dernière relation étant la primitive de la fonction de distribution, que prenant x de moins l'infini à plus l'infini que nous avons bien 1. Il s'agit donc bien d'une fonction de répartition!

S'il y a plusieurs variables prédictives nous avons alors :

equation   (57.143)

Lorsque nous optons pour cette fonction de répartition de la loi logistique, nous obtenons le modèle de régression logistique ou "modèle Logit" et c'est là son deuxième avantage le plus important: nous pouvons faire des statistiques sur une régression linéaire multiple!

Ainsi, nous estimerons la probabilité cumulée d'avoir fini ses études pour un individu d'âge x par (il existe plusieurs manières d'écrire cette loi suivant les habitudes et le contexte) :

equation   (57.144)

il en découle la fonction de distribution :

equation   (57.145)

Nous pouvons calculer aussi l'espérance de la fonction de distribution en appliquant ce qui a déjà été vu au chapitre de Statistiques mais une partie de cette intégrale ne peut être résolue que numériquement par contre... si nous posons:

equation   (57.146)

comme étant la variable aléatoire alors nous pouvons calculer numériquement:

equation   (57.147)

qui vaut 0 nous obtenons alors:

equation   (57.148)

Ainsi, nous voyons que si nous posons :

equation   (57.149)

Nous retombons sur une fonction de répartition ayant parfaitement les mêmes caractéristiques qu'une loi Normale centrée réduite (moyenne nulle et variance unitaire).

exempleExemple:

La fonction sigmoïde (de répartition) est présentée ci-dessous pour equation :

equation
  (57.150)

Les paramètres a, b sont ajustés selon le principe du maximum de vraisemblance (cf. chapitre de Statistiques). De plus, ces paramètres doivent généralement être ajustés de manière itérative, à l'aide d'un programme auquel nous fournissons des valeurs initiales, et qui optimise ces valeurs de manière récurrente (nous n'entrerons pas dans ces détails qui dépassent le cadre théorique de ce site à ce jour).

La dernière relation:

equation   (57.151)

peut par ailleurs être transformée de la façon suivante :

equation   (57.152)

d'où :

equation   (57.153)

Ce que certains écrivent aussi... :

equation   (57.154)

Le résultat de cette dernière transformation est appelé "logit". Il est égal au logarithme de "l'odds" P/1-P.

Donc lorsque les coefficients a et b ont été déterminés, l'expression précédente permet de déterminer P connaissant x facilement (il s'agit de résoudre une équation linéaire) et inversement! Par ailleurs, puisque x est une variable dichotomique les coefficients sont très facilement interprétables.

Remarque: L'odds est également appelé "cote" par analogie à la cote des chevaux au tiercé. Par exemple, si un étudiant a 3 chances sur 4 d'être reçu, contre 1 chance sur 4 d'être collé, sa cote est de 3 contre un 1, soit un odds=3.

Revenons un peu sur l'odds car il est possible d'introduire la notion de fonction logistique en faisant la démarche inverse de celle présentée ci-dessus (soit de commencer par la définition de l'odds pour aller jusqu'au logit) et ceci peut parfois même s'avérer plus pédagogique.

Supposons que nous connaissons la taille (hauteur) d'une personne pour prédire si la personne est un homme ou une femme. Nous pouvons donc parler de probabilité d'être un homme ou une femme. Imaginons que la probabilité d'être un homme pour une hauteur donnée est 90%. Alors l'odds d'être un homme est :

equation   (57.155)

Dans notre exemple, l'odds sera de 0.90/0.10 soit 9. Maintenant, la probabilité d'être une femme sera donc de 0.10/0.90 soit 0.11. Cette asymétrie des valeurs est peu parlante parce que l'odds d'être un homme devrait être l'opposé de l'odds d'être une femme idéalement. Nous résolvons justement cette asymétrie à l'aide du logarithme naturel. Ainsi, nous avons :

equation et  equation   (57.156)

Ainsi, le logit (logarithme de l'odds) est exactement l'opposé de celui d'être une femme de par la propriété du logarithme:

equation   (57.157)

exempleExemple:

Imaginons qu'une banque souhaite faire un scoring des ses débiteurs. Comme elle a plusieurs succursales (la banque) elle construit les tables de données (fictives...) suivantes pour chacune (toutes les succursales ne sont donc pas représentées):

- 1ère succursale :

Montant crédit

Payé

Non Payé

27200

1

9

27700

7

3

28300

13

0

28400

7

3

29900

10

1

Tableau: 57.3  - Scoring débituers par montant de crédit succursale 1

- 2ème succursale :

Montant crédit

Payé

Non Payé

27200

0

8

27700

4

2

28300

6

3

28400

5

3

29900

8

0

Tableau: 57.4  - Scoring débituers par montant de crédit succursale 2

- 3ème succursale :

Montant crédit

Payé

Non Payé

27'200

1

8

27'700

6

2

28'300

7

1

28'400

7

2

29'900

9

0

Tableau: 57.5  - Scoring débituers par montant de crédit succursale 3

Nous pouvons voir que la proportion totale des bons débiteurs dans les trois succursales est de equation.

Quand le crédit est inférieur à 27'500, la proportion de bons débiteurs est de equation. Quand le montant des crédits est inférieur à 28'000 la proportion de bons débiteurs est de equation.

Quand le montant des crédits est inférieur à 28'500, la proportion de bons débiteurs est de equation, et pour des montants inférieurs à 30'000 la proportion est de equation.

Nous poserons pour cette régression logistique que equation est un bon risque de crédit et equation est un mauvais risque. Ensuite, nous créons le tableau suivant qui est un récapitulatif des données de toutes les succursales:

Montant crédit

Proportion P

27'200

0.0741

27'700

0.7083

28'300

0.8667

28'400

0.7037

29'900

0.9643

Tableau: 57.6  - Proportion des bons débiteurs

Ce qui donne graphiquement en Kilo-francs :

equation
  (57.158)

Une fois ceci fait, nous utilisons la transformation en logit :

equation   (57.159)

Ce qui donne :

Montant crédit KF

Proportion P

Logit

27'200

0.0741

-2.5257

27'700

0.7083

0.8873

28'300

0.8667

1.8718

28'400

0.7037

0.8650

29'900

0.9643

3.2958

Tableau: 57.7  - Proportion des bons débiteurs et Logit

Une régression linéaire par la méthode des moindres carrés donne :

equation
  (57.160)

avec pour équation :

equation   (57.161)

La fonction logistique avec sa représentation vient alors immédiatement :

equation

equation
  (57.162)

Ainsi, il est possible de dire dans cet exemple, qu'elle est la proportion P de bons ou mauvais payeurs en fonction d'une valeur de crédit X plus petite ou égale à une certaien valeur donnée. Puisque 0 est un mauvais risque de crédit, nous voyons que plus les crédits sont élevés moins le risque est gros (dans ce cas fictif...).

INTERPOLATION POLYNÔMIALE

Il existe de nombreuses techniques d'interpolation de polynômes plus ou moins complexes et élaborées. Nous nous proposons ici de présenter quelques unes dans l'ordre croissant de difficulté et de puissance d'application.

COURBES DE BÉZIER (SPLINE)

L'ingénieur russe Pierre Bézier (Peugeot), aux débuts de la Conception Assistée par Ordinateur (C.A.O), dans les années 60, a donné un moyen de définir des courbes et des surfaces à partir de points. Ceci permet la manipulation directe, géométrique, des courbes sans avoir à donner d'équation à la machine!!

Le thème des Courbes de Bézier est une notion à multiples facettes, vraiment très riche, au croisement de nombreux domaines mathématiques très divers : Analyse, Cinématique, Géométrie Différentielle, Géométrie Affine, Géométrie Projective, Géométrie Fractale, Probabilités, ...

Les Courbes de Bézier sont par ailleurs devenues incontournables dans leurs applications concrètes dans l'industrie, l'infographie, ...

Voilà l'approche mathématique de cette technique:

D'abord, nous savons que l'équation d'une droite que nous noterons dans le domaine (par respect de tradition) M joignant deux points equation est:

equation   (57.163)

Ce qui est juste puisque lorsque equation nous sommes en A et lorsque equation nous sommes en B. Donc equation et le point M parcoure tout le segment [AB]. Par construction, si A et B étaient des masses physiques égales à l'unité, equation représente le barycentre (centre de gravité) du système pour un t donné.

Par définition, le segment [AB] est par définition la "courbe de Bézier de degré 1" avec points de contrôle A et B et les Polynômes 1-t et t sont les "polynômes de Bernstein de degré 1".

Construisons maintenant une courbe paramétrée en rajoutant une 2ème étape à ce qui précède:

equation
  (57.164)

 

1ère étape :

- Soit equation le barycentre de (A,1-t) et (B, t) et où equation décrit [AB].
- Soit equation le barycentre de (B,1-t) (C, t) et où equation décrit [BC].

2ème étape :

- Soit M(t) le barycentre de (equation,1-t) (equation,t).

Par construction, M(t) se situe donc à la même proportion du segment equation que equation par rapport au segment [AB] ou equationpar rapport au segment [BC].

La courbe obtenue est alors l'enveloppe des segments equation: en tout point M, la tangente à la courbe est donc le segment equation.

M(t) décrit alors une Courbe de Bézier de degré 2, qui, par construction
commence en A et se finit en C, et a pour tangentes [AB] en A et [BC] en C.

C'est en fait un arc de parabole (que nous pourrions noter très logiquement [ABC] ) :

equation
  (57.165)

Par le même schéma, nous pouvons définir une courbe de Bézier de n points equation soit equation. C'est ce que nous appelons "l'algorithme de Casteljau". Ainsi, soit:

equation   (57.166)

Nous avons:

equation   (57.167)

La récurrence se terminant pour:

equation   (57.168)

Ainsi, pour equation nous avons trivialement:

equation   (57.169)

Soit:

equation   (57.170)

Ainsi, nous avons forcément avec deux points l'équation d'une droite.

Considérons maintenant M(t) la courbe de Bézier d'ordre 3, nous avons donc les points définis par:

equation   (57.171)

Nous avons par la relation de récurrence:

equation   (57.172)

où nous avons éliminé les termes contenant des points non déterminés.

Nous avons donc:

equation   (57.173)

Il vient alors:

equation   (57.174)

Et donc:

equation   (57.175)

Soit sous forme matricielle:

equation   (57.176)

Par le même raisonnement, nous avons pour une courbe de Bézier d'ordre 4:

equation   (57.177)

Et là nous pouvons creuser un peu les coefficients en comparant les coefficients de Bézier des courbes d'ordre 2, 3 et 4.

D'abord, reprenons la courbe de Bézier précédente:

equation   (57.178)

Nous remarquons d'abord aisément la proportionnalité suivante:

equation   (57.179)

et si on regarde de plus près les coefficients nous remarquons que nous avons aussi:

equation   (57.180)

Il ne s'agit ni plus ni moins que du triangle de Pascal!! Et donc les constantes sont simplement les coefficients binomiaux (cf. chapitre de Calcul Algébrique) donnés par pour l'ordre n dans notre cas par:

equation   (57.181)

Ainsi, les polynômes de Bernstein sont donnés par:

equation   (57.182)

et finalement les courbes de Bernstein par d'ordre n :

equation   (57.183)

Au fait, si nous avions noté plus haut la somme sous la forme suivante:

equation   (57.184)

Nous aurions alors les polynômes de Bernstein qui seraient donnés (ce qui est plus respectueux des traditions....):

equation   (57.185)

C'est une relation très pratique car elle permet de calculer facilement et rapidement le polynôme correspondant à une courbe de Bézier d'ordre n.

Nous avons alors:

equation   (57.186)

Remarque: Une courbe de Bézier est totalement modifiée dès qu'on déplace un point de contrôle. Nous disons alors que la méthode de Bézier est une "méthode globale".

Un exemple très connu des courbes de Bézier d'ordre 3 est l'outil Plume des produits phares Adobe Photoshop ou Adobe Illustrator. Effectivement ces deux outils créent une succession de courbes de Bézier d'ordre 3 dont le point equation est défini après coup à la souris en utilisant des poignées ("torseurs" dans le langage de spécialistes Adobe...). Voici un exemple prix d'un de ces logiciels fait avec un tracé à la plume de 5 points (soit 4 splines):

equation
  (57.187)

Tant que l'utilisateur ne bouge pas les poignées de points alors tous les points sont alignés sur la droite. Nous avons alors l'impression d'avoir une spline d'ordre 2.

MÉTHODE D'EULER

Il s'agit là de la méthode numérique la plus simple (elle est triviale et dans l'idée assez proche de la méthode de Newton même si leur objectif n'est pas le même). En fait elle ne fournit une approximation (au sens très large du terme) d'une fonction f(x) dont la dérivée est connue.

Ici les points choisis sont équidistants, c'est-à-dire equation (h étant le "pas"). Nous notons equation la valeur exacte et equation, la valeur approchée.

Il y a plusieurs méthodes pour procéder (comme souvent) :

1. Graphiquement :

Nous nous déplaçons d'un pas equation en equation en suivant le vecteur de pente f(x,y)

Par construction nous savons (cf. chapitre de Calcul Différentiel Et Intégral) que (nous adoptons une notation un peu particulière dans ce contexte) :

equation   (57.188)

qui correspond donc bien à la pente (non instantané bien sûr!) en equationde la "courbe intégrale" passant par ce point. D'où :

equation   (57.189)

2. Analytiquement :

Nous remplaçons dans la dernière relation equation par equation. Nous obtenons alors :

equation   (57.190)

appelée "équation aux différences pour la méthode d'Euler".

L'application en est triviale et ne nécessite pas d'exemples particuliers.

POLYNÔME DE COLLOCATION

Soit equation une fonction connue sous forme explicite ou sous forme tabulée, et supposons qu'un certain nombre de valeurs :

equation   (57.191)

en sont données. Les points equation sont appelés les "points d'appui".

"Interpoler" f signifie estimer les valeurs de f pour des abscisses situées entre equation et equation, c'est-à-dire dans l'intervalle d'interpolation, par une fonction approximante equation, qui vérifie les "conditions de collocations" (rien à voir avec votre colocataire !) :

equation

equation
  (57.192)

La fonction p s'appelle "fonction de collocation" sur les equation. Lorsque p est un polynôme, nous parlons de "polynôme de collocation" ou de "polynôme d'interpolation".

"Extrapoler" f signifie approcher f(x) par p(x) pour des abscisses situées "hors" de l'intervalle d'interpolation.

Remarque: Il va sans dire que l'interpolation est un outil très important pour tous les chercheurs, statisticiens et autres.

Quand nous connaissons un polynôme de degré n en n+1 points, nous pouvons donc connaître par une méthode simple (mais pas très rapide - mais il existe plusieurs méthodes) complètement ce polynôme.

Pour déterminer le polynôme, nous allons utiliser les résultats exposés précédemment lors de notre étude des systèmes d'équations linéaires. Le désavantage de la méthode présentée ici est qu'il faut deviner à quel type de polynôme nous avons affaire et savoir quels sont les bons points qu'il faut choisir...

Un exemple particulier devrait suffire à la compréhension de cette méthode, la généralisation en étant assez simple (voir plus loin).

Soit un polynôme du second degré :

equation   (57.193)

et nous avons connaissances des points suivants (dont vous remarquerez l'ingéniosité des points choisis par les auteurs de ces lignes...) :

equation   (57.194)

Nous en déduisons donc le système d'équations :

equation   (57.195)

Système qui une fois résolu dans les règles de l'art nous donne :

equation   (57.196)

Voyons le cas général :

Théorème : Soient equation des points d'appui, avec equation si equation. Alors il existe un polynôme equation de degré inférieur ou égal à n, et un seul, tel que equation pour equation.

Démonstration:

Posons :

equation   (57.197)

Les conditions de collocation :

equation   (57.198)

s'écrivent donc :

equation   (57.199)

Il s'agit d'un système de n+1 équations à n+1 inconnues.

Sont déterminant s'écrit :

equation   (57.200)

relation que nous appelons "déterminant de Vandermonde". Nous savons que si le système à une solution, le déterminant du système doit être non nul (cf. chapitre d'Algèbre linéaire).

Montrons par l'exemple (en reprenant un polynôme du même degré que celui que nous avons utilisé plus haut) que le déterminant se calcule selon la relation suivante précédente (le lecteur généralisera par récurrence) :

Donc dans le cas equation, nous considérons le déterminant :

equation   (57.201)

qui correspond dont au système (pour rappel) :

equation   (57.202)

Calculons ce déterminant suivant la colonne 1 (en faisant usage des cofacteurs comme démontré dans le chapitre d'Algèbre linéaire) :

equation   (57.203)

Ce dernier polynôme peut s'écrire :

equation   (57.204)

Ce qui s'écrit :

equation   (57.205)

Comme les equation sont l'énoncé de notre problème tous différents tels que equation alors le système a une solution unique. Ce qui prouve qu'il existe toujours alors un polynôme d'interpolation.

equationC.Q.F.D.


page suivante : 9. Recherche de racines