Come verificare se i vettori di dimensione mn sono linearmente indipendenti?

Question

Declinazione di responsabilità
Questa non è una domanda di programmazione, ma la maggior parte dei programmatori deve occuparsi presto della matematica (in particolare l'algebra), quindi penso che la risposta potrebbe rivelarsi utile a qualcun altro in futuro.

Ora il problema
Sto cercando di verificare se m vettori di dimensione n sono linearmente indipendenti. Se m == n puoi semplicemente costruire una matrice usando i vettori e controllare se il determinante è! = 0. Ma cosa succede se m < n?

Eventuali suggerimenti?

---

Vedere anche this video lecture.

Answer 1

Costruire una matrice di vettori (una riga per vettore) ed eseguire un Gaussian elimination su questa matrice. Se una qualsiasi delle righe della matrice viene cancellata, esse non sono linearmente indipendenti.

Il caso banale è quando m> n, in questo caso, non possono essere linearmente indipendenti.

Answer 2

Costruire una matrice M le cui righe sono i vettori e determinare il rango di M. Se il grado di M è inferiore a m (il numero di vettori), allora esiste una dipendenza lineare. Nell'algoritmo per determinare il rango di M è possibile interrompere la procedura non appena si ottiene una riga di zeri, ma l'esecuzione dell'algoritmo a completamento ha il vantaggio aggiuntivo di fornire la dimensione del set spanning dei vettori. Oh, e l'algoritmo per determinare il grado di M è semplicemente l'eliminazione gaussiana.

Prestare attenzione all'instabilità numerica. Vedere l'avviso all'inizio del capitolo due in Ricette numeriche.

Answer 3

Se m<n, dovrete fare qualche operazione su di loro (ci sono molteplici possibilità: eliminazione Gaussiana, ortogonalizzazione, ecc., Quasi tutte le trasformazioni che possono essere usate per risolvere le equazioni lo faranno) e controllare il risultato (es. Eliminazione gaussiana => zero riga o colonna, ortogonalizzazione => zero vettore, SVD => zero numero singolare)

Tuttavia, si noti che questa domanda è una domanda non valida per un programmatore da porre e questo problema è un problema grave per un programma da risolvere. Questo perché ogni insieme linearmente dipendente di vettori n<m ha un diverso insieme di vettori linearmente indipendenti nelle vicinanze (ad esempio il problema è numericamente instabile)

Answer 4

Se la potenza di calcolo non è un problema, probabilmente il modo migliore è trovare valori singolari del matrice. Fondamentalmente è necessario trovare gli autovalori di M'*M e osservare il rapporto tra il più grande e il più piccolo. Se il rapporto non è molto grande, i vettori sono indipendenti.

Answer 5

Un altro modo per verificare che i vettori m riga sono linearmente indipendenti, quando viene messo in una matrice M di dimensioni mxn, è quello di calcolare

det(M * M^T) 

cioè il determinante di una matrice quadrata mxm. Sarà zero se e solo se M ha delle righe dipendenti. Tuttavia l'eliminazione gaussiana dovrebbe essere in generale più veloce.

Answer 6

Ho lavorato su questo problema in questi giorni.

In precedenza, ho trovato alcuni algoritmi relativi all'eliminazione Gaussiana o Gaussiana-Giordana, ma la maggior parte di questi algoritmi si applica solo alla matrice quadrata, non alla matrice generale.

di applicare per matrice generale, una delle migliori risposte potrebbe essere questo: http://rosettacode.org/wiki/Reduced_row_echelon_form#MATLAB

si possono trovare sia pseudo-codice e il codice sorgente in varie lingue. Per quanto mi riguarda, ho trasformato il codice sorgente Python in C++, il codice C++ fornito nel link sopra è in qualche modo complesso e inappropriato da implementare nella mia simulazione.

Spero che questo vi aiuterà, e buona fortuna ^^

Answer 7

uomo dispiace, il mio errore ...

---

Il codice sorgente fornito nel link qui sopra si rivela corretta, almeno il codice python che ho testato e il codice C++ che ho trasformato non genera la risposta giusta tutto il tempo. (Mentre per l'exmample nel link qui sopra, il risultato è corretto :) -)

Per verificare il codice python, è sufficiente sostituire il mtx con

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

e il risultato restituito sarebbe come:

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

Tuttavia, ho trovato una via d'uscita. È solo in questo momento che ho trasformato il codice sorgente matalb della funzione rref in C++. È possibile eseguire matlab e utilizzare il comando type rref per ottenere il codice sorgente di rref.

Basta notare che se si sta lavorando con un valore molto grande o un valore veramente piccolo, assicurarsi di utilizzare il tipo di dati in C++. In caso contrario, il risultato sarà troncato e incoerente con il risultato matlab.

Ho eseguito simulazioni di grandi dimensioni in ns2 e tutti i risultati osservati sono validi. spero che questo possa aiutare te e chiunque altro abbia incarnato il problema ...

Answer 8

Un modo molto semplice, che non è il più efficiente dal punto di vista computazionale, è semplicemente rimuovere le righe casuali fino allo m=n e quindi applicare il trucco determinante.

• m < n: rimuovere righe (rendere i vettori più brevi) fino a quando la matrice è quadrata, e quindi
• m = n: controllare se il determinante è 0 (come detto)
• m < n (il numero di vettori è maggiore della loro lunghezza): sono linearmente dipendenti (sempre).

La ragione, insomma, è che qualsiasi soluzione al sistema di equazioni m x n è anche una soluzione al sistema di equazioni n x n (si sta cercando di risolvere Av=0). Per una spiegazione migliore, vedi Wikipedia, che lo spiega meglio di me.