162 Systèmes d’équations linéaires ; opérations élémentaires, aspects algorithmiques et conséquences théoriques.

Systèmes d’équations linéaires ; opérations élémentaires, aspects algorithmiques et conséquences théoriques.

algebra

Soit un corps commutatif.

Généralités

Définitions

Définition 1.

  • On appelle système linéaire à équations en inconnues, un système d’équations de la forme .

  • On appelle solution de tout vecteur dont les composantes satisfont toutes les équations.

  • est dit compatible s’il admet au moins une solution.

Exemple 2. Le système ci-dessous est linéaire, il n’est pas compatible.

Écriture sous forme matricielle

Proposition 3. On considère le système de la Définition 1. On peut l’écrire sous forme matricielle avec , et .

Définition 4. On appelle rang du système le rang de la matrice .

Proposition 5. Soit un système linéaire à équations et inconnues. Si est inversible, on a une unique solution, donnée par .

Étude de systèmes particuliers

Systèmes de Cramer

Définition 6. On appelle système de Cramer, un système linéaire à équations et inconnues .

Théorème 7 (Formules de Cramer). Un système de Cramer admet une unique solution donnée par avec obtenue en remplaçant la -ième colonne de par .

Exemple 8. Le système est de Cramer, son unique solution est .

Équations de Sylvester

Lemme 9. Soit une norme d’algèbre sur , et soit une matrice dont les valeurs propres sont de partie réelle strictement négative. Alors il existe une fonction polynômiale et tels que .

Application 10 (Équation de Sylvester). Soient et deux matrices dont les valeurs propres sont de partie réelle strictement négative. Alors pour tout , l’équation admet une unique solution dans .

Méthodes générales de résolution

Théorème de Rouché-Fontené

Lemme 11. Soit . Soit . Il existe un déterminant d’ordre extrait de .

Définition 12.

  • Le déterminant précédent est le déterminant principal de .

  • Les équations (resp. inconnues) dont les indices sont deux des lignes (resp. colonnes) de s’appellent les équations principales (resp. inconnues principales).

  • Si , on appelle déterminants caractéristiques les déterminants d’ordre de la forme

    avec .

Théorème 13 (Rouché-Fontené). Un système de rang avec , et admet des solutions si et seulement si ou les déterminants caractéristiques sont nuls. Le système est alors équivalent au système des équations principales. Les inconnues principales étant déterminées par un système de Cramer à l’aide des inconnues non principales.

Exemple 14. Si, on a , admet des solutions si et seulement si , et

Algorithme du pivot de Gauss

Opérations élémentaires

Définition 15. Soit .

  • On dit que est échelonnée en lignes si elle est nulle ou si elle est non nulle et il existe un entier compris entre et tel que :

    • Les premières lignes de sont non nulles.

    • Les dernières lignes de sont nulles.

    • En notant , on a

  • On dit que est échelonnée en colonnes si est échelonnée en lignes.

Proposition 16. Avec les notations précédentes, si est échelonnée en lignes, alors .

Définition 17. On dit qu’un système linéaire est échelonné si la matrice est échelonnée en lignes.

Théorème 18.

  1. La multiplication à gauche par une matrice de dilatation (obtenue à partir de la matrice identité en remplaçant le coefficient à la -ième ligne par ) a pour effet de multiplier la ligne par .

  2. La multiplication à gauche par une matrice de transvection (obtenue à partir de la matrice identité en remplaçant le coefficient à la -ième ligne et -ième colonne par ) a pour effet de multiplier la ligne par la somme de la ligne et de la ligne multipliée par .

  3. La multiplication à droite fait des effets similaires sur les colonnes.

Remarque 19. Pour effectuer une permutation des lignes et , il suffit de multiplier à gauche par

Définition 20. On appelle opération élémentaire une des opérations citées précédemment.

Théorème 21. Une opération élémentaire sur les lignes d’un système linéaire le transforme en un système équivalent.

Résolution pratique

On cherche à résoudre ke système linéaire de équations à inconnues :

mis sous forme matricielle . On suppose (sinon l’ensemble des solutions de est ). On note la ligne numéro de pour tout .

Théorème 22 (Échelonnement par pivot).

  1. Si les premières colonnes de la matrice sont nulles, les variables peuvent être quelconques et on passe à la colonne , ce qui nous donne un système de équations à inconnues. On suppose donc que la première colonne de la matrice n’est pas nulle et en permutant la ligne avec une des lignes suivantes on se ramène à un système avec . On élimine alors des lignes à en effectuant les opérations élémentaires pour , ce qui donne le système :

    • Si l’un des coefficients est non nul (pour ), on recommence avec un procédé analogue pour éliminer des équations à .

    • Si tous les coefficients sont nuls, on passe alors à la colonne suivante. Et on recommence ainsi de suite.

  2. Au bout d’un nombre fini d’étapes, on aboutit à un système échelonné qui est équivalent au système .

Une fois le système échelonné, on peut procéder à la résolution.

Théorème 23 (Remontée). Trois cas de figure sont possibles.

  1. Soit on a obtenu un système de Cramer triangulaire supérieur d’ordre . Un tel système a une unique solution et se résout alors en remontée. Dans ce cas, est de rang .

  2. Soit on a obtenu un système de équations à inconnues. Les premières inconnues sont les inconnues principales et les autres inconnues non principales. Ces dernières sont alors utilisées comme paramètres en second membre et on résout le système d’inconnues principales . L’ensemble des solutions est un espace affine de dimension et le rang de la matrice est .

  3. Soit on a obtenu un système de équations à inconnues, de la forme : si l’un des pour est non nul, alors le système est incompatible. Sinon, le système des équations principales est un système de Cramer, qui admet une unique solution. Dans ce cas, la matrice est de rang .

Exemple 24. On a pour unique solution .

Comparaison avec les formules de Cramer

Théorème 25. L’algorithme du pivot de Gauss pour résoudre un système a un complexité de . L’utilisation des formules de Cramer se fait en .

Conséquences théoriques

Familles libres

Proposition 26. La méthode du pivot permet de décider si une famille est libre (en échelonnant la matrice formée des vecteurs de cette famille).

Exemple 27. La famille est libre.

Rang, équivalence

Proposition 28. Soit de rang . Par des opérations élémentaires sur des lignes et des colonnes de , on peut la transformer en

Commutant d’une matrice

Soit .

Lemme 29. Si , alors est cyclique :

Notation 30.

  • On note l’ensemble des matrices carrées triangulaires supérieures d’ordre à coefficients dans le corps .

  • On note le commutant de .

Lemme 31.

Lemme 32. Le rang de est invariant par extension de corps.

Théorème 33.

Décompositions

Décomposition LU

Définition 34. Les sous-matrices principales d’une matrice sont les matrices . Les déterminants principaux sont les déterminants des matrices , pour .

Théorème 35 (Décomposition lower-upper). Soit . Alors, admet une décomposition (où est une matrice triangulaire inférieure à diagonale unité et une matrice triangulaire supérieure) si et seulement si tous les déterminants principaux de sont non nuls. Dans ce cas, une telle décomposition est unique.

Corollaire 36. Soit . Alors, on a l’unique décomposition de : est une matrice triangulaire inférieure et une matrice diagonale.

Application 37 (Décomposition de Cholesky). Soit . Alors, si et seulement s’il existe triangulaire inférieure telle que . De plus, une telle décomposition est unique si on impose la positivité des coefficients diagonaux de .

Exemple 38. On a la décomposition de Cholesky :

Proposition 39. Soit vérifiant les hypothèses du Théorème 35. On définit la suite et , est la matrice obtenue à partir de à l’aide du pivot de Gauss sur la -ième colonne. Alors, est la matrice de la décomposition du Théorème 35.

Remarque 40. Pour résoudre un système linéaire , on se ramène à en . Puis, on résout deux systèmes triangulaires en cascade : ceux-ci demandant chacun opérations.

Théorème 41 (Décomposition PLU). Soit . Alors, il existe , matrice de permutations, telle que admet une décomposition .

Décomposition QR

Théorème 42 (Décomposition QR). Soit . Alors, admet une décomposition est une matrice orthogonale et est une matrice triangulaire supérieure à coefficients diagonaux strictement positifs. On a unicité d’une telle décomposition.

Corollaire 43 (Théorème d’Iwasawa). Soit . Alors, admet une décomposition est une matrice orthogonale, est une matrice diagonale à coefficients strictement positifs et est une matrice triangulaire supérieure à coefficients diagonaux égaux à . On a unicité d’une telle décomposition.

Exemple 44. On a la factorisation QR suivante, qui peut être obtenue via un procédé de Gram-Schmidt.

Remarque 45. Pour résoudre un système linéaire , si l’on a trouvé une telle factorisation , on résout c’est-à-dire, un seul système triangulaire (contre deux pour la factorisation LU).