Calculatrice en ligne: Triangulation d'une matrice

Voici ci-dessous deux calculateurs pour la triangulation d'une matrice.
La première utilise la méthode de Gauss et la seconde la méthode de Bareiss. La description des méthodes et la théorie est plus bas.

Triangulation d'une matrice (méthode de Gauss)

Matrice

Précision de calcul

Chiffres après la virgule décimale : 4

Matrice triangulaire (méthode de Gauss)

Matrice triangulaire (méthode de Gauss avec une sélection maximale dans une colonne) :

Matrice triangulaire (méthode de Gauss avec un choix maximal dans toute la matrice) :

Triangulation d'une matrice (méthode de Bareiss)

Matrice

Précision de calcul

Chiffres après la virgule décimale : 4

Matrice triangulaire (méthode de Bareiss)

Matrice triangulaire (méthode de Bareiss avec une sélection maximale dans une colonne) :

Matrice triangulaire (méthode de Bareiss avec un choix maximal dans toute la matrice) :

D'abord, nous donnerons une notion sur la matrice triangulaire et celle échelonnée
La matrice a une forme échelonnée si :

Toutes les lignes de zéro, si existantes, sont en bas de la matrice
Le coefficient principale (le premier nombre non-nulle à partir de la gauche, également appelé pivot) d'une ligne non-nulle est toujours strictement à droite du coefficient principal de la ligne supérieur
Toutes les lignes non-nulles (ligne avec au moins un élément non-nulle) sont au-dessus des lignes nulles.

Exemple de matrice échelonnée :
1 0 2 5
0 3 0 0
0 0 0 4
La notion de matrice triangulaire est plus restrictive and elle n'utilise que des matrices carrées. Elle est ainsi : la matrice triangulaire est une matrice carrée où tous les éléments en-dessous de la diagonale principale sont nulles. Elle est actuellement appelée matrice triangulaire supérieure Il est évident que la matrice triangulaire supérieur est également une matrice échelonnée.

Exemple de matrice triangulaire supérieure :
1 0 2 5
0 3 1 3
0 0 4 2
0 0 0 3
D'ailleurs, le déterminant d'une matrice triangulaire est calculé en multipliant simplement tous ses éléments diagonaux.

Vous pouvez demander ce qu'il y a de si intéressant concernant les matrices échelonnées (et triangulaires) pour que toutes les autres soient réduites dans cette forme ?
Elles ont une propriété incroyable - toutes les matrices rectangulaires peuvent être réduites à des matrices échelonnées via des transformations élémentaires.

Vous pouvez vous demander ce que sont les transformations élémentaires ?
Les transformations élémentaires des matrices sont les opérations suivantes :

Echange de lignes (la ligne A de la matrice peut être échangée avec une autre ligne de la matrice).
Multiplication de lignes (chaque élément d'une ligne peut être multiplié par une constante non-nulle).
Addition de lignes (Une ligne A peut être remplacé par la somme de cette ligne et d'un multiple d'une autre ligne).

Et maintenant?
Les transformations élémentaires des matrices conservent l'équivalence des matrices. Et si vous vous souvenez que les systèmes linéaires d'équations algébriques sont écrits sous la forme d'une matrice, cela signifie que les transformations élémentaires des matrices ne changent pas l'ensemble de solutions des systèmes linéaires d'équations algébriques représentés par cette matrice.

En triangulant la matrice de l'équation linéaire AX=B vers AX'=B' soit avec la transformation correspondante de la colonne B, vous pouvez faire une "substitution vers l'arrière".

Pour clarifier, nous utiliserons la matrice triangulaire ci-dessus, et réécrirons le systèmes d'équations sous une forme plus commune (j'ai composé la colonne B) :

$1*x_1 + 0*x_2 + 2 * x_3 + 5 * x_4 = 10 \\ 0*x_1 + 3*x_2 + 1 * x_3 + 3 * x_4 = 7 \\ 0*x_1 + 0*x_2 + 4 * x_3 + 2 * x_4 = 5 \\ 0*x_1 + 0*x_2 + 0 * x_3 + 3 * x_4 = 9$

il est clair que nous trouverons d'abord $x_4$ , puis nous le substituons dans l'équation précédente et trouvons $x_3$ et ainsi de suite - en allant de la dernière équation à la première. C'est ce qui est appelée la substitution vers l'arrière.
Cet algorithme de réduction de ligne est appelé méthode de Gauss. La méthode de Gauss est une méthode classique pour résoudre les systèmes d'équations linéaires. C'est également l'élimination de Gauss, puisque c'est une méthode d'élimination successive des variables, lorsqu'avec l'aide des transformations élémentaires, les systèmes d'équations sont réduits sous une forme échelonnée (ou triangulaire), dans laquelle toutes les autres variables sont placées (en commençant par la dernière).

Maintenant quelques mots à propos de cette méthode.
Comment faire passer la variable $x_1$ à zéro dans la deuxième équation ?
En soustrayant la première, multiplié par un facteur $\frac{a_{21}}{a_{11}}$
Voici un exemple :

$2*x_1 + 3*x_2 + 4 * x_3 = 10 \\ 6*x_1 + 3*x_2 - 4 * x_3 = 7$

Zéro $x_1$ dans la première équation

$6*x_1 + 3*x_2 - 4 * x_3 - \frac{6}{2}(2*x_1 + 3*x_2 + 4 * x_3)= 7 - \frac{6}{2}10 \\ 6*x_1 + 3*x_2 - 4 * x_3 - 6*x_1 - 9*x_2 - 12 * x_3 = 7 - 30 \\ -6*x_2 - 16 * x_3 = -23$

Il n'y a aucun $x_1$ dans la deuxième équation
Dans un sens plus général, la méthode de Gauss peut être représentée ainsi :

$\begin{matrix}For\, j = 0,..., N-2 \\ \qquad \qquad For\,i = j + 1,..., N - 1 \\ \qquad \qquad \qquad \vec{a_i} \leftarrow \vec{a_i} - \frac{a_{ij}}{a_{jj}} \vec{a_j} \end{matrix}$

où N - dimension de la ligne,

$\vec{a_i}$ - i-row,
$a_{ij}$ - élément dans la ligne i, colonne j

Cela semble être une superbe méthode, mais il y a une chose. C'est la division par $a_{jj}$ qui a lieu dans la formule. Tout d'abord si l'élément de la diagonale est zéro, cette méthode ne fonctionne pas. Deuxièmement, durant le calcul la déviation va augmenter de plus en plus. Ainsi le résultat ne sera pas précis.
Pour réduire la déviation, des modifications de la méthode de Gauss sont utilisées. Elles se basent sur le fait que plus le dénominateur est grand, plus la déviation est faible. Ces modifications sont la méthode de Gauss avec la sélection maximale dans une colonne et la méthode de Gauss avec un choix maximal dans toute la matrice. Comme le nom l'indique, avant chaque étape d'exclusion de variable, l'élément avec la valeur maximal est cherché dans une ligne (ou toute la matrice) et une permutation de ligne est réalisée, ainsi elle changera de place avec $a_{jj}$ .

Néanmoins, il y a une modification radicale de la méthode de Gauss - la méthode de Bareiss.
Comment se débarrasser des divisions ? En multipliant la ligne $\vec{a_i}$ par $a_{jj}$ avant de soustraire. Ensuite, vous devez soustraire $\vec{a_i}$ , multiplié par $a_{ij}$ sans aucune division.
$\vec{a_i} \leftarrow a_{jj}\vec{a_i} - a_{ij} \vec{a_j}$ .
Cela a l'air bien, mais il y a un problème de croissance de la valeur des éléments durant les calculs.

Bareiss a proposé de diviser l'expression ci-dessus par $a_{j-1,j-1}$ et a monté que si les éléments de la matrice initiale sont des nombres entiers, alors le nombre résultant sera un entier. Il est également supposé que pour les lignes nulles $a_{-1,-1}=1$ .

D'ailleurs, le fait que l'algorithme de Bareiss réduise les éléments entiers de la matrice initiale vers une matrice triangulaire avec des éléments entiers, soit sans accumulation de déviation, est une caractéristique très importante du point de vue de la machine arithmétique.

L'algorithme de Bareiss peut être représenté ainsi :
$\begin{matrix} a_{-1,-1}=1 \\For\, j = 0,..., N-2 \\ \qquad \qquad For\,i = j + 1,..., N - 1 \\ \qquad \qquad \qquad \vec{a_i} \leftarrow \frac{a_{jj}\vec{a_i} - a_{ij} \vec{a_j}}{a_{j-1,j-1}} \end{matrix}$

Cet algorithme peut être amélioré, tout comme celui de Gauss, avec une sélection maximale dans une colonne (ou toute la matrice) et en réarrangeant les lignes correspondantes (lignes et colonnes).

PLANETCALC Calculatrices en ligne

Triangulation d'une matrice

Cette page existe grâce aux efforts des personnes suivantes :

Timur

Gaulthier Marrel

Triangulation d'une matrice (méthode de Gauss)

Triangulation d'une matrice (méthode de Bareiss)

Calculatrices similaires

commentaires

PLANETCALC Calculatrices en ligne

Triangulation d'une matrice (méthode de Gauss)

Triangulation d'une matrice (méthode de Bareiss)

Calculatrices similaires

commentaires

Partager la page