pptts2
Chương 2. Hệ phương trình đại số tuyến tính
3(2/0.5/0.5x2)
Nội dung chính:
1. Phương pháp khử trực tiếp, phương pháp nhân tử LU
2. Hệ phương trình đường chéo; Phương pháp lặp
3. Độ chính xác và sự hội tụ
4. Phương pháp giảm trên liên tiếp
Đặt vấn đề
Xét việc giải hệ phương trình đại số tuyến tính n phương trình n ẩn:
(2.1)
trong đó: là các số đã biết, là các ẩn phải tìm.
Gọi
là ma trận hệ số của phương trình (2.1) và
là véc tơ vế phải và véc tơ nghiệm của hệ phương trình (2.1). Hệ (2.1) có dạng:
(2.2)
Hệ (2.2) có nghiệm duy nhất nếu ma trận hệ số A không suy biến, tức là:
Chứng minh:
(đpcm)
Hệ phương trình (2.2) được giải đúng theo quy tắc Crame như sau:
trong đó là định thức cấp n thu được từ bằng cách thay cột thứ i của bằng cột vế phải của hệ.
Khi đó, muốn giải hệ phương trình (2.2):
+ cần tính n + 1 định thức cấp n.
+ Để tính mỗi định thức cấp n cần phép cộng và phép nhân.
+ thực hiện n phép chia, theo công thức Crame.
Như vậy số phép tính tổng cộng:
Do đó khi n tăng, khối lượng tính theo qui tắc Crame tăng rất nhanh, đến mức không thực hiện được trong thực tế. Khi tính toán trên máy tính, nếu tất cả các phần tử của ma trận A khác 0, ta phải dùng ô nhớ để chứa các phần tử đó.
Vì vậy cần xây dựng phương pháp giải hệ phương trình đại số tuyến tính sao cho khi n lớn, khối lượng tính toán không quá lớn, có thể thực hiện được.
Hệ phương trình đại số tuyến tính gặp trong nhiều kiểu bài toán khác nhau: từ các mạng điện tử, xấp xỉ hàm thực nghiệm, các hệ thống các phương trình sai phân hữu hạn, phương pháp số giải các phương trình vi phân.
Hai phương pháp hệ thống giải:
1. Phương pháp trực tiếp: Phương pháp cho nghiệm đúng sau một số hữu hạn các phép tính sơ cấp.
2. Phương pháp lặp: Nghiệm đúng là giới hạn của một dẫy vô hạn những nghiệm gần đúng. Trong thực hành, buộc phải dừng lại ở một cụ thể và xem là nghiệm gần đúng, do đó ta chỉ nhận được nghiệm gần đúng với một sai số có thể ước lượng được.
Phương pháp trực tiếp thường áp dụng khi một hoặc nhiều điều kiện sau:
1. Số phương trình bé hơn 100
2. Đa số các hệ số khác không
3. Hệ không phải dạng đường chéo trội
4. Hệ trong điều kiện xấu (Ill conditioned)
Phương pháp lặp thường được dùng khi: ma trận hệ số A “thưa” (những phần tử khác không ít và thường phân bố ở lân cận đường chéo chính và cấp của ma trận lớn.
Phương pháp lặp nói chung là phân kỳ trừ khi hệ có dạng đường chéo trội.
Sơ đồ nội dung chính của Chương 2
§1.Các tính chất cơ bản của ma trận và định thức
1.1.Định nghĩa
Ma trận: là mảng chữ nhật các phần tử được sắp xếp thứ tự theo các dòng và các cột. Mỗi phần tử của ma trận là khác nhau và tách biệt. Chúng có thể là số hay biểu thức hình thức.
Ký hiệu ma trận: (chữ cái in)
là phần tử dòng i cột j của ma trận A.
Ma trận n dòng, m cột được hiểu là ma trận cấp .
Véc tơ là ma trận một dòng hay một cột.
Véc tơ cột là ma trận cấp , kí hiệu
Véc tơ dòng là ma trận cấp , ký hiệu:
Véc tơ đơn vị là véc tơ có độ dài bằng đơn vị (1):
Ma trận vuông là ma trận mà số hàng (n) bằng số cột (m) : m = n. Ta quan tâm chủ yếu đến ma trận vuông.
Đường chéo chính của ma trận vuông A là tập các phần tử .
Đường chéo phụ của ma trận vuông A là tập các phần tử .
Ma trận đường chéo D là ma trận vuông mà tất cả các phần tử đều bằng không trừ các phần tử trên đường chéo chính
Ma trận đơn vị I: ma trận đường chéo mà các phần tử trên đường chéo bằng 1.
Ma trận tam giác trên là ma trận vuông U có tất cả các phần tử nằm dưới đường chéo chính bằng không
Ma trận tam giác dưới là ma trận vuông U có tất cả các phần tử nằm trên đường chéo chính bằng không
Ma trận ba đường chéo là ma trận vuông mà trong đó tất cả các phần tử không nằm trên đường chéo chính, hoặc không trên hai đường chéo bao quanh đường chéo chính đều bằng không.
Ma trận băng là ma trận có tất cả các phần tử bằng 0, trừ các phần tử nằm trên các đường chéo cụ thể.
Ma trận chuyển vị của ma trận cấp là ma trận mà:
Ma trận vuông A là đối xứng nếu
Ma trận thưa là ma trận mà hầu mọi các phần tử là bằng không. Đa số các ma trận trong các ứng dụng khoa học và kỹ thuật là ma trận thưa.
Ma trận đường chéo trội nếu giá trị tuyệt đối của từng phần tử trên đường chéo chính là bằng hoặc lớn hơn tổng các giá trị tuyệt đối của tất cả các phần tử khác trên dòng đó, đồng thời sự lớn hơn xảy ra ở dòng cuối cùng.
1.2.Đại số ma trận cơ bản
Cộng, trừ ma trận: A, B là hai ma trận cùng cỡ
Các tính chất của phép cộng ma trận
Nhân ma trận:
Điều kiện nhân ma trận: số cột của ma trận bị nhân bằng số hàng của ma trận nhân.
Các tính chất của phép nhân ma trận:
Nói chung, giả thiết phép nhân là được phép, thì:
Nghịch đảo ma trận
Ma trận vuông được gọi là ma trận nghịch đảo (ngược) của ma trận nếu:
Ký hiệu
Phân tích ma trận ra thừa số là biểu diễn ma trận thành tích hai ma trận khác:
Ma trận con là ma trận chứa nhóm các phần tử của ma trận khác.
1.3.Hệ phương trình đại số tuyến tính
Có dạng ma trận:
ở đây:
A : ma trận hệ số, b véc tơ vế phải.
Có 3 phép biến đổi (dòng – ma trận) dùng khi giải hệ phương trình đại số tuyến tính, không làm thay đổi nghiệm của hệ phương trình đại số tuyến tính.
1. Phương trình bất kỳ (dòng) có thể được nhân với hằng số khác không (phép tỷ lệ - scaling).
2. Trật tự của các phương trình có thể trao đổi cho nhau (phép tráo đổi -pivoting)
3. Phương trình bất kỳ (dòng) có thể được thay bởi tổ hợp tuyến tính trọng số của phương trình (dòng) đó với phương trình khác bất kỳ (phép loại trừ -elimination)
1.4. Định thức
Định thức của ma trận vuông A cấp được ký hiệu bởi:
Nói chung, định thức của ma trận cấp là tổng của tất cả các tích có thể bằng cách chọn một và chỉ một phần tử trên mỗi hàng và mỗi cột của định thức với dấu cộng hay trừ xác định bởi số các hoán vị của các phần tử dòng và cột.
Định thức của ma trận 2 x 2: tích các phần tử trên đường chéo chính trừ đi tích các phần tử trên đường chéo phụ.
Định thức của ma trận 3 x 3: là tổng của 6 phần tử tích bộ ba, nhận được từ định thức ghép (định thức ban đầu, ghép thêm hai cột đầu tiên của nó vào bên phải). Tính định thức
(Qui tắc đường chéo tính định thức 2 x 2, 3x3)
Qui tắc chung để tính định thức là biểu diễn theo các định thức con hay các phần phụ đại số.
Tính định thức theo dòng i bất kỳ
trong đó là định thức của ma trận con cấp của ma trận A cấp nhận được bằng cách xóa đi dòng i và cột j.
là phần phụ đại số của phần tử .
Tính định thức theo cột j bất kỳ
Khối lượng tính toán: Lấy tổng của n! tích, mỗi tích có n phần tử.
Định thức cấp :
Lấy tổng của 10! tích (10! = 3.628.800), mỗi tích có 9 phép nhân (tích của 10 phần tử). Tổng cộng có 3.628.800 x 9 = 32.659.200 phép nhân và (10! – 1) = 3.627.999 phép cộng, chưa kể đến việc tính để giữ dấu.
Trong thực hành, việc tính định thức theo phần phụ đại số ít được dùng, trừ khi với các định thức cấp rất bé.
Nếu định thức của ma trận bằng không, ma trận được gọi là ma trận suy biến.
Ma trận không suy biến là ma trận có định thức khác không.
Nếu ma trận có dòng (cột) có tất cả các phần tử bằng không thì ma trận là suy biến.
Ma trận tam giác trên (tam giác dưới) có định thức là tích các phần tử trên đường chéo chính.
§2.Các phương pháp khử trực tiếp
2.1. Qui tắc Crame
Theo quy tắc Crame nghiệm của hệ n phương trình đại số tuyến tính: được cho bởi công thức:
(2.1)
ở đây là ma trận nhận được khi thay cột j của ma trận bằng véc tơ cột b.
Hệ phương trình đại số tuyến tính có nghiệm duy nhất khi và chỉ khi ma trận hệ số là không suy biến.
Khối lượng tính toán:
Số phép nhân (và chia) N ,bắt buộc cho phương pháp định thức con là
Với n = 10, N = 360.000.000. Khối lượng tính khổng lồ.
Với n = 100, N =10157. Thật khó thực hiện tính toán.
Chú ý: Khi giải hệ phương trình đại số tuyến tính, có 4 khả năng nghiệm:
1. Nghiệm tồn tại và duy nhất
2. Không có nghiệm
3. Có vô số nghiệm
4. Nghiệm tầm thường x = 0, cho hệ thuần nhất b = 0
Minh họa đồ thị: Xét hệ hai phương trình
Mỗi phương trình biểu diễn bởi đường thẳng trong hệ tọa độ Đề các xOy:
Ví dụ 2.1: Giải hệ phương trình
Áp dụng qui tắc Crame:
Vậy
Bài tập về nhà: Giải hệ trên khi tính định thức theo 2 cách: qui tắc đường chéo và theo phần phụ đại số
2.2. Các phương pháp khử đơn, khử Gauss, khử Gauss-Jordan, Ma trận ngược
2.2.1.Phương pháp khử
Xét hệ 3 phương trình:
Giảiphương trình (2.2a) đối với x1, giả sử a11 ≠ 0 (a11 gọi là phần tử trụ thứ nhất):
Thay biểu diễn của x1 vào phương trình (2.2b), nó trở thành:
Tương tự, phương trình (2.2c) trở thành;
Các phương trình (2.5) có thể viết lại dưới dạng:
trong đó
Suy rộng biểu diễn hệ số này cho hệ n phương trình: i, j =1,2,…,n.
Trong lập trình tính toán, các hệ số mới được lưu trữ ở vị trí của các hệ số ban đầu, vì các hệ số ban đầu đó không cần dùng nữa.
Tiếp theo, giải phương trình (2.6a) theo x2, giả sử (a22 gọi là phần tử trụ thứ hai):
Thế (2.9) vào phương trình (2.6b), nhận được:
trong đó
Suy rộng cho hệ n phương trình i, j =1,2,…,n.
Như vậy hệ (2.2) tương đương với hệ:
Quá trình này được gọi là quá trình khử (Elimination Process)
Để giải hệ tiếp tục ta thực hiện quá trình thế ngược (Back Substitution):
Từ các phương trình (2.13), giải phương trình cuối cùng và thế ngược về phương trình đầu, ta có công thức xác định nghiệm cần tìm:
Tổng quát hóa: thiết lập bảng tính tương ứng.
Kí hiệu tiếp theo ở dòng thứ i tức là: phương trình thứ i được thay bởi tổ hợp tuyến tính của phương trình thứ i cộng với k lần phương trình thứ j. Hệ số k được chọn để khử hệ số thứ nhất trong phương trình thứ i. Việc khử các hệ số được thực hiện theo trình tự nhất định, sao cho mỗi lần một hệ số được khử, các phép toán sau không đưa vào giá trị khác không cho hệ số đó. Như vậy tất cả các hệ số dưới đường chéo chính ở cột thứ nhất được khử bởi các tổ hợp tuyến tính với phương trình thứ nhất. Sau đó tất cả các hệ số nằm dưới đường chéo chính ở cột thứ hai được khử bởi các tổ hợp tuyến tính với phương trình thứ hai mới. Quá trình khử này được tiếp tục cho đến khi tất các phần tử nằm dưới đường chéo chính được khử. Kết thúc quá trình khử khi phương trình cuối cùng chỉ chứa một biến xn, và có thể giải được nó ngay. Dùng giá trị này, phương trình thứ (n -1) rút gọn chỉ chứa một ẩn chưa biết, xn-1 , mà có thể xác định nó. Quá trình này được gọi là thế ngược và nó được lặp lại đến khi tìm được x1.
Điều kiện để thực hiện được phương pháp khử là: các phần tử trụ phải khác không.
Số các phép nhân và chia trong phương pháp khử là xấp xỉ bởi:
Theo phương pháp Qui tắc Crame:
Như vậy khối lượng tính toán của phương pháp khử là ít hơn nhiều so với phương pháp giải theo qui tắc Crame.
Ví dụ 2.2: Giải hệ phương trình sau bằng phương pháp khử
Khử các phần tử dưới đường chéo chính, từng cột, như dưới đây:
Phương pháp khử chứa các thao tác ma trận hệ số A và véc tơ khác không b. Véc tơ nghiệm x cố định.
2.2.2.Phương pháp khử đơn
Phương pháp khử đơn là phương pháp khử mà các thao tác khử thực hiện trên ma trận hệ số A và véc tơ vế phải b.
1. Ghép thêm vào bên phải ma trận A, véc tơ vế phải b.
2. Thực hiện các phép toán khử theo dòng của ma trận A ghép thêm.
3. Thực hiện thế ngược để nhận được nghiệm.
Nội dung phương pháp thể hiện qua ví dụ.
Ví dụ 2.3. Giải hệ (2.2) bằng phương pháp khử đơn
Phương pháp khử đơn còn áp dụng được khi giải nhiều hệ phương trình đại số tuyến tính có các vế phải khác nhau.
Phương pháp khử đơn không thực hiện được khi hoặc
+ Trụ đầu tiên bằng không
+ Phần tử bất kỳ aii bằng không (trên đường chéo chính)
+ Các phần tử trên đường chéo chính của ma trận ban đầu khác không nhưng chúng có thể sẽ bằng không trong quá trình khử.
Trong quá trình khử, để tránh giá trị không trên đường chéo chính cần tráo đổi các phương trình (các dòng) hay các biến (các cột) trước khi mỗi bước khử được thực hiện cho phần tử biên độ lớn nhất nằm trên đường chéo.
Các phần tử trên đường chéo chính được gọi là phần tử trụ (phần tử lớn nhất về trị tuyệt đối trên cột chứa nó).
Việc hoán vị các hàng để có được phần tử trụ được gọi là phép trụ (pivoting)
Phép trụ loại bỏ các giá trị không ở các phần tử trụ trong quá trình khử.
Ví dụ 2.4. Dùng phương pháp khử với phép trụ giải hệ phương trình
Áp dụng quá trình khử đơn bởi ma trận ghép A và b.
Phần tử trụ thứ nhất bằng không, do vậy phép trụ là bắt buộc.
Số lớn nhất (về biên độ) ở cột 1 dưới phần tử trụ có ở dòng 2. Như vậy khi hoán vị dòng 1 và dòng 2 và thực hiện tuần tự thao tác dòng, ta có:
Dù phần tử trụ ở hàng thứ hai khác không, nhưng nó không phải là phần tử lớn nhất trong cột thứ hai ngay dưới phần tử trụ. Như vậy phép trụ lại được thực hiện. Chú ý rằng phép trụ chỉ được thực hiện trên các dòng phía dưới phần tử trụ.
Phép tỷ lệ
Phép tỷ lệ được thực hiện bằng cách chia các phần tử của mỗi dòng (gồm cả véc tơ b) cho phần tử lớn nhất trong dòng đó (trừ véc tơ b).
Phép tỷ lệ cần dùng khi các biên độ của các phần tử của một hay nhiều phương trình khác biệt khá nhiều so với biên độ của các phần tử của các phương trình khác. Sau phép tỷ lệ, phép trụ được thực hiện sẽ giảm được sai số làm tròn
2.2.3. Phương pháp khử Gauss
Phương pháp khử không thực hiện được nếu các phần tử trụ bằng không.
Phương pháp khử có thể làm giảm độ chính xác của nghiệm khi mà: có một vài phần tử trụ có trị tuyệt đối rất nhỏ so với các phần tử còn lại trong cùng hàng thì phép chia phần tử đó cho phần tử trụ, sai số làm tròn sẽ lớn.
Để khắc phục 2 hạn chế trên dùng phương pháp khử có tìm trụ lớn nhất (được gọi là phương pháp khử Gauss).
Quá trình khử bao gồm các phép toán tỷ lệ hóa và phép trụ tạo nên phép khử Gauss.
Nội dung phương pháp khử Gaus:
Khi khử x1, trong sơ đồ khử đơn, chọn trụ thứ nhất là số lớn nhất về trị tuyệt đối trong n số là hệ số của x1. Tiếp đó hoán vị hàng chứa trụ thứ nhất với hàng thứ nhất để trụ thứ nhất nằm ở hàng 1 cột 1 của sơ đồ khử. Quá trình khử được tiến hành đối với x1.
Khi khử x2, trong sơ đồ khử đơn, chọn trụ thứ hai là số lớn nhất về trị tuyệt đối trong (n - 1) số là hệ số của x2, trừ hệ số của x2 ở hàng đầu tiên. Tiếp đó hoán vị hàng chứa trụ thứ hai với hàng chứa phần tử để trụ thứ hai nằm ở hàng 1 cột 1 của ma trận trung gian ( là ma trận A khi bỏ đi hàng 1, và cột 1). Quá trình khử được tiến hành đối với x2.
Khi khử x3, trong sơ đồ khử đơn, chọn trụ thứ 3 là số lớn nhất về trị tuyệt đối trong (n -2) số là hệ số của x3, trừ các hệ số của x3 ở hai hàng đầu. Tiếp đó hoán vị hàng chứa trụ thứ ba với hàng chứa phần tử để trụ thứ ba nằm ở hàng 1 cột 1 của ma trận trung gian ( là ma trận khi bỏ đi hàng 1, và cột 1). Quá trình khử được tiến hành đối với x3.
Thực hiện tiếp các bước trên cho các biến .
Ví dụ 2.4. Giải hệ sau bằng phương pháp khử Gauss
Tỷ lệ xích: Dùng tỷ lệ xích là để giảm sai số làm tròn xuất hiện khi biên độ của một hay nhiều hệ số lớn hơn rất nhiều so với biên độ của các hệ số còn lại khác.
Tỷ lệ xích được thực hiện bằng cách chia các phần tử trên mỗi dòng, kể cả véc tơ b cho phần tử lớn nhất trong dòng. Sau đó mới bắt đầu khử.
Ví dụ 2.5: Làm rõ sự giảm sai số làm tròn khi giải hệ sau
Nghiệm đúng tìm được theo qui tắc Crame:
Giải theo phương pháp lặp không dùng tỷ lệ xích:
Giải theo phương pháp lặp với tỷ lệ xích:
Nghiệm này gần nghiệm đúng hơn.
Thủ tục khử Gauss, có thể dùng cho lập trình trên máy tính số:
1. Ghép bên phải ma trận A véc tơ vế phải b (hoặc m véc tơ vế phải)
2. Nếu có thể, tỷ lệ hóa các dòng của ma trận ghép A
3. Tìm phần tử biên độ lớn nhất (chính ,trụ) ở cột đầu tiên, phần tử chính thứ nhất và đổi dòng để đưa phần tử chính đó vào vị trí khử a11. Bước này được hoàn thành khi bằng cách thay đổi các phần tử tương ứng của véc tơ thứ tự.
4. Áp dụng phép khử cho các dòng 2 đến n để đưa tạo ra 0 trong cột thứ nhất đối với các phần tử nằm dưới phần tử chính thứ nhất. Tính các phần tử trong mỗi cột, từ 2 đến (n + m) cho dòng 2 đến n và lưu trữ tại vị trí của các phần tử ban đầu theo công thức
(2.15)
5. Lặp lại bước 3 và 4 cho các dòng 3 đến n. Kết thúc bước này ma trận A ban đầu được đưa về dạng tam giác trên.
6. Giải x khi dùng phép thế ngược. Nếu có nhiều hơn một véc tơ b, giải các véc tơ x tương ứng cùng lúc theo công thức:
(2.16)
2.2.4.Phương pháp khử Gauss - Jordan
Phương pháp khử Gauss - Jordan là phương pháp khử Gauss, sao cho Ma trận hệ số A được biến đổi thành ma trận đường chéo. Các dòng thường được thừa số hóa để nhận được phần tử đường chéo là 1. Khi đó ma trận A được biến đổi thành ma trận đơn vị I và véc tơ biến đổi b là véc tơ nghiệm.
Có thể áp dụng phương pháp khử Gauss – Jordan với nhiều véc tơ vế phải.
Số phép nhân và chia trong phép khử Gauss – Jordan, tính gần đúng theo công thức:
Khối lượng tính toán này lớn hơn khoảng 50% so với phương pháp khử Gauss.
Ví dụ 2. 6. Dùng phương pháp khử Gauss – Jordan, giải hệ
Chia dòng 1 cho 5 để nhận được a11 = 1
Chia dòng 2 cho – 0.6 để được a22 = 1, sau đó áp dụng thu gọn dòng cả trên và dưới dòng 2
Chia tỷ lệ dòng 3 để được a33 = 1, sau đó áp dụng rút gọn dòng 2
Phương pháp khử Gauss – Jordan thường dùng để nhận được ma trận ngược.
Thủ tục tính số cho phương pháp khử Gauss-Jordan:
1. Ghép ma trận đơn vị vào bên phải ma trận . Thực hiện phép khử Gauss với ma trận ghép
2. Nếu có thể, tỷ lệ hóa các dòng của ma trận ghép
3. Tìm phần tử biên độ lớn nhất (chính ,trụ) ở cột đầu tiên, phần tử chính thứ nhất và đổi dòng để đưa phần tử chính đó vào vị trí khử a11. Phần tử chính được tỷ lệ hóa về 1 khi chia tất cả các phần tử của dòng cho chính phần tử chính.
4. Áp dụng phép khử cho các dòng 2 đến n để đưa tạo ra 0 trong cột thứ nhất đối với các phần tử nằm dưới phần tử chính thứ nhất. Tính các phần tử trong mỗi cột, từ 2 đến (n + m) cho dòng 2 đến n và lưu trữ tại vị trí của các phần tử ban đầu theo công thức
5. Lặp lại bước 3 và 4 để khử các phần tử ở trên và dưới phần tử chính. Kết thúc bước này ma trận A ban đầu được đưa về đơn vị I và ma trận đơn vị I ban đầu được biến đổi thành ma trận ngược .
Ví dụ 2.7. Tìm ma trận ngược bằng phép khử Gauss-Jordan cho ma trận
Áp dụng phép khử Gauss-Jordan, ta nhận được
Bài tập về nhà: Thủ tục khử Gauss – Jordan (lập trình được) (?)
2.2.5.Phương pháp ma trận ngược
Tìm ma trận ngược theo phương pháp Gauss – Jordan.
Nghiệm cần tìm xác định bởi
2.2.6.Tính định thức
Bằng kỹ thuật tỷ lệ hóa, khử, có thể đưa ma trận A về dạng đường chéo. Sau đó định thức được tính bằng tích các phần tử trên đường chéo chính.
Ví dụ 2.7: Tính định thức theo phương pháp khử
Tỷ lệ hóa ma trận:
Các hệ phương trình điều kiện xấu (Ill-conditioned Systems ò Equations)
Khi hệ phương trình đại số tuyến tính là suy biến (định thức của ma trận hệ số bằng không), đó là giới hạn trên của điều kiện xấu.
Thể hiện của điều kiện xấu: định thức của ma trận rất bé.
Trong hệ điều kiện xấu, sai số làm tròn trong thiết bị tính toán có thể loại bỏ hoàn toàn độ chính xác của nghiệm.
Để làm giảm thiểu điều kiện xấu, có thể:
1. Dùng phép tỷ lệ hóa hay phép khử để giảm sai số làm tròn. Thường dùng phép khử dòng.
2. Dùng độ chính xác Double cho các phép toán số học trên máy tính để tăng số chữ số có nghĩa.
Không có cách để tránh hiện tượng hệ yếu.
§3.Phương pháp nhân tử LU
3.1.Định nghĩa nhân tử LU
Nhân tử LU là phép biến đổi A thành tích một ma trận tam giác dưới (Low triangular, L ) và một ma trận tam giác trên (Upper Triangular, U).
Phân tích LU dùng để giảm bớt khối lượng tính toán trong phép khử Gauss khi xét với nhiều véc tơ vế phải b.
Phương pháp Doolittle: là phân tích LU sao cho tất cả các phần tử trên đường chéo chính của ma trận tam giác dưới L có giá trị bằng 1.
Phương pháp Crout: là phân tích LU sao cho tất cả các phần tử trên đường chéo chính của ma trận tam giác trên U có giá trị bằng 1.
Phương pháp Cholesky: là phân tích LU sao cho
Xét hệ tuyến tính và .
Đặt , suy ra:
(3.1)
và:
(3.2)
Do L là ma trận tam giác dưới, phương trình cho phép giải b’ qua b khi dùng phép thế thuận.
Do U là ma trận tam giác trên, phương trình cho phép giải ẩn x qua b’ khi dùng phép thế ngược.
3.2. Phương pháp Doolittle
Trong phương pháp Doolittle, ma trận U là ma trận tam giác trên nhận được bằng phép khử Gauss; Ma trận L là ma trận tam giác dưới chứa các nhân tử trong quá trình khử Gauss như các phần tử nằm dưới đường chéo chính còn các phần tử trên đường chéo chính có giá trị là 1.
Khi L đã được xác định, giải phương trình với ẩn là b’ nhờ phép thế thuận.
Khi U đã được xác định, giải phương trình nhờ phép thế ngược nhận ẩn x cần tìm.
Ví dụ 3.1. Bằng phương pháp Doolittle, giải hệ phương trình
Xác định các ma trận L và U.
U là ma trận tam giác trên xác định bởi phép khử Gauss.
Ma trận L, một cách đơn giản, chứa các nhân tử trong phép khử biến đổi A thành U, có dạng:
Với véc tơ cột thứ nhất
Phương trình xác định b’, có dạng
Thực hiện phép thế thuận, ta được:
Véc tơ b’ thỏa mãn phương trình , tức là:
Thực hiện phép thế ngược, ta có
Với véc tơ vế phải thứ hai, , ta nhận được:
Lập trình PC:
1. Ở mỗi bước khử, khi các dòng của ma trận A được:
+ tỷ lệ hóa thì các hệ số tỷ lệ lưu giữ như các phần tử của véc tơ tỷ lệ S.
+ hoán vị, trật tự các dòng được lưu giữ trong véc tơ thứ tự O.
2. Véc tơ vế phải mới được xét, đầu tiên lấy tỷ lệ theo các phần tử của véc tơ S, sau đó xử lý một cách thứ tự tương ứng với các phần tử của véc tơ O.
Tiện lợi chính của phép phân tích LU là giải hệ phương trình đại số tuyến tính với nhiều vế phải khác nhau.
Khối lượng tính toán: Các phép nhân và phép chia bắt buộc:
+ Cho phương pháp khử Gauss:
+ Cho các phép thế thuận để giải phương trình
+ Cho các phép thế ngược khi giải phương trình
Tổng số các phép toán nhân và chia khi phân tích LU là bé hơn nhiều so với phương pháp khử Gauss nhất là đối với hệ lớn.
Các bước thực hiện của phương pháp Doolittle:
1. Định nghĩa véc tơ tỷ lệ và véc tơ thứ tự
2. Thực hiện các bước 3 đến bước 5 của phương pháp khử Gauss. Lưu giữ các hệ số tỷ lệ trong véc tơ S và thông tin hoán vị hàng trong véc tơ thứ tự O. Lưu giữ các nhân tử khử dòng ở vị trí của các phần tử đã được khử. Kết quả của bước này là các ma trận L và U xác định.
3. Nếu dùng phép tỷ lệ, tỷ lệ hóa véc tơ b khi dùng các hệ số tỷ lệ trong véc tơ tỷ lệ S.
4. Đặt lại trật tự véc tơ b (chưa / đã được tỷ lệ hóa) theo trình tự đã mô tả trong véc tơ thứ tự O.
5. Tính véc tơ b’ khi dùng phép thế thuận:
(3.3)
6. Tính véc tơ nghiệm x khi dùng phép thế ngược:
(3.4)
3.3.Phương pháp Crout
Phương pháp Crout, trong đó ma trận U có các phần tử trên đường chéo chính bằng 1, tương tự phương pháp Doolittle. Các ma trận L, U nhận được trong quá trình phân tích A = LU.
Công thức xác định:
Phương pháp Doolittle là sự cải tiến dễ làm của phương pháp khử Gauss.
Phương pháp Crout việc lập trình thuận lợi hơn.
§4.Các hệ phương trình đường chéo
4.1.Thuật toán Thomat
Các hệ đường chéo là dạng đặc biệt của phương trình đại số tuyến tính. Các thuật toán trực tiếp giải các hệ đường chéo cần được nghiên cứu để đặc biệt tăng hiệu quả về mặt thời gian tính và không gian lưu trữ.
Thuật toán Thomat (1949) được đặc biệt chú ý.
Các hệ đường chéo có kích thước lớn xuất hiện trong một số lĩnh vực, đặc biệt khi giải số các hệ phương trình sai phân.
Thuật toán Thomat:
Thuật toán Thomat là áp dụng phép khử Gauss cho ma trận hệ đường chéo, với thay đổi thủ tục để loại bỏ tất cả các phép toán đối với giá trị không.
Xét phương trình ma trận:
(4.1)
ở đây ma trận T có dạng đường chéo.
Ma trận ghép của (4.1):
Tất cả các phần tử ở cột 1, dưới dòng 2 đều bằng 0, chỉ có một phần tử cần được khử là . Thay thế dòng 2 bởi . Dòng 2 trở thành
Tương tự ở cột 2 cũng chỉ có một phần tử cần khử ; cột 3 cũng chỉ có một phần tử cần khử , …
Phần tử đã khử, tự nó không cần để tính toán. Vị trí của phần tử đã được khử dùng để lưu các nhân tử khử để dùng như trong phương pháp nhân tử LU.
Trên mỗi dòng, chỉ các phần tử trên đường chéo chính và các thành phần tương ứng của véc tơ b bị ảnh hưởng trong phép khử. Như vậy bước khử chỉ gồm 2n phép nhân để biến T thành ma trận tam giác trên.
Ma trận đường chéo T cỡ được lưu trữ như ma trận cỡ không cần lưu trữ các giá trị không.
Để đơn giản ma trận đường chéo T được lưu giữ bởi 3 véc tơ cột . Trong đó
(4.2a)
(các phần tử ở dưới đường chéo chính của T)
(4.2b)
(các phần tử ở đường chéo chính của T)
(4.2c)
(các phần tử ở trên đường chéo chính của T)
Giải (4.1) theo phương pháp khử, với qui ước (4.2), ta có:
trong đó:
trong đó:
và véc tơ vế phải trở thành:
Quá trình này tiếp tục đến khi được khử khỏi dòng n.
Dòng đầu tiên của ma trận T không thay đổi.
Tất cả các phần tử của được chuyển thành 0.
Các nhân tử khử dòng được lưu giữ ở vị trí của các phần tử của để dùng sau trong phương pháp nhân tử LU. Các phần tử ở phía trên các phần tử của u đều bằng 0, không có phần tử nào của u thay đổi, vì vậy chúng không cần tính. Như vậy chỉ các phần tử đường chéo, d, và véc tơ vế phải, b, cần tính.
Ma trận tam giác T được biến đổi thành:
(4.5)
Theo (4.5), qui trình tính toán véc tơ b khi rút gọn ma trận T được thực hiện khi dùng các nhân tử đặt ở vị trí của véc tơ . Do đó quá trình này chính là phương pháp nhân tử LU với:
và
(4.6)
Từ Ux = b’, ta nhận được nghiệm cần tìm qua phép thế ngược:
(4.7)
Các công thức (4.2), (4.4) và (4.7) tạo nên các bước tính toán của thuật toán Thomat như sau:
1. Sắp xếp các phần tử của ma trận trong ma trận cỡ :
2. Các công thức (4.4) và (4.7) trở thành:
Khối lượng tính toán:
Số phép nhân bắt buộc trong bước khử:
Số phép nhân và chia bắt buộc trong bước thế ngược:
Số phép nhân và chia tổng cộng:
Nếu phương trình với nhiều vế phải, chỉ phần thế ngược được thực hiện lại.
Các bước thực hiện thuận toán:
1. Lưu giữ ma trận đường chéo T cỡ trong 3 véc tơ cột . Vế phải trong véc tơ cột b.
2. Tính theo công thức
(lưu các nhân tử ở vị trí của )
3. Tính véc tơ b’ từ:
4. Tính véc tơ nghiệm x bằng phép thế ngược:
4.2.Hệ phương trình đường chéo khối (SV tự đọc, Tham khảo)
Trong thuật toán, các phần tử tham gia đều là đại lượng vô hướng.
Khi giải số hệ phương trình vi phân, dùng phương pháp sai phân, ta thường gặp bài toán giải hệ phương trình đại số tuyến tính với ma trận hệ số, véc tơ vế phải, véc tơ nghiệm có các phần tử là các ma trận con.
Hệ phương trình đường chéo khối có dạng:
(4.10)
hay
trong đó:
(1) là các ma trận vuông cấp
(2) là các véc tơ cột .
và
Phương trình (4.10) có thể được giải theo phương pháp Thomat. Các phép toán đối với các số hạng là vô hướng được thay bởi phép cộng, trừ và nhân ma trận.
Giả sử . Ta có:
Các bước giải:
(1). Dùng phương pháp nhân tử, phân tích
(2). Tìm bằng phép thế thuận
(3). Tìm bằng phép thế ngược
Gọi , ma trận đơn vị cấp , nằm trên đường chéo chính, là các ma trận khối đường chéo chính.
Nếu , và giả sử
(4.11)
(là ma trận nhận được từ các ma trận hệ số trong phép khử Gauss.)
thì theo phép nhân ma trận, ta có:
(4.12)
(4.13)
Tổng quát, ta có phương trình lặp:
(4.14)
(4.15)
Các phương trình (4.12) đến (4.13) được giải như sau:
Phương trình (4.12) cho . Từ phương trình (4.13), các cột của ma trận , được xác định, mỗi cột một thời điểm, từ các cột tương ứng của khi dùng phép thế thuận. Sau đó tính trực tiếp từ phương trình (4.14). Các giá trị tuần tự của được tính tuần tự theo từng cột, theo phương trình (4.15). Các giá trị tuần tự của có thể nhận được từ phương trình (4.14). kết thúc bước này tính được .
Phương trình được viết lại:
(4.16)
(4.17)
Phương trình (4.16), (4.17) giải được theo nhờ phép thế thuận.
Phương trình có dạng:
(4.18)
(4.19)
Phương trình (4.19) có thể giải được theo bằng phép thế ngược.
Các bước thực hiện thuận toán đường chéo khối:
(1). Tính các ma trận con từ các phương trình (4.12) đến (4.15).
(2). Tính các véc tơ con từ các phương trình (4.16) đến (4.17).
(3). Tính các véc tơ con từ các phương trình (4.18) đến (4.19).
§5.Các phương pháp lặp
Phương pháp lặp là phương pháp giải chỉ cho nghiệm gần đúng của hệ phương trình đại số tuyến tính với độ chính xác bất kỳ.
Các phương pháp lặp dùng khi ma trận hệ số A là ma trận “thưa” (đa số các phần tử bằng không).
Có hai phương pháp lặp được xét: lặp Jacobi và lặp Gauss - Seidel
Nội dung chủ yếu của phương pháp lặp:
1. Chọn véc tơ nghiệm ban đầu .
2. Nghiệm được chọn theo cách nào đấy để giảm sự khác biệt giữa và nghiệm đúng .
3. Lặp lại bước 2 đến khi quá trình lặp hội tụ (bước lặp tạo ra véc tơ nghiệm xấp xỉ nghiệm đúng khi số bước lặp tăng lên).
Quá trình lặp sẽ kết thúc ở bước lặp mà sự thay đổi nghiệm giữa hai bước lặp liên tiếp là không đáng kể.
(Độ đo sự thay đổi tương đối hay tuyệt đối của véc tơ nghiệm bé hơn tiêu chuẩn hội tụ).
Dấu > đúng cho ít nhất một dòng.
Số lần lặp bảo đảm sự hội tụ phụ thuộc:
1. Tính trội của các hệ số đường chéo
2. Nghiệm chọn ban đầu
3. Thuật toán được dùng
4. Tiêu chuẩn hội tụ
Hai phương pháp lặp Jacobi và lặp Gauss - Seidel sẽ hội tụ với véc tơ nghiệm ban đầu tùy ý nếu ma trận hệ số là ma trận đường chéo trội:
(5.0)
5.1.Lặp Jacobi
Xét phương trình , hay
(5.1)
Thuật toán Jacobi:
1. Chọn nghiệm ban đầu tùy ý (5.2)
2. Nghiệm lặp được chọn bởi:
(5.3)
Các giá trị lặp sauchỉ phụ thuộc và giá trị lặp ngay trước đó
được gọi là phần dư
3. Quá trình lặp sẽ kết thúc khi độ lệch giữa hai bước lặp liên tiếp nhỏ hơn sai số cho trước :
(5.4)
Ví dụ 5.1: Phương pháp lặp Jacobi
(a)
(b)
Nghiệm ban đầu được chọn . Thế các giá trị này vào phương trình (b) trên, cho ta . Thế các giá trị này theo phương trình (5.3), ta được: .
Lặp lại thủ tục trên cho .
Kết quả của 18 lần lặp cho bởi bảng sau:
Do tính đối xứng của ma trận A, và tính đối xứng của véc tơ b, .
Quá trình lặp kết thúc ở bước thứ 18, khi mà
5.2.Phương pháp lặp Gauss-Seidel
Thuật toán lặp Gauss-Seidel:
4. Chọn nghiệm ban đầu tùy ý (5.6)
5. Nghiệm lặp được chọn bởi:
(5.7)
Các giá trị lặp sau phụ thuộc vào tất cả các giá trị lặp trước đó.
6. Quá trình lặp sẽ kết thúc khi độ lệch giữa hai bước lặp liên tiếp nhỏ hơn sai số cho trước :
(5.8)
Phương pháp lặp Gauss-Seidel gọi là phương pháp lặp đủ vì hầu hết các giá trị dùng trong tính toán ở mỗi bước lặp.
Phép lặp Gauss-Seidel hội tụ nhanh hơn lặp Jacobi (công nhận):
Ví dụ 5.2. Giải bài toán trong ví dụ 5.1 bằng phương pháp lặp Gauss-Seidel.
Nghiệm ban đầu được chọn . Thế các giá trị này vào phương trình (b) trên, cho ta . Thế kết quả này vào phương trình lặp (5.7), ta được .
Thế giá trị vào phương trình xác định phần dư:
Công thức lặp cho ta:
Tiếp tục tương tự, ta nhận được
Kết quả tính sau chỉ với 15 bước lặp với cùng sai số như trong ví dụ 5.1.
§6.Độ tin cậy và sự hội tụ
6.1.Độ tin cậy
Khi giải gần đúng hệ phương trình đại số tuyến tính theo phương pháp lặp các sai số sau có thể xuất hiện:
1. Sai số làm tròn: được giảm thiểu khi dùng các tỷ lệ hóa hay trụ hóa.
2. Sai số do máy tính: tăng số lần lặp đến giới hạn được phép của máy tính, coi như nghiệm xấp xỉ là nghiệm chính xác. Vì thế sai số do máy có thể bỏ qua.
3. Sai số do tiêu chuẩn hội tụ: sai số phương pháp. Chỉ xét sai số này.
Độ tin cậy: đo bằng các sai số phương pháp xác định bởi:
1. Sai số tuyệt đối = giá trị xấp xỉ - giá trị đúng
2. Sai số tương đối = Sai số tuyệt đối / giá trị đúng (× 100 %).
Chú ý : Sai số tuyệt đối không bảo đảm số chữ số có nghĩa giống nhau trong giá trị xấp xỉ.
Sai số tương đối bảo đảm số chữ số có nghĩa giống nhau của giá trị xấp xỉ, bất kể biên độ của giá trị đúng.
Ví dụ:
(a) Với sai số tuyệt đối thiết kế :
(a1) Nếu số đúng là thì giá trị gần đúng là và có 5 chữ số có nghĩa.
(a2) Tuy nhiên nếu số đúng là thì giá trị gần đúng là lại không có chữ số có nghĩa.
(b) Với sai số tương đối thiết kế
(b1) Nếu số đúng là thì sai số tuyệt đối phải là
và giá trị gần đúng là có 5 chữ số có nghĩa.
(b2) Tuy nhiên nếu số đúng là thì sai số tuyệt đối là:
giá trị gần đúng là có 5 chữ số có nghĩa.
6.2. Sự hội tụ
Sự hội tụ của phương pháp lặp xảy ra khi tiêu chuẩn hội tụ thiết kế được thỏa mãn. Tiêu chuẩn hội tụ có thể được định rõ bởi sai số tương đối hay sai số tuyệt đối.
Do nghiệm chính xác chưa biết, nên sai số ở bước lặp nào đó được dựa trên sự thay đổi về lượng đang được tính toán ở bước đó và bước tiếp sau.
Khi giải hệ phương trình đại số tuyến tính bằng phương pháp lặp, nghiệm đúng không biết, nên sai số:
Một số tiêu chuẩn hội tụ (điều kiện kết thúc lặp), khi sai số hội tụ được cho trước:
1. Tiêu chuẩn sai số tuyệt đối:
(6.1)
2. Tiêu chuẩn sai số tương đối:
(6.2)
§7.Giảm trên liên tiếp (Successive Over-Relaxation), SOR
Phương pháp giảm trên liên tiếp được áp dụng để tăng tốc độ hội tụ của phương pháp Gauss-Seidel.
Công thức thuật toán giảm trên liên tiếp:
1. Chọn tùy ý (7.1)
2. Với bất kỳ
Khi ta có phương pháp giảm dưới liên tiếp.
Khi phương pháp phân kỳ.
Phương pháp giảm dưới liên tiếp thích hợp khi thuật toán Gauss-Seidel tạo ta véc tơ nghiệm dị biệt, khi kết quả trong một mẫu dao động. Phản ứng này nói chung gắn liền với nghiệm lặp của các hệ phương trình đại số phi tuyến.
Hệ số giảm không làm thay đổi nghiệm cuối cùng, vì nó nhân với số dư , mà sẽ triệt tiêu khi nghiệm cuối cùng tìm được.
Khó khăn chính trong phương pháp giảm trên liên tiếp là xác định giá trị tốt nhất cho hệ số giảm trên . Hiện không có phương pháp tổng quát để xác định giá trị tối ưu cho hệ số giảm trên .
Ví dụ 7.1. Bằng phương pháp SOR, giải bài toán trong ví dụ 5.1.
Dùng
Các kết quả tính toán cho trên bảng sau, với sai số tuyệt đối giưa hai lần lặp liên tiếp:
Quá trình lặp kết thúc sau 13 lần lặp. Số lần lặp ít hơn so với phương pháp Gauss – Seidel (15).
Tìm giá trị tối ưu cho hệ số giảm trên có thể làm bằng thực nghiệm.
Với bảng này, là các giá trị tốt nhất cho
Bài tập Chương 2
I. Các tính chất của ma trận và định thức
Cho bốn ma trận
1. Tính A+B, B+A, A+D, A+C, B+C
2. Tính A-B, B-A, A-D, B-D, A-C, B-C, C-B, D-C
3. Tính AC, BC, CA, CB, AD, BD, CTB, CTD, AAT, BBT, DDT
4. Tính AB và BA, AD và DA, BD và BD sau đó cho chỉ ra sự khác nhau của từng cặp
5. Chứng minh rằng (AB)T = BTAT và AB = (Ab1 Ab2 Ab3) trong đó b1, b2, b3 là các cột của B.
6. Kiếm tra rằng: A + (B+D) = (A+B)+D; A(BD) = (AB)D.
7. Theo phương pháp đường chéo, tính các định thức sau:
det(A); det(B); det(C); det(D);
det(AB); det(AB); det(BA); det(DA); det(CD);det(CTA)
8. Tích các đinh thức trong bài tập 7 theo phương pháp phần phụ đại số
9. Chỉ ra rằng det(A) det(B) = det(AB) và det(A) det(D) = det(AD)
II. Phương pháp khử trực tiếp
Giải các hệ phương trình sau theo qui tắc Crame
10.
11.
12.
13.
14.
15.
16.
17
18*. Giải bài toán 10 khi dùng phương pháp khử Gauss
19. Giải bài toán 11 khi dùng phương pháp khử Gauss
20*. Giải bài toán 12 khi dùng phương pháp khử Gauss
21. Giải bài toán 13 khi dùng phương pháp khử Gauss
22. Giải bài toán 14 khi dùng phương pháp khử Gauss
23. Giải bài toán 15 khi dùng phương pháp khử Gauss
24. Giải bài toán 16 khi dùng phương pháp khử Gauss
25*. Giải bài toán 17 khi dùng phương pháp khử Gauss
26*. Giải bài toán 10 khi dùng phương pháp khử Gauss-Jordan
27. Giải bài toán 11 khi dùng phương pháp khử Gauss-Jordan
28*. Giải bài toán 12 khi dùng phương pháp khử Gauss-Jordan
29. Giải bài toán 13 khi dùng phương pháp khử Gauss-Jordan
30. Giải bài toán 14 khi dùng phương pháp khử Gauss-Jordan
31. Giải bài toán 15 khi dùng phương pháp khử Gauss-Jordan
32. Giải bài toán 16 khi dùng phương pháp khử Gauss-Jordan
33*. Giải bài toán 17 khi dùng phương pháp khử Gauss-Jordan
34. Tính ma trận ngược của bài toán 10 theo phương pháp khử Gauss-Jordan. Giải hệ phương trình theo phương pháp ma trận ngược.
35. Giải bài toán 11 theo thủ tục mô tả trong bài 34.
36. Giải bài toán 12 theo thủ tục mô tả trong bài 34.
37. Giải bài toán 13 theo thủ tục mô tả trong bài 34.
38. Giải bài toán 14 theo thủ tục mô tả trong bài 34.
39. Giải bài toán 15 theo thủ tục mô tả trong bài 34.
40. Giải bài toán 16 theo thủ tục mô tả trong bài 34.
41. Giải bài toán 17 theo thủ tục mô tả trong bài 34.
III. Phương pháp nhân tử LU
42*. Giải bài toán 10 theo phương pháp nhân tử LU khi dùng phương pháp Doolittle.
43. Giải bài toán 11 theo phương pháp nhân tử LU khi dùng phương pháp Doolittle.
44*. Giải bài toán 12 theo phương pháp nhân tử LU khi dùng phương pháp Doolittle.
45. Giải bài toán 13 theo phương pháp nhân tử LU khi dùng phương pháp Doolittle.
46. Giải bài toán 14 theo phương pháp nhân tử LU khi dùng phương pháp Doolittle.
47. Giải bài toán 15 theo phương pháp nhân tử LU khi dùng phương pháp Doolittle.
48. Giải bài toán 16 theo phương pháp nhân tử LU khi dùng phương pháp Doolittle.
49*. Giải bài toán 17 theo phương pháp nhân tử LU khi dùng phương pháp Doolittle.
IV. Các hệ phương trình đường chéo
Giải các hệ phương trình sau theo thuật toán Thomat
50*.
51
52*.
53*.
54.
V. Các phương pháp lặp
Giải các hệ phương trình sau theo phương pháp lặp. Giá trị ban đầu cho trước
55. Giải bài toán 50 theo phương pháp lặp Jacobi
56. Giải bài toán 52 theo phương pháp lặp Jacobi
57. Giải bài toán 53 theo phương pháp lặp Jacobi
58. Giải bài toán 54 theo phương pháp lặp Jacobi
59. Giải bài toán 50 theo phương pháp lặp Gauss-Seidel
60. Giải bài toán 52 theo phương pháp lặp Gauss-Seidel
61. Giải bài toán 53 theo phương pháp lặp Gauss-Seidel
62. Giải bài toán 54 theo phương pháp lặp Gauss-Seidel
V. Phương pháp giảm trên (SOR)
63. Giải bài toán 50 theo phương pháp SOR, với w = 1.27
64. Giải bài toán 52 theo phương pháp SOR, với w = 1.27
65. Giải bài toán 53 theo phương pháp SOR, với w = 1.27
66. Giải bài toán 54 theo phương pháp SOR, với w = 1.05
67. Giải bài toán 63 với 1.25 ≤ w ≤1.35 và Dw = 0.01
68. Giải bài toán 64 với 1.25 ≤ w ≤1.35 và Dw = 0.01
69. Giải bài toán 65 với 1.25 ≤ w ≤1.35 và Dw = 0.01
70. Giải bài toán 66 với 1.00 ≤ w ≤1.10 và Dw = 0.01
Một số chương trình nguồn
Bốn trình con FORTRAN để giải hệ phương trình đại số tuyến tính được giới thiệu trong phần này:
1. Khử đơn Gauss
2. Thuật toán nhân tử LU Doolittle
3. Thuật toán Thomat
4. Thuật toán giảm trên liên tiếp (SOR)
1.Khử đơn Gauss
Các bước khử của phương pháp khử đơn được cho bởi công thức:
Với mỗi cột k ,
(8.1)
Phép thế ngược thực hiện theo công thức (2.16)
(8.2)
Mã nguồn
2. Phương pháp nhân tử LU Doolittle
Phương pháp nhân tử LU Doolittle dựa trên phương pháp nhân tử LU và phương pháp khử Gauss.
Trình con Gauss ở trên được sửa đổi đơn giản để nhận được các ma trận L và U khi bỏ đi dòng xác định b(i) trong nhóm thứ nhất của lệnh và xóa đầu vào nhóm lệnh thứ hai mà xác định các bước thế ngược. Chương trình là lufactor.
Các bước tính toán tiếp theo được cho bởi công thức sau:
(8.3)
Kết luận chương 2. Giải phương trình đại số tuyến tính cấp n
Các phương pháp trực tiếp: qui tắc Crame, khử Gauss, khử Gauss-Jordan, nhân tử LU, thuật toán Thomat cho các hệ đường chéo.
Thực hành tính:
Hệ ít hơn 3, 4 phương trình, thường dùng qui tắc Crame.
Hệ nhiều hơn 3,4 phương trình dùng phương pháp khử Gauss.
Hệ có nhiều vế phải, dùng phương pháp nhân tử LU.
Hệ 3 đường chéo, dùng thuật toán Thomat
Dùng phương pháp trực tiếp khi hệ có ít nhất một trong các điều kiện sau:
(a) Số phương trình bé
(b) Đa số các hệ số của hệ khác không
(c) Hệ không có dạng đường chéo trội
(d) Hệ có điều kiện yếu
Các phương pháp lặp: Lặp Jacobi, lặp Gauss-Seidel, giảm trên liên tiếp SOR.
Tất cả các phương pháp lặp trên đều hội tụ, nếu ma trận hệ số là đường chéo trội. Phương pháp SOR thường được chọn nhất khi hệ có nhiều vế phải.
Dùng phương pháp lặp khi:
(a) Số phương trình lớn
(b) Ma trận hệ số thưa
(c) Ma trận hệ số là đường chéo trội
Bạn đang đọc truyện trên: AzTruyen.Top