Về nghịch đảo Moore-Penrose của ma trận

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

36
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Khái niệm nghịch đảo Moore-Penrose ra đời bởi hai nhà toán học độc lập E. H. Moore và nhà toán học R. Penrose. Bài viết trình bày việc tìm các biểu diễn tường minh cho nghịch đảo Moore-Penrose và một số ứng dụng của nó.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Về nghịch đảo Moore-Penrose của ma trận

VỀ NGHỊCH ĐẢO MOORE-PENROSE CỦA MA TRẬN NGUYỄN THANH NGUYÊN Khoa Toán học Tóm tắt: Trong bài báo này, chúng tôi tìm các biểu diễn tường minh cho nghịch đảo Moore-Penrose và một số ứng dụng của nó. 1 GIỚI THIỆU Khái niệm nghịch đảo Moore-Penrose ra đời bởi hai nhà toán học độc lập E. H. Moore và nhà toán học R. Penrose. Vào năm 1955 Penrose đã chứng tỏ được rằng với mọi ma trận hữu hạn A thực hoặc phức , có duy nhất một ma trận X thỏa mãn 4 phương trình sau (mà chúng ta gọi là phương trình Penrose) AXA = A (1) XAX = X (2) (AX)∗ = AX (3) (XA)∗ = XA (4) với A∗ là ma trận chuyển vị liên hợp của A. Khi đó ta ký hiệu X bằng A† và A† được gọi là giả nghịch đảo Moore-Penrose của ma trận A. Lý thuyết nghịch đảo Moore-Penrose đã phát triển một cách nhanh chóng và có nhiều ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau. Do đó việc đi tìm các tính chất đặc biệt và biểu diễn tường minh cho nghịch đảo Moore-Penrose cho một lớp các ma trận đặc biệt luôn là vấn đề thời sự đã thu hút sự quan tâm của nhiều nhà Toán học trên thế giới. Mục đích chính của bài báo là tìm các biểu diễn tường minh cho nghịch đảo Moore- Penrose của một số dạng ma trận đặc biệt và một số hướng tiếp cận để tính nghịch đảo Moore-Penrose của một ma trận bất kỳ. Kết quả chính của bài báo là tổng quan lại một số cách biểu diễn nghịch đảo Moore- Penrose đã biết. Từ đó chúng tôi cải tiến để đưa ra một số biểu diễn khác một cách tường minh và hiệu quả hơn. Ngoài ra chúng tôi còn giới thiệu một số ứng dụng của nghịch đảo Moore-Penrose trong thực tế như sự phục hồi ảnh thông qua nghịch đảo Moore-Penrose. Phương pháp này hiệu quả hơn phương pháp Lagrange trước đây. Bài báo được chia làm 3 phần Phần 1. Một số tính chất của nghịch đảo Moore-Penrose Kỷ yếu Hội nghị Khoa học Sinh viên năm học 2014-2015 Trường Đại học Sư phạm Huế, tháng 12/2014: tr. 20-29
NGHỊCH ĐẢO MOORE-PENROSE CỦA MA TRẬN 21 Phần 2. Công thức tính nghịch đảo Moore-Penrose Phần 3. Ứng dụng của nghịch đảo Moore-Penrose và sử dụng MATLAB 7 để tính nghịch đảo Moore-Penrose 2 TÍNH CHẤT CỦA NGHỊCH ĐẢO MOORE-PENROSE Tuy nghịch đảo Moore-Penrose của một ma trận bất kỳ không hoàn toàn có những tính chất giống hệt nghịch đảo thông thường, nhưng nhiều tính chất vẫn được thỏa mãn khi ta thay nghịch đảo thông thường bằng giả nghịch đảo Moore-Penrose. Định lý sau chứng tỏ điều đó Định lý 2.1. [5] Cho A ∈ Cm×n r , khi đó 1. (A† )† = A 8. R(A) = R(AA† ) = R(AA∗ ). 2. (A∗ )† = (A† )∗ 9. R(A† ) = R(A∗ ) = R(A† A) = 3. (AT )† = (A† )T R(A∗ A). 4. A∗ = A∗ AA† = A† AA∗ 10. R(I − AA† ) = N (AA† ) = N (A∗ ) = 5. (A∗ A)† = A† A∗† N (A† ) = R(A)⊥ . 6. A† = (A∗ A)† A∗ = A∗ (AA∗ )† 11. R(I − A† A) = N (A† A) = N (A) = 7. Nếu A = A∗ thì AA† = A† A R(A∗ )⊥ . Định lý sau đây thể hiện sự tương đương giữa định nghĩa về ma trận giả nghịch đảo được đưa ra bởi Penrose năm 1955 với định nghĩa của Moore được đưa ra vào năm 1935. Định lý 2.2. Cho A ∈ Cm×n , khi đó ma trận A† là ma trận nghịch đảo Moore- Penrose của A khi và chỉ khi A† thỏa mãn các tính chất sau 1. AA† = PR(A) , 2. A† A = PR(A† ) 2.1 Tính chất giải tích của nghịch đảo Giả nghịch đảo Moore-Penrose có rất nhiều tính chất đặc biệt và một trong số là "tính chất giải tích" của nghịch đảo Moore-Penrose. Tính chất này cho chúng ta một công thức tính nghịch đảo Moore-Penrose của một ma trận bất kỳ.
22 NGUYỄN THANH NGUYÊN Bổ đề 2.3. [4] Cho A ∈ Cn×n và A là ma trận đối xứng, khi đó PA = lim (A + λI)−1 A = lim A(A + λI)−1 λ→0 λ→0 Định lý 2.4. [4] Cho A ∈ Cm×n r . Khi đó A† = lim (A∗ A + λI)−1 A∗ = lim A∗ (AA∗ + λI)−1 . λ→0 λ→0 Ví dụ 1. Với mọi vectơ x ∈ Cn ta có   0 nếu x = 0 x† = (x∗ x)−1 x∗ = x∗ .  ∗ nếu x 6= 0 xx 3 CÔNG THỨC TÍNH MA TRẬN MOORE-PENROSE Cho H ∈ Cm×n và E1 , E2 , ..., Ek là các phép biển đổi dòng sơ cấp. Khi đó tồn tại ma trận chuyển vị P sao cho Ir K EHP = O O trong đó E = Ek Ek−1 ...E2 E1 . Thuật toán 3.1. Để tính nghịch đảo Moore-Penrose của ma trận A bất kỳ cho trước ta thực hiện lần lượt các bước sau 1. Tìm dạng ma trận có hạng đầy đủ của ma trận A - Bằng các phép biển đổi sơ cấp dòng, chuyển ma trận A thành ma trận Hermite dạng chuẩn tắc . - Xác định ma trận G biết G EA = O trong đó E = Ek Ek−1 ...E1 với Ek , Ek−1 , ..., E1 là các phép biến đổi sơ cấp dòng. - Xác định ma trận chuyển vị P và ma trận con P1 của P trong đó P1 là ma trận r cột đầu tiên của ma trận P với r là hạng của ma trận A. - Đặt F = AP1 . Khi đó A = F G. 2. Tính nghịch đảo Moore-Penrose của ma trận A qua công thức A† = G∗ (F ∗ AG∗ )−1 F ∗
NGHỊCH ĐẢO MOORE-PENROSE CỦA MA TRẬN 23 Dựa vào định lý 2.2 chúng ta có thể xây dựng thuật toán tính nghịch đảo Moore- Penrose của ma trận A dựa vào việc xác định ảnh của một cơ sở trong Cn qua A† . Thuật toán 3.2. Để tính nghịch đảo Moore-Penrose của ma trận A ta thực hiện lần lượt các bước sau - Xác định một cơ sở của R(A∗ ) và N (A∗ ). - Xác định ảnh của một cơ sở trong R(A∗ ) qua ma trận A. Từ đó xác định ảnh của một cơ sở trong Cn qua ma trận A† . - Tính ma trận A† . Định lý 3.3. [Công thức Cayley-Hamilton][4] 1. Cho A ∈ Cn×n là ma trận Hermite khi đó đa thức đặc trưng của A có thể được viết thành PA (λ) = aλk (1 − λϕ(λ)) trong đó n − k là hạng của A. Khi đó nếu A khả nghịch thì A−1 = ϕ(A) và trong trường hợp tổng quát A† = ϕ(A) + ϕ(0)[Aϕ(A) − I]. 2. Nếu H ∈ Cm×n và nếu đa thức đặc trưng của H ∗ H được xác định bởi aλk (1 − λϕ(λ), thì H † = ϕ(H ∗ H)H ∗ . Ta có thể tính đa thức đặc trưng của một ma trận qua công thức sau PA (λ) = (−λ)n + C1 (−λ)n−1 + ... + Ck (−λ)n−k + ... + Cn trong đó Ck là tổng các định thức con cấp k lập nên từ các dòng và các cột với chỉ số giống nhau.
24 NGUYỄN THANH NGUYÊN 3.1 Nghịch đảo Moore-Penrose của ma trận khối và tổng hai ma trận 3.1.1 Nghịch đảo Moore-Penrose của ma trận khối Khi tính toán nghịch đảo Moore-Penrose của một ma trận A ∈ Cm×n , kích thước của ma trận hay độ phức tạp của bài toán tìm nghịch đảo có thể được giảm bớt nếu ma trận A được viết dưới dạng ma trận khối như sau A11 A12 A= A21 A22 Do đó trong phần này chúng ta sẽ nghiên cứu về công thức tính nghịch đảo Moore- Penrose của ma trận khối và một số dạng ma trận khối đặc biệt. Định lý 3.4. [5] Cho ma trận A ∈ Cm×n r với r < m, n. Khi đó, nếu A11 A12 P AQ = A21 A22 trong đó P và Q là những ma trận chuyển vị và A11 ∈ Cr×r r thì † Ir (Ir + T T ∗ )−1 A−1 ∗ −1 A =Q 11 (Ir + S S) Ir S ∗ P T∗ với T = A−1 −1 11 A12 và S = A21 A11 . Nhận xét 3.5. Nếu A ∈ Cr×n r thì khi đó công thức trở thành † Ir A =Q (Ir + T T ∗ )−1 A−1 1 T∗ với T = A−1 1 A2 . Định lý 3.6. Với Ai là ma trận cấp ri × si , ta có  †   A1 0 . . . 0 A1 † 0 ... 0 0 A2 . . . 0 0 A2 † ... 0      = .     ... ... ... ... ... ... ... ...      0 0 . . . An 0 0 . . . An †
NGHỊCH ĐẢO MOORE-PENROSE CỦA MA TRẬN 25 3.1.2 Nghịch đảo của tổng 2 ma trận Định lý 3.7. [2] Cho 2 ma trận A, B ∈ Cm×n . Khi đó nếu AB ∗ = 0 thì (A + B)† = A∗ (AA∗ + BB ∗ )† + B ∗ (AA∗ + BB ∗ )† . Nhận xét 3.8. với AB ∗ = O khi đó ta có 1. Nếu đặt ma trận U = A B A∗ (AA∗ + BB ∗ )† † ∗ ∗ † U = U (U U ) = B ∗ (AA∗ + BB ∗ )† Từ nhận xét trên chúng ta có thể thiết lập được thuật toán tính nghịch đảo Moore-Penrose của tổng 2 ma trận A, B nếu AB ∗ = O dựa vào định lý 3.4 và định lý 3.7. Chẳng hạn xét 2 ma trận 1 2 3 0 −3 2 A= và B = 1 0 0 0 −3 2 Ta có AB ∗ = O   0 13   28 −28   1 2 3 0 −3 2 1 42 −42    † Đặt U = . Khi đó U = .  1 0 0 0 −3 2 182  0 0      0 −39  0 26 Từ đó ta có       0 13 0 0 0 13 1  1  1  (A + B)† = 28 −28  + 0 −39  = 28 −67  . 182 182 182 42 −42 0 26 42 −16 2. Nếu AB ∗ = A∗ B = O thì (A + B)† = A† + B † . 3.2 Nghịch đảo Moore-Penrose của một số dạng ma trận đặc biệt 3.2.1 Ma trận có hạng bằng 1 1 Cho ma trận A ∈ Cm×n và rankA = 1. Khi đó A† = A∗ T rA∗ A
26 NGUYỄN THANH NGUYÊN 3.2.2 Ma trận chéo  †   λ1 0 ... 0 λ1 † 0 . . . 0  0 λ2 ... 0 0 λ2 † . . . 0      = ,     ... ... ... ... ... ... ... ...     0 0 . . . λn 0 0 . . . λn †   0 nếu λi = 0 trong đó λ†i = 1 .  nếu λi 6= 0 λi 3.2.3 Ma trận trực giao Cho ma trận A ∈ Cm×n và A = (aij ) là ma trận sao cho ai aj = 1 (i 6= j) với ai là cột thứ i của ma trận A khi đó  Pm † a2 0 ... 0  i=1 i1   m  a2i2  0 P ... 0  A† =   ∗  A  i=1  ... ... ... ...     m  a2in P 0 0 ... i=1 Nhận xét 3.9. Nếu A ∈ Cn×n là ma trận trực giao thì khi đó A† = A∗ . 3.2.4 Ma trận Hermite Để tính nghịch đảo Moore-Penrose của ma trận Hermite H ta thực hiện lần lượt các bước sau - Tính đa thức đặc trưng PH (λ) và tìm giá trị riêng khác nhau của H. - Tìm các vectơ riêng ứng với mỗi giá trị riêng khác nhau bằng cách xét phương trình (H − λi I)x = 0 - Trực chuẩn các vectơ riêng n - Tính H † = λ†i ci c∗i . P i=1
NGHỊCH ĐẢO MOORE-PENROSE CỦA MA TRẬN 27 4 ỨNG DỤNG CỦA NGHỊCH ĐẢO MOORE-PENROSE VÀ TÍNH NGHỊCH ĐẢO MOORE-PENROSE BẰNG MATLAB 7 4.1 Tìm nghiệm của hệ phương trình tuyến tính bất kỳ Định lý 4.1. Cho A ∈ Cm×n , b ∈ Cm . Khi đó R(b) ⊆ R(A) khi và chỉ khi AA† b = b. Định lý 4.2. Cho A ∈ Cm×n và b ∈ Cm . Giả sử rằng AA† b = b. Khi đó với bất kỳ vectơ có dạng x = A† b + (I − A† A)y với y ∈ Cn bất kỳ (1) là nghiệm của hệ phương trình Ax = b. Hơn nữa, tất cả các nghiệm của hệ phường trình Ax = b đều có dạng như trên. Nhận xét 4.3. 1. Nếu phương trình tuyến tính Ax = b có nghiệm thì nghiệm x = A† b là nghiệm bình phương tối tiểu của phương trình. 2. Nếu phương trình tuyến tính Ax = b vô nghiệm thì ta có thể coi A† b là một "nghiệm gần đúng" của phương trình. 4.2 Nghịch đảo Moore-Penrose trong phục hồi ảnh kỹ thuật số [1] Trong quá trình phục hồi ảnh bị mờ, người ta sử dụng mối quan hệ giữa 2 thành phần xout và xin trong đó xout là hình ảnh xuống cấp được X-quang số hóa và xin là bản gốc xác định hình ảnh đó đã được phục hồi. Mối quan hệ giữa xout và xin được thể hiện qua phương trình sau Hxin = xout Tuy nhiên, vì có vô số nghiệm xin thỏa mãn phương trình Hxin = xout , nên việc bổ sung thêm 1 tiêu chuẩn để tìm thấy một vectơ phục hồi mạnh là điều cần thiết. Và tiêu chuẩn để phục hồi hình ảnh mờ mà chúng ta thường sử dụng là tối thiểu khoảng cách của các dữ liệu của hình ảnh, nghĩa là, tìm nghiệm bình phương tối tiểu của phương trình Hxin = xout . Như đã nêu ở phần 4.1, ta đã chứng minh được rằng nghiệm bình phương tối tiểu của phương trình dạng Ax = b là x˜ = A† b
28 NGUYỄN THANH NGUYÊN Hình 1: Hình ảnh X-quang Chúng ta nhận thấy kết quả xử lý hình ảnh qua hai phương pháp Lagrang và giả nghịch đảo là giống nhau tuy nhiên tốc độ xử lý ảnh khi dùng phương pháp nghịch đảo nhanh hơn nhiều so với phương pháp Lagrang. Và đây là một trong những ứng dụng phổ biến nhất của nghịch đảo Moore-Penrose. 4.3 Sử dụng MATLAB 7 để tính nghịch đảo Moore-Penrose Phần mềm MATLAB 7.0 có thể sử dụng trên Intel(R) Pentium(R) Dual CPU T2310@1.46GHz 1.47 GHz 32-bit system, RAM 2GB chạy trên Windows Vista Home Premium Operating System. function Y=Moore(A) H=A’*A; [m,n]=size(H); r=rank(H); P=poly(H); k=m-r; [z,x]= size(P); v=x-k; for i=1:x if i>v | i
NGHỊCH ĐẢO MOORE-PENROSE CỦA MA TRẬN 29 w(1,i)=0; end t=deconv(q,w); [g,h]=size(t); c=zeros(m); for i=1:h c=c+t(1,i)*H^(h-i); end Y=c*A’ TÀI LIỆU THAM KHẢO [1] Spiros Chountasis, Vasilios N. Katsiki và Dimitrios Pappas (2009), Applications of the Moore-Penrose Inverse in Digital Image Restoration, Hindawi Publishing Corporation. [2] Ching-hsiang Hung và T.L.Markham (1974), The Moor-Penrose Inverse of a Partitioned matrix, University of South Carolina. [3] Xuzhou Chen và Jun ji (2011), Computing the Moore-Penrose Inverse of à matrix through Symmetric Rank-One Updates, American Journal of Computa- tional Mathematics,2011,1,147-151. [4] Arthur Albert (1972), Regression and the Moore-Penrose pseudoinverse, Boston University, Boston, Massachusetts. [5] A. Ben-Israel and T. N. E Greville (2003), Generalized Inverses: Theory and Applications, 2nd Edition, Springer-Verlag, NewYork. [6] A. Ben-Israel (1986), Generalized inverses of matrices: a perspective of the work of Penrose, Math. Proc. Camb. Phil. Soc. 100, 401-425. NGUYỄN THANH NGUYÊN SV lớp Toán 3, Khoa Toán học, trường Đại học Sư phạm - Đại học Huế