Bonjour,

Je souhaiterais trouver une méthode générale (si possible sous forme d'algorithme) pour vérifier si un système d'équation linéaire à n inconnues a une solution (il ne s'agit pas nécessairement de le résoudre)
Le problème réside également dans le fait qu'il s'agit de système dits creux, c'est à dire ayant beaucoup de coefficient nuls.

Sous forme matricielle on peut écrire cette équation Ax=b
Pour vous donner une idée voici un exemple de la matrice A :

1	1	0	1	0	0	0	0	0
1	1	1	0	1	0	0	0	0
0	1	1	0	0	1	0	0	0
1	0	0	1	1	0	1	0	0
0	1	0	1	1	1	0	1	0
0	0	1	0	1	1	0	0	1
0	0	0	1	0	0	1	1	0
0	0	0	0	1	0	1	1	1
0	0	0	0	0	1	0	1	1

Merci d'avance pour vos réponses

J'imagine que tu parles d'un système de n équations à n inconnues.

La méthode générale c'est de calculer le déterminant de ta matrice n*n

Il existe une formule générale du déterminant à partir des permutations

En général on n'utilise pas cette formule car elle fait apparaitre n! ( factorielle n ) termes, ce qui commence à faire beaucoup à partir de n=4 ou 5

C'est la méthode générale mais on ne l'utilise jamais, enfin à ma connaissance

Et en quoi le calcul du déterminant renseigne sur l'existence d'une ou plusieurs solution(s) ? Les solutions dépendent du vecteur b donc je vois pas à quoi ça mène...
De plus je précise que les calculs seront faits par un programme donc pas de souci pour la factorielle (si on reste raisonnable tout de même)

La méthode du pivot de Gauss te permettra de résoudre ton système.

Le problème c'est que le pivot de gauss, d'après mes essais, n'aime pas trop les matrices creuses... voici ce que j'obtiens pour la matrice précédente :

1	1	0	1	0	0	0	0	0
0	0	1	-1	1	0	0	0	0
0	0	-1	1	-1	0	0	0	0
0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0

Je me suis peut-être trompé mais en tout cas il me parait difficile d'obtenir une matrice d'identité à partir de là...

Si tu obtiens ça, en faisant les mêmes opérations sur le vecteur b,
soit les 6 dernières lignes sont nuls et tu as une infinité de solution, soit tu n'en as aucune. (qqn confirme?)

Citation : alcinos

Le problème c'est que le pivot de gauss, d'après mes essais, n'aime pas trop les matrices creuses...

Le pivot de Gauss aime toutes les matrices.

Alors comment faire quand on obtient un pivot nul ?

Cela correspond à une infinité de solution, comme l'équation <math>\(0*x=0\)</math>.

Akhenaton : la méthode de Cramer donne effectivement un calcul du déterminant en <math>\(O(n!)\)</math>, cepandant ce n'est pas la seule technique que l'on connait. La pivot de Gauss par exemple le calcul en <math>\(O(n^3)\)</math>. On arrive aujourd'hui sans aucune difficultés et sur n'importe quel ordinateur à inverser des matrices comportant des milliers de lignes.

Bonjour,

Citation : alcinos

Et en quoi le calcul du déterminant renseigne sur l'existence d'une ou plusieurs solution(s) ? Les solutions dépendent du vecteur b donc je vois pas à quoi ça mène...

C'est précisément ce à quoi sert le déterminant à l'origine : à déterminer si oui ou non un système d'équations linéaires possède une unique solution. C'est le cas si le déterminant est non nul. La méthode de Cramer montre bien ce résultat.

Sinon, en faisant une décomposition LU ou l'algorithme de Gauss Jordan avec pivot partiel, sont d'autres bonnes solutions.

Citation : alcinos

De plus je précise que les calculs seront faits par un programme donc pas de souci pour la factorielle (si on reste raisonnable tout de même)

Pourquoi ne pas calculer le déterminant de façon récursive alors dans ce cas?

Bonjour,

J'ai oublié de préciser quelque chose de fondamentale, c'est que je travaille sur Z/2Z par conséquent on a les règles de calcul suivantes :
0+0=1+1=0 et 0+1=1+0=1

Du coup l'existence ou non d'une ou de solutions (on peut en avoir un nombre fini différent de 1) dépend du vecteur b et non pas de la matrice A

Si on prend la matrice A suivante (pardon pour la mise en forme) :

1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1

Avec le vecteur b=[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] l'équation Ax=b n'a pas de solution dans Z/2Z
Tandis qu'avec la même matrice A, si on prend le vecteur b=[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
l'équation a 4 solutions :
x1=[0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0]
x2=[0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0]
x3=[1 1 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 1 1 0 1]
x4=[1 0 1 1 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1]

Cela a été dit, puis redit, mais je vais le reredire. Le calcul du déterminant de A renseigne de la manière suivante : si det A non nul, alors il existe une unique solution ; si det A = 0, on ne peut rien dire (du moins dans le cas général).

(Z/2Z étant un corps comme un autre, tu peux lui appliquer tout ce que tu as appris sur les matrices.)

Méthode de Cramer (ineffective algorithmiquement, mais prouve ce qui est dit précédemment).

Non justement, l'exemple que j'ai donné contredit ce que tu dis : le déterminant de A ne change pas d'une fois sur l'autre, donc selon toi le nombre de solution devrait rester inchangé quelque soit b, et pourtant avec les vecteurs b que j'ai donnés on trouve dans un cas aucune solution et dans l'autre exactement 4...

Ca sent l'exo 4 de prologin ça non ?

En réalité il existe énormément de méthode pour le démonter mais vaut mieux éviter le déterminant, c'est extremement long.

Si det(A)=0 alors tu as une infinité de solution en fixant une des valeurs

Bonsoir,

Si tu cherches à savoir à connaitre ton déterminant c'est pour inverser ta matrice, et donc résoudre le système non ?
Si tu veux résoudre ton système, il existe un tas de méthodes, mais il ne faut surtout pas passer par l'inversion de matrice, beaucoup trop lente.

Si cela t'intéresse, je peux te filer les sources de mon projet qui porte justement sur la résolution de ces systèmes :
http://www.siteduzero.com/forum-83-594 [...] c-linear.html

Hod, ton programme fonctionne certainement dans R, voici le résultat avec dans Z/2Z :


Pourtant le système a bien des solutions (cf poste précédent)

Il fonctionne dans R, mais ta remarque est intéressante dans le sens où je n'ai pas même pas pensé à spécifier quelque part qu'il s'agissait que de R (puisque c'est destiné avant tout pour un usage de l'ingénieur).

Peut-être que j'aurais la motivation de faire une version permettant de changer cela.
En attendant, il peut te permettre de poser les bases algorithmiques de ces méthodes et de la adapter à ta sauce.

Par contre, je serais intéressé de savoir quelle méthode t'a retournée ce résultat. Je pencherais pour une des deux premières puisque je discutais justement avec ma collègue de projet qui me souflait bien délicatement à l'oreille qu'en cas de pivot nul, la méthode ne marchait pas. C'est à implémenter également donc : un choix de pivot non-nul.

Oui c'est bien la méthode du pivot de gauss qui renvoie un tel résultat, mais la décomposition LU renvoie la même chose. Les autres méthodes ne sont pas plus fructueuses...

En fait la décomposition LU est basée sur celle de Gauss-Jordan. Elle permet simplement de réduire le nombre d'opération pour trouver le résultat lorsque l'on fait une série de mesure (cad que l'on ne change que le membre de droite).

Le soucis est du au fait, que l'algorithme est bête : il va prendre le pivot suivant sans se demander s'il est nul ou non. S'il est nul, il divise par zéro et te renvoie des résultats absurdes. Il faut donc que j'intègre de quoi contourner ce soucis, en laissant le programme choisir le pivot le plus intéressant.