Phương pháp tính - Chương II: Giải hệ phương trình Ax=b

Chương II : GIẢÛI HỆÄ PHƯƠNG TRÌNH 
 Ax=b 
1) Hệää cóùù A làøø ma trậään tam giáùùc trêâân 












=




















=
n
n
b
b
x
x
a
aaa
aaa
xA
.
.
.
.
.....
..00
.0
..
2
1
2
1
33
22322
11211
Phương pháp TínhNgơ Thu Lương








 nnnn bxa0000
Tính nghiệm 
1 2 3 1....n n n nx x x x x− − −→ → → → 





=++
=++
=++
1.001.000
2.2021.00
0.182
3
32
321
x
xx
xxx
Ví dụïï : 



=
=
2
4
2
1
x
x
Phương pháp TínhNgơ Thu Lương

 =103x
2) Hệää cĩ A làøø ma trậään tam giáùùc dướùùi 
















=
































=
nnnnnn b
b
b
x
x
x
aaa
aaa
aa
a
xA
.
.
.
.
..
0....
..
0.0
0..0
2
1
2
1
21
333231
2221
11
Phương pháp TínhNgơ Thu Lương
Tính nghiệm 1 2 3 4.... nx x x x x→ → → → 
3) Giảûûi bằèèng phương pháùùp nhââân tửûû LU : 
( A ma trậään vuôââng bấáát kỳøø ) 
a) Nộääi dung : Phân tích ma trận A = L.U 
 L là ma trận tam giác dưới 
U là ma trận tam giác trên 
Phương pháp TínhNgơ Thu Lương
Việc giải hệ phương trình sẽ đưa về giải hai hệää 
phương trình dạng tam giáùùc 
Quy ước 11 22 33 .. 1l l l= = = = : có nghiệm duy nhất 
Cáùùch tìm L, U từø ma trậän A : 
Nhân hàng1 của Lvới cột 1 của U tìm được 11u 
Nhân hàng2 của Lvới cột 1 của U tìm được 21l 
Nhân hàng3 của Lvới cột 1 của U tìm được 31l 
Nhân hàng1 của Lvới cột 2 của U tìm được 12u 
Nhân hàng1 của Lvới cột 3 của U tìm được 13u 
Nhân hàng2 của với cột 2 của tìm được 
Phương pháp TínhNgơ Thu Lương
L U 22u
Nhân hàng3 của Lvới cột 2 của U tìm được 32l 
Nhân hàng2 của Lvới cột 3 của U tìm được 23u 
Nhân hàng3 của Lvới cột 3 của U tìm được 33u 
4) Phương pháùùp Cholesky 
( phương pháùùp căêên bậääc hai ) 
a) Nộääi dung : 
Biểu diễn ma trận A dưới dạng TBBA .= 
trong đó B là ma trận tam giác dưới 
Phương pháp TínhNgơ Thu Lương
( TB : ma trận chuyển vị của B, là ma trận tam 
giác trên ) 
b) Nhậän xéùt : 
Cách tìm B tương tựïï như phương pháp LU 
nhưng số phép tính giảm đi 2 lần 
Phương pháp Cholesky khôââng đòi hỏi đường 
chéo của ma trận B bằng 1 
Phương pháp TínhNgơ Thu Lương
Khi lấy căn bậc 2 quy ước rằng lấy căêên sốáá họïïc 
( căêên làøø sốáá dương ) 
Ví dụ : 










=
1451
551
111
A
0 0
0B
 
 
=
 
 
Phương pháp TínhNgơ Thu Lương
 










−
−−
−
=
210
121
012
A
0 0
0B
 
 
=
 
Phương pháp TínhNgơ Thu Lương
  
b) Nhậään xéùùt : 
*) Phương pháp chỉ dùng được nếu A là 
 đốáái xứùùng và xáùùc định dương 
5) Cáùùc phương pháùùp lặëëp : 
(thường dùng cho các hệ với ma trận 
 A có kích thước rất lớn) 
Phương pháp TínhNgơ Thu Lương
5.1) Định nghĩa : (Chuẩn của vectơ ) 
i
ni
xx
≤≤∞
=
1
max 
( ix : các thành phần của véctơ x ) 
 (chuẩn vô hạn , hàng ) 
 i
n
i
xx ∑=
=1
1 
( chuẩn 1, cột ) 





−
= 2
1
x
x
∞
=
5.1) Định nghĩa : (Chuẩn của vectơ ) 
Phương pháp TínhNgơ Thu Lương
− 3 1x =
0x ≥
0 0x x= ↔ =
5.2) Định nghĩa ( Chuẩn của ma trận ) 








∑=
=≤≤
∞
n
j
ji
ni
aMaxA
11
(chuẩn vô hạn , chuẩn hàng) 




∑=
n
jiaMaxA 1 
Phương pháp TínhNgơ Thu Lương
 =≤≤ inj 11
(chuẩn 1 , chuẩn cột ) 
Ví dụïï : 





=
12
34
A ta có 
7)3,7(
11
==








∑=
=≤≤
∞
MaxaMaxA
n
j
ji
ni
6)4,6(
11
1 ==





∑=
=≤≤
MaxaMaxA
n
i
ji
nj
Phương pháp TínhNgơ Thu Lương
Cáùùc tính chấáát củûûa chuẩåån ma trậään : 
0
0 0
A
A A
≥
= ⇔ =
BABA +≤+
xAxA .. ≤
5.3) Định nghĩa ( Số điều kiện cuả ma trận A) 
1
1
111 .)()(
−
== AAAcondAk 
∞
−
∞∞∞
==
1
.)()( AAAcondAk 
Ví dụïï : 





=
12
34
A , 



=
−
−
−
21
2/32/11A 
Phương pháp TínhNgơ Thu Lương
 213.7.)( 1 ===
∞
−
∞∞
AAAk
 11 1 1
7( ) . 6 21
2
k A A A−= = = 
Ví dụïï : 










=
01.51.63
41.42
121
A 










−−
−
−−
=
−
100100100
200020101980
390039203859
1A 
Phương pháp TínhNgơ Thu Lương
69.164790)( =∞ Ak 
73566)(1 =Ak 
Sự biến thiên của nghiệm tỷ lệ với sự biến 
thiên của vế phải với hệää sốáá tỷûû lệää là )(Ak 
' ( ) 'x x k A b b− ≈ −
5.4) Phương pháùùp lặëëp Jacobi ( lặëëp đơn ) : 
a) Nộääi dung: 
*) Đưa hệ bxA = về dạng gxx +Φ= 
Phương pháp TínhNgơ Thu Lương
*) Kiểm tra điều kiện 1<=Φ q 
(chuẩn hàng hoặc cột) 
*) Lấy )0(x là véctơ giá trị ban đầu tùu ý 
*) Dãy lặp )(kx xây dựng theo công thức 
gxx kk +Φ=+ )()1( 
b) Đáùùnh giáùù sai sốáá : 
( ) (1) (0)
1
k
k d qx x x x
q
− ≤ −
−
công thức tiên nghiệm 
( ) ( ) ( 1)
1
k d k kqx x x x
q
−
− ≤ −
−
công thức hậu nghiệm 
Phương pháp TínhNgơ Thu Lương
Ví dụïï : Xét hệ phương trình 





−=++
=−+
=+−
101032
51101
02110
321
321
321
xxx
xxx
xxx
 +−+= 02.01.0 xxx
Phương pháp TínhNgơ Thu Lương




−−−=
++−=
13.02.0
5.01.01.0
213
312
321
xxx
xxx
5.0=Φ
∞
 = ∞q 
 4.01 =Φ = 1q 







−−−=
++−=
+−+=
+
+
+
13.02.0
5.01.01.0
02.01.0
)(
2
)(
1
)1(
3
)(
3
)(
1
)1(
2
)(
3
)(
2
)1(
1
kkk
kkk
kkk
xxx
xxx
xxx
Với Tx ]000[)0( = , số bước lặp là k = 3 
Phương pháp TínhNgơ Thu Lương
 k 0 1 2 3 
)(
1
k
x 0 0 0.25 0.270 
)(
2
k
x
0 0.5 0.4 0.360 
)(
3
k
x
0 -1 -1.15 -1.170 
Sai số 
∞
 - 0.04 
c)Nhậään xéùùt : 
A ma trận có đườøøng chéùùo trộääi theo hàøøng: 
 ii
ji
ji aa <∑
≠
 ⇒ 1<Φ
∞
A ma trận có đườøøng chéùùo trộääi theo cộäät 
 ii
ij
ji aa <∑
≠
 ⇒ 11 <Φ 
Phương pháp TínhNgơ Thu Lương
5.5) Phương pháùùp lặëëp Gauss - Seidel : 
Nộääi dung : Các thành phần của )1( +kix vừa 
tính được đã dùøøng ngay để tính )1( 1
+
+
k
ix trong 
bước tiếp theo 
( 1) ( ) ( )0.1 0.2 0k k kx x x+ = + − +
Phương pháp TínhNgơ Thu Lương
1 2 3
( 1) ( )
2 1 3
( 1 (
3
(
) (
1 2
0.1 0.1 0.5
0.2 0.3 1
k k
k
x x x
x x x
+
+
+
+ +


=− + +

=− − −
k 1)
k 1) k 1)
k 0 1 2 3 
)(
1
k
x 0 0 0.28 0.26832 
)(
2
k
x
0 0.5 0.357 0.356858 
)(
3
k
x
0 -1.15 -1.1631 -1.1607214 
c) Nhậään xéùùt: 
Phương pháp TínhNgơ Thu Lương
Phương pháp Gauss – Seidel thông thường có 
tốc độ hội tụ nhanh hơn phương pháp lặp jacobi 
Giải thuật đơn giản hơn so với phương pháp 
Jacobi . 
Nhược điểm : Đánh giá sai số phức tạp
Ax b=
A D L U= − − 10 0 0
0 10 0
0 0 10
D
 
 
=
 
  
0 0 0
1 0 0L
 
 
= −
 
Jacobi
( )D L U x b− − =
( )Dx L U x b= + +
1 1( )x D L U x D b− −= + +
x x g= Φ +
Phương pháp TínhNgơ Thu Lương
10 1 2
1 10 1
2 3 10
A
− 
 
= −
 
  
0 1 2
0 0 1
0 0 0
U
− 
 
=
 
  
2 3 0− −  
Ax b=
A D L U= − −
Gauss-Seidel
( )D L U x b− − =
( )D L x Ux b− = +
Phương pháp TínhNgơ Thu Lương
1( )D L U−− = Φ
1 1( ) ( )x D L U x D L b− −= − + −
1( )D L b g−− =
?=
10 3
5 11
A
− 
=  
− 
10 0 
10 0
5 11
D L
 
− =  
− 
(làm trịn hai 
chữ số lẻ)
gΦ
Phương pháp TínhNgơ Thu Lương
0 11
D =  
 
0 0
5 0
L
 
=  
 
0 3
0 0
U  =  
 
1 0.1 0( )
0.04545454 0.09090909
D L −
 
− =  
 
1 0 0.3( )
0 0.136363636
D L U−  − =  
 