Graphe circulant

Graphe circulant

Matrice circulante

En algèbre linéaire, une matrice circulante est une matrice carrée dans laquelle on passe d'une ligne à la suivante par permutation circulaire (décalage vers la droite) des coefficients.

Une matrice circulante de taille n est donc de la forme

C= \begin{pmatrix} c_0 & c_1 & c_2 & \dots & c_{n-1} \\ c_{n-1} & c_0 & c_1 & & c_{n-2} \\ c_{n-2} & c_{n-1} & c_0 & & c_{n-3} \\ \vdots & & & \ddots & \vdots \\ c_1 & c_2 & c_3 & \dots & c_0 \end{pmatrix}

où les coefficients ci sont des complexes.

Une matrice circulante constitue un cas particulier de matrice de Toeplitz, et aussi un cas particulier de carré latin.

La réduction des matrices circulantes fait intervenir les formules de la transformation de Fourier discrète. En analyse numérique, les systèmes circulants peuvent être résolus très efficacement par transformée de Fourier rapide.

On parle parfois de matrice anticirculante ou circulante gauche quand on effectue un décalage à gauche des coefficients en passant d'une ligne à la suivante.

Sommaire

Algèbre des matrices circulantes

Pour alléger les notations, on désigne par C(c0,...,cn − 1) la matrice circulante précédente.

En notant J = C(0,1,0,...,0), on peut constater que toute matrice circulante est un polynôme en J

C(c_0,\dots,c_{n-1}) = \sum_{j=0}^{n-1} c_j J^j=P_C(J)

Réciproquement, comme Jn est la matrice identité, tout polynôme en J est une matrice circulante.

Ainsi la somme, le produit de matrices circulantes sont circulantes, et un tel produit est commutatif. L'ensemble des matrices circulantes n'est autre que l'algèbre commutative des polynômes en J.

Réduction des matrices circulantes

Diagonalisation de J

La matrice J vérifiant Jn = I, elle est diagonalisable sur \mathbb C avec pour valeurs propres des racines n-èmes de l'unité.

On appelle donc \omega= e^{\frac{2i\pi}{n}}, racine primitive de l'unité. On vérifie alors sans peine que pour tout k

X_k = \begin{pmatrix} 1 \\\omega^k \\ \omega^{2k}\\ \vdots\\ \omega^{(n-1)k}\end{pmatrix}

est vecteur propre de J associé à la valeur propre ωk.

On a donc exhibé, pour k allant de 0 à n-1, une famille de n vecteurs propres associés à des valeurs propres distinctes, soit une base de diagonalisation de J.

Diagonalisation d'une matrice circulante

Par conséquent, c'est une base de diagonalisation aussi pour tout polynôme en J, c'est-à-dire toute matrice circulante. Les valeurs propres de C(c0,...,cn − 1) sont donc les

\lambda_k= \sum_{j=0}^{n-1} c_j \omega^{kj}=P_C(\omega^k)

qui, cette fois, ne sont plus nécessairement distinctes.

On peut prendre pour matrice de passage de la base canonique à la base de diagonalisation la matrice U

U= \frac1{\sqrt n}\begin{pmatrix} 1&1&\dots &1 \\ 1& \omega&\dots &\omega^{n-1} \\ \vdots & \vdots & &\vdots \\ 1&\omega^{n-1}&\dots &\omega^{(n-1)^2}\end{pmatrix}

Alors cette matrice U est unitaire (U*U=I) et les formules de passage précédentes s'écrivent, en notant Λ la matrice diagonale de coefficients les valeurs propres

C= U\Lambda U^{-1} =U\Lambda U^* \qquad \Lambda =U^{-1}CU=U^*CU

Une nouvelle définition possible pour l'ensemble des matrices circulantes est l'ensemble des matrices de la forme UDU * avec D diagonale. Géométriquement, cela correspond aux endomorphismes qui admettent la base orthonormale des Xk comme base de vecteurs propres.

Déterminant circulant

Le déterminant circulant est le déterminant de la matrice circulante ; il est égal au produit des valeurs propres

\det C= \prod_{k=0}^{n-1} P_C(\omega^k)

La matrice est inversible si et seulement si son déterminant est non nul, et dans ce cas son inverse est lui aussi une matrice circulante.

Intervention de la transformée de Fourier discrète

Les formules de changement de base à l'aide de la matrice U ont un intérêt particulier. La formule de passage des coefficients aux valeurs propres est la définition classique d'une transformée de Fourier discrète. On peut retrouver les coefficients à partir des valeurs propres en effectuant cette fois une transformée inverse

c_k= \frac1n \sum_{j=0}^{n-1} \lambda_j \omega^{-kj}

Système circulant

Soit le système circulant Cx=b, avec C matrice circulante de taille n. Ce système peut se réécrire à l'aide d'un produit de convolution discret

\mathbf{c} * \mathbf{x} = \mathbf{b}

en notant c la première colonne de la matrice C et en périodisant les composantes des vecteurs c, x et b. La transformée de Fourier discrète transforme cette équation de convolution en un produit composante par composante.

\mathcal{F}_{n}(\mathbf{c} * \mathbf{x}) = \mathcal{F}_{n}(\mathbf{c}) \mathcal{F}_{n}(\mathbf{x}) = \mathcal{F}_{n}(\mathbf{b})

et ainsi

\mathbf{x} = \mathcal{F}_{n}^{-1} \left [ \left ( \frac{(\mathcal{F}_n(\mathbf{b}))_{\nu}} {(\mathcal{F}_n(\mathbf{c}))_{\nu}} \right )_{\nu \in \mathbb{Z}} \right ].

Cet algorithme de résolution est bien plus rapide que l'élimination de Gauss-Jordan, et l'est d'autant plus si on a recours à la transformée de Fourier rapide.

Voir aussi

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Matrice circulante ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe circulant de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Graphe octaédrique — Représentation du graphe octaédrique. Nombre de sommets 6 Nombre d arêtes 12 Distribution des degrés 4 régulier Rayon …   Wikipédia en Français

  • Graphe régulier — En théorie des graphes, un graphe régulier est un graphe où tous les sommets ont le même nombre de voisins, c est à dire le même degré ou valence. Un graphe régulier dont les sommets sont de degré k > est appelé un graphe k régulier ou graphe… …   Wikipédia en Français

  • Problème des ménages —  Ne doit pas être confondu avec Lemme des mariages. Une table à dix couverts. D après la solution au problème des ménages, il y a 3120 manières différentes, pour 5 couples, de s asseoir en alternant hommes et femmes et sans qu aucu …   Wikipédia en Français

  • Architecture Dataflow — Un ordinateur dataflow (flot de données) décrit une architecture où les données sont des entités actives qui traversent le programme de manière asynchrone, contrairement à l architecture classique von Neumann où elles attendent passivement en… …   Wikipédia en Français

  • Vent — Pour les articles homonymes, voir Vent (homonymie). Le vent est le mouvement d’une atmosphère, masse de gaz située à la surface d une planète. Les vents les plus violents connus ont lieu sur Neptune et sur Saturne. Il est essentiel à tous les… …   Wikipédia en Français

  • Chemin de fer Lausanne-Échallens-Bercher — 46° 38′ 22″ N 6° 37′ 59″ E / 46.639433, 6.632944 …   Wikipédia en Français

  • Densite (homonymie) — Densité (homonymie) Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Densité (Homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Densité (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Densité (homonymie) », sur le Wiktionnaire (dictionnaire universel) La densité correspond en général à …   Wikipédia en Français

  • Electricite — Électricité L’électricité est l interaction de particules chargées sous l action de la force électromagnétique. Ce phénomène physique est présent dans de nombreux contextes : l électricité constitue aussi bien l influx nerveux des êtres… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”