Giải phương trình tuyến tính bằng định thức
|
MỤC LỤCMỤC LỤC 1CHƯƠNG 1: MA TRẬN–ĐỊNH THỨC VÀ HỆ PHƯƠNG TRÌNH TUYẾN TÍNH 21.1.MA TRẬN-ĐỊNH THỨC 21.1.1.MA TRẬN 21.1.2.ĐỊNH THỨC 31.2.HỆ PHƯƠNG TRÌNH ĐẠI SỐ TUYẾN TÍNH 71.2.1.DẠNG TỔNG QUÁT CỦA HỆ PHƯƠNG TRÌNH TUYẾN TÍNH 71.2.2.GIẢI HỆ PHƯƠNG TRÌNH ĐẠI SỐ TUYẾN TÍNH 101.2.3.PHƯƠNG PHÁP GIẢI HỆ PHƯƠNG TRÌNH ĐẠI SỐ TUYẾN TÍNH 14CHƯƠNG 2 : THUẬT TOÁN-GIẢI THUẬT 192.1 ĐỊNH THỨC MA TRẬN 192.1.1 THUẬT TOÁN 192.1.2 GIẢI THUẬT 202.2 HỆ PHƯƠNG TRÌNH ĐẠI SỐ TUYẾN TÍNH 212.2.1 THUẬT TOÁN CRAMER 212.2.2 GIẢI THUẬT 21CHƯƠNG 3: CHƯƠNG TRÌNH 233.1. TÍNH ĐỊNH THỨC VÀ GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH 233.2HÌNH ẢNH 32ĐỒ ÁN KỸ THUẬT LẬP TRÌNHCHƯƠNG 1: MA TRẬN–ĐỊNH THỨC VÀ HỆ PHƯƠNG TRÌNH TUYẾN TÍNH1.1. MA TRẬN-ĐỊNH THỨC1.1.1. MA TRẬNa. Định nghĩa Một bảng số chữ nhật có m hàng, n cột gọi là ma trận cỡ m x n, ký hiệu là : A = [aij]mxn hay A = (aij)mxn trong đó: aij là phần tử của ma trận A nằm ở giao điểm của hàng i và cột j.Ví dụ 1:Là ma trận 3x2Chú ý: Khi m=n thì ta gọi ma trân A là ma trận vuông cấp n (gọi tắt là ma trận cấp n). A11, a22, ,amn được gọi là các phần tử chéo. Đường thẳng đi qua các phần tử chéo được gọi là đường chéo chính. Ma trận tam giác trên: là ma trận vuông cấp n mà tất cả các phần tử nằm dưới đường chéo chính đều bằng 0, tức là aij = 0 nếu i > j. Ma trận tam giác dưới: là ma trận vuông cấp n mà tất cả các phần tử nằm ở trên đường chéo chính đều bằng 0, , tức là aij = 0 nếu i < j. 2ĐỒ ÁN KỸ THUẬT LẬP TRÌNH Ma trận chéo: là ma trận vuông cấp n mà tất cả các phần tử nằm ngoài đường chéo đều bằng 0, tức là aij = 0 nếu i ≠ j. Ma trận đơn vị: là ma trận chéo mà tất cả các phần tử nằm trên đường chéo chính đều bằng 1 và ký hiệu là I. Ma trận không: là ma trận mà tất cả các phần tử của nó đều bằng không. Ma trận không ký hiệu là O. Hai ma trận bằng nhau: Hai ma trận A và B được gọi là bằng nhau, ký hiệu A = B , nếu chúng cùng cỡ và các phần tử có cùng vị trí bằng nhau, tức là:A= B b. Các phép toán về ma trận. Phép cộng hai ma trận cùng cỡ. Phép nhân ma trận với một số. Phép nhân ma trận với ma trận. Ma trận chuyển vị.1.1.2. ĐỊNH THỨCXét ma trận vuông cấp n:A= 3ĐỒ ÁN KỸ THUẬT LẬP TRÌNHTừ ma trận A, bỏ đi hàng i và cột j ta thu được ma trận vuông cấp n-1. Ta ký hiệu nó là Mij và gọi nó là ma trận con tương ứng với phần tử aij.a. Định nghĩaĐịnh thức của ma trận A, ký hiệu là det(A) và được định nghĩa dần như sau: A là ma trận cấp 1: A = [a11 ] thì det(A) = a11|a11| = a11, gọi là định thức cấp 1.A là ma trận cấp A= Thì det(A)= là một số được định nghĩa như sau: Det(A)= = a11a22 – a12a21 Các số a11 , a12 , a21 , a22gọi là các phần tử của định thức Chú ý: Định thức cấp 2 bằng tích đường chéo chính trừ đi tích đường chéo phụ. Để ký hiệu định thức, người ta dùng 2 gạch đứng đặt ở 2 bên.Ví d :ụ b. Các tính chất của định thứcTính chất 1: Định thức của ma trận chuyển vị At bằng định thức của ma trận A, tức là : det(At) = det(A). 4ĐỒ ÁN KỸ THUẬT LẬP TRÌNHTính chất 2: Đổi chỗ 2 hàng( hay 2 cột ) của một định thức, ta được một định thức mới bằng định thức cũ đổi dấu.Tính chất 3: Một định thức có 2 hàng (hay 2 cột ) như nhau thì bằng 0.Tính chất 4:• Tính det(A) bằng cách khai triển theo hàng thứ i.Det(A) = (-1)i+1ai1.det(Mi1) +(-1)i+2ai2.det(Mi2) + + (-1)i+nain.det(Min)• Tính det(A) bằng cách khai triển theo cột thứ j.Det(A) = (-1)1+ja1j.det(M1j) +(-1)2+ja2j.det(M2j) + + (-1)n+janj.det(Mnj)Tính chất 5: Một định thức có một hàng( hay một cột) toàn là số không thì bằng không.Tính chất 6: Khi ta nhân các phần tử của một hàng( hay một cột) với cùng một số thực k thì ta được một định thức mới bằng định thức cũ nhân với k.Hệ quả: Khi các phần tử của một hàng (hay một cột) có một thức số chung, ta có thể đưa thừa số chung đó ra ngoài dấu ngoặc định thức.Tính chất 7: Một định thức có 2 hàng( hay 2 cột ) tỷ lệ thì bằng không.Tính chất 8: Khi tất cả các phần tử của một hàng (hay một cột ) có dạng tổng của 2 số hàng thì định thức đó có thể phân tích thành tổng của 2 định thức, chẳng hạn như: Tính chất 9: Một định thức có một hàng (hay một cột) là tổ hợp tuyến tính của các hàng khác(hay cột khác) thì định thức ấy bằng không. 5ĐỒ ÁN KỸ THUẬT LẬP TRÌNHTính chất 10: Khi ta cộng bội k của hàng khác ( hay bội k của cột này vào cột khác ) thì ta được một định thức mới bằng một định thức cũ. Tính chất 11: Định thức của ma trận tam giác trên bằng tích các phần tử chéo.c. Cách tính định thức bằng phép biến đổi sơ cấpTa sử dụng các tính chất của định thức để biến đổi một định thức về dạng đơn giản như: định thức ma trận tam giác trên, định thức ma trận tam giác dưới.Các phép biến đổi về hàng ma ta hay sử dụng đó là:- Nhân 1 hàng với một số thực k ≠0(tính chất 6).- Đổi chỗ 2 hàng(tính chất 2).- Cộng k lần hàng này vào hàng khác(tính chất 10).Ví dụ:Cho một ma trận cấp 4. Tính định thức bằng cách biến đổi ma trận về dạng ma trận tam giác trên. Lấy phần tử là p1=a11, ta chia các phần tử của hàng thứ nhất cho p1=a11 thì định thức sẽ là: D/p1(theo tính chất 6), và ma trận còn lại là:Lấy hàng 2 trừ đi hàng 1 đã nhân với a21, lấy hàng 3 trừ đi hàng 1 đã nhân với a31 và lấy hàng 4 trừ đi hàng 1 đã nhân với a41(thay hàng bằng tổ hợp tuyến tính của các hàng còn lại), thì định thức vẫn là D/p1 và ma trận là: 6ĐỒ ÁN KỸ THUẬT LẬP TRÌNHLấy giá tri trụ là p2= a’22. Ta chia các phần tử của hàng thứ 2 cho p2 thì định thức sẽ là: D/(p1p2) và mà phần còn lại là:Lấy hàng 1 trừ đi hàng 2 đã nhân với a’12, lấy hàng 3 trừ đi hàng 2 đã nhân với a’32, và lấy hàng 4 trừ đi hàng 2 đã nhân với a’42, ta có định thức vẫn là D/(p1p2) và ma trận còn lại là:Tiếp tục lấy hàng 3, hàng 4 làm trụ, ta thu được ma trận cuối cùng là:Định thức của ma trận này là: Nên định thức của ma trận A là: D/(p1p2p3p4)(phương pháp trên còn có thể mở rộng cho ma trận cấp n)1.2. HỆ PHƯƠNG TRÌNH ĐẠI SỐ TUYẾN TÍNH1.2.1. DẠNG TỔNG QUÁT CỦA HỆ PHƯƠNG TRÌNH TUYẾN TÍNHĐó là một hệ gồm m phương trình đại số bậc nhất đối với n ẩn: 7ĐỒ ÁN KỸ THUẬT LẬP TRÌNHTrong đó: x1, x2, ,xn là các ẩn số. aij là hệ số ở phương trình thứ i của ẩn thứ xj. bi là vế phải của phương trình thứ i.Chú ý:o Nếu m = n : Hệ (I) trở thành hệ vuông với n phương trình n ẩn.o Nếu bj =0, ∀ i thì hệ (I) gọi là hệ thuần nhất.Hệ này được viết dưới dạng ma trận là : A.x=b trong đó: A là ma trận được lập từ các hệ số: A= (aij) mxn A= b là vecto cột các số hạng tự do(hay gọi là ma trận vế phải): 8ĐỒ ÁN KỸ THUẬT LẬP TRÌNHb = = tx được gọi là ma trận ẩn(vecto cột các biến):x = = tHệ phương trình đại số tuyến tính được gọi là: thuần nhất nếu tất cả các bi =0, i =1, 2, , m.không thuần nhất nếu có ít nhất một bi ≠ 0.tương thích nếu hệ có ít nhất một nghiệm, tức là tồn tại một bộ giá trị của x1 , x 2 , , x n mà khi thay vào sẽ có một đồng nhất thức. không tương thích nếu không có một nghiệm nào. xác định nếu hệ chỉ có một nghiệm duy nhất. bất định nếu tồn tại quá một nghiệm.Muốn giải hệ phương trình đại số tuyến tính thì trước hết phải xác định xem hệ đã cho tương thích hay không tương thích. Nếu là hệ tương thích thì lại phải xem hệ là xác định hay bất định. Nếu hệ phương trình là xác định thì ta đi tìm nghiệm duy nhất của nó. 9ĐỒ ÁN KỸ THUẬT LẬP TRÌNHVí dụ: Hệ phương trình 2 ẩn: Hệ 3 phương trình 3 ẩn: Hệ 2 phương trình 3 ẩn: 1.2.2. GIẢI HỆ PHƯƠNG TRÌNH ĐẠI SỐ TUYẾN TÍNH Khi giải hệ phương trình đại số tuyến tính có thể xảy ra hai trường hợp: m = n và m ≠ n.a. Trường hợp m = nLúc này ma trận A có dạng: A= Định nghĩa: Hệ (I) gọi là hệ Cramer nếu det (A) ≠ 0 (ma trận A không suy biến). Khi đó sẽ tồn tại ma trận nghịch đảo A-1.Định lí (Cramer): Hệ Cramer có nghiệm duy nhất tính bằng công thức: 10ĐỒ ÁN KỸ THUẬT LẬP TRÌNH i=1,2, nChú ý: Từ định lý trên, ta có 2 phương pháp giải hệ phương trình như sau: Phương pháp 1: Phương pháp ma trân nghịch đảo:1. Xác địnhma trận hệ số A?2. Tính ma trận nghịch đảo A-1=?3. Tính ma trận ẩn bởi công thức: x= A-1.b từ đó suy ra nghiệm của phương trình. Phương pháp 2: Phương pháp Cramer:1. Tính det(A)=?, det(Aj)=?2. Tính nghiệm của hệ bởi công thức: xj=Ví dụ: Giải hệ pt sau: Giải : ta có: A= ; b = ; Det(A) =49 = ; det(A1) = 98; = det(A2) = 49 11ĐỒ ÁN KỸ THUẬT LẬP TRÌNH= det(A3) = 49Ta có nghiệm của hệ đã cho là: = = 2; = =1 ; = =1b. Trường hợp m ≠ nTa gọi: A= (aij )mx n là ma trận của hệ. Sau khi thêm cột các số hạng tự do b vào ma trận A, ta lập được ma trận mở rộng B:A=Để giải trường hợp này, ta dựa vào định lí sau:Định lí (Croneker – Capeli): Điều kiện cần và đủ để hệ có nghiệm là hạng của ma trận A bằng hạng của ma trận mở rộng B. Nếu r ( A) = r ( B)= n thì hệ có một nghiệm duy nhất. Nếu r (A ) = r ( B) < n thì hệ có vô số nghiệm.Vi dụ: Giải hệ phương trình sau: 12Trong đó: p là số lần hóan vị các dòng để tìm phần tử trụĐỒ ÁN KỸ THUẬT LẬP TRÌNHGiảiỞ đây m = 3, n = 4B= → → Ta có r ( A)= r ( B) = 3 < n = 4.Vậy hệ có vô số nghiệm.Với ma trận cuối cùng ta có:Đặt x 4 = c,ta được:→ Vậy các nghiệm có dạng:với mỗi giá trị của c ta có một nghiệm tương ứng. 13ĐỒ ÁN KỸ THUẬT LẬP TRÌNH1.2.3. PHƯƠNG PHÁP GIẢI HỆ PHƯƠNG TRÌNH ĐẠI SỐ TUYẾN TÍNH.a. Giải hệ phương trình bằng phương pháp ma trận nghịch đảo1. Xác địnhma trận hệ số A?2. Tính ma trận nghịch đảo A-1=?3. Tính ma trận ẩn bởi công thức: x= A-1.b Từ đó suy ra nghiệm của phương trình.b. Giải hệ phương trình tuyến tính bằng phương pháp Cramer Tính det(A) = ? Tính det(Aj) = ? Tính nghiệm của hệ bởi công thức xj = det(Aj) / det(A)Ví dụ: Giải: Ta có: A = ; b = ; Det(A)= 5= det(A1) = 5 14ĐỒ ÁN KỸ THUẬT LẬP TRÌNH = det(A2) = 10= det(A3) = -1Vậy = = =1 ; = = = 2 ; = = = -2c. Giải hệ phương trình tuyến tính bằng biến đổi sơ cấp ( pp khử Gauss)Xét hệ phương trình: (II)Ta lập ma trận mở rông bằng cách từ ma trận A, ta thêm vào vế phải của ma trận A bởi cột vế phải (ma trận vế phải b) ,tức là: 15ĐỒ ÁN KỸ THUẬT LẬP TRÌNH= [A|b]= Phương pháp khử Gauss: ta sử dụng các phép biến đổi sơ cấp về, đó là: Đổi chỗ 2 hàng (đổi vị trí 2 phương trình cho nhau). Nhân, chia các phần tử của một hàng với số thực k ≠ 0 (nhân, chia 2 vế của phương trình với số thực k ≠ 0 ). Cộng bội k hàng này vào hàng khác ( công bội k phương trình này vào phương trình khác ) để biến đổi ma trận mở rộng sao cho ma trận A có trong ma trận về dạng của ma trận tam giác trên. Sau đó viết lại hệ phương trình đã cho ứng với ma trận mở rộng sau khi đã biến đổi, rồi giải hệ phương trình bằng cách giải ngược từ dưới lên.Ví dụ: Giải: Quá trình thuậnBước 1: - Giả sử a11 ≠ 0, chia dòng 1 cho a11. (a11 là phần tử trụ). Hệ đã cho tương đương với: 16−=+−=+−=−+1232232321321321xxxxxxxxx=nnnnnnnnnnbbbbxxxxaaaaaaaaaaaaaaa . 132)1(132132133332312232221)1(1)1(13)1(12−=+−=+−=−+12322232121321321321xxxxxxxxxĐỒ ÁN KỸ THUẬT LẬP TRÌNHVới Khử x1 trong phương trình thứ i=2,3,4,…, n bằng cách:Thay dòng i bởi dòng i – dòng 1 * ai1 . Nghĩa là: a(1)ij = aij - a(1)1j *ai1 với j=1,n và: b(1)i=bi - b(1)1*ai1Hệ đã cho tương đương với:Bước 2: Giả sử a(1)22≠0, chia dòng 2 cho a(1)22. Hệ đã cho tương đượng với: 17=)1()1(3)1(2)1(1321)1()1(3)1(2)1(3)1(33)1(32)1(2)1(23)1(22)1(1)1(13)1(12 . 0 0 0 1nnnnnnnnnbbbbxxxxaaaaaaaaaaaa−=+−=+−=−+2112527 212523 2321213232321xxxxxxx=)1()1(3)2(2)1(1321)1()1(3)1(2)1(3)1(33)1(32)2(2)2(23)1(1)1(13)1(12 . 0 0 10 1nnnnnnnnnbbbbxxxxaaaaaaaaaaa−=+−−=−=−+2112527 3135 2321213232321xxxxxxx111)1(1111)1(1/ ,/ abbaaajj==), ,2,1(,/ ,/)1(22)1(2)2(2)1(22)1(2)2(2njabbaaajj===ĐỒ ÁN KỸ THUẬT LẬP TRÌNHVới Khử x2 ở phương trình thứ i=3,4,5,…,n bằng cách:Dòng i = dòng i – dòng 2 * ai2(1)Nghĩa là: a(2)ij = a(1)ij-a(2)2j *ai2 , với j=1,2,…,nvà: b(2)i=b(1)i - b(2)2*ai2Hệ đã cho tương đương với:Tiếp tục thực hiện như trên cho đến khi đưa được ma trận hệ số về ma trận tam giác trên. Hệ đã cho tương đương với:Quá trình nghịch: 18=)()3(3)2(2)1(1321)3(3)2(2)2(23)1(1)1(13)1(12 .1 000 100 10 1nnnnnnbbbbxxxxaaaaaa=−=−=−+2 3135 232121332321xxxxxx=−=−=−+2 3135 232121332321xxxxxx=)2()2(3)2(2)1(1321)2()2(3)2(3)2(33)2(2)2(23)1(1)1(13)1(12 . 00 00 10 1nnnnnnnnbbbbxxxxaaaaaaaaa−=−=−=−+320310- 3135 232121332321xxxxxxĐỒ ÁN KỸ THUẬT LẬP TRÌNHTừ phương trình thứ 3, ta có: x3 = 2Từ phương trình thứ 2, ta có: x2 =-1/3+5/3x3 = 3Từ phương trình thứ 1, ta có: x1 =3/2-1/2x2+1/2x3 = 1Vậy nghiệm của hệ là: x1 = 1; x2 = 3; x3 = 2CHƯƠNG 2 : THUẬT TOÁN-GIẢI THUẬT2.1 ĐỊNH THỨC MA TRẬN2.1.1 THUẬT TOÁNCó rất nhiều phương pháp khác nhau để tính định thức trong ma trận như gauss,cramer,choleski,…trong đó phương pháp giải đưa ma trận về dạng ma trận tam giác trên được xem là phương pháp giải chính xác và khối lượng các phép tính ít nhất. Biến đổi ma trận A về ma trận tam giác trên có dạng:Gọi a(k)kk là phần tử trụ được chọn trong bước thứ k. Ta có: 19=1 0 a a 1 0a a a 1(n)2n(n)23(n)1n(n)13(n)12)(nA∏=−=nkkkkpaA1)(.)1()det(ĐỒ ÁN KỸ THUẬT LẬP TRÌNHTrong đó: p là số lần hoán vị các dòng để tìm phần tử trụ2.1.2 GIẢI THUẬTdetA = 1;Cho k=1,2,3,…, n. Với mỗi dòng k Chọn t sao cho . Nếu atk=0 thì det(A)=0; dừng thuật toán. Nếu atk ≠ 0 thì làm các việc sau đây: Nếu t≠k thì đổi chỗ dòng k với dòng t và detA = detA*(-1) ; Chọn trụ là akk. Chia dòng k cho akk. Khử aik ở các dòng i (i=k+1, k+2,…) bằng cách: Tính: hệ số = aik. Dòng i = dòng i – dòng k * hệ số. Giá trị định thức det(A)=det(A)*akk. 20ĐỒ ÁN KỸ THUẬT LẬP TRÌNH2.2 HỆ PHƯƠNG TRÌNH ĐẠI SỐ TUYẾN TÍNH2.2.1 THUẬT TOÁN CRAMERXét hệ gồm n phương trình n ẩn:(I)A.x=bMa trận Aj là ma trận được thành lập từ ma trận A bằng cách từ ma trận A bỏ đi cột thứ j và thay vào đó cột vế phải.Lần lượt tính định thứ của các ma trận thay thế rồi tìm nghiệm theo công thức Cramer là xj = 2.2.2 GIẢI THUẬTdetA = 1; Với mỗi dòng ko Chọn t sao choo Nếu atk=0 thì det(A)=0; dừng thuật toán.o Nếu atk ≠ 0 thì làm các việc sau đây: 21ĐỒ ÁN KỸ THUẬT LẬP TRÌNH-Thay b vào từng cột của ma trân A để tính các định thức-Cho k=1,2,3,…, n-Với mỗi dòng k nếu hàng i=k thì thay r[j][i]=b[j]-Ngược lại r[j][i] = a[j][i] Nếu t≠k thì Đổi chỗ dòng k với dòng t và detA = detA*(-1) ; Chọn trụ là akk Chia dòng k cho akk; Khử aik ở các dòng i (i=k+1, k+2,…) bằng cách:Tính: hệ số = aikDòng i = dòng i – dòng k * hệ số Giá trị định thức det(Ak)=det(Ak)*akk Nghiệm của hệ là x[i]= det(Ak)/det(A) 22ĐỒ ÁN KỸ THUẬT LẬP TRÌNHCHƯƠNG 3: CHƯƠNG TRÌNH3.1. TÍNH ĐỊNH THỨC VÀ GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH#include |
