BỘ MÔN TOÁN ỨNG DỤNG - ĐHBK

PHƯƠNG PHÁP TÍNH – BG SINH VIÊN
CHƯƠNG 2
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH
Ax = b
TS. NGUYỄN QUỐC LÂN (2/2006)
NỘI DUNG

A- CÁC PHƯƠNG PHÁP CHÍNH XÁC
1- PHƯƠNG PHÁP KHỬ GAUSS (PHẦN TỬ TRỤ)
2- PHÂN TÍCH NHÂN TỬ A = LU
3- PHÂN TÍCH CHOLESKY
B- CÁC PHƯƠNG PHÁP LẶP
1- LẶP JACOBI
2- LẶP GAUSS - SEIDEL
C- SỐ ĐIỀU KIỆN – HỆ ĐIỀU KIỆN XẤU
TỔNG QUAN

Hệ n phương trình bậc 1 (tuyến tính), n ẩn → Dạng Ax = b:
Hàng i: h
i
= [a
i1
a
i2
… a
in
]
T
. Biến đổi sơ cấp trên hàng h

nnnn
n
n
aaa
aaa
aaa
A




,
2
1












=
n
b
b

Đơn giản: Hệ tam giác












=
nn
n
n
a
aa
aaa
A



00

0
222
11211
⇒ Giải lùi





−
−
−
14
5
1
30
14
3
84
76
22
Khử cột 1 với hệ số khử m
1j
3
2
6
21
==m
2
2
4
31
==m
→








− 1322
0
1−
5 2
0
4− 24
12
11
1
1
a
a
m
j
j
=
ii
ij
ij
a
a
m = :quaùt Toång
GIẢI LÙI & PHẦN TỬ TRỤ







−
−
4
2
1
4
5
3
00
10
22
Điều kiện: Khử cột 1: a
11
(1)
≠ 0 & Khử cột 2: a
22
(2)
≠ 0 &
Giải lùi: a
33
(3)
≠ 0 ⇒ Phần tử trụ (pivot) a
kk
≠ 0
Giải lùi với hệ tam giác trên thu được:

1322
3
32
321
x
xx
xxx










=⇒
1
3
2
x
4
1
4
32
=
−
−
=m

2
→ h
2
– m
21
h
1
> A := swaprow(A,1,2) ; # Nếu cần thiết, đổi hàng h
2
↔ h
1
> x := backsup(A) ; # Hệ đã ở dạng tam giác trên: Giải lùi
> AA := gausselim(A); # Lệnh gộp khử Gauss toàn ma trận
> with(linalg); # Khởi động gói lệnh Đại số tuyến tính
KHỬ GAUSS VỚI MA TRẬN “LẺ”: PIVOT ĐƠN VỊ

[ ]






−
−
−





−=−+−
−=−+−
=−
116.108.27.0
168.03.108.27.0
152.03.108.27.0
608.03.108.2
43
332
321
21
xx
xxx
xxx
xx












=⇒
736.0
593.0

10
001.1
104400104300
17.5914.59003.0
1
2
2
21
sao Taïi



−=
=
⇒



−=−
=+
x
x
x
xx



=−
=+
)(E78.46130.6291.5









=
*000
**00
***0
****
1***
01**
001*
0001
A
Giải hệ đầu ⇔ Giải 2 hệ ∆: Ly = b (2) tìm y; Ux = y (1) tìm x
( )
( )
giaùc tam heä 2:
2
1



=
=
bLy












−
−
−
=












−−
−−
−

=










−
−
⋅










400
510
322
142
013
001

m
m
m










=⇒
142
013
001
L
L (hoặc U) có đchéo chính = 1 ⇒ G/thuật Doolitle (Crout)
For j = 1 to n: i = 1 → j
∑
−
=
−=
1
1
i
k
kjikijij
ulau










−
−
−
=
3084
1476
322
A










=



11
31
31
u
a
=
22
123132
32
u
ua 

−
=
i = 3
1313
au =
13212323
uau −=
233213313333
uuau  −−=
i = 2 i = 3
i = 2
i = 3
i = 2
i = 1
i = 1
i = 1 i = 3
PHÂN TÍCH CHOLESKY


321
>−+++=⇒∈=∀ xxxxxxxAxxRxxxx
T
T
A: XĐD⇔ n định thức con (hvuông) trên đ/chéo chính đều > 0
VD:











−
−=
220
251
011
A
: ma trận (đối xứng) xác định dương vì

GIẢI THUẬT CHOLESKY


ikjkji
ii
ji
bba
b
b
Ax = b ⇔ (BB
T
)x = b ⇔ B
T
x = y & By = b: 2 hệ ∆ (như LU)
A k0 xác định dương (chỉ đối xứng): A = BB
T
có thể chứa số
phức ⇒ 2 hệ B
T
x = y & By = b: phức. Nhưng nghiệm x: thực!
MINH HOẠ GIẢI THUẬT CHOLESKY

i = 1
i = 2
i = 3
VD:








11
31
31
b
a
b =
2
212222
bab −=
22
213132
32
b
bba
b
−
=
2
32
2
313333
bbab −−=
j = 2 j = 3
j = 3
TỔNG QUAN PHƯƠNG PHÁP LẶP

Chương 1: Phương pháp lặp đơn với phương trình f(x) = 0
( )
( )
nn

]
T
∈ R
n
, A = [a
ij
]

{ }
⇒=
≤≤
∞
i
ni
xx
1
max






=
∑
=
≤≤
∞
n
j

1
1
1
max
VÍ DỤ


Tính các chuẩn vectơ và ma trận
Tch. chuẩn vectơ, chuẩn ma trận: Chuẩn tích ≤ tích chuẩn

( ) ( ) ( )
1: <−⋅≤−=−⇒⋅≤ TyxTyxTyxxAAx
ϕϕ

Vectơ nào trong số hai vectơ sau xấp xỉ tốt nhất theo chuẩn
∞, chuẩn một nghiệm hệ phương trình
( ) ( )










−=



132
321
321
321
xxx
xxx
xxx
3
6
12
13
( )
( )





≈
≈
→
∞
xx
xx
1
.
1
.
2


⇒










−−
−
−
=
∞
1
165
342
231
A
A
A
LẶP JACOBI

Với vectơ x
(0)
= [0, 0, 0]
T
, tìm vectơ nghiệm xấp xỉ x









−−=−−=
++=++=
+−−=+−−=
3125.025.0125.0
8
5.2
8
2
8
1
9.01.03.0
10
9
10
1
10
3
75.01.03.0
10
5.7
10
1




=












−
−−
=
∞
3125.0
9.0
75.0
,1
10
4
8
3
,
10

−−=
++=
+−−=
+
+
+
3125.025.0125.0
9.01.03.0
75.01.03.0
)(
2
)(
1
)1(
3
)(
3
)(
1
)1(
2
)(
3
)(
2
)1(
1
kkk
kkk
kkk

9.01.03.0
75.01.03.0
)0(
2
)0(
1
)1(
3
)0(
3
)0(
1
)1(
2
)0(
3
)0(
2
)1(
1
xxx
xxx
xxx
LẶP JACOBI KHÔNG BIẾN ĐỔI MA TRẬN A

Hệ Ax = b:





5.7310
)(
2
)(
1
)1(
3
)(
3
)(
1
)1(
2
)(
3
)(
2
)1(
1
kkk
kkk
kkk
xxx
xxx
xxx
: Giữ đ/chéo chính ở vế trái
(→ x
(k+1)
) ; Chuyển số hạng
còn lại sang vế phải (→ x

5.282
9103
5.7310
)1(
3
)(
2
)(
1
)(
3
)1(
2
)(
1
)(
3
)(
2
)1(
1
kkk
kkk
kkk
xxx
xxx
xxx
: Thay x
(k)
vào các số hạng

10
5.73
)(
2
)(
1
)1(
3
)(
3
)(
1
)1(
2
)(
3
)(
2
)1(
1
kk
k
kk
k
kk
k
xx
x
xx
x

+
+
+
5.228
9310
5.7310
:
)(
2
)(
1
)1(
3
)(
3
)(
1
)1(
2
)(
3
)(
2
)1(
1
kkk
kkk
kkk
xxx
xxx

(k-1)
||

0.9
LẶP GAUSS – SEIDEL

Tương tự lặp Jacobi nhưng với thông tin cập nhật hoá





−=++−
=−+−
=++
5.282
9103
5.7310
:
321
321
321
xxx
xxx
xxx
Heä
Dùng x
(k)

để tính







−−
=
++
=
+−−
=
⇔
+
+
+
8
5.22
10
93
10
5.73
)(
2
)(
1
)1(
3
)(
3




−−
=
++
=
+−−
=
⇒
++
+
+
+
+
8
5.22
10
93
10
5.73
)1(
2
)1(
1
)1(
3
)(
3
)1(




−=++−
+=+−
+−−=
⇔
+++
++
+
5.282
9103
5.7310
)1(
3
)1(
2
)1(
1
)(
3
)1(
2
)1(
1
)(
3
)(
2
)1(

( )
1+
→
k
xheäGiaûi
1+= kk
Gauss - Seidel: Biết x
(k)
→ Tính vế phải b
(k)
→ Giải hệ ra x
(k+1)
LẶP GAUSS – SEIDEL: VÍ DỤ TÁCH MA TRẬN

Xét ví dụ lặp Gauss – Seidel, x
(0)
= [0, 0, 0]
T
. Công thức lặp:
Phép lặp ⇔ Thay hệ Ax = b bằng giải liên tiếp nhiều hệ ∆
( )
k
kkk
kkk
kkk
b
xxx
xxx
xxx
→

1
)(
3
)(
2
)1(
1
x
2
b
10k
||x
(k)
-x
(k-1)
||
∞
0.0x
3
(k)
0.0x
2
(k)
0.0x
1
(k)
bxbx