Đăng ký Đăng nhập
Trang chủ Phương pháp lặp mới giải hệ phương trình tuyến tính lớn và thưa...

Tài liệu Phương pháp lặp mới giải hệ phương trình tuyến tính lớn và thưa

.PDF
61
407
90

Mô tả:

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------- ĐẶNG ANH TÚ PHƢƠNG PHÁP LẶP MỚI GIẢI HỆ PHƢƠNG TRÌNH TUYẾN TÍNH LỚN VÀ THƢA LUẬN VĂN THẠC SỸ TOÁN HỌC THÁI NGUYÊN - 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------- ĐẶNG ANH TÚ PHƢƠNG PHÁP LẶP MỚI GIẢI HỆ PHƢƠNG TRÌNH TUYẾN TÍNH LỚN VÀ THƢA Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60.46.01.12 LUẬN VĂN THẠC SỸ TOÁN HỌC NGƢỜI HƢỚNG DẪN KHOA HỌC TS. Lê Thanh Huệ THÁI NGUYÊN - 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ MỤC LỤC MỞ ĐẦU .................................................................................................................... 1 1.Lý do chọn đề tài. .................................................................................................... 1 2.Mục đích của đề tài. ................................................................................................ 2 3. Phạm vi nghiên cứu. ............................................................................................... 2 4. Nội dung nghiên cứu của đề tài.............................................................................. 3 5. Phƣơng pháp nghiên cứu. ....................................................................................... 3 6. Bố cục của đề tài. ................................................................................................... 3 CHƢƠNG I: CÁC PHƢƠNG PHÁP GIẢI HỆ PHƢƠNG TRÌNH TUYẾN TÍNH 5 I.1 Hệ phƣơng trình tuyến tính. .................................................................................. 5 I.1.1 Hệ phƣơng trình tuyến tính tổng quát. ............................................................... 5 I.1.2 Nghiệm của hệ phƣơng trình tuyến tính. ........................................................... 6 I.1.3 Các hệ phƣơng trình tƣơng đƣơng ..................................................................... 6 I.1.4 Các dạng ma trận, dạng véctơ của hệ phƣơng trình tuyến tính. ........................ 7 I.2. Phƣơng pháp tìm nghiệm của hệ phƣơng trình tuyến tính. ................................. 8 CHƢƠNG II : PHƢƠNG PHÁP LẶP ..................................................................... 12 II.1 Các phƣơng pháp giải trực tiếp. ........................................................................ 12 II.1 Sự thay đổi thuật toán trong tính toán cỡ lớn. ................................................. 12 II.2. Những khó khăn của các phương pháp giải trực tiếp. ..................................... 13 II.2.1 Phương pháp khử Gauss. ............................................................................... 13 II.2.2. Phương pháp nhân tử hóa Cholesky ............................................................. 14 II.2.3 Vấn đề Fill – in ( suy giảm độ thưa ).............................................................. 15 II.2.4. Vấn đề truy cập đối với ma trận .................................................................... 18 II. 3. Các phƣơng pháp lặp cơ bản ........................................................................... 18 II.3.1 Tách ma trận. .................................................................................................. 19 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ II. 3.2 Phép lặp Jacobi ............................................................................................. 22 II.3.3 Phép lặp Gauss-Seidel. ................................................................................... 24 II.4. Phƣơng pháp nới lỏng....................................................................................... 25 II.4.1 Phương pháp trên – nới lỏng liên tiếp ........................................................... 25 II.5. Các phƣơng pháp lặp dựa trên phép chiếu ....................................................... 26 II.5.1 phép chiếu song song...................................................................................... 26 II.5.2 Phương pháp chiếu Kaczmarz ........................................................................ 27 II.5.3 Phương pháp chiếu đồng thời của Cimmino .................................................. 30 CHƢƠNG III. PHƢƠNG PHÁP LẶP MỚI TÌM NGHIỆM HỆ PHƢƠNG TRÌNH TUYẾN TÍNH .......................................................................................................... 33 III.1. Phƣơng pháp lặp cho hệ phƣơng trình tuyến tính ........................................... 33 III.2. Phát biểu bài toán. ........................................................................................... 35 III.3 Cơ sở lý thuyết của thuật toán .......................................................................... 36 III.4. Mô tả thuật toán............................................................................................... 41 III.5. Tính toán thử nghiệm. ..................................................................................... 43 Kết luận. ................................................................................................................... 45 TÀI LIỆU THAM KHẢO ........................................................................................ 47 PHỤ LỤC ................................................................................................................. 49 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ MỘT SỐ CÁC KÝ HIỆU VÀ ĐỊNH NGHĨA Cho  n là không gian Euclid. Ta sử dụng các ký hiệu và khác niệm: x  n là véc tơ cột, xT là véc tơ hàng. Với x  n , chuẩn của véc tơx, ký hiệu là x đƣợc định nghĩa x1 , x2 ,..., xn x12 bởi: x x22 ... xn2 Tích vô hƣớng của hai véc tơ x, y x x1 , x2 ,..., xn , y n x y , ở đây i 1 i i y1 , y2 ,..., yn Ma trận A cấp m n A a11 a12 a21 a22 . . . . . . am1 am 2 ... a1n ... a2 n ... . ... . ... . ... amn Các ký hiệu det(A),A-1, AT, R(A), N(A), r(A) lần lƣợt là định thức, nghịch đảo, chuyển vị, ảnh, hạch và hạng của ma trận A. Phép chiếu a. Định nghĩa phép chiếu: Giả sử cho trƣớc điểm x  n và tập lồi đóng C khác rỗng. Hình chiếu của x lên C, ký hiệu PCx xác định nhƣ sau: Pc x C x pC x inf x y y C Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ b. Tính chất của phép chiếu: Phép chiếu xác định nhƣ trên có các tính chất quan trọng sau: PC  PC i) ii) Tính chất duy nhất: điểm duy nhất Py đƣợc đặc trƣng bởi Py iii) PC C và C Py, y Py 0 P là ánh xạ không dãn. Vài trƣờng hợp cụ thể: C là hình cầu đơn vị: C PC x x 1 . Khi đó PCx = x, nếu x C : x / x , và trƣờng hợp khác. C là orthan không âm: C C là siêu phẳng: C PC x X: x x a, x a b 2 x x X : x 0 . Khi đó PCx = x+. X ; a, x b , ở đây a 0 và b R . Khi đó a C là không gian con: C span a1 ,..., an , ở đó ai là các véc tơ cột độc lập tuyến tính của ma trận A. Khi đó: PC x A A* A 1 A* x Các trƣờng hợp còn lại với 1 < m < n -1 là bài toán khó tƣơng đƣơng với việc giải một hệ đại số tuyến tính. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ DANH MỤC HÌNH VẼ - BẢNG BIỂU Hình 1: Phép chiếu Kaczmarz trong không gian 2 chiều Hình 2: Mô tả ý tƣởng thuật toán Hình 3: Minh họa bài toán bổ trợ Bảng 1: Kết quả tính toán trên một vài bộ dữ liệu chuẩn. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1 MỞ ĐẦU 1.Lý do chọn đề tài. Trong suốt thời gian qua luôn luôn có cuộc cạnh tranh liên tục giữa các phƣơng pháp lặp và các phƣơng pháp giải trực tiếp các bài toán cỡ lớn xuất hiện trong thực tiễn. Ở một lớp bài toán này thì phƣơng pháp giải trực tiếp chiếm ƣu thế, ở một lớp bài toán khác, các phƣơng pháp lặp lại tỏ ra hiệu quả hơn. Có những bài toán do kích cỡ số liệu tƣởng chừng nhƣ chỉ có thể sử dụng các phƣơng pháp lặp, nhƣng rồi sự tiến bộ về khả năng tính toán và lƣu trữ vƣợt trội của máy tính đã cho phép các phƣơng pháp trực tiếp đua tranh. Nhu cầu tìm kiếm lời giải của hệ phƣơng trình tuyến tính nhƣ một công đoạn tính toán, xuất hiện rất thƣờng xuyên trong quá trình tìm lời giải cho nhiều bài toán lý thuyết và thực tiễn trong khoa học kỹ thuật, trong các công trình nghiên cứu khoa học, bài toán xử lý ảnh, bài toán tối ƣu trong kỹ thuật, trong kinh tế, … Bởi vậy, nghiên cứu cải tiến các phƣơng pháp giải hệ phƣơng trình tuyến tính lớn và thƣa xuất hiện trong các tính toán ứng dụng thực tế là một vấn đề quan trọng trong khoa học tính toán. Do đó việc tìm kiếm các thuật toán hữu hiệu giải các hệ tuyến tính đặc thù này thực sự là một yêu cầu cấp thiết. Về mặt lý thuyết thuần túy, việc giải hệ phƣơng trình tuyến tính là không khó. Tuy nhiên về mặt tính toán thực tiễn, việc thực hiện liên tục các phép tính với sự sai số, có thể biến một bài toán đơn giản thành một bài toán rất phức tạp nhiều khi là không thể thực hiện đƣợc. Phƣơng pháp truyền thống giải hệ phƣơng trình tuyến tính không suy biến là rất hoàn hảo về mặt lý thuyết. Song trong thực tế các bài toán trong các lĩnh vực Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 2 khoa học kỹ thuật, cũng nhƣ trong lĩnh vực kinh tế đòi hỏi ngày một cao và cả tính ổn định trong tính toán. Đặc biệt các phƣơng pháp trực tiếp áp dụng cho các hệ tuyến tính lớn và thƣa có thể dẫn đến các “fill-in” cao làm tràn bộ nhớ trong quá trình tính toán. Hơn nữa, ngày nay không có kỹ thuật hữu hiệu nào để tính “fill-in” cực tiểu. Gần đây, có một thuật toán xấp xỉ cho bài toán “fill-in” cực tiểu đã đƣợc đề xuất nhƣng chƣa rõ tính hiệu quả thực sự của nó. Mặt khác do sự tích lũy sai số trong quá trình tính toán nên các phƣơng pháp giải trực tiếp thƣờng kém ổn định. Trong các trƣờng hợp nhƣ vậy, phƣơng pháp lặp chiếm ƣu thế và đƣợc sự dụng rộng rãi hơn. Thông thƣờng thì các phƣơng pháp lặp tận dụng đƣợc tốt hơn tính thƣa và tính đƣờng chéo của ma trận đầu vào, cho phép bỏ qua các phần tử bằng 0 không cần thiết để giảm yêu cầu lƣu trữ ở bộ nhớ, nhằm tăng cƣờng khả năng tính toán cả về độ lớn và thời gian cho lớp các bài toán siêu kích cỡ và ma trận hệ số thƣa. Để giải quyết những yêu cầu trên, em đã tìm một hƣớng tiếp cận mới để giải hệ phƣơng trình tuyến tính cỡ lớn và sử dụng phƣơng pháp lặp. 2.Mục đích của đề tài. Nghiên cứu các thuật toán lặp và trên cơ sở đó đề xuất hƣớng tiếp cận thuật toán lặp mới giải hệ phƣơng trình tuyến tính cỡ lớn và thƣa. 3. Phạm vi nghiên cứu. Nghiên cứu phƣơng pháp lặp mới để giải hệ phƣơng trình tuyến tính lớn và thƣa. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 3 4. Nội dung nghiên cứu của đề tài - Tìm hiểu sự phát triển các phƣơng pháp lặp nhƣ: phƣơng pháp gradient liên hợp, Lanczos, phƣơng pháp lặp Krylov,…. - Nghiên cứu các phƣơng pháp chiếu trực giao liên tiếp của Cimmino, Kaczmarz, - Tiến hành xây dựng thuật toán chiếu lặp mới, ứng dụng cho việc tìm nghiệm hệ phƣơng trình tuyến tính cỡ lớn và các hệ gần thoái hóa. - Lập trình theo các modul của thuật toán đã xây dựng. - Tính toán chạy thử nghiệm trên các bộ dữ liệu chuẩn, đánh giá kết quả cụ thể. 5. Phƣơng pháp nghiên cứu. - Nghiên cứu các kiến thức cơ sở về hệ phƣơng trình tuyến tính - Nghiên cứu lý thuyết về các phƣơng pháp lặp. - Nghiên cứu lý thuyết về các phƣơng pháp chiếu liên tiếp - Nghiên cứu, xây dựng thuật toán lặp mới ứng dụng giải hệ tuyến tính lớn và thƣa. - Ngôn ngữ lập trình C/C++ trên môi trƣờng Windows. 6. Bố cục của đề tài. Luận văn đƣợc trình bày trong 50 trang, đƣợc chia làm 3 chƣơng: Chƣơng I: Các phƣơng pháp giải hệ phƣơng trình tuyến tính. Chƣơng II: Phƣơng pháp lặp. Chƣơng III: Phƣơng pháp lặp mới tìm nghiệm hệ phƣơng trình tuyến tính. Kết luận. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 4 Tài liệu tham khảo. Phụ lục. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 5 CHƢƠNG I: CÁC PHƢƠNG PHÁP GIẢI HỆ PHƢƠNG TRÌNH TUYẾN TÍNH I.1 Hệ phƣơng trình tuyến tính. I.1.1 Hệ phƣơng trình tuyến tính tổng quát. Hệ m phƣơng trình tuyến tính n ẩn x1, x2 ,..., xn hệ số thuộc không gian véc tơ  n là hệ có dạng: a11 x1 a12 x2 ... a1n xn b1 (1.1) ........................................... ; am1 x1 am 2 x2 ... amn xn bm Hay có thể viết gọn hơn: n aik xk bi , i 1,..., m k 1 Trong đó aik , bi là các phần tử thuộc không gian véc tơ  n ; aik gọi là hệ số của ẩn xk , bi gọi là hệ số tự do, i 1,..., m; k 1,...n. Hệ phƣơng trình (1.1) gọi là hệ phương trình tuyến tính tổng quát. Đặc biệt nếu b1 ... bm 0 thì hệ (1.1) có dạng n aik xk 0, i 1,..., m (1.2) k 1 Hệ phƣơng trình (1.2) đƣợc gọi là hệ phương trình tuyến tính thuần nhất. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 6 I.1.2 Nghiệm của hệ phƣơng trình tuyến tính. Mỗi nghiệm của hệ phƣơng trình (1.1) là một véc tơ không gian véc tơ  n sao cho khi thay ẩn xk bởi thành phần k 1 ,..., n của , k 1,..., n vào hệ (1.1) ta đƣợc m đẳng thức. - Nếu hệ (1.1) có một nghiệm duy nhất thì gọi là hệ xác định. - Nếu hệ (1.1) có nhiều nghiệm thì gọi là hệ không xác định . - Nếu hệ (1.1) không có nghiệm thì gọi là hệ vô nghiệm. Dễ thấy rằng véc tơ 0,...,0 luôn luôn là một nghiệm của hệ thuần nhất (1.2); nghiệm này đƣợc gọi là nghiệm tầm thường. I.1.3 Các hệ phƣơng trình tƣơng đƣơng Hai hệ phƣơng trình tuyến tính n n aik xk aik' xk bi , i 1,..., m và k 1 bi' , i 1,..., p k 1 Đƣợc gọi là tƣơng đƣơng nếu mỗi nghiệm của hệ này là nghiệm của hệ kia và ngƣợc lại. Tức là các tập nghiệm của hệ phƣơng trình đó là trùng nhau. Các phép biến đổi tƣơng đƣơng Mỗi phép biến đổi không làm thay đổi tập nghiệm của các hệ phƣơng trình gọi là phép biến đổi tƣơng đƣơng. Dễ dàng chứng minh đƣợc rằng các phép biến đổi sau đây là các phép biến đổi tương đương: a) Thay đổi thứ tự các phƣơng trình của hệ (1.1) Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 7 b) Loại khỏi hệ (1.1) các phƣơng trình có các hệ số của các ẩn và hệ số tự do đều bằng 0. c) Nhân hai vế của một phƣơng trình với một phần tử k 0 . d) Cộng hai vế của một phƣơng trình vào các vế của một phƣơng trình khác. I.1.4 Các dạng ma trận, dạng véctơ của hệ phƣơng trình tuyến tính. Tƣơng ứng với hệ phƣơng trình (1.1) ta có các ma trận sau: A a11 a12 ... a1n ... ... ... ... , A am1 am 2 ... amm a11 a21 ... a1n b1 ... ... ... ... am1 am 2 ... amm bm Ma trận A gọi là ma trận của hệ phƣơng trình (1.1), hạng của ma trận A gọi là hạng của hệ phương trình (1.1). Ma trận A nhận đƣợc từ ma trận A bằng cách bổ sung thêm cột thứ n+1 là hệ số tự do của hệ phƣơng trình (1.1). Ma trận A gọi là ma trận mở rộng của hệ (1.1) Nếu sử dụng kí hiệu ma trận thì hệ phƣơng trình (1.1) có thể viết dƣới dạng một phƣơng trình ma trận: x1 b1 . . A . . . . xn . (1.3) bm Hệ thức (1.3) gọi là dạng ma trận của hệ phƣơng trình tuyến tính (1.1). Nếu coi các véc tơ cột trong ma trận mở rộng A là: Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 8 j 1j , 2j ,..., mj , j 1, n ; b1 , b2 ,..., bm Khi đó thì hệ phƣơng trình tuyến tính (1.1) có thể viết dƣới dạng véc tơ nhƣ sau: x 1 1 2 x2 ... n (1.4) xn Hệ thức (1.1) đƣợc gọi là dạng véc tơ của hệ phƣơng trình tuyến tính (1.1). I.2. Phƣơng pháp tìm nghiệm của hệ phƣơng trình tuyến tính. Định lý 1.1.Hệ phương trình tuyến tính (1.1) có nghiệm khi và chỉ khi hạng của ma trận A bằng hạng của ma trận mở rộng A . Chứng minh: Điều kiện cần: Giả sử hệ phƣơng trình tuyến tính (1.1) có nghiệm là (c1 , c2 ,..., cn ) tức là : c c 1 1 Nhƣ vậy ... 2 2 c n n là một tổ hợp tuyến tính của hệ véc tơ Suy ra L( 1, 2 ,..., n , ) L( 1, 2 ,..., n 1 , 2 ,..., n . ) . Điều đó chứng tỏ r (A) r ( A) Điều kiện đủ: Giả sử r (A) r ( A) điều đó có nghĩa là hạng của hệ véc tơ 1 , 2 ,..., n , Suy ra dim( 1, bằng hạng của hệ véc tơ 2 ,..., Từ đó suy ra L( 1, n 2 , ) ,..., dim( 1, n , ) 2 L( 1, 1 , ,..., 2 2 n ,..., n . ) ,..., n ) và do đó L( 1, 2 ,..., tồn tại các phần tử (c1, c2 ,..., cn ) Rn sao cho : Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ n ) hay 9 c c 1 1 2 2 ... c n n . Vậy hệ phƣơng trình tuyến tính (1.1) có nghiệm. I.2.1 Hệ Cramer : Hệ phƣơng trình tuyến tính (1.1) đƣợc gọi là hệ Cramer nếu ma trận A là ma trận vuông khả nghich tức là m n và det( A) 0 . Định lý 1.2 : Hệ Cramer a11 x1 ... a1n xn b1 (1.5) ................................ an1 x1 ... ann xn bn là một hệ xác định. Nghiệm duy nhất của hệ đƣợc tính bởi công thức j xj Trong đó , j 1,..., n (1.6) det( A) j a11 ... b1 ... a1n ... ... ... ... ... an1 ... bn ... ann (1.7) Công thức (1.6) đƣợc gọi là công thức Cramer. Chú ý : Định thức j là định thức nhận đƣợc từ ma trận A của hệ phƣơng trình tuyến tính (1.5) bằng cách thay các phần tử ở cột thứ j (hệ số của ẩn x j ) bởi các phần tử b1 ,..., bn (các hệ số tự do). Chứng minh : Theo (1.7) nếu khai triển định thức Số hóa bởi Trung tâm Học liệu j theo cột thứ j ta có : http://www.lrc-tnu.edu.vn/ 10 n bk Akj j (a) k 1 Trong đó Akj là phần bù đại số của phần tử akj trong định thức det(A). Ta viết lại hệ (1.5) dƣới dạng ma trận: x1 b1 . A . . . . . xn bn . (b) Vì định thức det( A) 0 nên ma trận A có ma trận nghịch đảo A 1 . Nhân bên trái hai vế của đẳng thức (b) với ma trận A 1 , trong đó: A 1 1 A* , với A* det( A) A11 ... A1n A21 ... An1 ... ... ... là ma trận phù hợp của ma trận A và A2 n ... Ann hệ thức (a) ta có: x1 b1 . . . . A1 . . xn 1 Thay A bn 1 A* ta đƣợc: det( A) Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 11 x1 b1 . 1 . . A11 A21 ... An1 . ... A1n ... ... ... A2 n ... Ann . . xn bn n bk Ak 1 x1 k 1 . 1 . . . . . n xn bk Akn k 1 Suy ra: 1 x1 . . . . . . xn (c) n Từ đẳng thức ma trận (c) ta có xj j , j 1,..., n Vậy công thức Cramer đƣợc chứng minh. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 12 CHƢƠNG II : PHƢƠNG PHÁP LẶP II.1 Các phƣơng pháp giải trực tiếp. II.1 Sự thay đổi thuật toán trong tính toán cỡ lớn. Khi ma trận hệ số lớn và thƣa, phƣơng pháp Gauss thƣờng khó áp dụng đƣợc trong quá trình tính toán đòi hỏi không gian lƣu trữ và thời gian tính toán đƣợc tích lũy quá lớn. Mặt khác nói đến “thƣa”là sự ƣu việt số lƣợng và vị trí các phần tử khác 0. Giả sử cho trƣớc ma trận A cỡ m n và véctơ x có n chiều, nếu ma trận thƣa thì việc tính toán ma trận véctơ Ax chỉ cần số các phép tính số học rất nhỏ, cỡ n hoặc (nlogn), so với n 2 phép tính khi ma trận đầy. ( Lƣu ý rằng tuy có thể là ma trận đầy, nhƣng có những ma trận đƣợc xây dựng , chẳng hạn ma trận Toepliz, mà tích ma trận véc tơ có thể it hơn (nlogn) lần, thậm chí tốt hơn ) Ta xét hệ phƣơng trình tuyến tính Ax b (2.1) Với A là ma trận không suy biến ( det A 0 ). Ở đây chúng ta tập trung trƣờng hợp A không đối xứng (với A đối xứng, xác định dƣơng đã đƣợc nghiên cứu bằng phƣơng pháp Conjugate Gradient ). Và ta chỉ ra nguyên nhân tại sao trong các tính Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 13 toán cỡ lớn, có sự thay đổi từ các phƣơng pháp trực tiếp Gauss sang các phƣơng pháp lặp. II.2. Những khó khăn của các phương pháp giải trực tiếp. Các phƣơng pháp giải trực tiếp tạo thành một trong hai lớp kỹ thuật để giải hệ phƣơng trình Ax b . Trong những phƣơng pháp này, nghiệm đúng x* A 1b nhận đƣợc sau một số bƣớc biến đổi đã biết. Bộ nhớ dành cho ma trận hệ số thƣờng bị tràn trong quá trình thao tác chi tiết với các hàng và các cột của ma trận. Hai ví dụ nổi bật của phƣơng pháp trực tiếp đối với hệ số không đối xứng dƣơng là phƣơng pháp khử Gauss và phƣơng pháp nhân tử hóa Cholesky tƣơng ứng. II.2.1 Phương pháp khử Gauss. Là một cách tiếp cận trực tiếp điển hình đối với các hệ tuyến tính phi – Hecmit. Giai đoạn đầu tiên của quá trình giải là tính biểu thức nhân tử hóa dạng : A PLU (2.2) Trong đó P là ma trận hoán vị cấp m n . Các phần tử L 1 * 1 ,U ... ... ... * ... * 1 * ... ... * * ... ... ... * L là ma trận tam giác dƣới cấp n n với các phần tử trên đƣờng chéo bằng đơn vị, và U là ma trận tam giác trên cùng cấp. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
- Xem thêm -

Tài liệu liên quan