Le calcul différentiel discret

La convention du sujet est la différence en avant de pas $1$ : $\Delta P(X)=P(X+1)-P(X)$. Toutes les formules ci-dessous utilisent cette convention.

I — Une dérivée sans limite ?

1. On obtient

$$\Delta 1=0,$$ $$\Delta X=1,$$ $$\Delta X^2=2X+1,$$

et

$$\Delta X^3=3X^2+3X+1.$$

Comme la dérivation usuelle, $\Delta$ annule les constantes et abaisse ici le degré d'une unité. Mais les termes de degré inférieur ne disparaissent pas : par exemple $(X^2)'=2X$ tandis que $\Delta X^2=2X+1$.

(a) Pour $\lambda,\mu\in\mathbb R$ et $P,Q\in\mathbb R[X]$,

$$\begin{aligned} \Delta(\lambda P+\mu Q)(X) &=(\lambda P+\mu Q)(X+1)-(\lambda P+\mu Q)(X)\\ &=\lambda\bigl(P(X+1)-P(X)\bigr) +\mu\bigl(Q(X+1)-Q(X)\bigr). \end{aligned}$$

Ainsi

$$\Delta(\lambda P+\mu Q)=\lambda\Delta P+\mu\Delta Q.$$

Donc $\Delta$ est linéaire.

(b) Écrivons

$$P(X)=a_dX^d+\text{termes de degré inférieur}, \qquad a_d\neq0.$$

Alors

$$P(X+1)-P(X) =a_d\bigl((X+1)^d-X^d\bigr)+R(X),$$

où $R=0$ si $d=1$, et $\deg R\leqslant d-2$ si $d\geqslant2$. Or, par la formule du binôme,

$$(X+1)^d-X^d=dX^{d-1}+\text{termes de degré au plus }d-2.$$

Par conséquent

$$\boxed{\deg(\Delta P)=d-1}$$

et le coefficient dominant de $\Delta P$ vaut

$$\boxed{d\,a_d}.$$

(c) Toutes les constantes appartiennent à $\ker\Delta$. Réciproquement, si $P$ n'est pas constant, alors $\deg(\Delta P)=\deg P-1$, donc $\Delta P\neq0$. Ainsi

$$\boxed{\ker\Delta=\mathbb R}.$$

(a) On écrit

$$P(X+1)=P(X)+\Delta P(X), \qquad Q(X+1)=Q(X)+\Delta Q(X).$$

Donc

$$\begin{aligned} \Delta(PQ) &=P(X+1)Q(X+1)-P(X)Q(X)\\ &=(P+\Delta P)(Q+\Delta Q)-PQ\\ &=P\,\Delta Q+Q\,\Delta P+(\Delta P)(\Delta Q). \end{aligned}$$

Ainsi

$$\boxed{\Delta(PQ)=P\,\Delta Q+Q\,\Delta P+(\Delta P)(\Delta Q)}.$$

(b) En ajoutant et retranchant $P(X+1)Q(X)$,

$$\begin{aligned} \Delta(PQ) &=P(X+1)\bigl(Q(X+1)-Q(X)\bigr)\\ &\quad+Q(X)\bigl(P(X+1)-P(X)\bigr), \end{aligned}$$

d'où

$$\boxed{\Delta(PQ)=P(X+1)\,\Delta Q+Q\,\Delta P}.$$

Une formule symétrique s'obtient en échangeant $P$ et $Q$ :

$$\Delta(PQ)=P\,\Delta Q+Q(X+1)\,\Delta P.$$

Il existe donc bien une règle de produit, mais $\Delta$ n'est pas une dérivation au sens algébrique : la règle de Leibniz usuelle doit être corrigée par le terme $(\Delta P)(\Delta Q)$, ou bien par un décalage d'un des facteurs.

(a) Si $P\in E_n$, alors $\Delta P\in E_{n-1}$ lorsque $P$ est non constant, et $\Delta P=0$ lorsqu'il est constant. Donc $\Delta(E_n)\subset E_n$. Avec la linéarité de la question 2, $\Delta$ induit bien un endomorphisme de $E_n$.

(b) Pour $n\geqslant1$, le noyau de la restriction de $\Delta$ à $E_n$ est l'espace des constantes, de dimension $1$. Le théorème du rang donne donc

$$\dim\operatorname{Im}\Delta=(n+1)-1=n.$$

Or $\operatorname{Im}\Delta\subset E_{n-1}$ et $\dim E_{n-1}=n$. Par conséquent

$$\boxed{\operatorname{Im}\Delta=E_{n-1}}.$$

(c) Chaque application de $\Delta$ abaisse d'au moins une unité le degré d'un polynôme non constant. Ainsi

$$\boxed{\Delta^{n+1}=0\quad\text{sur }E_n}.$$

Si le coefficient de $X^n$ dans $P$ est $a_n$, les coefficients dominants sont multipliés successivement par

$$n,\ n-1,\ldots,1.$$

On obtient donc

$$\boxed{\Delta^nP=n!\,a_n}.$$

II — Les bons monômes du monde discret

(a) Pour $k=0$, $B_0=1$. Pour $k\geqslant1$, le numérateur de $B_k$ est un produit de $k$ polynômes unitaires de degré $1$. Ainsi

$$\deg B_k=k$$

et son coefficient dominant vaut

$$\frac1{k!}.$$

(b) Les polynômes $B_0,\ldots,B_n$ ont des degrés deux à deux distincts, donc la famille est libre. Elle comporte $n+1$ éléments dans $E_n$, qui est de dimension $n+1$. Ainsi

$$\boxed{(B_0,\ldots,B_n)\text{ est une base de }E_n}.$$

(a) On a

$$\Delta B_0=0, \qquad \Delta B_1=1=B_0.$$

De plus,

$$B_2(X)=\frac{X(X-1)}2,$$

donc

$$\Delta B_2(X) =\frac{(X+1)X-X(X-1)}2 =X=B_1(X).$$

Enfin,

$$B_3(X)=\frac{X(X-1)(X-2)}6,$$

et

$$\begin{aligned} \Delta B_3(X) &=\frac{(X+1)X(X-1)-X(X-1)(X-2)}6\\ &=\frac{X(X-1)}6\bigl((X+1)-(X-2)\bigr)\\ &=\frac{X(X-1)}2 =B_2(X). \end{aligned}$$

La régularité suggère que $\Delta$ décale l'indice d'une unité vers le bas.

(b) Pour $k\geqslant1$,

$$\begin{aligned} B_k(X+1)-B_k(X) &=\frac{(X+1)X\cdots(X-k+2)-X(X-1)\cdots(X-k+1)}{k!}\\ &=\frac{X(X-1)\cdots(X-k+2)}{k!} \bigl((X+1)-(X-k+1)\bigr)\\ &=\frac{k\,X(X-1)\cdots(X-k+2)}{k!}\\ &=B_{k-1}(X). \end{aligned}$$

Donc

$$\boxed{\Delta B_k=B_{k-1}\quad(k\geqslant1)},$$

avec $\Delta B_0=0$.

(a) Si $j\leqslant k$, on applique $j$ fois la relation précédente :

$$\Delta^jB_k=B_{k-j}.$$

Si $j>k$, après $k$ différences on obtient $B_0$, puis la différence suivante est nulle. Ainsi

$$\boxed{ \Delta^jB_k= \begin{cases} B_{k-j},&j\leqslant k,\\ 0,&j>k. \end{cases}}$$

Cette formule contient bien le cas $j=0$.

(b) Dans la base $(B_0,B_1,\ldots,B_n)$,

$$\Delta B_0=0,\quad \Delta B_1=B_0,\quad\ldots,\quad \Delta B_n=B_{n-1}.$$

Donc

$$\operatorname{Mat}(\Delta)= \begin{pmatrix} 0&1&0&\cdots&0\\ 0&0&1&\ddots&\vdots\\ \vdots&\ddots&\ddots&\ddots&0\\ 0&\cdots&0&0&1\\ 0&\cdots&\cdots&0&0 \end{pmatrix}.$$

(c) Si $C_k=X^k/k!$, alors pour $k\geqslant1$,

$$C_k'=C_{k-1},$$

et $C_0'=0$. La dérivation dans la base $(C_0,\ldots,C_n)$ a donc exactement la même matrice. C'est le parallèle structurel précis entre les deux opérateurs.

8. La relation de la question 6 s'écrit

$$B_k(X+1)-B_k(X)=B_{k-1}(X),$$

donc

$$\boxed{B_k(X+1)=B_k(X)+B_{k-1}(X)}.$$

Pour $m\in\mathbb N$, on obtient

$$\binom{m+1}{k} = \binom{m}{k} + \binom{m}{k-1},$$

c'est-à-dire la relation de Pascal.

III — Une formule de Taylor sur une grille

(a) On a

$$\Delta^2f(x) =\Delta f(x+1)-\Delta f(x) =f(x+2)-2f(x+1)+f(x).$$

Puis

$$\begin{aligned} \Delta^3f(x) &=\Delta^2f(x+1)-\Delta^2f(x)\\ &=f(x+3)-3f(x+2)+3f(x+1)-f(x). \end{aligned}$$

(b) Les coefficients sont les coefficients binomiaux, avec des signes alternés. On conjecture

$$\boxed{ \Delta^kf(x) = \sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j}f(x+j)}.$$

Pour $k=0$, le membre de droite vaut bien $f(x)$.

(c) Supposons la formule vraie à l'ordre $k$. Alors

$$\begin{aligned} \Delta^{k+1}f(x) &=\Delta^kf(x+1)-\Delta^kf(x)\\ &=\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}f(x+j+1) -\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}f(x+j). \end{aligned}$$

Dans la première somme, on pose $r=j+1$. Pour $1\leqslant r\leqslant k$, le coefficient de $f(x+r)$ devient

$$(-1)^{k-r+1}\binom{k}{r-1} -(-1)^{k-r}\binom{k}{r} = (-1)^{k+1-r}\binom{k+1}{r},$$

par la relation de Pascal. Les deux termes extrêmes ont également les coefficients attendus. On obtient donc la formule à l'ordre $k+1$.

(a) Partons de

$$P=\sum_{k=0}^{n}a_kB_k.$$

Pour $j\in\{0,\ldots,n\}$,

$$\Delta^jP = \sum_{k=j}^{n}a_kB_{k-j}.$$

En $X=0$, on a $B_0(0)=1$ et $B_r(0)=0$ pour $r\geqslant1$. Il reste donc uniquement le terme $k=j$ :

$$\boxed{\Delta^jP(0)=a_j}.$$

(b) Les coordonnées de $P$ dans la base $(B_0,\ldots,B_n)$ sont donc

$$a_j=\Delta^jP(0).$$

La formule de reconstruction est

$$\boxed{ P(X)=\sum_{k=0}^{n}\Delta^kP(0)\,B_k(X)}.$$

C'est la formule de Newton discrète dans ce cadre.

(c) La formule de Taylor polynomiale en $0$ s'écrit

$$P(X)=\sum_{k=0}^{n}\frac{P^{(k)}(0)}{k!}X^k.$$

Dans le calcul continu, les polynômes $X^k/k!$ satisfont

$$\left(\frac{X^k}{k!}\right)'=\frac{X^{k-1}}{(k-1)!}.$$

Dans le calcul discret, les $B_k$ satisfont

$$\Delta B_k=B_{k-1}.$$

Les $B_k$ jouent donc le rôle des monômes divisés adaptés à $\Delta$, et les dérivées successives en $0$ sont remplacées par les différences successives en $0$.

(a) La question 9 donne, en $x=0$,

$$\boxed{ \Delta^kP(0) = \sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j}P(j)}.$$

Ainsi chaque coordonnée de $P$ dans la base $(B_k)$ dépend uniquement des valeurs $P(0),\ldots,P(k)$.

En substituant dans la formule de Newton, on peut aussi écrire

$$P(X)= \sum_{k=0}^{n} \left( \sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j}P(j) \right)B_k(X).$$

(b) Les valeurs $P(0),\ldots,P(n)$ déterminent donc toutes les coordonnées de $P$ dans la base $(B_0,\ldots,B_n)$, donc déterminent $P$ lui-même.

On retrouve ici, pour les nœuds équidistants $0,1,\ldots,n$, une autre forme de l'unicité connue par l'interpolation de Lagrange.

(a) La table des différences en avant est

$$\begin{array}{c|cccc} j&0&1&2&3\\ \hline P(j)&2&3&8&23\\ \Delta P(j)&1&5&15&\\ \Delta^2P(j)&4&10&&\\ \Delta^3P(j)&6&&& \end{array}$$

Ainsi

$$P(0)=2,\qquad \Delta P(0)=1,\qquad \Delta^2P(0)=4,\qquad \Delta^3P(0)=6.$$

(b) La formule de Newton donne

$$P=2B_0+B_1+4B_2+6B_3.$$

Or

$$B_1=X,\qquad B_2=\frac{X(X-1)}2,\qquad B_3=\frac{X(X-1)(X-2)}6.$$

Donc

$$\begin{aligned} P(X) &=2+X+2X(X-1)+X(X-1)(X-2)\\ &=X^3-X^2+X+2. \end{aligned}$$

IV — Primitives discrètes et sommes exactes

(a) Si

$$P=\sum_{k=0}^{n}a_kB_k,$$

alors, puisque $\Delta B_{k+1}=B_k$,

$$Q=\sum_{k=0}^{n}a_kB_{k+1}$$

vérifie $\Delta Q=P$. Plus généralement,

$$\boxed{ Q=C+\sum_{k=0}^{n}a_kB_{k+1}}$$

est une primitive discrète pour tout $C\in\mathbb R$.

(b) Si $Q_1$ et $Q_2$ sont deux primitives discrètes de $P$, alors

$$\Delta(Q_1-Q_2)=0.$$

Donc $Q_1-Q_2$ est constant.

(c) Soit $P$ non nul de degré $d$ et de coefficient dominant $a$. Si $Q$ est une primitive discrète de degré $r$, alors

$$\deg(\Delta Q)=r-1.$$

Comme $\Delta Q=P$, on a $r=d+1$. Si $b$ est le coefficient dominant de $Q$, alors le coefficient dominant de $\Delta Q$ vaut $(d+1)b$. Ainsi

$$(d+1)b=a,$$

donc

$$\boxed{b=\frac{a}{d+1}}.$$

(a) Pour tout entier $m$,

$$P(m)=Q(m+1)-Q(m).$$

Par télescopage,

$$\begin{aligned} \sum_{m=a}^{b-1}P(m) &=\sum_{m=a}^{b-1}\bigl(Q(m+1)-Q(m)\bigr)\\ &=Q(b)-Q(a). \end{aligned}$$

Donc

$$\boxed{ \sum_{m=a}^{b-1}P(m)=Q(b)-Q(a)}.$$

(b) Pour une primitive usuelle $F$ de $f$,

$$\int_a^b f(x)\,dx=F(b)-F(a).$$

La somme finie joue ici le rôle de l'intégrale, tandis que $\Delta Q=P$ joue le rôle de $Q'=P$.

15. Comme $\Delta B_{k+1}=B_k$, le polynôme $B_{k+1}$ est une primitive discrète de $B_k$. La question 14 donne donc

$$\sum_{m=0}^{n-1}B_k(m) = B_{k+1}(n)-B_{k+1}(0).$$

Or $B_{k+1}(0)=0$. Ainsi

$$\boxed{ \sum_{m=0}^{n-1}B_k(m) = B_{k+1}(n) = \binom{n}{k+1}}.$$

Le cas $n=0$ est cohérent : la somme vide vaut $0$.

(a) Pour $P=X$,

$$P(0)=0,\qquad \Delta P(0)=1,$$

d'où

$$\boxed{X=B_1}.$$

Pour $P=X^2$,

$$\Delta P=2X+1,\qquad \Delta^2P=2,$$

donc

$$\boxed{X^2=B_1+2B_2}.$$

Pour $P=X^3$,

$$\Delta P=3X^2+3X+1,$$ $$\Delta^2P=6X+6,$$

et

$$\Delta^3P=6.$$

Ainsi

$$\boxed{X^3=B_1+6B_2+6B_3}.$$

(b) En utilisant la question 15,

$$\sum_{m=0}^{n-1}m = B_2(n) = \boxed{\frac{n(n-1)}2}.$$

Ensuite,

$$\begin{aligned} \sum_{m=0}^{n-1}m^2 &=B_2(n)+2B_3(n)\\ &=\frac{n(n-1)}2+\frac{n(n-1)(n-2)}3\\ &=\boxed{\frac{n(n-1)(2n-1)}6}. \end{aligned}$$

Enfin,

$$\begin{aligned} \sum_{m=0}^{n-1}m^3 &=B_2(n)+6B_3(n)+6B_4(n)\\ &=\boxed{\frac{n^2(n-1)^2}{4}}. \end{aligned}$$

17. D'après la question 13, $P$ possède une primitive discrète $Q$. Choisissons-la de sorte que $Q(0)=0$. Alors, pour tout $n\in\mathbb N$,

$$\sum_{m=0}^{n-1}P(m)=Q(n).$$

La fonction considérée coïncide donc sur $\mathbb N$ avec le polynôme $Q$. Si $P$ est de degré $d$ et de coefficient dominant $a$, alors $Q$ est de degré $d+1$ et de coefficient dominant

$$\boxed{\frac{a}{d+1}}.$$

(a) Si $u_n=P(n)$ avec $\deg P\leqslant d$, alors

$$(\Delta u)_n=(\Delta P)(n).$$

Par récurrence,

$$(\Delta^ku)_n=(\Delta^kP)(n).$$

Or $\Delta^{d+1}P=0$. Donc

$$\boxed{\Delta^{d+1}u=0}.$$

(b) La formule de reconstruction de la partie III suggère de poser

$$R(X)=\sum_{k=0}^{d}(\Delta^ku)_0\,B_k(X).$$

Alors $R\in\mathbb R_d[X]$ et, pour tout $j\in\{0,\ldots,d\}$,

$$\Delta^jR(0)=(\Delta^ju)_0.$$

Posons

$$v_n=u_n-R(n).$$

On a donc

$$(\Delta^jv)_0=0$$

pour $0\leqslant j\leqslant d$. De plus,

$$\Delta^{d+1}v=0,$$

car $\Delta^{d+1}u=0$ par hypothèse et $\Delta^{d+1}R=0$.

La suite $\Delta^dv$ a donc une différence nulle : elle est constante. Comme son premier terme vaut $0$, on obtient

$$\Delta^dv=0.$$

Alors $\Delta^{d-1}v$ est constante et son premier terme vaut encore $0$, donc

$$\Delta^{d-1}v=0.$$

En répétant l'argument, on descend jusqu'à

$$v=0.$$

Ainsi, pour tout $n\in\mathbb N$,

$$u_n=R(n).$$

(c) On a finalement

$$\boxed{ \Delta^{d+1}u=0 \quad\Longleftrightarrow\quad \exists P\in\mathbb R_d[X],\ \forall n\in\mathbb N,\ u_n=P(n)}.$$

Cette équivalence résume l'architecture du devoir : dans la base $(B_k)$, l'opérateur $\Delta$ devient un décalage ; la formule de Newton reconstruit un polynôme à partir de ses différences initiales ; et l'inversion de $\Delta$ transforme les sommes en primitives discrètes.

Sources

[SOURCE] Programme officiel de mathématiques de MPSI, Ministère de l'Éducation nationale : polynômes, formule de Taylor polynomiale, interpolation de Lagrange, espaces vectoriels, applications linéaires, sommes et coefficients binomiaux. Lien direct

[SOURCE] Isaac Newton, Analysis per quantitatum series, fluxiones, ac differentias (Londres, 1711), volume contenant la Methodus differentialis. Notice et exemplaire numérisé de la Library of Congress. Lien direct

[SOURCE] Duncan C. Fraser, « Newton's Interpolation Formulas », Journal of the Institute of Actuaries, vol. 51, no 2, octobre 1918, p. 77-106, DOI 10.1017/S0020268100028407. Étude historique des textes de Newton sur l'interpolation par différences finies. Lien direct

[SOURCE] Charles Jordan, Calculus of Finite Differences, 3e éd., AMS Chelsea Publishing, 1965. Référence classique sur les opérateurs de différence, l'interpolation et la sommation discrète. Lien direct