Thuật toán tìm ma trận bậc thang

Để lại phản hồi Go to comments

Bước 1: Kiểm tra a_{11} \ne 0 ?

1.1 Nếu a_{11} = 0 và a_{i1} \ne 0 , ta đổi chỗ vị trí hàng 1 và hàng i.

1.2 Nếu a_{11} \ne 1 và a_{k1} = 1 , ta đổi chỗ vị trí hàng 1 và hàng k để cho bước 2 đơn giản.

1.3 Nếu tất cả các phần tử của cột 1 bằng 0 thì cột 1 coi như bước 2 đã hoàn thành, chuyển sang bước 3.

Bước 2: Khử tất cả các phần tử của cột 1 dưới a_{11} bằng phép biến đổi:

h_i \to h_i - { \dfrac{a_{i1}}{a_{11}}} h_1 , (i = 2, 3, ... m)

Khi đó, ma trận sẽ có dạng:

Chuẩn hóa cột 1 để đưa về dạng b�c thang dòng

Chuẩn hóa cột 1 để đưa về dạng bậc thang dòng

Bước 3: Kiểm tra b_{22} \ne 0 ?

1.1 Nếu b_{22} = 0 và b_{j2} \ne 0 (j > 2) , ta đổi chỗ vị trí hàng 2 và hàng j.

1.2 Nếu b_{22} \ne 1 và b_{k2} = 1 , ta đổi chỗ vị trí hàng 2 và hàng k để cho bước 4 đơn giản.

1.3 Nếu tất cả các phần tử của cột 2 (từ b_{22} trở xuống) bằng 0 thì cột 2 đã được chuẩn hóa, coi như bước 4 đã hoàn thành

Bước 4: Khử tất cả các phần tử của cột 2 ở dưới b_{22} bằng phép biến đổi:

h_i \to h_i - { \dfrac{b_{i2}}{b_{22}}} h_2 , (i = 3, ... m)

Ma trận đưa về dạng:

Chuẩn hóa cột 2

Chuẩn hóa cột 2

Tiếp tục quá trình trên cho phần tử c_{33} , phần tử ở dòng 4, cột 4; … ta sẽ đưa ma trận về dạng bậc thang dòng.

Ví dụ: Đưa ma trận sau về dạng bậc thang:

\left ( \begin{array}{ccccc} 0 & 4 & 1 & 10 & 3 \\ 4 & 8 & 7 & 18 & 35 \\ 10 & 18 & 17 & 40 & 83 \\ 1 & 7 & 3 & 17 & 9 \\ \end{array} \right )

Bước 1: Phần tử a_{11} = 0 , a_{i1} \ne 0 , (i = 2, 3, 4) . Tuy nhiên a_{41} = 1 nên ta hoán đổi vị trí dòng 1 và dòng 4. Ta có:

\left ( \begin{array}{ccccc} 1 & 7 & 3 & 17 & 9 \\ 4 & 8 & 7 & 18 & 35 \\ 10 & 18 & 17 & 40 & 83 \\ 0 & 4 & 1 & 10 & 3 \\ \end{array} \right )

Bước 2:Lần lượt thực hiện các phép biến đổi: h_2 \to h_2 - 4h_1, h_3 \to h_3 - 10h_1 . Ta có:

\left ( \begin{array}{ccccc} 1 & 7 & 3 & 17 & 9 \\ 0 & -20 & -5 & -50 & -1 \\ 0 & -52 & -13 & -130 & -7 \\ 0 & 4 & 1 & 10 & 3 \\ \end{array} \right )

Bước 3: Xét giá trị ở dòng 2, cột 2. Ta thấy a_{22} = -20 là 1 số khá lớn. Nếu để nguyên như thế thì các bước sau chắc chắn xuất hiện phân số. Điều này làm cho bài toán rối rắm hơn.

Nhận thấy: 20 và 52 đều cho hết cho 4 nên ta đổi chỗ dòng 2 và dòng 4. Ta có:

\left ( \begin{array}{ccccc} 1 & 7 & 3 & 17 & 9 \\ 0 & 4 & 1 & 10 & 3 \\ 0 & -52 & -13 & -130 & -7 \\ 0 & -20 & -5 & -50 & -1 \\ \end{array} \right )

Bước 4: Lần lượt thực hiện các phép biến đổi: h_3 \to h_3 + 13h_2, h_4 \to h_4 + 5h_2 . Ta có:

\left ( \begin{array}{ccccc} 1 & 7 & 3 & 17 & 9 \\ 0 & 4 & 1 & 10 & 3 \\ 0 & 0 & 0 & 0 & 32 \\ 0 & 0 & 0 & 0 & 14 \\ \end{array} \right )

Tiếp theo, ta chia dòng 3 cho 32 và chia dòng 4 cho 14. Ta có:

\left ( \begin{array}{ccccc} 1 & 7 & 3 & 17 & 9 \\ 0 & 4 & 1 & 10 & 3 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right )

Bước 5: Xét giá trị ở dòng 3, cột 3.

Nhận thấy các phần tử a_{33} = 0, a_{43} = 0 nên cột 3 đã được chuẩn hóa.

Do đó, ta chuyển sang chuẩn hóa cột 4 bằng cách xét phần tử a_{34}

Do a_{34} = 0 , và a_{44} = 0 nên ta cột 4 đã được chuẩn hóa. Ta chuyển sang cột 5. Lấy dòng 4 trừ dòng 3.

Ta có:

\left ( \begin{array}{ccccc} 1 & 7 & 3 & 17 & 9 \\ 0 & 4 & 1 & 10 & 3 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} \right )

Sau bước này ta đã có được ma trận bậc thang dòng. Vậy ta đã có dạng bậc thang

Để chuyển về ma trận bậc thang chính tắc. Ta tiếp tục thực hiện các phép biến đổi trên cột như sau:

Bước 6: Bằng cách thực hiện phép biến đổi: c_2 \to c_2 -7c_1 , c_3 \to c_3 - 3c_1 , c_4 \to c_4 - 17c_1 , c_5 \to c_5 - 9c_1 . Ta có:

\left ( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 4 & 1 & 10 & 3 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} \right )

Bước 7: Đổi chỗ cột 2 và cột 3. Ta có:

\left ( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 4 & 10 & 3 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} \right )

Bằng cách thực hiện phép biến đổi: c_3 \to c_3 -4c_2 , c_4 \to c_4 - 10c_2 , c_5 \to c_5 - 3c_2 . Ta có:

\left ( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} \right )

Bước 9: Do xuất hiện cột không nên ta cần đổi chỗ cột 3 và cột 5. Mục đích để cột không nằm ở vị trí cuối cùng. Ta có:

\left ( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} \right )

Vậy ta có dạng ma trận bậc thang chính tắc:

\left ( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} \right )

  1. ngoc ha
    05.11.2009 lúc 09:18 | #1
    Trả lời | Trích dẫn

    vd ta có ma trận vuông sau

    7 3 4 5
    3 1 4 5
    6 7 8 9
    4 6 5 2

    Khi đưa ma trận sau về dạng bậc thang nếu như em không muốn đổi các dòng với nhau, thì em có thể đưa d3-> 7d3-6d1 vẫn đúng đúng không thầy?
    Ta vẫn có thể áp dụng như vậy đối với ma trận hệ số mở rộng khi giải phương trình?
    Còn khi tính định thức thì không được nhân 7 vào dòng 3 vì khi đó giá trị định thức đã tăng 3 lần đúng không thầy?

    • 2Bo02B
      05.11.2009 lúc 13:44 | #2
      Trả lời | Trích dẫn

      Khi đó, giá trị của định thức tăng lên 7 lần lận em à

  2. ngoc ha
    05.11.2009 lúc 09:20 | #3
    Trả lời | Trích dẫn

    Các phép biến đổi sơ cấp ở cột cũng chỉ áp dụng được khi đưa ma trận về dạng ma trận bậc thang với khi tính định thức. Chứ khi giải phương trình (dùng ma trận hệ số mở rộng thì không được dùng đúng không thầy?

  3. nguyen khoi
    18.11.2009 lúc 18:58 | #4
    Trả lời | Trích dẫn

    đồng ý, khi giải hệ pt bằng pp Gauss ta chỉ cần đưa về dạng bậc thang, nhưng khi dùng pp Jordan gauss phải đưa về dạng Hermit (bậc thang thu gọn),và các phép biến đổi sơ cấp đều phải dùng cho hàng, không được dùng cho cột vì thứ tự và giá trị các phần tử trong cột có liên quan đến biến (ẩn số), làm như vậy sẽ dẫn đến thay đổi bản chất của ma trận đang giải

Comment pages
  1. No trackbacks yet.