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
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/


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
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:

n
x 
là véc tơ cột,
T
x
là véc tơ hàng.
Với
12
, , ,
n

21 22 2
12

...

n
n
mm
mn
a
aa
a a a
A
aa
a

Các ký hiệu det(A),A
-1
, A
T
, R(A), N(A), r(A) lần lƣợt là định thức, nghịch đảo,

ii) Tính chất duy nhất: điểm duy nhất P
y
đƣợc đặc trƣng bởi
y
PC
và
,0C Py y Py

iii) P là ánh xạ không dãn.
Vài trƣờng hợp cụ thể:
C là hình cầu đơn vị:
:1C x X x
. Khi đó P
C
x = x, nếu
xC
:
/
C
P x x x
, và trƣờng hợp khác.
C là orthan không âm:
:0C x X x
. Khi đó P
C
x = x
+
.
C là siêu phẳng:
;,C x X a x b
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.
1

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 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

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.
3

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 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.

là hệ có dạng:
11 1 12 2 1 1
1 1 2 2

;

nn
m m mn n m
a x a x a x b
a x a x a x b
(1.1)
Hay có thể viết gọn hơn:
1
, 1, ,
n
ik k i
k
a x b i m

Trong đó
,
ik i
ab
là các phần tử thuộc không gian véc tơ
n

;
ik
a
gọi là hệ số

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ơ
1
, ,
n
của
không gian véc tơ
n

sao cho khi thay ẩn
k
x
bởi thành phần
k
,
1, ,kn
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
1
, 1, ,
n


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:
11 12 1 11 21 1 1
1 2 1 2

,

nn
m m mm m m mm m
a a a a a a b
AA
a a a a a a b

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:
11

. . .

nm

(1.4)
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à
12
( , , , )
n
c c c
tức là :
1 1 2 2

nn
c c c

Nhƣ vậy là một tổ hợp tuyến tính của hệ véc tơ
12
, , ,
n
.
Suy ra
1 2 1 2
( , , , , ) ( , , , )
nn
LL
. Điều đó chứng tỏ
(A) ( )r r A

( , , , )
n
n
c c c R
sao cho :
9

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
1 1 2 2

nn
c c c
.
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à
mn
và
det( ) 0A
.
Định lý 1.2 : Hệ Cramer

11 1 1 1
11

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
j
x
) bởi các
phần tử
1
, ,
n
bb
(các hệ số tự do).
Chứng minh : Theo (1.7) nếu khai triển định thức
j
theo cột thứ j ta có :
10

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
1
n
j k kj
k
bA
(a)
Trong đó
kj
A
là phần bù đại số của phần tử

11 21 1
*
12
n
n n nn
A A A
A
A A A
là ma trận phù hợp của ma trận A và
hệ thức (a) ta có:

11
1
nn
xb
A
xb

Thay
1*
1
det( )
AA
A


n
kk
k
n
n
k kn
k
bA
x
x
bA

Suy ra:

1
1
nn
x
x
(c)
Từ đẳng thức ma trận (c) ta có

, 1, ,
j
j
x j n

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 0A
). Ở đâ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
13

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 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
*1
x A b
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.


T
Ly P b
và
Ux y

Sự phát biểu lại này, thoạt đầu có vẻ không hợp lý vì một hệ tuyến tính đƣợc
thay thế bởi hai hệ tuyến tính cùng cấp. ý tƣởng then chốt ở đây là ở chỗ hai hệ trên
rất dễ giải nhờ vào cấu trúc các ma trận.
Do độ phức tạp thời gian của phƣơng pháp khử Gauss đƣợc cho bởi
32
2 / 3 ( )nn
các phép toán số học. Phần tính toán chính của phƣơng pháp là tính
phân tích (2.1), cụ thể là tính L và U. Phƣơng pháp Gauss có thể đƣợc thực hiện tại
chỗ theo cách thay các phần tử của A bởi các phần tử L và U. Vậy đòi hỏi không
gian của phƣơng pháp là
2
()nn

II.2.2. Phương pháp nhân tử hóa Cholesky
Với những hệ xác định Hecmit, phƣơng pháp khử Gauss đƣợc đơn giản hóa
thành phƣơng pháp nhân tử hóa Cholesky. Trong giai doạn đầu phƣơng pháp
Cholesky, ta tính toán các nhân tử của tích.

.A L LH
(2.3)
Trong đó L là ma trận tam giác dƣới.

*
*

Cholesky là tính toán phân tích (2.3), nghĩa là phần tính của các ma trận tam giác
Cholesky L. Độ phức tạp tính toán của toàn bộ quá trình giải là
32
/ 3 ( )nn
các
phép toán số học. Có thể cải tiến phƣơng pháp Cholesky theo cách viết L thay vào
phần tam giác dƣới của A. Nhƣ vậy đòi hỏi không gian bộ nhớ của phƣơng pháp là
2
/ 2 ( )nn
. Lƣu ý rằng so với phƣơng pháp Gauss đối với các ma trận tổng quát,
việc nhân tử hóa các ma trận xác định dƣơng Hecmit chỉ cần xấp xỉ một nửa số
lƣợng các phép toán cũng nhƣ một nửa bộ nhớ.
Nhƣ vậy, các phƣơng pháp trực tiếp thƣờng gồm 2 giai đoạn. Số các phép tính
số học và nhu cầu bộ nhớ tƣơng ứng là lũy thừa cấp 3 và cấp 2 của bậc ma trận hệ
số. Những điều này rất khó chấp nhận trong quá trình tính toán cỡ lớn với cấp của
ma trận tăng rất nhanh theo thời gian. Trong
4
có trình bày một số cải tiến của
thuật toán này cho việc giải các bài toán cỡ lớn hơn.
II.2.3 Vấn đề Fill – in ( suy giảm độ thưa )
Ví dụ sau sẽ giải thích rõ sự khó khăn của các phƣơng pháp trực tiếp trong
trƣờng hợp các ma trận thƣa. Giả sử hệ xác định dƣơng, đối xứng cấp n với ma trận
hệ số thƣa
16

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
* * * *

biểu diễn thƣa của nó do giới hạn dung lƣợng của bộ nhớ. Có thể xem “fill-in” nhƣ
thƣớc đo bộ nhớ cần thiết thêm vào dung lƣợng bộ nhớ cực đại đƣợc dùng trong
quá trình tính toán.
Liệu phần thƣa của ma trận A có ảnh hƣởng đến lƣợng fill-in trong quá trình
phân tích? Các phần thƣa khác nhau khi ta đánh số lại các ẩn và đổi chỗ các
17

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ phƣơng trình (đổi cột và hàng của ma trận ) có thể biểu diễn bởi phép toán hoán vị
đƣợc xác định nhƣ sau. Cho ma trận A và ma trận hoán vị P, ma trận
T
P AP
đƣợc
gọi là “hoán vị đối xứng” của A. Một ma trận hoán vị đối xứng của A trong công
thức (2.4) đƣợc cho bởi

**
**
**
* * * *
T
P AP


(2.6)
Trong đó chỉ các thành phần đầu tiên và cuối cùng và hai phƣơng trình tƣơng ứng
đƣợc đổi chỗ cho nhau. Với các ma trận A là đối xứng và xác định dƣơng, có thể
chỉ ra rằng với ma trận hoán vị bất kỳ P thì hoán vị đối xứng

. Số các phần tử khác 0 của L
A
là
2
()n
, trong khi chỉ có
()n
những phần tử
18

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ khác 0 trong
T
P
L AP
. Tiếc rằng việc tìm ra phép hoán vị đối xứng cho phép cực tiểu
hóa của “fill-in” là một bài toán tối ƣu tổng hợp có độ khó cao. Chính xác hơn, có
thể chỉ ra rằng vấn đề tìm “fill-in” cựu tiểu có độ phức tạp là NP đầy đủ, có nghĩa
là không thể có thuật toán thời gian đa thức theo bậc của ma trận để xác định nó
5

Tóm lại, các phƣơng pháp trực tiếp áp dụng cho các hệ tuyến tính cỡ lớn và
thƣa có thể dẫn đến khối lƣợng các “fill-in” cao làm tràn bộ nhớ. 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ó
7
.