Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
147 personne(s) sur le site en ce moment
E. Cartan

Les maths pour l'agreg

A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 
Opérations sur les lignes et les colonnes next up previous index
suivant: Matrices par blocs monter: Algèbre linéaire en dimension précédent: Cofacteurs   Index

Opérations sur les lignes et les colonnes

On trouvera des manipulations proches de celles décrites ici dans la partie sur les déterminants[*]. La proposition [*] illustre aussi des opérations sur les lignes et les colonnes.

FLEMMARD -> determinants -> resol syst. lineaires

Définition

On appelle système d'équations linéaires une équation de la forme $ MX=Y$, où $ M$ (matrice) et $ Y$ (vecteur) sont donnés et où $ X$ est l'inconnue.

Les opérations sur les lignes et les colonnes d'une matrice ou d'un système linéaire sont par définition:

$ \bullet\ $l'addition d'une ligne (resp. colonne) $ i$ à une ligne (resp. colonne) $ j\neq i$

$ \bullet\ $la multiplication d'une ligne (resp. colonne) $ i$ par un scalaire $ {\lambda}\neq 0$

$ \bullet\ $la permutation de deux lignes (resp. colonnes) $ i$ et $ j\neq i$

Ces opérations seront notées respectivement:

$ \bullet\ $ $ L_i \leftarrow L_i + L_j$ (resp. $ C_i \leftarrow C_i+ C_j$)

$ \bullet\ $ $ L_i \leftarrow L_i$ (resp. $ C_i \leftarrow C_i$)

$ \bullet\ $ $ L_i \leftrightarrow L_j$ (resp. $ C_i \leftrightarrow C_j$)

On pourra éventuellement ajouter à une ligne (resp. une colonne) une autre ligne (resp. colonne) multipliée par un scalaire $ {\lambda}$; cela se notera $ L_i\leftarrow L_i+{\lambda}L_j$ (resp. $ C_i\leftarrow C_i+{\lambda}C_j$).


Exemples:
$ \bullet\ $Sur un système:

Avant:

\begin{displaymath}\left(\begin{array}{ccc}
1 & 2 & -3 \\
0 & 1 & 1 \\
-1 & 3 ...
...=
\left(
\begin{array}{c}
1 \\
2 \\
3 \\
\end{array}\right)
\end{displaymath}

Après $ L_1 \leftarrow L_1+2\ L_2$:

\begin{displaymath}\left(\begin{array}{ccc}
1 & 4 & -1 \\
0 & 1 & 1 \\
-1 & 3 ...
...
=
\left(
\begin{array}{c}
5 \\
2 \\
3 \\
\end{array}\right)\end{displaymath}

$ \bullet\ $Sur une matrice Avant:

\begin{displaymath}\begin{array}{ccc}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9 \\
\end{array}\end{displaymath}

Après $ C_1 \leftrightarrow C_2$

\begin{displaymath}\begin{array}{ccc}
2 & 1 & 3 \\
5 & 4 & 6 \\
8 & 7 & 9 \\
\end{array}\end{displaymath}

Proposition

Les opérations sur les lignes correspondent à des multiplications à droite par des matrices inversibles; les opérations sur les colonnes correspondent à des multiplications à gauche par des matrices inversibles. L'inverse d'une opération sur les lignes (resp. les colonnes) est une opération sur les lignes (resp. les colonnes).


Démonstration:

Proposition

$ \bullet\ $Le déterminant d'une matrice n'est pas modifié en ajoutant à une ligne une combinaison linéaire des autres lignes.

$ \bullet\ $Multiplier une ligne par $ {\lambda}$ multiplie le déterminant par $ {\lambda}$.

$ \bullet\ $Permuter des lignes multiplie le déterminant par $ -1$.

Les mêmes résultats sont valables pour les colonnes.


Démonstration: Cela découle immédiatement des propriétés du déterminant, et du fait que le déterminant d'une matrice est égal au déterminant de sa transposée. Ceux qui ont besoin de rappels peuvent consulter la partie [*].$ \sqcap$$ \sqcup$

Théorème [Formules de Cramer]

Considérons le système d'équations linéaire $ MX=Y$, avec $ M$ de type $ (n,n)$:

\begin{displaymath}M=\left(
\begin{array}{cccc}
M_{1,1} & M_{1,2} & \dots & M_{1...
... \\
M_{n,1} & M_{n,2} & \dots & M_{n,n} \\
\end{array}\right)\end{displaymath}

$\displaystyle Y=(y_1,...,y_p)$

On suppose en outre que $ M$ est inversible.

Alors $ X$ est solution, avec

\begin{displaymath}x_i=\frac{
\left\vert
\begin{array}{cccccccc}
M_{1,1} & M_{1,...
...n,i+1} & \dots & M_{n,n} \\
\end{array}\right\vert
}{
det\ M
}\end{displaymath}


Démonstration: La solution $ X$ est clairement unique, car par inversibilité de $ M$ $ X=M^{-1}Y$.

On a alors $ Y=\sum_k X_k C_k$ avec $ C_k$ la $ k$-ième colonne de $ M$.

Donc, quel que soit $ i$, on a alors $ det\ {M_k}^{(i)}=\sum X_k det\ {M'_k}^{(i)}$

avec

\begin{displaymath}{M_k}^{(i)}=
\left\vert
\begin{array}{cccccccc}
M_{1,1} & M_{...
... & Y_n & M_{n,i+1} & \dots & M_{n,n} \\
\end{array}\right\vert\end{displaymath}

et

\begin{displaymath}{M'_k}^{(i)}=
\left\vert
\begin{array}{cccccccc}
M_{1,1} & M_...
..._{n,k} & M_{n,i+1} & \dots & M_{n,n} \\
\end{array}\right\vert\end{displaymath}

On en déduit donc, en supprimant de la somme $ \sum X_k C_k$ les termes nuls, $ X_i det\ M={M'_i}^{(i)}$, ce qui est précisément le résultat désiré.$ \sqcap$$ \sqcup$

Théorème [Méthode du pivôt de Gauss] La méthode de Gauss consiste à :
1) permuter les lignes pour avoir un coefficient non nul en haut à gauche de la matrice; ce coefficient est appelé pivôt
2) soustraire la première ligne multipliée par un coefficient adéquat à chacune des autres lignes de manière à avoir des zéros sur toute la première colonne en dehors du premier coefficient
3) Procéder de même sur la matrice extraite, simplement dépourvue de sa première ligne et sa première colonne.

Le point $ 1)$ pourra toujours être réalisé si on trouve toujours un coefficient non nul à échanger; pour peu que la matrice soit inversible, cette condition sera toujours vérifiée. Si elle ne l'est pas, on peut travailler sur la matrice extraite par suppression de la première colonne.

En réitérant cette méthode, on arrive à obtenir une matrice triangulaire supérieure. En fait la matrice obtenue est de la forme illustrée sur la figure [*], du moins après permutation des colonnes.


Figure: Matrice obtenue après pivôt de Gauss. La "ligne brisée" évoquée comporte soit des sauts à droite, soit des sauts en diagonale en bas à droite. Le premier élément de la ligne brisée se trouve quelque part sur la première ligne (éventuellement en haut à gauche).
\begin{figure}\begin{displaymath}
\epsfxsize =7cm
\epsfbox{matobt.eps}\end{displaymath}\end{figure}

La matrice ainsi obtenue est donc beaucoup plus maniable: le calcul du déterminant (si la matrice est carré) se résume à la multiplication des éléments diagonaux, la résolution de systèmes linéaires est plus aisée (il convient de noter pour cela que les opérations sur les colonnes sont de simples permutations sur les inconnues), le calcul du rang est immédiat (nombre d'éléments avant le dernier élément non nul de la dernière colonne).

Remarque Afin de minimiser les pertes de précision d'un calcul numérique, il est préférable de choisir un pivôt grand en valeur absolue.

La méthode du pivôt total consiste à chercher le pivôt non pas seulement sur la colonne en cours, mais d'éventuellement permuter les colonnes pour avoir un pivôt plus grand. Par opposition au pivôt total, la méthode ci-dessus est dite pivôt partiel.

Théorème [Décomposition $ A=LU$] Etant donnée une matrice $ A$ supposée inversible, on définit $ a_k=\vert (A_{i,j})_{i,j\leq k} \vert$, déterminant de la matrice obtenue en se restreignant aux $ k$ premières lignes et $ k$ premières colonnes.

On appelle décomposition $ A=LU$ un produit du type $ A=LU$ avec $ L$ matrice triangulaire inférieure ne comportant que des $ 1$ sur la diagonale, $ U$ matrice triangulaire supérieure, Alors il existe une décomposition $ A=LU$ si et seulement si les $ a_k$ sont non nuls pour tout $ k$ dans $ [1,n]$.

Démonstration: Il suffit d'utiliser la méthode de Gauss, en considérant les matrices correspondant aux opérations sur les lignes et les colonnes. C'est-à-dire que l'on obtient un produit $ \pi_{i=1}^nM_{n-i}A=U$, avec $ M_i$ la matrice correspondant à l'opération sur les lignes et les colonnes effectué à la $ i$-ième étape. Mais l'inverse d'une opération sur les lignes ou les colonnes est une opération sur les lignes ou les colonnes (facile à trouver); donc on peut aussi écrire $ A=\pi_{i=1}^n N_i U$, avec $ N_i$ l'inverse de $ M_i$. Le produit des $ N_i$ est bien de la forme désirée, triangulaire supérieure à diagonale unité, comme on s'en convaincra en considérant la stabilité de l'ensemble des matrices triangulaires supérieures à diagonale unité par multiplication par les matrices des opérations sur les lignes et les colonnes.

Proposition Si $ A$ est inversible, il existe une matrice de permutation $ P$ telle que $ PA=LU$.

Démonstration: Si $ a_k$ est nul, il existe nécéssairement une permutation de lignes qui arrange ça, sinon $ A$ ne pourrait pas être de rang plein - il suffit donc de multiplier les différentes permutations de lignes nécéssaires pour obtenir une matrice vérifiant les conditions demandées.

Théorème [Décomposition de Cholesky] On appelle décomposition de Cholesky ou décomposition $ A=^tRR$, un produit de la forme $ A=^tRR$, avec $ R$ triangulaire inférieure inversible.

$ A$ admet une décomposition de Cholesky si et seulement si $ A$ est symétrique définie positive.


Démonstration: On pourra consulter [7] pour cette preuve.$ \sqcap$$ \sqcup$


next up previous index
suivant: Matrices par blocs monter: Algèbre linéaire en dimension précédent: Cofacteurs   Index
C_Antonini,J_F_Quint,P_Borgnat,J_Bérard,E_Lebeau,E_Souche,A_Chateau,O_Teytaud
 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page