Tài liệu Về một số thuật toán tính giá trị riêng của ma trận cỡ lớn

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ VĂN TẦN VỀ MỘT SỐ THUẬT TOÁN TÍNH GIÁ TRỊ RIÊNG CỦA MA TRẬN CỠ LỚN LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ VĂN TẦN VỀ MỘT SỐ THUẬT TOÁN TÍNH GIÁ TRỊ RIÊNG CỦA MA TRẬN CỠ LỚN Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. NGUYỄN THANH SƠN Thái Nguyên - 2015 i Mục lục Lời cảm ơn iii Mở đầu 1 1 Kiến thức chuẩn bị 3 1.1 Nhắc lại sơ lược kiến thức trong đại số tuyến tính . . . . . . . . . . 3 1.1.1 Tầm quan trọng của giá trị riêng . . . . . . . . . . . . . . . 3 1.1.2 Một số khái niêm và ký hiệu . . . . . . . . . . . . . . . . . 6 1.1.3 Bài toán giá trị riêng . . . . . . . . . . . . . . . . . . . . . 8 Không gian con Krylov . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2 2 Một số phương pháp tìm giá trị riêng 15 2.1 Phương pháp luỹ thừa . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.1.1 Lặp đơn vectơ . . . . . . . . . . . . . . . . . . . . . . . . 15 2.1.2 Trường hợp đối xứng . . . . . . . . . . . . . . . . . . . . . 17 2.1.3 Lặp nghịch đảo vectơ . . . . . . . . . . . . . . . . . . . . . 18 2.1.4 Tính giá trị riêng bậc cao . . . . . . . . . . . . . . . . . . . 20 Phương pháp Arnoldi . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.1 Cơ sở trực giao cho không gian Krylov . . . . . . . . . . . 21 2.2.2 Phương pháp Arnoldi tính giá trị riêng . . . . . . . . . . . . 23 Phương pháp Lanczos . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2 2.3 3 Ví dụ số 3.1 27 Một vài giải thích cho phương pháp Arnoldi và phương pháp Lanczos 27 ii 3.2 3.1.1 Thuật toán QR . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1.2 Thuật toán Chia để Trị của Cuppen . . . . . . . . . . . . . 29 Ví dụ số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.2.1 Phương pháp Arnoldi . . . . . . . . . . . . . . . . . . . . . 34 3.2.2 Phương pháp Lanczos . . . . . . . . . . . . . . . . . . . . 36 3.2.3 Nhận xét . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Kết luận 38 Tài liệu tham khảo 39 iii Lời cảm ơn Tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc đến TS. Nguyễn Thanh Sơn, người thầy đã tận tình chỉ bảo, hướng dẫn tôi trong suốt thời gian làm luận văn. Tôi xin chân thành cảm ơn sự giúp đỡ quý báu của các thầy, cô giáo đã tham gia giảng dạy lớp cao học khóa 7 của Khoa Toán - Tin trường Đại học Khoa học - Đại học Thái Nguyên, đã truyền thụ và mang đến cho tôi những kiến thức bổ ích trong khoa học và cuộc sống. Tôi xin cảm ơn sự động viên, giúp đỡ, tạo điều kiện của gia đình, bạn bè, đồng nghiệp, Ban chuyên môn, Ban giám hiệu trường THPT Nguyễn Trung Ngạn - Ân Thi, Hưng Yên đã dành cho tôi trong quá trình nghiên cứu và hoàn thành luận văn. Thái Nguyên, tháng 11 năm 2015 Vũ Văn Tần Học viên Cao học Toán K7Y, Trường ĐH Khoa học - ĐH Thái Nguyên 1 Mở đầu Giá trị riêng đóng một phần quan trọng trong các ứng dụng của đại số tuyến tính, là bài toán điển hình trong nhiều lĩnh vực lý thuyết và ứng dụng thực tế. Những phương pháp giải trực tiếp cho kết quả chính xác nhưng chỉ làm được với những bài toán cỡ nhỏ, không đáp ứng được các ứng dụng trong thực tế. Với bài toán có kích thước lớn phương pháp này là không khả thi và các giá trị riêng phải được tính bằng các phương tiện khác. May mắn thay là có tồn tại một số kỹ thuật khác để tìm ra giá trị riêng và vectơ riêng của ma trận. Những phương pháp này, là những phương pháp lặp, làm việc bằng cách liên tục cải tiến xấp xỉ các giá trị riêng, và có thể được chấm dứt bất cứ khi nào những xấp xỉ đạt được một mức độ phù hợp chính xác. Các phương pháp lặp cho kết quả gần đúng nhưng đáp ứng được nhiều ứng dụng trong thực tế, đặc biệt là các ma trận cỡ lớn. Nó hình thành cơ sở của nhiều đại tính toán giá trị riêng ngày nay. Luận văn này chúng tôi đã tìm hiểu và trình bày "Về một số thuật toán tính giá trị riêng của ma trận cỡ lớn". Ngoài phần mở đầu và kết luận, luận văn này gồm ba chương. Chương 1: Kiến thức chuẩn bị. Chương này nhắc lại sơ lược các kiến thức trong đại số tuyến tính như một số khái niệm và ký hiệu, bài toán giá trị riêng và không gian con Krylov. Chương 2: Một số phương pháp tìm giá trị riêng. Nội dung của chương này nhằm trình bày phương pháp lũy thừa, phương pháp Arnoldi và phương pháp Lanczos. Chương 3: Ví dụ số. Chương này trình bày một vài giải thích cho phương pháp Arnoldi và phương pháp Lanczos là thuật toán QR cơ bản, thuật toán chia để trị của 2 Cuppen, cuối cùng là một số ví dụ số. Kết quả làm việc chính của chúng tôi là chạy những thuật toán đã biết trên MATLAB với những ma trận lớn đươc lấy từ thực tiễn. Dù đã nghiêm túc nghiên cứu và rất cố gắng thực hiện luận văn, nhưng với thời gian hạn chế cùng nhiều lý do khác, luận văn chắc chắn không tránh khỏi những thiếu sót. Chúng tôi mong nhận được những ý kiến đánh giá, phê bình để luận văn này hoàn chỉnh và nhiều ý nghĩa hơn. Thái Nguyên, ngày 01 tháng 11 năm 2015 Vũ Văn Tần Học viên Cao học Toán lớp Y, khóa 01/2014 - 01/2016 Chuyên ngành Toán ứng dụng Trường Đại học Khoa học - Đại học Thái Nguyên Email: [email protected] 3 Chương 1 Kiến thức chuẩn bị Chương 1 được viết dựa trên tài liệu tham khảo [1], [3], [4]. 1.1 1.1.1 Nhắc lại sơ lược kiến thức trong đại số tuyến tính Tầm quan trọng của giá trị riêng Trong vật lý, giá trị riêng thường gắn với các dao động. Các đối tượng như dây đàn, trống, cầu,... dao động ở tần số nhất định. Và trong một số tình huống chúng dao động rất nhiều đến mức bị phá hủy. Ngày 07 tháng 11 năm 1940, cây cầu Tacoma Narrows, Washington, Hoa Kỳ bị sập sau khi khai trương gần nửa năm. Gió mạnh kích thích cây cầu quá nhiều khiến cây cầu bị sụp đổ. Một vài năm trước đây cây cầu đi bộ Thiên niên kỷ ở London bắt đầu lắc lư và bị đóng cửa. Đây là những ví dụ nổi bật của cấu trúc dao động. Nhưng giá trị riêng xuất hiện ở nhiều nơi khác. Điện trường tại cyclotrones, một hình thức đặc biệt của máy gia tốc hạt có dao động một cách chính xác để đẩy nhanh tiến độ các hạt tích điện quay tròn quanh tâm của nó. Các giải pháp của phương trình Schrodinger từ vật lý lượng tử và hóa học lượng tử có những giải pháp tương ứng với dao động của các mô hình phân tử. Các giá trị riêng tương ứng với mức năng lượng mà phân tử có thể chiếm. Nhiều giá trị đặc trưng trong khoa học là giá trị riêng. Xét dao động dây là sự dịch chuyển của các vị trí tại x, 0 < x < L, và thời gian t được ký hiệu là u(x, t). Chúng ta có phương trình vi phân có dạng   ∂ 2u ∂ ∂u − ρ(x) 2 + p(x) + q(x)u(x, t) = 0, ∂t ∂x ∂x (1.1) 4 với u(0, t) = u(1, t) = 0. Ở đây ρ(x) đóng vai trò của mật độ khối lượng, p(x) là modul đàn hồi khác nhau tại địa phương. Từ vật lý chúng tôi biết rằng ρ(x) > 0 và p(x) > 0 với mọi x. Để đơn giản chúng tôi giả sử rằng ρ(x) = 1. Để tìm u trong (1.1) chúng tôi phân tích (1.2) u(x, t) = v(t)w(x), trong đó v là một hàm mà chỉ phụ thuộc vào thời gian t, trong khi w chỉ phụ thuộc vào biến không gian x. Với phân tích này (1.1) trở thành v”(t)w(x) − v(t)(p(x)w0 (x))0 − q(x)v(t)w(x) = 0. (1.3) Bây giờ chúng tôi rút các biến phụ thuộc vào t theo biến phụ thuộc vào x 1 v 00 (t) = (p(x)w0 (x))0 + q(x). v(t) w(x) Chúng tôi có thể thay đổi t và x độc lập với nhau mà không cần thay đổi giá trị trên mỗi vế của phương trình. Do đó, mỗi vế của phương trình phải bằng một giá trị không đổi, chúng tôi biểu thị giá trị này bằng λ. Như vậy, từ vế trái chúng tôi có được phương trình −v 00 (t) = λv(t). √ √ Phương trình này có nghiệm v(t) = a. cos( λt) + b. sin( λt) với giả sử λ > 0. Vế bên phải của (1.3) cho ta bài toán − (p(x)w0 (x))0 + q(x)w(x) = λw(x), w(0) = w(1) = 0. (1.4) Một giá trị λ thuộc (1.4) có một nghiệm không tầm thường (tức là khác không) được gọi là một giá trị riêng, w là một hàm riêng tương ứng. Tất cả các giá trị riêng của (1.4) là dương. Bằng phân tích (1.2) chúng tôi nhận được √ √ u(x, t) = w(x)[a. cos( λt) + b. sin( λt)] là một nghiệm của (1.1). Ta thấy (1.4) có vô số các giá trị riêng thực dương 0 < λ1 < λ2 < ... < λk , (λk → ∞ khi k → ∞), mỗi nghiệm khác không w(x) của (1.4) chỉ 5 cho ta những giá trị đặc biệt λk . Vì vậy, nghiệm chung của (1.1) có dạng u(x, t) = ∞ X p p wk (x)[ak . cos( λk t) + bk . sin( λk t)]. k=0 Các hệ số ak và bk được xác định bởi các điều kiện ban đầu và kết thúc. Chúng tôi giả sử u(x, 0) = ∞ X ak wk (x) = u0 (x), k=0 ∂u (x, 0) = ∂t ∞ p X λk bk wk (x) = u1 (x). k=0 Ở đây u0 và u1 là các hàm đã cho. Các wk tạo thành một cơ sở trực giao trong không gian của các hàm khả tích vuông L2 (0, 1). Vì vậy không khó khăn để tính toán các hệ số ak và bk . Ta thấy rằng bài toán khó là giải quyết bài toán giá trị riêng (1.4). Phương trình (1.4) có thể được giải quyết chỉ trong phân tích tình huống rất đặc biệt, chẳng hạn nếu tất cả các hệ số là hằng số. Nói chung phương pháp số là cần thiết để giải quyết vấn đề của bài toán (1.4). Để giải quyết bài toán (1.4) chúng tôi xấp xỉ w(x) bởi giá trị của nó tại các điểm rời rạc xi = ih, h = 1/(n + 1), i = 1, ..., n.. Tại thời điểm xi chúng tôi xấp xỉ các đạo hàm bởi các điểm khác biệt hữu hạn. Đầu tiên chúng tôi viết g(xi+ 1 ) − g(xi− 1 ) d 2 2 g(xi ) ≈ . dx h Cho g = p dw chúng tôi nhận được dx g(xi+ 1 ) = p(xi+ 1 ) 2 2 w(xi+1 ) − w(xi ) h và cuối cùng, cho i = 1, . . . , n,     dw 1 w(xi+1 ) − w(xi ) w(xi ) − w(xi−1 ) d − p (xi ) ≈ − p(xi+ 1 ) − p(xi− 1 ) 2 2 dx dx h h h 1 = 2 [p(xi− 1 )wi−1 + (p(xi− 1 ) + p(xi+ 1 ))wi + p(xi+ 1 )wi+1 ]. 2 2 2 2 h Lưu ý rằng ở các điểm cuối khoảng w0 = wn+1 = 0. Chúng tôi thu thập tất cả các phương trình trong một phương trình ma trận 6  p(x 1 ) + p(x 3 ) 2 2 h2           −  p(x 3 ) + q(x1 ) p(x 3 ) 2 − 2 h p(x 3 ) + p(x 5 )h2 + q(x2 ) 2 2    p(x 5 )  2 − 2  h   ... ...     2 h2 − p(x 5 ) 2 h2 w1        w2      = λ  w3     ..   .    wk w1    w2    w3 ,  ..  .   wk hay Aw = λw, trong đó A là ma trận ba đường chéo đối xứng. Đây là một ví dụ về bài toán giá trị riêng của một ma trận thưa. 1.1.2 Một số khái niêm và ký hiệu Các trường số thực và số phức được biểu thị tương ứng bằng R và C. Chúng tôi biểu thị không gian vectơ có n thành phần thực bởi Rn và không gian vectơ có n thành phần phức bởi Cn .     x ∈ Rn ⇔ x =     x1    x2   ..  , xi ∈ R. .   xn Khi chúng tôi làm việc với vectơ hoặc ma trận thực hoặc phức thì chúng tôi viết như sau, ví dụ x ∈ Fn . Tích vô hướng của hai vectơ cỡ n trong C được định nghĩa là (x, y) = n X xi y i = y ∗ x, (1.5) i=1 y ∗ = (y 1 , y 2 , ..., y n ) là liên hợp chuyển vị của vectơ phức. Để đơn giản hóa các ký hiệu chúng tôi biểu thị chuyển vị thực bằng một dấu sao. Hai vectơ x và y được gọi là trực giao nếu x∗ y = 0. Ta ký hiệu là x⊥y. Tích vô hướng trong (1.5) tạo ra một chuẩn trong F n X p 1 ||x|| = (x, x) = ( |xi |2 ) 2 . i=1 (1.6) 7 Trong đó |xi | là modul của số phức hoặc trị tuyệt đối của số thực. Chuẩn này thường được gọi là chuẩn Euclid hay chuẩn - 2. Ma trận cỡ m × n trong trường F được ký hiệu là Fm×n ,   a a12 · · · a1n   11     a a · · · a 21 22 2n  A ∈ Fm×n ⇔ A =   .. . .  , aij ∈ F. . .  . . .    am1 am2 · · · amn Ma trận A∗ ∈ Fm×n ,     ∗ A =    a11 a21 · · · am1 a12 a22 · · · am2 .. .. .. . . . an1 an2 · · · anm         là Hermite chuyển vị của A. Chú ý rằng với cách viết này vectơ cỡ n có thể được xác định bởi ma trận cỡ n × 1. Các khái niệm sau đây của các ma trận vuông là đặc biệt quan trọng: • A ∈ Fn×n được gọi là Hermite nếu và chỉ nếu A∗ = A . • Một ma trận Hermite thực được gọi là đối xứng. • U ∈ Fn×n được gọi là Unita nếu U −1 = U ∗ , hay U ∗ U = In . • Ma trận Unita thực được gọi là trực giao. • A ∈ Fn×n được gọi là chuẩn tắc nếu A∗ A = AA∗ . Ma trận Hermite và ma trận Unita là chuẩn tắc. Chúng tôi định nghĩa chuẩn của một ma trận theo chuẩn vectơ (1.6) là ||A|| := max x6=0 ||Ax||| = max ||Ax||. ||x|| ||x||=1 Nếu U là Unita thì ||U x|| = ||x|| với mọi x. 8 1.1.3 Bài toán giá trị riêng Cho một ma trận vuông A ∈ Fn×n . Tìm đại lượng vô hướng λ ∈ C và vectơ x ∈ Cn , x 6= 0 sao cho Ax = λx, (1.7) (A − λI)x = 0 (1.8) hoặc có một nghiệm không tầm thường (khác không). Định nghĩa 1.1. Cho cặp (λ, x) là một nghiệm của (1.7) hoặc (1.8) tương ứng thì • λ được gọi là một giá trị riêng của A. • x được gọi là một vectơ riêng của A tương ứng với λ. • (λ, x) được gọi là một cặp riêng của A. • Đặt σ(A) là tập tất cả các giá trị riêng của A. Ta gọi nó là phổ của A. • Tất cả các vectơ riêng tương ứng với giá trị riêng λ cùng với các vectơ 0 tạo thành một không gian con tuyến tính của Cn gọi là không gian riêng tương ứng của λ. • Một giá trị riêng λ là một nghiệm của đa thức đặc trưng det(λI − A) = λn + an−1 λn−1 + ... + a0 . Một nghiệm không tầm thường y của y ∗ A = λy ∗ được gọi là vectơ riêng trái tương ứng với λ. Một vectơ riêng trái của A là một vectơ riêng phải của A∗ tương ứng với các giá trị riêng λ, ta viết A∗ y = λy. A được gọi là một ma trận tam giác trên nếu aij = 0 ∀i > j. Hay A có dạng   a a · · · a1n  11 12     a22 · · · a2n    , aij = 0 ∀i > j, A= . . . . ..      ann 9 thì chúng tôi có det(λI − A) = n Q (λ − aii ). i=1 Một không gian con V ∈ Fn được gọi là bất biến đối với A nếu AV ⊂ V. Định nghĩa 1.2. Một ma trận A ∈ Fn×n được gọi là tương đương với một ma trận C ∈ Fn×n ta viết A ∼ C khi và chỉ khi có một ma trận không suy biến S sao cho S −1 AS = C. Ánh xạ A → S −1 AS được gọi là một phép biến đổi tương đương. Định lí 1.1. Hai ma trận tương đương có giá trị riêng bằng nhau với bội số tương ứng bằng nhau. Nếu (λ, x) là một cặp riêng của A và C = S −1 AS thì (λ, S −1 x) là một cặp riêng của C. Định lí 1.2. (Phân tích Schur) Nếu A ∈ Cn×n thì có một ma trận Unita U ∈ Cn×n sao cho U ∗ AU = T là một ma trận tam giác trên. Các phần tử trên đường chéo của T là những giá trị riêng của A. Nhận xét 1.1. Vậy, bằng cách tìm phân tích Schur, ta cũng có thể tìm được các giá trị riêng của A. Chú ý 1.1. Phân tích Schur không duy nhất. Cho U ∗ AU = T là một phân tích Schur của A với U = [u1 , u2 , ..., un ]. Các phân tích Schur có thể được viết là AU = U T . Cột thứ k của phương trình này là Auk = λk uk + k−1 X tik ui , λk = tkk , (1.9) i=1 nghĩa là Auk ∈ span{u1 , ..., uk }, ∀k. (1.10) Như vậy, k vectơ Schur đầu tiên u1 , ..., uk tạo thành một không gian con bất biến đối với A. Từ (1.9) ta có vectơ Schur đầu tiên là một vectơ riêng của A (nhưng các vectơ khác thì không phải). Định lí 1.3. (Phân tích Schur thực) 10 Nếu A ∈ Rn×n thì có một ma trận trực giao Q ∈ Rn×n sao cho   R R12 · · · R1m   11    R22 · · · R2m  T   Q AQ =  . . .. ..      Rmm là tựa tam giác trên. Các khối chéo Rii là ma trận 1 × 1 hoặc 2 × 2. Một khối 1 × 1 tương ứng với một giá trị riêng thực, một khối 2 × 2 tương ứng với một cặp giá trị riêng phức liên hợp.  Ví dụ ma trận  α β   , α, β ∈ R có giá trị riêng α + iβ và α − iβ. −β α Tính phân tích Schur của ma trận Hermite là đơn giản. Đầu tiên chúng ta lưu ý rằng A là Hermite tức là các tam giác trên Λ trong phân tích Schur A = U ΛU ∗ là Hermite và chéo. Thật vậy, bởi vì Λ = Λ∗ = (U ∗ AU )∗ = U ∗ A∗ U = U ∗ AU = Λ, mỗi phần tử đường chéo λi của A thoả mãn λi = λi .Vì vậy Λ phải là thực. Tóm lại ta có kết quả sau. Định lí 1.4. (Định lý phổ cho ma trận Hermite) Cho A là Hermite thì có một ma trận Unita U và một ma trận đường chéo thực Λ sao cho ∗ A = U ΛU = n X λi ui u∗i . (1.11) i=1 Các cột u1 , ..., un của U là vectơ riêng tương ứng với giá trị riêng λ1 , ..., λn . Chúng tạo thành một cơ sở trực chuẩn cho Fn . Phân tích (1.11) được gọi là một phân tích phổ của A. Định nghĩa 1.3. Tỉ số ρ(x) := x∗ Ax , x 6= 0 x∗ x được gọi là các tỉ số Rayleigh của A tại x. 11 Định nghĩa 1.4. Một ma trận P thỏa mãn P 2 = P được gọi là một phép chiếu. Nếu P là một phép chiếu thì P x = x với mọi x trong vùng ảnh <(P ) của P . Thật vậy nếu x ∈ <(P ) thì x = P y, với y ∈ Fn và P x = P (P y) = P 2 y = P y = x. Định nghĩa 1.5. Một ma trận P được gọi là phép chiếu trực giao nếu (i) P 2 = P, (ii) P ∗ = P. Mệnh đề 1.1. Cho P là một phép chiếu, thì các phát biểu sau là tương đương (i) P ∗ = P , (ii) <(I − P )⊥<(P ) tức là (P x)∗ (I − P )y = 0 ∀x, y. Định nghĩa 1.6. Góc giữa hai vectơ x và y khác không được định nghĩa bởi       ∗ ∗ y |x y| xx ∠(x, y) = arcsin I − ||x||2 ||y|| = arccos ||x||.||y|| . Định nghĩa 1.7. Các ma trận G(i, j, ϑ) ∈ Rn×n là một phép quay, được định nghĩa bởi       G(i, j, ϑ) =       I c s I −s c I           trong đó c = cos(ϑ) và s = sin(ϑ), G(i, j, ϑ) là một ma trận trực giao. Nếu x ∈ Rn và y = G(i, j, ϑ)∗ x thì    cx − sxj ,   i yk = sxi + cxj ,    x . k k=i k=j k 6= i, j Chúng tôi có thể buộc yj bằng không bằng cách thiết lập c= p xi , |xi |2 + |xj |2 s= p −xj . |xi |2 + |xj |2 12 Định nghĩa 1.8. Cho A là một ma trận vuông. Phép phân tích LU của A là cách viết A thành tích của hai ma trận có dạng A = LU , trong đó L và U lần lượt là các ma trận tam giác dưới và tam giác trên có cùng kích thước với A. Phép phân tích LDU là cách phân tích có dạng A = LDU , với D là một ma trận chéo, L và U là các ma trận tam giác đơn vị, nghĩa là tất cả các phần tử trên đường chéo của L và U đều bằng một. Phép phân tích LU P là cách phân tích có dạng P A = LU , với L và U tương ứng là ma trận tam giác dưới và trên, và P là một ma trận hoán vị, nghĩa là P chỉ gồm không và một và chỉ có duy nhất một phần tử 1 trên mỗi dòng và cột. Định nghĩa 1.9. Cho A ∈ Cn×m , n ≥ m có hạng là m (nghĩa là các cột của A độc lập tuyến tính). bR, b trong đó Q b ∈ Cn×m có các cột là các vectơ trực giao và Phân tích A = Q b ∈ Cm×m là ma trận tam giác trên. Phép phân tích như vậy (nếu có) gọi là phân R tích QR rút gọn của ma trận A. Với ma trận A như trên, dạng phân tích QR đầy đủ của A chính là sự mở rộng b n − m vectơ trực chuẩn để tạo của QR rút gọn bằng cách thêm vào bên phải của Q b cũng được thêm vào bên dưới thành ma trận Unita Q có n hàng và n cột. Ma trận R n − m dòng không tạo thành ma trận tam giác trên R với n dòng và m cột. 1.2 Không gian con Krylov Định nghĩa 1.10. Cho A ∈ Cn×n . Các ma trận K m (x) = K m (x, A) := [x, Ax, ..., A(m−1) x] ∈ Fn×m được tạo bởi vectơ x ∈ Fn được gọi là ma trận Krylov. Không gian vectơ sinh bởi các cột của nó được goi là không gian con Krylov Km (x) = Km (x, A) := span{x, Ax, A2 x, ..., A(m−1) x} = <(K m (x)) ⊂ Fn . 13 Một cơ sở tự nhiên của không gian Krylov là các vectơ x, Ax, ... cho đến khi hệ này vẫn độc lập tuyến tính. Tuy nhiên, chúng thường có xu hướng gần phụ thuộc tuyến tính. Điều này cần phải tránh trong tính toán. Do đó, thay vì sử dụng cơ sở tự nhiên, người ta tìm cách xây dựng một cơ sở trực chuẩn của nó. Các phương pháp Arnoldi và Lanczos là những phương pháp để tính toán một cơ sở trực chuẩn của không gian Krylov. Cho [x, Ax, ..., A(k−1) x] = Q(k) R(k) là nhân tử QR của ma trận Krylov K m (x). (k) Các giá trị Ritz ϑj , 1 ≤ j ≤ k và Ritz vectơ của A trong không gian này thu được bằng phương pháp của bài toán giá trị riêng k × k ∗ Q(k) AQ(k) y = ϑ(k) y. (k) (1.12) (k) Nếu (ϑj , yj ) là một cặp riêng của (1.12) thì (ϑj , Q(k) yj ) là một cặp Ritz của A trong K m (x). Ta có các tính chất sau của không gian Krylov 1. Km (x, A) = Km (αx, βA), α, β 6= 0. 2. Km (x, A − σI) = Km (x, A). 3. Nếu U là Unita thì U Km (U ∗ x, U ∗ AU ) = Km (x, A). Thực tế là K m (x, A) = [x, Ax, ..., A(m−1) x] = U [U ∗ x, (U ∗ AU )U ∗ x, ..., (U ∗ AU )m−1 U ∗ x], = U K m (U ∗ x, U ∗ AU ). Rõ ràng là đối với ma trận A cỡ n × n các cột của ma trận Krylov K n+1 (x) là phụ thuộc tuyến tính. Mặt khác nếu u là một vectơ riêng tương ứng với giá trị riêng λ thì Au = λu và K2 (u) = span{u, Au} = span{u} = K1 (u). Vì vậy, có một số m nhỏ nhất thỏa mãn 1 ≤ m ≤ n phụ thuộc vào x sao cho   K1 (x) ⊂ K2 (x) ⊂ ... ⊂ Km (x) = Km+1 (x) = ...  K1 (x) 6= K2 (x) 6= ... 6= Km (x) Đối với số m này Km+1 (x) = [x, Ax, ..., Am x] ∈ Fn×m+1 có cột phụ thuộc tuyến 14 tính tức là có một vectơ khác không a ∈ Fm+1 sao cho Km+1 (x)a = p(A)x = 0 với p(λ) = a0 + a1 λ + ... + am λm . Đa thức p(λ) với am 6= 0 được gọi là đa thức tối thiểu của A so với x. 15 Chương 2 Một số phương pháp tìm giá trị riêng Như đã biết giá trị riêng của ma trận là nghiệm của phương trình đặc trưng, như vậy ý tưởng đơn giản để tìm giá trị riêng đó là giải phương trình đặc trưng. Một ma trận cỡ n × n thì phương trình đặc trưng là một phương trình đa thức bậc n, nếu muốn tìm giá trị riêng chính xác thì ta phải giải được chính xác nghiệm của phương trình đặc trưng. Theo định lý nổi tiếng của lý thuyêt Galois thì phương trình đa thức từ bậc 5 trở lên không thể giải được bằng căn thức, tức là nghiệm của nó không thể tính được bằng các phép tính của các số hữu tỉ như là cộng, trừ, nhân, chia hoặc lấy căn. Như vậy, đối với ma trận từ bậc 5 trở lên chúng ta không thể tìm được chính xác giá trị riêng. Vậy để giải được những bài toán thực tế mà có cấp lớn hơn thì ta buộc phải sử dụng phương pháp xấp xỉ, những phương pháp xấp xỉ ở đây đều là những phương pháp lặp. Trong chương này chúng tôi sẽ giới thiệu một số phương pháp lặp phổ biến, thông dụng và hiệu quả để tính giá trị riêng. Chương này được viết dựa trên tài liệu tham khảo [1], [2]. 2.1 2.1.1 Phương pháp luỹ thừa Lặp đơn vectơ Trong mục này chúng tôi trình bày một phương pháp đơn giản để tính giá trị riêng có modul lớn nhất và duy nhất. Cho A ∈ Fn×n bắt đầu với một vectơ ban đầu  ∞ tùy ý x(0) ∈ Fn chúng ta hình thành các chuỗi vectơ x(k) k=0 được xác định như