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

CHƯƠNG 5. PHƯƠNG PHÁP số TRONG
ĐẠI SỐ TUYẾN TÍNH
%
••• ali-l
bl
aii+l
- ain '
^21
- a2-i
b2
a2i+l
- a2n
...
...
...
lanl
- anM
b„
ani+l
- ann>
Định thức, trong đại số tuyến tính, là một hàm cho mỗi ma trận vuông A, tương ứng với số vô hướng, ký hiệu là det(A).
Ý nghĩa hình học của định thức là tỷ lệ xích cho thể tích khi A được coi là một biến đổi tuyến tính. Định thức được sử dụng để giải (và biện luận) các hệ phương trình đại số tuyến tính.
□ Định thức chỉ được xác định trong các ma trận vuông. Nếu định thức của một ma trận bằng 0, ma trận này được gọi là ma trận suy biến, nếu định thức bằng 1, ma trận này được gọi là ma trận đơn môđula.
3
□ Khái niệm định thức xuất hiện đầu tiên gắn với việc giải hệ phương trình đại số tuyến tính có số phương trình bằng số ẩn. Hệ này có một nghiệm duy nhất khi và chỉ khi định thức của ma trận tương ứng với hệ phương trình này khác 0.
Vi dụ hệ hai phương trình tuyến tính hai ẩn:
í a.x + b.y = e,
|c.x + d.y = f,
CÓ các hệ số của các ản tao thành ma trân vuông:
- _ a b
A - |c d
định thức cúa nỏ là
det(A)=ad-bc.
www.lenhattung.com	4
-slide 4- 30/03/2014 định thức cúa nó lã:
ơef(>A)=ad-ôc
Nếu det(A) khác 0, hệ có nghiêm duy nhầt ed — bf	af — ce
x ad — bc. ' y ad — bc
Nếu det(A) = 0 hệ có thể có vô số nghiệm hoặc không có nghiệm nào.
Nếu e = f = 0, hệ trên là một hệ phương trình tuyến tính thuần nhất, nó luôn có ít nhất một nghiệm tầm thường là X = 0 và y = 0. Khi đó hệ có nghiệm không tầm thường khi và chỉ khi định thức của hệ bằng không.
www.lenhattung.com	5
-slide 5 - 30/03/2014
Định nghĩa của định thức trong đại số tuyến tính liên quan đến khái niệm dấu của hoán vị.
■ ■
Định thức của ma trận vuông cấp n là tổng đại số của n! (n giai thừa) số hạng, mỗi số hạng là tích của n phần tử lấy trên các hàng và các cột khác nhau của ma trận A, mỗi tích được nhân với phần tử dấu là +1 hoặc -1 theo phép thế tạo bởi các chỉ số hàng và chỉ số cột của các phần tử trong tích. Gọi Sn là nhóm các hoán vị của n phần tử 1,2,...,n ta có:(Công thức Leibniz)
n
det(.4) = sSnH n
ơ€Sn	i=l
Tim đinh thức cúa ma trán:
Cách 1: Sử dung công thức Leibniz
8
Cách 2: Sử dụng công thức Laplace để khai triển định thức theo một hàng hoặc một cột. Cách tốt nhất là chọn hàng, hoặc cột nào có nhiều phần tử bằng 0, vì như vậy, giá trị định thức của phần tử đó sẽ bằng 0 0 vì thế ta sẽ khai triển theo cột thứ 2.
Tim đinh thức của ma trản:
det(A)= (-1)1+2
2 • det
-1
2
3
-1
1 • det
= (-2) • ((-1) ■ (-1) - 2 ■ 3) + 1 • ((-2) ■ (-1) - 2 . (-3)) = (—2)(—5) + 8 = 18.
□ N0[ duny của píìtroTTQ p/?áp: Gồm 2 quá trình:
> Qua trinh thuarr.
(1) In
(2)
Biến đổi ma trận A về ma trận tam giác trên:
bị1* b2) u2
Trong đó: a-j ,bị là phần tử ở hàng i cột j của ma trận A và phần tử
Thứ i của ma trân B sau bước biến đổi thứ k.
10
□ Hệ phương trình đã cho tương đương với:
12	2
11
> Quá trinh nghịch: Lần lượt tính nghiệm xn, xn.1; ... X1 theo cách:
Y = b(nn)
n n
r =	— Z7("_h V
/7-1	/7-1	(/7-l)/7 /7
= £Ơ) _ y (0
ưi Z_jUik Ak
Ắr=í+1
• • • •
/7
k=2
www.lenhattung.com	12
-slide 12- 30/03/2014
□ Các bước Ịhưc hjerr. Để minh họa, ta sử dụng phương pháp Gauss để giải hệ sau:
> Quá trình thuân
Bước 1: - Giả sử an # 0, chia dòng 1 cho a1v (an là phần tử trụ). Hệ đã cho tương đượng với:
an
ru
“21
ứ31
“22
^32
“23
^33
3/7
Với
14
13
- Khử X1 trong phương trình thứ i=2,3,4,..., n bằng cách: Thay dòng i bởi dòng i - dòng 1 * aM . Nghĩa là:
a(1)ij = aij - a(1)ij *aii với j=1 ,n
và:	bj=bj- b<1)1*ai1
Hệ đã cho tương đương với:
«3?
2. Giải HPT tuyến tính bằng phương pháp Gauss
□ Bước 2: Giả sử a<1)22^0, chia dòng 2 cho a(1)22. Hệ đã cho tương đượng với:
w12
ứ13
(2) ỉ
(2)
a2n
u3n
a„2
a'
nn
•/V ọ I ./V Q
2	2	2
Với
16
Khử x2 ở phương trình thứ i=3,4,5,...,n bằng cách:
Dòng i = dòng i - dòng 2 * a/2W a(2).. = aC^j-a^j *ai2, với j=1,2,...,n b(2)i=b(1)ị - b(2)2*ai2
Nghĩa là'.
và:
Hệ đã cho tương đương với:
a
“12
u13
<2;
a\n
a
unĩ
a(ỵ
nn
9	7
3	3
10	20
-^*3 =- —
17
□ Tiếp tục thực hiện như trên cho đến khi đưa được ma trận hệ số về ma trận tam giác trên. Hệ đã cho tương đương với:
(ỉ)
12
13
(2)
23
1/7
(2)
2n
(2)
3n
18
> Quá trình nqhich:
*3 =2
Từ phương trình thứ 3, ta có: x3 = 2
Từ phương trình thứ 2, ta có: x2 =-l/3+5/3x3 = 3
Từ phương trình thứ 1, ta có: Xi = 3/2-l/2x2+l/2x3 = 1
Vậy nghiệm của hệ là: Xi = 1; x2 = 3; x3 = 2
www.lenhattung.com	19
-slide 19 - 30/03/2014
Ví dụ 3.3: Giải hệ sau bằng phương phap Gauss
Xj+X2 + X3=4
< 2xj + x2 -x3 =5
Xj +3x2 +3x3 = 6
GịẩL- ?2?
□ Bước 1:
o Phần tử trụ an # 0, chia dòng 1 cho a1v o Khử X1 ở các phương trình 2, 3 bằng cách:
Thay dòng i bởi dong i - dòng 1 * a21 (Với i=2,3)
Ẩ(l) = 0 -1 -3
ự) 2	2
□ Bước 2: phần tử trụ a<1)22 = -1
21
Chia dòng 2 cho a22=-1 > và khử x2 ở phương trình 3, ta được
□ Bước 3: Chia dòng 3 cho phần tử trụ a(2)
22
Ta có hệ đã cho tương đương với:
+ x2 + x3 = 4
<	%2 + 3.X3 — 3
*3=1
□ Quá trinh ngược;
Từ phương trình 3, ta có: x3 = 1
Từ phương trình 2, ta có: x2 = 3 - 3 * x3 = 0
Từ phương trình 1, ta có: x1 = 4 - 1*x3 - 1* x2 = 3
Vậy nghiệm của hệ là: xl =3; x2=0 và x3 = 1
www.lenhattung.com
Quá trình thuân:
for (int k= 1; k<=n;k++) {
m = akk;//m là phần tử trụ
If m= =0 “Chưa xét trường hợp này, dừng”
else {//Chia dòng k cho m=akk
bk=bk/m;
for (int j=1; j<=n; j++) akj=akj/m;
for (int i=k+1; i<=n;i++){
hệsố = aik; bị=bi-heso*bk;
for (int j = k; j<=n; j++) aij=aij-akj*heso;
}
}
www.lenhattung.com	24
-slide 24- 30/03/2014
❖ Quá trình nqhich:
for (int i=n; i>=1; i--)
{//Tính nhiệm Xj.
s = 0;
for (int k=i+1; k<=n; k++)
s = s + aik*xk;
Xj = bj-s;
www.lenhattung.com -slide 25 - 30/03/2014
r
«11
«12
- «ln
A
, a =
«21
• • •
«22
-	«2n
J3„ ;
<«nl
«n2
- «nn >
Tìm nghiệm của hệ: AX=B
Nội dung của phương pháp
-Biến đổi hệ về dạng tương dượng: X = p
Trong đó:
- Bắt đầu với x(°) nào đó, nếu dãy: x co thì xn là nghiệm của hệ
26
www.lenhattung.com
Cho hệ phương trình:
alìxl + aY2x2 + aỉnxn = ^1
a21xl + a22x2 + ■" a2nxn —
^nl^ì + &n2x2 + ■■■ &nnxn
Các phần tử trên đường chéo: a11, a22, a33,... có giá trị khác 0
www.lenhattung.com	27
Cho hệ phương trình:
<211*1 + a12*2 + ••• aỉnxn =
a21xl + a22x2 + a2nxn — t>2
e
^nlxl 3“ &n2x2 "T &nnxn bn
Các phần tử trên đường chéo: a11, a22, a33,... có giá trị khác 0
□ Ta lần lượt tìm x1,x2,..xn bằng cách chia toàn bộ phương trình cho aH
X1 ~ ~	(^1	«12*2	«13*3 '"a\nxn)
«11
1 L
x2 — "	(^2 — «21*1 - «23*3 — *** «2n*n)
«22
1
xn ~ (^n	«711-^1	«n2^2	«n,n—l^n-1)
«nn
29
WWW.Ienhattung.com
□ Lần lượt lặp và tính giá trị của Xj bởi công thức
for ỉ = 1,2,,... n
30
-slide 30- 30/03/2014
Ví dụ: Giải hệ phương trình
5xx — 2*2 + 3xn = — 1
-3Xi + 9*2 +xn = 2
Ta có:	2xt — x2 — 7xn = 3
_-l 2	3
*1 = —+ ị*2
2 3	1
Bắt đầu lặp \	*2 = g + 5*1 -5X3
3 2	1
Xo — — —+ —X1 — —Xo
www.lenhattung.com	31
-slide 31 - 30/03/2014
□ Với x^O, x2=0, x3=0 ta có (thay giá trị xn x2, x3
để tính giá trị x1s x2, x3 mới):
xí1} = ^- + |(O)-|(O) =-0.200
m 2 3	 ĩ'
xị1)=| + |(O)-|(O) = 0.222
x^ = -| + |(0)-i(0) = -0.429
□ Tiếp tục lặp bằng cách thay giá trị x^-0.2,
x2=0.222, x3=-0.429 vào hệ trên để có giá trị Xị mới.
3. Giải HPT tuyến tính bằng phương pháp lặp đơn (Jacobi)
□ Ta thực hiện việc lặp n bước (cho sẵn theo yêu cầu đề bài) hoặc lặp cho đến khi nào các giá trị X gần thỏa mãn hệ phương trình (thử lại).
for ỉ = 1,2,,... n
n
k = 0
k = 1
k = 2
k = 'Ẳ
*1
0.000
-0.200
0.146
0.192
X™
x2
0.000
0.222
0.203
0.328
„(*) ■*2
0.000
-0.429
-0.517
-0.416
33