báo cáo giải tích số tìm giá trị riêng trội giá trị riêng trội tiếp theo

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (3.58 MB, 16 trang )

Trang 1<div class="page_container" data-page="1">

ĐỀ TÀI:

TÌM GIÁ TR RIÊNG TR I & Ị Ộ

GIÁ TRỊ RIÊNG TRỘI TIẾP THEO

GV hướng dẫn: TS. HÀ TH NGOC YẾNỊ

Nhóm sinh viên thực hiện:

HÀ NỘI, 4/2021

</div>Trang 2<div class="page_container" data-page="2">

2 LỜI NÓI Đ UẦ

Vecto riêng và giá trị riêng có vai trị nổi bật trong vi c phân tích các biệ ến đổi tuy n ếtính. Trong tiếng Anh, giá tr ị riêng và vecto riêng tương ứng được gọi là eigenvalue và eigenvector. Ban đầu được sử dụng để nghiên cứu các trục chính của sự quay của các vật rắn, giá tr riêng và vecto riêng ngày càng có nhi u ng d ng, ví d : trong phân tích n ị ề ứ ụ ụ ổđịnh, phân tích rung động, lí thuyết orbital nguyên tử, nghiên cứu băng hà trong địa chất, hệ số lây nhiễm cơ bản, và công ngh nh n di n khuôn mệ ậ ệ ặt.

Với phương pháp Danilepski và phương pháp A.N.Cơrưlơp là nh ng ữ phương pháp tìm trị riêng đúng (nếu nghiệm của phương trình đặc trưng được giải đúng). Với những phương trình đặc trưng giải nghiệm gần đúng thì ta chỉ được giá trị riêng gần đúng. Sau khi tìm hi u và nghiên c u ể ứ nhóm chúng em xin trình bày phương pháp lũy thừ đểa tìm tr ịriêng gần đúng. Bài báo cáo dưới đây của bọn em g m hai ph n: Lí thuy t và Thu t tốn ồ ầ ế ậáp dụng phương pháp lũy thừa để tìm giá trị riêng trội và phương pháp xuống thang đểtìm các giá trị riêng ti p theo. ế

Do khả năng viết thuật tốn và chương trình của nhóm em cịn kém nên khơng thể ạ t o ra được một chương trình tìm giá trị riêng trội và giá tr riêng trội tiếp theo một cách hoàn ịchỉnh, nên mong cơ góp ý cho bọn em ạ.

Chúng em xin cảm ơn cô Hà Thị Ngọc Yến đã có những hướng d n, góp ý trong quá ẫtrình tiến hành bài nghiên c u này. ứ

Nhóm sinh viên th c hi n ự ệ

</div>Trang 3<div class="page_container" data-page="3">

3 2 MỤC LỤC:

I. Nội dung lí thuyết ... 4

1. Trị riêng, vecto riêng ... 4

1.1. Định nghĩa ... 4

1.2. Tính chất ... 4

2. Giá trị riêng trội ... 4

3. Phương pháp lũy thừa tìm GTR trội ... 4

3.1. Trường hợp 1: trị riêng trội |𝝀𝟏| > |𝝀𝟐| ... 5

3.2. Trường hợp 2: |λ1| = |λ2| > |λ3| và λ1 = −λ2 ... 6

3.3. Trường hợp 3: |𝜆1| = |𝜆2| > |𝜆3| và 𝜆1= 𝜆2 ... 7

4. Phương pháp xuống thang tìm GTR trội tiếp theo ... 9

II. Thuật toán và ví ... 11 dụ1. Thuật tốn ... 11

1.1. Thuật toán tổng quan ... 11

1.2. Thuật tốn chi tiết ... 11 2. Ví ... 13 dụ

</div>Trang 4<div class="page_container" data-page="4">

4 I. Nội dung lí thuyết

1. Trị riêng, vectơ riêng:1.1 Định nghĩa:

Cho A là ma trận vuông cấp n trên trường số K (K= ℝ ℂ ; ). Số 𝜆 ∈ 𝐾 được gọi là giá tr riêng (gị ọi tắt là tr ị riêng – kí hi u GTR) c a ma tr n A, n u t n t i mệ ủ ậ ế ồ ạ ột vectơ 𝑣 ≠ 0sao cho: A𝑣 = 𝜆𝑣

Khi đó vectơ 𝑣 được gọi là vectơ riêng của ma trận A ứng v giá tr riêng ới ị 𝜆1.2 Tính chất:

- Giá trị riêng 𝜆 chính là nghiệm của phương trình det(A- 𝜆I) = 0 được gọi là phương (trình đặc trưng của ma trận A).

- Một giá trị riêng có thể có nhiều vectơ riêng.- Mỗi vectơ riêng chỉ ứng v i m t giá tr riêng duy nhớ ộ ị ất.

- Ma trận A là nghiệm của đa th c đứ ặc trưng của chính nó (trong trường hợp này đa thức đặc trưng được coi là đa thức ma trận, nghĩa là biến số của nó khơng phải là biến số thực mà là bi n ma tr n) ế ậ

- Nếu 𝜆 = 0 là giá trị riêng c a ma tr n A thì A khơng kh ngh ch. ủ ậ ả ị Ngược lại, n u mế ọi giá tr riêng cị ủa A đều khác khơng thì A kh nghả ịch.

- Nếu giá tr𝜆là ị riêng c a ma tr n A thì ủ ậ 𝜆𝑘là giá trị riêng của ma tr n ậ 𝐴𝑘1.3 Một số cách tìm giá tr ị riêng và vector riêng

-Giải phương trình det A − λI = 0( ) tìm các giá trị riêng. Ứng với mỗi giá trị riêng λta gi i hả ệ phương trình tuyến tính thu n nhầ ất (A − λI v = 0) .

-Sử dụng phương pháp Danhilepski đưa ma trậ A ề ạn v d ng ma trận có phương trình đặc trưng theo cơng thức để giải và tìm giá trị riêng.

-Sử dụng phương pháp luỹ thừa để tính gần đúng giá trị riêng tr i và vector riêng ộtương ứng.

Khi đó:|𝜆1|> |𝜆2| ⇒ 𝜆1 là giá trị riêng ội tr

|𝜆1|= |𝜆2| > |𝜆 | ⇒ 𝜆3 1, 𝜆2𝑙à 𝑐á𝑐 á ị 𝑔𝑖 𝑡𝑟 𝑟𝑖ê𝑛𝑔 𝑡𝑟ộ𝑖

3. Phương pháp lũy thừa tìm GTR trội

Sử d ng tính chụ ấ : |𝑞| < 1 ⇒ 𝑞t 𝑛𝑛→∞→ 0 Xây d ng công th c ự ứ

</div>Trang 5<div class="page_container" data-page="5">

5

- Xét ma tr n A[a ] là ma tr n vuông c p n, có các ph n t a v i i, j = ậ ij ậ ấ ầ ử ij ớ 1, 𝑛 u là thđề ực và mỗi trị riêng bội k có đủ k vectơ riêng độ ậc l p tuy n tính. ế

- Như vậy, gi s ma tr n A cả ử ậ ấp n có đủ n tr riêng thị ực hoặc phức (đơn hoặc bội) được đánh số theo module giảm dần:

|𝜆1| ≥ |𝜆2| ≥ … … … ≥ |𝜆 |𝑛

- Các vecto riêng tương ứng lần lượt là: 𝑣1, 𝑣2, 𝑣3… 𝑣𝑛 là các vecto độc lập tuyến tính - Giả ử: có vecto X là tổ ợ s h p tuy n tính các vecto riêng ế

X= 1n

i ii

a v với ai – Const (I) Ta chọn vectơ X nào có a 0 và tính dãy: i≠

i i iii i

A a v a v (VìAvi i iv ) ………

AkX = A(A X) k-1

ki iii

a v⇒ A Xkk = a v1 1+

3.1. Trường hợp 1: trị riêng trội |𝝀𝟏| > |𝝀𝟐|

Giả sử trị riêng c a ma tr n A thủ ậ ỏa mãn điều ki n: ệ

2 3 34 3 53 2 9

</div>Trang 6<div class="page_container" data-page="6">

6 Giải:

Ta chọn vector riêng X bất kì, ở đây lấy X = (1,1,1) t. Ta tính được AX, A2X,... được viết thành bảng sau:

A X AX A2X A3X A4X A5X A6X 2 3 2 1 7 78 900 10589 125128 1480345 4 3 5 1 12 134 1569 18512 218927 2590563 3 2 9 1 14 171 2041 24207 286654 3393124 Ta thấy:

125128≈ 11 8306. ( 𝑗 = 1)2590563

218927≈ 11 8330. ( 𝑗 = 2)3393124

286654≈ 11 8370. (𝑗 = 3)

Do đó có thể lấy λ1 ≈ 11.83 và vector riêng là vector A6X. Tuy v y các vector riêng khác ậnhau một hằng s nhân, nên ta ch n vector riêng X = (1; 1.750; 2.991) . ố ọ 1 t

Nhận xét: Vậy v i gi thiớ ả ế (*), ta cht ọn vectơ 𝑋 ấ bt kì có 𝑎1 ≠ 0, tính dãy

𝐴𝑋, 𝐴 𝑋, … . , 𝐴2𝑘+1𝑋, tính cho đến khi tỉ số (1) xấp xỉ bằng nhau, 𝑘 đủ lớn, thì tìm được trị riêng trội là 𝜆1 c a ma tr n . N u các t sủ ậ 𝐴 ế ỉ ố này không tương đương nhau thì ta chuyển sang trường h p 2 ợ

3.2. Trường hợp 2: |λ1| = λ| 2| > λ| |3 và λ1= −λ2 Giả sử: |𝜆1| = 𝜆| 2| > 𝜆| 3| ≥ ⋯ ≥ 𝜆| |𝑛 và 𝜆1= −𝜆2 Ta có:

AX 1 1 12 2 23n

i i ii

𝐴𝑋 = 𝜆1(𝑎1𝑣1− 𝑎2𝑣2) +3n

i i ii

a v

11 12 23

i iii

22

</div>Trang 7<div class="page_container" data-page="7">

1 12 22

* Để tìm vecto riêng tương ứng: Từ: A2n−1X ≈ λ12n−1(a1v1− a2v2)

A2nX ≈ λ12n(a1v1+ a2v2)

⇒ A2kX + λ1A2k−1X ≈ λ12k2a1v1 và A2kX − λ1A2k−1X ≈ λ12k2a2v2 (cộng trừ 2 v ) ế

Hay A A( 2kX + λ1A2k−1X) ≈ λ12k2a1Av1= λ12k2a1λ1v1= λ1(λ12k2a1v1) ≈ λ1(A2kX +λ A1 2k−1X)

Vậy với 𝛌𝟏 thì vecto riêng tương ứng là:

v1≈ A2kX + λ1A2k−1X

Cịn với 𝛌 = −𝛌𝟐 𝟏thì vecto riêng tương ứng là:

v ≈ A2 2kX − λ A1 2k−1X

3.3. Trường hợp 3: |𝜆1| = 𝜆| 2| > 𝜆| |3 và 𝜆1= 𝜆2Giả sử: |𝜆1| = 𝜆| 2| > 𝜆| 3| ≥ 𝜆| 4| ≥ ⋯ ≥ |𝜆𝑛| và 𝜆 = 𝜆12 Ta có:

𝐴 𝑋𝑘

𝜆𝑘1 = 𝑎1𝑣1+ 𝑎2𝜆2𝑘

a v ; 𝜆1,2= 𝛼 ± 𝑖𝛽 Ta tính: lim

a v] = 0 ⇒ 𝐴𝜆𝑘𝑋

𝑘 ≈ 𝑎1𝑣1+ 𝑎2𝜆2𝑘

𝜆1𝑘𝑣2⇒ 𝐴𝑘𝑋= 𝑎1𝜆1𝑘𝑣1+ 𝑎2𝜆2𝑘𝑣2⇒ 𝐴𝑛+2𝑋 − 𝜆 + 𝜆(1 2)𝐴𝑛+1𝑋 + 𝜆 𝐴

1𝜆2 𝑛𝑋 = 0 Đặt: 𝜆 + 𝜆 = 𝑝 ; 𝜆121𝜆2= 𝑞; (1; -p; q) ≠ (0; 0; 0) 𝐴𝑛+2𝑋 − 𝑝𝐴𝑛+1𝑋 + 𝑞𝐴 𝑋 = 0𝑛

</div>Trang 8<div class="page_container" data-page="8">

8 • 𝜆 , 𝜆12 là 2 nghi m cệ ủa phương trình: 𝜆 − 𝑝𝜆+ 𝑞 = 0

• Viết dưới d ng tạ ọa độ : (𝐴𝑛+2𝑋)𝑖− 𝑝 𝐴( 𝑛+1𝑋)𝑖+ 𝑞 𝐴( 𝑛𝑋)𝑖= 0 𝑖 = 1, 𝑛• Lấy hai tọa độ ấ b t kì, ch ng h n iẳ ạ = 𝑟 , 𝑖 = 𝑠, (𝑟 ≠ 𝑠) ta được hai phương trình và

ghép với phương trình (19) được hệ 3 phương trình: {

𝜆2− 𝑝𝜆 + 𝑞 = 0(𝐴𝑛+2𝑋)𝑟− 𝑝(𝐴𝑛+1𝑋)𝑟+ 𝑞(𝐴𝑛𝑋)𝑟= 0(𝐴𝑛+2𝑋)𝑠− 𝑝(𝐴𝑛+1𝑋)𝑠+ 𝑞(𝐴𝑛𝑋)𝑠= 0 𝑣ớ𝑖 3 ẩ𝑛 𝑙à 1, 𝑝, 𝑞

• Hệ trên là hệ thuần nhất nên để có nghiệm khác 0 thì định thức phả ằi b ng 0

𝐷𝑒𝑡 |

(𝐴𝑛+2𝑋)𝑟 (𝐴𝑛+1𝑋)𝑟 (𝐴𝑛𝑋)𝑟(𝐴𝑛+2𝑋)𝑠 (𝐴𝑛+1𝑋)𝑠 (𝐴𝑛𝑋)𝑠

| = 0 Từ đó ta tính được 𝜆1;2• Để tìm vecto riêng, ta xét:

𝐴 𝑋 ≈𝑛 𝜆1𝑛𝑎1𝑣1+ 𝜆2𝑛𝑎2𝑣2

=> { 𝐴𝑛+1𝑋 − 𝜆 𝐴 𝑋 ≈ 𝑎1 𝑛 2𝜆2𝑛(𝜆2− 𝜆1)𝑣2 𝐴𝑛+1𝑋 − 𝜆 𝐴 𝑋 ≈ 𝑎 𝜆

2 𝑛 1 1𝑛(𝜆1− 𝜆2)𝑣1=>{ 𝐴(𝐴𝑛+1𝑋 − 𝜆 𝐴1 𝑛𝑋) ≈ 𝜆2(𝐴𝑛+1𝑋 − 𝜆 𝐴

1 𝑛𝑋) 𝐴(𝐴𝑛+1𝑋 − 𝜆 𝐴 ≈ 𝜆

2 𝑛𝑋) 1(𝐴𝑛+1𝑋 − 𝜆 𝐴2 𝑛𝑋) Vecto riêng ứng với 𝜆2là(𝐴𝑛+1𝑋 − 𝜆 𝐴

1 𝑛𝑋) Vecto riêng ứng với 𝜆1 là (𝐴𝑛+1𝑋 − 𝜆 𝐴

2 𝑛𝑋)Ví dụ 2: Tính tr riêng và vector riêng c a ma tr n sau ị ủ ậ

𝐴 =

2 1 1 17 5 2 1

1 0 1 0Giải:

Chọn = (-1,1,0,0) . Ta tính A X thành b ng sau: X tm ả

</div>Trang 9<div class="page_container" data-page="9">

9

Qua bảng này, ta th y r ng các t s (8) và (12) biấ ằ ỉ ố ến đổi khá linh tinh, điều đó chứng t ỏrằng ma trận A có các trị riêng trội là ph c liên h p ứ ợ 𝜆 𝑣à1 𝜆2= 𝜆1 . Chúng là nghiệm của phương trình dạng (19), cụ thể là:

1 -29573 -10922𝑍 78374 201490 𝑍2 −35205 −1396942

| = 0 Hay 𝑍2+ 8, 𝑍 +02 20 05, = 0

2 𝑚𝑋 1𝜆1𝑚(𝜆1− 𝜆2)𝑋2Do đó

4. Phương pháp xuống thang tìm GTR trội tiếp theo

Mối quan h giệ ữa trị riêng c a hai ma tr n và : ủ ậ 𝐴 𝐴𝑇Giả s là tr riêng cử λ ị ủa ma trậ An T. Khi đó: det( AT- λI) = 0Ta có : det( AT- λI) = det( AT- λIT) ( do IT= I)

= det ((A −λI)T)

= det( A − λI) ( do det(A) = det(AT) ) => 2 ma tr n A và ậ ATcó cùng trị riêng.

Tiếp theo, ta đi tìm mối quan hệ giữa các vectơ riêng ứng với các trị riêng khác nhau của ma tr n A và ậ AT.

Đặt vấn đề Giả sử 𝑣: 1 là vectơ riêng của ma trận 𝐴 tương ứng v i giá tr riêng và ớ ị 𝜆1 𝑊1là vectơ riêng của ma trận 𝐴𝑇tương ứng với giá tr ị riêng 𝜆1.

Từ định nghĩa 𝐴𝑣 = 𝜆 𝑣11 1 ta viết: (𝐴 −𝜆𝐸)𝑣1= 0 • Ta tạo ma tr n ậ 𝐴1 d ng: ạ 𝐴1= 𝐴 −𝜆1

𝑊1𝑇𝑣1𝑣1𝑊1𝑇 (**)

Chú ý là 𝑣 𝑊11𝑇 là m t ma tr n còn ộ ậ 𝑊1𝑇𝑣1 là một con số. Khi nhân hai vế c a biủ ểu thức

(**) với 𝑣1 ta có: 𝐴1𝑣1= 𝐴𝑣1− 𝜆1

𝑊1𝑇𝑣1𝑣1𝑊1𝑇𝑣1

</div>Trang 10<div class="page_container" data-page="10">

10 = 𝐴𝑣 − 𝜆 𝑣1 1 1.

𝑊1𝑇𝑣1 = 𝐴𝑣 − 𝜆 𝑣11 1= 0 => 𝐴1 chấp nh n giá tr riêng b ng không. ậ ị ằ

Nếu v 2là vec tơ riêng tương ứng với giá trị riêng ,thì khi nhân (**) v2 ới v2 ta có: 𝐴1𝑣2= 𝐴𝑣2− 𝜆1

𝑊1𝑇𝑣1𝑣1𝑊1𝑇𝑣2 = 𝐴𝑣 − 𝜆 𝑣2 1 1.𝑊1𝑇𝑣2

Theo định nghĩa vì W1 là vectơ riêng của AT 𝜆 𝑊11= 𝐴𝑇𝑊1 Chuyển vị ta nhận được: (𝐴 𝑊𝑇

1)𝑇= 𝜆1𝑊1𝑇Áp dụng tính ch t: ấ (𝐴𝑣)𝑇= 𝑣 𝐴𝑇𝑇 và (𝐴𝑇)𝑇= 𝐴 => 𝑊1𝑇𝐴 = 𝜆1𝑊1𝑇

Nhân cả 2 v vế ới 𝑣2=> 𝑊 1𝑇𝐴𝑣2= 𝜆1𝑊1𝑇𝑣2 mà 𝐴𝑣2= 𝜆 𝑣22Nên: 𝑊1𝑇𝜆2𝑣2= 𝑊1𝑇𝜆1𝑣2 ⇒ (𝜆1− 𝜆2)𝑊1𝑇𝑣2= 0

Khi 𝜆 ≠ 𝜆1 2 thì: 𝑊1𝑇𝑣2= 0 thay vào (***) ta có: 𝐴1𝑣2= 𝐴𝑣2= 𝐴𝑣2

Tìm giá tr - ị riêng và vec tơ riêng của A1 b ng cách l p luằ ặ ỹ thừa và cứ thế tiế ụp t c và xuống thang (n-1) lần ta tìm đủ n giá trị riêng c a ma tr n A. ủ ậ

</div>Trang 11<div class="page_container" data-page="11">

11 II. Thuật toán và h ệ thống ví d ụ

1. Thuật tốn

a. Nhập ma tr n vng c p n ậ ấb. Lặp n lần:

i. Khởi t o vector X=(1,1,..1) ạ tii. Tính các vector A X và ki m tra: m ể

1. Nếu các vector k nhau h i tề ộ ụ, đánh dấu là trường hợp 1 2. Nếu các vector có b c luậ ỹ thừa cùng ch n ho c l h i tẵ ặ ẻ ộ ụ,

3. Nếu từ vector th 10 tr ứ ở đi, 2 trường hợp trên khơng có dấu hi u tho ệ ả mãn, đánh dấ là trường hợp 4. u iii. Xử lý các trường hợp:

iv. TH1&2: Đưa ra trị riêng trội và vector tương ứng. Tính ma trận mới để tìm tr riêng ti p theo ị ế

v. TH3&4: Đưa ra các trị riêng trội và vector riêng tương ứng. Thơng báo kết thúc chương trình.

1.2. Thuật tốn chi ti ết:

Trong chương trình, ta sẽ lưu các vector AmX vào các c t c a 1 mộ ủ ảng 2 chi u là ềmảng B. Ta có th ể thay vì lưu tồn bộ các vector tính được thì chỉ lưu 1 số lượng

truy c p tu ý n các vector ậ ỳ đế AmX.

Đối với phương pháp luỹ thừa, quan tr ng nh t cọ ấ ủa thuật toán là điều ki n d ng vịng ệ ừlặp tính tốn vì vi c tính tốn ch g m các phép nhân ma tr n và các cơng th c có ệ ỉ ồ ậ ứ

vector được lưu trong mảng B:

a. Dữ u vào: m ng B, hàng h1, hàng h2, s liệ ả ố n.b. Biến tam ≔ |b 1,[ h1]− b[1,h2 ]|

i. Nếu (|b[i,h1]− b[i,h2]|)> tam thì tam ≔ b i,| [ h1]− b[i,h2]|

d. kiemtra = tam

</div>Trang 12<div class="page_container" data-page="12">

12

e. Nếu kiemtra b, m, m − 1, n( ) ≤ E, thì th= 1, kết thúc vi c tính tốnệf. Nếu kiemtra b, m, m − 2, n ≤ E( ) , thì th = 3, kết thúc vi c tính tốnệg. Nếu kiemtra b, m, m − 1, n − kiemtra b, m − 1, m − 2, n > 0( ) ( ) và

kiemtra b, m, m − 2, n − kiemtra b, m − 1, m − 3, n > 0( ) ( ) và 𝑚 >10 thì th = 4, kết thúc vi c tính tốn.ệ

th=3 thì th=4 b i n u tr ở ế ị riêng khơng rơi vào 3 trường hợp đầu thì s ẽ rơi và trường h p phức) ợ

hội tụ thì hi u c a chúng ph i nh ệ ủ ả ỏ hơn 0, ngược lại tức là không h i t . Bi n th dùng ộ ụ ế

h. Trường h p 1 và 2: ợ

i. Tính thêm 1 vector Am+1X. Tính được giá trị riêng trội b ng to ằ ạ độlớn nh t cấ ủa Am+1X.

ii. In ra vector riêng là Am+1X

iii. Tính ma tr n A mậ ới để tìm tr riêng ti p theo. ị ếi. Trường h p 3: ợ

i. Tính thêm 2 vector Am+1X và Am+2X.

ii. Thiết lập và giải phương trình (8) để tìm được 2 trị riêng ph c ứ

iv. Kết thúc chương trình.