Comment vérifier si les vecteurs de taille M n sont indépendants de façon linéaire?

Construire une matrice M dont les rangs sont les vecteurs et déterminent le rang de M. Si le rang de Mm (le nombre de vecteurs), alors il existe une dépendance linéaire. Dans l'algorithme pour déterminer le rang de M vous pouvez arrêter la procédure dès que vous obtenez une rangée de zéros, mais l'exécution de l'algorithme à l'achèvement a l'avantage supplémentaire de fournir la dimension de l'ensemble de couverture des vecteurs. Oh, et l'algorithme pour déterminer le rang de M est simplement une élimination gaussienne.

attention à l'instabilité numérique. Voir l'avertissement au début du chapitre deux dans recettes numériques.

Si m<n, vous devrez faire une opération sur eux (il y a plusieurs possibilités: élimination gaussienne, orthogonalisation, etc., presque n'importe quelle transformation qui peut être utilisé pour résoudre des équations fera) et vérifier le résultat (par exemple. L'élimination de gauss => zéro de ligne ou de colonne, orthogonalization => vecteur nul, SVD => zéro singulier)

notez, Toutefois, que cette question est une mauvaise question pour un programmeur de demander, et ce problème est un grave problème pour un programme de résoudre. C'est parce que chaque linéairement dépendants ensemble de n<m les vecteurs ont un ensemble différent de vecteurs linéairement indépendants à proximité (p. ex. le problème est numériquement instable)

je travaille sur ce problème ces jours-ci.

auparavant, j'ai trouvé quelques algorithmes concernant L'élimination gaussienne ou gaussienne-Jordanie, mais la plupart de ces algorithmes ne s'appliquent qu'à la matrice carrée, pas à la matrice générale.

Pour appliquer la matrice, l'une des meilleures réponses pourrait être ce: http://rosettacode.org/wiki/Reduced_row_echelon_form#MATLAB

vous pouvez trouver à la fois du pseudo-code et du code source dans différentes langues. Comme pour moi, j'ai transformé le code source Python en C++, les causes le code C++ fourni dans le lien ci-dessus est en quelque sorte complexe et inapproprié à mettre en œuvre dans ma simulation.

j'Espère que cela va vous aider, et bonne chance ^^

Si la puissance de calcul n'est pas un problème, probablement la meilleure façon est de trouver des valeurs singulières de la matrice. Fondamentalement, vous devez trouver des valeurs propres de M'*M et regardez le rapport du plus grand au plus petit. Si le rapport n'est pas très grand, les vecteurs sont indépendants.

une autre façon de vérifier que les vecteurs de ligne sont linéairement indépendants, lorsqu'ils sont mis dans une matrice M de taille mxn, est de calculer

det(M * M^T)

c'est à dire le déterminant d'une mxm matrice carrée. Il sera zéro si et seulement si M a quelques lignes dépendantes. Cependant L'élimination gaussienne devrait être en général plus rapide.

Désolé mec, mon erreur...

le code source fourni dans le lien ci-dessus s'avère être incorrect, au moins le code python que j'ai testé et le code C++ que j'ai transformé ne génère pas toujours la bonne réponse. (alors que pour l'exmample dans le lien ci-dessus, le résultat est correct :) -- )

Pour tester le code python, il suffit de remplacer le mtx

[30,10,20,0],[60,20,40,0]

et le résultat serait comme:

[1,0,0,0],[0,1,2,0]

Néanmoins, j'ai un moyen de sortir de cette. C'est juste que cette fois j'ai transformé le code source de matalb de rref fonction vers C++. Vous pouvez lancer matlab et utiliser le type rref commande pour obtenir le code source de rref.

il suffit de noter que si vous travaillez avec une valeur vraiment grande ou vraiment petite, assurez-vous d'utiliser le long double type de données en c++. Sinon, le résultat sera tronqué et incompatible avec le matlab résultat.

je ont effectué de grandes simulations en ns2, et tous les résultats observés sont bons. j'espère que cela vous aidera, vous et tous ceux qui ont atténué le problème...

une façon très simple, qui n'est pas la plus efficace sur le plan informatique, consiste simplement à supprimer les lignes aléatoires jusqu'à m=n et ensuite appliquer le déterminant truc.

• m < n: supprimer les lignes (raccourcir les vecteurs) jusqu'à ce que la matrice soit carrée, puis
• m = n: vérifier si le déterminant est égal à 0 (comme vous l'avez dit)
• m < n (le nombre de vecteurs est plus grande que leur longueur): ils sont linéairement dépendants (toujours).

le la raison, en bref, est que toute solution du système d' m x n équations est aussi une solution pour l' n x n système d'équations (que vous essayez de résoudre Av=0). Pour une meilleure explication, voir Wikipédia, ce qui explique mieux que moi.