Jak sprawdzić, czy wektory wielkości m n są liniowo niezależne?

Question

Disclaimer
To nie jest programowanie, ale większość programistów musi zajmować się matematyką (szczególnie algebrą), więc myślę, że odpowiedź może okazać się użyteczna dla kogoś innego w przyszłości.

Teraz problem
Próbuję sprawdzić, czy m wektory wymiaru n są liniowo niezależne. Jeśli m == n, możesz po prostu zbudować macierz używając wektorów i sprawdzić, czy wyznacznik to! = 0. Ale co, jeśli m < n?

Jakieś wskazówki?

---

Zobacz także this video lecture.

Answer 1

Skonstruuj macierz wektorów (jeden wiersz na wektor) i wykonaj Gaussian elimination na tej macierzy. Jeśli którykolwiek z wierszy macierzy zostanie anulowany, nie są one liniowo niezależne.

Ten trywialny przypadek ma miejsce, gdy m> n, w tym przypadku nie mogą być liniowo niezależne.

Answer 2

Skonstruuj macierz M, której wiersze są wektorami i określ pozycję M. Jeśli pozycja M jest mniejsza niż m (liczba wektorów), wówczas istnieje zależność liniowa. W algorytmie określającym pozycję M można zatrzymać procedurę, gdy tylko uzyska się jeden wiersz zer, ale uruchomienie algorytmu do końca ma dodatkową wartość, pozwalającą na określenie wymiaru zbioru spinającego wektorów. Aha, a algorytm wyznaczania rangi M jest po prostu gaussowską eliminacją.

Zadbaj o niestabilność numeryczną. Zobacz ostrzeżenie na początku rozdziału drugiego w Przepisach numerycznych.

Answer 3

Jeśli m<n, będziesz musiał wykonać na nich pewną operację (istnieje wiele możliwości: eliminacja Gaussa, ortogonalizacja itp., Prawie każda transformacja, która może być użyta do rozwiązywania równań) i sprawdzenie wyniku (np. Eliminacja Gaussa => zerowy wiersz lub kolumna, ortogonalizacja => wektor zerowy, SVD => zero liczba pojedyncza)

Należy jednak zauważyć, że to pytanie jest dla programiści złym pytaniem, a ten problem stanowi zły problem dla program do rozwiązania. Dzieje się tak, ponieważ każdy liniowo zależny zbiór wektorów n<m ma inny zestaw liniowo niezależnych wektorów w pobliżu (np. Problem jest niestabilny numerycznie)

Answer 4

Jeśli moc obliczeniowa nie jest problemem, prawdopodobnie najlepszym sposobem jest znalezienie osobliwych wartości matryca. Zasadniczo musisz znaleźć wartości własne M'*M i spojrzeć na stosunek największej do najmniejszej. Jeśli stosunek nie jest zbyt duży, wektory są niezależne.

Answer 5

Innym sposobem, aby sprawdzić, czy M wektorów rzędów są liniowo niezależne, gdy umieszcza się w macierzy M, rozmiaru MXN jest obliczenie

det(M * M^T) 

to znaczy determinantę mxm kwadratowy podłoża. Będzie zero wtedy i tylko wtedy, gdy M ma pewne wiersze zależne. Jednak gaussowska eliminacja powinna być generalnie szybsza.

Answer 6

Pracuję nad tym problemem w dzisiejszych czasach.

Wcześniej znalazłem kilka algorytmów dotyczących eliminacji Gaussa lub Gaussa-Jordana, ale większość tych algorytmów dotyczy tylko macierzy kwadratowej, a nie macierzy ogólnej.

Aby ubiegać się o ogólnym matrycy, jeden z najlepszych odpowiedzi może być w ten sposób: http://rosettacode.org/wiki/Reduced_row_echelon_form#MATLAB

Można znaleźć zarówno pseudo-kod i kod źródłowy w różnych językach. Co do mnie, zamieniłem kod źródłowy Pythona na C++, powoduje, że kod C++ zawarty w powyższym linku jest w jakiś sposób złożony i niewłaściwy do implementacji w mojej symulacji.

nadzieję, że to pomoże i powodzenia ^^

Answer 7

Niestety człowiek, mój błąd ...

---

Kod źródłowy przewidziane w powyższym linku okazuje się być nieprawidłowe, co najmniej testowany przeze mnie kod Pythona i zmieniony przeze mnie kod C++ nie generuje prawidłowej odpowiedzi przez cały czas. (A przez exmample w powyższym linku, wynik jest prawidłowy :) -)

Aby przetestować kod Pythona, po prostu zastąpić mtx z

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

i zwróconego wyniku byłoby jak:

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

Mimo to mam wyjście z tego. Właśnie tym razem zamieniłem kod źródłowy programu Matalb na rref na C++. Możesz uruchomić matlab i użyć polecenia type rref, aby uzyskać kod źródłowy rref.

Po prostu zauważ, że jeśli pracujesz z naprawdę dużą wartością lub naprawdę małą wartością, upewnij się, że użyłeś long double typów danych w C++. W przeciwnym razie wynik zostanie obcięty i niespójny z wynikiem matlab.

Przeprowadzałem duże symulacje w ns2, a wszystkie zaobserwowane wyniki są dźwiękiem. mam nadzieję, że to pomoże tobie i każdemu, kto zablokował problem ...

Answer 8

Bardzo prosty sposób, który nie jest najbardziej wydajny obliczeniowo, polega po prostu na usunięciu losowych wierszy do m=n, a następnie zastosowaniu sztuczki decydującej.

• m < n wynieść rzędów (aby wektory krótszy), aż matryca jest kwadratowy, a następnie
• m = n: sprawdzenie, czy wyznacznik 0 (jak to powiedziane)
• m < n (liczby nosicieli większa niż ich długość): są liniowo zależne (zawsze).

Powodem, w skrócie, jest to, że każde rozwiązanie do systemu m x n równań jest także rozwiązanie układu równań z n x n (starasz się rozwiązać Av=0). Aby uzyskać lepsze wyjaśnienie, zobacz: Wikipedia, który wyjaśnia to lepiej niż ja.