Bài giảng Phương pháp số - Chương 2: Các phương pháp số trong đại số tuyến tính

Chương 2: Các phương pháp số trong đại số tuyến tính 
CHƯƠNG 2 
CÁC PHƯƠNG PHÁP SỐ TRONG ĐẠI SỐ TUYẾN TÍNH 
MỤC ĐÍCH, YÊU CẦU: 
Sau khi nghiên cứu chương 1, yêu cầu sinh viên: 
1. Hiểu và nắm được các phương pháp tìm nghiệm đúng, nghiệm xấp xỉ của hệ phương 
trình tuyến tính. 
2. Biết cách ứng dụng các phương pháp trên vào việc tính định thức của ma trận, tìm ma 
trận nghịch đảo, giải quyết các bài toán thực tế. 
3. Biết cách đánh giá sai số của từng phương pháp 
2.1. MA TRẬN VÀ ĐỊNH THỨC 
2.1.1. Ma trận 
Cho ma trận chữ nhật A cấp m x n: 
 a11 a12 ... a1n 
 a21 a22 ... a2n 
A = . . ... . 
 am1 am2 ... amn 
ở đây aij là các số thực. Ma trận này có m hàng và n cột. Khi m = n ta có ma trận cấp nxn 
và được gọi tắt là ma trận vuông cấp n. 
Ma trận vuông cấp n mà mọi phần tử nằm ngoài đường chéo chính bằng 0, tức là aij = aji = 0 
với i ≠ j, được gọi là ma trận đường chéo. Nếu ma trận đường chéo có aii = 1 thì ta gọi A là ma trận 
đơn vị và ta thường ký hiệu là E hoặc I. 
Ma trận vuông A được gọi là ma trận tam giác trên, nếu A có dạng 
 a11 a12 ... a1n 
 0 a22 ... a2n 
A = . . ... . 
 0 0 ... ann 
 13
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
Tương tự, ma trận vuông A được gọi là ma trận tam giác dưới, nếu A có dạng: 
 a11 0 ... 0 
 a21 a22 ... 0 
A = . . ... . 
 an1 an2 ... ann 
Ma trận chữ nhật AT cấp n x m được gọi là ma trận chuyển vị của ma trận A cấp m x n nếu: 
 a11 a21 ... am1 
 a12 a22 ... am2 
AT = . . ... . 
 a1n a2n ... amn 
2.1.2. Định thức của ma trận 
Trước khi đưa ra định nghĩa định thức của ma trận, chúng tôi giới thiệu khái niệm hoán vị 
chẵn, hoán vị lẻ của một tập hợp n số nguyên {1, 2, ... , n}. 
Cho α = (i1, i2,..., in) là một hoán vị của tập {1,2,...,n}. Ta xét tất cả các cặp (ik, ih), trong đó 
k ih thì ta gọi cặp (ik, ih) là cặp ngược, tức là các giá trị ik, ih được sắp xếp ngược với 
k,h. Nếu trong α số cặp ngược là chẵn thì ta gọi α là hoán vị chẵn, ngược lại thì ta gọi α là hoán 
vị lẻ. 
Với mỗi ma trận vuông A cấp n: 
 a11 a12 ... a1n 
 a21 a22 ... a2n 
A = . . ... . 
 an1 an2 ... ann 
tồn tại một số thực được gọi là định thức của ma trận A, ký hiệu là det A, được xác định 
bởi công thức: 
det A = ∑ s(i
α
1, i2,..., in) (2.0) 
nniii
aaa ...
21 21
với α = (i1, i2,..., in) chạy trong tập tất cả các hoán vị của tập {1,2,...,n}, và 
s(i1, i2,..., in) = 
 1 nếu α là hoán vị chẵn
-1 nếu α là hoán vị lẻ 
 14 
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
Định thức của ma trận còn được ký hiệu là 
 a11 a12 ... a1n 
 a21 a22 ... a2n 
A = . . ... . 
 an1 an2 ... ann 
Với mỗi ma trận chữ nhật A cấp m x n bất kỳ ta có thể tính định thức của tất cả các ma 
trận con vuông cấp k, với k ≤ min (m, n). Nếu tồn tại một số r sao cho có một ma trận con cấp r 
có định thức khác 0, còn mọi ma trận con vuông cấp lớn hơn r đều bằng 0 thì ta nói rằng r là hạng 
của ma trận A. 
Các phép biến đổi sơ cấp sau đây không làm biến đổi hạng của ma trận: 
• Đổi chỗ 2 hàng hoặc 2 cột bất kỳ. 
• Nhân một hàng hay một cột bất kỳ với một số khác không. 
• Cộng các thành phần tương ứng của 2 hàng hoặc hai cột bất kỳ. 
Các phép biến đổi sơ cấp sẽ được sử dụng để tính định thức của ma trận và tìm nghiệm của 
hệ phương trình tuyến tính. 
Ma trận E được gọi là ma trận đơn vị cấp n nếu E là ma trận vuông cấp n và E có dạng 
 1 0 ... 0 
 0 1 ... 0 
E = . . ... . 
 0 0 ... 1 
2.1.3. Các phương pháp tính định thức 
a. Tính định thức dựa trực tiếp vào định nghĩa 
Ta có thể dùng (2.0) để tính định thức của một ma trận trên máy tính. Tuy nhiên cách tính 
này đòi hỏi khoảng c*n! phép tính. Đây là con số khổng lồ với n không lớn lắm. Ví dụ với máy 
tính hiện đại nhất hiện nay cũng cần hàng triệu năm để tính định thức của ma trận cấp n = 25. 
b. Tính định thức dựa vào công thức khai triển theo hàng 
Cho A là ma trận vuông cấp n và aij là một phần tử bất kỳ của nó. Định thức của ma trận 
con cấp n-1 sau khi “xóa” hàng thứ i và cột thứ j đi và không thay đổi vị trí các thành phần còn 
lại, được gọi là minor của phần tử aij , và được ký hiệu là Mij. Giá trị Aij = (-1)i+j Mij được gọi là 
phần bù đại số của phần tử aij. Ta có các công thức sau để tính định thức ma trận vuông cấp n 
thông qua việc tính định thức của các ma trận con cấp bé hơn: 
Khai triển định thức theo hàng thứ i: 
 det A = ∑ a
=
n
j 1
ij Aij 
 15
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
Khai triển định thức theo cột thứ j: 
 det A = ∑ a
=
n
i 1
ij Aij 
Áp dụng các công thức trên đây ta có thể dùng thuật toán đệ quy sau đây để tính định thức 
của ma trận vuông cấp n : 
Nếu n = 1 : A11 = 1; det A = a11 A11
n > 1: det A = a∑
=
n
j 1
1j A1j 
Tuy nhiên, cũng như cách tính trực tiếp, cách tính này cần khoảng c*n! phép tính, và như 
vậy không thể thực hiện được trên máy tính hiện đại nhất hiện nay dù chỉ với n không lớn lắm. Rõ 
ràng việc phân tính thuật toán giúp chúng ta đánh giá được thời gian tính toán trên máy tính và 
nếu thời gian đó là quá lớn thì chúng ta khỏi phải tốn công vô ích viết chương trình và chạy thử. 
c. Tính định thức bằng cách chuyển ma trận về dạng tam giác trên 
Ta sẽ biến đổi để đưa ma trận A về dạng ma trận tam giác trên 
 b11 b12 ... b1n 
 0 b22 ... BB2n 
B = . . ... . 
 0 0 ... bmn 
Vậy det A=det B = b11 b22...bnn 
2.1.4. Ma trận nghịch đảo 
Ma trận nghịch đảo của một ma trận vuông A cấp n là ma trận được ký hiệu là A-1, thoả 
mãn điều kiện 
 A-1A = A A-1 = E 
Trong đó E là ma trận đơn vị. Có thể chứng minh rằng để thỏa mãn điều kiện trên thì bắt 
buộc A-1 phải là ma trận vuông, và ma trận đảo nếu tồn tại là duy nhất. 
Điều kiện tồn tại của ma trận nghịch đảo: Ma trận vuông A cấp n có ma trận nghịch đảo 
khi và chỉ khi det A ≠ 0. 
Cách tính ma trận nghịch đảo: 
Gọi Aij là phần bù đại số của phần tử aij , khi đó ta có: 
 A11 A21 ... An1 
 A12 A22 ... An2 
A-1 = 
Adet
1 
. 
. 
... 
. 
 A1n A2n ... Ann 
 16 
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
Tuy nhiên công thức này chỉ có ý nghĩa lý thuyết, không thể áp dụng để tính trực tiếp ma 
trận đảo trên máy tính được vì số phép tính đòi hỏi quá lớn. 
Trong phần sau ta sẽ áp dụng phương pháp khử Gauss-Jordan để tính ma trận nghịch đảo 
với số phép tính nhỏ hơn nhiều (khoảng n3) 
2.2. HỆ PHƯƠNG TRÌNH ĐẠI SỐ TUYẾN TÍNH 
Xét một hệ phương trình gồm n phương trình tuyến tính với n ẩn số x1, x2,...,xn như sau: 
 a11x1 + a12x2 + . . . + a1nxn = b1 
 a21x1 + a22x2 + . . . + a2nxn = b2 
 . . . . . . . . . . . . . . . . (2.1) 
 an1x1 + an2x2 + . . . + annxn = bn 
Hệ phương trình này có thể viết dưới dạng ma trận Ax = b, trong đó 
A = , x = , b = 
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
nnnn
n
n
aaa
aaa
aaa
...
......
...
...
21
22221
11211
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
nx
x
x
.
2
1
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
nb
b
b
.
2
1
Nếu det A ≠ 0 thì nghiệm của hệ (2.1) có thể tính theo công thức x = A-1b. Áp dụng công thức 
tính ma trận đảo ta có thể biến đổi và dẫn đến lời giải được diễn tả bằng định lý Cramer như sau: 
Định lý Cramer. Gọi Aj là ma trận nhận được từ ma trận A bằng cách thay cột thứ j bằng 
cột b, khi đó hệ (2.1) có nghiệm duy nhất và xj được tính bởi công thức 
 xj = A
Aj
det
det
Tuy nhiên trong thực hành người ta không dùng công thức này để tính nghiệm vì số phép 
tính quá lớn. Người ta dùng những phương pháp hữu hiệu hơn mà chúng tôi sẽ giới thiệu sau đây. 
2.2.1. Phương pháp trực tiếp giải hệ phương trình tuyến tính 
Giả sử ta giải hệ phương trình(2.1) 
a. Phương pháp khử Gauss 
Phương pháp khử Gauss dùng cách khử dần các ẩn để đưa hệ phương trình đã cho về một 
dạng tam giác trên rồi giải hệ tam giác này từ giới lên trên, không phải tính một định thức nào 
Phương pháp này được thực hiện qua các bước sau: 
Quá trình xuôi: 
- Bước 0: Dùng phương trình đầu tiên để khử x1 trong n-1 phương trình còn lại. Giả sử a11≠0. 
(Để cho công thức đơn giản , trước khi khử ta có thể chia phương trình thứ nhất cho a11 ). 
Cụ thể để khử x1 ở hàng thứ k( k=2,3,n) ta phải tính lại các hệ số akj ở hàng thứ k 
(j=1,2,..n+1) như sau: akj=akj-a1j*ak1/a11 
. . . 
 17
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
- Bước 1: Dùng phương trình thứ 2 để khử x2 trong n-2 phương trình còn lại phía sau. Giả 
sử a22≠0. (Để cho công thức đơn giản, trước khi khử ta có thể chia phương trình thứ hai 
cho a22). 
Cụ thể để khử x2 ở hàng thứ k (k=3,4,n) ta phải tính lại các hệ số akj ở hàng thứ k 
(j=2,..n+1) như sau: akj=akj-a2j*ak2/a22 
 . 
- Bước i: Dùng phương trình i để khử xi trong các phương trình thứ i+1,i+2, ..., n. Giả 
sử aii≠0. Để cho công thức đơn giản, trước khi khử ta có thể chia phương trình thứ i cho 
aii). 
Cụ thể để khử xi ở hàng thứ k (k=i+1,n) ta phải tính lại các hệ số akj ở hàng thứ k 
(j=i,..n+1) như sau: akj=akj-aij*aki/aii 
- Bước n-1: Dùng phương trình thứ n-1 để khử xn-1 trong phương trình thứ n.Giả sử an-1 n-1≠0. 
(Để cho công thức đơn giản, trước khi khử ta có thể chia phương trình thứ n-1 cho an-1 n-1) 
 Cụ thể để khử xn-1 ở hàng thứ n ta phải tính lại các hệ số anj ở hàng thứ n (j=n-1,n,n+1) 
như sau: anj=anj-an-1j*an-1i/an-1n-1 
Kết thúc quá trình khử. 
Chú ý: 
Trong quá trình giải xuôi ta giả thiết a11≠0, a22≠0,a33≠0,...,an-1 n-1≠0. Nếu 1 trong các hệ số 
đó bằng không thì quá trình không tiếp tục được. Lúc đó ta phải thay đổi cách tính. 
Giả sử khi khử x1 ta gặp a11=0 thì ta nhìn các hệ số a21, a31 ...an1 của x1 ở các phương trình 
phía dưói, nếu có hệ số nào khác không ta có thể lấy nó thay cho vai trò của a11 bằng cách hoán vị 
hai phương trình. Nếu tất cả các hệ số số a11, a21, a31 ...,an1 đều bằng không thì hệ đã cho suy biến. 
Vậy tốt nhất là trước khi khử x1 ta chọn trong các hệ số a11, a21, a31 ...,an1 hệ số có giá trị tuyệt đối 
lớn nhất làm trụ thứ nhất( gọi là trụ tối đại thứ nhất) rồi hoán vị hàng thứ nhất cho hàng có giá 
trị tuyệt đối lớn nhất). Tức là ta chọn hàng r sao cho: 
| ar1 | = max {| ak1 | / k=1,2, ... ,n} Sau đó ta đổi hàng r cho hàng 1. 
Tương tự trong các bước khử x2,... xn-1 , trước khi khử ta cũng tìm trụ tối đại: 
| ari | = max {| aki | / k=i,i+1, ... ,n} ( với i=2,3,,n-1) 
 Sau đó ta đổi hàng r cho hàng i. 
Sau khi thực hiện xong quá trình giải xuôi hệ phương trình (2.1) có dạng: 
Dạng1: Tại các bước (bước i) ta không chia cho hệ số aii
 a11x1 + a12x2 + . . . + a1nxn = b1 
 a22x2 + . . . + a2nxn = b2 
 . . . . . . . . . . . 
 ann xn = bn 
 18 
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
hoặc: Dạng 2: Tại các bước (bước i) ta chia cho hệ số aii: 
x1 + a12x2 + . . . + a1nxn = b1 
 x2 + . . . + a2nxn = b2 
 . . . . . . . . . . . 
 xn = bn 
Xuất phát từ phương trình thứ n ta lần lượt tính được các giá trị xi bằng các công thức của 
quá trình giải ngược sau: 
Quá trình giải ngược 
 xn = bn/ann hoặc ( xn=bn) 
 . . . 
 xi = (bi -( a∑
+=
n
ij 1
ijxj) )/aii ) hoặc (bi -( a∑
+=
n
ij 1
ijxj) ), i =n-1, n-2, ..., 1 
Để việc viết chương trình được đơn giản, khi cài đặt trên máy tính ta dùng một mảng a 
thay cho cả ma trận a và vec tơ b. Tức là 
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢
⎣
⎡
+
+
+
)1(,21
)1(,222221
)1(,111211
...
.......
...
...
nnnnnn
nn
nn
aaaa
aaaa
aaaa
 = 
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
nnnnn
n
n
baaa
baaa
baaa
...
.......
...
...
21
222221
111211
Ta áp dụng các phép biến đổi sơ cấp như vừa trình bày để biến đổi ma trận chữ nhật cấp 
nx(n+1) trên đây về dạng 
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢
⎣
⎡
+
+
+
)1(,
)1(,22
)1(,1112
'1...00
.......
''...10
''...'1
nn
nn
nn
a
aa
aaa
Ví dụ:Giải hệ phương trình sau bằng phương pháp khử Gauss: 
 2x1 + 3x2 +x3 = 11 
 -x1 + 2x2 -x3 = 0 
 3x1 + 2x3 =9 
Bước1: Hệ phương trình trên tương đương với: 
 h1=h3 
 h2=h2 
 h3=h1 
3x1 + 2x3 = 9 
-x1 + 2x2 -x3 = 0 
2x1 + 3x2 +x3 = 11 
 19
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
Bước 2: 
 h1=h1 
 h2=h2+h1/3 
 h3=h3-2*h1/3 
3x1 + 0 + 2x3 = 9 
 2x2 - x3/3 = 3 
 3x2 - x3/3 = 5 
 h1=h1 3x1 + 0 + 2x3 = 9 
3x2 - x3/3 = 5 
2x2 - x3/3 = 3 
 h2=h3 
 h3=h2 
Vậy 
 h1=h1 
 h2=h2 
 h3=h3-2*h2/3 
3x1 + 0 + 2x3 = 9 
 x2 - x3 /3 = 5 
 -x3/9 = -1/3 
x3=3 
x2=2 
x1=1 
Chương trình minh họa. 
 Sau đây là đoạn chương trình chính thể hiện (mô tả) thuật toán khử Gauss. 
/*Giai he phuong trinh tuyen tinh dung khu Gauss, ma tran vuong n, 
 cac phan tu cot thu n+1 la vecto b*/ 
/*Dua ma tran a ve dang tam giac tren Giai he phuong trinh tuyen tinh. 
 Tra ve gia tri true neu co nghiem */ 
int khugauss(kmatran a,double *x,int n) 
 { 
int i,j,k,h;double tmp,p;kmatran aa; 
 int n1=n+1; 
 for(i=1;i<=n;i++) 
 for(j=1;j<=n1;j++) aa[i][j]=a[i][j]; 
 for(i=1;i<=n;i++) //Vong lap cac buoc khu 
 {//Tim hang co phan tu dau lon nhat 
 h=i; 
 for(k=i+1;k<=n;k++) 
 if(fabs(a[k][i])>fabs(a[h][i]) {h=k;} 
 if(a[h][i])==0) {cout<<"Ma tran suy bien";delay(1000);return false;} 
 20 
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
 if(h!=i) //Doi hang i va hang h vi a[h][i] > a[i][i] 
 {int j;double tmp; 
 for(j=i;j<=n1;j++) 
 {tmp=a[i][j];a[i][j]=a[h][j];a[h][j]=tmp;} 
 } 
 //chuyen he so a[i][i] = 1 
 tmp=a[i][i]; 
 for(j=i;j<=n1;j++) a[i][j] = a[i][j]/tmp; 
 //Bat tinh lai cac hang 
 for(k=i+1;k<=n;k++) 
 {p=a[k][i]; 
 /*Vi ta biet a[k][i] =0 sau bien doi, 
 chi tinh tu a[k][i+1]*/ 
 for(j=i+1;j<=n1;j++) a[k][j]=a[k][j] - p*a[i][j]; 
 } 
 } 
 x[n]=a[n][n+1]; 
 for(i=n-1;i>=1;i--) 
 {double xx=0; 
 for(j=i+1;j<=n;j++) xx=xx+a[i][j]*x[j]; 
 x[i]=a[i][n+1]-xx;//b[i]-xx 
 } 
 //Dat cac gia tri phi duoi duong cheo chinh bang 0(phan nay khong can) 
 for(i=2;i<=n;i++) 
 for(j=1;j<i;j++) a[i][j]=0; 
 //Thu lai 
 kvecto bb; 
 for(i=1;i<=n;i++) 
 {bb[i]=aa[i][1]*x[1]; 
 for(j=2;j<=n;j++) bb[i]+=aa[i][j]*x[j]; 
 } 
 //Dua ket qua vao tep ketqua 
 return true; 
 } 
 21
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
b. Phương pháp khử Gauss-Jordan 
 Phương pháp khử Gauss-Jordan dùng cách khử dần các ẩn để đưa hệ phương trình đã cho 
về một dạng ma trận đường chéo rồi giải hệ phương trình này, không phải tính một định thức nào 
Phương pháp này được thực hiện qua các bước sau: 
- Bước 1: Dùng phương trình đầu tiên để khử x1 trong n-1 phương trình còn lại, cách làm 
tương tự như phương pháp khử để tính định thức... (Để cho công thức đơn giản, trước khi 
khử ta có thể chia phương trình thứ nhất cho a11). 
Cụ thể để khử x1 ở hàng thứ k( k=2,3,n) ta phải tính lại các hệ số akj ở hàng thứ k 
(j=1,2,..n+1) như sau: akj=akj-a1j*ak1/a11
. . . 
- Bước i: Dùng phương trình i để khử xi trong các phương trình thứ 1,2, i-1,i+1,i+2,...,n.. 
(Để cho công thức đơn giản , trước khi khử ta có thể chia phương trình thứ i cho aii) 
Cụ thể để khử xi ở hàng t ...  
Để phương pháp lặp hội tụ thì thường ma trận A phải thỏa mãn tính chéo trội của ma trận vuông. 
Định nghĩa: (Tính chéo trội của một ma trận vuông): Ma trận A với các thành phần aij được 
gọi là có tính chéo trội, nếu giá trị tuyệt đối của các phần tử nằm trên đường chéo chính lớn hơn 
tổng các giá trị tuyệt đối của các phần còn lại nằm cùng hàng, tức là 
 | aii | > | a∑
≠−
n
ijj ,1
ij |, i = 1, 2, . . ., n. (2.9) 
 Sau đây sẽ giới thiệu 2 phương pháp lặp đơn Jacobi và Gaus-Seidel 
c. Phương pháp lặp Jacobi 
Với giả thiết ma trận A có tính chéo trội, khi đó các hệ số aii ≠ 0, i = 1,2,...,n do đó ta có 
thể chia phương trình thứ i của hệ (2.1) cho aii và nhận được hệ tương tương 
x1 + 
11
12
a
a
x2 + 
11
13
a
a
x3 +. . . + 
11
1
a
a n xn = 
11
1
a
b
22
21
a
a
x1 + x2 + 
22
23
a
a
x3+. . . + 
22
2
a
a n xn = 
22
2
a
b
 . . . 
ii
i
a
a 1 x1 + 
ii
i
a
a 2 x2 +...+ 
ii
ii
a
a 1, − xi-1+ xi +
ii
ii
a
a 1, + xi+1. . . + 
ii
in
a
a
xn = 
ii
i
a
b
 . . . 
nn
n
a
a 1 x1 + 
nn
n
a
a 2 x2 +...+ 
nn
nn
a
a 1, − xn-1+ xn = 
nn
n
a
b
Từ đây ta có 
 x1 = - (0.x1 + 
11
12
a
a
x2 + 
11
13
a
a
x3 +. . . + 
11
1
a
a n xn ) + 
11
1
a
b
 x2 = - (
22
21
a
a
x1 + 0.x2 + 
22
23
a
a
x3+. . . + 
22
2
a
a n xn ) + 
22
2
a
b
 . . . 
 32 
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
 xi = - (
ii
i
a
a 1 x1 + 
ii
i
a
a 2 x2 +...+ 
ii
ii
a
a 1, − xi-1+ 0.xi +
ii
ii
a
a 1, + xi+1. . . + 
ii
in
a
a
xn ) + 
ii
i
a
b
 . . . 
 xn = - (
nn
n
a
a 1 x1 + 
nn
n
a
a 2 x2 +...+ 
nn
nn
a
a 1, − xn-1+ 0.xn ) + 
nn
n
a
b
Khi đó ma trận C, vectơ d là: 
C = -
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
0...
......
...0
...0
21
22
2
22
21
11
1
11
12
nn
n
nn
n
n
n
a
a
a
a
a
a
a
a
a
a
a
a
, d = 
⎟⎟
⎟⎟
⎟⎟
⎟⎟
⎠
⎞
⎜⎜
⎜⎜
⎜⎜
⎜⎜
⎝
⎛
nn
n
a
b
a
b
a
b
.
22
2
11
1
(Đến đây ta đã đưa hệ (2.4) về dạng (2.5) và dễ thấy rằng ma trận C thỏa mãn điều kiện lặp 
đơn, tức là ||C||∞ < 1.). 
Vậy đến đây ta tiếp tục áp dụng phương pháp lặp (2.6) để tính nghiệm ở các bước lặp như sau: 
Với vec tơ x(0) cho trước bất kỳ, ví dụ x(0) = θ (vec tơ 0) ta có thể tính các vec tơ x(k) tại 
bước lặp k bằng công thức x(k) = C x(k-1) + d , k =1, 2, ... 
Cụ thể hơn, nếu x(k) = (x1(k), x2(k), . . ., xn(k)) thì ta có 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
)(
)(
2
)(
1
.
k
n
k
k
x
x
x
 = -
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
0...
......
...0
...0
21
22
2
22
21
11
1
11
12
nn
n
nn
n
n
n
a
a
a
a
a
a
a
a
a
a
a
a
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
−
−
−
)1(
)1(
2
)1(
1
.
k
n
k
k
x
x
x
 + 
⎟⎟
⎟⎟
⎟⎟
⎟⎟
⎠
⎞
⎜⎜
⎜⎜
⎜⎜
⎜⎜
⎝
⎛
nn
n
a
b
a
b
a
b
.
22
2
11
1
Với từng thành phần xi(k) ta có 
xi(k) = - ∑
≠−
n
ijj ,1 ii
ij
a
a
xj(k-1) +
ii
i
a
b
 = 
iia
1 (bi - a∑
≠−
n
ijj ,1
ij xj(k-1)) (2.10) 
 i = 1, 2, . . ., n, k = 1,2,... 
Điều kiện hội tụ, đánh gái sai số của phương pháp lặp Jacobi cũng giống với phương 
pháp lặp đơn. 
Ví dụ. Dùng phương pháp lặp Jacobi tìm nghiệm gần đúng của hệ phương trình: 
 4x1 + 0.24x2 - 0.08x3 = 8 
 0.09x1 + 3x2 - 0.15x3 = 9 
 0.04x1 - 0.08x2 + 4x3 = 20 
 33
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
Giải. (1).Có thể thấy rằng ma trận các hệ số của hệ phương trình trên đây thỏa mãn tính 
chéo trội, do đó ta có thể biến đổi hệ này để áp dụng phương pháp lặp Jacobi. Chia hai vế phương 
trình đầu tiên cho 4, hai vế phương trình thứ hai cho 3 và hai vế của phương trình thứ ba cho 4 
rồi biến đổi thích hợp ta nhận được: 
 x1 = 2 - 0.06x2 +0.02x3
 x2 = 3 - 0.03x1 + 0.05x3
 x3 = 5 - 0.01x1 + 0.02x2
hay 
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
3
2
1
x
x
x
 = + = Cx + d 
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−
−
002.001.0
05.0003.0
02.006.00
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
3
2
1
x
x
x
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
5
3
2
||C||∞ = max(0 + 0.06 + 0.02, 0.03 + 0 + 0.05, 0.01 + 0.02 + 0) = 
 = max(0.08,0.08,0.03) = 0.08 <1 
(2) Chọn x(0) = (2,3,5)T, rồi tính x(1), x(2),... theo công thức (2.10) với lưu ý aii =1 ta được 
bảng kết quả sau: 
k x1(k) x2(k) x3(k)
0 
1 
2 
3 
2 
1.92 
1.9094 
1.909228 
3 
3.19 
3.1944 
3.194948 
5 
5.04 
5.0446 
5.044794 
(3) Xem x(3) là nghiệm gần đúng cần tìm, ta có thể đánh giá sai x(3) với nghiệm đúng x* 
theo (2.10) như sau: ||x(3) - x*|| ≤ 
||||1
||||
C
C
− ||x
(3) - x(2)|| 
 ||x(3) - x(2)||∞ = |x
i
max i(3) - xi(2)| = max(0.000172, 0.000548, 0.000194) = 0.000548 
Như vậy 
 ||x(3) - x*||∞ ≤ 
08.01
08.0
− 0.000548 = 0.0000476 ≈ 0.00005 
d. Phương pháp lặp Gauss - Seidel 
Với giả thiết ma trận A có tính chéo trội. Từ công thức (2.10) ta thấy rằng phần tử thứ i 
của vec tơ nghiệm tại bước k được tính qua các phần tử ở các vị trí khác i trong bước k-1. 
Phương pháp Gauss-Seidel cải tiến phương pháp Jacobi bằng cách dùng ngay những kết quả vừa 
tính được cho các thành phần của nghiệm tại bước k để tính các thành phần khác của bước k, chỉ 
có những thành phần nào chưa được tính thì mới lấy ở bước k-1. Cụ thể hơn ta có tại các bước: 
(1) Giá trị x1(1) được tính qua các giá trị x2(0), x3(0), ... xn(0)
 34 
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
Giá trị x2(1) được tính qua các giá trị x1(1), x3(0), ... xn(0)
Giá trị x3(1) được tính qua các giá trị x1(1), x2(1),x4(0), ... xn(0)
. . . 
(h) Giá trị x1(h) được tính qua các giá trị x2(h-1), x3(h-1), ... xn(h-1)
Giá trị x2(h) được tính qua các giá trị x1(h), x3(h-1), ... xn(h-1)
Giá trị x3(h) được tính qua các giá trị x1(h), x2(h),x4(h-1), ... xn(h-1)
 . . . 
Với vec tơ x(0) cho trước bất kỳ, ví dụ x(0) = θ (vec tơ 0) ta có thể tính các vec tơ x(k) tại 
bước lặp k bằng công thức 
xi(k) = 
iia
1 (bi -( a∑−
−
1
1
i
j
ijxj(k) +∑
+−
n
ij 1
aijxj(k-1))) (2.11) 
 i = 1, 2, . . ., n, k = 1,2,... 
Trong công thức (2.11) chúng ta có thể không dùng chỉ số trên để chỉ ra rằng chúng ta chỉ 
dùng một mảng là vec tơ có n thành phần để lưu trữ nghiệm. Giá trị nào vừa được tính toán thì 
được lưu trữ ngay vào vị trí cũ và được dùng ngay trong công thức tính các giá trị khác. 
xi =
iia
1 (bi - a∑
≠−
n
ijj ,1
ij xj) 
i = 1, 2, . . ., n, k = 1,2,... 
Sự hội tụ của phương pháp Gause-Seidel 
 Điều kiện hội tụ của phương pháp lặp Gause- Seidel cũng giống với phương pháp lặp đơn. 
Như ta sẽ thấy trong ví dụ trong phần sau, phương pháp Gause- Seidel nói chung hội tụ nhanh hơn 
phương pháp lặp đơn. 
Ta có thể sử dụng các công thức sau để đánh giá sai số của phương pháp lặp Gause-Seidel: 
Gọi x* là nghiệm đúng của hệ phương trình và gọi 
pi = ∑ |c−
=
1
1
i
j
ij|, qi = ∑ |c
=
n
ij
ij| , μ = 
i
max
i
i
p
q
−1 
Khi đó ta có 
||x(k) - x*|| ≤ μ
μ
−1 ||x
(k) - x(k-1)|| (2.12) 
hoặc 
 ||x(k) - x*|| ≤ μ
μ
−1
k
||x(1) - x(0)|| (2.13) 
Ví dụ. Dùng phương pháp lặp Gause-Seidel tìm nghiệm gần đúng của hệ phương trình: 
4x1 + 0.24x2 - 0.08x3 = 8 
0.09x1 + 3x2 - 0.15x3 = 9 
 0.04x1 - 0.08x2 + 4x3 = 20 
 35
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
Giải. (1).Có thể thấy rằng ma trận các hệ số của hệ phương trình trên đây thỏa mãn tính 
chéo trội, do đó ta có thể biến đổi hệ này để áp dụng phương pháp lặp Jacobi. Chia hai vế phương 
trình đầu tiên cho 4, hai vế phương trình thứ hai cho 3 và hai vế của phương trình thứ ba cho 4 
rồi biến đổi thích hợp ta nhận được: 
 x1 = 2 - 0.06x2 +0.02x3
 x2 = 3 - 0.03x1 + 0.05x3
 x3 = 5 - 0.01x1 + 0.02x2
hay 
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
3
2
1
x
x
x
 = + = Cx + d 
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−
−
002.001.0
05.0003.0
02.006.00
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
3
2
1
x
x
x
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
5
3
2
||C||∞ = max(0 + 0.06 + 0.02, 0.03 + 0 + 0.05, 0.01 + 0.02 + 0) = 
 = max(0.08,0.08,0.03) = 0.08 <1 
(2) Chọn x(0) = (2,3,5)T, rồi tính x(1), x(2),... theo công thức (2.11) với lưu ý aii =1 ta được 
bảng kết quả sau: 
k x1(k) x2(k) x3(k)
0 
1 
2 
3 
2 
1.92 
1.9093489 
1.909199 
3 
3.1924 
3.194952 
3.1949643 
5 
5.044648 
5.0448056 
5.0448073 
Xem x(3) là nghiệm gần đúng cần tìm, ta có thể đánh giá sai số phạm phải của x(3) 
theo(2.12): ||x(k) - x*|| ≤ μ
μ
−1 ||x
(k) - x(k-1)|| 
Trong đó: 
||x(3) - x(2)||∞ = |x
i
max i(3) - xi(2)| = max(0.0001499,0.000123,0.0000017) = 
0.0001499 
μ = 
i
max
i
i
p
q
−1 = max(0.08,0.0515463,0) = 0.08 
Như vậy 
 ||x(3) - x*||∞ ≤ μ
μ
−1 ||x
(k) - x(k-1)|| ≤ 
08.01
08.0
− 0.00001499 ≈ 0.000013 
 Thuật toán Jacobi cũng tương tự như thuật toán Gauss-Seidel, nhưng thuật toán Gauss - 
Seidel có tốc độ hội tụ nhanh hơn. 
 36 
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
Chương trình minh họa. 
 Sau đây là đoạn chương trình chính thể hiện (mô tả) thuật toán lặp Gauss - Seidel 
/*Giai he phuong trinh tuyen tinh dung lap Gauss-Seidel, ma tran vuong n, 
 cac phan tu cot thu n+1 la vecto b*/ 
//=============================================== 
double kcach(double *x,double *y,int n) 
 {double tmp=0; 
 for(int i=1;i<=n;i++) tmp=tmp+fabs(x[i]-y[i]); 
 return tmp; 
 } 
//=============================================== 
int cheotroi(kmatran a, int n) 
 {double tmp;int i,j; 
 for(i=1;i<=n;i++) 
 {tmp=0; 
 for(j=1;j<=n;j++) {if(j!=i) tmp=tmp+fabs(a[i][j]);} 
 if(fabs(a[i][i])<=tmp) return false; 
 } 
 return true; 
 } 
//=============================================== 
/*Giai he phuong trinh tuyen tinh bang phep lap Gauss-Seidel. 
 Tra ve true neu co nghiem */ 
int gseidel(kmatran aa,double *x,int n) 
{int h,i,j,k;double tmp;kvecto z;kmatran a; 
 int n1=n+1; 
 for(i=1;i<=n;i++) 
 for(j=1;j<=n1;j++) a[i][j]=aa[i][j]; 
 if(!cheotroi(a,n)) 
 {cout<<endl<<"Khong phai cheo troi";delay(1000);return false;} 
 for(i=1;i<=n;i++) //chuyen ve dang he so a[i][i] == 1 
 {tmp=a[i][i]; 
 for(j=1;j<=n1;j++) a[i][j] = a[i][j]/tmp; 
 } 
 //Vong lap cac buoc khu 
 37
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
 for(i=1;i<=n;i++) {x[i]=0;z[i]=0;} 
 k=1; 
 while(true) 
 {for(i=1;i<=n;i++) 
 {tmp=0; 
 for(j=1;j<=n;j++) if(j!=i) tmp+=a[i][j]*x[j]; 
 x[i] = a[i][n+1]-tmp; 
 } 
 k++; 
 if(kcach(x,z,n)<epsi) break; 
 if(k>kmax) 
 {cout<<endl<<"Phep lap chua hoi tu";delay(1000);return(false);} 
 //Gan z = x va chuan bi sang vong lap tinh x 
 for(i=1;i<=n;i++) z[i]=x[i]; 
 } 
 //Thu lai 
 kvecto bb; 
 for(i=1;i<=n;i++) 
 {bb[i]=aa[i][1]*x[1]; 
 for(j=2;j<=n;j++) bb[i]+=aa[i][j]*x[j]; 
 } 
 //Dua ket qua vao tep ketqua 
 return true; 
) 
2.3. BÀI TẬP 
Bài 1. Tính và kiểm tra bằng chương trình định thức của ma trận 
A = 
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
1167
642
131
Bài 2. Tìm và kiểm tra bằng chương trình nghịch đảo của ma trận 
A = 
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−−
203
121
132
 38 
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
Bài 3. Tìm nghiệm hệ phương trình 
 2x1 + 3x2 +x3 = 11 
 -x1 + 2x2 - x3 = 0 
 3x1 +2x3 = 9 
 Bằng phương pháp khử Gauss và Jordan. Kiểm tra bằng chương trình. 
Bài 4. Giải bằng các phương pháp khử Gauss, khử Gauss-Jordan, phương lặp Jacobi và lặp 
Gauss-Seidel (nếu thỏa mãn điều kiện) hệ phương trình sau: 
A = = 
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
−
−
−
104753
.19112356
28371612
50136517
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
4
3
2
1
x
x
x
x
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
18
36
25
84
Kiểm tra trên máy tính và thông báo về khả năng giải được hay không các phương 
pháp trên. 
Bài 5. Giải bằng các phương pháp lặp hệ phương trình sau: 
 10x1 + 2x2 + x3 =9 
 2x1 + 20x2 - 2x3 = -44 
 -2x1 + 3x2 + 10x3 =22 
 39
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
TÓM TẮT NỘI DUNG CHƯƠNG 2 
Trong chương này sinh viên cần nắm vững ít nhất là các vấn đề sau: 
1. Phương pháp trực tiếp giải hệ phương trình tuyến tính 
a.Phương pháp khử Gauss 
Phương pháp khử Gauss dùng cách khử dần các ẩn để đưa hệ phương trình đã cho về một 
dạng tam giác trên rồi giải hệ tam giác này từ giới lên trên, không phải tính một định thức nào. 
b. Phương pháp khử Gauss-Jordan 
Phương pháp khử Gauss-Jordan dùng cách khử dần các ẩn để đưa hệ phương trình đã cho 
về một dạng ma trận đường chéo rồi giải hệ phương trình này, không phải tính một định thức nào. 
2. Phương pháp lặp giải hệ phương trình tuyến tính 
a. Phương pháp lặp đơn 
- Giả sử phải tìm nghiệm gần đúng của hệ phương trình tuyến tính (2.1) có dạng Ax=b. Đối 
với phương pháp lặp đơn, nói chung chúng ta phải đưa hệ (2.1) về dạng x=Cx+d.Trong đó ma trận 
C và vec tơ d được xây dựng từ A và b. Ma trận phải thoả mãn điều kiện ||C||<1. 
Để thực hiện phép lặp ta chọn một vec tơ ban đầu x(0), sau đó tính các x(i), i =1,2,... theo 
công thức lặp sau: x(i) = Cx(i-1) + d cho tới khi nào thảo mãn điều kiện dừng. 
- Sai số của phương pháp: 
||x(k) - x*|| ≤ 
||||1
||||
C
C
− ||x
(k) - x(k-1)|| 
hoặc 
 ||x(k) - x*|| ≤ 
||||1
||||
C
C k
− ||x
(1) - x(0)|| 
b. Phương pháp lặp Jacobi 
- Giả thiết ma trận A có tính chéo trội. Phương pháp lặp Jacobi sẽ có các bước lặp như : 
Với vec tơ x(0) cho trước bất kỳ, ví dụ x(0) = θ (vec tơ 0) ta có thể tính các vec tơ x(k) tại 
bước lặp k bằng công thức x(k) = C x(k-1) + d , k =1, 2, ... 
Cụ thể hơn, nếu x(k) = (x1(k), x2(k), . . ., xn(k)) thì ta có 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
)(
)(
2
)(
1
.
k
n
k
k
x
x
x
 = -
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
0...
......
...0
...0
21
22
2
22
21
11
1
11
12
nn
n
nn
n
n
n
a
a
a
a
a
a
a
a
a
a
a
a
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
−
−
−
)1(
)1(
2
)1(
1
.
k
n
k
k
x
x
x
 + 
⎟⎟
⎟⎟
⎟⎟
⎟⎟
⎠
⎞
⎜⎜
⎜⎜
⎜⎜
⎜⎜
⎝
⎛
nn
n
a
b
a
b
a
b
.
22
2
11
1
 40 
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Chương 2: Các phương pháp số trong đại số tuyến tính 
Với từng thành phần xi(k) ta có 
xi(k) = - ∑
≠−
n
ijj ,1 ii
ij
a
a
xj(k-1) +
ii
i
a
b
 = 
iia
1 (bi - a∑
≠−
n
ijj ,1
ij xj(k-1)) 
 i = 1, 2, . . ., n, k = 1,2,... 
- Điều kiện hội tụ, đánh gái sai số của phương pháp lặp Jacobi cũng giống với phương pháp 
lặp đơn. 
c.Phương pháp lặp Gauss – Seidel 
 - Giả thiết ma trận A có tính chéo trội. Phương pháp lặp Gauss - Seidel sẽ có các bước lặp 
như sau: 
Với vec tơ x(0) cho trước bất kỳ, ví dụ x(0) = θ (vec tơ 0) ta có thể tính các vec tơ x(k) tại 
bước lặp k bằng công thức : 
xi(k) = 
iia
1 (bi -( a∑−
−
1
1
i
j
ijxj(k) +∑
+−
n
ij 1
aijxj(k-1))) 
 i = 1, 2, . . ., n, k = 1,2,... 
 - Đánh giá sai số: 
pi = ∑ |c−
=
1
1
i
j
ij|, qi = ∑ |c
=
n
ij
ij| , μ = 
i
max
i
i
p
q
−1 
Khi đó ta có: 
||x(k) - x*|| ≤ μ
μ
−1 ||x
(k) - x(k-1)|| 
hoặc 
 ||x(k) - x*|| ≤ μ
μ
−1
k
||x(1) - x(0)|| 
 41
CuuDuongThanCong.com https://fb.com/tailieudientucntt