Tài liệu Phương pháp lặp giải hệ thưa và ứng dụng

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA LÊ TRUNG SAN PHƯƠNG PHÁP LẶP GIẢI HỆ THƯA VÀ ỨNG DỤNG CHUYÊN NGÀNH: TOÁN ỨNG DỤNG MÃ SỐ NGÀNH: 60 46 36 LUẬN VĂN THẠC SĨ CBHD: TS. ĐẶNG VĂN VINH TP. HỒ CHÍ MINH, THÁNG 11 NĂM 2008 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH Cán bộ hướng dẫn khoa học : Tiến sĩ ĐẶNG VĂN VINH............................ ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... Cán bộ chấm nhận xét 1 : PGS TS ĐẬU THẾ CẤP ..................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... Cán bộ chấm nhận xét 2 : Tiến sĩ LÊ THỊ QUỲNH HÀ ............................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... ....................................................................................................................... Luận văn thạc sĩ được bảo vệ tại HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày 29 tháng 08 năm 2009 -i- CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM PHÒNG ĐÀO TẠO SĐH ĐỘC LẬP – TỰ DO – HẠNH PHÚC Tp. HCM, ngày . . . . tháng . 02 . năm 2008. NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: Lê Trung San Phái : Nam Ngày, tháng, năm sinh: 05 – 02 - 1977 Nơi sinh : Nam Định Chuyên ngành: Toán ứng dụng MSHV : 02407705. I- TÊN ĐỀ TÀI: PHƯƠNG PHÁP LẶP GIẢI HỆ THƯA VÀ ỨNG DỤNG II- NHIỆM VỤ VÀ NỘI DUNG: 1. Nghiên cứu một số phương pháp lặp cơ bản giải hệ phương trình Ax = b. 2. Lập trình giải hệ Ax = b (Coding ) bằng ngôn ngữ Matlab. 3. Nghiên cứu một vài giải pháp lưu trữ ma trận thưa. 4. Một số bài toán ứng dụng hệ Ax = b. III- NGÀY GIAO NHIỆM VỤ : IV- NGÀY HOÀN THÀNH NHIỆM VỤ: ngày 25 tháng 11 năm 2008 V- CÁN BỘ HƯỚNG DẪN : TIẾN SĨ ĐẶNG VĂN VINH CÁN BỘ HƯỚNG DẪN CN BỘ MÔN QL CHUYÊN NGÀNH TS. Đặng Văn Vinh PGS TS Nguyễn Đình Huy - ii - LỜI CẢM ƠN Được học tập và nghiên cứu Toán ứng dụng ở bậc sau đại học tại Khoa khoa học ứng dụng Trường Đại Học Bách Khoa Tp.HCM là một hạnh phúc lớn lao đối với tôi. Nhờ khoá học này mà tôi được tập thể các thày cô Bộ môn Toán ứng dụng thuộc Khoa Khoa học ứng dụng tận tình dùi dắt, triyền đạt nhiều kiế thức khoa học cần thiết cho nghề nghiệp và cuộc sống. Tôi bày tỏ lòng biết ơn và cảm ơn sâu sắc tới Thầy Tiến sĩ Đặng Văn Vinh đã nhận lời hướng dẫn, hết lòng giục giã và tận tình chỉ dẫn tôi hoàn thành luận văn tốt nghiệp này. Tôi xin chân thành cảm ơn tập thể quý thầy cô trong Bộ môn Toán ứng dụng thuộc Khoa khoa học ứng dụng Trường Đại Học Bách Khoa Tp.HCM đã tạo điều kiện học tập tốt và truyền đạt nhiều kiến thức bổ ích trong suốt khoá học cao học. Tôi xin chia sẻ niềm vui và gởi lời cảm ơn đến gia đình tôi, những người thân đã luôn yêu thương nâng đỡ tôi tinh thần và giúp đỡ vật chất để tôi có nghị lực và điều kiện hoàn thành khoá học. Cuối cùng tôi xin gởi lời cảm ơn đến các bạn trong tập thể lớp cao học toán ứng dụng K2005 đã động viên, chia sẻ với tôi trong suốt khoá học. Lê Trung San - iii - TÓM TẮT Những bài toán kỹ thuật tính toán kế cấu, tính toán nhiệt, điện tử,... tương thích với các quá trình truyền nhiệt, truyền sóng, ... được mô tả bởi các phương trình vi phân đạo hàm riêng mà nghiệm giải tích thường rất khó tìm hoặc có thì biểu thức nghiệm quá phức tạp. Phương pháp phần tử hữu hạn nhằm tuyến tính hoá bài toán phi tuyến được áp dụng nhiều trong những năm gần đây. Cùng với sự phát triển vượt bậc của khoa học máy tính đã tạo thuận lợi cho những người tính toán có thể giải những bài toán lớn hơn với thời gian thực hiện nhanh hơn. Giải hệ phương trình tuyến tính Ax = b là một bước quan trọng trong phương pháp phần tử hữu hạn mà người thực hiện tính toán phải tiến hành. Các phương pháp giải trực tiếp Cramer, Gauss hay phân tích LU có nhiều hạn chế mà chủ yếu là sai số tích luỹ lớn không khắc phục được và độ phức tạp thời gian tính toán lớn. Nghiên cứu phương pháp lặp và phát triển hàm solver hệ Ax = b với khả năng kiểm soát sai số được thực hiện bởi luận văn này nhằm đóng góp một phần khắc phục sai số và giảm thời gian tính toán giúp người giải bài toán kỹ thuật có điều kiện tốt trong việc lựa chọn phương pháp xấp xỉ bậc cao và độ mịn của sự chia lưới thoả đáng. - iv - MỤC LỤC MỞ ĐẦU..............................................................................................................4 NHU CầU THựC TIễN CủA KHOA HọC TÍNH TOÁN.....................................................................4 MụC TIÊU CủA LUậN VĂN .........................................................................................................8 NộI DUNG THựC HIệN CủA LUậN VĂN: ......................................................................................8 CHƯƠNG 1 - PHƯƠNG PHÁP LẶP GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH....................................................................................................................9 I./ TÓM LƯỢC CÁC PHƯƠNG PHÁP GIẢI ĐÚNG ...........................................................10 II./ MỘT SỐ PHƯƠNG PHÁP LẶP .......................................................................................15 1. CHUẩN CủA VÉCTƠ VÀ MA TRậN...................................................................... 15 2. GIớI THIệU PHƯƠNG PHÁP LặP ......................................................................... 16 MộT Số KếT QUả TRÊN Dữ LIệU THử:....................................................................... 36 3. SO SÁNH THờI GIAN THựC HIệN GIữA CÁC THUậT TOÁN .................................... 37 CHƯƠNG 2: HỆ THƯA................................................................................. 40 1. Hệ THƯA .............................................................................................................................41 2. LƯU TRữ MA TRậN THƯA – GIảI PHAP TIN HọC[3].............................................................42 3. Đồ THị BIểU DIễN MA TRậN:................................................................................................44 CHƯƠNG 3: PHƯƠNG PHÁP PHầN Tử HữU HạN GIảI BÀI TOÁN CƠ HọC VậT RắN ................................................................................................... 48 I. MỘT SỐ KHÁI NIỆM CƠ BẢN VỀ CƠ HỌC VẬT RẮN BIẾN DẠNG (TRÍCH Từ [5]) 48 1. CÁC PHƯƠNG TRÌNH CÂN BằNG: (EQUATION OF INTERNAL EQUILIBRIUM)....... 48 2. QUAN Hệ GIữA BIếN DạNG – CHUYểN Vị: .......................................................... 49 3. CÁC PHƯƠNG TRÌNH LIÊN TụC CủA BIếN DạNG: ................................................ 51 -1- 4. ĐIềU KIệN BIÊN (BOUNDARY CONDITIONS) ..................................................... 52 5. CÁC PHƯƠNG TRÌNH VậT LÝ – QUAN Hệ GIữA ứNG SUấT VÀ BIếN DạNG – ĐịNH LUậT HOOKE ........................................................................................................ 52 II. PHƯƠNG PHÁP PHầN Tử HữU HạNGIảI BÀI TOÁN CƠ HọC VậT RắN.......................59 2.1. XÂY DựNG PHƯƠNG TRÌNH CƠ BảN................................................................. 61 2.2. CÁC CÔNG THứC NộI SUY ............................................................................... 63 2.4. CÁC PHầN Tử CƠ BảN ...................................................................................... 66 2.5. GHÉP NốI CÁC PHầN Tử - MA TRậN Độ CứNG TổNG THể: .................................... 70 III. CÁC BƯớC Để GIảI MộT BÀI TOÁN BằNG PHƯƠNG PHÁP PHầN Tử HữU HạN [6] 71 KếT LUậN CHƯƠNG 3: .........................................................................................................73 CHƯƠNG 4: CÁC ỨNG DỤNG ...................................................................... 74 BÀI TOÁN 1: ....................................................................................................................................... 74 BÀI TOÁN 2: ....................................................................................................................................... 85 BÀI TOÁN 3: GIÀN KHÔNG GIAN ................................................................................................. 107 KẾT LUẬN...................................................................................................... 109 HẠN CHẾ........................................................................................................ 109 HƯỚNG MỞ RỘNG....................................................................................... 109 PHỤ LỤC ........................................................................................................ 110 A. CODE CHƯƠNG TRÌNH MATLAB GIẢI BÀI TOÁN CƠ HỌC VẬT RẮN BIẾN DẠNG: ........................................................................................................................................................................... 110 B. CODE CHƯƠNG TRÌNH ANSYS GIẢI BÀI TOÁN CƠ HỌC VẬT RẮN BIẾN DẠNG:... 126 DANH SÁCH BẢNG .............................................................................................................133 DANH SÁCH HÌNH ẢNH.............................................................................. 134 TÀI LIỆU THAM KHẢO............................................................................... 135 -2- -3- MỞ ĐẦU Nhu cầu thực tiễn của khoa học tính toán Trong thực tiễn của khoa học tính toán nhằm giải quyết các bài toán thực tiễn có nhiều bài toán được mô tả bởi một hệ phương trình tuyến tính hay phi tuyến, thậm chí được mô tả bởi các phương trình vi phân hay phương trình vi phân đạo hàm riêng mà cấu trúc nghiệm thường rất phức tạp. Các bài toán như vậy thường gặp phải như quá trình lan truyền chất thải trong các môi trường không khí, nước, hay sự biến dạng của vật thể khi chịu tác động của ngoại lực mà tương thích với nó là quá trình truyền nhiệt, truyền sóng , … chẳng hạn trong cơ học, người ta cần giải bài toán cơ bản của lý thuyết đàn hồi là chuyển vị và ứng suất tại mọi điểm của vật thể dưới tải trọng tác dụng bên ngoài và các điều kiện biên cho trước. Ứng suất và biến dạng được quy định bởi phương trình vi phân đạo hàm riêng. Một ví dụ về bài toán 2D có phương trình chủ đạo được mô tả: ∂ 4φ ∂ 4φ ∂ 4φ + + =0 ∂x 4 ∂x 2∂y 2 ∂y 4 hay phương trình lan truyền chất tan có dạng: ∂c ∂c ∂c ∂c ∂  ∂c  ∂  ∂c  ∂  ∂c   +  D z  − λc + w +u + v + w =  Dx  +  D y ∂t ∂x ∂y ∂z ∂x  ∂x  ∂y  ∂y  ∂z  ∂z  Cho đến nay người ta chưa tìm được quy tắc chung để giải các phương trình vi phân đạo hàm riêng với nghiệm giải tích. Thường đưa ra phương pháp tìm nghiệm giải tích cho từng phương trình riêng biệt mà thực tiễn cho thấy cấu trúc nghiệm giải tích rất phức tạp (cũng chỉ giải được một số phương trình đơn giản) hoặc được biểu diễn dưới dạng tích phân mà việc lấy tích phân gặp không ít khó khăn. -4- Để giải quyết khó khăn nói trên, cách tiếp cận hiện nay là tuyến tính hóa các bài toán phi tuyến bằng các kỹ thuật khác nhau nhằm tìm nghiệm gần đúng của bài toán với sai số chấp nhận được (còn gọi là nghiệm yếu). Trong vài thập niên gần đây đã diễn ra nhiều sự thay đổi lớn về phương pháp nghiên cứu trong lĩnh vực tính toán, đặc biệt là các bài toán kỹ thuật. Máy tính với tốc độ xử lý ngày càng nhanh là một công cụ hỗ trợ tích cực cho việc tính toán. Để sử dụng máy tính cần phải xây dựng được các phương pháp tính toán tổng quát được mô tả bằng các công thức đơn giản, cô đọng. Các công thức này được biểu diễn bằng ngôn ngữ phù hợp với máy tính. Ma trận là một trong các ngôn ngữ diễn tả lí tưởng dưới dạng số. Nhờ khả năng tính toán với tốc độ cao của máy tính đã giúp khắc phục trở ngại về khối lượng tính toán của bài toán, giúp những người nghiên cứu tập trung lựa chọn, hoàn thiện các mô hình tính toán phản ánh tối đa các tính chất của bài toán cần giải quyết. Có 2 phương pháp rời rạc hóa bài toán thường được sử dụng hiện nay là phương pháp sai phân hữu hạn và phương pháp phần tử hữu hạn. Phương pháp sai phân hữu hạn dực trên sự rời rạc hóa toán học trong đó các đạo hàm được thay thế bằng các sai phân hữu hạn, còn phương pháp phần tử hữu hạn xây dựng trên cơ sở của sự rời rạc hóa vật lý. Trong phương pháp phần tử hữu hạn, vật thể liên tục được thay bởi các phần tử rời rạc có hình dáng đơn giản, chúng được nối với nhau bởi các điểm gọi là các nút. Các phần tử này vẫn giữ nguyên vật thể trong phạm vi của nó, nhưng có hình dáng đơn giản nên cho phép nghiên cứu dễ dàng hơn trên cơ sở một số luật phân bố. Trong quá trình tính toán bằng phương pháp phần tử hữu hạn xuất hiện một hệ phương trình tuyến tính Ax = b mà cấp của ma trận A phụ thuộc vào độ mịn của sự chia lưới hữu hạn. Một sơ đồ giải thuật cho bài toán tính toán sự biến dạng của cơ học vật rắn: -5- Bắt đầu Rời rạc hóa miền tính (chia lưới) Lắp ghép ma trận độ cứng toàn cục K Áp điều kiện biên và tải trọng F Giải hệ Kx = F Tính toán lượng biến dạng Kết quả của việc tính toán bằng phương pháp phần tử hữu hạn phụ thuộc vào nhiều yếu tố như kiểu chia lưới phần tử là thô hay mịn, phần tử được chọn bậc 1 (tam giác 3 nút) hay bậc cao. Tuy nhiên, thực tiễn cũng cho thấy vấn đề quan trọng lại là bộ solver hệ Ax = b với bài toán lớn, do làm tròn số ở bước tính trung gian nên cho kết quả cuối cùng bị sai số nên yêu cầu về bộ giải solver ma trận phải: - có sai số trong phạm vi cho phép. - thời gian tính toán chấp nhận được. - không quá phức tạp về thuật toán. Có 2 cách tiếp cận giải (solver) hệ Ax = b là phương pháp trực tiếp (direct solver) và phương pháp lặp (iteration solver). Phương pháp giải trực tiếp như Cramer, Gauss hay phân tích LU thường cho sai số lớn do ma trận A lớn nên sai số tích lũy khi làm tròn đáng kể, nhiều trường hợp sai số vượt khỏi phạm vi cho phép. -6- Hơn nữa, các phương pháp giải trực tiếp thường có độ phức tạp tính toán (tổng các phép toán sơ cấp: +, - , *, , …) lớn nên có thời gian tính toán lâu. Phương pháp lặp vì vậy được đề xuất sử dụng vào việc solver hệ Ax = b nhằm khắc phục phần nào các hạn chế mà phương pháp trực tiếp chưa giải quyết được. Đặc biệt trong nhiều bài toán kỹ thuật cho ma trận A là một ma trận chứa rất nhiều phần tử 0. Trong trường hợp này việc lưu trữ các phẩn tử bằng 0 là không cần thiết nên cần thiết nghiên cứu thêm các giải pháp cho việc lưu trữ ma trận A, các ma trận A có nhiều số 0 gọi là thưa (sparse). Tính thưa của ma trận cũng được xem xét nhằm tiết kiệm không gian lưu trữ. Những lí do nói trên cho biết sự cần thiết của việc nghiên cứu phương pháp lặp (interative method) để giải (solver) hệ Ax =b. Và cần thiết phải xem xét đến tính thưa của ma trận. -7- Mục tiêu của luận văn Nghiên cứu phương pháp lặp giải hệ phương trình tuyến tính ứng dụng trong các bài toán kỹ thuật. Có xem xét đến tính thưa của ma trận nhằm vào 2 mục tiêu chủ yếu: - Giải được hệ phương trình tuyến tính lớn với sai số chấp nhận được (kiểm soát sai số). - Giảm độ phức tạp tính toán để tăng tốc độ xử lí. - Tối ưu không gian lưu trữ để giải được với bài toán có kích thước lớn hơn. Nội dung thực hiện của luận văn: - Tổng kết sơ bộ về các phương pháp trực tiếp giải hệ phương trình tuyến tính thực Ax = b. - Nghiên cứu một số phương pháp lặp cơ bản giải hệ phương trình Ax=b. - Lập trình giải hệ Ax = b (coding) bằng ngôn ngữ Mathlab. - Nghiên cứu một vài giải pháp lưu trữ ma trận thưa. - Một số bài toán kỹ thuật về cơ học vật rắn biến dạng giải bằng phương pháp phần tử hữu hạn, sử dụng hàm để giải hệ Ax = b bằng phương pháp SOR. - Nghiên cứu sử dụng phần mềm ANSYS tính toán chuyển vị của bài toán cơ học vật rắn biến dạng để so sánh. -8- CHƯƠNG 1 - PHƯƠNG PHÁP LẶP GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH NỘI DUNG I./ TÓM LƯỢC CÁC PHƯƠNG PHÁP GIẢI ĐÚNG Sơ lược một số phương pháp trực tiếp giải hệ Ax=b, là các phương pháp cho lời giải sau hữu hạn bước.Các phương pháp được đề cập đến là: Cramer, Gauss, sơ đồ Gauss compact, phương pháp phần tử trội, phương pháp phân tích LU. II./ MỘT SỐ PHƯƠNG PHÁP LẶP Xem xét một số phương pháp lặp cơ bản giải gần đúng hệ phương trình tuyến tính thực và đánh giá những cải thiện của phương pháp này nhằm làm giảm độ phức tạp tính toán so với các phương pháp giải đúng. Tham khảo: [1]. Phương pháp số, Phạm Kỳ Anh, NXB Đại học Quốc Gia Hà Nội, 1997 [2]. Slide Bài giảng Phương pháp tính, TS Nguyễn Quốc Lân, Đại học Bách khoa TpHCM [3]. Yousef Saad. Iterative Methods For Sparse Linear Systems. -9- I./ TÓM LƯỢC CÁC PHƯƠNG PHÁP GIẢI ĐÚNG Ax = b ; A ∈ R nxn , b∈ R n Xét hệ: (1.1) Để tìm véctơ x trong phương trình (1.1) người ta phân loại 2 nhóm phương pháp là: Nhóm phương pháp trực tiếp, là các phương pháp cho nghiệm đúng sau một số hữu hạn bước. Nhóm phương pháp lặp, cho dãy nghiệm xấp xỉ x(m) hội tụ về nghiệm đúng x* khi m → ∞. Trong thực tế tính toán số thì đa số các bài toán khi giải đều nhận được nghiệm xấp xỉ kể cả giải bằng phương pháp trực tiếp. Sở dĩ như vậy vì khi tính toán, chúng ta phải thực hiện các phép toán cộng, trừ , nhân, chia trên các con số thập phân nên không tránh được việc làm tròn số. Ta nói phương pháp đúng có nghĩa là sai số phương pháp bằng 0, trong khi phương pháp lặp thì sai số phương pháp là số khác 0. Cả hai đều phải nhận sai số tính toán, là sai số khi làm tròn số. Trong phần I này, xin tóm lược một số phương pháp giải đúng hệ phương trình (1.1). Nếu Det ( A) ≠ 0 , quy tắc Cramer giải hệ (1) thể hiện bởi công thức viết dạng toạ độ là: xi = ∆i ; ∆ i = 1,..., n (1.2) Trong đó ∆ = Det ( A) , ∆i là định thức của ma trận nhận được từ A bằng cách thay cột i bởi cột b. Để tìm nghiệm theo công thức (1.2) ta phải tính n+1 định thức cấp n. Mỗi định thức có n! số hạng, mỗi số hạng có n thừa số, do vậy để tính mỗi số hạng phải thực hiện n-1 phép nhân. Như vậy, riêng số phép nhân phải thực hiện trong (1.2) là n!(n+1)(n-1). Công thức (1.2) đẹp về mặt lí thuyết, xong nó chỉ nên áp dụng cho việc giải các hệ có kích thước nhỏ. - 10 - Phương pháp Gauss cải thiện đáng kể về mặt độ phức tạp tính toán so với phương pháp Cramer. Hệ (1.1) viết lại dạng toạ độ: n ∑a ij x j = bi , n+1 i = 1,2,..., n (1.3) j =1 Phương pháp Gauss gồm 2 quá trình: Quá trình 1: Đưa hệ (1.3) về dạng tam giác trên  x1 + b12( 0) x2 + b13( 0) x3 + ... + b1(,0n)−1 x n−1 + b1(n0) x n = b1(,0n)+1  x 2 + b23(1) x3 + ... + b2(1,n) −1 x n−1 + b2(1n) x n = b2(1,n) +1   ...   xn −1 + bn( n−1−,2n) x n = bn( n−1−,2n)+1   xn = bn( n,n−+11)  Quá trình 2: Tìm từ hệ tam giác x n , x n−1 ,..., x1. Công thức tính toán trong quá trình 2 là: aij( k ) = aij( k −1) − aik( k −1) bkj( k −1) ; (i, j ≥ k ) ( k −1) kj b = akj( k −1) akk( k −1) ; ( j > k) (1.4) (1.5) Phương pháp Gauss thực hiện được nếu a kk( k −1) ≠ 0 , ∀k = 1,2,..., n ; trong đó a11( 0 ) = a11 . Khối lượng phép tính trong phương pháp Gauss (kể cả phép ∑ ): Quá trình 1: n(n+1) +(n-1)n +...+ 1.2 = (12 + 22 + ...+n2) + (1 + 2+ ...+n) = n (n + 1)( n + 2) . 3 Quá trình 2: n(n-1). Tổng số phép nhân, chia trong phương pháp Gauss là : N = - 11 - n 2 (n + 6n − 1) . 3 Phương pháp Gauss về cơ bản là tương đối đơn giản, dễ cho việc lập trình. Tuy vậy, thuật toán chỉ thực hiện được khi các phần tử a kk( k −1) ≠ 0 , ∀k = 1,2,..., n ; nếu phần tử a kk( k −1) ≈ 0 , phương pháp Gauss có thể cho kết quả không chính xác[1]. Trong phương pháp Gauss, các hệ số aij( k ) chỉ đóng vai trò bổ trợ. Dwyer Paul sử dụng sơ đồ sau gọi là sơ đồ Gauss compact để tránh việc tính toán và nhớ các hệ số aij( k ) : Đặt cik = aik( k −1) ; d kj = bkj( k −1) có được từ công thức (1.4) : aij( k ) = aij( k −1) − aik( k −1) bkj( k −1) = aij( k −1) − cik d kj = aij( k −2 ) − ci ,k −1d k −1, j − cik d kj = ... = aij − ci1d 1 j − ci 2 d 2 j − ... − cik d kj k aij( k ) = aij − ∑ ciυ dυj Vậy (1.6) υ =1 j −1 Tiếp theo, từ (1.6) suy ra cij = aij( j −1) = aij − ∑ ciυ dυj ( j < i ) . Sử dụng (1.5) được: υ =1 i −1 d ij = bij(i −1) = aij(i −1) a ( i −1) ii = aij − ∑ ciυ dυj υ =1 (1.7) cii Phương pháp phần tử trội xét ma trận mở rộng của hệ (1.1): ~ (0) A  a11 a12 ... a1n a1, n +1    = ... ... ... ... ...  a   n1 an 2 ... ann an , n +1  ~ Nói a pq là phần tử trội nếu a pq = max aij , khi đó hàng thứ p của ma trận A( 0 ) cũng 1≤ i , j ≤ n được gọi là hàng trội. Đặt mi = − aiq a pq ~ (i ≠ p ) . Lấy hàng p của ma trận A( 0 ) nhân với ~ mi rồi cộng với hàng i (i ≠ p), được ma trận mới A(1) . Tiếp tục quá trình trên được: ~ ~ ~ ~ A(1) , A( 2 ) , ..., A( n −1) . A( n −1) là ma trận hàng gồm có 2 phần tử cũng gọi là hàng trội. - 12 - ~ Để tìm xi, gom tất cả các hàng trội bắt đầu từ A( n −1) (đánh số lại nếu cần) sẽ được một hệ tam giác để tìm {xi }, i = 1,2,.., n . Phương pháp phần tử trội áp dụng được khi det(A) ≠ 0. Phương pháp này khắc phục được sự cố phải chia cho những số nhỏ a kk( k −1) ≈ 0 . Phương pháp phân tích nhân tử LU (Cholesky) Khi A là ma trận đối xứng A = AT, Tìm cách biểu diễn A dạng A = LU (1.8) trong đó U là ma trận tam giác trên (Upper triangular) uij = 0 với i>j, còn L là ma trận tam giác dưới (Lower triangular) lij= 0 với i 1) sau khi có y, tìm được x : xn = yn unn yi − xi = n ∑u ik k = i +1 uii xk , (i < n ) Ví dụ một phân tích ma trận A thành tích LU thực hiện bởi Mathlab : - 13 - Nhận xét rằng trong phương pháp phân tích LU, chỉ phải ghi nhớ một nửa ma trận A ; phép khử với những phần tử bằng 0 của A cho phép giải hệ có kích thước lớn hơn. Số phép tính trong phương pháp Cholesky[1] là: nhân : 1 3 ( n + 9n 2 + 2 n ) 6 cộng : 1 3 ( n + 6n 2 − 7 n ) 6 chia : n khai căn : n. * Thuật toán giải hệ AX = b bằng phương pháp phân tích LU gồm các bước: (1) Phân tích A = LU (2) Giải LY = b tìm Y (3) Giải UX = Y tìm X LU Algorithm. - 14 - II./ MỘT SỐ PHƯƠNG PHÁP LẶP 1. Chuẩn của véctơ và ma trận
Chuẩn của véctơ : Chuẩn của véctơ thực x là số thực xác định bởi ánh xạ n x → x trên R , thỏa 3 tính chất : x ≥ 0, ∀x ∈ R n , và x = 0 ⇔ x = 0 . i. k .x = k . x , ∀x ∈ R n , ∀k ∈ R. ii. x + y ≤ x + y , ∀x, y ∈ R n iii. Chuẩn được sử dụng nhiều trong số học tính toán là: 1 x p  n pp =  ∑ xi   i =1  p=1: x 1 = x1 + x2 + ... + xn ( 2 2 p= 2 : x 2 = x1 + x 2 + ... + xn p=∞: x ∞ chuẩn 1 ) 1 2 2 = max {xi } i =1, 2 ,..., n chuẩn 2 chuẩn vô cùng
Chuẩn của ma trận : Cho A là ma trận thực trong Mmxn(R). Ta định nghĩa chuẩn của ma trận A là ánh xạ: . : R mxn → R thoả các tính chất của chuẩn : (i). A ≥ 0, ∀A ∈ M mxn ( R ) , và A = 0 ⇔ A = 0 . (ii). kA = k A , ∀A ∈ M mxn ( R ), ∀k ∈ R. (iii). A + B ≤ A + B , ∀A, B ∈ M mxn ( R ). Khi A là ma trận dòng hay cột thì chuẩn của ma trận tương thích chuẩn của véctơ. Chuẩn ma trận được dùng nhiều trong số học tính toán là : n  A ∞ = max ∑ aij  i =1, 2 ,..., m  j =1  chuẩn vô cùng, - 15 -