Discrétisation

Une solution d'une équation aux dérivées partielles discrétisée, obtenue par la méthode des éléments finis.

En mathématiques appliquées, la discrétisation est la transposition d'un état continu (fonction, modèle, variable, équation) en un équivalent discret. Ce procédé constitue en général une étape préliminaire à la résolution numérique d'un problème ou sa programmation sur machine. Un cas particulier est la dichotomisation où le nombre de classes discrètes est 2, où on peut approcher une variable continue en une variable binaire.

La discrétisation est aussi reliée aux mathématiques discrètes, et compte parmi les composantes importantes de la programmation granulaire. Dans le contexte, la discrétisation peut renvoyer à la modification de la granularité, quand plusieurs variables discrètes sont réunies ou des catégories discrètes fusionnées.

Discrétiser des données continues engendre systématiquement une erreur de discrétisation (en). Un des objectifs est donc de concevoir un modèle discret qui minimise au mieux cette erreur.

Il ne faut pas confondre discrétisation et quantification.

On compte également la méthode d'Euler-Maruyama (en) et le bloqueur d'ordre 0 parmi les méthodes de discrétisation.

Discrétisation de modèles d'état linéaires

La discrétisation apparait dans la transformation d'équations différentielles continues en équations aux différence discrètes.

On considère le modèle d'état en espace, continu en temps :

${\begin{aligned}{\dot {\mathbf {x} }}(t)&=\mathbf {A} \mathbf {x} (t)+\mathbf {B} \mathbf {u} (t)+\mathbf {w} (t)\\\mathbf {y} (t)&=\mathbf {C} \mathbf {x} (t)+\mathbf {D} \mathbf {u} (t)+\mathbf {v} (t)\end{aligned}}$

où v et w sont des sources de bruit blanc avec une densité spectrale de puissance

$\mathbf {w} (t)\sim {\mathcal {N}}(0,\mathbf {Q} )\ ,\ \mathbf {v} (t)\sim {\mathcal {N}}(0,\mathbf {R} )$

peuvent être discrétisées, en supposant que le signal u est un bloqueur d'ordre 0 et une intégration continue pour le bruit v, donnant

${\begin{aligned}\mathbf {x} [k+1]&=\mathbf {A} _{d}\mathbf {x} [k]+\mathbf {B} _{d}\mathbf {u} [k]+\mathbf {w} [k]\\\mathbf {y} [k]&=\mathbf {C} _{d}\mathbf {x} [k]+\mathbf {D} _{d}\mathbf {u} [k]+\mathbf {v} [k]\end{aligned}}$

avec des covariances

$\mathbf {w} [k]\sim {\mathcal {N}}(0,\mathbf {Q} _{d})\ ,\ \mathbf {v} [k]\sim {\mathcal {N}}(0,\mathbf {R} _{d})$

où

$\mathbf {A} _{d}=\mathrm {e} ^{\mathbf {A} T}={\mathcal {L}}^{-1}\{(s\mathbf {I} -\mathbf {A} )^{-1}\}_{t=T}$

$\mathbf {B} _{d}=\left(\int _{\tau =0}^{T}\mathrm {e} ^{\mathbf {A} \tau }\mathrm {d} \tau \right)\mathbf {B} =\mathbf {A} ^{-1}(\mathbf {A} _{d}-I)\mathbf {B}$, si A est régulière

$\mathbf {C} _{d}=\mathbf {C}$

$\mathbf {D} _{d}=\mathbf {D}$

$\mathbf {Q} _{d}=\int _{\tau =0}^{T}\mathrm {e} ^{\mathbf {A} \tau }\mathbf {Q} \mathrm {e} ^{\mathbf {A} ^{\top }\tau }\,\mathrm {d} \tau$

$\mathbf {R} _{d}={\frac {1}{T}}\mathbf {R}$

et T est le temps d'échantillonnage, et $\mathbf {A} ^{\top }$ est la transposée de A.

Une astuce pour calculer A_d et B_d en une étape consiste à utiliser la propriété

$\exp \left(T{\begin{bmatrix}\mathbf {A} &\mathbf {B} \\\mathbf {0} &\mathbf {0} \end{bmatrix}}\right)={\begin{bmatrix}\mathbf {M_{11}} &\mathbf {M_{12}} \\\mathbf {0} &\mathbf {I} \end{bmatrix}}$

et donc

$\mathbf {A} _{d}=\mathbf {M} _{11},\quad \mathbf {B} _{d}=\mathbf {M} _{12}.$

Discrétisation de bruits

L'évaluation numérique de Q_d est rendue plus délicate avec l'intégrale d'une exponentielle de matrice. On peut la calculer en deux temps, d'abord la construction de la matrice, puis le calcul de son exponentielle

$\mathbf {F} ={\begin{bmatrix}-\mathbf {A} &\mathbf {Q} \\\mathbf {0} &\mathbf {A} ^{\top }\end{bmatrix}}T$

$\mathbf {G} =\mathrm {e} ^{\mathbf {F} }={\begin{bmatrix}\dots &\mathbf {A} _{d}^{-1}\mathbf {Q} _{d}\\\mathbf {0} &\mathbf {A} _{d}^{\top }\end{bmatrix}}.$

Le bruit discrétisé est ensuite évalué en multipliant la transposée du bloc en bas à droite de G avec celui en haut à droite :

$\mathbf {Q} _{d}=(\mathbf {A} _{d}^{\top })^{\top }(\mathbf {A} _{d}^{-1}\mathbf {Q} _{d})=\mathbf {A} _{d}(\mathbf {A} _{d}^{-1}\mathbf {Q} _{d}).$

Dérivation

En partant du modèle continu

$\mathbf {\dot {x}} (t)=\mathbf {A} \mathbf {x} (t)+\mathbf {B} \mathbf {u} (t)$

on sait que l'exponentielle de matrice est

${\frac {\mathrm {d} }{\mathrm {d} t}}\mathrm {e} ^{\mathbf {A} t}=\mathbf {A} \mathrm {e} ^{\mathbf {A} t}=\mathrm {e} ^{\mathbf {A} t}\mathbf {A}$

et en multipliant à gauche le modèle :

$\mathrm {e} ^{-\mathbf {A} t}\mathbf {\dot {x}} (t)=\mathrm {e} ^{-\mathbf {A} t}\mathbf {A} \mathbf {x} (t)+\mathrm {e} ^{-\mathbf {A} t}\mathbf {B} \mathbf {u} (t)$

on reconnait

${\frac {\mathrm {d} }{\mathrm {d} t}}(\mathrm {e} ^{-\mathbf {A} t}\mathbf {x} (t))=\mathrm {e} ^{-\mathbf {A} t}\mathbf {B} \mathbf {u} (t)$

L'intégration donne ainsi

$\mathrm {e} ^{-\mathbf {A} t}\mathbf {x} (t)-\mathrm {e} ^{0}\mathbf {x} (0)=\int _{0}^{t}\mathrm {e} ^{-\mathbf {A} \tau }\mathbf {B} \mathbf {u} (\tau )\,\mathrm {d} \tau$

$\mathbf {x} (t)=\mathrm {e} ^{\mathbf {A} t}\mathbf {x} (0)+\int _{0}^{t}\mathrm {e} ^{\mathbf {A} (t-\tau )}\mathbf {B} \mathbf {u} (\tau )\,\mathrm {d} \tau$

ce qui est une solution analytique du modèle continu.

On veut désormais discrétiser cette expression. On suppose u constante sur chaque pas de temps.

$\mathbf {x} [k]\ {\stackrel {\mathrm {def} }{=}}\ \mathbf {x} (kT)=\mathrm {e} ^{\mathbf {A} kT}\mathbf {x} (0)+\int _{0}^{kT}\mathrm {e} ^{\mathbf {A} (kT-\tau )}\mathbf {B} \mathbf {u} (\tau )\,\mathrm {d} \tau$

$\mathbf {x} [k+1]=\mathrm {e} ^{\mathbf {A} (k+1)T}\mathbf {x} (0)+\int _{0}^{(k+1)T}\mathrm {e} ^{\mathbf {A} ((k+1)T-\tau )}\mathbf {B} \mathbf {u} (\tau )\,\mathrm {d} \tau =\mathrm {e} ^{\mathbf {A} T}\left[\mathrm {e} ^{\mathbf {A} kT}\mathbf {x} (0)+\int _{0}^{kT}\mathrm {e} ^{\mathbf {A} (kT-\tau )}\mathbf {B} \mathbf {u} (\tau )\,\mathrm {d} \tau \right]+\int _{kT}^{(k+1)T}\mathrm {e} ^{\mathbf {A} (kT+T-\tau )}\mathbf {B} \mathbf {u} (\tau )\,\mathrm {d} \tau$

On reconnait l'expression entre crochets dans le premier terme comme x[k], et le second terme peut être simplifié en faisant la substitution v(τ) = kT + T – τ, ce qui permet d τ = – d v. On suppose aussi que u est constante dans l'intégrale, ce qui donne :

${\begin{aligned}\mathbf {x} [k+1]&=&\mathrm {e} ^{\mathbf {A} T}\mathbf {x} [k]-\left(\int _{v(kT)}^{v((k+1)T)}\mathrm {e} ^{\mathbf {A} v}\,\mathrm {d} v\right)\mathbf {B} \mathbf {u} [k]\\&=&\mathrm {e} ^{\mathbf {A} T}\mathbf {x} [k]-\left(\int _{T}^{0}\mathrm {e} ^{\mathbf {A} v}\,\mathrm {d} v\right)\mathbf {B} \mathbf {u} [k]\\&=&\mathrm {e} ^{\mathbf {A} T}\mathbf {x} [k]+\left(\int _{0}^{T}\mathrm {e} ^{\mathbf {A} v}\,\mathrm {d} v\right)\mathbf {B} \mathbf {u} [k]\\&=&\mathrm {e} ^{\mathbf {A} T}\mathbf {x} [k]+\mathbf {A} ^{-1}\left(\mathrm {e} ^{\mathbf {A} T}-\mathbf {I} \right)\mathbf {B} \mathbf {u} [k]\end{aligned}}$

qui est une solution exacte du problème de discrétisation.

Approximations

Une discrétisation exacte peut parfois être impossible à cause d'une exponentielle de matrice lourde et des étapes d'intégrations. Il devient alors plus simple de calculer un modèle discret approché, basé sur de petits pas de temps de sorte qu'on ait $\mathrm {e} ^{\mathbf {A} T}\approx \mathbf {I} +\mathbf {A} T$. La solution approchée devient alors :

$\mathbf {x} [k+1]\approx (\mathbf {I} +\mathbf {A} T)\mathbf {x} [k]+T\mathbf {B} \mathbf {u} [k].$

D'autres approximations possibles sont $\mathrm {e} ^{\mathbf {A} T}\approx \left(\mathbf {I} -\mathbf {A} T\right)^{-1}$ et $\mathrm {e} ^{\mathbf {A} T}\approx \left(\mathbf {I} +{\frac {1}{2}}\mathbf {A} T\right)\left(\mathbf {I} -{\frac {1}{2}}\mathbf {A} T\right)^{-1}$. Chacun a des propriétés de stabilité différentes. On peut également mentionner la transformation bilinéaire, ou transformation de Tustin, qui préserve les propriétés de stabilité du système continu en temps.

Discrétisation d'équations différentielles

Le découpage d'un domaine en sous-domaines simples (ici, par une triangulation) est une première étape de discrétisation de l’espace avant la résolution numérique.

La résolution numérique d'une équation différentielle (ordinaire ou aux dérivées partielles) nécessite une discrétisation du domaine de définition de la solution (espace ou temps, voire les deux). Ainsi, d'une fonction u(x , t) définie sur un domaine Ω et un intervalle de temps [0 ; T], on ne calculera que des valeurs (u(x_i , tⁿ)), où les x_i sont des points de Ω et tⁿ des instants de [0 ; T]. Pour cela, les opérateurs différentiels sont également approchés par des versions discrètes, comme la dérivée seconde discrète :

${\frac {\partial ^{2}u}{\partial x^{2}}}\simeq {\frac {u_{i-1}-u_{i}}{x_{i-1}-x_{i}}}+{\frac {u_{i+1}-u_{i}}{x_{i+1}-x_{i}}}.$

La méthode de résolution (différences finies, éléments finis ou volumes finis, pour citer les plus courantes) permet de construire un problème discret dont la solution est une approximation de la solution du problème continu. L'erreur commise a deux sources :

• l'erreur de projection : en passant d'un espace continu à un espace discret, l'espace dans lequel la solution existante est changée ;
• l'erreur d'interpolation : le choix du schéma numérique et la définition de la grille espace-temps choisie pour la résolution va influer sur la qualité de l'approximation.

Discrétisation de caractéristiques continues

En statistique et apprentissage machine, la discrétisation renvoie à la conversion de variables ou caractéristiques continues en variables ou caractéristiques discrètes nominales. Ce procédé est utile pour créer des fonctions de densité de probabilités.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Discretization » (voir la liste des auteurs).

Voir aussi

Articles connexes

• Espace discret
• Algèbre temporelle
• Simulation à événements discrets
• Simulation stochastique
• Méthode des volumes finis pour des flux instables
• Temps discret et temps continu

Liens externes

• Robert Grover Brown & Patrick Y. C. Hwang, Introduction to random signals and applied Kalman filtering : with MATLAB exercises and solutions, 3rd, 1997, 484 p. (ISBN 978-0-471-12839-7)
• Chi-Tsong Chen, Linear System Theory and Design, Philadelphia, PA, USA, Saunders College Publishing, 1984 (ISBN 0-03-071691-8)
• (en) Charles Van Loan, « Computing integrals involving the matrix exponential », IEEE transactions on automatic control, vol. 23, n^o 3,‎ 1978, p. 395-404
• R.H. Middleton et G.C. Goodwin, Digital control and estimation : a unified approach, 1990, 33 p. (ISBN 0-13-211665-0)