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 - Phan Thị Hà

 
(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