Làm cách nào để kiểm tra xem các vectơ cỡ n có độc lập tuyến tính hay không?

Question

Tuyên bố từ chối
Đây không phải là câu hỏi lập trình, nhưng hầu hết các lập trình viên sớm hay muộn phải đối phó với toán (đặc biệt là đại số), vì vậy tôi nghĩ câu trả lời có thể hữu ích cho người khác trong tương lai.

Bây giờ vấn đề
Tôi đang cố gắng kiểm tra xem v vectơ thứ nguyên n có độc lập tuyến tính hay không. Nếu m == n bạn chỉ có thể xây dựng một ma trận bằng cách sử dụng các vectơ và kiểm tra xem định thức là! = 0. Nhưng nếu m < n thì sao?

Bất kỳ gợi ý nào?

---

Xem thêm this video lecture.

Answer 1

Tạo ma trận của vectơ (một hàng trên mỗi véc tơ) và thực hiện Gaussian elimination trên ma trận này. Nếu bất kỳ hàng ma trận nào hủy bỏ, chúng không độc lập tuyến tính.

Trường hợp tầm thường là khi m> n, trong trường hợp này, chúng không thể độc lập tuyến tính.

Answer 2

Tạo ma trận M có hàng là véc tơ và xác định xếp hạng M. Nếu xếp hạng M nhỏ hơn m (số lượng vectơ) thì có sự phụ thuộc tuyến tính. Trong thuật toán để xác định thứ hạng của M, bạn có thể dừng quy trình ngay sau khi bạn nhận được một hàng số không, nhưng chạy thuật toán để hoàn thành có phần bổ sung cung cấp thứ nguyên của tập bao trùm của vectơ. Oh, và thuật toán để xác định thứ hạng của M chỉ đơn thuần là loại bỏ Gaussian.

Chăm sóc cho sự bất ổn định số. Xem cảnh báo ở đầu chương hai trong Bí quyết số.

Answer 3

Nếu m<n, bạn sẽ phải thực hiện một số thao tác trên chúng (có nhiều khả năng: loại bỏ Gaussian, trực giao, v.v., hầu như bất kỳ phép biến đổi nào có thể được sử dụng để giải phương trình) và kiểm tra kết quả (ví dụ: Loại trừ Gaussian => không có hàng hoặc cột, trực giao => số không vector, SVD => số không số lẻ)

Tuy nhiên, lưu ý rằng câu hỏi này là một câu hỏi không hay đối với lập trình viên, và vấn đề này là một vấn đề không tốt một chương trình để giải quyết. Đó là bởi vì mỗi bộ phụ thuộc tuyến tính của các vector n<m có một tập hợp các vectơ độc lập tuyến tính khác nhau gần đó (ví dụ: vấn đề không ổn định về số)

Answer 4

Nếu điện toán không phải là vấn đề, có lẽ cách tốt nhất là tìm giá trị số ít của ma trận. Về cơ bản bạn cần phải tìm giá trị riêng của M'*M và nhìn vào tỷ lệ lớn nhất đến nhỏ nhất. Nếu tỷ lệ không phải là rất lớn, các vectơ độc lập.

Answer 5

Một cách khác để kiểm tra xem vectơ m hàng là tuyến tính độc lập, khi đặt trong một ma trận M kích thước mxn, là để tính toán

det(M * M^T) 

ví dụ: yếu tố quyết định của một ma trận mxm vuông. Nó sẽ bằng không nếu và chỉ khi M có một số hàng phụ thuộc. Tuy nhiên, việc loại bỏ Gauss phải nhanh hơn.

Answer 6

Tôi đã làm việc về vấn đề này những ngày này.

Trước đây, tôi đã tìm thấy một số thuật toán liên quan đến loại bỏ Gaussian hoặc Gaussian-Jordan, nhưng hầu hết các thuật toán đó chỉ áp dụng cho ma trận vuông chứ không phải ma trận chung.

Để áp dụng cho ma trận chung, một trong những câu trả lời tốt nhất có thể là thế này: http://rosettacode.org/wiki/Reduced_row_echelon_form#MATLAB

Bạn có thể tìm thấy cả hai pseudo-code và mã nguồn bằng các ngôn ngữ khác nhau. Đối với tôi, tôi đã chuyển mã nguồn Python thành C++, khiến mã C++ được cung cấp trong liên kết ở trên bằng cách nào đó phức tạp và không phù hợp để thực hiện trong mô phỏng của tôi.

Hy vọng điều này sẽ giúp bạn, và chúc may mắn ^^

Answer 7

người đàn ông Xin lỗi, sai lầm của tôi ...

---

Mã nguồn được cung cấp trong liên kết ở trên hóa ra là không chính xác, ít nhất mã python tôi đã thử nghiệm và mã C++ tôi đã chuyển đổi không tạo ra câu trả lời đúng lúc nào. (Trong khi đối với các exmample trong liên kết trên, kết quả là đúng :) -)

Để kiểm tra mã python, bạn chỉ cần thay thế các mtx với

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

và kết quả trả về sẽ như thế nào:

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

Tuy nhiên, tôi đã có cách thoát khỏi điều này. Nó chỉ là thời gian này tôi đã chuyển mã nguồn matalb của hàm rref thành C++. Bạn có thể chạy MATLAB và sử dụng lệnh type rref để lấy mã nguồn của rref.

Chỉ cần lưu ý rằng nếu bạn đang làm việc với một số giá trị thực sự lớn hoặc giá trị thực sự nhỏ, hãy đảm bảo sử dụng kiểu dữ liệu long double trong C++. Nếu không, kết quả sẽ bị cắt bớt và không phù hợp với kết quả MATLAB.

Tôi đã tiến hành các mô phỏng lớn trong ns2 và tất cả các kết quả quan sát đều là âm thanh. hy vọng điều này sẽ giúp bạn và bất kỳ người nào khác đã giải quyết vấn đề ...

Answer 8

Một cách rất đơn giản, không hiệu quả về mặt tính toán, chỉ đơn giản là xóa hàng ngẫu nhiên cho đến m=n và sau đó áp dụng mẹo xác định.

• m < n: loại bỏ hàng (làm cho các vectơ ngắn hơn) cho đến khi ma trận là hình vuông, và sau đó
• m = n: kiểm tra xem yếu tố quyết định là 0 (như bạn nói)
• m < n (số lượng vectơ là lớn hơn chiều dài của chúng): chúng phụ thuộc tuyến tính (luôn luôn).

Lý do, trong ngắn hạn, là bất kỳ giải pháp cho hệ thống m x n phương trình cũng là một giải pháp cho hệ thống n x n của phương trình (bạn đang cố gắng để giải quyết Av=0). Để có giải thích tốt hơn, hãy xem Wikipedia, giải thích tốt hơn tôi có thể.