Tài liệu Phương pháp khử gauss giải hệ phương trình đại số tuyến tính

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------ Trần Thị Hương Liên PHƯƠNG PHÁP KHỬ GAUSS GIẢI HỆ PHƯƠNG TRÌNH ĐẠI SỐ TUYẾN TÍNH LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60 46 01 12 Người hướng dẫn khoa học PGS. TS. TẠ DUY PHƯỢNG THÁI NGUYÊN - NĂM 2014 Mục lục Mở đầu 3 1 Các phương pháp giải hệ phương trình đại số tuyến tính 1.1 Các phương pháp khử . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Phương pháp khử Gauss . . . . . . . . . . . . . . . . 1.1.2 Phương pháp phần tử trội toàn phần . . . . . . . . . 1.1.3 Phương pháp khử Gauss - Jordan . . . . . . . . . . . 1.2 Phương pháp phân rã LU . . . . . . . . . . . . . . . . . . . . 1.3 Phương pháp Cholesky . . . . . . . . . . . . . . . . . . . . . 1.4 Phương pháp phân rã QR . . . . . . . . . . . . . . . . . . . . 1.5 Phương pháp lặp đơn . . . . . . . . . . . . . . . . . . . . . . 1.6 Phương pháp lặp theo Seidel . . . . . . . . . . . . . . . . . . 1.7 Phương pháp lặp theo Jacobi và phương pháp lặp theo GaussSeidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Tổng quan về phương pháp khử Gauss giải hệ phương trình đại số tuyến tính 2.1 Sơ lược về các thuật toán song song giải hệ phương trình đại số tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Sơ lược về các phần mềm giải phương trình đại số tuyến tính trên máy tính song song . . . . . . . . . . . . . . 2.1.2 Giải hệ tam giác trên máy tính với bộ nhớ phân tán . 2.2 Các phương pháp giải hệ phương trình có ma trận hệ số thưa 2.2.1 Hệ ba đường chéo. Phương pháp Thomas . . . . . . . 2.2.2 Hệ ma trận băng. Phương pháp Thomas cải biên . . . 5 5 6 9 10 11 14 16 18 21 23 26 26 26 28 29 30 32 3 Sử dụng máy tính điện tử khoa học và phần mềm Maple trong đại số tuyến tính 33 1 3.1 Sử dụng máy tính điện tử khoa học trong giải hệ phương trình tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Tính toán ma trận trên CASIO fx-570VN PLUS . . . 3.1.2 Giải hệ phương trình bậc nhất hai ẩn trên CASIO fx570VN PLUS . . . . . . . . . . . . . . . . . . . . . . 3.1.3 Hệ ba phương trình bậc nhất ba ẩn trên CASIO fx570VN PLUS . . . . . . . . . . . . . . . . . . . . . . 3.1.4 Hệ bốn phương trình bậc nhất bốn ẩn trên CASIO fx-570VN PLUS . . . . . . . . . . . . . . . . . . . . . 3.1.5 Tính toán trên ma trận trên Vinacal 570 ES Plus . . . 3.1.6 Giải hệ phương trình bậc nhất bốn ẩn trên Vinacal 570 ES Plus . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Sử dụng phần mềm Maple trong giải hệ phương trình tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . 2 33 33 36 38 39 40 43 45 50 51 Mở đầu Phương pháp khử Gauss giải hệ phương trình đại số tuyến tính đã được biế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ực tế 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ững nă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ông tin (máy tính tốc độ cao, máy tinh song song,...). Luận văn " Phương pháp khử Gauss giải hệ phương trình đại số tuyến tính" có mục đích trình bày các phươ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ảng dạy đại số tuyến tính trong trường phổ thông, Luận văn cũng đề cập đến cá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ết luậ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ến tính Cá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óm cá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án trước được, ma trận hệ số thường không suy biến. Còn phương pháp lặp thường được sử dụng cho hệ có kích thước lớn hoặc hệ gần suy biến hoặc thỏa mãn điều kiện xấu. Mỗi một phương pháp được nêu trong chương thường kèm theo ví dụ minh họa. 3 Chương 2 Tổng quan về phương pháp khử Gauss giải hệ phương trình đại số tuyến tính Chương này trình bày tổng quan theo [6] các phương pháp giải hệ phương trình tuyến tính trong những năm gần đây: Sơ lược giới thiệu một số phần mề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ính Chương này giới thiệu sơ lược cách sử dụng các máy tính khoa học (CASIO fx-570VN Plus, Vinacal 570 ES Plus) và phần mềm Maple trong đại số tuyến tí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ủa PGS.TS. Tạ Duy Phượng- Viện Toán học, Viện khoa học và Công nghệ Việt Nam. 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ọc Khoa 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 ơn tới gia đình, bạn bè, tập thể lớp cao học toán K6D Trường Đại học Khoa họ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. 4 Chương 1 Các phương pháp giải hệ phương trình đại số tuyến tính 1.1 Các phương pháp khử . Xét hệ phương trình đại số dạng tổng quát    a11 x1 + a12 x2 + ... + a1n xn = b1 , a21 x1 + a22 x2 + ... + a2n xn = b2 , .... .... ..... .... ....   an1 x1 + an2 x2 + ... + ann xn = bn , (1.1) hoặc ở dạng ma trận Ax = b, (1.2) trong đó  a11  a21 A =  ... an1 a12 a22 ... an2 ... ... ... ...  a1n a2n  ...  ann được gọi là ma trận hệ số của phương trình đại số tuyến tính (1.1),   x1 x  x =  ...2  xn là véctơ ẩn cần tìm,   b1 b  b =  ...2  bn 5 là véctơ hệ số tự do. Ma trận  a11  a21 A1 = (A|b) =  ... an1 a12 a22 ... an2 ... ... ... ... a1n a2n ... ann  b1 b2  ...  bn đượ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ần các ẩn để đưa hệ phương trình đã cho về dạng tam giác rồi giải hệ tam giác nà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ư sau Sử dụng phép biến đổi tương đương trên ma trận A1 để đưa ma trận A về dạng tam giác trên. Tức là:  0 0 0 xn   a11 x1 +a0 12 x2 +... +a1n a22 x2 +... +a02n xn (1.1) ⇔ ... ...   0 ann xn = = ... = b01 , b02 , ... b0n . (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 , ..., x1 Ta mô tả gắn gọn phương pháp khử Gauss như sau Phần thuận: (k) Không làm mất tính tổng quát, giả sử các aii 6= 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/a11 rồi cộng vào dòng thứ hai sẽ khử được biến x1 ở phương trình thứ hai. Sau nhiều nhất n − 1 phép biến đổi ta đưa phần tử ở cột một từ vị trí thứ hai đổ xuống của ma trận A1 về giá trị không. Ở bước hai, bằng cách làm tương tự. Qua nhiều nhất n − 2 phép biến đổi ta đưa phần tử ở cột hai tính từ vị trí thứ ba đổ 6 xuố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 x2 ra 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ương trì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 tam giác trên. Trong quá trình biến đổi ta cũng biến đổi cùng một lúc vế phải củ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ệm xn , ..., x1 của hệ phương trình đã cho theo công thức: xn = b0n a0nn b0k − , xk = n P j=k+1 a0kk a0kj xj , 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áp khử Gauss: ( x1 +2x2 +5x3 = −9, x1 −x2 +3x3 = 2, 3x1 −6x2 −x3 = 25. Giải Viế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 1 −1 3 3 −6 −1 −9 2 25 ! ⇒ 1 2 5 0 −3 −2 0 −12 −16 −9 11 52 ! ⇒ 1 2 5 0 −3 −2 0 0 −8 −9 11 8 Khi đó ta có hệ phương trình: ( x1 +2x2 −5x3 = −9 −3x2 −2x3 = 11 −8x3 = 8 Quy 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. 7 ! Phươ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ác cù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ước khử đầ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 6= 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ực hiệ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ử x1 ta 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−1 ta cũng tìm phần tử có modul lớ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 −1 2 −1 3 0 2 11 0 9 ! . Trên cột một của ma trận A1 ta thấy max {|ak1 | /k = 1, 2, 3} = a31 = 3, đổi dò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ử 8 1/3 rồi cộng với dòng hai và nhân với phần tử ta được: ! 3 0 2 9 0 A1 = −1 2 −1 ⇒ A1 = 2 3 1 11 (−2/3) rồi cộng với dòng ba 3 0 2 0 2 −1/3 0 3 −1/3 9 3 5 ! . Ở bước khử thứ hai ta có max {|ak2 | /k = 2, 3} = a32 = 3. Thực hiện phép đổi vị trí dòng hai cho dòng ba, rồi nhân dòng vừa hoán đổi cho phần tử (−2/3) sau đó cộng với dòng ba ta được: A1 = 3 0 2 0 3 −1/3 0 2 −1/3 9 5 3 ! ⇒ A1 = 3 0 2 0 3 −1/3 0 0 −1/9 9 3 −1/3 ! Khi đó hệ phương trình đã cho có dạng:  +2x3 = 9  3x1 3x2 − 31 x3 = 5  − 19 x3 = − 13 Quy 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ần Ngay từ bước khử đầu tiên, ta chọn phần tử có giá trị tuyệt đối lớn nhất trong 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òng này với thừa số −alp/apq (l 6= p) rồi cộng dòng thứ l. Bằng cách này loại bỏ ẩn xp ra khỏi hệ phương trình, trừ phương trình thứ p. Sau đó loại hàng trội và cột q ra khỏi hệ phương trình vừa biến đổi, ta thu được hệ gồm n − 1 phươ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ép khử 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 đến phương trình hai ẩn ở hàng trội bị bỏ sau bước khử thứ n−1, rồi đến phương 9 trình ba ẩn là hàng trội bị bỏ sau bước khử thứ n − 2,... cho đến phương trình đủ n là dòng trội đầu tiên bị bỏ sau bước khử lần thứ nhất. Đặc trưng củ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 x1 mà 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 - Jordan Cơ sở của phương pháp này như sau: Từ ma trận suy rộng A1 , dùng phép biến đổi tương đương đưa ma trận hệ số của hệ phương trình về ma trận đơn vị E , và vế phải của hệ cũng được biến đổi đồng thời.  1  0 A1 ⇔  ... 0 0 1 ... 0 ... ... ... ... 0 0 ... 1  b01 b02  ...  b0n Khi đó nghiệm của hệ phương trình (1.1) là x = (b01 , b02 , ..., b0n )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ên hoặc phương pháp phần tử trội như đã mô tả (nếu cần thiết). Ở đây không cần phần nghịch để tìm nghiệm của hệ phương trình như trong phương pháp Gauss 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ì.Ta có 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à ma trận nghịch đảo của ma trận hệ số: ( 2x1 +3x2 +x3 = 11 −x1 +2x2 −x3 = 0 3x1 +2x3 = 9 10 Giải. Sử dụng biến đổi như trong ví dụ 1.2 đổi (A|b|E) như sau: ! 2 3 1 11 1 0 0 −1 2 −1 0 0 1 0 9 0 0 0 3 0 2   3 0 2 9 0 0 1 1 3 0 1 31  ⇒0 2 3 0 3 − 13 5 1 0 − 23   3 0 2 9 0 0 1 1 5 1 0 − 23  ⇒  0 3 −3 − 31 − 32 1 97 0 0 − 19 ! 3 0 0 3 12 18 15 3 −3 −3 ⇒ 0 3 0 6 0 0 1 3 6 −9 −7 và kết hợp ma trận đơn vị E biến 3 0 2 −1 2 −1 2 3 1 ⇒  3 0 2 1 ⇒  0 3 −3 0 2 − 31 ⇒ 3 0 2 0 3 − 13 0 0 1 ⇒ 1 0 2 0 1 0 0 0 1 9 0 11 9 5 3 9 5 3 1 2 3 0 0 1 0 1 0 1 0 0  0 0 1 1 0 − 23  0 1 13 0 0 1 1 0 − 32 6 −9 −7 ! −4 6 5 1 −1 −1 6 −9 −7 ! Vậy nghiệm của hệ phương trình là: x = (1, 2, 3)T và ma trận nghịch đảo tìm được là: A−1 = 1.2 −4 6 5 1 −1 −1 6 −9 −7 ! . Phương pháp phân rã LU Như chúng ta đã biết, nếu hệ phương trình (1.2) có dạng tam giác thì rất dễ 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 con từ 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, 11 ! (1.4) trong đó L là ma trận tam tổng quát như sau:  1 0 0 ... α 1 0 ...  21  L =  α31 α32 1 ... ... ... ... ... αn1 αn2 αn3 ... giác dưới, U là ma trận tam giác trên có dạng    β11 β12 β13 ... β1n 0 0   0 β22 β23 ... β2n   0 ;U =  0 β33 ... β3n   0  . (1.5) ... ... ... ... ... ... 1 0 0 0 ... βnn

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 P αik βkj (1 ≤ i ≤ j) (1.6a) k=1 αij = 1 βjj  aij − j−1 P  αik βkj (1.6b) k=1 Khi đó hệ (1.2) viết được dưới dạng: LU x = 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:   i−1 P y1 = b1/α11 , yi = α1ii bi − αik yk k=1   i−1 P xn = yn/βnn , xi = β1ii yi − βik yk k=1 12 (1.8) (1.9) Ví dụ 1.5 Giải hệ phương trình đại số tuyến tính sau : ( 2x1 +3x2 +x3 = 11 −x1 +2x2 −x3 = 0 3x1 +2x3 = 9 bằng phương pháp phân rã LU. Giải Xét ma trận hệ số của hệ phương trình ! 2 3 1 A = −1 2 −1 3 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 hai ma trận có dạng A = LU , trong đó: ! ! β11 β12 β13 1 0 0 0 β22 β23 L = α21 1 0 , U = α31 α32 1 0 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ông thức (1.6b) ta tính được: α21 = α31 = 1 β11 1 β11 (a21 ) = − 21 , (a31 ) = 23 Với j = 2 làm tương tự như trên ta tính được β12 = a12 = 3, β22 = a22 − α21 β12 = 27 , α32 = β122 (a32 − α31 β12 ) = − 79 . Với j = 3 ta tính được: β13 = a13 = 1 β23 = a23 − α21 β13 = − 21 β33 = (a33 − α31 β13 − α32 β23 ) = − 17 Khi đó ta tìm được ma trận: L= 1 0 0 −1/2 1 0 3/2 −9/7 1 13 ! ,U = 2 3 1 0 7/2 −1/2 0 0 −1/7 ! Bây giờ ta đi tìm nghiệm của hệ phương trình Ly = b. Suy ra ! ! ! 1 0 0 y1 11 −1/2 1 0 y2 = 0 y 9 3/2 −9/7 1 3
3 T ; − Giải hệ phương trình này ta tìm được y = 11; 11 2 7 Bước tiếp theo, giải hệ phương trình U x = y ta có: 2 3 1 0 7/2 −1/2 0 0 −1/7 x1 x2 x3 ! ! = 11 11/2 −3/7 ! Cuối cùng ta tìm được nghiệm x3 = 3, x2 = 2, x1 = 1 1.3 Phương pháp Cholesky Xét hệ phương trình (1.1). Nếu A là ma trận đối xứng thì ta có thể phân tích ma trận A dưới dạng: A = S.S T (1.10) với S là ma trận tam giác dưới, S T là ma trận chuyển vị của S .  s11 0  s12 s22 S =  ... ... s1n s2n   s11 s12 ... 0 0 s22  ... 0  T ; S =   ... ... ... ... 0 0 ... snn ... ... ... ...  s1n s2n  ...  . snn Khi đó: T (1.2) ⇔ S.S  x=b Sy = b (1.7) ⇔ ST x = y Các công thức (1.6)(1.8)(1.9) bây giờ có dạng:
 √ a1j s = a ; s = ; j = 2, n 11  s11  s 11 1j   i−1 
P  ski ; i = 2, n sii = aii − k=1   i−1 P   aij − ski skj   k=1 sij = (i < j) ; sij = 0 (i > j) sii 14 (1.11)  i−1 P  bi − s y   y = b1 ; y = k=1 ik k ; (i > 1) 1 i s11 sii n P  yi − sik xk   n xn = synn ; xi = k=i+1 sii (1.12) Ví dụ 1.6 Giải hệ phương trình đại số tuyến tính sau: ( x1 +2x2 +x3 = 1 2x1 +5x2 +x3 = 1 x1 +x2 +2x3 = 1 bằng phương pháp Cholesky. Giải. Xét ma trận 1 2 1 2 5 1 1 1 2 A= ! là ma trận đối xứng. Khi đó ta có thể phân tích ma trận A thành tích hai ma trận A = S T .S , trong đó S là ma trận tam giác trên. Nên ta có: √ 12 13 = 2; s13 = as11 = 1; s11 = 1 = 1; s12 = as11 p √ s22 = a22 − s212 = 5 − 22 = 1; 12 .s13 s23 = a23 −s = −1; p s22 √ √ s33 = a33 − s213 − s223 = −2 − 1 − 1 = −4 = 2i. ! ! 1 2 1 1 0 0 ⇒ S = 0 1 −1 ⇒ ST = 2 1 0 0 0 2i 1 −1 2i Tìm y : y1 = 1 1 = 1, y2 = 1 − 2y1 = −1, y3 = Tìm x: 1−y1 +y2 2i = 2i . x3 = 2i . 2i1 = 14 , x2 = −1 + 1 4 x1 = 1 − 14 + Vậy nghiệm của hệ phương trình là x = 15 = − 34 , 3 2 = 94 .
9 −3 1 T , , 4 4 4 . 1.4 Phương pháp phân rã QR Nế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 QT ta được: Rx = QT b. 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ông thức truy hồi; xn = b0n ; a0nn b0k xk = − n P j=k+1 a0kk a0kj xj ; 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ực giao nào đó để đưa các phần tử nằm dưới đường chéo của ma trận Q về ma trận không. Và ta có phép biến đổi Householder là một phép biến đổi trực giao, 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ẫn giữ 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ần tử 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 ma trận Householder theo công thức P1 = E − u1 .uT1 ku1 k2 (1.14) với véctơ sinh v u n uX T u1 = (a11 + sign (a11 ) .α, a21 , ..., an1 ) ; α = t a2i1 (1.15) i=1 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 ma trận P1 A đều có giá trị bằng không, ngoại trừ phần tử đầu tiên có giá trị là: −sign (a11 ) .α 16 (1.16) Cũng bằng kiểm tra trực tiếp các phần tử của ma trận P1 A được tính bằng công thức sau: a1 aj . (1.17) a0ij = aij − 2 ku1 k 2 trong đó kí hiệu a1 và aj để chỉ cột thứ nhất và cột thứ j của ma trận A. Trong công thức (1.17) khi i = 1 thay vì viết phần tử a11 ta phải lấy a11 + sign(a11 )α. Tiếp theo, ta xây dựng ma trận Householder của phép biến đổi Householder P2 theo (1.14) nhưng dựa trên véctơ sinh: v u n uX 0 0 0 0 0 T 0 u2 = (0, a22 + sign (a22 ) .α , a32 , ..., an2 ) ; α = t a2i2 i=2 Khi đó, ma trận P2 P1 A sẽ có cột một và cột hai thỏa mãn điều kiện ma trậ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ông thay đổi giá trị, trong kki các phần tử khác của ma trận P1 A vẫn thay đổi giá 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 được xây dựng như mô tả ở trên ta sẽ đưa được ma trận A ban đầu về ma trận R là ma trận tam giác trên. Pn−1 ...P1 A = R (1.18) Kí hiệu QT = Pn−1 ...P1 từ (1.18) và từ tính chất ma trận trực giao ta suy ra T A = QR; Q = P1T ...Pn−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 ...P1 A x=Pn−1 ...P b → R x = QT b (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 truy hồi như đã nêu trên. 17 1.5 Phương pháp lặp đơn Trướ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ột số không âm được kí hiệu là kAk và thỏa mãn các tính chất sau: i) kAk ≥ 0, kAk = 0 ⇔ A = Θ, ii) kλAk = |λ| kAk , iii) kA + Bk ≤ kAk + kBk . Ba chuẩn thường dùng đối với ma trận là: kAk∞ = max n X 1≤i≤n |aij |, kAk1 = max 1≤j≤n j=1 n X |aij |, v uX u n 2 kAkF = t aij . i=1 i,j=1 (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: kAxk kAk = sup x6=0 kxk Dễ thấy kAk xác định như trên thỏa mãn ba điều kiện về định nghĩa chuẩ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+1 i = bi1 xk1 + bi2 xk2 + ... + bin xkn + gi = X bij xkj + gi
i = 1, n (1.23b) trong đó xk và xk+1 là các xấp xỉ nghiệm ở bước lặp thứ k và k + 1 Như 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 đặt ra 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ụ) 18 Phé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 x0 nếu ta có: kBk < 1 (1.24) Hơn nữa ta có đánh giá sai số: k x − x∗ ≤ k x − x∗ ≤ kBk 1−kBk k kBk 1−kBk k x − xk−1 1 x − x0 (1.25) Chứng minh: Ta có đánh giá sau: m+1 m m−1 x x − xm−1 − xm = Bxm − Bx ≤ kBk , ≤ ... ≤ kBkm−k xk+1 − xk (∀m > k ≥ 0) . Sử dụng đánh giá này vào bất đẳng thức: k+p x − xk ≤ xk+p − xk+p−1 + ... + xk+1 − xk ta được:  k+p  2 p−1 k+1 k x − x ≤ 1 + kBk + kBk + ... + kBk x − xk p = 1−kBk 1−kBk k+1 x − xk . Lấy giới hạn hai vế cuả bất đẳng thức này khi k cố định, còn p → ∞, ta sẽ nhận được đánh giá sau: k+1 k x k − x kBkk x1 − x0 x − x∗ ≤ ≤ ... ≤ 1 − kBk 1 − kBk 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ĩa là 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: k+1 x − xk < ε, (1.26) 1 − kBk Nhận xét: 19