Tài liệu Cận dưới cho giá trị kỳ dị nhỏ nhất của ma trận (Luận văn thạc sĩ)

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI THỊ TUYẾN CẬN DƯỚI CHO GIÁ TRỊ KỲ DỊ NHỎ NHẤT CỦA MA TRẬN LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI THỊ TUYẾN CẬN DƯỚI CHO GIÁ TRỊ KỲ DỊ NHỎ NHẤT CỦA MA TRẬN LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Mã số: Toán ứng dụng 60 46 01 12 NGƯỜI HƯỚNG DẪN KHOA HỌC TS. NGUYỄN THANH SƠN Thái Nguyên - 2016 Mục lục Danh mục ký hiệu Mở đầu 1 Kiến thức chung về ma trận 1.1 Ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Định nghĩa ma trận . . . . . . . . . . . . . . . . . 1.1.2 Ma trận trực giao . . . . . . . . . . . . . . . . . . 1.2 Véc tơ riêng, giá trị riêng . . . . . . . . . . . . . . . . . . 1.3 Chuẩn của véc tơ và chuẩn của ma trận . . . . . . . . . . . 1.4 Khai triển SVD (singular value decomposition) của ma trận 1 . . . . . . 4 4 4 5 6 7 10 2 Một số cận dưới cho giá trị kỳ dị nhỏ nhất của ma trận hằng 2.1 Cận dưới cho giá trị kỳ dị nhỏ nhất của ma trận đường chéo trội . 2.2 Cận dưới cho giá trị kỳ dị của H - ma trận . . . . . . . . . . . . 14 14 19 3 Cận dưới cho giá trị kỳ dị nhỏ nhất của ma trận phụ thuộc tham số 3.1 Ma trận affine bức . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Cận dưới cho giá trị kỳ dị nhỏ nhất của ma trận bức affine . . . . 3.3 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 24 25 27 . . . . . . . . . . . . Kết luận Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 30 Danh mục ký hiệu Trong toàn luận văn, ta dùng những ký hiệu với các ý nghĩa xác định trong bảng dưới đây: Rn×m ai j AT A−1 SVD kxk kAk σi (A), i = 1, 2, · · · , n λi (A), i = 1, 2, · · · , n tập các ma trận thực cỡ n × m phần tử nằm trên dòng i, cột j ma trận chuyển của ma trận A ma trận nghịch đảo của ma trận A phân tích giá trị kỳ dị chuẩn của véc tơ x chuẩn của ma trận A tập hợp các giá trị kỳ dị của ma trận A tập hợp các giá trị riêng của A R+ UA |A| kí hiệu phần trong của không gian Rn+ bao đóng của U định thức của ma trận A ◦n i Mở đầu Giá trị kỳ dị của ma trận không chỉ đóng vai trò quan trọng trong toán học lý thuyết mà còn đối với toán học ứng dụng. Trong toán học tính toán nó là một phần cấu thành số điều kiện của ma trận. Đây là đại lượng quyết định tính ổn định hay không ổn định của thuật toán. Nếu ta tìm được cận dưới cho giá trị kỳ dị nhỏ nhất của ma trận thì ta đã tìm được một cận trên cho số điều kiện của ma trận. Đó là đại lượng không thể thiếu trong các đánh giá sai số. Thật vậy, hãy xét hệ phương trình tuyến tính n ẩn số, Ax = b. (1) Xin lưu ý rằng đây hầu như vẫn là bài toán quan trọng bậc nhất trong toán học tính toán vì để ra được kết quả cuối cùng, gần như mọi bài toán đều quy về hoặc liên quan đến giải hệ phương trình tuyến tính. Vế phải và ma trận hệ số của (1) thường thu được do quá trình đo đạc ngoài thực địa hoặc là kết quả của một quá trình tính toán xấp xỉ trước đó. Dù bằng cách nào, A và b không thể tránh khỏi những sai số mà ta lần lượt ký hiệu là ∆A, δ b. Như vậy đáng ra, ta có hệ (1) nhưng thực tế, ta lại có hệ (A + ∆A)x̃ = b + δ b. (2) Điều chúng ta quan tâm ở đây là x̃ cách x bao xa hay là độ lớn của sai số. Người 1 ta đã chỉ ra rằng nếu k∆Ak < −1 và b 6= 0 thì kA k k∆Ak kδ bk
kx − x̃k cond (A) ≤ + , (3) kxk kbk 1 − kA−1 k k∆Ak kAk trong đó, cond(A) = kAk A−1 là số điều kiện của ma trận A. Bất đẳng thức (3) chỉ ra rằng, sai số tương đối của nghiệm bị chặn trên bởi một đại lượng phụ thuộc vào sai số tương đối của dữ liệu (tất nhiên!) và vào bản thân ma trận hệ số. Ta cũng sẽ thấy rằng, cond (A) = kAk A−1 = σ1 (A) 1 1 , σn (A) trong đó, σ1 (A) và σn (A) lần lượt là giá trị kỳ dị lớn nhất và nhỏ nhất của ma trận A. Nếu ta tìm được cận dưới dương α ≤ σn (A) thì ta có cond(A) = σ1 (A) σ1 (A) ≤ . σn (A) α (4) Thay (4) vào (3), ta thu được một cận trên mới cho sai số tương đối. Ngoài ra, tìm cận dưới cho giá trị kỳ dị nhỏ nhất của ma trận phụ thuộc tham số cũng đóng vai trò quan trọng trong phương pháp giảm cơ sở. Xin xem [3] và [5] để biết thêm chi tiết. Chính vì tầm quan trọng của vấn đề, chúng tôi quyết định chọn đó làm đề tài luận văn thạc sĩ. Để làm rõ chủ đề này, luận văn của chúng tôi bao gồm những phần sau. Chương 1. Chúng tôi trình bày một số kiến thức chung về ma trận như khái niệm về ma trận, ma trận đơn vị, ma trận trực giao, véc tơ riêng, giá trị riêng, chuẩn của véc tơ và chuẩn của ma trận, đặc biệt là dạng khai triển giá trị kỳ dị SVD của ma trận. Đó đều là những kiến thức cơ bản, làm cơ sở nghiên cứu chương sau. Chương 2. Chúng tôi trình bày về một số cận dưới cho giá trị kỳ dị nhỏ nhất của ma trận hằng. Trước tiên, chúng tôi sẽ trình bày một vài kết quả liên quan đến cận dưới cho chuẩn của ma trận nghịch đảo. Sau đó, dựa vào mối quan hệ của chuẩn của ma trận nghịch đảo và giá trị kỳ dị nhỏ nhất của ma trận ta thu được cận dưới cho giá trị kỳ dị của hai lớp ma trận đặc biệt: ma trận đường chéo trội và H−ma trận. Cuối cùng, chúng tôi đưa hai ví dụ để minh họa cho các cận tìm được. Chương 3. Chúng tôi sẽ trình bày một kết quả về cận dưới cho giá trị kỳ dị nhỏ nhất của ma trận phụ thuộc tham số cùng với nó là một ví dụ minh họa. Trong các ví dụ ở cả 2 chương, chúng tôi đều sử dụng MATLAB như một phần mềm để tính toán và minh họa kết quả. Luận văn này được hoàn thành tại trường Đại học Khoa học - Đại học Thái Nguyên. Trước khi trình bày nội dung chính của luận văn, tôi xin gửi lời cảm ơn chân thành, sâu sắc tới TS. Nguyễn Thanh Sơn. Thầy là người trực tiếp hướng dẫn, tận tình chỉ bảo, giúp đỡ và động viên tôi trong suốt quá trình nghiên cứu và 2 hoàn thành luận văn. Tôi cũng xin chân thành cảm ơn ban lãnh đạo phòng Sau Đại học, quý thầy cô trong khoa Toán - Tin, các bạn học viên lớp cao học Toán 8a đã tạo điều kiện thuận lợi, giúp đỡ, động viên tôi trong suốt quá trình học tập và nghiên cứu tại trường. Qua đây, tôi xin bày tỏ lòng biết ơn sâu sắc tới người thân trong gia đình, bạn bè đã luôn động viên khích lệ tôi trong suốt quá trình hoàn thành khóa học. Thái Nguyên, ngày 7 tháng 7 năm 2016 Tác giả Bùi Thị Tuyến 3 Chương 1 Kiến thức chung về ma trận Để phục vụ cho Chương 2, ta sẽ nhắc lại một số kiến thức cơ bản giúp cho việc trình bày nội dung của Chương 2 được rõ ràng. Trước hết, ta nhắc lại các khái niệm về ma trận. Chương này được viết chủ yếu dựa vào tài liệu [1, 2, 4]. 1.1 Ma trận 1.1.1 Định nghĩa ma trận Định nghĩa 1.1. Ma trận một bảng gồm m × n số thực được sắp xếp thành m dòng, n cột và gọi là ma trận cấp m × n. Ký hiệu ma trận là,   a11 a12 · · · a1n  a  21 a22 · · · a2n  A =  .. .. . . .  . ..   . . am1 am2 · · · amn hoặc A = (ai j )m×n . Trong đó, ai j là phần tử của ma trận nằm trên dòng i, cột j, i = 1, 2, · · · , m, j = 1, 2, · · · , n. Các phần tử aii gọi là phần tử nằm trên đường chéo chính. Nếu m = n thì A được gọi là một ma trận vuông. Định nghĩa 1.2. Ma trận đơn vị là ma trận vuông có mọi phần tử nằm trên đường chéo chính bằng 1, các phần tử khác bằng 0 và có dạng sau   1 0 ··· 0 0 1 · · · 0   I =  .. .. . . ..  . . . . 0 0 ··· 1 4 Định nghĩa 1.3. Ma trận đường chéo là ma trận vuông có các phần tử nằm ngoài đường chéo chính bằng 0. Ta đặc biệt quan tâm đến lớp ma trận đường chéo vuông. Ma trận đường chéo có dạng,  a11 0 0 a 22  D =  .. ..  . . 0 0  ··· 0 ··· 0   . . . ..  .  · · · ann Định nghĩa 1.4. Ma trận chuyển vị là một ma trận ở đó các hàng được thay thế bằng các cột và ngược lại. Ma trận chuyển vị của ma trận A được kí hiệu là AT .   a11 a21 · · · am1 a   12 a22 · · · am2  T A =  .. .. . . .  . ..   . . a1n a2n · · · amn Nếu A là một ma trận có kích thước m × n với các giá trị ai j tại hàng i, cột j thì ma trận chuyển vị B = AT là ma trận có kích thước n × m với các giá trị bi j = a ji . Định nghĩa 1.5. Ma trận A được gọi là ma trận đối xứng nếu AT = A. Ma trận đối xứng A được gọi là xác định dương (nửa xác định dương) nếu xT Ax > 0, ∀x 6= 0 (xT Ax ≥ 0). 1.1.2 Ma trận trực giao Định nghĩa 1.6. Ma trận vuông A được gọi là ma trận trực giao nếu, AT A = I, hay dưới dạng biểu thức, ( n ∑ aik a jk = σi j = k=1 1, i = j 0, i 6= j trong đó, σi j là kí hiệu Kronecker. Tính chất 1.7. • Ma trận trực giao A là khả nghịch và có A−1 = AT . 5 • Ma trận A trực giao khi và chỉ khi các vec tơ cột và các hàng của A tạo thành các hệ trực chuẩn. • Ta có |AT A| = |I| = 1 → |A| = ±1. 1.2 Véc tơ riêng, giá trị riêng Định nghĩa 1.8. Cho A là ma trận vuông cấp n,   a11 a12 · · · a1n a   21 a22 · · · a2n  A =  .. .. . . .  . ..   . . an1 an2 · · · ann Khi đó, nếu có véc tơ x khác không và số λ sao cho Ax = λ x thì ta nói λ là một giá trị riêng của A và x là một véc tơ riêng của A tương ứng với giá trị riêng λ . Như đã biết, giá trị riêng và véc tơ riêng của ma trận thực có thể là phức. Tuy nhiên, nếu A là ma trận đối xứng thì các giá trị riêng và kéo theo là các véc tơ riêng luôn là thực. Ta nhắc lại ở đây một kết quả quan trọng của đại số tuyến tính. Đó chính là Định lý Courant-Fischer. Để tiện cho việc hiểu và vận dụng, chúng tôi trích một phần của định lý. Phát biểu đầy đủ và chứng minh của định lý có thể tìm thấy trong [4]. Định lý 1.9. (Định lý 4.2.6, [4]) Giả sử A là ma trận thực đối xứng cấp n. Gọi λn (A) là giá trị riêng nhỏ nhất theo nghĩa đại số của nó. Khi đó, xT Ax λn (A) = min T . x6=0 x x Từ định lý này, ta suy ra ngay một hệ quả sau. Hệ quả 1.10. Nếu A là một ma trận đối xứng xác định dương (nửa xác định dương) thì các giá trị riêng của nó đều dương (không âm). 6 1.3 Chuẩn của véc tơ và chuẩn của ma trận Định nghĩa 1.11. Cho véc tơ x, chuẩn của x kí hiệu là kxk được xác định là một số không âm thỏa mãn các tính chất sau, 1. kxk ≥ 0 và kxk = 0 khi và chỉ khi x = 0. 2. kαxk = |α| kxk với mọi α ∈ R. 3. kx + yk ≤ kxk + kyk . Kí hiệu véc tơ xT = (x1 , x2 , · · · , xn )T . Trong thực tế người ta hay sử dụng một số dạng chuẩn sau. Chuẩn - p Cho p > 0 là số thực, chuẩn - p được định nghĩa là, n 1 kxk p = ( ∑ |xi | p ) p . i=1 Với p = 1, 2, ∞ ta được các dạng chuẩn Manhattan, Euclide và chuẩn cực đại tương ứng theo thứ tự đó. Với 0 < p < 1, hàm khoảng cách này không thỏa mãn bất đẳng thức tam giác nên nó không phải là một chuẩn. Chuẩn Manhattan Trong công thức chuẩn - p, cho p = 1 ta được, n kxk1 = ∑ |xi | . i=1 Chuẩn này còn được gọi là chuẩn Taxicab, chuẩn Manhattan hoặc đơn giản là chuẩn L1 . Khoảng cách tương ứng thường được gọi là khoảng cách Manhattan, khoảng cách L1 . Chuẩn Euclide Trong công thức chuẩn - p, cho p = 2 ta được, q n √ 2 1/2 kxk2 = ( ∑ |xi | ) = x12 + x22 + · · · + xn2 = xT x. i=1 7 Chuẩn Euclide còn gọi là chuẩn L2 . Chuẩn vô cực Trong công thức chuẩn - p, cho p → +∞ ta được chuẩn cực đại, kxk∞ = max(|x1 | , |x2 | , · · · , |xn |). Bổ đề 1.12. Cho k.kα và k.kβ là hai chuẩn của Rn . Khi đó, với mỗi x ta luôn có c1 kxkα ≤ kxkβ ≤ c2 kxkα với c1 , c2 là hằng số. Chúng ta cũng nói rằng chuẩn k.kα và k.kβ là tương đương. Bổ đề 1.13. (Mối quan hệ giữa các loại chuẩn) Từ định nghĩa về các loại chuẩn 1, 2, ∞ ở trên ta có mối quan hệ giữa các loại chuẩn như sau, √ n kxk2 , √ kxk∞ ≤ kxk2 ≤ n kxk∞ , kxk2 ≤ kxk1 ≤ kxk∞ ≤ kxk1 ≤ n kxk∞ . Ngoài các chuẩn về véc tơ, chúng tôi cũng sẽ cần chuẩn của ma trận để đánh giá sai số trên các ma trận. Định nghĩa 1.14. Cho ma trận A ∈ Rm×n , chuẩn của A kí hiệu kAk là một số không âm thỏa mãn, 1. kAk ≥ 0 và kAk = 0 khi và chỉ khi A = 0. 2. kαAk = |α| kAk với mọi α ∈ R. 3. kA + Bk ≤ kAk + kBk . Không giống như chuẩn của véc tơ, các dạng chuẩn của ma trận đều được phái sinh từ một chuẩn duy nhất là chuẩn - p. Khi đó, ta có các dạng chuẩn của ma trận như sau. Ta xét chuẩn toán tử của ma trận A, kAk p = max x6=0 kAxk p kxk p 8 , x ∈ Rn . Trường hợp đặc biệt, với p = 1 thì chuẩn toán tử trở thành chuẩn cực đại theo cột, m   kAk1 = max ( ∑ ai j ). 1≤ j≤n i=1 Với p = ∞ thì chuẩn toán tử trở thành chuẩn cực đại theo dòng, n   kAk∞ = max ( ∑ ai j ). 1≤i≤m j=1 Với p = 2 và m = n, ta được dạng chuẩn Euclide của ma trận được tính bằng giá trị lớn nhất trong các giá trị kỳ dị của A. kAk2 = max kAxk2 = max kxk2 =1 kxk2 =1 √ xT AT Ax. Áp dụng một cách trực tiếp chuẩn -p của véc tơ đối với từng phần tử của ma trận, ta được loại chuẩn tương đối trực quan này. n m kAk p = ( ∑ ∑ |ai j | p )1/p . i=1 j=1 Với p = 2 thì chuẩn trên được gọi là chuẩn Frobenius. Lưu ý rằng kí hiệu kAk p trong trường hợp này hoàn toàn khác với chuẩn toán tử ở bên trên. Bổ đề tiếp theo nhằm tóm lược các tính chất cốt yếu của chuẩn của véc tơ và chuẩn của ma trận cái mà đã được giới thiệu trước đó. Chúng ta sẽ sử dụng các tính chất này nhiều hơn trong các phần tiếp theo. Bổ đề 1.15. 1. kQAZk = kAk nếu Q và Z là các ma trận trực giao hoặc đồng nhất cho chuẩn Frobenius và cho chuẩn toán tử k.k2 . kAk∞ = max ∑ |ai j | = giá trị lớn nhất trong tổng các giá trị i x6=0 kxk∞ j tuyệt đối của phần tử theo hàng. 2. kAk∞ ≡ max kAk1 = AT ∞ = max ∑ |ai j | = giá trị lớn nhất trong tổng các j i x6=0 kxk1 giá trị tuyệt đối của phần tử theo cột. 3. kAk1 ≡ max kAk2 p = λmax (AT A), trong đó λmax là giá trị riêng lớn nhất. x6=0 kxk2 T 5. kAk2 = A 2 . 4. kAk2 ≡ max 9 6. Nếu A là (n × n) - ma trận, thì n−1/2 kAk2 ≤ kAk1 ≤ n1/2 kAk2 . 7. Nếu A là (n × n) - ma trận, thì n−1/2 kAk2 ≤ kAk∞ ≤ n1/2 kAk2 . 8. Nếu A là (n × n) - ma trận, thì n−1 kAk∞ ≤ kAk1 ≤ n kAk∞ . 9. Nếu A là (n × n) - ma trận, thì kAk1 ≤ kAkF ≤ n1/2 kAk2 . 1.4 Khai triển SVD (singular value decomposition) của ma trận Định lý 1.16. Cho A là một (m × n) - ma trận tùy ý với m ≥ n. Khi đó, ta có thể viết A = UΣV T , trong đó U là (m × n) - ma trận và U T U = I,V là (n × n) - ma trận, V T V = I, và Σ = diag(σ1 , · · · , σn ), trong đó σ1 ≥ · · · ≥ σn ≥ 0. Các cột u1 , · · · , un của U được gọi là các véc tơ kỳ dị trái. Các hàng v1 , · · · , vn của V được gọi là các véc tơ kỳ dị phải. Giá trị σi (i = 1, 2, · · · , n) được gọi là giá trị kỳ dị. (Nếu m < n, ta áp dụng định lý cho AT ). Chứng minh. Giả sử rằng SVD tạo bởi (m − 1) × (n − 1) - ma trận và đặt nó là (m × n) - ma trận. Ta giả sử A 6= 0, ta cần chỉ ra Σ = 0 và đặt U và V là các ma trận trực giao tùy ý. A , Σ = kAk2 và V = 1. kAk2 Bước tiếp theo, chọn v sao cho kvk2 = 1 và kAk2 = kAvk2 > 0. Tức là véc tơ v Av tạo nên bởi định nghĩa kAk2 = max kAvk2 . Đặt u = , là một véc tơ đơn kAvk2 kvk2 =1 vị. Chọn Ũ và Ṽ sao cho U = [u, Ũ] là một (m × m) - ma trận bất kỳ, và V = [v, Ṽ ] Khi n = 1 (khi m ≥ n), ta viết A = UΣV T với U = là một (n × n) - ma trận bất kỳ. Ta có,  T  T  T AṼ   u u Av u U T AV = A v Ṽ = . Ũ T Ũ T Av Ũ T AṼ Khi đó, (Av)T (Av) kAvk22 u Av = = = kAvk2 = kAk2 ≡ σ , kAvk2 kAvk2 T và Ũ T Av = Ũ T u kAvk2 = 0. Ta cũng có uT AṼ = 0 vì σ = kAk2 = U T AV 2 ≥ [1, 0, · · · , 0]U T AV = [σ |uT AṼ |] > σ .  2   2 σ 0 σ 0 Vì vậy, U T AV = = . T 0 Ũ AṼ 0 à 10 Bây giờ, chúng ta có thể áp dụng công thức để thay à bởi à = U1 Σ1V1T , trong đó U1 là (m − 1) × (n − 1) - ma trận, Σ1 là (n − 1) × (n − 1) - ma trận, và V1 là (n − 1) × (n − 1) - ma trận. Vì vậy,      T σ 0 1 0 σ 0 1 0 T U AV = = 0 U1 Σ1V1T 0 U1 0 Σ1 0 V1 hoặc       1 0 σ 0 1 0 T A = (U ) (V ) . 0 U1 0 Σ1 0 V1 Đó là điều chúng ta phải chứng minh. Ví dụ 1.17. Tìm khai triển SVD của ma trận,   1 1 0 A= . 0 0 1 Trước tiên, ta tìm các giá trị riêng của ma trận AT A. Ta có,      1 0  1 1 0 1 1 0 AT A = 1 0 = 1 1 0 . 0 0 1 0 1 0 0 1 Giải phương trình det(A − λ I) = 0, ta được các giá trị riêng của ma trận AT A là λ1 = 2, λ2 = 1, λ3 = 0. Với mỗi giá trị riêng λi , giải phương trình (A − λi I)x = 0, ta được các véc tơ riêng tương ứng là,    1 1   − √2   √2  0     1  , v2 = 0 , v3 =  1  . v1 =   √  √   2   2 1 0 0  Ta được ma trận,   1 1  √2 √2 0   . VT =  0 0 1    1  1 −√ √ 0 2 2 √ Các giá trị kì dị của ma trận A là σ1 = 2, σ2 = 1, σ3 = 0. Từ đó ta được ma trận,  √ 2 0 0 . Σ= 0 1 0 11 Tiếp theo ta đi tìm ma trận U. Ta có,  1    √2     1 1 1 1 0   1 = 1 , ui = Av ⇒ u1 = √ √  0 σi 2 0 0 1   2 0      0   1 1 1 0   0 u2 = . 0 = 1 1 0 0 1 1   1 0 ⇒U = . 0 1 ⇒ Phân tích SVD của ma trận A là,  1 1   √2 √2 0     √  1 1 0 1 0 2 0 0  .  0 A= = UΣV T = 0 1  0 0 1 0 1 0 1 0    1 1 −√ √ 0 2 2  Định lý 1.18. Đặt A = UΣV T là một SVD của (m × n) - ma trận A, trong đó m ≥ n. 1. Giả sử A là ma trận đối xứng với giá trị riêng λi và véc tơ riêng ui trực chuẩn. Trong trường hợp này A = UΛU T là một dạng khai triển của A, với Λ = diag(λ1 , · · · , λn ),U = [u1 , · · · , un ], và UU T = I. Khi đó, một SVD của A là A = UΣV T , trong đó σi = |λi | và vi = sign(λi )ui , trong đó sign(0) = 1. 2. Giá trị riêng của ma trận đối xứng AT A là σi2 . Véc tơ kỳ dị phải vi là véc tơ riêng tương ứng của A. −1 3. kAk2 = σ1 . Nếu A là ma trận vuông và không suy biến, thì A−1 2 = σn σ1 và cond(A) = kAk2 . A−1 2 = . σn Chứng minh. 1. Luôn đúng theo định nghĩa của SVD ma trận. 2. AT A = V ∑ U T U ∑ V T = V ∑2 V T . Đây là một dạng khai triển của AT A, với các cột của V là các véc tơ riêng và các khối chéo của ∑2 là các giá trị riêng. 12 3. Đây là trường hợp đúng để chỉ ra 2−chuẩn của một ma trận đường chéo là tổng tuyệt đối lớn nhất trên đường chéo của nó. Khi đó, từ 4 của Bổ đề 1.15 , kAk = U T AV = k∑k = σ1 và A−1 = V T A−1U = ∑−1 = 2 2 2 2 2 2 σn−1 . Nhận xét 1.19. Nếu A là ma trận đối xứng, nửa xác định dương thì các giá trị riêng của A là không âm và theo mục 1 của Định lí 1.18 thì các giá trị riêng chính là các giá trị kỳ dị của nó. 13 Chương 2 Một số cận dưới cho giá trị kỳ dị nhỏ nhất của ma trận hằng 2.1 Cận dưới cho giá trị kỳ dị nhỏ nhất của ma trận đường chéo trội Trong mục này, trước hết chúng tôi sẽ trình bày một vài kết quả liên quan đến cận dưới cho chuẩn của ma trận nghịch đảo. Dựa vào mối liên hệ của đại lượng này với giá trị kỳ dị nhỏ nhất, ta thu được cận dưới cho giá trị kỳ dị nhỏ nhất. Kết quả này sau đó được mở rộng lên ma trận chéo trội khối. Một số ví dụ cũng được trình bày nhằm minh họa cho lý thuyết. Phần lý thuyết của mục này được viết dựa theo [6]. Định nghĩa 2.1. Cho A ∈ Rn×n , A được gọi là chéo trội hàng nếu |aii | > ∑ |ai j |, 1 ≤ i ≤ n. j6=i Ma trận A được gọi là chéo trội cột nếu AT là chéo trội hàng. Mệnh đề 2.2. Giả sử A ∈ Rn×n là chéo trội hàng và đặt   α = min(|aii | − ∑ ai j ). i j6=i Khi đó, A khả nghịch và −1 A ≤ 1 . ∞ α (2.1) Chứng minh. Trước tiên, ta chỉ ra A khả nghịch bằng phản chứng. Thật vậy, nếu A không khả nghịch tồn tại u ∈ Rn sao cho Au = 0. Giả sử ui là thành phần có giá 14 trị tuyệt đối lớn nhất. Ta luôn có thể giả sử ui > 0 (vì nếu không, ta thay u bằng −u). Khi đó, xét hàng i của tích Au, ta có n ∑ ai j u j = 0, j=1 aii ui = − ∑ ai j u j , j6=i uj ai j . u i j6=i aii = − ∑ Lấy trị tuyệt đối hai vế |aii | ≤ ∑ | j6=i uj ai j | ≤ ∑ ai j . ui j6=i Điều này mâu thuẫn với giả thiết chéo trội hàng. Tiếp theo ta chứng minh bất đẳng thức (2.1). Theo định nghĩa, −1 A x −1 kyk∞ ∞ A = sup = sup , ∞ x6=0 kxk∞ y6=0 kAyk∞ hay −1 −1 A = ∞ kAyk∞ 1 . = infy6=0 kyk∞ kyk∞ sup y6=0 kAyk∞ (2.2) Từ (2.2), để chứng minh (2.1) ta chỉ cần chỉ ra với mọi y, α kyk∞ ≤ kAyk∞ . Lấy vectơ y bất kỳ, giả sử kyk∞ = |yk |. Khi đó, 0 < α ≤ |akk | − ∑ |ak j |. j6=k Nhân cả hai vế với |yk |, 0 < α|yk | ≤ |akk yk | − ∑ |ak j ||yk | j6=k ≤ |akk yk | − ∑ |ak j ||y j | j6=k ≤ |akk yk | − | ∑ ak j y j | j6=k ≤ | ∑ ak j y j | ≤ max | ∑ |ak j x j | = kAxk∞ . k j 15 j Kết quả trên được phát biểu cho ma trận chéo cột như sau. Hệ quả 2.3. Giả sử A là ma trận chéo trội cột và β = min(|akk | − ∑ |a jk |). k j6=k Khi đó, −1 A ≤ 1 . 1 β Mệnh đề 2.4. Với A là ma trận bất kỳ, ta luôn có kAk22 ≤ kAk1 kAk∞ . Chứng minh. Chứng minh này được tham khảo từ tài liệu [2]. Trước tiên, ta chỉ ra khẳng định sau là đúng: cho A ∈ Rm×n bất kỳ. Khi đó, tồn tại z ∈ Rn , kzk2 = 1 sao cho, AT Az = kAk22 z. (2.3) Thật vậy, theo định nghĩa chuẩn, tồn tại z ∈ Rn , kzk2 = 1 sao cho, kAzk2 = kAk2 . (2.4) Đặt f (x) = 1 kAxk22 1 xT AT Ax . = 2 kxk22 2 xT x Dễ thấy khi đó z là một điểm cực đại của hàm f (x). Từ định lý về điều kiện cần, ta suy ra ∇ f (z) = 0. (2.5) Bằng tính toán cụ thể, ta thu được n ∂ f (z) = ∂ zi zT z ∑ ((AT A)i j z j − (zT AT Az)z j ) j=1 (zT z)2 . (2.6) Điều kiện (2.5) cho (2.6) được viết gọn lại dưới dạng ma trận, AT Az = (zT AT Az)z. Đẳng thức (2.3) được suy ra từ (2.4) và (2.7). 16 (2.7)