Nous souhaitons représenter des polynômes à variable réelle et à coefficients réels. Nous représenterons un monôme par un couple (c, e), où c est le coefficient du monôme de degré e. Un polynôme sera représenté par une liste de couples disposés par ordre de degrés strictement décroissant. Par exemple, le polynôme x2 −x + 1 est représenté par la liste [(2.,2);(-1., 1); (1.,0)].
Comment représenter le polynôme x + 2 − x3 ?
Quel polynôme est représenté par [(4., 4) ; (2., 3) ; (-3., 2) ; (3., 0)] ?
Définir la fonction polynomeUnite : (float * int) list telle que polynomeUnite;; retourne le polynome unité, c’est-à-dire l’élément neutre pour la multiplication dans l’anneau des polynômes.
Définir la fonction polynomeNul : (float * int) list telle que polynomeNul;; retourne le polynome nul, c’est-à-dire l’élément neutre pour l’addition dans l’anneau des polynômes.
Définir la fonction strOfMonome : float * int -> string telle que strOfMonome m retourne une représentation au format chaîne de caractères du monôme m.
# strOfMonome (4., 3);; - : string = "4.*X^3" # strOfMonome (-2., 1);; - : string = "-2.*X^1" # strOfMonome (2., 0);; - : string = "2.*X^0"
Définir la fonction strOfPolynome : (float * int) list -> string telle que strOfPolynome p retourne une représentation au format chaîne de caractères du polynôme p. Par exemple,
# strOfPolynome [(0., 3) ; (-1., 2); (0., 1) ; (2., 0)];; - : string = "0.*X^3 + -1.*X^2 + 0.*X^1 + 2.*X^0"
Définir la fonction expOfPolynome : (float * int) list -> exp telle que expOfPolynome p convertit le polynôme p en expression de la forme donnée dans 1.3.2, par exemple
# let k = expOfPolynome [(-1., 2);(2., 0)];; val k : exp = Somme (Produit (Const (-1.), Puiss (X, 2)), Somme (Produit (Const 2., Puiss (X, 0)), Const 0.)) # str_of_exp k;; - : string = "((-1.*(x^2))+((2.*(x^0))+0.))"
Nous allons dans cette section implémenter les opérations les plus courantes sur les polynômes : addition, soustraction et produit. D’autres opérations, plus élaborées, seront examinées dans les sections suivantes.
Pour toutes les questions suivantes, un coefficient sera considéré comme nul s’il contient une valeur inférieure à 10−15.
Définir la fonction absFloat : float -> float telle que absFloat x retourne la valeur absolue de x.
Définir la fonction estNul : float -> bool telle que estNul x retourne vrai si et seulement si |x| ≤ 10−15.
Définir la fonction addPolynomes : (float * ’a) list -> (float * ’a) list -> (float * ’a) list telle que addPolynomes a b retourne la somme des polynômes a et b.
Définir la fonction multConst : (float * ’a) list -> float -> (float * ’a) list telle que multConst p k retourne le produit du polynôme p par la constante k.
Définir la fonction subPolynomes : (float * ’a) list -> (float * ’a) list -> (float * ’a) list telle que subPolynomes a b retourne le résultat de la soustraction du polynôme b au polynôme a.
Définir la fonction multXk : (’a * int) list -> int -> (’a * int) list telle que multXk p k retourne le polynôme p multiplié par Xk.
Définir la fonction multMonome : (float * int) list -> float * int -> (float * int) list telle que multMonome p (c, e) retourne le produit de p par cXe.
Définir la fonction multPolynomes : (float * int) list -> (float * int) list -> (float * int) list telle que multPolynomes p q retourne le produit des polynômes p et q.
Définir la fonction expPolynome : (float * int) list -> int -> (float * int) list telle que expPolynome p n retourne le polynôme p élevé à la puissance n.
Définir la fonction polynomeOfExp : exp -> (float * int) list telle que polynomeOfExp e convertit en polynôme l’expression e donnée dans la forme décrite en 1.3.2, par exemple
# let k = polynomeOfExp (Puiss(Somme(Const(1.), X), 4));; val k : (float * int) list = [(1., 4); (4., 3); (6., 2); (4., 1); (1., 0)] # strOfPolynome k;; - : string = "1.*X^4 + 4.*X^3 + 6.*X^2 + 4.*X^1 + 1.*X^0"
Définir la fonction floatExp : float -> int -> float telle que floatExp x n retourne xn.
Définir la fonction evalueMoche : (float * int) list -> float -> float telle que evalueMoche p x retourne l’image de x par la fonction polynôme représentée par p.
Quelle la complexité de l’évaluation d’un polynôme de degré n avec la fonction evalueMoche ?
Nous allons redéfinir la fonction d’évaluation d’un polynôme en utilisant la méthode de Horner. A titre d’exemple, observons que le polynôme 5x3 + x2 + 3x − 1 = (5x2 + x + 3)x − 1, que 5x2 + x + 3 = (5x + 1)x + 3, puis que 5x + 1 = (5)x + 1, ce qui nous donne
| 5x3 + x2 + 3x − 1 = (((5)x + 1)x + 3)x − 1 |
On généralise ce procédé avec la relation de récurrence
| anxn + … + a1x + a0 = (anxn−1 + … + a1)x + a0 |
Utiliser ce procédé pour reformuler les expressions
| x3 − 2x2 + 7x −1 |
et
| 4x7 + 2x3 − 2x2 − x + 1 |
Définir la fonction evalHorner : (float * int) list -> float -> float telle que evalHorner p x retourne l’image de x par la fonction polynôme représentée par p. Vous utiliserez une fonction auxiliaire avec un accumulateur.
Quelle la complexité de l’évaluation d’un polynôme de degré n avec la fonction evalHorner ?
Définir la fonction derivePolynome : (float * int) list -> (float * int) list telle que derivePolynome p retourne la dérivée de p.
Définir la fonction primitivePolynome : (float * int) list -> (float * int) list telle que primitivePolynome p retourne une primitive de p.
Définir la fonction integrePolynome : (float * int) list -> float -> float -> float telle que integrePolynome p a b retourne ∫abp(x)dx.
Lorsque les fonctions à intégrer sont difficiles à primitiver, il est usuel d’utiliser des algorithmes donnant rapidement des valeurs approchées d’une précision plus ou moins convenable selon le domaine d’application. Nous implémenterons la méthode des rectangles ainsi que la méthode des trapèzes.
Dans les deux méthodes que nous implémenterons, nous utiliserons la subdivision du segment [a, b] en n segments de même taille, que nous noterons [a0, a1], [a1, a2], …, [an, an−1] et tels que ∀ i ∈ {1,…, n} les valeurs (ai − ai −1) soient identiques.
La méthode des rectangles consiste à approcher l’aire ∫ai−1aip(x)dx par la surface du rectangle délimité par les points de coordonnées (ai−1, 0), (ai, 0), (ai−1, p(ai−1)) et (ai, p(ai−1)). L’intégrale ∫abp(x)dx sera donc approchée par la somme sur i des ∫ai−1aip(x)dx.
Définir la fonction rectangles : (float * int) list -> float -> float -> int -> float telle que rectangles p a b n retourne une approximation de ∫abp(x)dx en utilisant n rectangles.
La méthode des trapèzes est une variante dans laquelle on approche chaque ∫ai−1aip(x)dx par la surface du trapèze délimité par les points de coordonnées (ai−1, 0), (ai, 0), (ai−1, p(ai−1)) et (ai, p(ai)).
Définir la fonction trapezes : (float * int) list -> float -> float -> int -> float telle que trapezes p a b n retourne une approximation de ∫abp(x)dx en utilisant n trapèzes. Il est conseillé de chercher à simplifier la formule donnant la valeur de l’approximation et de la calculer avec une boucle.
A partir d’une liste de n points du plan [(x0, y0), (x1, y1), …, (xn, yn)], nous souhaitons déterminer un polynôme p, de degré n tel que tel que ∀ i ∈ {0, …, n}, p(xi) = yi.
Définir la fonction facteurLagrange : float -> (float * int) list telle que facteurLagrange z retourne le polynôme (x − z).
Étant donné i, posons
| fi(x) = Πj ≠ i(x − xj) |
Définir la fonction lagrange_f_i : (float * ’a) list -> float -> (float * int) list telle que si pts est la liste de points [(x0, y0), (x1, y1), …, (xn, yn)], lagrange_f_i pts x_i retourne fi.
Déterminer en fonction de fi un polynôme pi vérifiant pi(xi) = yi et ∀ j {0, …, n} tel que i ≠ j, pi(xj) = 0.
Définir la fonction lagrange_p_i : (float * ’a) list -> float * float -> (float * int) list telle que lagrange_p_i pts (x_i, y_i) retourne le polynôme pi.
Déterminer en fonction des pi un polynôme p interpolant les points [(x0, y0), (x1, y1), …, (xn, yn)].
Définir la fonction interpolationLagrange : (float * float) list -> (float * int) list telle que interpolationLagrange pts retourne un polynôme interpolant les points pts.
Il existe une façon assez élégante d’interpoler un polynôme p(x) = a0 + a1x + a2x2 + … + anxn passant par les points [(x0, y0), (x1, y1), …, (xn, yn)] en posant l’équation matricielle
| ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ | × | ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ | = | ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ |
Définir la fonction interpolationVandermonde : (float * float) list -> (float * int) list telle queinterpolationVandermonde pts retourne un polynôme interpolant les points pts. Vous utiliserez l’algorithme de résolution de systèmes linéaires codé dans le TP précédent.
La méthode de Newton consiste, étant donnée une fonction dérivable f, à définir une suite numérique convergeant vers un point l solution de l’équation f(l) = 0. Les conditions garantissant la convergence sortent du cadre de cet exercice.
Étant donné un point xn de cette suite, on détermine le point suivant xn+1 en calculant la tangente T à f au point d’abscisse xn. xn+1 est l’abscisse de l’intersection de T et de l’axe des abscisses.
Exprimer xn+1 en fonction de f, de f′ et de xn.
Définir la fonction newton : (float * int) list -> float -> int -> float telle que si f est la fonction polynôme représentée par p, et si le premier point de la suite x est z, alors newton p z n retourne le n-ème point de la suite x.