Suy Biến | My Weblog
Có thể bạn quan tâm
Trở ngại cuối cùng trong thuật toán đơn hình là tình huống lặp vô hạn khi gặp phải nghiệm cơ sở bị suy biến. Có hai nguyên nhân dẫn đến có thể xảy ra lặp vô hạn khi tiến hành thuật toán đơn hình:
- Khi tính toán , có hai giá trị mà
nên khi cập nhật, ta có . Tức là ta đi đến một nghiệm cơ sở bị suy biến.
- Thuật toán đi đến một nghiệm cơ sở bị suy biến (có it nhất một biến cơ sở bằng 0) và
do . Như vậy, nghiệm cơ sở không thay đổi mà chỉ có hệ cơ sở thay đổi. Có thể xảy ra trường hợp các véctơ cơ sở bị tráo đổi theo cách vòng tròn mà nghiệm cơ sở không hề thay đổi, dẫn tới tình huống lặp vô hạn (mặc dù khả năng này rất hiếm khi xảy ra).
Để ý rằng, trong phương pháp đơn hình, ta có quyền chọn cặp chỉ số chốt miễn là
Người ta chứng minh được rằng, nếu chọn theo những luật nhất định thì sẽ tránh được tình huống lặp vô hạn. Trong bài này, ta sẽ xem xét hai phương pháp đơn giản để khử vòng lặp vô hạn, đó là luật từ điển và luật Bland.
Định nghĩa (thứ tự từ điển): Ta nói véctơ có thứ tự từ điển nhỏ hơn véctơ , kí hiệu là hay nếu
nghĩa là ở chỉ số đầu tiên mà thì .
Lưu ý: định nghĩa có thể mở rộng cho hai véc tơ không có cùng số chiều, nhưng trong bài này ta chỉ quan tâm đến các véctơ có cùng số chiều.
Định nghĩa (thứ tự từ điển dương): Ta nói véctơ có thứ tự từ điển dương (gọi tắt là thứ tự dương) nếu hay .
Định nghĩa (luật từ điển): Luật từ điển là cách chọn chỉ số dòng tại mỗi bước lặp sao cho dòng được chọn có thứ tự từ điển nhỏ nhất khi chia cho phần tử chốt .
Định lý (tính dừng của luật từ điển): Nếu trong bước chọn dòng , ta luôn chọn dòng có thứ tự từ điển nhỏ nhất khi chia cho phần tử chốt thì
- Nếu các dòng của bảng (trừ dòng đầu tiên) đều có thứ tự dương, thì sau phép biến đổi dòng, các dòng này vẫn có thứ tự dương.
- Nếu các dòng của bảng (trừ dòng đầu tiên) đều có thứ tự dương, thì sau phép biến đổi dòng, thứ tự từ vựng của dòng đầu tiên tăng.
- Nếu các dòng của bảng ban đầu (trừ dòng đầu tiên) có thứ tự dương thì thuật toán đơn hình luôn dừng.
Chứng minh (1): Với những dòng mà thì nên nhân dòng với rồi cộng vào dòng ta vẫn có thứ tự dương.
Với những dòng mà thì , tức là dòng vẫn có thứ tự dương vì là giá trị đầu tiên trong dòng thứ ).
Với những dòng mà thì sau biến đổi dòng, dòng vẫn có thứ tự dương vì dòng chia cho có thứ tự từ điển nhỏ hơn dòng chia cho . Thật vậy, giả sử cột là cột đầu tiên mà
Trong đó lần lượt là các giá trị ở cột tại các hàng. Suy ra
Vì là giá trị đầu tiên khác trên dòng sau khi biến đổi dòng nên dòng có thứ tự dương.
Chứng minh (2): vì nên. Do vậy, khi nhân dòng thứ với rồi cộng vào dòng đầu tiên, thứ tự từ điển của dòng đầu tiên sẽ tăng lên (do dòng có thứ tự dương).
Chứng minh (3): Do số bảng đơn hình là hữu hạn (bằng số bộ cơ sở có thể có), mà thứ tự từ điển của dòng đầu tiên lại luôn tăng, nên đến lúc nào đó, thuật toán đơn hình phải dừng.
Nhận xét: Để tạo được các dòng có thứ tự dương trong bảng ban đầu, ta có thể đảo chỗ các biến bù lên đầu, như vậy ma trận , hơn nữa, (cột đầu tiên của bảng) nên tất cả các dòng của bảng (trừ dòng đầu tiên) đều có thứ tự dương.
Định nghĩa (Luật Bland): Cách lựa chọn cặp chỉ số chốt sau đây gọi là luật Bland:
- Trong bước chọn cột, chọn chỉ số nhỏ nhất sao cho.
- Trong bước chọn dòng, chọn chỉ số nhỏ nhất sao cho.
Định lý (tính dừng của luật Bland): Nếu lựa chọn cặp chỉ số chốt theo luật Bland thì thuật toán đơn hình luôn dừng.
Từ khóa » Không Suy Biến Là Gì
-
Ma Trận Khả Nghịch – Wikipedia Tiếng Việt
-
Định Thức – Wikipedia Tiếng Việt
-
Từ điển Tiếng Việt "suy Biến" - Là Gì?
-
Suy Biến Trong Toán Học Là Gì? - Blog Tổng Hợp Tin Tức định Nghĩa "là Gì"
-
" Suy Biến Là Gì ? Nghĩa Của Từ Suy Biến Trong Tiếng Việt Suy ...
-
Chứng Minh Một Ma Trận Suy Biến Và Ma Trận Khả Nghịch - Vted
-
Suy Biến Là Gì? Hiểu Thêm Văn Hóa Việt - Từ điển Tiếng Việt
-
Tài Liệu Ma Trận Không Suy Biến Là Ma Trận Như Thế Nào, Ma ...
-
[PDF] Bài 2 : MA TRẬN VÀ ĐỊNH THỨC - Topica
-
17.1. Phương Pháp Phân Tích Suy Biến — Deep AI KhanhBlog
-
[Hỏi] Về Xét Tính đơn điệu Của Hàm Số Chứa Tham Số. Các Bạn Giúp ...
-
Ma Trận Suy Biến Là Gì - Hỏi Gì?
-
Vecto Suy Biến Là Gì??? Câu Hỏi 1023449