CHƯƠNG 2: MA TRẬN

Chia sẻ: hikaru28

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  ⎡ A∗ ⎤ = ⎡ A ⎤ .  Ví  dụ  ma  trận  ⎣ ⎦ ⎣ ⎦ 2 + j⎤ ⎡ 3  là ma trận Hermite.  [A] = ⎢ 2−j 1 ⎥ ⎣ ⎦ T      Ma trận Householder là một ma trận vuông dạng:  2 [ H] = [E ] − T [ U ][ U ]T   [U]...

Bạn đang xem 20 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Thể loại:

  Khoa Học Tự Nhiên  » Toán học

Chủ đề liên quan:

 

Nội dung Text: CHƯƠNG 2: MA TRẬN

 

  1. 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  T liên  hợp  của  phân  tử  ở  hàng  j  cột  i  ⎡ A∗ ⎤ = ⎡ A ⎤ .  Ví  dụ  ma  trận  ⎣ ⎦ ⎣ ⎦ ⎡ 3 2 + j⎤ [A] = ⎢  là ma trận Hermite.  ⎣ 2−j 1 ⎥⎦    Ma trận Householder là một ma trận vuông dạng:  2   [ H] = [E ] − T [ U ][ U ]T   [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]  T  Ma trận phức [U] gọi là ma trận unita nếu  ⎡ U ⎤ ⎡ U∗ ⎤ = ⎡E ⎤ . Ví dụ ma  ⎣ ⎦⎣ ⎦ ⎣ ⎦ ⎡ 1 + j −1 + j ⎤ ⎢ 2 2 ⎥ trận  [ U ] = ⎢ ⎥  là ma trận unita  ⎢ 1+ j 1− j ⎥ ⎢ 2 ⎣ 2 ⎥ ⎦  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:      ‐  X 1 = max x j   j n     ‐  X 2 = ∑ x j   j=1 58
  2. n ∑ xj   2     ‐  X 3 = j=1    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     ‐  A 1 = max ∑ a i ,j   i j=1 n     ‐  A 1 = max ∑ a i ,j   j i =1 n ∑ a i ,j   2     ‐  A 3 = i ,j=1    Ma trận [A] gọi là xác định dương nếu với vec tơ [x] bất kì ta có:       [ x]T[ 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ó:       [ x ]T[ 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.  [ U ][ U ]T       [ H] = [ E] −             (1)  Q 59
  3. Trong đó:  1 1 Q = [ U ] [ U ] = [ U ]    T 2               (2)  2 2 Do [H] đối xứng nên:      ⎛ [ U ][ U ]T ⎞⎛ E − [ U][ U]T ⎞   [ H] [ H] = [ H][ H] = ⎜ [ E] − T ⎟⎜ [ ] ⎟      ⎝ Q ⎠⎝ Q ⎠                          = [ E ] − 2 ( T ) [ U ][ U]T + [ U ] [ U ][ U ] [ U ]   T Q Q2                         = [ E ] − 2 [ U ][ U ]T + [ U] ( 2Q ) [ U ]T = E   2 [ ] 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]     [I1 ] = ⎡1 T   ⎣ 0 L 0⎤   ⎦           Ta có:  [ U ][ U ]T ⎞ X = ⎧ E − [ U] ([ X ] + k [ I1 ]) ⎫ X   T ⎛ ⎪ ⎪   [ H][ X ] = ⎜ [E] − ⎟ [ ] ⎨[ ] ⎬[ ] ⎝ Q ⎠ ⎪ Q ⎪ ⎩ ⎭ [ U ] ([ X ]T[ X ] + k [ I1 ] [ X ]) [ U ] ( k 2 + k[ X1 ]) T   = [X] − = [X] −   Q Q Nhưng:    2 ( T T ) 2Q = ([ X ] + k [ I1 ]) ([ X ] + k [ I1 ]) = [ X ] + k [ X ] [ I1 ] + [ I1 ] [ X ] + k 2 [ I1 ] [ I1 ]   T T = k 2 + 2kx1 + k 2 = 2(k 2 + kx1 )   Như vậy:  [ H][ X ] = [ X ] − [ U ] = −k [ I1 ] = ⎡−k 0 0 L 0⎤   T   ⎣ ⎦     (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:  ⎡ 1 [ 0 ]T ⎤ ⎡ a11 [ X ]T ⎤ ⎡ a11 [ X ]T ⎤   ⎡P1 ⎤[ A ] = ⎢ ⎣ ⎦ ⎥⎢ ⎥=⎢ ⎥      (5)  ⎣[ 0] [ H] ⎦ ⎣[ X ] [ A′] ⎦ ⎣[ H][ X ] [ H][ A′]⎦ 60
  4. 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:  ⎡a11 ⎤ ⎢ −k ⎥ ⎡ a11 ⎤ ⎢ ⎥   ⎢ H H ⎥ = ⎢ 0 ⎥    ⎣[ ][ ]⎦ ⎢ M ⎥ ⎢ ⎥ ⎢0⎥ ⎣ ⎦ Phép biến đổi:  ⎡ a ([H][ X ]) ⎤ → [ A]   T     ⎡P1 ⎤[ A ]⎡P1 ⎤ = ⎢ 11 ⎣ ⎦ ⎣ ⎦ ⎥       (6)  ⎢[ H ][ X ] ⎣ [ H ][ A′][ H ]⎥ ⎦ 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à:                1  0  0  0  a11  a12  a13  a14  1 0 0 0 a11  ‐k  0  0   0  a21  0 ‐k    0  [Q]  ×  a31  [A’] ×  0 [Q] =  0  [Q][A’]  [Q]    0  a41  0 0    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  [ P2 ][ A ][ P2 ] → [ A ] , trong đó:  ⎡[ E 2 ] [ 0 ]T ⎤   [P2 ] = ⎢ ⎥                (7)  ⎣ [0] [ H] ⎦ 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:  ⎡[ Ei ] [ 0 ]T ⎤   [Pi ] = ⎢ ⎥       i = 1, 2,..., n ‐ 2  ⎣ [0] [H] ⎦ để có được ma trận ba đường chéo(tridiagonal). Ta có:  61
  5. ⎛ [ U ][ U ]T ⎞ = A′ − [ A′][ U] U T = A′ − V U T     [ A′][H] = [ A′]⎜ [E] − ⎟ [ ] [ ] [ ] [ ][ ] ⎝ Q ⎠ Q Trong đó:  [ A′][ U]       [V] =               (8)  Q Do vậy:  ⎛ [ U ][ U ]T ⎞ A′ − V U T     [ H ][ A ′][ H ] = ⎜ [ E ] − Q ( ⎟ [ ] [ ][ ] ) ⎝ ⎠ [ U ][ U]T A′ − V U T                          = [ A′] − [ V ][ U ]T − Q ( [ ] [ ][ ] ) [ U ] ([ U ]T [ A′]) [ U ]([ U]T [ V ])[ U]T            = [ A′] − [ V ][ U ] − + T       Q Q            = [ A′] − [ V ][ U ] − [ U ][ V ] + 2g [ U ][ U ]   T T T Trong đó:    g= [ U ]T [ V ]                   (9)  2Q Đặt: [W] = [V] ‐ g[U]                  (10)  Ta thấy ngay phép biến đổi có dạng:    [ H][ A′][ H] = [ A′] − [ W ][ U ]T − [ U ][ W ]T           (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   ‐ Đặt  ⎡ X ⎤ = ⎡a i+1,i ⎣ ⎦ ⎣ a i+ 2 ,i L a n ,i ⎤   ⎦   ‐ Tính  [ X ] . Cho k =  [ X ]  nếu x1 > 0 và k = ‐ [ X ]  nếu x1 < 0   T   ‐ Cho  ⎡ U ⎤ = ⎡k + x1 ⎣ ⎦ ⎣ x 2 L x n −i ⎤   ⎦ [ U] 2   ‐ Tính  Q =   2   ‐ Tính  [ V ] = [ A′][ U]   Q [U] [ V] T   ‐ Tính  g =   2Q 62
  6.   ‐ Tính [W] = [V] ‐ g[U]  ‐ Tính  [ A ] = [ A′] − [ W ][ U ] − [ U ][ W ]   T T     ‐ Đặt  a i ,i+1 = a i+1,i = − 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;  63
  7. Để  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:  ⎡a 11 a 12 a 13 L a 1,n ⎤ ⎢a a 22 a 23 L a 2 n ⎥ ⎢ 21 ⎥   [ H ] = ⎢ 0 a 32 a 33 L a 2 n ⎥   ⎢ M M M L M⎥ ⎢ ⎥ ⎢0 ⎣ 0 0 L a nn ⎥ ⎦ 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   ‐ Đặt  ⎡ X ⎤ = ⎡0 a i+ 2 ,i L a n ,i ⎤   ⎣ ⎦ ⎣ ⎦   ‐ Tính  [ X ] . Cho α=  [ X ]  nếu ai+2,i > 0 và α = ‐ [ X ]  nếu ai+2,i < 0   T   ‐ Cho  ⎡ U ⎤ = ⎡0 α + x 2 L x n −i ⎤   ⎣ ⎦ ⎣ ⎦ [U] 2   ‐ Tính  β =   2 [ U ][ U′]   ‐ Tính  [ P ] = [ E ] −   β 64
  8.   ‐ 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  65
  9. 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:  ⎡ 1 0 0⎤ ⎡ r11 r12 r13 ⎤ ⎢l ⎥ [ L] = ⎢ 21 1 0 ⎥ [ R ] = ⎢ 0 r22 r23 ⎥   ⎢ ⎥ ⎢l 31 l 32 1 ⎥ ⎣ ⎦ ⎢ 0 0 r33 ⎥ ⎣ ⎦  Để tìm lij và rij ta thực hiện phép nhân. Sau khi nhân ta có:  ⎡r11 r12 r13 ⎤ ⎢r l ⎥  [ A ] = ⎢ 11 21 r12l 21 + r22 r13l 21 + r23 ⎥ ⎢r11l 31 r12 l 31 + r22 l 32 r13l 31 + r23l 32 + r33 ⎥ ⎣ ⎦ 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ó:  ⎡r11 r12 r13 ⎤ ⎢0 r ⎥    [ A1 ] = ⎢ 22 r23 ⎥ ⎢0 r22 l 32 r23l 32 + r33 ⎥ ⎣ ⎦ 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ó:  ⎡r11 r12 r13 ⎤   [ A 2 ] = ⎢ 0 r22 r23 ⎥   ⎢ ⎥ ⎢ 0 0 r33 ⎥ ⎣ ⎦ 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  66
  10. 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:  ⎡ l11 0 0 ⎤ ⎡ 1 r12 r13 ⎤       [ L ] = ⎢l 21 l 22 0 ⎥ ⎢ ⎥ [ R ] = ⎢0 1 r23 ⎥   ⎢ ⎥ ⎢l 31 l 32 l 33 ⎥ ⎣ ⎦ ⎢0 0 1 ⎥ ⎣ ⎦ Để tìm lij và rij ta thực hiện phép nhân. Sau khi nhân ta có:  67
  11. ⎡l11 l11r12 l11r13 ⎤ ⎢l ⎥  [ A ] = ⎢ 21 l 21r12 + l 22 l 21r13 + l 22r23 ⎥ ⎢l 31 l 31r12 + l 32 l 31r13 + l 32r23 + l 33 ⎥ ⎣ ⎦ 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   i −1 rij = a ij − ∑ l ik rkj   ( j = i tới n)  k =1 i −1 a ji − ∑ l jk rki       l ji = k =1   (j = i tới n)  rii 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  68
  12.         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:  ⎡a11 a12 a13 ⎤ ⎡ l11 0 0 ⎤ ⎡l11 l 21 l 31 ⎤ ⎢a ⎥ ⎢ ⎥⎢ ⎥ ⎢ 21 a 22 a 23 ⎥ = ⎢l 21 l 22 0 ⎥ ⎢ 0 l 22 l 32 ⎥   ⎢a 31 a 32 a 33 ⎥ ⎢l 31 l 32 l 33 ⎥ ⎢ 0 0 l 33 ⎥ ⎣ ⎦ ⎣ ⎦⎣ ⎦ Sau khi thực hiện phép nhân ta có:  ⎡a11 a12 a13 ⎤ ⎡l11 2 l11l 21 l11l 31 ⎤   ⎢a ⎥ = ⎢l l a 22 a 23 ⎥ ⎢ 11 21 l 2 + l 2 ⎥ l 21l 31 + l 22l 32 ⎥   ⎢ 21 21 22 ⎢a 31 a 32 a 33 ⎥ ⎢l11l 31 l 21l 31 + l 22 l 32 ⎣ ⎦ ⎣ l 31 + l 32 + l 33 ⎥ 2 2 2 ⎦ 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ó:  l11 = a11 l 21 = a 21 / l11 l 31 = a 31 / l11   l 22 = a 22 − l 21 2 l 32 = (a 32 − l 21l 31 ) / l 22 l 33 = a 33 − l 31 − l 32 2 2 Tổng quát, với ma trận cấp n, ta có:  ([L][L] ) j = l i1l j1 + l i2 l j2 + ⋅⋅⋅+ = ∑ l ik l jk i ≥ j   T ij k =1 Cân bằng với phần tử của ma trận [A] ta có:  j   a ij = ∑ l ik l jk i = j, j + 1,...,n j = 1,2,...,n   k =1 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ó:    l11 = a11 l i1 = a i1 / l11   Đối với cột khác, rút lij ra khỏi tổng ta có:  69
  13. j−1   a ij = ∑ l ik l jk + l ijl jj   k =1 Nếu i = j (phần tử trên đường chéo) thì:  j−1   l jj = a jj − ∑ l 2 jk j = 2,3,...,n   k =1 và phần tử nằm ngoài đường chéo:  j−1 ⎛ ⎞1   l ij = ⎜ a ij − ∑ l ik l jk ⎟ j = 2, 3,..., n i = j + 2, j + 3,...,n   ⎝ k =1 ⎠ l jj 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;  70
  14. 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].     [Hn−1 ][Hn−2 ] ⋅ ⋅ ⋅ [H1 ][ A ] = [ R ]               (1)  Như vậy:  [ A ] = ([ Hn−1 ][ H n−2 ] ⋅⋅ ⋅ [ H1 ]) [ R ] = [ H1 ] ⋅ ⋅ ⋅ [ Hn−2 ] [H n−1 ][ R ] −1 −1 −1     (2)  = [ H1 ] ⋅ ⋅ ⋅ [ H n −2 ][ H n −1 ][ R ] = [ Q ][ R ] Tích của tất cả các ma trận Householder:      [ Q] = [ H1 ]L[ H n −2 ][ H n −1 ]               (3)  không những đối xứng mà còn trực giao như mỗi ma trận [Hk]:  [ Q] [Q] = ([H1 ] ⋅ ⋅⋅ [Hn−2 ][Hn−1 ]) [H1 ] ⋅ ⋅⋅ [Hn−2 ][Hn−1 ] T T     = [ H n −1 ] [ H n −2 ] ⋅ ⋅ ⋅ [ H1 ] [ H1 ] ⋅ ⋅ ⋅ [ H n −2 ][ H n −1 ] = [ E ] T T T 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)  71
  15. 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  đó:  72
  16. x2   θ = arctg   x1 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 đó:  x1 x2 cos θ = c =   sin θ = s =   x +x 2 1 2 2 x +x 2 1 2 2 Do đó:  1 ⎡ x1 x 2 ⎤ ⎡ c s ⎤   [ Qθ ] = 2 ⎢ −x = x1 ⎥ ⎢ − s c ⎥   x1 + x 2 ⎣ 2 2 ⎦ ⎣ ⎦ Chú ý là như mong muốn:  ⎡ x1 + x 2 ⎤ 2 ⎡ x1 ⎤ ⎡ cx1 + sx 2 ⎤ ⎢ 2 ⎥ ⎡ x + x2 ⎤ 2 2 2   [ Qθ ] ⎢ ⎥ = ⎢ x 2 ⎦ ⎣ −sx1 + cx 2 ⎥ = ⎢ x1 + x 2 ⎥ = ⎢ 1 2 ⎥  ⎣ ⎦ ⎢ ⎥ ⎢ ⎣ 0 ⎥ ⎦ ⎣ 0 ⎦ 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:  ⎡ 1 L 0 L 0 L 0⎤ ⎢M O M M M O M⎥ ⎧δkl k ≠ i, l ≠ j ⎢ ⎥ ⎪ c k, l = i; k,l = j ⎢ 0 L c L s L 0⎥ ⎪ ⎢ ⎥   [ Gkl ] = ⎨ s k = i; l = j =⎢M M M O M M M⎥   ⎪ ⎢ 0 L −s L c L 0 ⎥ ⎪ −s k = j; l = i ⎩ ⎢ ⎥ ⎢M M 0 M M O M⎥ ⎢0 L 0 L 0 L 1⎥ ⎣ ⎦ 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à:  73
  17.   ∑g l lk g lp = δkp   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ó:  ⎧ ⎪∑ δkla lp = a kp k ≠ i, j ⎪ l ⎪   b kp = ∑ g kla lp = ⎨∑ g ila lp = ca ip + sa jp k = i    l ⎪ l ⎪∑ g jla lp = −sa ip + ca jp k = j ⎪ l ⎩ 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:  a jr a   s= 2   c = 2 ir 2   a jr + a ir 2 a jr + a ir Như vậy ta sẽ có:  −a jra ir + a ir b jr   b jr = = 0  a 2 + a ir jr 2 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;  74
  18. 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à:    v1 = a1   Để 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ó:    v 2 = y1 − ba1   với b được chọn sao cho v1 trực giao với v2:    v1v 2 = v1 (a 2 − bv1 ) = v1a 2 − bv1v1 = 0   hay:  va   b= 1 2   v 1v 1 Tiếp tục quá trình đến bước thứ k ta có:  k −1 ∑vv v   v ia k   vk = ak − i i =1 i i Như vậy thuật toán gồm các bước:   a   ‐  r11 = a1 , q1 = 1   r11 - lặp từ k = 2 đến n  ⎛ k −1 ⎞ q k = ⎜ a k − ∑ rik q i ⎟ rkk    ⎝ i =1 ⎠ với   rik = q iTa k    và rkk được chọn sao cho  q k = 1 , nghĩa là:  75
  19.   z = a k − q k rik     rkk = 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  76
  20. 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 ).     77
Theo dõi chúng tôi
Đồng bộ tài khoản