Théorie > Algèbre > Analyse discrète


Général

Résumé Chapitre entier

Points théoriques

Dérivée discrète Intégration Polynômes de Pochhammer Nombres de Stirling

Exercices

Exercice 1 Exercice 2 Exercice 3 Exercice 4 Exercice 5 Exercice 6 Exercice 7

Polynômes de Pochhammer

Tout cela est bien sympathique mais si l'on ne peut pas calculer explicitement de primitives, ça ne nous avance pas fort. Comment pourrait-on calculer facilement les dérivées et primitives d'un polynôme ? Les deux sections suivantes ont pour but de répondre à cette question. On commence par examiner pourquoi ces opérations sont si simples avec la dérivée usuelle :

Lorsqu'on dérive $P(x)=a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0$, on obtient
$$P'(x) = n a_n x^{n-1} + (n-1) a_{n-1} x^{n-2} + \ldots + 2 a_2 x + a_1$$ et similairement ses primitives sont
$$\int P(u) \,\mathrm du = \frac{a_n}{n+1} x^{n+1} + \frac{a_{n-1}} n x^n + \ldots + \frac{a_1}{2} x^2 + a_0 x + C.$$ Ces formules sympathiques viennent de "polynômes élémentaires" dont les dérivées sont elles-même jolies : on peut construire tout polynôme à base de polynômes de la forme $x^n$, et la dérivée de chaque $x^n$ est simplement $n x^{n-1}$.

Une nouvelle base

Dans le cas discret, le polynôme $x^n$ a pour dérivée $(x+1)^n - x^n$, ce qui est moins sympathique. (Comme vous l'aurez remarqué, dans cette section la sympathie des polynômes est souvent remise en question.) Pour cette raison on va partir d'une autre base de polynômes :

Définition
Pour chaque naturel $n$, on définit le $n^\text{ème}$ polynôme de Pochhammer comme
$$(x)_n := x(x-1)(x-2)\ldots (x-n+1).$$

Ainsi, la liste commence par
\begin{align*}
(x)_0 & = 1 \\
(x)_1 & = x \\
(x)_2 & = x(x-1) \\
(x)_3 & = x(x-1)(x-2)
\end{align*}Comme annoncé, on a une jolie expression pour leurs dérivées :

Proposition (Relation de Pascal 2.0)
Les polynômes de Pochhammer vérifient la relation
$$\Delta (x)_n = n \cdot (x)_{n-1}.$$

Démonstration
Il s'agit d'un simple calcul :
$$\begin{align*}
\Delta (x)_n
& = (x+1)_n - (x)_n \\
& = (x+1)x\ldots(x-n+2) - x(x-1)\ldots(x-n+1) \\
& = \big((x+1)-(x-n+1)\big) \cdot x(x-1)\ldots (x-n+2) \\
& = n \cdot (x)_{n-1}
\end{align*}$$

Remarque
La raison de notre dénomination "Relation de Pascal 2.0" est la suivante : on peut définir les coefficients binomiaux généralisés
$$C^k_x := \frac{x(x-1)\ldots(x-k+1)}{k!} = \frac{(x)_k}{k!}$$ pour tout $x$ réel et $k$ naturel. (C'est une généralisation car, pour $x$ naturel, on retrouve la définition habituelle des coefficients binomiaux.)

Avec cette notation, l'égalité $\Delta(x)_n = n \cdot (x)_{n-1}$ se réécrit comme $\Delta{C^n_x}={C^{n-1}_x}$ ou encore
$$C^n_{x+1} = C^n_x + C^{n-1}_x.$$

Ainsi, si l'on vous donne un polynôme sous la forme $P(x)=b_n(x)_n + b_{n-1}(x)_{n-1}+\ldots+b_1(x)_1+b_0$, vous pourrez calculer sa dérivée
$$\Delta P(x) = nb_n(x)_{n-1} + (n-1)b_{n-1}(x)_{n-2} + \ldots + 2b_2(x)_1+b_1$$ tandis que ses primitives seront
$$\frac{b_n}{n+1}(x)_{n+1}+\frac{b_{n-1}}n(x)_n + \ldots + \frac{b_1}2(x)_2+b_0(x)_1 + C.$$

Comment changer de base ?

On pourrait encore objecter que $P(x)$ ne nous est jamais donné sous cette forme... Il faudrait donc trouver une méthode permettant de passer d'une écriture à l'autre. La première méthode part de l'observation que les $(x)_n$ sont unitaires et de degrés distincts, on peut donc choisir $n=\deg P$ ainsi que $q_n$ son coefficient dominant, puis soustraire $P(x)-q_n\cdot (x)_{n-1}$ afin d'obtenir un reste de degré inférieur (puis itérer). En équations,
$$\begin{eqnarray}
P(x) \;\, & - & \;\; q_n\cdot (x)_n & = & r_{n-1}(x) \\
r_{n-1}(x) \; & - & q_{n-1}\cdot (x)_{n-1} & = & r_{n-2}(x) \\
& & & \;\;\vdots & \\
r_1(x) \; & - & \;\; q_1\cdot (x)_1 & = & r_0(x) \\
r_0(x) \; & - & \;\; q_0\cdot (x)_0 & = & 0
\end{eqnarray}$$ afin d'obtenir $P(x)=q_n(x)_n+q_{n-1}(x)_{n-1}+\ldots+q_1(x)_1+q_0$.

Par exemple, pour $P(x)=x^3$,
$$\begin{eqnarray}
x^3 \hspace{7mm} & - & \; (x)_3 & = & 3x^2 - 2x \\
(3x^2 - 2x) \;& - & 3(x)_2 & = & \hspace{8mm} x \\
x \hspace{9mm} & - & \; (x)_1 & = & \hspace{8mm} 0
\end{eqnarray}$$ et donc $x^3 = (x)_3+3(x)_2+(x)_1$.

Une autre manière d'obtenir les coefficients d'un polynôme dans notre nouvelle base provient de la formule suivante :

Formule de Taylor
Si $P$ est un polynôme de degré $n$ alors
$$P(x) = \sum_{i=0}^n \frac{\Delta^i P(0)}{i!} \cdot (x)_i$$ (où bien sûr $\Delta^0 P=P$). Plus généralement, on a
$$P(x) = \sum_{i=0}^n \frac{\Delta^i P(a)}{i!} \cdot (x-a)_i$$

Démonstration
La preuve est identique à celle de la formule usuelle, présentée dans un chapitre précédent.

Ceci nous donne un autre algorithme pour obtenir les coefficients d'un polynôme dans la base des polynômes de Pochhammer. Nous l'expliquons une nouvelle fois sur l'exemple de $P(x) = x^3$.

  1. On va construire un triangle de coefficients, en commençant par remplir la première ligne avec $P(0), P(1), \ldots, P(n)$ :
    $$\begin{array}{c}
    0 & & 1 & & 8 & & 27 \; \\
    & \,*\, & & \,*\, & & \,*\, & \\
    & & * & & * & & \\
    & & & * & & &
    \end{array}$$
  2. Itérativement, on remplace chaque entrée par la différence entre les deux entrées directement supérieures, spécifiquement celle de droite moins celle de gauche
    $$\begin{array}{c}
    \color\red0 & & 1 & & 8 & & 27 \\
    & \color\red1 & & 7 & & 19 & \\
    & & \color\red6 & & 12 & & \\
    & & & \color\red6 & & &
    \end{array}$$
  3. Finalement, les $\Delta^iP(0)$ sont obtenus en lisant la diagonale descendante (en rouge ci-dessus), en commençant par $\Delta^0P(0)=P(0)$. On obtient les coefficients en divisant par $i!$.
    $$\begin{align} x^3 & = \frac{\color\red0}{0!}\cdot (x)_0 + \frac{\color\red1}{1!}\cdot (x)_1 + \frac{\color\red6}{2!} \cdot (x)_2 + \frac{\color\red6}{3!}\cdot (x)_3 \\ & = (x)_3 + 3(x)_2 + (x)_1. \end{align}$$