( Ma trận [A] gọi là đối xứng nếu [A]
T
= [A]
( Cho một ma trận vuông [A], cấp n. Ta nói ma trận [A] không suy biến
(non singular) nếu ma trận có thể nghịch đảo được hay nói cách khác, định
thức của ma trận khác không.
( Ma trận Hermite là một ma trận vuông có các phần tử là số phức
bằng chuyển vị liên hợp của nó, nghĩa là phần tử ở hàng i cột j bằng số phức
liên hợp của phân tử ở hàng j cột i
T
AA∗
⎡ ⎤ ⎡⎤=
⎣⎦⎣ ⎦
. Ví dụ ma trận
[]
32j A
2j 1
+ ⎡⎤ =
⎢⎥−
⎣⎦ là ma trận Hermite.
( Ma trận Householder là một ma trận vuông dạng:
[][]
[][]
[][] =− T
T
2
HE UU UU
Trong đó v là vec tơ cột khác zero
( Ma trận [A] gọi là trực giao nếu [A]
T
[A] = [E]
( Ma trận phức [U] gọi là ma trận unita nếu
T
UU E ∗
⎡ ⎤⎡⎤ ⎡⎤=
⎣⎦ ⎣ ⎦⎣⎦. Ví dụ ma
trận []
1j 1j
22 U
1j 1j
22
+−+ ⎡⎤ ⎢⎥ =⎢⎥+− ⎢⎥ ⎣⎦
là ma trận unita
( Một ma trận chỉ có một cột gọi là một vec tơ
( Chuẩn của một vec tơ X, kí hiệu là X, là một số thực thoả mãn:
‐ X > 0
‐ cX c X =
‐ XY X Y +≤ +
Giả thiết X = [x1, x2, ,xn]
T
, ta thường dùng một trong 3 chuẩn sau đây:
‐ j 1
j
Xmaxx =
‐ n
j 2
j1
Xx=
=∑
77 trang |
Chia sẻ: oanh_nt | Lượt xem: 2322 | Lượt tải: 0
Bạn đang xem trước 20 trang nội dung tài liệu Bài giảng Toán cao cấp: Ma trận, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
58
CHƯƠNG 2: MA TRẬN
§1. MỘT SỐ KHÁI NIỆM
( Ma trận [A] gọi là đối xứng nếu [A]T = [A]
( Cho một ma trận vuông [A], cấp n. Ta nói ma trận [A] không suy biến
(non singular) nếu ma trận có thể nghịch đảo được hay nói cách khác, định
thức của ma trận khác không.
( Ma trận Hermite là một ma trận vuông có các phần tử là số phức
bằng chuyển vị liên hợp của nó, nghĩa là phần tử ở hàng i cột j bằng số phức
liên hợp của phân tử ở hàng j cột i
T
A A∗ ⎡ ⎤⎡ ⎤ =⎣ ⎦ ⎣ ⎦ . Ví dụ ma trận
[ ] 3 2 jA 2 j 1
+⎡ ⎤= ⎢ ⎥−⎣ ⎦ là ma trận Hermite.
( Ma trận Householder là một ma trận vuông dạng:
[ ] [ ] [ ] [ ][ ][ ]= −
T
T
2H E U U
U U
Trong đó v là vec tơ cột khác zero
( Ma trận [A] gọi là trực giao nếu [A]T[A] = [E]
( Ma trận phức [U] gọi là ma trận unita nếu TU U E∗⎡ ⎤ ⎡ ⎤⎡ ⎤ =⎣ ⎦⎣ ⎦ ⎣ ⎦ . Ví dụ ma
trận [ ]
1 j 1 j
2 2U
1 j 1 j
2 2
+ − +⎡ ⎤⎢ ⎥= ⎢ ⎥+ −⎢ ⎥⎢ ⎥⎣ ⎦
là ma trận unita
( Một ma trận chỉ có một cột gọi là một vec tơ
( Chuẩn của một vec tơ X, kí hiệu là X , là một số thực thoả mãn:
‐ X > 0
‐ cX c X=
‐ X Y X Y+ ≤ +
Giả thiết X = [x1, x2,…,xn]T, ta thường dùng một trong 3 chuẩn sau đây:
‐ j1 jX max x=
‐
n
j2
j 1
X x
=
=∑
59
‐
n 2
j3
j 1
X x
=
= ∑
( Chuẩn của một ma trận [A], kí hiệu là A , là một số thực thoả mãn:
‐ A > 0
‐ cA c A=
‐ A B A B+ ≤ +
‐ AB A B≤
Ta thường dùng một trong 3 chuẩn sau đây:
‐
n
i ,j1 i j 1
A max a
=
= ∑
‐
n
i ,j1 j i 1
A max a
=
= ∑
‐
n 2
i ,j3
i ,j 1
A a
=
= ∑
( Ma trận [A] gọi là xác định dương nếu với vec tơ [x] bất kì ta có:
[ ] [ ][ ]Tx A x 0>
( Ma trận [A] gọi là nửa xác định dương nếu với vec tơ [x] bất kì ta có:
[ ] [ ][ ]Tx A x 0≥
Ta định nghĩa ma trận xác định âm và nửa xác định âm một cách tương
tự.
( Hạng của ma trận là cấp của ma trận con của ma trận ấy có định thức
khác không còn mọi ma trận con cấp cao hơn đều có định thưc bằng
không(ma trận con là ma trận có được bằng cách xoá một số hàng và cột của
ma trận ban đầu).
§2. BIẾN ĐỔI HOUSEHOLDER
1. Ma trận Householder: Ta biến đổi ma trận [A] về dạng có các phần tử
thuộc đường chéo chính, các phần tử phía trên và phía dưới đường chéo
chính khác zero, còn các phần tử còn lại bằng zero(ma trận ba đường chéo)
bằng cách dùng phép biến đổi Householder.
Phép biến đổi Householder dùng ma trận Householder.
[ ] [ ] [ ][ ]= −
TU UH E
Q
(1)
60
Trong đó:
[ ] [ ] [ ]= = 2T1 1Q U U U
2 2
(2)
Do [H] đối xứng nên:
[ ] [ ] [ ][ ] [ ] [ ][ ] [ ] [ ][ ]⎛ ⎞⎛ ⎞= = − −⎜ ⎟⎜ ⎟⎝ ⎠⎝ ⎠
T T
T U U U UH H H H E E
Q Q
[ ] [ ][ ] [ ] [ ][ ]( )[ ]= − + T TT 2U U U UU UE 2 Q Q
[ ] [ ][ ] [ ]( )[ ] [ ]= − + =
TT
2
U 2Q UU UE 2 E
Q Q
Từ đây ta thấy [H] cũng là ma trận trực giao.
Cho [X] là vec tơ bất kỳ và khảo sát phép biến đổi [H][X]. Chọn:
[U] = [X] + k[I1] (3)
Trong đó:
[ ]= ±k X [ ] = ⎡ ⎤⎣ ⎦L T1I 1 0 0
Ta có:
[ ][ ] [ ] [ ][ ] [ ] [ ] [ ] [ ] [ ]( ) [ ]⎧ ⎫+⎛ ⎞ ⎪ ⎪= − = −⎨ ⎬⎜ ⎟⎝ ⎠ ⎪ ⎪⎩ ⎭
TT
1U X k IU UH X E X E X
Q Q
[ ] [ ] [ ] [ ] [ ] [ ]( ) [ ] [ ] [ ]( )+ += − = −TT 21 1U X X k I X U k k XX X
Q Q
Nhưng:
[ ] [ ]( ) [ ] [ ]( ) [ ] [ ] [ ] [ ] [ ]( ) [ ] [ ]= + + = + + +T 2 T TT 21 1 1 1 1 12Q X k I X k I X k X I I X k I I
= + + = +2 2 21 1k 2kx k 2(k kx )
Như vậy:
[ ][ ] [ ] [ ] [ ]= − = − = −⎡ ⎤⎣ ⎦L T1H X X U k I k 0 0 0 (4)
nghĩa là phép biến đổi loại trừ tất cả các phần tử của [X] trừ phần tử đầu tiên.
2. Biến đổi Householder một ma trận đối xứng: Bây giờ ta áp dụng phép
biến đổi cho ma trận [A] đối xứng:
[ ] [ ][ ] [ ]
[ ]
[ ] [ ]
[ ]
[ ][ ] [ ][ ]
⎡ ⎤ ⎡ ⎤⎡ ⎤= =⎡ ⎤ ⎢ ⎥ ⎢ ⎥⎢ ⎥⎣ ⎦ ′ ′⎣ ⎦ ⎣ ⎦ ⎣ ⎦
T TT
11 11
1
a X a X1 0
P A
X A H X H A0 H
(5)
61
Trong đó [X] là cột đầu tiên của [A] với phần tử đầu tiên bị bỏ đi. [A’] có được
từ [A] bằng cách bỏ đi cột và hàng đầu tiên. Ma trận [H] cấp (n ‐1) được xây
dựng theo các công thức (1) ÷ (3). Do (4) ta thấy phép biến đổi này làm cột
đầu tiên của [A] trở thành:
[ ][ ]
⎡ ⎤⎢ ⎥−⎢ ⎥⎡ ⎤ ⎢ ⎥=⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎢ ⎥⎢ ⎥⎣ ⎦
M
11
11
a
k
a
0
H H
0
Phép biến đổi:
[ ] [ ][ ]( )[ ][ ] [ ][ ][ ] [ ]
⎡ ⎤= →⎡ ⎤ ⎡ ⎤ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ′⎢ ⎥⎣ ⎦
T
11
1 1
a H XP A P A
H X H A H
(6)
sẽ đường chéo hoá hàng đầu tiên và cột đầu tiên của ma trận [A]. Sơ đồ biến
đổi của ma trận 4×4 là:
Hàng và cột thứ 2 của ma trận [A] được biến đổi tiếp bằng cách dùng phép
biến đổi đối với phần bên phải, phía dưới của ma trận. Phép biến đổi này có
thể biểu diễn bằng [ ][ ][ ] [ ]→2 2P A P A , trong đó:
[ ] [ ] [ ][ ] [ ]
⎡ ⎤= ⎢ ⎥⎣ ⎦
T
2
2
E 0
P
0 H
(7)
với [E2] là ma trận đơn vị 2×2 và [H] là ma trận (n ‐ 2)×(n ‐ 2) có được bằng
cách chọn [X] từ (n ‐ 2) phần tử phía dưới của cột thứ 2 của ma trận [A]. Thực
hiện (n ‐ 2) phép biến đổi:
[ ] [ ] [ ][ ] [ ]
⎡ ⎤= ⎢ ⎥⎣ ⎦
T
i
i
E 0
P
0 H
i = 1, 2,..., n ‐ 2
để có được ma trận ba đường chéo(tridiagonal). Ta có:
×
1 0 0 0
0
0
0
[Q]
a11 a12 a13 a14
a21
a31
a41
[A’]
1 0 0 0
0
0
0
[Q]× =
a11 ‐k 0 0
‐k
0
0
[Q][A’]
[Q]
62
[ ][ ] [ ] [ ] [ ][ ] [ ] [ ][ ][ ] [ ] [ ][ ]⎛ ⎞ ′′ ′ ′ ′= − = − = −⎜ ⎟⎝ ⎠
T
T TA UU UA H A E A U A V U
Q Q
Trong đó:
[ ] [ ][ ]′= A UV
Q
(8)
Do vậy:
[ ][ ][ ] [ ] [ ][ ] [ ] [ ][ ]( )⎛ ⎞′ ′= − −⎜ ⎟⎝ ⎠
T
TU UH A H E A V U
Q
[ ] [ ][ ] [ ][ ] [ ] [ ][ ]( )′ ′= − − −TT TU UA V U A V UQ
[ ] [ ][ ] [ ] [ ] [ ]( ) [ ] [ ] [ ]( )[ ]′′= − − +T T TT U U A U U V UA V U
Q Q
[ ] [ ][ ] [ ][ ] [ ][ ]′= − − +T T TA V U U V 2g U U
Trong đó:
[ ] [ ]= TU Vg
2Q
(9)
Đặt: [W] = [V] ‐ g[U] (10)
Ta thấy ngay phép biến đổi có dạng:
[ ][ ][ ] [ ] [ ][ ] [ ][ ]′ ′= − −T TH A H A W U U W (11)
Thuật toán có thể tóm lại như sau:
‐ Cho [A’] là ma trận vuông cấp (n ‐ i) có được từ phần dưới bên phải
của ma trận [A]
‐ Đặt + += ⎡ ⎤⎡ ⎤⎣ ⎦ ⎣ ⎦L Ti 1,i i 2 ,i n ,iX a a a
‐ Tính [ ]X . Cho k = [ ]X nếu x1 > 0 và k = ‐ [ ]X nếu x1 < 0
‐ Cho −= +⎡ ⎤ ⎡ ⎤⎣ ⎦⎣ ⎦ L T1 2 n iU k x x x
‐ Tính [ ]=
2U
Q
2
‐ Tính [ ] [ ][ ]′= A UV
Q
‐ Tính [ ] [ ]= TU Vg
2Q
63
‐ Tính [W] = [V] ‐ g[U]
‐ Tính [ ] [ ] [ ][ ] [ ][ ]′= − −T TA A W U U W
‐ Đặt + += = −i ,i 1 i 1,ia a k
Ta xây dựng hàm housetrans() để thực hiện thuật toán trên:
function A = housetrans(A)
% Bien doi Householder ma tran A thanh ma tran
% ba đường chéo dang[c\d\c].
% De co c va d dung d = diag(A), c = diag(A,1).
n = size(A, 1);
for k = 1:n‐2
u = A(k+1:n, k);
uMag = sqrt(dot(u, u));
if u(1) < 0;
uMag = ‐uMag;
end
u(1) = u(1) + uMag;
A(k+1:n, k) = u; % Luu u vao phan duoi cua A.
H = dot(u, u)/2;
v = A(k+1:n,k+1:n)*u/H;
g = dot(u, v)/(2*H);
v = v ‐ g*u;
A(k+1:n, k+1:n) = A(k+1:n, k+1:n) ‐ v*uʹ ‐ u*vʹ;
A(k, k+1) = ‐uMag;
end
k = zeros(n);
for i = 1:n
k(i, i) = A(i, i);
end
for i = 1:n‐1
k(i, i+1) = A(i, i+1);
k(i+1, i) = A(i, i+1);
end
A = k;
64
Để tính ma trận ba đường chéo theo phép biến đổi Householder ta dùng
chương trình cthousetrans.m:
clear all, clc
a = [ 1 2 3 4; 2 9 3 5; 3 3 3 7; 4 5 7 6];
b = householder(a)
d = diag(b)
c = diag(b, 1)
§3. BIẾN ĐỔI THÀNH MA TRẬN HESSENBERG
Nếu ma trận [A] là ma trận đối xứng, phương pháp Householder có thể
được sử dụng để biến đổi nó thành ma trận đồng dạng đối xứng ba đường
chéo. Nếu ma trận [A] không đối xứng, phương pháp Householder biến đổi
ma trận [A] thành ma trận đồng dạng Hessenberg.
Ma trận Hessenberg là ma trận có dạng:
[ ]
11 12 13 1,n
21 22 23 2n
32 33 2n
nn
a a a a
a a a a
0 a a aH
0 0 0 a
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥= ⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
L
L
L
M M M L M
L
Ta thực hiện phép biến đổi Householder trên ma trận [A] và có được:
[Q][H][Q’] = [A]
trong đó [Q] là ma trận trực giao (ta gọi đây là phân tích Hessenberg ma trận
[A]) .
Thuật toán có thể tóm lại như sau:
‐ Cho [Q] là ma trận đơn vị cấp n
‐ Đặt += ⎡ ⎤⎡ ⎤⎣ ⎦ ⎣ ⎦L Ti 2,i n ,iX 0 a a
‐ Tính [ ]X . Cho α= [ ]X nếu ai+2,i > 0 và α = ‐ [ ]X nếu ai+2,i < 0
‐ Cho −= α +⎡ ⎤ ⎡ ⎤⎣ ⎦⎣ ⎦ L T2 n iU 0 x x
‐ Tính [ ]β =
2U
2
‐ Tính [ ] [ ] [ ][ ]′= − β
U UP E
65
‐ Tính [ ] [ ][ ]=Q Q P
‐ Tính [ ] [ ][ ][ ]=A P A P
Ta xây dựng hàm hessenberg() để thực hiện phép phân tích trên:
function [H, Q] = hessenberg(a)
[n, n] = size(a);
q = eye(n);
for k = 1:n ‐ 2
alfa = 0;
for j = k+1:n
alfa = alfa + a(j, k)^2;
end
alfa = sign(a(k+1, k))*sqrt(alfa);
u = zeros(1, n);
u(k+1:n) = a(k+1:n, k);
u(k+1) = u(k+1) + alfa;
beta = .5*u*uʹ;
p = eye(n);
for i = 1:n
p(i, 1:n) = p(i, 1:n) ‐ (u(i)*u(1:n))/beta;
end
q = q*p;
a = p*a*p;
end
H = a;
Q = q;
Để phân tích ma trận ta dùng chương trình cthessenberg.m:
clear all, clc
a = [ 1 2 3 4; 5 6 7 4; 6 4 8 9; 3 5 7 9];
[H, Q] = hessenberg(a)
§4. PHÂN TÍCH MA TRẬN THEO PHƯƠNG PHÁP DOOLITTLE
66
Một ma trận không suy biến [A] gọi là phân tích được thành tích hai ma
trận [L] và [R] nếu:
[A] = [L] [R]
Việc phân tích này, nếu tồn tại, là không duy nhất.
Nếu ma trận [L] có các phần tử nằm trên đường chéo chính bằng 1, ta có
phép phân tích Doolittle.
Nếu ma trận [R] có các phần tử nằm trên đường chéo chính bằng 1, ta
có phép phân tích Crout.
Nếu [R] = [L]T (hay [L] = [R]T) ta có phép phân tích Choleski.
Với ma trận bậc 3, [L] và [R] có dạng:
[ ] [ ]
11 12 13
21 22 23
31 32 33
1 0 0 r r r
L l 1 0 R 0 r r
l l 1 0 0 r
⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥= =⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦
Để tìm lij và rij ta thực hiện phép nhân. Sau khi nhân ta có:
[ ]
11 12 13
11 21 12 21 22 13 21 23
11 31 12 31 22 32 13 31 23 32 33
r r r
A r l r l r r l r
r l r l r l r l r l r
⎡ ⎤⎢ ⎥= + +⎢ ⎥⎢ ⎥+ + +⎣ ⎦
Bây giờ ta thực hiện phép khử Gauss đối với phương trình trên. Đầu tiên ta
chọn hàng thứ nhất làm trụ và thực hiên phép biến đổi:
hàng 2 ‐ l21 × hàng 1 (khử a21) → hàng 2
hàng 3 ‐ l31 × hàng 1 (khử a31) → hàng 3
kết quả ta có:
[ ] 11 12 131 22 23
22 32 23 32 33
r r r
A 0 r r
0 r l r l r
⎡ ⎤⎢ ⎥= ⎢ ⎥⎢ ⎥+⎣ ⎦
Sau đó ta lấy hàng thứ hai làm trụ và thực hiện biến đổi:
hàng 3 ‐ l32 × hàng 2 (khử a32) → hàng 3
và có:
[ ] 11 12 132 22 23
33
r r r
A 0 r r
0 0 r
⎡ ⎤⎢ ⎥= ⎢ ⎥⎢ ⎥⎣ ⎦
Như vậy ta thấy ngay rằng ma trận [R] là ma trận có được khi thực hiện
loại trừ Gauss tiến ma trận [A] và các phần tử của [L] là các nhân tử dùng khi
67
loại trừ aij. Điều đó có nghĩa là để tìm ma trận [L] và [R] ta dùng phép khử
Gauss tiến. Ta xây dựng hàm doolittle() để thực hiện loại phân tích Doolittle.
function [l,r] = doolittle(A)
%Phan tich ma tran A thanh A = L*U
n = size(A, 1);
u = zeros(n);
for k = 1:n‐1
for i = k+1:n
if A(i, k)~= 0.0
lambda = A(i, k)/A(k, k);
A(i, k+1:n) = A(i, k+1:n) ‐ lambda*A(k, k+1:n);
A(i, k) = lambda;
end
end
end
l = tril(A);
for i = 1:n
l(i, i) = 1;
end
l = triu(A);
for i = 1:n
l(i,i) = A(i, i);
end
§5. PHÂN TÍCH MA TRẬN THEO PHƯƠNG PHÁP CROUT
Tương tự như thuật toán Doolittle, ta có thể phân tích ma trận [A] theo
thuật toán Crout thành tích của ma trận [L] và [R]. Các ma trận bậc 3 theo
Crout có dạng:
[ ] [ ]
11 12 13
21 22 23
31 32 33
l 0 0 1 r r
L l l 0 R 0 1 r
l l l 0 0 1
⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥= =⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦
Để tìm lij và rij ta thực hiện phép nhân. Sau khi nhân ta có:
68
[ ]
11 11 12 11 13
21 21 12 22 21 13 22 23
31 31 12 32 31 13 32 23 33
l l r l r
A l l r l l r l r
l l r l l r l r l
⎡ ⎤⎢ ⎥= + +⎢ ⎥⎢ ⎥+ + +⎣ ⎦
Như vậy:
a11 = 1. r11 + 0.0 + 0.0 = r11 ;
a12 = r12 ; a13 = r13
a21 = l21r11 ;
a22 = l21r12 + r22 ; a23 = l31r11
a31 = l31r11 ; a32 = l31r12 ;
a33 = l31r13 + l32r23 + r33
Một cách tổng quát ta có :
với j > i : lij = rji = 0
với i = 1 : r1j = a1j (j = 1 tới n)
lj1 = aj1/r11 (j = 1 tới n)
với i = 2 tới n
∑−
=
−= 1i
1k
kjikijij rlar ( j = i tới n)
ii
1i
1k
kijkji
ji r
rla
l
∑−
=
−
= (j = i tới n)
Ta xây dựng hàm crout() để phân tích ma trận theo thuật toán Crout:
function [l, r] = crout(a)
n = size(a, 1);
l = zeros(n);
r = zeros(n);
for i = 1:n
r(1, i) = a(1, i);
l(i, i) = 1.;
l(i, 1) = a(i, 1)/a(1, 1);
end
for k = 2:n
r(k, k:n) = a(k, k:n) ‐ l(k, 1:k)*r(1:k, k:n);
if k~= n
69
for i = 1:n
l(i, k) = (a(i, k)‐ l(i, 1:k‐1)*r(1:k‐1, k))/r(k, k);
end
end
end
§6. PHÂN TÍCH MA TRẬN THEO PHƯƠNG PHÁP CHOLESKI
Thuật toán Choleski cho phép phân tích ma trận [A] thành tích hai ma
trận:
[A] = [L][L]T.
Thuật toán này đòi hỏi:
‐ [A] là ma trận thực, đối xứng
‐ [A] là ma trận xác định dương
Ta vuông [A] cấp 3 theo thuật toán Choleski:
11 12 13 11 11 21 31
21 22 23 21 22 22 32
31 32 33 31 32 33 33
a a a l 0 0 l l l
a a a l l 0 0 l l
a a a l l l 0 0 l
⎡ ⎤ ⎡ ⎤ ⎡ ⎤⎢ ⎥ ⎢ ⎥ ⎢ ⎥=⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦
Sau khi thực hiện phép nhân ta có:
2
11 12 13 11 11 21 11 31
2 2
21 22 23 11 21 21 22 21 31 22 32
2 2 2
31 32 33 11 31 21 31 22 32 31 32 33
a a a l l l l l
a a a l l l l l l l l
a a a l l l l l l l l l
⎡ ⎤⎡ ⎤ ⎢ ⎥⎢ ⎥ = + +⎢ ⎥⎢ ⎥ ⎢ ⎥⎢ ⎥ + + +⎣ ⎦ ⎣ ⎦
Vế phải là ma trận đối xứng. Cân bằng các phần tử của hai ma trận ta có:
11 11 21 21 11 31 31 11
2 2 2
22 22 21 32 32 21 31 22 33 33 31 32
l a l a / l l a / l
l a l l (a l l ) / l l a l l
= = =
= − = − = − −
Tổng quát, với ma trận cấp n, ta có:
[ ][ ]( ) jT i1 j1 i2 j2 ik jkij k 1L L l l l l l l i j== + + ⋅⋅ ⋅+ = ≥∑
Cân bằng với phần tử của ma trận [A] ta có:
j
ij ik jk
k 1
a l l i j, j 1,...,n j 1,2,...,n
=
= = + =∑
Do ma trận [L] là ma trận tam giác trái nên đối với cột thứ nhất ta có:
11 11 i1 i1 11l a l a / l= =
Đối với cột khác, rút lij ra khỏi tổng ta có:
70
j 1
ij ik jk ij jj
k 1
a l l l l
−
=
= +∑
Nếu i = j (phần tử trên đường chéo) thì:
j 1
2
jj jj jk
k 1
l a l j 2,3,...,n
−
=
= − =∑
và phần tử nằm ngoài đường chéo:
j 1
ij ij ik jk
k 1 jj
1l a l l j 2, 3,..., n i j 2, j 3,...,n
l
−
=
⎛ ⎞= − = = + +⎜ ⎟⎝ ⎠∑
Dựa vào thuật toán trên ta xây dựng hàm choleski()
function L = choleski(A)
% Phan tich ma tran a thanh A = LL’.
% Cu phap: L = choleski(A)
f = posdef(A);
if f == 0
error(ʹMa tran khong xac dinh duong!ʹ);
return
end
n = size(A, 1);
for j = 1:n
temp = A(j, j) ‐ dot(A(j, 1:j‐1),A(j, 1:j‐1));
if temp < 0.0
error(ʹMa tran khong xac dinh duongʹ)
end
A(j, j) = sqrt(temp);
for i = j+1:n
A(i, j)=(A(i, j) ‐ dot(A(i, 1:j‐1),A(j, 1:j‐1)))/A(j, j);
end
end
L = tril(A);
function f = posdef(M)
%Kiem tra lieu ma tran M co xac dinh duong hay kong
isposdef = true;
71
for i=1:length(M)
if ( det( M(1:i, 1:i) ) <= 0 )
isposdef = false;
break;
end
end
f = isposdef;% 0 neu sai, 1 neu dung
§7. PHÂN TÍCH QR BẰNG THUẬT TOÁN HOUSEHOLDER
Cho ma trận [A], phân tích QR của nó cho ta:
[A] = [Q]*[R]
Trong đó [Q] là ma trận trực giao và [R] là ma trận tam giác phải.
Ta dùng biến đổi Householder để tìm các ma trận [Q] và [R].
[ ][ ] [ ][ ] [ ]− − ⋅ ⋅ ⋅ =n 1 n 2 1H H H A R (1)
Như vậy:
[ ] [ ][ ] [ ]( ) [ ] [ ] [ ] [ ][ ]
[ ] [ ][ ][ ] [ ][ ]
− − −
− − − −
− −
= ⋅ ⋅ ⋅ = ⋅ ⋅ ⋅
= ⋅ ⋅ ⋅ =
1 1 1
n 1 n 2 1 1 n 2 n 1
1 n 2 n 1
A H H H R H H H R
H H H R Q R
(2)
Tích của tất cả các ma trận Householder:
[ ] [ ] [ ][ ]− −= L1 n 2 n 1Q H H H (3)
không những đối xứng mà còn trực giao như mỗi ma trận [Hk]:
[ ] [ ] [ ] [ ][ ]( ) [ ] [ ][ ]
[ ] [ ] [ ] [ ] [ ][ ] [ ]
− − − −
− − − −
= ⋅ ⋅ ⋅ ⋅ ⋅ ⋅
= ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ =
TT
1 n 2 n 1 1 n 2 n 1
T T T
n 1 n 2 1 1 n 2 n 1
Q Q H H H H H H
H H H H H H E
Ta xây dựng hàm qrdecom() để phân tích ma trận:
function [Q, R] = qrdecom(A)
%Phan tich QR
n = size(A, 1);
R = A;
Q = eye(n);
for k = 1:n ‐ 1
H = householder(R(:, k), k);
R = H*R; %Pt.(1)
Q = Q*H; %Pt.(3)
72
end
Hàm householder() dùng để tạo ra ma trận Householder:
function H = householder(x, k)
% Tao ma tran Householder
n = length(x);
tmp = sum(x(k+1:n).^2);
g = sqrt(x(k)^2 + tmp);
c = sqrt((x(k) + g)^2 + tmp);
u = zeros(n, 1);
u(k) = (x(k) + g)/c;
u(k + 1:n) = x(k + 1:n)/c;
H = eye(n) ‐ 2*u*uʹ; %ma tran Householder
Để phân tích ma trận ta dùng chương trình ctqrdecom.m:
clear all, clc
a = [4 1 3 ‐2; 1 ‐2 4 1; 3 4 1 2; ‐2 1 2 3];
[q, r] = qrdecom(a)
§8. PHÂN TÍCH QR BẰNG THUẬT TOÁN QUAY GIVENS
Kỹ thuật quay Givens là một phương pháp để phân tích ma trận [A]
thành tích của ma trận [Q] và ma trận [R] bằng cách làm cho các phần tử lần
lượt bằng zero cho đến khi có được ma trận tam giác phải. Ý tưởng là dùng
một ma trận quay đơn giản 2 × 2 đặt dọc theo đường chéo chính của một ma
trận đơn vị và làm cho một phần tử của ma trận bằng zero. Các phần tử của
ma trận quay để quay một vec tơ ngược chiều kim đồng hồ một góc θ là:
[ ]θ θ − θ⎡ ⎤= ⎢ ⎥θ θ⎣ ⎦
cos sin
Q
sin cos
Nếu ta muốn quay vec tơ [x1 x2]T và muốn làm cho x2 bằng zero rồi quaytheo
chiều kim đồng hồ một góc θ(hay ngược chiều kim đồng hồ một góc ‐θ) trong
đó:
73
θ = 2
1
xarctg
x
thì ma trận quay để thực hiện phép quay này theo chiều kim đồng hồ một góc
θ là:
[ ]θ θ θ⎡ ⎤= ⎢ ⎥− θ θ⎣ ⎦
cos sin
Q
sin cos
Trong đó:
θ = = +
1
2 2
1 2
xcos c
x x
θ = = +
2
2 2
1 2
xsin s
x x
Do đó:
[ ]θ ⎡ ⎤ ⎡ ⎤= =⎢ ⎥ ⎢ ⎥− −+ ⎣ ⎦ ⎣ ⎦
1 2
2 2
2 11 2
x x c s1Q
x x s cx x
Chú ý là như mong muốn:
[ ]θ
⎡ ⎤+ ⎡ ⎤+⎡ ⎤ ⎡ ⎤ +⎢ ⎥= = =+ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥− +⎣ ⎦ ⎣ ⎦ ⎢ ⎥⎣ ⎦⎢ ⎥⎣ ⎦
2 2
1 2 2 2
1 1 2 2 2 1 2
1 2
2 1 2
x x
x cx sx x xQ x xx sx cx 00
Nếu A là ma trận m × n, ta sẽ xem điều gì xảy ra khi ta thay các phần tử của
[Q] vào ma trận con xác định bằng các cột và hàng thứ i, các cột và hàng thứ j.
Nói cách khác ta thay ma trận 2 × 2 này dọc theo đường chéo chính tại một số
điểm:
[ ]
kl
kl
1 0 0 0
k i, l j
0 c s 0
c k, l i; k,l j
G
s k i; l j
0 s c 0
s k j; l i
0
0 0 0 1
⎡ ⎤⎢ ⎥⎢ ⎥δ ≠ ≠⎧ ⎢ ⎥⎪ = =⎪ ⎢ ⎥= =⎨ ⎢ ⎥= =⎪ ⎢ ⎥−⎪− = = ⎢ ⎥⎩ ⎢ ⎥⎢ ⎥⎣ ⎦
L L L
M O M M M O M
L L L
M M M O M M M
L L L
M M M M O M
L L L
Như vậy [G] là ma trận đơn vị m × m ngoại trừ các giá trị đã bị thay thế:
gii = gjj = c
gij = ‐gij = s
Điều này sẽ tạo ra ma trận unita:
[G]T[G] = [E]
nghĩa là:
74
= δ∑ lk lp kp
l
g g
và đòi hỏi:
c2 + s2 = 1
Điều này đúng vì cos2θ + sin2θ = 1 ∀θ. Khi ma trận này được áp dụng cho ma
trận m × n ta có:
⎧ δ = ≠⎪⎪⎪= = = + =⎨⎪⎪ = − + =⎪⎩
∑
∑ ∑
∑
kl lp kp
l
kp kl lp il lp ip jp
l l
jl lp ip jp
l
a a k i, j
b g a g a ca sa k i
g a sa ca k j
Như vậy ma trận mới chỉ bị thay đổi ở hàng i và cột j. Ta chọn s và c sao cho
các phần tử ở cột r và hàng j bằng zero:
= +
jr
2 2
jr ir
a
s
a a
= +
ir
2 2
jr ir
ac
a a
Như vậy ta sẽ có:
− += =+
jr ir ir jr
jr 2 2
jr ir
a a a b
b 0
a a
Ta xây dựng hàm givens() để thực hiện thuật toán trên:
function [Q, R] = givens(A);
% Phan tich QR bang thuat toan quay Givens
n = size(A, 1);
Q = eye(n);
for j = 1:n‐1
for i = n:‐1:j+1
z = 1/sqrt(A(i‐1, j)^2 + A(i, j)^2);
c = A(i‐1, j)*z;
s = A(i, j)*z;
A(i‐1:i,:) = [c s; ‐s c]*A(i‐1:i,:);
Q(i‐1:i,:) = [c s; ‐s c]*Q(i‐1: i,:);
end
end
R = A;
75
Q = Qʹ;
Để phân tích một ma trận ta dùng chương trình ctgivens.m:
clear all, clc
A = [17 24 30 17; 8 13 20 7; 2 10 8 6; ‐23 ‐43 ‐54 ‐26];
[Q, R] = givens(A)
§9. PHÂN TÍCH QR BẰNG THUẬT TOÁN GRAM ‐ SCHMIDT
Ta có thể thực hiện việc phân tích ma trận [A] thành tích các ma trận [Q]
và [R] bằng cách trực giao hoá các cột của ma trận [A]. Ta gọi các cột của ma
trận [A] là a1,...,an. Từ các vec tơ này ta muốn có n vec tơ trực giao v1,...,vn. Vec
tơ trực giao đầu tiên được chọn là:
1 1v a=
Để có vec tơ thứ hai, ta dùng y2 nhưng trừ bớt đi phần y2 cùng chiều với v2.
Như vậy ta có:
2 1 1v y ba= −
với b được chọn sao cho v1 trực giao với v2:
1 2 1 2 1 1 2 1 1v v v (a bv ) v a bv v 0= − = − =
hay:
1 2
1 1
v ab
v v
=
Tiếp tục quá trình đến bước thứ k ta có:
k 1
i k
k k i
i ii 1
v av a v
v v
−
=
= −∑
Như vậy thuật toán gồm các bước:
‐ = = 111 1 1
11
ar a , q
r
- lặp từ k = 2 đến n
k 1
k k ik i kk
i 1
q a r q r
−
=
⎛ ⎞= −⎜ ⎟⎝ ⎠∑
với
T
ik i kr q a=
và rkk được chọn sao cho kq 1= , nghĩa là:
76
k k ikz a q r= −
kkr z=
Ta xây dựng hàm qrgramschmidt() để thực hiện thuật toán trên:
function [Q, R] = qrgramschmidt(A);
% Phan tich mt bang thuat toan Gram ‐ Schmidt
[m,n] = size(A);
R(1,1) = norm(A(:, 1));
Q(:,1) =A(:, 1)/R(1, 1);
for k = 2:n
R(1:k‐1, k) = Q(1:m, 1:k‐1)ʹ*A(1:m, k);
z = A(1:m, k) ‐ Q(1:m, 1:k‐1)*R(1:k‐1, k);
R(k,k) = norm(z);
Q(1:m,k) = z/R(k, k);
end
Để phân tích một ma trận ta dùng chương trình chương trình
ctqrgamschmidt.m:
clear all, clc
a = [ 1 2 3 4 5; 6 7 8 9 0; 3 4 5 6 7; 8 9 0 1 2; 2 4 6 8 1];
[q, r] = qrgramschmidt(a)
§10. PHÂN TÍCH MA TRẬN THEO GIÁ TRỊ RIÊNG
Cho ma trận [A], ta có:
[A][X] = λ[X]
Nếu ta đặt [U] là một ma trận mà các cột của nó là các vec tơ riêng của ma
trận [A] và ma trận [Λ] là ma trận đường chéo có các phần tử trên đường chéo
chính là λi thì:
[A][U] = [Λ][U]
hay:
[A] = [U][Λ][U]‐1
Dạng này của ma trận được gọi là dạng phân tích theo giá trị riêng và vec tơ
riêng. Ta dùng chương trình cteigdecom.m để phân tích ma trận:
clear all, clc
77
a = [ 1 3 5; 3 4 9; 5 9 6];
[L, U] = eigjacobi(a)
§11. PHÂN TÍCH LQ
Cho ma trận [A]T, ta có thể phân tích QR ma trận này thành:
[A]T = [Q1][R1]
Do ([Q][R])T = [R1]T[Q1]T nên:
([A]T)T = [A] = [L][Q]
và ta nhận được phân tích LQ của ma trận [A]. Ta xây dựng hàm lqdecom()
để thực hiện thuật toán này:
function [Q, L] = lqdecom(A)
A = Aʹ;
[Q, L] = qrdecom(A);
L = Lʹ;
Q = Qʹ;
Để phân tích một ma trận ta dùng chương trình ctlqdecom.m:
clear all, clc
a = [ 1 3 5; 2 4 6; 7 8 9];
[Q, L] = lqdecom(a)
§12. PHÂN TÍCH JORDAN
1. Ma trận có thể đường chéo hoá: Ma trận [A] gọi là có thể đường chéo hoá
nếu và chỉ nếu tồn tại phép biến đổi đồng dạng [V] sao cho [A] = [V][Λ][V]‐1
trong đó [Λ] là ma trận đường chéo [Λ] = diag(λ1, λ2,..., λn). Điều kiện cần để
[A] có thể đường chéo hoá là [A] có n vec tơ riêng độc lập tuyến tính. Điều
kiện đủ để [A] có thể đường chéo hoá là [A] có n giá trị riêng phân biệt vì khi
[A] có n giá trị riêng phân biệt thì các vec tơ riêng tương ứng là độc lập tuyến
tính. Số lần lặp lại mi của giá trị riêng λi gọi là vô số đại số (algebraic
multiplicity) của λi, kí hiệu là AM(λi ). Số vec tơ riêng độc lập tuyến tính
tương ứng với giá trị riêng λi gọi là vô số hình học (geometric multiplicity)
của λi, kí hiệu là GM(λi ).
78
2. Dạng Jordan: Khi không thể tìm được n giá trị riêng phân biệt, nghĩa là ma
trận [A] không có n vec tơ riêng độc lập tuyến tính thì ma trận [A] không thể
đường chéo hoá. Tuy nhiên, nếu có phép biến đổi đồng dạng [M] biến đổi [A]
thành [J]:
[A] = [M][J][M]‐1
Trong đó [J] là ma trận gần đường chéo:
[J] = diag(J1,..., Jn)
[ ]
i
i
ii
i
i
1 0 0
0 1
J
1
0
λ⎡ ⎤⎢ ⎥λ⎢ ⎥λ⎢ ⎥= ⎢ ⎥λ⎢ ⎥⎢ ⎥λ⎣ ⎦
L
O M
M O O M
M O O
M L L
là khối Jordan và ma trận [J] được gọi là dạng Jordan kinh điển của ma trận
[A]. Số khối Jordan bằng số vec tơ riêng độc lập tuyến tính của ma trận [A],
nghĩa là bằng GM(λi). Cụ thể, mỗi vec tơ riêng độc lập tuyến tính tương ứng
với mỗi khối. Do vậy nếu ma trận [A] có các vec tơ riêng độc lập tuyến tính
thì dạng Jordan trùng với dạng đường chéo của ma trận [S]‐1[A][S] = [Λ] trong
đó [Λ] = diag(λ1,..., λn) và [S] có các cột là các vec tơ riêng của [A]
3. Xây dựng dạng Jordan của ma trận [A]: Khi [A] không có n vec tơ riêng
độc lập tuyến tính để tạo ra các cột của ma trận [M] thì ta có thể thêm các vec
tơ độc lập tuyến tính vào các vec tơ riêng để tạo ra ma trận này.
Trước hết ta khảo sát một giá trị riêng λi có GM(λi) < AM(λi). Nếu
GM(λi) = pi , AM(λi) = mi thì ta cần tìm mi ‐ pi vec tơ độc lập tuyến tính để kết
hợp với giá trị riêng này. Các vec tơ này được tạo từ các vec tơ riêng và được
gọi là vec tơ riêng tổng quát
Các file đính kèm theo tài liệu này:
- chuong_002.pdf