Manipulation de polynômes
Activités #6

3.1. Fonctions utilitaires

1. Définir la fonction is_poly0(p) indiquant si le polynôme est nul.
   
2. Définir la fonction degre(mp) (resp. coeff(mp)) renvoyant le degré (resp. coefficient) d’un monôme ou d’un polynôme.
   
3. Programmez la fonction poly2str(p) renvoyant une chaîne de caractères représentant le polynôme creux sous la forme \(\sum a_i X^i\).
   

   poly2str(list())
   poly2str(p)
   

   [1] ""
   [1] "2*X^5 + -1*X^4 + -2*X^1"

4. Programmez la fonction mult_ext(p,k) de multiplication par un scalaire k d’un polynôme.
   

   poly2str(mult_ext(p,-2))
   

   [1] "-4*X^5 + 2*X^4 + 4*X^1"

3.2. Constructeurs

1. Programmez la fonction make_poly(x) transformant un polynôme plein en un polynôme creux.
   

   poly2str(make_poly(c(0, -2, 0, 0, -1, 2)))
   poly2str(make_poly(c(-1, 0, -7, 0, 1)))
   

   [1] "2*X^5 + -1*X^4 + -2*X^1"
   [1] "1*X^4 + -7*X^2 + -1*X^0"

2. Programmez la fonction rand_poly(n, coeffs) générant un polynôme aléatoire de degré inférieur à n et dont les coefficients sont tirés dans le vecteur coeffs.
   

   poly2str(rand_poly(5,0:3))
   poly2str(rand_poly(10,0:1))
   

   [1] "2*X^3 + 1*X^2 + 1*X^0"
   [1] "1*X^9 + 1*X^7 + 1*X^5 + 1*X^4 + 1*X^2"

3.3. Addition et soustraction   KEY

1. Programmez la fonction add(p,q) d’addition de deux polynômes.
   

   Nous allons nous appuyer sur deux fonctions auxiliaires :

   • la fonction sort_monoms(p) qui trie une liste de monômes par degré décroissant ;
   • la fonction merge_monoms(p) somme les termes de même degré, et supprime les termes dont le coefficient est nul.

   poly2str(add(p, list()))
   poly2str(add(list(), q))
   poly2str(add(p,q))
   

   [1] "2*X^5 + -1*X^4 + -2*X^1"
   [1] "1*X^4 + 7*X^2 + -1*X^0"
   [1] "2*X^5 + 7*X^2 + -2*X^1 + -1*X^0"

2. Programmez la fonction sub(p,q) de soustraction de deux polynômes.
   

   poly2str(sub(p,p))
   poly2str(sub(p,q))
   poly2str(sub(q,p))
   

   [1] ""
   [1] "2*X^5 + -2*X^4 + -7*X^2 + -2*X^1 + 1*X^0"
   [1] "-2*X^5 + 2*X^4 + 7*X^2 + 2*X^1 + -1*X^0"

   ## Random list of monoms
   li <- replicate(10, sample(0:3, 2, replace=TRUE), simplify = FALSE)
   paste(li)
   ## Test auxiliary functions
   p1 <- sort_monoms(li)
   paste(p1)
   p1 <- merge_monoms(li)
   poly2str(p1)
   
   
   p1 <- merge_monoms(append(li, mult_ext(li,-1)))
   poly2str(p1)
   
   
   

   [1] "c(1, 0)" "c(0, 0)" "2:3"     "c(0, 0)" "1:2"     "c(0, 0)" "2:3"
    [8] "c(0, 0)" "c(2, 0)" "c(1, 1)"
    [1] "2:3"     "2:3"     "1:2"     "c(1, 1)" "c(2, 0)" "c(0, 0)" "c(0, 0)"
    [8] "c(0, 0)" "c(0, 0)" "c(1, 0)"
   [1] "4*X^3 + 1*X^2 + 1*X^1 + 3*X^0"
   [1] ""

3.4. Intégration et dérivation

1. Programmez la fonction integ(p) retournant une primitive du polynôme p.
   

   poly2str(integ(p))
   poly2str(integ(q))
   

   [1] "0.333333333333333*X^6 + -0.2*X^5 + -1*X^2"
   [1] "0.2*X^5 + 2.33333333333333*X^3 + -1*X^1"

2. Programmez la fonction deriv(p) retournant le polynôme dérivé du polynôme p.
   

   poly2str(deriv(p))
   poly2str(deriv(q))
   

   [1] "10*X^4 + -4*X^3 + -2*X^0"
   [1] "4*X^3 + 14*X^1"

3.5. Multiplication interne   HARD

p1 <- make_poly(c(1,1))
p2 <- make_poly(c(-1,1))

poly2str(p1)
poly2str(p2)
poly2str(mult(p1,p2))
print("")

p3 <- make_poly(c(1,-1,1))
poly2str(p3)
poly2str(p3)
poly2str(mult(p3,p3))

[1] "1*X^1 + 1*X^0"
[1] "1*X^1 + -1*X^0"
[1] "1*X^2 + -1*X^0"
[1] ""
[1] "1*X^2 + -1*X^1 + 1*X^0"
[1] "1*X^2 + -1*X^1 + 1*X^0"
[1] "1*X^4 + -2*X^3 + 3*X^2 + -2*X^1 + 1*X^0"

3.6. Évaluation d’un polynôme p en un point x.   KEY

1. p n’est pas une fonction, mais on peut toujours créer une fonction associée au polynôme !
   
2. Programmez la fonction polyval(p,x) calculant naïvement \(\sum a_i X^i\).
   

   poly2str(p)
   for(i in -1:1) {
     print(paste("p(",i,") = ",polyval(p,i), sep=""))
   }
   poly2str(q)
   for(i in -1:1) {
     print(paste("q(",i,") = ",polyval(q,i), sep=""))
   }
   

   [1] "2*X^5 + -1*X^4 + -2*X^1"
   [1] "p(-1) = -1"
   [1] "p(0) = 0"
   [1] "p(1) = -1"
   [1] "1*X^4 + 7*X^2 + -1*X^0"
   [1] "q(-1) = 7"
   [1] "q(0) = -1"
   [1] "q(1) = 7"

3. Programmez la fonction polyhorn(p,x) avec la méthode de Horner.
   

   poly2str(p)
   for(i in -1:1) {
     print(paste("p(",i,") = ",polyhorn(p,i), sep=""))
   }
   poly2str(q)
   for(i in -1:1) {
     print(paste("q(",i,") = ",polyhorn(q,i), sep=""))
   }
   

   [1] "2*X^5 + -1*X^4 + -2*X^1"
   [1] "p(-1) = -1"
   [1] "p(0) = 0"
   [1] "p(1) = -1"
   [1] "1*X^4 + 7*X^2 + -1*X^0"
   [1] "q(-1) = 7"
   [1] "q(0) = -1"
   [1] "q(1) = 7"

4. Comparez les implémentations grâce au code ci-dessous.
   

   x <- seq(2-0.02,2.02,length.out=1001)
   vec <- c(-2,0,1)
   ## p(x) = (x^2-2)^16
   p1 <- make_poly(vec)
   for(i in 1:4) {
     p1 <- mult(p1,p1)
   }
   ## Evaluate p using our methods (observed)
   vn <- sapply(x, polyval, p=p1)
   vh <- sapply(x, polyhorn, p=p1)
   
   
   library("polynom")
   ## Evaluate p using R package (expected)
   pr <-as.polynomial(c(-2,0,1))
   ## p is an R object ! I directly used the power operator.
   pr <- pr ** 16
   ## I also use a generic function
   vr <- predict(pr,x)
   
   ## Last, visualize the results
   cols <- c("red", "gold")
   matplot(x, cbind(vn-vr,vh-vr),t="l", lwd=2, lty=1,col=cols, xlab="x",ylab="P(x)-P^R(x)")
   legend("topleft", inset=.05, legend=c("Naive", "Horner"), horiz=TRUE, lwd=2, lty=1, col=cols)
   

   

3.7. Visualisation

x <- seq(-2,4,length.out=1000)
p1 <- make_poly(c(-1,-1,1))
dessiner(p1,x)