- HỆ PHƯƠNG TRÌNH ĐI-Ô-PHĂNG TUYẾN TÍNH. - 1.1 Dạng chuẩn Hecmit. - 1.2 Ma trận đơn môđula. - 2 Phương trình Đi-ô-phăng tuyến tính 14 2.1 Ước chung lớn nhất. - 2.3 Phương trình Đi-ô-phăng tuyến tính. - 2.4 Một số ứng dụng của phương trình Đi-ô-phăng. - 3 Hệ phương trình Đi-ô-phăng tuyến tính 32 3.1 Hệ phương trình Đi-ô-phăng tuyến tính. - 3.3 Thuật toán Hecmit. - 3.4 Nghiệm nguyên dương của hệ phương trình Đi-ô-phăng. - 3.5 Quy hoạch tuyến tính Đi-ô-phăng. - Phương trình Đi-ô-phăng tuyến tính (Linear Diophantine Equations) mang tên nhà toán học cổ Hy Lạp Đi-ô-phăng ở xứ Alexandria vào khoảng Thế kỷ thứ 3 sau Công nguyên. - Đi-ô-phăng đã viết một chuyên luận có tên “Arithmetica”, đó là cuốn sách sớm nhất được biết về lý thuyết số và đại số.. - Phương trình Đi-ô-phăng là phương trình đại số đòi hỏi tìm nghiệm hữu tỉ hoặc nguyên. - Phương trình đại số là phương trình chỉ bao gồm các biểu thức đa thức của một hoặc nhiều biến. - Tính “Đi-ô-phăng” của phương trình là ở chỗ các hệ số của đa thức phải là các số hữu tỉ (hoặc số nguyên) và nghiệm cũng chỉ có thể là số hữu tỉ (hoặc số nguyên).. - Hai phương trình quen biết từ lý thuyết số sơ khai, có từ trước thời Đi-ô-phăng là những ví dụ về phương trình Đi-ô-phăng. - Cả hai loại phương trình này đều đã được người Babylon biết đến. - Phương trình bậc nhất (tuyến tính), hai biến ax + by = c.. - Phương trình bậc hai (phi tuyến), ba biến x 2 + y 2 = z 2. - Luận văn này có mục đích tìm hiểu và trình bày thuật toán Ơ-clít tìm các nghiệm nguyên của phương trình Đi-ô-phăng tuyến tính n biến có dạng. - a n , b là các số hữu tỉ và thuật toán Hecmit tìm tất cả các nghiệm nguyên của hệ phương trình Đi-ô-phăng tuyến tính Ax = b với ma trận A và véctơ b hữu tỉ.. - nhắc lại các khái niệm của đại số về dạng chuẩn Hecmit và ma trận đơn môđula, liên quan tới việc giải hệ phương trình Đi-ô-phăng tuyến tính. - Đáng chú ý là mọi ma trận với các phần tử hữu tỉ và có hạng bằng số hàng của ma trận đều đưa được về dạng chuẩn Hecmit nhờ các phép biến đổi cột trên ma trận, dạng chuẩn này là duy nhất. - Dạng chuẩn Hecmit lại có quan hệ với các ma trận đơn môđula (ma trận nguyên, không suy biến và có định thức bằng +1 hay −1. - Với ma trận hữu tỉ A có hạng bằng số hàng luôn tồn tại ma trận đơn môđula U sao cho AU là dạng chuẩn Hecmit của A . - Nêu cách đưa một ma trận về dạng chuẩn Hecmit, cách tìm ma trận đơn môđula tương ứng và đưa ra các ví dụ số minh họa cách làm.. - Chương 2 "Phương trình Đi-ô-phăng tuyến tính". - đề cập tới phương trình Đi-ô-phăng tuyến tính của hai hay nhiều biến số. - Chương này trình bày nhiều định nghĩa và định lý cần thiết cho việc tìm tất cả các nghiệm nguyên của phương trình Đi-ô-phăng tuyến tính. - Cuối chương đề cập đến một số ví dụ ứng dụng thực tế của phương trình Đi-ô-phăng tuyến tính.. - Chương 3 "Hệ phương trình Đi-ô-phăng tuyến tính". - đề cập tới hệ phương trình Đi-ô-phăng tuyến tính và các điều kiện cần và đủ để hệ có nghiệm nguyên, dựa trên các kết quả lý thuyết về dạng chuẩn Hecmit và ma trận đơn môđula đã nêu ở Chương 1. - Sau đó, trình bày thuật toán Hecmit tìm tất cả các nghiệm nguyên của hệ phương trình Đi-ô-phăng tuyến tính. - Cuối chương đề cập tới nghiệm nguyên dương của hệ phương trình Đi-ô-phăng tuyến tính và bài toán qui hoạch tuyến tính Đi-ô-phăng.. - Trần Vũ Thiệu đã hướng dẫn tận tình tác giả hoàn thành luận văn này. - Chương này nhắc lại khái niệm về dạng chuẩn Hecmit và ma trận đơn môđula có liên quan tới việc giải hệ phương trình Đi-ô-phăng tuyến tính.. - Mục 1.1 nói về dạng chuẩn Hecmit: mọi ma trận với các phần tử hữu tỉ và có hạng bằng số hàng của ma trận đều đưa được về dạng chuẩn Hecmit, dạng chuẩn này là duy nhất. - Mục 1.2 nói tới ma trận đơn môđula: với ma trận hữu tỉ A có hạng bằng số hàng luôn tồn tại ma trận đơn môđula U sao cho AU là dạng chuẩn Hecmit của A . - Một ma trận cấp m × n có hạng bằng số hàng của ma trận được gọi là ở dạng chuẩn Hecmit (Hecmit normal form) nếu:. - • Ma trận có dạng [BO. - trong đó B là ma trận cấp m × m có nghịch đảo;. - • Các phần tử đường chéo của B dương;. - • Mọi phần tử khác của B không âm;. - • Phần tử lớn nhất ở mỗi hàng của B là duy nhất và nằm trên đường chéo chính của B , còn O là ma trận không cấp m × (n − m). - Sau đây là một ví dụ về ma trận ở dạng chuẩn Hecmit:. - Các phép toán sau về ma trận được gọi là phép toán cột sơ cấp (elementary column operations):. - Mọi ma trận với các phần tử hữu tỉ có hạng bằng số hàng của ma trận có thể đưa về dạng chuẩn Hecmit bằng cách thực hiện các phép toán cột sơ cấp.. - Giả sử A là một ma trận hữu tỉ với hạng bằng số hàng.. - Không giảm tổng quát, có thể xem A là ma trận với các phần tử nguyên.. - Giả sử ta đã biến đổi A (bằng cách thực hiện các phép toán cột sơ cấp) về dạng. - trong đó B có dạng tam giác dưới và mọi phần tử ở trên đường chéo là số dương. - d 1k = 0 và ta nhận được ma trận tam giác dưới lớn hơn.. - Bằng cách lặp lại thao tác này, cuối cùng ma trận A sẽ được biến đổi thành [BO] với B = (b ij ) là ma trận tam giác dưới với đường chéo dương.. - Tiếp theo, ta biến đổi ma trận B như sau. - Có thể thấy rằng sau một số phép biến đổi cột sơ cấp này, ma trận A sẽ đưa được về dạng chuẩn Hecmit.. - Ví dụ 1.1. - Đưa ma trận sau về dạng chuẩn Hecmit A. - Ta biến đổi D như sau: cột 3 trừ hai lần cột 1, cột 1 trừ hai lần cột 2 và đổi chỗ hai cột 1 và 2 ta lần lượt nhận được các ma trận. - Tiếp đó, nhân cột 2 với −1, cột 3 trừ cột 2, cột 2 trừ cột 3 và cột 3 trừ ba lần cột 2, ta nhận được các ma trận. - Tiếp theo, cột 2 trừ hai lần cột 3 và đổi chỗ hai cột 2, 3 ta được ma trận. - Cuối cùng, ta biến đổi B như sau: với i = 2 , lấy cột j = i − 1 = 1 trừ hai lần cột i = 2, ta được ma trận B không âm, dạng tam giác dưới, không suy biến và mỗi hàng của B có duy nhất một phần tử lớn nhất nằm trên. - Từ đó nhận được dạng chuẩn Hecmit duy nhất [BO]. - của ma trận A ban đầu:. - Nhóm G được gọi là một dàn nếu G sinh bởi các véctơ độc lập tuyến tính. - Nếu ma trận B nhận được từ ma trận A bằng các phép toán cột sơ cấp thì các cột của B và các cột của A sinh ra cùng một nhóm.. - a m là các véctơ hữu tỉ thì nhóm sinh bởi a 1 , a 2. - a m là một dàn, nghĩa là nhóm đó sinh bởi các véctơ độc lập tuyến tính.. - a m sinh ra toàn bộ không gian R n , vì nếu trái lại ta có thể áp dụng phép biến đổi tuyến tính đối với không gian có số chiều thấp hơn. - Giả sử A là ma trận với các cột a 1 , a 2. - a m , do dó A có hạng bằng số hàng của A . - Hệ phương trình Đi-ô-phăng tuyến tính. - 9 − 3y 3 nên bài toán qui hoạch tuyến tính nguyên Đi-ô-phăng (3.5) cho ví dụ này có dạng: