Giải hệ thống PT ĐSTT

Chia sẻ: Lưu Hoàng Em Hoàng Em | Ngày: | Loại File: PPT | Số trang:79

Thêm vào BST

Báo xấu

127
lượt xem 21
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phương pháp Gaoxơ là một phương pháp được dùng phổ biến để giải hệ thống phương trình (3.1) khi ma trận hệ số A không có đặc điểm gì (trừ điều kiện không suy biến). Đặc biệt, người ta thường dùng phương pháp này khi ma trận hệ số A “đầy”. Để đơn giản việc trình bày, xét hệ thống 4 phương trình 4 ẩn số

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giải hệ thống PT ĐSTT

Báo Cáo Chương Lưu Hoàng em – DH7A2 Đại học An Giang
• ĐẶT VẤN ĐỀ • PHƯƠNG PHÁP TRỰC TIẾP: PHƯƠNG PHÁP GAOXƠ (HAY PHƯƠNG PHÁP KHỬ) • NHỮNG PHƯƠNG PHÁP LẶP
BÀI 1. ĐẶT VẤN ĐỀ Trong chương này, ta xét giải hệ thống phương trình đại số tuyến tính (pt đstt) n pt n ẩn.  a11 x1 + a12 x2 + a13 x3 + ... + a1n xn = a1n+1 a x + a x + a x + ... + a x = a  21 1 2 n +1 22 2 23 3 2n n (3.1)   ... ... ... ... ...  an1 x1 + an 2 x2 + an 3 x3 + ... + ann xn = ann +1  Muốn giải hệ thống pt này bằng pp Crame thì khối lượng tính rất lớn khi n lớn. Vì vậy, người ta phải xây dựng những pp sao cho khối lượng tính có thể thực hiện được khi n lớn.
Những pp giải hệ thống pt (3.1) được chia làm 2 loại: những pp trực tiếp và những pp lặp. Việc chọn pp giải phụ thuộc vào đặc điểm cảu ma trận hệ số A của hệ. Việc chọn không phải là một nguyên tắc cứng nhắc, không phải không có những trường hợp ngoại lệ.
BÀI 2. PHƯƠNG PHÁP GAOXƠ 2.1. Nội dung pp 2.2. Sơ đồ tính 2.3. Kiểm tra quá trình tính 2.4. Khối lượng tính 2.5. Sai số của pp Gaoxơ 2.6. PP Gaoxơ có tìm trụ lớn nhất 2.7. Tính định thức bằng pp Gaoxơ 2.8. Tính ma trận nghịch đảo bằng pp Gaoxơ 2.9. Chuẩn của ma trận và chuẩn của pp vectơ 2.10. Sự không ổn định của hệ thống pt đstt
2.1. Nội dung pp Phương pháp Gaoxơ là một phương pháp được dùng phổ biến để giải hệ thống phương trình (3.1) khi ma trận hệ số A không có đặc điểm gì (trừ điều kiện không suy biến). Đặc biệt, người ta thường dùng phương pháp này khi ma trận hệ số A “đầy”. Để đơn giản việc trình bày, xét hệ thống 4 phương trình 4 ẩn số sau:  a11(0) x1 + a12 (0) x2 + a13(0) x3 + a14 (0) x4 = a15(0)  (0) a21 x1 + a22 (0) x2 + a23(0) x3 + a24 (0) x4 = a25(0)  (3.4)  (0) a31 x1 + a 32 (0) x2 + a33(0) x3 a34 x4 = a35 (0) (0)  a41(0) x1 + a42 (0) x2 + a43(0) x3 + a44 (0) x4 = a45(0) 
Nội dung cơ bản của PP Gaoxơ là khử dần các ẩn số để đưa hệ (3.4) về hệ “tam giác” tương đương (ma trận hệ số của hệ là ma trận tam giác trên):  x1 + a12 (1) x2 + a13(1) x3 + a14 (1) x4 = a15(1)  x2 + a23(1) x3 + a24 (1) x4 = a25(1)  (3.5)  x3 + a34 x4 = a35 (1) (1)   x4 = a45(1)  Sau đó giải hệ (3.5) từ dưới lên trên. Quá trình đưa hệ (3.4) về hệ (3.5) gọi là quá trình thuận, quá trình giải hệ (3.5) gọi là quá trình ngược.
a) Quá trình thuận Khử x1 . Giả sử a11 ≠ 0 (a11 gọi là trụ thứ nhất). Chia (0) (0) phương trình đầu của hệ (3.4) cho a11(0) , ta nhận được: x1 + a12 (1) x2 + a13(1) x3 + a14 (1) x4 = a15(1) (3.6) (aij(1) = aij(0) , j = 2,3, 4,5) Dùng pt (3.6) khử x1 trong ba pt còn lại của hệ (3.6). Muốn thế, đem pt thứ hai của hệ (3.4) trừ pt (3.6) đã nhân vớia21(0) đem phương trình thứ ba của hệ (3.4) trừ phương trình (3.6) đã av (0) nhân 31ới đem phương trìng thứ tư của hệ (3.4) trừ phương trình (3.6) đã nhân với a41(0)
Kết quả nhận được hệ ba phương trình sau: a22 (1) x2 + a23(1) x3 + a24 (1) x4 = a25(1)  (1) a32 x2 + a33(1) x3 + a34 (1) x4 = a35(1) (3.7)  a (1) x + a (1) x + a (1) x = a (1)  42 2 43 3 44 4 45 (aij(1) = aij(0) − a11(0) aij(1) , i = 2,3, 4; j = 2,3, 4,5) a22 (1) ≠ 0( a22 (1) gọi là trụ hạng thứ hai). Khử x2 . Giả sử Chia pt đầu của hệ (3.7) cho , ta được: a22 (1) x2 + a23(2) x3 + a24 (2) x4 = a25(2) (3.8) (a2 j (2) = a2 j (1) / a22 (1) , j = 3, 4,5).
Đem phương trình thứ hai của hệ (3.7) trừ phương trình (1) avới . (3.8) đã nhân 42 Kết quả nhận được hệ hai phương trình sau:  a33(2) x3 + a34 (2) x4 = a35(2) ( 3.9 )  (2) a43 x3 + a44 (2) x4 = a45(2)  (aij(2) = aij (1) − ai 2(1) a2 j (2) , i = 3, 4; j = 3, 4,5)
Khử x3 . Giả sử a33 ≠ 0(a33 gọi là trụ thứ ba). Chia pt (2) (2) đầu của hệ (3.9) cho a33(2) và đem pt thứ hai của hệ (3.9) trừ pt vừa nhận được đã nhân với a43(2) ,ta được: x3 + a34 (3) x4 = a35(3) ( 3.10 ) ( 3.11) a44 (3) x4 = a45(3) (a3 j (3) = a3 j (2) / a33(2) , a4 j (3) = a4 j (2) − a43(2) a3 j (3) , j = 4,5) Cuối cùng nếu a44 ≠ 0 (a44 gọi là trụ thứ tư), ta (3) (3) chia pt (3.11) cho a44 (3) , pt (3.11) có dạng: x4 = a45(4) ( 3.12 ) ( ) a 45 (4) = a45(3) / a44(3)
(0) (1) (2) (3) Rõ ràng là các phần tử trụ a11 ,a22 ,a33 vaøa44 khác không thì hệ thống phương trình (3.4) tương đương với hệ thống phương trình “tam giác” sau:  x1 + a12 (1) x2 + a13(1) x3 + a14 (1) x5 = a15(1)  x2 + a23(2) x3 + a24 (2) x4 = a25(2)  ( 3.13)  x3 + a34 (3) x4 = a35(3)   x4 = a45(4) 
b) Quá trình ngược: Giải hệ thống (3.13) từ dưới lên, ta có: x4 = a45(4) ( 3.14 ) x3 = a35(3) − a34 (3) x4 x2 = a25(2) x3 − a23(2) x3 − a24 (2) x4 x1 = a15(1) − a12 (1) x2 − a13(1) x3 − a14 (1) x4 Chú ý rằng điều kiện để áp dụng phương pháp Gaoxơ là các phần tử trụ phải khác không.
2.2. Sơ đồ tính Phân tích quá trình áp dụng phương pháp Gaoxơ ở mục 2.1 ta thấy: để đưa hệ thống (3.4) về hệ thống “tam giác” tương đương (3.13), chỉ cần tính các hệ số a1 j (1) ( j = 2,5), aij(1) (i = 2, 4; j = 2,5), a2 j (2) ( j = 3,5), aij(2) (i = 3, 4; j = 3,5), a3 j (3) , a4 j (3) ( j = 4,5), a45(4) . Kết quả tính, trong trường hợp không dùng máy tính điện tử, thường được ghi thành bảng, gọi là sơ đồ Gaoxơ, trong đó cột ∑ dùng để kiểm tra quá trình tính.
2.3. Kiểm tra quá trình tính Khi không dùng máy tính điện tử, để có thể kiểm tra từng bước quá trình tính toán của phương pháp Gaoxơ, người ta 5 ∑ ( 3.15 ) dùng “tổng kiểm tra” a (0) = a (0) , i = 1;2;3;4 i6 ij (nó chính là tổng những phầnj =1 thuộc hàng I cùa ma trận hệ tử số A và số hạng vế phải tương ứng) như một vế phải mới của hệ thống phương trình (3.4) và xét hệ thống phương trình: 4 ∑ ( 3.16 ) aij x j = ai(0) , i = 1;2;3;4 (0) 6 j =1 ( 3.17 ) Rõ ràng là: x j = x j + 1, i = 1;2;3;4
Thật vậy, thay (3.17) vào (3.16) do (3.4), ta nhân được: 4 4 ∑ aij x j = ∑ aij ( x j + 1) (0) (0) j =1 j =1 4 4 4 5 = ∑ aij x j + ∑ aij = ai5 + ∑ aij = ∑ aij = ai(0) , i = 1;2;3;4 (0) (0) (0) (0) (0) 6 j =1 j =1 j =1 j =1 Vì đối với mỗi phần tử của cột ta đều thực hiện ∑ những phép tính giống như đối với những phần tử của những cột bên trái cột và nằm trong cùng một hàng với phần tử∑ a cột nên nếu không có sai số tính toán thì những ∑ củ phần tử của cột phải bằng tổng những phần tử tương ứng của những cột bên trái cột . Hiện tượng này được dùng để∑ểm tra quá trình thuận. Quá trình ngược được ki kiểm tra bằng hệ thức (3.17). Sơ đồ Gaoxơ
Nếu khi tính toán có sai số làm tròn thì bắt đầu từng hàng thứ 5 trở đi (trong sơ đố Gaoxơ) phần từ ờ cột∑ và tổng những phần tử cùng hàng và ở bên trái và bên trái được phép lệch nhau trong phạm vi giới hạn của sai số làm tròn đã phạm phải. một sự chênh lệch lớn chứng tỏ đã có sự nhầm lẫn trong quá trình tính toán Nhận xét: Sơ đồ Gaoxơ nêu trên hoàn toàn có thể mở rộng cho hệ thông n phương trình n ẩn số. Nếu ma trận hệ số A của hệ thống phương trình xuất phát đối xứng, nghĩa là aij = a ji thì căn cứ vào các công thức (3.6), (3.8) và (3.9) dễ thấy rằng a ij = a (1) , a ij = a (2) (1) (2) ji ji
Nghĩa là những ma trận trung gian:  a22 a23 a24  (1) (1) (1) ÷ (2)  a33 a34  (2) (1)  (1) A(1) =  a32 a33 a34 ÷, A =  (1) (1) (1) (1) ÷ a43 a44    a42 a43 a44 ÷ (1) (1) (1)   Cũng đối xứng. Do đặc điểm này, trong sơ đồ Gaoxơ, ta chỉ cần tính a ij , a ij ( j ≥ i ) vì vậy khối lượng tính toán sẽ giảm (1) (2) đi gân một nửa.
2.4. Khối lượng tính Xét hệ thống n phương trình n ẩn số. Căn cứ vào những công thức tính của pp Gaoxơ, ta đếm được số các phép tính cộng, trừ, nhân và chia S n cần phải thực hiện gồm (không ∑ kể các phép tính đối với các phần tử của cột kiểm tra ): n(n − 1)(2n + 5) phép nhân 6 n(n + 1) phép chia 2 n(n − 1)(2n + 5) phép cộng hoặc trừ 6 4n 3 + 9n 2 − 7 n phép tính. Sn = 6
Nếu ma trận hệ số của hệ thống phương trình đối xứng thì số các phép tính cộng, trừ, nhân và chia cần phải Sn thực hiện gồm : n(n − 1)(n + 1) phép nhân 6 n(n + 1) phép chia 2 n(n − 1)(n + 1) phép cộng hoặc trừ 6 2n3 + 3n 2 + n phép tính. Sn = 6 giảm hơn một nửa so với trường hợp ma trận hệ số A không đối xứng.