ĐẠ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 -