Systèmes d'équations linéaires et matrices.
Résolution de systèmes d'équations linéaires.
2x+y+z=1
3x+3y-z=5
x-2y+3z=2
2x+y+z=1
3y+z=7
-3y+5z=3
2x+y+z=1
3y+z=7
6z=10
donc z=6/10=3/5 et y=
Factorisation formula_1 d'une matrice.
Certains systèmes d'équations linéaires sont plus faciles à résoudre que d'autres. Un cas particulier de système facile à résoudre est un système d'équations triangulaire tel que
formula_2
La factorisation formula_1 d'une matrice permet de transformer un système d'équations linéaires en deux systèmes d'équations triangulaires. En effet, si formula_4 avec formula_5 une matrice triangulaire inférieure et formula_6 une matrice triangulaire supérieure (la notation formula_1 prend son origine de l'anglais formula_5 pour lower et formula_6 pour upper) alors résoudre formula_10 est équivalent à résoudre formula_11 qui peut se faire en résolvant les deux systèmes triangulaires formula_12 et
formula_13.
Factorisation formula_1 sans permutation.
Pour alléger l'écriture, nous allons montrer comment faire une factorisation formula_15 sur un exemple simple d'une matrice 3×3. Le lecteur devrait être capable de généraliser facilement la procédure à des matrices carrées d'autres dimensions. Soit formula_16 la matrice que l'on veut factoriser :
formula_17
Nous transformerons la matrice formula_16 en une matrice triangulaire supérieure par des opérations linéaires sur les lignes, ce sera la matrice formula_19, la matrice formula_20 pourra être récupérée simplement en prenant note des opérations effectuées. Pour faire la factorisation, nous procédons par colonne. Nous voulons mettre des zéros dans la première colonne partout sous le premier élément, ce premier élément que l'on n'annule pas est appelé le pivot. Pour mettre un zéro à la position formula_21, nous retranchons 2 fois la première ligne de la deuxième. Le nombre de fois qu'il faut soustraire la première ligne est bien entendu obtenu en divisant l'élément formula_21 par le pivot formula_23, nous obtenons :
formula_24
Nous devons garder en mémoire l'opération qui a été faite de manière à pouvoir construire la matrice formula_20, alors appelons formula_26 le facteur de l'opération effectuée, c'est-à-dire le nombre de fois que l'on a soustrait la première ligne à la deuxième, ici nous avons formula_27.
Continuons avec l'élément suivant sur la première colonne. Nous voulons mettre un zéro à la position formula_28. Cette fois il nous faudra ajouter la ligne 1 à la ligne 3 ; à l'opération précédente nous avions pris en note combien de fois nous avions soustrait la ligne 1 à la ligne 2. Pour être constant dans notre façon de noter les opération et parce que, comme nous le verrons plus loin, c'est beaucoup plus pratique, nous noterons toujours combien de fois nous soustrayons les lignes. Au lieu de noter que nous ajoutons une fois la ligne 1 à la ligne 3, nous noterons que nous soustrayons moins une fois la ligne 1 à la ligne 3, donc formula_29 et nous avons maintenant la matrice :
formula_30
PASSONS maintenant à la deuxième colonne. Il nous faut choisir un nouveau pivot sur la deuxième colonne. Nous ne pouvons pas choisir le pivot sur la première ligne sinon nous remplirons la première colonne en annulant les entrées dans la deuxième colonne. Prenons donc l'élément à la position 2,2 pour pivot. L'opération pour mettre un zéro à la position 3,2 sera de soustraire 3 fois la deuxième ligne à la troisième ligne. Nous obtenons notre matrice triangulaire supérieure :
formula_31
Et nous notons le facteur de l'opération formula_32.
La matrice formula_20 est obtenue en mettant des zéros au-dessus de la diagonale, des un sur la diagonale et les coefficients pris en note à leur position respective sous la diagonale c'est-à-dire :
formula_34
Avant de démontrer pourquoi cela fonctionne, vérifions-le sur cet exemple en faisant le produit :
formula_35
Pour voir pourquoi les matrices formula_20 et formula_19 obtenues selon la procédure décrite ci-haut sont bien des facteurs de la matrice formula_38 nous introduisons des matrices de soustraction de lignes formula_39. Ces matrices sont obtenus en mettant des 1 sur la diagonale et l'élément formula_40 à la position formula_41. Par exemple, pour les matrices 3×3 :
formula_42
On peut voir que pré-multiplier une matrice par formula_43 a pour effet de soustraire deux fois la première ligne à la deuxième ligne.
Et de manière générale, pré-multiplier une matrice par formula_39 a pour effet de soustraire formula_45 fois la ligne formula_46 à la ligne formula_47. Donc la triangularisation que l'on a faite ci-haut peut s'écrire
formula_48
L'inverse d'une matrice formula_39 est facile à déterminer. L'inverse est simplement formula_50, en effet formula_51. En multipliant à gauche l'équation de formula_19 ci-haut par formula_53 on obtient:
formula_54
Et en remultipliant successivement par formula_55 et formula_56, on obtient
formula_57
Nous laissons au lecteur l'exercice de vérifier que :
formula_58
Résoudre un système d'équation linéaire par factorisation formula_1 de la matrice.
Soit à résoudre le système d'équations
formula_60
Il est plus pratique d'utiliser la notation matricielle pour écrire le système d'équation, alors dorénavant nous n'écrirons plus de système d'équation tel que ci-haut, nous l'écrirons sous la forme formula_10, c'est-à-dire:
formula_62
Nous reconnaissons dans ce problème la matrice formula_38 de la section précédente. Le problème est donc équivalent à résoudre formula_11 :
formula_65
Pour résoudre ce problème on commence par faire la substitution formula_13. Le problème se résout donc en deux étapes, premièrement on résout formula_12, c'est une descente triangulaire:
formula_68
La première ligne nous donne formula_69. Ce que l'on peut introduire dans la deuxième ligne qui devient formula_70, d'où formula_71. On introduit ces deux valeurs dans la troisième ligne qui devient formula_72, ce qui donne formula_73.
Deuxièmement on résoud la remontée triangulaire formula_13
formula_75
La troisième ligne nous donne formula_76, c'est-à-dire formula_77. Que l'on insère dans la deuxième ligne, ce qui donne formula_78, donc formula_79. Finalement, on introduit formula_80 et formula_81 dans la première ligne pour avoir formula_82 et formula_83.
Les descentes et remontées triangulaires se font relativement rapidement, ce qui permet si on a plusieurs systèmes d'équations linéaire ayant la même matrice de toutes les résoudre à peu de frais une fois la matrice factorisé. Nous verrons, plusieurs situations où cela s'avère utile tout au long de ce livre.
Méthode de Gauss-Jordan.
Méthode de Gauss-Jordan.
C'est une méthode permettant la mise sous carré d'une forme quadratique.
Méthodes d'ordre inférieur à formula_86.
Note : Cette section introduit des notions qui sont peu utilisées et difficilement utilisables. De plus les notions de cette sections ne serviront pas dans le reste de ce livre. Le lecteur peut donc sans crainte passer à la section suivante.
Multiplication rapide de matrices.
La méthode de multiplication suivante est appelé l'algorithme de Strassen, ou multiplication rapide de matrices.
Soient "A" et "B" les matrices:
formula_87
La méthode standard pour multiplier ces deux matrices demandes 8 multiplications scalaires. Mais il est possible de faire cette multiplication matricielle avec une multiplication scalaire de moins de la manière suivante.
On pose:
On peut voir que
formula_95
Cette façon de multiplier ces deux matrices peut sembler compliquée et contre-intuitive et à première vue le gain n'est pas très important, on économise une multiplication au prix de 14 additions (ou soustraction) supplémentaires. Là où cette méthode devient plus intéressante, c'est lorsque les matrices sont de plus grande taille. Si les matrices formula_38 et formula_97 était des matrices 200×200 au-lieu de matrices 2×2, alors nous pourrions utiliser le même procédé mais en utilisant des sous-matrices de taille 100×100 à la place des scalaires. On économise alors un produit matricielle 100×100 au coût de 14 additions matricielles 100×100. Les produits matriciels 100×100 exigent environ formula_98 additions et multiplications scalaires lorsqu'ils sont faits de façon standard mais les additions matricielles 100×100 ne demandent que formula_99 additions. Donc le produit matriciel économisé prendrait beaucoup plus de temps de calcul que les 14 additions matricielles supplémentaires.
De plus, il est possible d'itérer ce processus. Si on veut multiplier 2 matrices de dimension formula_100, on peut utiliser l'algorithme ci-dessus avec des sous-matrices de dimension formula_101×formula_101 et faire chacune des 7 multiplications nécessaires en utilisant la même méthode avec des sous-matrices de dimension formula_103×formula_103. On peut donc multiplier deux matrices de dimension formula_100×formula_100 en ne faisant que formula_107 multiplications scalaires comparativement à formula_108 multiplications scalaires pour la méthode standard.
Si on veut multiplier deux très grandes matrices dont les dimensions ne sont pas des puissances de deux, on peut utiliser la même procédure simplement en complétant les matrices par des zéros et des uns sur la diagonale pour obtenir une dimension qui est puissance de 2. Il suffira ensuite de tronquer les lignes et les colonnes artificielles dans le résultat.
Résoudre des systèmes d'équations linéaires en utilisant la multiplication rapide de matrices.
Pour résoudre un système d"équation linéaire formula_10 en utilisant la multiplication rapide des matrices, on commence par calculer l'inverse de la matrice formula_38. Pour ce faire on utilise une notation par block de la matrice. Si a est une matrice de dimension formula_111×formula_111, alors on forme les sous matrices de dimensions formula_113×formula_113: formula_115, formula_116, formula_117 et formula_118 de manière à ce que
formula_119
Alors l'inverse de la matrice formula_38 peut s'écrire:
formula_121
Cela nécessite de calculer 2 inverses de matrices et 5 produits matricielles tous de dimensions formula_113×formula_113. En effet il suffit de calculer les inverses
et de faire les produits matricielle
En calculant ces produits matricielle et ces matrices inverses en utilisant la multiplication rapide et cette méthode d'inversion de manière récursive le nombre d'opération nécessaire pour inverser une matrice de dimension formula_113×formula_113 est de l'ordre de formula_133.
Les méthodes de multiplication rapide et d'inversion rapide de matrice d'écrite ici ne sont pas optimales. On peut construire des méthodes plus élaborer de multiplication de matrices par exemple on peut multiplier des matrices 3×3 plus efficacement que les matrices 2×2 par un astuce similaire à celle décrite ci-dessus mais plus élaborée. Il est possible de développer ce genre d'astuce de plus en plus élaborer sur des matrices de plus en plus grande. Il est possible d'avoir des méthodes dont la complexité numérique pour une matrice formula_113×formula_113 est de l'ordre de formula_136 ce qui est bien moins que le formula_137. Cependant toutes ces méthodes ont des problèmes de stabilités numériques, c'est-à-dire que de petites erreurs d'arrondie peuvent avoir des conséquences désastreuses sur les résultats. Pour cette raison, ces méthodes ne sont pas utilisées. Peut-être un jour trouvera-t-on une solution à ces problèmes d'instabilités numériques.
Systèmes d'équations linéaires et matrices.
Systèmes de deux équations à deux inconnues.
2x+4y_3=0.
Factorisation formula_1 d'une matrice.
Certains systèmes d'équations linéaires sont plus faciles à résoudre que d'autres. Un cas particulier de système facile à résoudre est un système d'équations triangulaire tel que
formula_2
La factorisation formula_1 d'une matrice permet de transformer un système d'équations linéaires en deux systèmes d'équations triangulaires. En effet, si formula_4 avec formula_5 une matrice triangulaire inférieure et formula_6 une matrice triangulaire supérieure (la notation formula_1 prend son origine de l'anglais formula_5 pour lower et formula_6 pour upper) alors résoudre formula_10 est équivalent à résoudre formula_11 qui peut se faire en résolvant les deux systèmes triangulaires formula_12 et
formula_13.
Factorisation formula_1 sans permutation.
Pour alléger l'écriture, nous allons montrer comment faire une factorisation formula_1 sur un exemple simple d'une matrice 3×3. Le lecteur devrait être capable de généraliser facilement la procédure à des matrices carrées d'autres dimensions. Soit formula_38 la matrice que l'on veut factoriser :
formula_17
Nous transformerons la matrice formula_38 en une matrice triangulaire supérieure par des opérations linéaires sur les lignes, ce sera la matrice formula_6, la matrice formula_5 pourra être récupérée simplement en prenant note des opérations effectuées. Pour faire la factorisation, nous procédons par colonne. Nous voulons mettre des zéros dans la première colonne partout sous le premier élément, ce premier élément que l'on n'annule pas est appelé le pivot. Pour mettre un zéro à la position formula_158, nous retranchons 2 fois la première ligne de la deuxième. Le nombre de fois qu'il faut soustraire la première ligne est bien entendu obtenu en divisant l'élément formula_158 par le pivot formula_160, nous obtenons :
formula_24
Nous devons garder en mémoire l'opération qui a été faite de manière à pouvoir construire la matrice formula_5, alors appelons formula_163 le facteur de l'opération effectuée, c'est-à-dire le nombre de fois que l'on a soustrait la première ligne à la deuxième, ici nous avons formula_164.
Continuons avec l'élément suivant sur la première colonne. Nous voulons mettre un zéro à la position formula_165. Cette fois il nous faudra ajouter la ligne 1 à la ligne 3 ; à l'opération précédente nous avions pris en note combien de fois nous avions soustrait la ligne 1 à la ligne 2. Pour être constant dans notre façon de noter les opération et parce que, comme nous le verrons plus loin, c'est beaucoup plus pratique, nous noterons toujours combien de fois nous soustrayons les lignes. Au lieu de noter que nous ajoutons une fois la ligne 1 à la ligne 3, nous noterons que nous soustrayons moins une fois la ligne 1 à la ligne 3, donc formula_166 et nous avons maintenant la matrice :
formula_30
PASSONS maintenant à la deuxième colonne. Il nous faut choisir un nouveau pivot sur la deuxième colonne. Nous ne pouvons pas choisir le pivot sur la première ligne sinon nous remplirons la première colonne en annulant les entrées dans la deuxième colonne. Prenons donc l'élément à la position 2,2 pour pivot. L'opération pour mettre un zéro à la position 3,2 sera de soustraire 3 fois la deuxième ligne à la troisième ligne. Nous obtenons notre matrice triangulaire supérieure :
formula_31
Et nous notons le facteur de l'opération formula_169.
La matrice formula_5 est obtenue en mettant des zéros au-dessus de la diagonale, des un sur la diagonale et les coefficients pris en note à leur position respective sous la diagonale c'est-à-dire :
formula_34
Avant de démontrer pourquoi cela fonctionne, vérifions-le sur cet exemple en faisant le produit :
formula_35
Pour voir pourquoi les matrices formula_5 et formula_6 obtenues selon la procédure décrite ci-haut sont bien des facteurs de la matrice formula_38 nous introduisons des matrices de soustraction de lignes formula_176. Ces matrices sont obtenus en mettant des 1 sur la diagonale et l'élément formula_177 à la position formula_178. Par exemple, pour les matrices 3×3 :
formula_42
On peut voir que pré-multiplier une matrice par formula_180 a pour effet de soustraire deux fois la première ligne à la deuxième ligne.
Et de manière générale, pré-multiplier une matrice par formula_176 a pour effet de soustraire formula_182 fois la ligne formula_183 à la ligne formula_184. Donc la triangularisation que l'on a faite ci-haut peut s'écrire
formula_185
L'inverse d'une matrice formula_176 est facile à déterminer. L'inverse est simplement formula_187, en effet formula_188. En multipliant à gauche l'équation de formula_6 ci-haut par formula_190 on obtient:
formula_191
Et en remultipliant successivement par formula_192 et formula_193, on obtient
formula_194
Nous laissons au lecteur l'exercice de vérifier que :
formula_195
Résoudre un système d'équation linéaire par factorisation formula_1 de la matrice.
Soit à résoudre le système d'équations
formula_60
Il est plus pratique d'utiliser la notation matricielle pour écrire le système d'équation, alors dorénavant nous n'écrirons plus de système d'équation tel que ci-haut, nous l'écrirons sous la forme formula_10, c'est-à-dire:
formula_62
Nous reconnaissons dans ce problème la matrice formula_38 de la section précédente. Le problème est donc équivalent à résoudre formula_11 :
formula_65
Pour résoudre ce problème on commence par faire la substitution formula_13. Le problème se résout donc en deux étapes, premièrement on résout formula_12, c'est une descente triangulaire:
formula_68
La première ligne nous donne formula_69. Ce que l'on peut introduire dans la deuxième ligne qui devient formula_70, d'où formula_71. On introduit ces deux valeurs dans la troisième ligne qui devient formula_72, ce qui donne formula_73.
Deuxièmement on résout la remontée triangulaire formula_13
formula_75
La troisième ligne nous donne formula_76, c'est-à-dire formula_77. Que l'on insère dans la deuxième ligne, ce qui donne formula_78, donc formula_79. Finalement, on introduit formula_80 et formula_81 dans la première ligne pour avoir formula_82 et formula_83.
Les descentes et remontées triangulaires se font relativement rapidement, ce qui permet si on a plusieurs systèmes d'équations linéaire ayant la même matrice de toutes les résoudre à peu de frais une fois la matrice factorisé. Nous verrons, plusieurs situations où cela s'avère utile tout au long de ce livre.
Méthode de Gauss-Jordan.
Méthode de Gauss-Jordan.
C'est une méthode permettant la mise sous carré d'une forme quadratique.
Méthodes d'ordre inférieur à formula_86.
Note : Cette section introduit des notions qui sont peu utilisées et difficilement utilisables. De plus les notions de cette sections ne serviront pas dans le reste de ce livre. Le lecteur peut donc sans crainte passer à la section suivante.
Multiplication rapide de matrices.
La méthode de multiplication suivante est appelé l'algorithme de Strassen, ou multiplication rapide de matrices.
Soient "A" et "B" les matrices:
formula_87
La méthode standard pour multiplier ces deux matrices demandes 8 multiplications scalaires. Mais il est possible de faire cette multiplication matricielle avec une multiplication scalaire de moins de la manière suivante.
On pose:
On peut voir que
formula_95
Cette façon de multiplier ces deux matrices peut sembler compliquée et contre-intuitive et à première vue le gain n'est pas très important, on économise une multiplication au prix de 14 additions (ou soustraction) supplémentaires. Là où cette méthode devient plus intéressante, c'est lorsque les matrices sont de plus grande taille. Si les matrices formula_38 et formula_97 était des matrices 200×200 au-lieu de matrices 2×2, alors nous pourrions utiliser le même procédé mais en utilisant des sous-matrices de taille 100×100 à la place des scalaires. On économise alors un produit matricielle 100×100 au coût de 14 additions matricielles 100×100. Les produits matriciels 100×100 exigent environ formula_98 additions et multiplications scalaires lorsqu'ils sont faits de façon standard mais les additions matricielles 100×100 ne demandent que formula_99 additions. Donc le produit matriciel économisé prendrait beaucoup plus de temps de calcul que les 14 additions matricielles supplémentaires.
De plus, il est possible d'itérer ce processus. Si on veut multiplier 2 matrices de dimension formula_100, on peut utiliser l'algorithme ci-dessus avec des sous-matrices de dimension formula_101×formula_101 et faire chacune des 7 multiplications nécessaires en utilisant la même méthode avec des sous-matrices de dimension formula_103×formula_103. On peut donc multiplier deux matrices de dimension formula_100×formula_100 en ne faisant que formula_107 multiplications scalaires comparativement à formula_108 multiplications scalaires pour la méthode standard.
Si on veut multiplier deux très grandes matrices dont les dimensions ne sont pas des puissances de deux, on peut utiliser la même procédure simplement en complétant les matrices par des zéros et des uns sur la diagonale pour obtenir une dimension qui est puissance de 2. Il suffira ensuite de tronquer les lignes et les colonnes artificielles dans le résultat.
Résoudre des systèmes d'équations linéaires en utilisant la multiplication rapide de matrices.
Pour résoudre un système d"équation linéaire formula_10 en utilisant la multiplication rapide de matrices, on commence par calculer l'inverse de la matrice formula_38. Pour ce faire on utilise une notation par block de la matrice. Si a est une matrice de dimension formula_111×formula_111, alors on forme les sous matrices de dimensions formula_113×formula_113: formula_115, formula_116, formula_117 et formula_118 de manière à ce que
formula_119
Alors l'inverse de la matrice formula_38 peut s'écrire:
formula_121
Cela nécessite de calculer 2 inverses de matrices et 6 produits matricielles tous de dimensions formula_113×formula_113. En effet il suffit de calculer les inverses
et de faire les produits matricielle
En calculant ces produits matricielle et ces matrices inverses en utilisant la multiplication rapide et cette méthode d'inversion de manière récursive le nombre d'opérations nécessaire pour inverser une matrice de dimension formula_113×formula_113 est de l'ordre de formula_133.
Les méthodes de multiplication rapide et d'inversion rapide de matrice décrite ici ne sont pas optimales. On peut construire des méthodes plus élaborer de multiplication de matrices par exemple on peut multiplier des matrices 3×3 plus efficacement que les matrices 2×2 par un astuce similaire à celui décrit ci-haut mais plus élaborer. Il est possible de développer ce genre d'astuce de plus en plus élaborer sur des matrices de plus en plus grande. Il est possible d'avoir des méthodes dont la complexité numérique pour une matrice formula_113×formula_113 est de l'ordre de formula_136 ce qui est bien moins que le formula_275. Cependant toutes ces méthodes ont des problèmes de stabilités numériques, c'est-à-dire que de petites erreurs d'arrondie peuvent avoir des conséquences désastreuses sur les résultats. Pour cette raison, ces méthodes ne sont pas utilisées. Peut-être un jour trouvera-t-on une solution à ces problèmes d'instabilités numériques.