GIẢI ĐÚNG, GẦN ĐÚNG HỆ PHƯƠNG TRÌNH
ĐẠI SỐ TUYẾN TÍNH
1. MỤC ĐÍCH
Cho hệ phương trình đại số tuyến tính
11 1 12 2 1 1
21 1 22 2 2 2
1 1 2 2
(1.1) Ax = b

n n
n n
n n nn n n
a x a x a x b
a x a x a x b
a x a x a x b
+ + + =


+ + + =

⇔



+ + + =

L
L
L
(1.2)
Nếu detA

trong đó
j
i
∆
là định thức cấp n – 1 bỏ đi hàng i cột j của
∆
Khi n lớn thì khối lượng tính toán sẽ rất lớn. Để giảm nhẹ khối lượng tính
toán ta có 2 phương pháp giải: giải đúng và giải gần đúng:
+) Phương pháp giải đúng: là phương pháp cho lời giải sau một số hữu hạn
bước. Phương pháp này thường để giải các hệ kích thước nhỏ với (A, b)
cho đúng
+) Phương pháp giải gần đúng: là các phương pháp lặp cho nghiệm xấp xỉ
( )
m
x
dần tới nghiệm đúng khi
m → ∞
. Đối với các hệ có kích thước lớn và
các số liệu cho gần đúng thì phương pháp lặp có lợi hơn.
2. CÁC PHƯƠNG PHÁP GIẢI ĐÚNG
2.1 Phương pháp khử Gauss
1
HPT
11 1 12 2 1 1 1
21 1 22 2 2 2 1
1 1 2 2 1

n n n
n n n
n n nn n nn

n nn
x b x b x b
x b x b
x b
+
+
+
+ + + =


+ + =

⇔



=

Dùng phương pháp thế ngược ta tìm được:
1 1
, , ,
n n
x x x
−
+) Cụ thể: với n = 4
Xét hệ pt:
11 1 12 2 13 3 14 4 15
21 1 22 2 23 3 24 4 25
31 1 32 2 33 3 34 4 35
41 1 42 2 43 3 44 4 45

ta có:
1 12 2 13 3 14 4 15
(1')x b x b x b x b+ + + =

trong đó
1
11
2,5
j
ij
a
b j
a
= =
Lấy phương trình (2) của hệ (1.3) trừ đi pt
21
(1').a
Lấy phương trình (3) của hệ (1.3) trừ đi pt
31
(1').a
Lấy phương trình (4) của hệ (1.3) trừ đi pt
41
(1').a
Ta có hệ:
2
22 23 24 25
32 33 34 35
42 43 44 45
1 1 1 1
2 3 4

x
trong hệ (1.4). Giả sử
22
1
0a ≠
chia 2 vế phương
trình (1) của hệ (1.5) cho
22
1
a
ta được:
2 23 3 24 4 25
(1.6)x b x b x b+ + =

Trong đó
1
2
2
1
22
2,3,4
j
j
a
b j
a
= =
Khử
2
x

2
. 3,4 3,4,5
ij i
j
ij
a a b a i j= − = =
- Bước 3: Khử
3
x
Giả sử
2
33
0a ≠
. Chia 2 vế phương trình (1) của hệ (1.7) cho
2
33
a
ta
được:
3 34 4 35
x b x b+ =
(1.8) trong đó
2
3
3
2
32
4,5
j
j

1 12 2 13 3 14 4 15
2 23 3 24 4 25
3 34 4 35
4 45
x b x b x b x b
x b x b x b
x b x b
x b
+ + + =


+ + =


+ =


=

*) Nhận xét:
- Vậy đối với hệ n phương trình, ta thực hiện n – 1 bước, khối lượng tính
toán là
2
( 6 1)
3
n
n n+ −
. Giảm nhiều so với giải bằng phương pháp định thức
- Ưu điểm: thuật toán đơn giản, độ phức tạp thấp
- Nhược điểm: không thực hiện được khi trong các phần tử dẫn

1 2 3 4
1 2 3 4 5
1 2 3 4 5
1 2 4 5
3
2 2 9 2
3 8 4 2
6 16 5 3
4 2 2
x x x x
x x x x
x x x x x
x x x x x
x x x x
− + − = −


+ + − =


− + − − = −


+ + − − = −

 + + + = −

Giải
a)
4

2 3
3
1
2
3
2 3 1
0
4 0
1
0
3
x x x
x x
x
x
x
x
+ + =


+ =


− =

=


⇔ =


0 0 6 -25 -2 14
5
0 1 1 3 3 1
1 0 -1 1 -1 -3
0 1 1 3 3 1
0 0 1 -17 -4 6
0 0 0 83 22 -22
0 0 0 77 22 -22
1 0 -1 1 -1 -3
0 1 1 3 3 1
0 0 1 -17 -4 6
0 0 0 83 22 -22
0 0 0 77 0 0
4
5
3
2
1
0
1
2
2
2
x
x
x
x
x
=


+ + + =

⇔



+ + + =

L
L
L
(1.2)
- Bước 1 : Tách ma trận A thành tích 2 ma trận: A = B.C trong đó:
11
21 22
1 2
0 0
0
Bnn
n n
b
b b
b b b
 
 ÷
 ÷
 ÷

Cx = y





⇔
- Bước 3 : +) By = b
11
1
1
21 22
2
2
1 2
0 0
0n
n
nn
n n
b
y
b
b b
y
b
y


n n nn n n
b y b
b y b y b
b y b y b y b
=


+ =

⇔



+ + + =

dùng phép thế thuận
1 2

n
y y y⇒ ⇒ ⇒ ⇒
+) Cx = y
12 13 1
1 1
2 2
23 2
1
0 1

0 0 1

n
n
n
n
n n
x c x c x y
x c x y
x y







+ + + =
+ + =
⇔
=
Theo phép thế ngược
1 1

n
n
x x x
−
⇒ ⇒ ⇒ ⇒
*) Cách tính
;
ij ij


1
1
j
ij ij ik kj
k
b a b c
−
=
⇒ = −
∑
+) Tính
ij
c
:
1 1 2 2 1 1
1

n
ij ik kj i j i j ij jj ij j j in nj
k
a b c b c b c b c b c b c
+ +
=
= = + + + + + +
∑
Do
0
ij
b =

2 1
5 3 3 3
x x x x
x x x x
x x x
x x x x
+ − + =


− + + − = −


+ − =


− + − =

Giải
8
11
12 13 14
21 22
23 24
31 32 33
34
41 42 43 44
0 0 0
1
3 1 1 2
0 0

 ÷
 ÷
 ÷
 
 
 
−
− −
= =
−
− −
12
11 11 12
11
21 21 13
31 31 14
41 41
1
3
3
1
5
3
2
2
3
1
a
b a c
a

43 43 41 13 42 23
44 44 41 14 42 24 43 34
1 5
( ) 2 ( ( ))
4
( ) 6
5
( )
2
b a b c b c c a b c b c
b
b a b c b c
b a b c b c b c
= − + = = − + = −
= − + =
= − + + =
Vậy
3 0 0 0
1 1 2
1
3 3 3
8
5 0 0
1 1
3
0 1
A
2 4
2
2 2 0

−
 ÷
 ÷
 
 
= B.C
Ax = b
By = b
Cx = y

⇔


9
By = b
1
1
1 2
2
1 2 3
3
4
1 2 3 4
3 6
2
8
3
5 12
3
4

 
− + =
 
= −
 
 
=
− + + =



Cx = y
1 2 3 4
1
2
2 3 4
3
3 4
4
4
1 1 2
2
3 3 3
1
1 1 3
1
2 4 4
2
5 7
3

=


2.3 Phương pháp Cholesky (Phương pháp căn bậc hai)
Nội dung: giải hệ Ax = b với điều kiện A là ma trận đối xứng (
T
A A=
).
Ta biểu diễn A dưới dạng:
T
A = S .S

trong đó:
( )
x
11 12 1
22 2

0
S

0 0
n
n
ij
n n
nn
s s s
s s
s

2
1
(2 )
i
ii ii ki
k
s a s i n
−
=
= − ≤ ≤
∑

1
1
( )
0 ( )
i
ij kj ki
k
ij
ii
a s s
i j
s
s
i j
−
=

−

1
1
2
2
0 0
0n n nn
n
n
s
s s
s s s
y
b
y
b
y
b
 
 
 
 ÷
 ÷
 ÷
 ÷
 ÷
 ÷
⇔



+ + + =

Giải theo phép thế thuận
1 2
, , ,
n
y y y⇒
+)
S.x = y

12 13 1
1 1
2 2
23 2
1
0 1

0 0 1
n
n
n n
c c c
x y
x y
c c
x y
 
   








+ + + =
+ + =
⇔
=
Theo phép thế ngược
1 1

n
n
x x x
−
⇒ ⇒ ⇒ ⇒
*) Ví dụ 3: Ggiải hệ phương trình
1 2 3
1 2 3
1 2 3
2 1
2 5 1
3 1
x x x
x x x
x x x
+ + =

s s
s
 
 ÷
=
 ÷
 ÷
 
+)
11 11
s a=

11 11
1s a⇒ = =

1 1
1
11 11
( 1)
j j
j
a a
s j
a s
= = >
12
12
11
13
13

k
s a s i n
−
=
= − ≤ ≤
∑

2
22 22 12
1s a s⇒ = − =

1
1
( )
0 ( )
i
ij kj ki
k
ij
ii
a s s
i j
s
s
i j
−
=

−


2 2
33 33 13 23
31
32
( ) 1
0
0
s a s s
s
s

= − + =


⇒ =


=


Vậy S =
1 2 1
0 1 1
0 0 1
 
 ÷
−
 ÷
 ÷
 

1
y
y y
y y y
=


+ =


− + =


1
2
3
1
1
1
y
y
y
=


= −


= −


⇔ = −


= −

12
3. GIẢI GẦN ĐÚNG HỆ PHƯƠNG TRÌNH ĐSTT
3.1 Phương pháp lặp đơn
Nội dung: Từ hệ Ax = b (1.2) với A =
( )
ij
n n
a
×
;x =
1
2
n
x
x
x
 
 ÷
 ÷
 ÷
 ÷
 
M
,b=
1

 ÷
 ÷
 
M
là xấp xỉ đều tuỳ ý
α
là nghiệm thì A
α
= b
⇔
α
= B
α
+ y
Đặt
1
2 1
1
o
k k
X BX g
X BX g
X BX g
+
= +
= +
= +
K
với X
k

x = BX+ g
Nếu
B
<1 thì dãy lặp (x
k
)
→
α
khi k
→
∞
Sai số:
1
.
1
k
k o
B
x x x
B
α
− ≤ −
−
hoặc
1
.
1
k k k
B
x x x

+ g và mọi dãy lặp TX
k+1
=TX
k
+ g (x
o
tuỳ ý ) hội tụ tới
α
.
*) Ví dụ 4: Giải hệ phương trình trên bằng phương pháp lặp đơn với ba
bước lặp
1 2 3
1 2 3
1 2 3
1,02 0,05 0,1 0,795
0,11 1,03 0,05 0,849
0,11 ,12 1,04 1,398
x x x
x x x
x o x x
− − =


− + − =


− − + =

Giải
Hệ

   
 ÷  ÷
 ÷  ÷
⇔ = − +
 ÷  ÷
 ÷  ÷
 ÷  ÷
 ÷  ÷
−
   
   
3
1
0,17
ij
j
b
=
=
∑
,
3
1
0,19
ij
j
b
=
=
∑

k k k k
x x x x
x x x x
x x x x
+
+
+

= − + + +

= − + +


= + − +

Chọn X
o
=
0,8
0,85
1,4
 
 ÷
 ÷
 ÷
 
1
2
3
0,02.0,08 0,05.0,85 0,1.1, 4 0,795 0,962

=

=


=

Và
3
1
3
2
3
3
0,98
1,004
1,563
x
x
x

=

=


=

sai số X
3

−
−
−

= ±

= ±


= ±

*) Ví dụ 5: Giải hệ
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
20,9 1,2 2,1 0,9 21,7
1,2 21, 2 1,5 2,5 27,46
2,1 1,5 19,8 1,3 28,76
0,9 2,5 1,3 32,1 49,72
x x x x
x x x x
x x x x
x x x x
+ + + =


+ + + =



x x x x x
x x x x

= − − − +



= − + − − +




= − − + − +



= − − − +


4
1
0,2
ij
j
b
=
∑
;
,
4

1
k
k k
X BX g
+
= +

k
1
k
x
2
k
x
3
k
x
4
k
x

0 1,04 1,3 1,45 1,55
1 0,75 0,95 1,14 1,36
2 0,8106 1,.118 1,2117 1,4077
3 0,7978 0,9977 1,1975 1,3983
4 0,8004 1,0005 1,2005 1,4003
5 0,7999 0,9999 1,1999 1,3999

Chọn x tuỳ ý
X

x
x
−
−
−
−

= ±

= ±


= ±


= ±

Phương pháp Jacobi:
Ma trận A=
( )
ij
1
n
a
gọi là ma trận đường chéo trội nếu 2 điều kiện dưới đây
thỏa mãn :
c
1
.
1, ,i n∀ =

ii
a
x .
a
i
j
i j
ii
b
x
a
≠
⇒ = − +
∑
Ta được hệ X= BX + g với
i
i
ii
b
g
a
=
B= (b
ij
) trong đó
ij
ij
ii
0;
;

<
∑
ij
ax( b ) 1B m= <
∑
nếu phép lặp X
k+1
= BX
k
+ g hội tụ
*) Ví dụ 6: Giải hệ phương trình sau:
1 2 3
1 2 3
1 2 3
5 2
5 3
5 4
x x x
x x x
x x x
+ + =


+ + =


+ + =

Giải :
16

= − − +



⇔ = − + − +



= − − + +


B=
1 1
0
5 5
1 1
0
5 5
1 1
0
5 5
 
− −
 
 
 
− −
 
 
 

Sai số X
3
- X
4
= ( -0,04,-0,0384-0,0368)

2
3 4
0,04 4.10X X
−
− = =

2
0,4
.4.10 ,026667
1 0,4
X o
α
−
− <
−
;
Vậy nghiệm của hệ là :
1
2
3
0,16 0,026667
0,4176 0,026667
0,6672 0,026667
x

b
b b b
 
 ÷
 ÷
 ÷
 ÷
 
B
2
=
11 12 1
12 2

0

0 0
n
n
nn
b b b
b b
b
 
 ÷
 ÷
 ÷
 ÷
 


+ + +
= =
= + +
∑ ∑
(1.10)
Định lý: phương pháp Seidel (1.10) hội tụ nếu
1B <
Chứng minh:
Do
1B <
nên TX = BX + g là ánh xạ co
⇒
! :T
α α α
∃ =
với
1
2

n
α
α
α
α
 
 ÷
 ÷
=
 ÷
 ÷

1,
ax
k
k j j
j n
X M x
α α
+
+
=
− = −
;
1,
ax
k
k j j
j n
X M x
α α
=
− = −1
1
k
i ij k ij k
j i j i
x b X b X
α α α

, 1,
k
i i i k i k
X X X i n
α γ α β α
+
+
⇒ − ≤ − + − ∀ =
Gọi i
o
là chỉ số sao cho
1 1
1
i=1,n
ax
o
k k
i o i i k
X M X X
α α α
+ +
+
− = − = −
1
1 1
o o o
k
k i i k i k
X X X X
α α γ α β α

M
ν
γ
=
−

Xét
( )
2
1
.
1 1 1
i i i
i i i i i i i
i i
i i i
γ β γ
β β β γ γ γ β
β γ
γ γ γ
− −
− + − −
+ − = =
− − −
Do
,0 1 1 0; 1
i i i i i
o
β γ γ γ β
< < < ⇒ − > + <

i n
i
M
β
ν
γ
=
⇒ = <
−
Vậy
2
1 1

k
k k k o
X X X X
α ν α ν α ν α
+ −
− ≤ − ≤ − ≤ ≤ −
Do
1
ν
<
nên
0
k
k
ν
→∞
→

+
thì không cần sử dụng
1
k
x
, lúc đó bỏ số
1
1
k
x
+
vào ô nhớ của
1
k
x
để tính
1
2
k
x
+

…
*) Ví dụ 7: Giải hệ ( VD5 dùng phương pháp lặp đơn)

1 2 3
1 2 3
1 2 3
1,02 0,05 0,1 0,795
0,11 1,03 0,05 0,849


= + − +


0,02 0,05 0,1
0,11 0,03 0,05
0,11 0,12 0,04
B
−
 
 ÷
⇒ = −
 ÷
 ÷
−
 
19
B
1
=
0 0 0
0,11 0 0
0,11 0,12 0
 
 ÷
 ÷
 ÷
 
B
2

( 0,02 0,05 0,1 ) 0,795
0,11 ( 0,03 0,05 ) 0,849
0,11 0,12 0,04 1,389
k k k k
k k k k
k k k k
x x x x
x x x x
x x x x
+
+ +
+ + + +

= − + +

⇔ = + − + +


= + − +


1 2 3
0 0,8 0,85 1,4
1 0,9615 0,9999265 1,56767
2 0,9825 1,00548 1,564025

k k k
k x x x
3.3 Phương pháp Gauss-Seidei
Là phương pháp Seidel áp dụng cho hệ phương trình với ma trận đường

= − − +


⇔ = − +


= − − +

Ta có B
0 0,1 0,1
0,2 0 0,1
0,2 0,2 0
− −
 
 ÷
− −
 ÷
 ÷
− −
 
B
1
=
0 0 0
0,2 0 0
0,2 0,2 0
 
 ÷
−
 ÷

3 1 2
0,1 0,1 1,2
0,2 0,1 1,3
0,2 0,2 1,4
k k k
k k k
k k k
x x x
x x x
x x x
+
+ +
+ + +

= − − +

⇔ = − − +


= − − +

20
k
1
1
k
x
+
1
2

for j:= 1 to n do
read(f,a[i,j]);
for i:= 1 to n do
read(f,b[i]);
close(f);
end;
Begin
nhap;
for k:=1 to n do
for i:= k+1 to n do
begin
if a[k,k] <> 0 then
p[i] := a[i,k]/a[k,k];
for j:=k+ 1 to n do
a[i,j]:= a[i,j] - p[i]*a[k,j];
b[i]:= b[i]-p[i]*b[k];
end;
if a[n,n] <> 0 then
22
x[n]:=b[n]/a[n,n];
for i:= n-1 downto 1 do
begin
s:=b[i];
for j:=i+1 to n do
s:=s-a[i,j]*x[j];
if a[i,i] <> 0 then
x[i]:=s/a[i,i];
end;
for i:=1 to n do
write(x[i]:10:3);

Tuy nhiên đối với hệ có nghiệm cụ thể thì sử dụng Pascal việc nhập
ma trận chính xác hơn và cho kết quả nhanh hơn sử dụng Maple 12. Ta xét
tiếp ví dụ 10 sau đây.
*) Ví dụ 10: Giải hệ đại số tuyến tính
A x = u
trong đó
24
Giải:
1.Dùng Maple 12
[>
[>
[>
[>
2.Sử dụng LT Pascal
Nhập ma trận lưu vào C.PAS
5
1 1 -1 1 -1
2 2 1 -9 1
3 -1 1 -8 -4
6 1 1 1 -5
25