Como verificar se m vetores n porte são linearmente independentes?

Question

Aviso
Isto não é estritamente uma questão de programação, mas a maioria dos programadores cedo ou mais tarde têm de lidar com a matemática (especialmente álgebra), então eu acho que a resposta poderia vir a ser útil para alguém no futuro.

Agora o problema
Eu estou tentando verificar se m vetores de dimensão n são linearmente independentes. Se m == n você pode apenas construir uma matriz usando os vetores e verifique se o determinante é! = 0. Mas e se m

Alguma dica?

---

Veja também este vídeo palestra .

Answer 1

construir uma matriz dos vectores (uma linha por vector), e executar uma Gaussian eliminação nesta matriz. Se qualquer uma das linhas da matriz anula, eles não são linearmente independentes.

O caso é trivial quando m> n, neste caso, eles podem não ser linearmente independentes.

Answer 2

Construir um M matriz cujas linhas são os vetores e determinar o grau de M. Se o posto de M é inferior a m (o número de vectores), em seguida, existe uma dependência linear. No algoritmo para determinar a classificação de M você pode parar o processo, logo que você obter uma linha de zeros, mas a execução do algoritmo para a conclusão tem a bonança adicional de fornecer a dimensão do conjunto gerador dos vetores. Oh, e o algoritmo para determinar a classificação de M é meramente eliminação de Gauss.

cuidar de instabilidade numérica. Veja o aviso no início do capítulo dois em Numerical Recipes.

Answer 3

Se m<n, você vai ter que fazer alguma operação sobre eles (existem várias possibilidades: eliminação de Gauss, ortogonalização, etc., quase qualquer transformação que pode ser usada para resolver equações vai fazer) e verificar o resultado (por exemplo, Gaussian. eliminação => fila zero ou coluna, ortogonalização => vetor zero, SVD => de zero número singular)

No entanto, nota que esta questão é uma pergunta ruim para um programador para perguntar, e este problema é um mau problema para um programa para resolver. Isso porque cada conjunto linearmente dependente de vetores n<m tem um conjunto diferente de vetores linearmente independentes próxima (por exemplo. O problema é numericamente instável)

Answer 4

Tenho vindo a trabalhar sobre este problema nos dias de hoje.

Anteriormente, eu encontrei alguns algoritmos sobre Gaussian ou eliminação de Gauss-Jordan, mas a maioria desses algoritmos só se aplicam a matriz quadrada, não matriz geral.

Para se candidatar a matriz geral, um dos melhores respostas pode ser esta: http://rosettacode.org/wiki/Reduced_row_echelon_form#MATLAB

Você pode encontrar tanto pseudo-código e código-fonte em várias línguas. Quanto a mim, eu transformou o código fonte Python para C ++, faz com que o código C ++ fornecido no link acima é de alguma forma complexa e inadequada para implementar na minha simulação.

Espero que isso irá ajudá-lo, e boa sorte ^^

Answer 5

Se o poder de computação não é um problema, provavelmente a melhor maneira é encontrar valores singulares da matriz. Basicamente, você precisa encontrar valores próprios de M'*M e olhar para a relação entre a maior para o menor. Se a relação não é muito grande, os vetores são independentes.

Answer 6

Outra forma de verificar que m vectores de linha são linearmente independentes, quando colocado numa matriz M de tamanho mxn, é a computação

det(M * M^T)

i. o determinante de uma matriz quadrada mxm. Ele será zero se e somente se M tem algumas linhas dependentes. No entanto eliminação de Gauss deve ser, em geral, mais rápido.

Answer 7

homem Desculpe, meu erro ...

---

O código-fonte fornecido no link acima acaba por ser incorreta, pelo menos, o código python Eu testei eo código C ++ I transformaram não gera a resposta certa o tempo todo. (Enquanto que para o exmample no link acima, o resultado está correto :) -)

Para testar o código python, basta substituir o mtx com

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

e o resultado retornado seria como:

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

No entanto, eu tenho uma maneira de sair dessa. É apenas desta vez eu transformou o código fonte matalb da função rref para C ++. Você pode executar o Matlab e usar o comando type rref para obter o código fonte de rref.

Apenas aviso que, se você está trabalhando com alguns realmente grande valor ou muito pequeno valor, certifique-se o uso do tipo de dados long double em C ++. Caso contrário, o resultado será truncado e inconsistente com o resultado Matlab.

Eu têm vindo a realizar grandes simulações em ns2, e todos os resultados observados são sólidos. espero que isso irá ajudá-lo e qualquer outro que encontered o problema ...

Answer 8

Uma maneira muito simples, que não é o mais computacionalmente eficiente, é simplesmente remover linhas aleatórias até m=n e depois aplicar o truque determinante.

• m < n: linhas Remover (fazer os vetores mais curto) até que a matriz é quadrada, e depois
• m = n: verificação se o determinante é 0 (como você disse)
• m < n (o número de vectores é maior do que o seu comprimento.): Eles são linearmente dependente (sempre)

A razão, em suma, é que qualquer solução para o sistema de equações m x n também é uma solução para o sistema n x n de equações (você está tentando resolver Av=0). Para uma explicação melhor, consulte Wikipedia , o que explica que melhor do que eu.