Giải hệ phương trình Ax B bằng phương pháp khử Gauss với phép tính lấy đến 3 chữ số thập phân

ĐẠI HỌC THÁI NGUYÊNTRƯỜNG ĐẠI HỌC KHOA HỌC- - - - - - - - - - - - - - - - - -Trần Thị Hương LiênPHƯƠNG PHÁP KHỬ GAUSSGIẢI HỆ PHƯƠNG TRÌNHĐẠI SỐ TUYẾN TÍNHLUẬN VĂN THẠC SỸ TOÁN HỌCChuyên ngành: TOÁN ỨNG DỤNGMã số: 60 46 01 12Người hướng dẫn khoa họcPGS. TS. TẠ DUY PHƯỢNGTHÁI NGUYÊN - NĂM 2014Mục lụcMở đầu 31 Các phương pháp giải hệ phương trình đại số tuyến tính 51.1 Các phương pháp khử . . . . . . . . . . . . . . . . . . . . . . 51.1.1 Phương pháp khử Gauss . . . . . . . . . . . . . . . . 61.1.2 Phương pháp phần tử trội toàn phần . . . . . . . . . 91.1.3 Phương pháp khử Gauss - Jordan . . . . . . . . . . . 101.2 Phương pháp phân rã LU . . . . . . . . . . . . . . . . . . . . 111.3 Phương pháp Cholesky . . . . . . . . . . . . . . . . . . . . . 141.4 Phương pháp phân rã QR . . . . . . . . . . . . . . . . . . . . 161.5 Phương pháp lặp đơn . . . . . . . . . . . . . . . . . . . . . . 181.6 Phương pháp lặp theo Seidel . . . . . . . . . . . . . . . . . . 211.7 Phương pháp lặp theo Jacobi và phương pháp lặp theo Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 Tổng quan về phương pháp khử Gauss giải hệ phương trìnhđại số tuyến tính 262.1 Sơ lược về các thuật toán song song giải hệ phương trình đạisố tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.1.1 Sơ lược về các phần mềm giải phương trình đại số tuyếntính trên máy tính song song . . . . . . . . . . . . . . 262.1.2 Giải hệ tam giác trên máy tính với bộ nhớ phân tán . 282.2 Các phương pháp giải hệ phương trình có ma trận hệ số thưa 292.2.1 Hệ ba đường chéo. Phương pháp Thomas . . . . . . . 302.2.2 Hệ ma trận băng. Phương pháp Thomas cải biên . . . 323 Sử dụng máy tính điện tử khoa học và phần mềm Mapletrong đại số tuyến tính 3313.1 Sử dụng máy tính điện tử khoa học trong giải hệ phương trìnhtuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.1.1 Tính toán ma trận trên CASIO fx-570VN PLUS . . . 333.1.2 Giải hệ phương trình bậc nhất hai ẩn trên CASIO fx-570VN PLUS . . . . . . . . . . . . . . . . . . . . . . 363.1.3 Hệ ba phương trình bậc nhất ba ẩn trên CASIO fx-570VN PLUS . . . . . . . . . . . . . . . . . . . . . . 383.1.4 Hệ bốn phương trình bậc nhất bốn ẩn trên CASIOfx-570VN PLUS . . . . . . . . . . . . . . . . . . . . . 393.1.5 Tính toán trên ma trận trên Vinacal 570 ES Plus . . . 403.1.6 Giải hệ phương trình bậc nhất bốn ẩn trên Vinacal 570ES Plus . . . . . . . . . . . . . . . . . . . . . . . . . 433.2 Sử dụng phần mềm Maple trong giải hệ phương trình tuyếntính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . 512Mở đầuPhương pháp khử Gauss giải hệ phương trình đại số tuyến tính đã đượcbiết đến từ lâu. Tuy nhiên, do nhu cầu của thực tiễn, nhiều bài toán của thựctế hoặc của chính toán học (sai phân hóa và giải số phương trình vi phân, ),phương pháp khử Gauss nói riêng, phương pháp giải hệ phương trình đại sốtuyến tính nói chung, vẫn được quan tâm nghiên cứu, đặc biệt vào nhữngnăm gần đây với việc sử dụng những thành tựu mới của công nghệ thôngtin (máy tính tốc độ cao, máy tinh song song, ). Luận văn " Phương phápkhử Gauss giải hệ phương trình đại số tuyến tính" có mục đích trình bày cácphương pháp giải hệ phương trình đại số tuyến tính, trong đó đặc biệt chútrọng trình bày phương pháp khử Gauss. Ngoài ra, nhằm phục vụ cho giảngdạy đại số tuyến tính trong trường phổ thông, Luận văn cũng đề cập đếncách giải phương trình đại số tuyến tính trên máy tính điện tử khoa học vàsử dụng phần mềm Maple. Luận văn bao gồm phần mở đầu, ba chương, kếtluận và danh mục tài liệu tham khảo.Chương 1 Các phương pháp giải hệ phương trình đại số tuyếntínhCác phương pháp giải hệ phương trình đại số tuyến tính trong chương nàyđược phân thành hai nhóm chính: nhóm các phương pháp trực tiếp và nhómcác phương pháp lặp. Các phương pháp trực tiếp thường sử dụng cho hệphương trình đại số tuyến tính cỡ không lớn, số phép toán có thể dự đoántrước được, ma trận hệ số thường không suy biến. Còn phương pháp lặpthường được sử dụng cho hệ có kích thước lớn hoặc hệ gần suy biến hoặcthỏa mãn điều kiện xấu. Mỗi một phương pháp được nêu trong chương thườngkèm theo ví dụ minh họa.3Chương 2 Tổng quan về phương pháp khử Gauss giải hệ phươngtrình đại số tuyến tínhChương này trình bày tổng quan theo [6] các phương pháp giải hệ phươngtrình tuyến tính trong những năm gần đây: Sơ lược giới thiệu một số phầnmềm giải hệ phương trình đại số tuyến tính trên máy tính song song; Giải hệphương trình đại số tuyến tính có dạng đặc biệt: hệ có ma trận hệ số thưa,ma trận chéo khối, Chương 3 Sử dụng máy tính khoa học và phần mềm Maple trongđại số tuyến tínhChương này giới thiệu sơ lược cách sử dụng các máy tính khoa học (CASIOfx-570VN Plus, Vinacal 570 ES Plus) và phần mềm Maple trong đại số tuyếntính, chủ yếu đi sâu vào cách giải hệ phương trình đại số tuyến tính.Luận văn được hoàn thành dưới sự hướng dẫn và chỉ bảo tận tình củaPGS.TS. Tạ Duy Phượng- Viện Toán học, Viện khoa học và Công nghệ ViệtNam. Từ đáy lòng em xin bày tỏ lòng biết ơn sâu sắc đối với sự quan tâm,động viên và chỉ dạy, hướng dẫn tận tình đầy tâm huyết của Thầy.Tôi xin chân thành cảm ơn các Thầy, các Cô giảng viên Trường Đại họcKhoa học, phòng đào tạo Trường Đại học Khoa học, khoa Toán-Tin TrườngĐại học Khoa học-Đại học Thái Nguyên. Đồng thời tôi xin gửi lời cảm ơntới gia đình, bạn bè, tập thể lớp cao học toán K6D Trường Đại học Khoahọc-Đại học Thái Nguyên đã luôn quan tâm, động viên giúp đỡ tôi trong quátrình học tập và làm luận văn này.4Chương 1Các phương pháp giải hệ phươngtrình đại số tuyến tính1.1 Các phương pháp khử.Xét hệ phương trình đại số dạng tổng quáta11x1+ a12x2+ + a1nxn= b1,a21x1+ a22x2+ + a2nxn= b2, an1x1+ an2x2+ + annxn= bn,(1.1)hoặc ở dạng ma trậnAx = b, (1.2)trong đóA =a11a12 a1na21a22 a2n an1an2 annđược gọi là ma trận hệ số của phương trình đại số tuyến tính (1.1),x =x1x2 xnlà véctơ ẩn cần tìm,b =b1b2 bn5là véctơ hệ số tự do.Ma trậnA1= (A|b) =a11a12 a1nb1a21a22 a2nb2 an1an2 annbnđược gọi là ma trận suy rộng của hệ phương trình đại số tuyến tính (1.1).1.1.1 Phương pháp khử Gauss.Phương pháp khử Gauss là bằng phương pháp thế hoặc cộng đại số khử dầncác ẩn để đưa hệ phương trình đã cho về dạng tam giác rồi giải hệ tam giácnày từ dưới lên trên hoặc từ trên xuống để tìm nghiệm (x1, , xn) của hệphương trình đã cho. Cơ sở thuật toán của phương pháp khử Gauss như sauSử dụng phép biến đổi tương đương trên ma trận A1để đưa ma trận Avề dạng tam giác trên. Tức là:(1.1) ⇔a11x1+a12x2+ +a1nxn= b1,a22x2+ +a2nxn= b2, annxn= bn.(1.3)Từ hệ phương trình trên ta đi ngược từ dưới lên để tìm nghiệm:xn, xn−1, xn−2, , x1Ta mô tả gắn gọn phương pháp khử Gauss như sauPhần thuận:Không làm mất tính tổng quát, giả sử các a(k)ii= 0 (k =1, n − 1). Ngayở bước khử đầu tiên, ta nhân dòng thứ nhất với đại lượng−a21/a11rồi cộngvào dòng thứ hai sẽ khử được biến x1ở phương trình thứ hai. Sau nhiều nhấtn −1 phép biến đổi ta đưa phần tử ở cột một từ vị trí thứ hai đổ xuống củama trận A1về giá trị không. Ở bước hai, bằng cách làm tương tự. Qua nhiềunhất n − 2 phép biến đổi ta đưa phần tử ở cột hai tính từ vị trí thứ ba đổ6xuống của ma trận biến đổi (lần hai) về giá trị không, tức là loại bỏ biến x2ra khỏi phương trình từ phương trình thứ ba đến phương trình thứ n.Quy trình đó, về nguyên tắc dừng ở bước khử biến thứ n−1 trong phươngtrình thứ n tương ứng với ma trận biến đổi là cột thứ n −1 về giá trị khôngở vị trí thứ n, để nhận được phương trình có ma trận hệ số là ma trận tamgiác trên. Trong quá trình biến đổi ta cũng biến đổi cùng một lúc vế phảicủa hệ phương trình (tức là véctơ b), ta được hệ phương trình có dạng (1.3).Phần nghịch: Từ hệ phương trình tuyến tính (1.3) ta đi tính ngiệmxn, , x1của hệ phương trình đã cho theo công thức:xn=bnann, xk=bk−nj=k+1akjxjakk, k = 1, n −1.Ví dụ 1.1 Giải hệ phương trình đại số tuyến tính sau bằng phương phápkhử Gauss:x1+2x2+5x3= −9,x1−x2+3x3= 2,3x1−6x2−x3= 25.GiảiViết ma trận suy rộng và thực hiện phép biến đổi như trên, ta có:1 2 5 −91 −1 3 23 −6 −1 25⇒1 2 5 −90 −3 −2 110 −12 −16 52⇒1 2 5 −90 −3 −2 110 0 −8 8Khi đó ta có hệ phương trình:x1+2x2−5x3= −9−3x2−2x3= 11−8x3= 8Quy trình thế ngược trở lại ta được nghiệm của hệ phương trình là :x3= −1, x2= −3, x1= 2.7Phương pháp trên có hai yếu điểm. Một là, ở bước khử nào đó mà phần tửtrên đường chéo bằng không thì biến đổi dừng lại. Hai là, các phần tử trênđường chéo khác không nhưng có giá trị tuyệt đối nhỏ hơn các phần tử kháccùng cột khi chia sẽ làm tăng sai số, do đó khuyếch đại sai số là làm tròn sốdẫn đến lời giải bài toán bị sai số lớn.Có thể khắc phục hai nhược điểm này bằng phương pháp như sau. Ở bướckhử đầu tiên ta chọn phần tử lớn nhất trên cột một, nếu phần tử đó nằm ởdòng k (k = 1) ta đổi vị trí dòng đó cho dòng một rồi thực hiện phép biếnđổi như trong phương pháp Gauss. Bước thứ hai, ta cũng chọn phần tử cógiá trị tuyệt đối lớn nhất trên cột hai, thực hiện đổi dòng nếu cần thiết, vàthực hiện phép khử từ vị trí thứ ba trở xuống. Tất cả các bước khử đều thựchiện với modul lớn nhất trên cột tương ứng trước khi tiến hành phép khử.Tức là, ở bước khử x1ta chọn hàng r sao cho:|ar1| = max {|ak1|, k = 1, , n}.Sau đó đổi hàng r cho hàng 1 và tiếp tục các bước khử như đã nêu ở trên.Tương tự trong các bước khử x2, x3, , xn−1ta cũng tìm phần tử có modullớn nhất trên từng cột tương ứng|ari| = max {|aki|, k = i, i + 1, , n} (i = 2, 3, , n −1) .Phương pháp khử kết hợp với phép chọn như vậy làm cho thuật toán ổnđịnh và luôn thực hiện trên ma trận suy rộng, không làm thay đổi thứ tựcủa các ẩn số.Ví dụ 1.2 Giải hệ phương trình sau bằng phương pháp khử Gauss:2x1+3x2+x3= 11,−x1+2x2−x3= 0,3x1+2x3= 9.Giải. Xét ma trận suy rộng của hệ phương trình trên ta có:A1=2 3 1 11−1 2 −1 03 0 2 9.Trên cột một của ma trận A1ta thấy max {|ak1|/k = 1, 2, 3} = a31= 3, đổidòng ba cho dòng một, rồi nhân lần lượt dòng một vừa biến đổi với phần tử81/3 rồi cộng với dòng hai và nhân với phần tử (−2/3) rồi cộng với dòng bata được:A1=3 0 2 9−1 2 −1 02 3 1 11⇒ A1=3 0 2 90 2 −1/3 30 3 −1/3 5.Ở bước khử thứ hai ta có max {|ak2|/k = 2, 3} = a32= 3. Thực hiệnphép đổi vị trí dòng hai cho dòng ba, rồi nhân dòng vừa hoán đổi cho phầntử (−2/3) sau đó cộng với dòng ba ta được:A1=3 0 2 90 3 −1/3 50 2 −1/3 3⇒ A1=3 0 2 90 3 −1/3 30 0 −1/9 −1/3Khi đó hệ phương trình đã cho có dạng:3x1+2x3= 93x2−13x3= 5−19x3= −13Quy trình thế ngược trở lại ta nhận được nghiệm của hệ phương trình đãcho là:x3= 3, x2= 2, x1= 1.1.1.2 Phương pháp phần tử trội toàn phầnNgay từ bước khử đầu tiên, ta chọn phần tử có giá trị tuyệt đối lớn nhấttrong số các phần tử aij(1 ≤ i, j ≤ n) của ma trân. Giả sử phần tử đó là apq(dòng thứ p và cột thứ q). Ta gọi dòng p là dòng trội, lần lượt nhân dòngnày với thừa số−alp/apq(l = p) rồi cộng dòng thứ l. Bằng cách này loại bỏẩn xpra khỏi hệ phương trình, trừ phương trình thứ p. Sau đó loại hàng trộivà cột q ra khỏi hệ phương trình vừa biến đổi, ta thu được hệ gồm n − 1phương trình. Tiếp tục thực hiện bước khử thứ hai như bước ban đầu thuđược hệ gồm n − 2 phương trình. Cứ như vậy sau n − 1 lần thực hiện phépkhử như trên ta nhận được phương trình một ẩn.Giai đoạn tiếp theo, ta tính nghiệm từ phương trình cuối cùng, rồi đếnphương trình hai ẩn ở hàng trội bị bỏ sau bước khử thứ n−1, rồi đến phương9trình ba ẩn là hàng trội bị bỏ sau bước khử thứ n − 2, cho đến phươngtrình đủ n là dòng trội đầu tiên bị bỏ sau bước khử lần thứ nhất. Đặc trưngcủa phương pháp này là các ẩn được tính từ giai đoạn hai không theo thứ tựtừ xnđến x1mà xuất hiện nhiều lần thay đổi các ẩn. Trong quá trình khử,vế phải của hệ cũng được thực hiện biến đổi đồng thời.1.1.3 Phương pháp khử Gauss - JordanCơ sở của phương pháp này như sau: Từ ma trận suy rộng A1, dùng phépbiến đổi tương đương đưa ma trận hệ số của hệ phương trình về ma trận đơnvị E, và vế phải của hệ cũng được biến đổi đồng thời.A1⇔1 0 0b10 1 0 b2 0 0 1 bnKhi đó nghiệm của hệ phương trình (1.1) là x = (b1, b2, , bn)TĐể biến đổi ma trận về dạng tương đương ta dùng phép biến đổi như môtả trong phương pháp Gauss, có thể kết hợp với phương pháp chọn như trênhoặc phương pháp phần tử trội như đã mô tả (nếu cần thiết). Ở đây khôngcần phần nghịch để tìm nghiệm của hệ phương trình như trong phương phápGauss nhưng phép khử lại nhiều hơn.Phương pháp này không những giải hệ phương trình tuyến tính (1.1) màcòn dùng để tìm ma trận nghịch đảo của ma trận không suy biến bất kì.Tacó sơ đồ để giải hệ phương trình (1.2) và tìm ma trận nghịch đảo như sau:(A|b|E) →E|x|A−1Ví dụ 1.4 Giải hệ phương trình sau bằng phương pháp Gauss-Jordan và matrận nghịch đảo của ma trận hệ số:2x1+3x2+x3= 11−x1+2x2−x3= 03x1+2x3= 910Giải.Sử dụng biến đổi như trong ví dụ 1.2 và kết hợp ma trận đơn vị E biếnđổi (A|b|E) như sau:2 3 1 11 1 0 0−1 2 −1 0 0 1 03 0 2 9 0 0 0⇒3 0 2 9 0 0 1−1 2 −1 0 0 1 02 3 1 11 1 0 0⇒3 0 2 9 0 0 10 2133 0 1130 3 −135 1 0 −23⇒3 0 2 9 0 0 10 3 −135 1 0 −230 2 −133 0 113⇒3 0 2 9 0 0 10 3 −135 1 0 −230 0 −19−13−23179⇒3 0 2 9 0 0 10 3 −135 1 0 −230 0 1 3 6 −9 −7⇒3 0 0 3 12 18 150 3 0 6 3 −3 −30 0 1 3 6 −9 −7⇒1 0 2 1 −4 6 50 1 0 2 1 −1 −10 0 1 3 6 −9 −7Vậy nghiệm của hệ phương trình là: x = (1, 2, 3)Tvà ma trận nghịch đảotìm được là:A−1=−4 6 51 −1 −16 −9 −7.1.2 Phương pháp phân rã LUNhư chúng ta đã biết, nếu hệ phương trình (1.2) có dạng tam giác thì rấtdễ giải. Nếu ma trận vuông A cấp n có tính chất: tất cả các định thức contừ cấp một đến đến cấp n trên đường chéo chính đều khác không thì ta cóthể phân tích ma trận A thành tích hai ma trận:A = L.U, (1.4)11trong đó L là ma trận tam giác dưới, U là ma trận tam giác trên có dạngtổng quát như sau:L =1 0 0 0α211 0 0α31α321 0 αn1αn2αn3 1; U =β11β12β13 β1n0 β22β23 β2n0 0 β33 β3n 0 0 0 βnn. (1.5)Nếu ta chọn βii= 1i = 1, nthì ta có công thức tương ứng với αiii = 1, nchưa xác định. Ở đây để tiện trình bày ta chỉ sử dụng công thức (1.5). Sửdụng công thức nhân hai ma trận ta có thể xác định αij(i > j) và βij(i ≤ j)như sau:∀j = 1, n :βij= aij−i−1k=1αikβkj(1 ≤ i ≤ j)(1.6a)αij=1βjjaij−j−1k=1αikβkj(1.6b)Khi đó hệ (1.2) viết được dưới dạng:LUx = b.Kí hiệu:Ly = x. (1.7a)Ta nhận được hệ phương trình tương với (1.2) dạng:Ux = y ((1.7b)Việc tìm nghiệm (1.1) tương ứng việc tìm nghiệm (1.7b) trước rồi tính nghiệm(1.7a) sau. Việc tính nghiệm có thể viết dưới dạng sau:y1=b1/α11, yi=1αiibi−i−1k=1αikyk(1.8)xn=yn/βnn, xi=1βiiyi−i−1k=1βikyk(1.9)12Ví dụ 1.5 Giải hệ phương trình đại số tuyến tính sau :2x1+3x2+x3= 11−x1+2x2−x3= 03x1+2x3= 9bằng phương pháp phân rã LU.Giải Xét ma trận hệ số của hệ phương trìnhA =2 3 1−1 2 −13 0 2Vì A là ma trận vuông cấp 3 nên ta có thể phân tích ma trận thành tích haima trận có dạng A = LU, trong đó:L =1 0 0α211 0α31α321, U =β11β12β130 β22β230 0 β33Ta đi tính các hệ số αij(i > j) và βij(i ≤ j)Với j = 1 theo (1.6a) ta tính được β11= a11= 2. Tiếp theo dùng côngthức (1.6b) ta tính được:α21=1β11(a21) = −12,α31=1β11(a31) =32Với j = 2 làm tương tự như trên ta tính đượcβ12= a12= 3,β22= a22− α21β12=72,α32=1β22(a32− α31β12) = −97.Với j = 3 ta tính được:β13= a13= 1β23= a23− α21β13= −12β33= (a33− α31β13− α32β23) = −17Khi đó ta tìm được ma trận:L =1 0 0−1/2 1 03/2 −9/7 1, U =2 3 10 7/2 −1/20 0 −1/713Bây giờ ta đi tìm nghiệm của hệ phương trình Ly = b. Suy ra1 0 0−1/2 1 03/2 −9/7 1y1y2y3=1109Giải hệ phương trình này ta tìm được y =11;112; −37TBước tiếp theo, giải hệ phương trình Ux = y ta có:2 3 10 7/2 −1/20 0 −1/7x1x2x3=1111/2−3/7Cuối cùng ta tìm được nghiệm x3= 3, x2= 2, x1= 11.3 Phương pháp CholeskyXét hệ phương trình (1.1). Nếu A là ma trận đối xứng thì ta có thể phântích ma trận A dưới dạng:A = S.ST(1.10)với S là ma trận tam giác dưới, STlà ma trận chuyển vị của S.S =s110 0s12s22 0 s1ns2n snn; ST=s11s12 s1n0 s22 s2n 0 0 snn.Khi đó:(1.2) ⇔ S.STx = b(1.7) ⇔Sy = bSTx = yCác công thức (1.6)(1.8)(1.9) bây giờ có dạng:s11=√a11; s1j=a1js11;j = 2, nsii=aii−i−1k=1ski;i = 2, nsij=aij−i−1k=1skiskjsii(i < j) ; sij= 0 (i > j)(1.11)14y1=b1s11; yi=bi−i−1k=1sikyksii; (i > 1)xn=ynsnn; xi=yi−nk=i+1sikxksii(1.12)Ví dụ 1.6 Giải hệ phương trình đại số tuyến tính sau:x1+2x2+x3= 12x1+5x2+x3= 1x1+x2+2x3= 1bằng phương pháp Cholesky.Giải. Xét ma trậnA =1 2 12 5 11 1 2là ma trận đối xứng. Khi đó ta có thể phân tích ma trận A thành tích haima trận A = ST.S, trong đó S là ma trận tam giác trên. Nên ta có:s11=√1 = 1; s12=a12s11= 2; s13=a13s11= 1;s22=a22− s212=√5 − 22= 1;s23=a23−s12.s13s22= −1;s33=a33− s213− s223=√−2 − 1 − 1 =√−4 = 2i.⇒ S =1 2 10 1 −10 0 2i⇒ ST=1 0 02 1 01 −1 2iTìm y:y1=11= 1,y2= 1 − 2y1= −1,y3=1−y1+y22i=i2.Tìm x:x3=i2.12i=14,x2= −1 +14= −34,x1= 1 −14+32=94.Vậy nghiệm của hệ phương trình là x =94,−34,14T.151.4 Phương pháp phân rã QRNếu A là ma trận n × n thì luôn phân tích được dưới dạng:A = QR, (1.13)trong đó R là ma trận tam giác trên, Q là ma trận trực giaoQT= Q−1Khi đó hệ (1.2) có dạng:QRx = b.Nhân cả hai vế hệ phương trình trên với QTta được:Rx = QTb.Do R là ma trận tam giác trên nên nghiệm của hệ được tính ngay bằng côngthức truy hồi;xn=bnann; xk=bk−nj=k+1akjxjakk; k = n − 1, , 1.Vì Q là ma trận trực giao, vấn đề đặt ra là ta phải tìm phép biến đổi trựcgiao nào đó để đưa các phần tử nằm dưới đường chéo của ma trận Q về matrận không. Và ta có phép biến đổi Householder là một phép biến đổi trựcgiao, có khả năng đưa một loạt các phần tử của một cột về không mà vẫngiữ nguyên các phần tử ở bên trái và bên phải nó. Chẳng hạn, đưa các phầntử trên cột một, tính từ phần tử thứ hai trở xuống về không ta xây dựng matrận Householder theo công thứcP1= E −u1.uT1u12(1.14)với véctơ sinhu1= (a11+ sign (a11) .α, a21, , an1)T; α =ni=1a2i1(1.15)Bằng kiểm tra trực tiếp ta thấy các phần tử nằm trên cột một của matrận P1A đều có giá trị bằng không, ngoại trừ phần tử đầu tiên có giá trị là:−sign (a11) .α (1.16)16Cũng bằng kiểm tra trực tiếp các phần tử của ma trận P1A được tínhbằng công thức sau:aij= aij−a1aju122(1.17)trong đó kí hiệu a1và ajđể chỉ cột thứ nhất và cột thứ j của ma trậnA. Trong công thức (1.17) khi i = 1 thay vì viết phần tử a11ta phải lấya11+ sign(a11)α.Tiếp theo, ta xây dựng ma trận Householder của phép biến đổi House-holder P2theo (1.14) nhưng dựa trên véctơ sinh:u2= (0, a22+ sign (a22) .α, a32, , an2)T; α=ni=2a2i2Khi đó, ma trận P2P1A sẽ có cột một và cột hai thỏa mãn điều kiện matrận tam giác trên. Và các phần tử nằm trên cột một và dòng một khôngthay đổi giá trị, trong kki các phần tử khác của ma trận P1A vẫn thay đổigiá trị nhưng vẫn tuân thủ (1.16) và (1.17) với các chỉ số thay đổi tương ứng.Như vậy, sử dụng n − 1 phép biến đổi Householder P1; P2; Pn−1đượcxây dựng như mô tả ở trên ta sẽ đưa được ma trận A ban đầu về ma trận Rlà ma trận tam giác trên.Pn−1 P1A = R (1.18)Kí hiệu QT= Pn−1 P1từ (1.18) và từ tính chất ma trận trực giao ta suyraA = QR; Q = PT1 PTn−1(1.19)Bây giờ ta đi tính nghiệm của hệ (1.2) sau khi sử dụng phân rã QR.Từ (1.18) ta có:Pn−1 P1A x=Pn−1 P b → R x = QTb (1.20)Vì R là ma trận tam giác trên nên hệ (1.20) giải được nhờ công thức truyhồi như đã nêu trên.171.5 Phương pháp lặp đơnTrước tiên ta nhắc lại khái niệm chuẩn của ma trận.Định nghĩa 1.1: Cho ma trận A = (aij)n×n. Chuẩn của ma trận A là mộtsố không âm được kí hiệu là A và thỏa mãn các tính chất sau:i) A ≥ 0, A = 0 ⇔ A = Θ,ii) λA = |λ|A,iii) A + B ≤ A+ B.Ba chuẩn thường dùng đối với ma trận là:A∞= max1≤i≤nnj=1|aij|, A1= max1≤j≤nni=1|aij|, AF=ni,j=1a2ij.(1.21)Người ta thường định nghĩa chuẩn của ma trận theo chuẩn của véctơtương ứng như sau:A = supx=0AxxDễ thấy A xác định như trên thỏa mãn ba điều kiện về định nghĩachuẩn của ma trận.Từ hệ (1.2) bằng phép biến đổi tương đương ta thu được hệ ở dạng:x = Bx + g (1.22)Phép lặp đơn được xây dựng trên (1.22) theo công thức:xk+1= Bxk+ g (k = 0, 1, 2, ) (1.23a)hoặc viết theo từng ẩn ta có:xk+1i= bi1xk1+ bi2xk2+ + binxkn+ gi=bijxkj+ gii = 1, n(1.23b)trong đó xkvà xk+1là các xấp xỉ nghiệm ở bước lặp thứ k và k + 1Như vậy bằng phép lặp (1.23) ta tạo ra được dãy các véctơ. Câu hỏi đặtra là: Khi nào dãy đó hội tụ đến x∗là nghiệm đúng của (1.1)Định lý 1.1.(về điều kiện đủ để phép lặp (1.23) hội tụ)18Phép lặp (1.23) sẽ hội tụ đến nghiệm x∗của hệ (1.1) với mọi xấp xỉ banđầu x0nếu ta có:B < 1 (1.24)Hơn nữa ta có đánh giá sai số:xk− x∗≤B1−Bxk− xk−1xk− x∗≤Bk1−Bx1− x0(1.25)Chứng minh: Ta có đánh giá sau:xm+1− xm=Bxm− Bxm−1≤ Bxm− xm−1, ≤ ≤ Bm−kxk+1− xk(∀m > k ≥ 0) .Sử dụng đánh giá này vào bất đẳng thức:xk+p− xk≤xk+p− xk+p−1+ +xk+1− xkta được:xk+p− xk≤1 + B + B2+ + Bp−1xk+1− xk=1−Bp1−Bxk+1− xk.Lấy giới hạn hai vế cuả bất đẳng thức này khi k cố định, còn p → ∞, tasẽ nhận được đánh giá sau:xk− x∗≤xk+1− xk1 − B≤ ≤Bk1 − Bx1− x0Trên thực tế đánh giá này còn dùng làm tiêu chuẩn dừng phép lặp. Nghĩalà ta lặp theo (1.25) tới bước thứ k + 1 thì dừng, nếu thỏa mãn điều kiện:xk+1− xk1 − B< ε, (1.26)Nhận xét:19- Đối với phép lặp (1.23) thỏa mãn (1.25) thì ta có thể lấy x0≡ g- Luôn tồn tại cách đưa (1.2) về (1.22) thoả mãn (1.25). Chẳng han, nếudet A = 0, ta nhân hai vế của (1.2) với D ≡ A1−ε trong đó ε = (εij) là matrận mà các phần tử εijđủ nhỏ về giá trị tuyệt đối. Khi đó ta có:A−1− εAx = Db → x =εAx + Db ≡ Bx + gVì ta lấy |εij| đủ nhỏ nên B < 1-Dùng phương pháp lặp đơn có thể tính được ma trận nghịch đảo A−1.Thật vậy:Xét phép lặp:Bk+1= Bk(2E − ABk). (1.27)Dễ thấy rằng:A−1− Bk= A−1E − ABk= A−1{E − A[Bk−1(2E − ABk−1)]}=A−1E − ABk−12= = A−1E − AB02k.Suy ra:A−1− Bk≤A−1E − AB02kBiểu thức này cho thấy nếu chọn B0sao choE − AB0< 1thì phép lặp (1.27) hội tụ rất nhanh đến A−1và khi đó dãy các véctơ xácđịnh bởi công thức {xk≡ Bkb} hội tụ đến nghiệm chính xác của (1.2)Ta có thể chọn B0= εATvới:ε =1ni,j=1aijhoặcε =1maxinj=1|aij| + maxjni=1|aij|Như vậy, dùng phép lặp (1.23) ta có thể tính được ma trận A−1và kếthợp với công thức xk= Bkb khiA−1− Bkđủ nhỏ ta sẽ nhận được lời giảixấp xỉ (1.2).201.6 Phương pháp lặp theo SeidelXét phương trình (1.22). Ta phân tích ma trận B thành tổng của hai matrậnB = B1+ B2,trong đó: B1là ma trận tam giác dưới nhận được từ ma trận B bằng cáchgiữ nguyên phần tử nằm dưới đường chéo chính, còn các phần tử khác bằng0, còn ma trận B2= B − B1. Khi đó (1.22) có dạng:x = B1x + B2x + g, (1.28a)hoặc viết theo từng ẩn:xk+1i=i−1j=1bijxk+1j+nj=1bijxkj+g. (1.28b)Công thức (1.28) cho thấy trong phương pháp lặp theo Seidel, các ẩn tìm ởbước hiện tại (bước k + 1) được sử dụng ngay để tìm các ẩn số tiếp theo, còncác ẩn số chưa được tính thị dùng giá trị ở bước trước (bước k)Định lý (về điều kiện đủ để phép lặp Seidel hội tụ)Nếu ta có B < 1 thì phép lặp (1.28) hội tụ.Chứng minh. Ta lấy chuẩn B = B∞Do B < 1 nên phép lặp đơn hội tụ nên ta có:x∗i=bijx∗j+ gi. (i)Lấy (1.28b) trừ đi (i) ta được:xk+1i− x∗i=j