›
›

Bài giảng Phương pháp số - Bài 3: Ma trận và hệ phương trình tuyến tính

Download
BÀI 3  
MA TRẬN VÀ HỆ  
PHƯƠNG TRÌNH TUYẾN TÍNH  
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (1)  
1. HỆ PHƯƠNG  
TRÌNH TUYẾN TÍNH  
gồm m phương trình n  
ẩn là một hệ có dạng  
Nếu đặt  
a x a x   
...  
a x b  
11 1  
12 2  
1n n  
1
a x a x ...  
a x b  
21 1  
22 2  
2n n  
2
............................................  
a x a x ... a x b  
m1 1  
m2 2  
mm n  
m
a
   
b
x
a
a12 ... a1n  
     
1j  
   
1
1
11  
     
a2j  
b2  
x2  
a21 a22 ... a  
2n   
   
     
v j   
,(j1,2,...,n),b   
, x   
và A   
,
   
.  
     
... ... ... ...  
am1 am2 ... amn  
   
     
bm xn  
a
mj  
   
     
thì hệ trên còn có thể viết ở dạng vectơ cột  
x1v1 +x2v2 +…+ xnvn = b  
hay dạng phương trình ma trận Ax = b  
PHƯƠNG PHÁP SỐ-Bài 3  
2
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (2)  
2. HỆ DẠNG TAM GIÁC TRÊN VÀ CÁCH GIẢI  
Hệ dạng tam giác trên là hệ có dạng a11x1 + a12x2 +…+ a1nxn = b1  
trong đó a11, a22,…,ann ≠ 0  
a22x2 +…+ a2nxn = b2  
……  
Cách giải: giải ngược từ dưới lên  
annxn = bn  
void heTGiac(vector<vector<double> > a, vector<double> &x) {  
unsigned n = a.size();  
vector<double> y(n, 0); // y co n phan tu 0  
y[n-1] = a[n-1][n]/a[n-1][n-1];  
for (int i = n-2; i >= 0; i--) {  
double tong = 0.;  
for(unsigned j = i+1; j <= n-1; j++)  
tong = tong + a[i][j] * y[j];  
y[i] = (a[i][n] - tong) / a[i][i];  
}
x = y;  
}
PHƯƠNG PHÁP SỐ-Bài 3  
3
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (3)  
3. MỘT SỐ ĐỊNH LÍ VỀ NGHIỆM  
Định lí 4.1: Hệ Ax = b có nhiều nhất một nghiệm (tức là,  
nghiệm là duy nhất nếu tồn tại ) nếu và chỉ nếu hệ thuần nhất  
tương ứng Ax = 0 chỉ có nghiệm “tầm thường” x= 0.  
Định lí 4.2: Bất kì hệ PTTT thuần nhất nào với số phương  
trình ít hơn số ẩn đều có nghiệm không tầm thường (khác 0)  
Định lí 4.3 Nếu A là một ma trận cấp m × n và hệ Ax = b có  
nghiệm với mọi vectơ m chiều b, thì m ≤ n..  
Định lí 4.4 Cho A là ma trận cấp n × n. Các khẳng định sau  
đây là tương đương:  
(i) Hệ thuần nhất Ax = 0 chỉ có nghiệm tầm thường x = 0.  
(ii) Với mọi vế phải b, hệ Ax = b luôn có nghiệm.  
(iii) A là ma trận khả nghịch  
PHƯƠNG PHÁP SỐ-Bài 3  
4
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (4)  
4. LỜI GIẢI BẰNG SỐ CỦA HỆ PTTT Ax = b  
Xét các hệ PTTT có số phương trình đúng bằng số ẩn.  
Nếu A khả nghịch thì hệ có duy nhất nghiệm đối với mọi b  
Có hai loại phương pháp giải:  
Trực tiếp: là các phương pháp đưa ra nghiệm chính xác bởi  
một số hữu hạn các phép toán số học sơ cấp (khử Gauss).  
Các phương pháp trực tiếp thực hiện trên máy tính thường  
không đưa đến các nghiệm chính xác do các sai số làm tròn.  
Lặp: xuất phát với một xấp xỉ ban đầu và dùng một thuật  
toán đã được lựa chọn phù hợp, sẽ đưa ra các xấp xỉ liên tiếp  
ngày càng tốt hơn.  
Chỉ nhận được nghiệm gần đúng.  
PHƯƠNG PHÁP SỐ-Bài 3  
5
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (5)  
5. CÁC PHÉP BIẾN ĐỔI TƯƠNG ĐƯƠNG HỆ PTTT  
Định lí 4.7 Cho Ax = b là hệ PTTT, các xử lí hệ này bằng các  
phép toán sau đây dẫn tới các hệ tương đương:  
(i) Nhân một phương trình với một hằng số khác 0  
(ii) Cộng một phương trình đã nhân với một hằng số vào một  
phương trình khác  
(iii) Đổi chỗ hai phương trình  
Nhận xét: Nếu với k và i xác định mà akk ≠ 0 thì chúng ta có thể  
khử ẩn xk từ phương trình thứ i bất kì bằng cách cộng phương  
trình thứ k đã nhân với –(aik /akk) vào phương trình thứ i. Khi đó  
hệ phương trình hệ quả sau là tương đương với hệ ban đầu  
Ãx b  
.
PHƯƠNG PHÁP SỐ-Bài 3  
6
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (6)  
6. PHÉP KHỬ GAUSS: đưa hệ Ax = b, về hệ tam giác trên:  
Gọi W là ma trận cấp n x (n + 1) chứa ma trận vuông A ở n cột đầu và  
vectơ b ở cột cuối cùng.  
Với k = 1, …, n–1 lặp các công việc:  
Tìm hàng trụ i ≥ k gần hàng k nhất sao cho wik ≠ 0  
Nếu không có hàng i như vậy thì dừng (A không khả nghịch)  
Nếu tìm được hàng i, thì đổi chỗ hàng i với hàng ktrụ wkk  
Với i = k+1, ..., n, lặp các công việc sau (khử các pt dưới trụ)  
mi = wik / wkk là hệ số nhân cho hàng i  
Với j = k+1, …, n+1, lặp các công việc sau (biến đổi hàng i)  
wij = w ij – mi x wkj  
Nếu wnn = 0 thì dừng (A không khả nghịch)  
Nếu trái lại hệ tam giác trên Ux = y với  
w i j  
ij  
u   
ij  
0 i j  
và yj = wi,n+1 i = 1, …, n  
PHƯƠNG PHÁP SỐ-Bài 3  
7
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (7)  
6. PHÉP KHỬ GAUSS (tiếp)  
Ví dụ : Giải hệ PTTT sau:  
2x – 3y  
= 3  
4x – 5y + z = 7  
2x – y – 3z = 5  
Giải:  
Bước 1: Dùng trụ đầu tiên của hệ để khử những hệ số bên dưới  
trụ đó: m2 = 4/2 = 2, m3 = 2/2 = 1 lấy pt 2 trừ đi 2 lần pt 1, và  
pt 3 trừ đi 1 lần pt 1 ta được hệ:  
2x – 3y  
= 3  
1 y + z = 1  
2 y – 3z = 2  
Bước 2: Dùng trụ thứ hai để khử hệ số bên dưới nó: m3 = 2/1 = 2  
lấy pt 3 trừ đi 2 lần pt 2 ta được hệ 2x – 3y = 3  
1y + z = 1  
–5z = 0  
giải ngược từ dưới lên ta được: z = 0, y = 1, x = 3  
PHƯƠNG PHÁP SỐ-Bài 3  
8
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (8)  
void giaiGauss(vector<vector<double> > a) {  
unsigned i, j, k, n = a.size(); double t, m;  
for (k = 0; k < n–1; k++) { // BUOC KHU XUOI HE TAM GIAC TREN  
while (a[i] [k] == 0 && i < n) i++; // Tim hang i gan k nhat: a[i] [k]≠0  
if (a[i] [k] != 0 && i != k) {  
for (j = i; j <= n; j++) {  
// Doi cho hang i va hang k  
t = a[i] [j]; a[i] [j] = a[k] [j]; a[k] [j] = t;  
}
}
else if(a[i] [k] == 0) {  
// Ma tran A suy bien  
cout<<"He khong co duy nhat nghiem"<< endl;  
exit(1);  
}
for (i = k+1; i <= a.size()–1; i++) { // Tao ma tran dang tam giac tren  
m = a[i] [k] / a[k] [k];  
for (j = k+1; j <= a.size(); j++) a[i] [j] = a[i] [j] – m * a[k] [j];  
} }…… // BUOC QUET NGUOC - GIAI HE TAM GIAC TREN  
Độ phức tạp thời gian của thuật toán là O(n3)  
}
PHƯƠNG PHÁP SỐ-Bài 3  
9
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (9)  
7. GIẢI HỆ PTTT DẠNG 3 ĐƯỜNG CHÉO  
Ma trận A = (aij) cấp n có dạng ba đường chéo nếu aij = 0 bất cứ  
khi nào |i – j| > 1. Hệ PTTT 3 đường chéo có dạng  
d x u x  
b  
1
1 1  
1 2  
l x d x u x  
b  
2
2 1  
2 2  
2 3  
l x d x u x  
b  
3
3 2  
3 3  
3 4  
l x  
n1 n2  
d x  
u x b  
n1 n1  
n1 n  
n1  
l x  
n n1  
d x  
b  
n n  
n
2 1 0 0 1  
1 2 1 0 0  
0 1 2 1 0  
0 0 1 2 0  
Ví dụ: hệ PTTT bên phải là  
hệ ba đường chéo  
PHƯƠNG PHÁP SỐ-Bài 3  
10  
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (10)  
7. GIẢI HỆ PTTT DẠNG 3 ĐƯỜNG CHÉO  
Cho trước các hệ số li, di, ui và vế phải bi của hệ ba đường chéo  
lixi–1 + dixi + uixi+1 = bi, i = 1 , . . . , n (với l1 = un = 0)  
Bước 1: Với k = 2, …, n lặp các công việc sau đây  
Nếu dk−1 = 0, đó là dấu hiệu sai và dừng  
Trái lại, m = lk / dk–1 và tiếp tục tính  
dk = dk – m*uk–1  
bk = bk – m*bk–1  
Nếu dn = 0, đó là dấu hiệu sai và dừng  
Trái lại: xn = bn / dn  
Bước 2: Với k = n–1, …, 1 lặp các công việc sau  
bk uk*xk1  
xk   
dk  
Nhận xét: Độ phức tạp thời gian của thuật toán là O(n)  
PHƯƠNG PHÁP SỐ-Bài 3  
11  
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (11)  
7. GIẢI HỆ PTTT DẠNG 3 ĐƯỜNG CHÉO (tiếp)  
for (unsigned k=1; k<n; k++) {  
if (d[k-1] == 0) { cout << "Khong giai duoc" << endl; return; }  
else {  
double m = l[k] / d[k-1];  
d[k] = d[k] - m * u[k-1];  
b[k] = b[k] - m * b[k-1];  
}
}
If (d[n-1] == 0) {  
cout << "He khong co nghiem duy nhat" << endl; return; }  
else {  
x[n-1] = b[n-1] / d[n-1];  
for(int i = n - 2; i >= 0; i--) x[i] = (b[i] - u[i] * x[i+1]) / d[i];  
}
for (unsigned i = 0; i < n; i++)  
cout << "x[" << i + 1 << "]=" << x[i] << endl;  
PHƯƠNG PHÁP SỐ-Bài 3  
12  
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (12)  
8. CHIẾN LƯỢC XOAY  
Nhận xét:  
Thuật toán khử Gauss đưa ra lời giải sai cho ví dụ sau  
0.0003 x1 + 1.566 x2 = 1.569  
0.3454 x1 – 2.436 x2 = 1.018  
0.0003 x1 + 1.566 x2 = 1.569  
– 1805.42 x2 = – 1807.46  
Hệ này có nghiệm đúng là x1= 10, x2 = 1, nhưng phép khử Gauss  
đưa ra x2 =1.001; x1 = 4.780 do trụ a11 = 0.0003 “rất nhỏ” so với a12  
Nếu lấy a12 làm trụ, ta có nghiệm đúng!  
Phân tích  
Trong bước khử Gauss đưa hệ Ax = b về hệ tam giác trên Ux = y  
sử dụng ma trận W cấp n × (n + 1) ta đã tìm các hàng trụ ở các  
bước lặp k = 1, …, n–1 theo tiêu chí:  
hàng trụ i ≥ k gần hàng k nhất sao cho wik ≠ 0  
PHƯƠNG PHÁP SỐ-Bài 3  
13  
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (13)  
8. CHIẾN LƯỢC XOAY (tiếp)  
Xoay theo tỉ lệ riêng: Ở lần lặp thứ k của phép khử Gauss  
• Tính “cỡ” di của hàng i của ma trận A, với i = k, . . . , n.  
di  
| aij |  
max  
kjn  
• Chọn ra phương trình xoay là một trong các phương trình  
trong n – k ứng cử viên còn lại mà hệ số của xk có giá trị tuyệt đối  
lớn nhất so với cỡ của phương trình đó Trong thuật toán Gauss,  
điều này có nghĩa là số nguyên j được lựa chọn là số nguyên nằm  
giữa k và n (thường là số nhỏ nhất) sao cho tỉ lệ riêng  
| w jk |  
d j  
| wik |  
di  
với mọi i = k, …, n  
PHƯƠNG PHÁP SỐ-Bài 3  
14  
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (14)  
9. PHÂN TÍCH MA TRẬN THÀNH TÍCH − GIẢI HỆ PTTT  
Sử dụng phép khử Gauss, không đổi chỗ các hàng, giải hệ Ax = b  
Bước 1: Phân tích A = LU, với U là ma trận tam giác trên, L là ma  
trận tam giác dưới, chứa các hệ số nhân của lần lặp thứ k  
w m , i k  
ik  
ik  
mik a(k1) / a(k1) ,  
ik  
kk  
l 1,  
i k  
i k  
ik  
k 1,
,n 1;i k  
0,  
Bước 2: - Giải hệ tam giác dưới tìm được y  
Ly b* (bp ),i 1,,n  
Vector p = (pi), i=1, …,n dùng để lưu thay đổi thứ tự của các hàng  
i
- Giải hệ tam giác trên Ux = y tìm được x  
PHƯƠNG PHÁP SỐ-Bài 3  
15  
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (15)  
9. PHÂN TÍCH MA TRẬN THÀNH TÍCH − GIẢI HỆ PTTT  
THUẬT TOÁN THÉ XUÔI VÀ KHỬ NGƯỢC  
PHA 1: Biến đổi ma trận A ban đầu về tích các ma trận tam giác  
Với k = 1, …, n–1 lặp các công việc:  
Tìm hàng trụ i ≥ k gần hàng k nhất sao cho nó có tỉ lệ riêng lớn nhất  
Nếu không có hàng i như vậy thì dừng (A không khả nghịch)  
Trái lại, thì đổi chỗ 2 hàng i và k, nếu i ≠ k, lưu thứ tự p mới của b  
Với i = k+1, ..., n, lặp các công việc (khử các phần tử dưới trụ):  
m = aik / akk (= Giá trị cần khử ở hàng i / Điểm trụ ở hàng trụ k)  
Với j = k+1, …, n-1, lặp các công việc (giữ nguyên vế phải):  
aij = aij – m x akj  
Gán aik = m  
PHƯƠNG PHÁP SỐ-Bài 3  
16  
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (16)  
9. PHÂN TÍCH MA TRẬN THÀNH TÍCH - GiẢI HỆ PTTT  
THUẬT TOÁN THÉ XUÔI VÀ KHỬ NGƯỢC  
PHA 2: Giải hệ tam giác dưới Ly = b* tìm y (L có đường chéo =1)  
Với k = 1, …, n lặp lại việc gán  
k1  
yk bp akj yj  
k
j1  
Giải hệ tam giác trên Ux = y tìm được x  
Với k = n, n–1, …, 1 lặp lại việc gán  
n
y a x  
k
kj j  
jk 1  
xk   
akk  
PHƯƠNG PHÁP SỐ-Bài 3  
17  
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (17)  
9. PHÂN TÍCH MA TRẬN THÀNH TÍCH − GIẢI HỆ PTTT  
Ví dụ 1:  
1 2  
Giải hệ u + 2v = 5  
   
A   
   
4u + 9v = 21  
4 9  
   
với hệ số nhân là 4, lưu trong L. Vế phải được dùng để tìm y  
1 0  
5
5
     
   
y   
y   
Giải hệ tam giác dưới Ly = b:  
     
   
4 1  
     
21  
1
   
1 2  
5
3
     
   
x   x   
Giải hệ tam giác trên Ux = y:  
     
   
0 1  
     
1
1
   
PHƯƠNG PHÁP SỐ-Bài 3  
18  
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (18)  
9. PHÂN TÍCH MA TRẬN THÀNH TÍCH − GIẢI HỆ PTTT  
Ví dụ 2: Giải hệ Ax = b PHA 1  
2 3 0 3  
3
   
   
| ai1 | | a21 | 4  
  i 2  
k 1xét A 4 5 1 7 d 5 max  
   
1i3  
di  
d2  
5
   
2 1 3 5  
3
   
4 5 1 7  
4 5 1 7  
1
2
l   
21  
1  
1
2
1
A* 2 3 0 3   
-
2 3  
-7  
5
2
2
1
2
l31   
1
2  
3
2 1 3 5  
2
4 5 1 7  
1 0 0  
1  
1  
1
2
1
k 2 hàng tru i 2 l32 - 3   
-
2 3 L   
1 0  
2
2
1
2  
1
2  
- 3 -5 5  
3 1  
PHƯƠNG PHÁP SỐ-Bài 3  
19  
HỆ PHƯƠNG TRÌNH TUYẾN TÍNH (19)  
9. PHÂN TÍCH MA TRẬN THÀNH TÍCH − GIẢI HỆ PTTT  
Ví dụ 2:  
Giải hệ Ly = b* với  
PHA 2  
1 0 0 7  
7
   
   
1  
1
   
L |b * 1 0 3 y    
   
2  
2
   
1
- 3 1 5  
0
   
2
Giải hệ Ux = y với  
4 5 1 7  
3
   
   
U | y  
0 - 1 1 1 x 1  
   
2
2
2
   
0 0 -5 0  
0
   
PHƯƠNG PHÁP SỐ-Bài 3  
20  
Tải về để xem bản đầy đủ
pdf 44 trang Mãnh Khiết 15/01/2024 11320 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Phương pháp số - Bài 3: Ma trận và hệ phương trình tuyến tính", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_phuong_phap_so_bai_3_ma_tran_va_he_phuong_trinh_tu.pdf