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

ĐẠI HỌC BÁCH KHOA HÀ NỘI

VIỆN TỐN ỨNG DỤNG VÀ TIN HỌC

CÁC PHƯƠNG PHÁP TÍNH GẦN ĐÚNG MATRẬN NGHỊCH ĐẢO

Hà Minh Dũng - MSSV 20200096GIẢNG VIÊN HƯỚNG DẪN

TS. Hà Thị Ngọc Yến

Hà Nội, tháng 1, 2022

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

2.2 Lí do chọn X<small>0</small>= <small>AT∥ ∥A2</small> . . . . 3

4.2 Ví dụ 2 (Ma trận chéo trội hàng) . . . . 15

4.3 Ví dụ 3 (Ma trận chéo trội cột gần suy biến) . . . . 18

4.4 Ví dụ 4 (Ma trận chéo trội cỡ lớn) . . . . 20

5 Phân tích và tổng kết các phương pháp 265.1 Nhận xét các ví dụ . . . . 26

5.2 Ưu, nhược diểm của các phương pháp . . . . 26

5.2.1 Ưu điểm . . . . 26

5.2.2 Nhược điểm . . . . 26

6 Hướng dẫn sử dụng chương trình 276.1 Phương pháp Newton . . . . 27

6.2 Phương pháp Jacobi . . . . 27

6.3 Phương pháp Gauss-Seidel . . . . 28

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

1 Đặt vấn đề

1.1 Phát biểu bài tốn

Bài tốn. ChomatrậnvngA cấpn.Tìmmatrậnnghịchđảocủa nếucó.A

Trong báo cáo này, ta sẽ nghiên cứu các phương pháp tìm gần đúng ma trận nghịch đảo củamột ma trận thực vng cấp .n

1.2 Lí do cần giải gần đúng ma trận nghịch đảo

Do khuyết điểm của các phương pháp tính đúng ma trận nghịch đảo:Máy tính bắt buộc phải thực hiện tính tốn q nhiều khi cần độ chính xác caoKhơng kiểm sốt được sai số tính tốn do giới hạn tính tốn của máy tính

Nên ta đề xuất sử dụng các phương pháp lặp để làm tăng độ chính xác của các ma trậnnghịch đảo có độ chính xác thấp và để kiểm soát sai số dễ dàng hơn.

1.3 Các phương pháp giải

Báo cáo này sẽ trình bày 3 phương pháp giải bao gồm phương pháp Newton có thể áp dụngvới ma trận bất kì và hai phương pháp Jacobi và Gauss-Seidel áp dụng với ma trận chéo trội.

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

Suy ra

G<small>k</small>=G<small>2−1</small>= G<small>4</small>

(1)Như vậy, nếu ta chọn xấp xỉ ban đầuX<small>0</small>gần A<small>−1</small>, sao cho

∥G<small>0</small>∥ = ∥E − AX<small>0</small>∥ < 1Thì ∥A<small>−1</small>− X<small>k</small>∥→0 rất nhanh khi k →∞ hay dãy (X<small>k</small>) hội tụ và

Kí hiệu λ(A) là giá trị lớn nhất của các trị tuyệt đối của các trị riêngλ_i(A)của ma trận A.Khi đó, với i bất kì, ta có

AA<small>T</small>x<small>i</small>= λ<small>i</small>(AA<small>T</small>)x<small>i</small>

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

Trong đó <small>i</small>là một vector khác . Nhân hai vế với <small>i</small> ta đượcx<small>T</small>

<small>i</small>AA<small>T</small>x= x<small>T</small>

<small>i</small>λ<small>i</small>(AA<small>T</small>)x<small>i</small>⇔ (x<small>Ti</small>A)(x<small>T</small>

<small>i</small>A)<small>T</small>= λ<small>i</small>(AA<small>T</small>)x<small>Ti</small>x<small>i</small>

<small>i</small>A∥<small>2</small>= λ<small>i</small>(AA<small>T</small>)∥x<small>i</small>∥⇔ λ AA<small>i</small>( <small>T</small>) =^∥x

Trước hết ta sẽ xét trường hợpdet(A) = 0.

Do det(A) = 0 và x<small>i</small> = 0 nên ta suy raλ<small>i</small>(AA<small>T</small>) > , ∀i0 .Từ đó ta có

0 <^λⁱ^(AA

<small>T</small>)λ(AA<small>T</small>)^<^{1, ∀i}Đặt

Trong đó

α= ¹∥A∥<small>2</small>= ¹

λ AA( <small>T</small>)Ta cóE− AX₀= E −αAA<small>T</small>là ma trận đối xứng nên

∥E − AX<small>0</small>∥ =q

<1Như vậy, ma trận X<small>0</small>= <small>AT</small>

<small>∥ ∥A2</small>thỏa mãn điều kiện hội tụ.

Mặt khác, ta xét trường hợp det(A) = 0. Lúc này, phương trình Ax = 0 có nghiệmx<small>0</small>khác0 nên λ<small>0</small>= 0 là một giá trị riêng của ma trậnA.

Từ (2) ta suy raλ<small>i</small>(AA<small>T</small>) ≥0, kéo theo

0 ≤^λ<small>i</small>(AA<small>T</small>)λ(AA<small>T</small>)^<^{1, ∀i}Suy ra

|1 −^λ<small>i</small>(AA<small>T</small>)λ AA( <small>T</small>)|≤1, ∀iĐẳng thức xảy ra khii= 0nên

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

max|1 − <small>i</small>

λ AA( <small>T</small>)| = 1Mà biến đổi (3) vẫn đúng nên ta có∥E − AX<small>0</small>∥ = 1.Vậy với cách chọn X<small>0</small>= <small>AT</small>

<small>∥ ∥A2</small>thì nếu ma trậnAkhơng khả nghịch, ta ln có∥E−AX<small>0</small>∥ = 1.Mà ngược lại, nếu ma trậnAkhả nghịch thì lại có∥E − AX<small>0</small>∥ < 1 nên dãy (X<small>k</small>)sẽ luôn hội tụ.

∥A<small>−1</small>∥ − ∥A<small>−1</small>∥q<small>t</small>≤∥A<small>−1</small>∥ − ∥A<small>−1</small>∥∥G<small>0</small>∥<small>t</small>

≤∥A<small>−1</small>∥ − ∥A<small>−1</small>G<small>t0</small>∥≤∥A<small>−1</small>− A<small>−1</small>G<small>t</small>

<small>0</small>∥= ∥A<small>−1</small>(E − G<small>t</small>

<small>0</small>)∥= ∥X<small>0</small>(E + G<small>0</small>+ G<small>2</small>+...+G<small>t</small>

<small>0</small>)∥= ∥X<small>0</small>∥∥E +G<small>0</small>+G<small>2</small>+ ... + G<small>t</small>

<small>0</small>∥≤∥X<small>0</small>∥(∥E∥ + G∥ <small>0</small>∥ + G∥ <small>2</small> ∥ +...+∥G<small>t</small>

<small>0</small>∥)≤∥X<small>0</small>∥(1 +q+ q<small>2</small>+ ... + q<small>t</small>)

=^∥X⁰^{∥(1 − q}

<small>t+1</small>)1 − qCho t →∞ ta được ∥A<small>−1</small>∥≤<small>∥X0∥</small>

<small>1−q</small>. Kết hợp với (1) ta có cơng thức sai số∥A<small>−1</small>− X<small>k</small>∥≤^∥X⁰^∥q

<small>2k</small>1 − q

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

q←∥E − AX<small>0</small>∥q<small>2k</small>

← qerror←<small>ε×(1−q)</small>

Bước 2: Nếu q = 1, thông báo ma trận không khả nghịch và trả về ma trận NaNBước 3: Whileq<small>2k</small> :

≥ errorX← X(2E − AX)q<small>2k</small> q

← (<small>2k</small>)<small>2</small>

Bước 4: Trả về ma trận X<small>0</small>

Chươngtrìnhnewton_inverse(A, ,n ε)Input: Ma trận , kích cỡA n, sai số εOutput: Ma trậnX<small>∗</small>xấp xỉ củaA<small>−1</small>

Bước 1: Chương trình tự chọn xấp xỉ đầu X<small>0</small>= <small>AT</small>

<small>∥ ∥A2</small>Bước 2: Trả về newton_iter(A, ,n ε, X<small>0</small>)

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

3 Các phương pháp tìm gần đúng nghịch đảo của ma trậnchéo trội

<small>i=j</small> a_ij∥ < a<small>jj</small>∥ (chéo trội cột)

Ý tưởng của các phương pháp này là áp dụng các phương pháp giải gần đúng hệ vng đểgiải hệ phương trình AX = E trong đóAlà ma trận chéo trội. Các phương pháp sẽ được trìnhbày ở đây là:

Phương pháp lặp JacobiPhương pháp lặp Gauss-Seidel

3.2 Phương pháp lặp Jacobi

3.2.1 Lí thuyếtĐặt T = diag a{<small>−1</small>

<small>11</small>, a<small>−1</small>

<small>22</small>, ..., a<small>−1</small>}, B = E − T A, B<small>1</small>= E − ATCông thức lặp:

X<small>k+1</small>=BX<small>k</small>+TCông thức sai số:

– Trường hợp chéo trội hàng: Với ∥ ∥B<small>∞</small>≤ q < 1∥X<small>k</small>− X<small>∗</small>∥

1 − q^∥X<small>k</small>− X<small>k−1</small>∥<small>1</small>

∥X_k− X<small>∗</small>∥ ≤ λ ^q^k

1 − q^∥^X<small>1</small>−^X<small>0 1</small>^∥

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

3.2.2 Thuật toánHàmcheck_dom(A, n)Input: Ma trận , kích cỡA nOutput: Trả về trạng thái trội 1, −1, 0

tương ứng với ma trậnAchéo trội hàng, chéo trội cột hoặc không chéo trộiBước 1: K ←|diag(A)|

sumRowlà dãy tổng trị tuyệt đối các phần tử trên các hàng củaAtrừ các phần tử trongKsumCollà dãy tổng trị tuyệt đối các phần tử trên các cột củaAtrừ các phần tử trongKBước 2:

Nếu K[i] > sumRow i], ∀i = 1, n, hàm trả về giá trị 1[Nếu K[i] > sumCol i], ∀i = 1, n, hàm trả về giá trị -1[Nếu cả hai trường hợp trên không xảy ra, hàm trả về giá trị 0

Hàmget_norm(A, domStatus)

Input: Ma trận , trạng thái trộiA domStatusOutput: Chuẩn của A theo trạng thái trội

Nếu domStatus = 1, trả về∥ ∥A<small>∞</small>. Nếu không, trả về∥A∥<small>1</small>.

Hàmget_lambda(A, domStatus)

Input: Ma trận , trạng thái trộiA domStatusOutput: Trả về λ = 1 nếu A chéo trội hàng, λ =<small>max a∥ii∥</small>

<small>min a∥ii∥</small>nếu A chéo trội cộtNếu domStatus = 1, trả về giá trị 1

Nếu khơng, tính K ←|diag(A)|, trả về<small>max(Kmin(K)</small>

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

Góiđánhgiátiênnghiệmpredecessor_iter( <small>0</small>,B, T domStatus,, λ, q ε, )Input: Ma trận X<small>0</small>, , ,B T domStatus, λ, hệ số q, sai số εOutput: Ma trậnX<small>∗</small>xấp xỉ củaA<small>−1</small>

Bước 1: Tính các giá trị

norm← get_norm((BX<small>0</small>+ T ) −X<small>0</small>,domStatus)X← X<small>0</small>

q<small>k</small>← 1error←<small>ε×(1 q)−</small>

<small>λ norm×</small>

Bước 2: Whileq<small>k</small>> error:X← BX+Tq<small>k</small>←q<small>k</small>× qBước 3: Trả về X

Góiđánhgiáhậunghiệmsuccessor_iter(X<small>0</small>,B, T domStatus,, λ, q ε, )Input: Ma trận X<small>0</small>,B, T domStatus, λ, hệ số q, sai số ε,Output: Ma trậnX<small>∗</small>xấp xỉ củaA<small>−1</small>

Bước 1: Tính các giá trịoldX← X<small>0</small>

newX← BX<small>0</small>+Terror←<small>ε(1−q)</small>

Bước 2: While get_norm(newX− oldX, domStatus) > error:oldX← newX

newX← B × oldX+TBước 3: Trả về newX

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

Chươngtrìnhjacobi_inverse(A, ,n ε, mode)

Input: Ma trận , kích cỡA n, sai số ε, chế độ đánh giámode

Output: Ma trậnX<small>∗</small>xấp xỉ củaA<small>−1</small>theo chế độ đánh giá tiên nghiệm nếumode= 1.Nếu không, thực hiện theo chế độ đánh giá hậu nghiệm.

Bước 1: domStatus ← check_dom(A, n)

Nếu domStatus = 0, thông báoAkhông chéo trội và dừng chương trìnhBước 2: Tính các giá trị

E←ma trận đơn vị cỡ nT← diag{a<small>−1</small>

<small>11</small>, a<small>−122</small>, ..., a<small>−1</small>}B← E − T A

λ← get_lambda(A, domStatus)q← get_q(B, E, T , A, domStatus)Bước 3: Chọn chế độ đánh giá

Nếu mode = 1, trả về predecessor_iter(A,B, T domStatus,, λ, q ε, )Nếu không, trả về successor_iter(A, ,B T, domStatus λ, , q, ε)

3.3 Phương pháp lặp Gauss-Seidel

3.3.1 Lí thuyếtĐặt T = diag a{<small>−1</small>

<small>11</small>, a<small>−1</small>

<small>22</small>, ..., a<small>−1</small>}, B = E − T A, B<small>1</small>= E − ATKí hiệuX<small>(i)</small>là dịng thứ của ma trậni X

Cơng thức lặp:X<small>( )i</small>

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

– Trường hợp chéo trội cột: Đặt

q= max

P_{i j=1}|b<small>1ji</small>|

1 −P_{n j=i+1}|b<small>1ji</small>|^≤∥B<small>1</small>∥<small>1</small><1S= max

⇒Công thức sai số là:∥X<small>k</small>− X<small>∗</small>∥ ≤ ^λq

Input: Ma trận , kích cỡ , trạng thái trộiB n domStatusOutput: Hệ số q

Bước 1: q ← 0Bước 2:

NếudomStatus= 1:For i from 1 to :n

<small>j=i</small>|b<small>ij</small>|, q<small>2</small>←^P<small>i−1j=1</small>|b<small>ij</small>|q← max(q, <small>q1</small>

<small>1−q2</small>)Nếu không:

For i from 1 to :nq₁←^P<small>i</small>

<small>=1</small>|b<small>ji</small>|, q<small>2</small>←^P<small>n j=i+1</small>|b<small>ji</small>|q← max(q, <small>q1</small>

<small>1−q2</small>)Bước 3:Trả về q

</div><span class="text_page_counter">Trang 13</span><div class="page_container" data-page="13">

Hàmget_S(B<small>1</small>, n)Input: Ma trậnB<small>1</small>, kích cỡnOutput: Hệ số SBước 1: S ← 0Bước 2: For i from 1 to :n

tmp←^P<small>nj=i+1</small>|b<small>1ji</small>|S← max(S, tmp)Bước 3: Trả về S

Hàmnext_iter(oldX, , ,B T n)Input: Ma trậnoldX, B, T, kích cỡnOutput: Ma trận lặp tiếp theo newXBước 1: For i from 1 to :n

newX^{( )}ⁱ

<small>k+1</small>+P_(k)<small>j=i+1</small>b_ijoldX<small>(j)k</small> + T<small>(i)</small>

Bước 2: Trả về newX

Góiđánhgiátiênnghiệmpredecessor_iter(X<small>0</small>, B, T , ,n domStatus λ, , S, q, ε)Input: Ma trận X<small>0</small>, ,B T, kích cỡ n, domStatus, λ, hệ số S, q, sai số εOutput: Ma trậnX<small>∗</small>xấp xỉ củaA<small>−1</small>

Bước 1: Tính các giá trịq<small>k</small>← 1

X← X<small>0</small>

X<small>1</small>← next_iter(X<small>0</small>, B, T , n)norm← get_norm(X<small>1</small>−X<small>0</small>,domStatus)error←<small>ε(1−q)(1−S)</small>

Bước 2: Whileq<small>k</small>> error:

X← next_iter(X, B, T , n)q<small>k</small>←q<small>k</small>× q

Bước 3: Trả về X

</div><span class="text_page_counter">Trang 14</span><div class="page_container" data-page="14">

Góiđánhgiáhậunghiệmsuccessor_iter(X<small>0</small>, B, T , n, , , S, q, )Input: Ma trận X<small>0</small>, ,B T, kích cỡ n, domStatus, λ, hệ số S, q, sai số εOutput: Ma trậnX<small>∗</small>xấp xỉ củaA<small>−1</small>

Bước 1: oldX ← X<small>0</small>; newX ← next_iter(X<small>0</small>, B, T , n); error ←<small>ε(1−q)(1−S)λ norm×</small>

Bước 2: While get_norm(newX− oldX, domStatus) > error:oldX← newX

newX← next_iter(newX, B, T , n)Bước 3: Trả về newX

Chươngtrìnhgauss_seidel_inverse(A, n, ,ε mode)

Input: Ma trận , kích cỡA n, sai số ε, chế độ đánh giámode

Output: Ma trậnX<small>∗</small>xấp xỉ củaA<small>−1</small>theo chế độ đánh giá tiên nghiệm nếumode= 1.Nếu không, thực hiện theo chế độ đánh giá hậu nghiệm.

Bước 1: domStatus ← check_dom(A, n)

Nếu domStatus = 0, thơng báoAkhơng chéo trội và dừng chương trìnhBước 2: Tính các giá trị

E←ma trận đơn vị cỡ nT← diag{a<small>−1</small>

<small>11</small>, a<small>−122</small>, ..., a<small>−1</small>}B← E − T A

λ← get_lambda(A, domStatus)NếudomStatus= 1:

S← 0

q← get_q(B, n, domStatus)Nếu không:

B<small>1</small>← E − ATS← get_S(B<small>1</small>, n)q← get_q(B<small>1</small>, n, domStatus)Bước 3: Chọn chế độ đánh giá

Nếu mode = 1, trả về predecessor_iter(A,B, T n domStatus,, , λ, ,S q ε, )Nếu không, trả về successor_iter(A, ,B T, n domStatus λ, , , S, q, )ε

</div><span class="text_page_counter">Trang 16</span><div class="page_container" data-page="16">

Gauss-4.2 Ví dụ 2 (Ma trận chéo trội hàng)

</div><span class="text_page_counter">Trang 19</span><div class="page_container" data-page="19">

4.3 Ví dụ 3 (Ma trận chéo trội cột gần suy biến)

Tìm nghịch đảo ma trận sau:

2 7 1. 0 0001.0 4 0 001.Vẫn với sai số là10<small>−10</small>, ta thu được các kết quả sau:

</div><span class="text_page_counter">Trang 21</span><div class="page_container" data-page="21">

4.4 Ví dụ 4 (Ma trận chéo trội cỡ lớn)

</div><span class="text_page_counter">Trang 27</span><div class="page_container" data-page="27">

Phương pháp Gauss-Seidel hội tụ nhanh hơn phương pháp Jacobi. Điều này là hoàn toànphù hợp với lí thuyết do phương pháp lặp Gauss-Seidel là một cải tiến của phương pháplặp Jacobi.

5.2 Ưu, nhược diểm của các phương pháp

5.2.1 Ưu điểm

Các phương pháp giải gần đúng ma trận nghịch đảo đều giúp ta kiểm soát và cải thiệnsai số tính tốn sau một số lần lặp nhất định, đây là điều mà các phương pháp giải đúngkhông làm được.

Với phương pháp Newton, công thức lặp hội tụ rất nhanh và không yêu cầu nhiều với matrận đầu vào, thuật toán lại đơn giản, dễ nhớ.

</div><span class="text_page_counter">Trang 28</span><div class="page_container" data-page="28">

Bước 1: Nhập sai số vào dòng đầu của file input.txt.

Bước 2: Nhập ma trận cần tìm nghịch đảo vào các dòng sau, lưu ý cần phân tách các giátrị trong cùng một hàng của ma trận bởi dấu cách và xuống dòng khi sang hàng tiếp theo.Bước 3: Chạy chương trình newton.py, chương trình sẽ đưa ra số lần lặp, ma trận nghịchđảo và kết quả kiểm tra nhân ngược. Trường hợp ma trận không khả nghịch, chương trìnhsẽ báo lỗi và đưa ra ma trận NaN.

6.2 Phương pháp Jacobi

Đặt các file sau trong cùng một thư mục:Chương trình chính: jacobi.pyFile dữ liệu đầu vào: input.txtCác bước sử dụng:

Bước 1: Nhập chế độ đánh giá vào dòng đầu của file input.txt ( Nhập "1" tương ứng vớichế độ đánh giá tiên nghiệm, nếu khơng chương trình sẽ chạy theo chế độ đánh giá hậunghiệm)

Bước 2: Nhập sai số vào dòng thứ hai của file input.txt

Bước 3: Nhập ma trận cần tìm nghịch đảo vào các dịng sau, lưu ý cần phân tách các giátrị trong cùng một hàng của ma trận bởi dấu cách và xuống dòng khi sang hàng tiếp theo.Bước 4: Chạy chương trình jacobi.py, chương trình sẽ đưa ra số lần lặp, ma trận nghịchđảo và kết quả kiểm tra nhân ngược. Trường hợp ma trận khơng chéo trội, chương trìnhsẽ báo lỗi và đưa ra ma trận NaN.

</div><span class="text_page_counter">Trang 29</span><div class="page_container" data-page="29">

6.3 Phương pháp Gauss-Seidel

Đặt các file sau trong cùng một thư mục:Chương trình chính: gauss_seidel.pyFile dữ liệu đầu vào: input.txtCác bước sử dụng:

Bước 1: Nhập chế độ đánh giá vào dòng đầu của file input.txt ( Nhập "1" tương ứng vớichế độ đánh giá tiên nghiệm, nếu khơng chương trình sẽ chạy theo chế độ đánh giá hậunghiệm)

Bước 2: Nhập sai số vào dòng thứ hai của file input.txt

Bước 3: Nhập ma trận cần tìm nghịch đảo vào các dịng sau, lưu ý cần phân tách các giátrị trong cùng một hàng của ma trận bởi dấu cách và xuống dòng khi sang hàng tiếp theo.Bước 4: Chạy chương trình jacobi.py, chương trình sẽ đưa ra số lần lặp, ma trận nghịchđảo và kết quả kiểm tra nhân ngược. Trường hợp ma trận khơng chéo trội, chương trìnhsẽ báo lỗi và đưa ra ma trận NaN.

Tài liệu

[1] J. Douglas (Douglas Faires) Faires, Richard L.Burden - Numericalmethods (2003)[2] Lê Trọng Vinh -Giáotrìnhgiảitíchsố (2007)

[3] Phạm Kỳ Anh -Giảitíchsố (1996)

[4] Jaan Kiusalaas - NumericalMethodsinEngineeringwithPython (2010)

[5] Adi Ben-Israel - ANoteonanIteractiveMethodforGeneralizedInversionofMatrices (1966)[6] Samuel Daniel Conte - Elementarynumericalanalysis,analgorithmicapproach (1980)

</div>