Báo cáo bài tập lớn Đại số tuyến tính cơ sở lý thuyết của phân tích a = lu và phân tích pa = plu

Với chủ đề trên, chúng em thực hiện dựa vào những kiến thức được học từ giảng viên, trong giáo trình Đại số tuyến tính và một số tài liệu tham khảo từ bên ngoài.. Cơsởlýthuyếtcủaphântích

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH

TRƯỜNG ĐẠI HỌC BÁCH KHOA

BỘ MÔN TOÁN ỨNG DỤNG

BÁO CÁO BÀI TẬP LỚN ĐẠI SỐ TUYẾN TÍNH

ĐỀ TÀI SỐ 2 Giảng viên hướng dẫn: Bùi Anh Tuấn

Lớp: L05

Nhóm: N07

Thành viên:

Nguyễn Hữu Tài 2011998 Đoàn Thụy Minh Uyên 2012399 Phạm Thiên Nhi 2011764 Nguyễn Thái Mai Thùy 2014665 Nguyễn Nhật Khang 2011366 Quách Khải Thành 2014507

Lê Thị Quỳnh Nhi 2014015

Hồ Chí Minh,5/2021

Báo cáo bài tập lớn nhóm N7

1

Danh sách nhóm – Nội dung đề tài

Danh sách nhóm:

Nội dung đề tài:

1 Nêu cơ sở lý thuyết của phân tích A = LU và phân tích PA =PLU

2 Viết chương trình dùng để phân tích A =LU

3 Tìm các ứng dụng của phân tích A =LU

Lời nói đầu

Đại số tuyến tính là môn toán cao cấp đang được nhiều trường đại học áp dụng giảng dạytrongđócótrườngĐạihọcBáchKhoa-ĐạihọcquốcgiaTPHồChíMinh.Đâylà môn học rất hay và tương đối phức tạp với khối lượng kiến thức đồ sộ cùng những phương pháp tính toán và tư duy hoàn toàn mớilạ

Nhận thức được rằng ma trận và các bài toán liên quan đến ma trận là nội dung vô cùng quan trọng trong chương trình Do đó ở bài báo cáo lần này, chúng em đã cùng nhau tìm hiểu về phép phân tích A=LU, phân tích PA=PLU cùng với những kiến thức liên quan tới chủ đề

Với chủ đề trên, chúng em thực hiện dựa vào những kiến thức được học từ giảng viên, trong giáo trình Đại số tuyến tính và một số tài liệu tham khảo từ bên ngoài

Hoàn thành bài báo cáo này không những giúp chúng em có cái nhìn tổng quan hơn về một phần kiến thức trong môn học mà nó còn giúp rèn luyện thêm những kỹ năng về làm việc nhóm, sử dụng phần mềm Matlab,

Trong quá trình thực hiện bài báo cáo, có thể còn tồn tại những sai sót, nhóm chúng

em mong rằng sẽ nhận được sự đánh giá và góp ý quý báu từ thầy

MỤC LỤC

Danh sách nhóm – Nội dung đềtài 1

Lờinóiđầu 2

I Cơ sở lý thuyết của phân tích A = LU và phân tích PA=PLU 4

1 Phân tích A=LU 4

2 Phân tích PA=PLU 5

II Chương trình để phântíchA=LU 7

1 Sơ đồthuậttoán: 7

2 Đoạn code phân tích thuậttoánA=LU 8

3 Ví dụminhhọa 8

III Ứngdụng 10

1 Giải hệ phương trìnhtuyếntính 10

2 Tính ma trậnnghịchđảo 11

3 Tínhđịnhthức 13

Lờikết 16

3 3 1

(

.

Ⅰ CơsởlýthuyếtcủaphântíchA=LUvàphântíchPA=PLUⅼ.PhântíchA

=LU

Trong đại số tuyến tính, phân tích A= LU là phương pháp phân tích ma trận thành tích của một ma trận tam giác dưới và một ma trận tam giác trên có cùng kích thước với ma trận đã cho Phép phân tích này thường được dùng trong giải tích số

để giải hệ phương trình tuyến tính hoặc tính định thức của ma trận

Trong đó :

A là một ma trận bất kỳ

L là ma trận tam giác dưới (L là viết tắt của Lower trong Lower Triangle)

U là ma trận tam giác trên (U là viết tắt của Upper trong Upper Triangle)

Ví dụ với ma trận3 × 3:

a11 a12 a13 l11 0 0 u11 u12 u13 (a21 a22 a23)=(l21 l21 0)×(0 u22 u23)

a31 a32 a33 l31 l32 l33 0 0 u33 Phép phân tích ma trận A = LU này rất đơn giản, đầu tiên ta thực hiện các phép biến đổi trên dòng để đưa A thành một ma trận bậc thang Lúc đó, ma trận bậc thang chính là U Vận dụng ma trận A và U vừa tìm được để tìm ma trận L

Để hiểu rõ hơn, chúng ta sẽ lấy một ma trận3 × 3làm ví dụ:

1 2 −1 A=(2 5 −3)

Đưa A về ma trận bậc thang

ℎ 2 →ℎ 2 −2ℎ

1 ℎ → ℎ

−3ℎ

→

𝐴 →

1 2 −1

0 1 −1

ℎ 3 →ℎ 3 −ℎ

2

)→

1 2 −1 (0 1 −1)

Ma trận bậc thang vừa tìm được chính là U (ma trận tam giác trên) Để tìm L thỏa điều kiện A = LU ta nhân hai vế cho U-1:

1 2 −1

1 2 −1− 1 1 0 0

Vậy ta có phép phân tích ma trận A = LU như sau :

2 Phân tích PA = PLU :

Tổng quát hơn với mọi ma trận vuông khả nghịch A – bất kể có vuông hay không ta đều có phân tích LUP đó là phân tích có dạng

PA=LU Trong đó:

- L,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 như phép phân tích A =LU

- P là một ma trận hoán vị (Pchỉ 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)

Để làm rõ hơn phép phân tích này, ta xét ma trận sau:

A=( 02 23 24)

Đầu tiên ta đổi chỗ hàng đầu và hàng cuối của ma trận A cho nhau để được phần tử hàng đầu tiên, cột đầu tiên khác 0, tức là ta chọn ma trận P, với:

1 0 0 ℎ1↔ℎ

3

0 0 1

0 0 1

1 0 0

Từ đó ta thu được ma trận PA (ma trận hoán vị của A)

−1 −1 1

Lập lại quy trình như trong ví dụ trên đối với ma trận PA

Biến đổi sơ cấp theo hàng đưa PA về ma trận bậc thang:

h2→h2+2h1 −1 −1

1 h3→h3−2h2

VậytacómatrậnU=( −1 −10 1 16 )

Bây giờ ta chỉ cần tìm ma trận L sao cho PA = LU

Để tìm L, ta có thể dùng phép tính L = PAU-1

−1 −1

Vậy ta có phép phân tích ma trận PA = LU :

−1 −1

Một ma trận vuông A cấp n suy biến có rank(A) < n cũng có thể có phân tích LUP, tuy nhiên ta không xét ở đây

II Chương trình để phân tích A=LU

Trong đại số tuyến tính, phép phân tích A=LU là một trong những phép biến đổi cốt lõi và thường được thực hiện bởi nhiều loại chương trình khác nhau.Tuy nhiên, nhóm chúng em đã lựa chọn Matlab để thực hiện đề tài bởi sự tiện lợi và nhanh chóng của phần mềm này

1 Sơ đồ thuậttoán:

2 Đoạn code phân tích thuật toánA=LU

3.Ví dụ minhhọa

1 2 −1

Vídụ1:PhântíchA=LUchomatrậnA=(2 5 −3)

2 3 5 4

1 1 2 1

Vídụ2:PhântíchA=LUchomatrậnA=( 2 7 6)3

4 5 9 3

III Ứng dụng

1 Giải hệ phương trình tuyến tính:

1.1 Phươngpháp

Cho phương trình:

Ax = LUx = b

Ta muốn giải phương trình này vớiAvàbcho trước Khi đó nghiệm của

phương trình được tính qua 2 bước:

Bước1:giảiphươngtrìnhLy=bđểtìmy

Bước2:giảiphươngtrìnhUx=yđểtìmx

Nhận xét rằng trong cả hai bước ta chỉ phải làm việc với các ma trận tam giác.Các phương trình này có thể được giải đơn giản bằng các phép thế thay vì

sử dụng phép khử Gauss.Do đó phân tích LU chỉ tỏ ra hiệu quả khi ta phải giải

phương trình trên nhiều lần với các giá trị khác nhau củab; khi đó chỉ cần tính

phân tích LU của A một lần và giải các ma trận tam giác với các giá trị khác

nhau củab, thay vì phải sử dụng nhiều lần các phép khử Gauss.

1.2 Ví dụ:

GiảihệphươngtrinhAx=b,vớiAlàmatrậnvừaphântíchởvídụ2bằng Matlab và𝑏=

(2,1,−1,3)𝑇

1 1 2

Trước tiên ta giải hệ LY = b

Vì ma trận L là tam giác dưới nên ta giải từ trên xuống:

1 0 0 02 (23 −1 1 0−11 0 0|1)→{

𝑦1= 2

𝑦2= −3

𝑦3= −10

𝑦4= −2

Tiếp theo ta giải phương trình Ux=Y, vớiY = (2, −3, −10, −2)T

37

𝑥1=

3 7

𝑥2= 3

(

0 0 0 −3−2

𝑥3= −

3

2 {𝑥4= 3

2 Tính ma trận nghịchđảo

Khi giải hệ phương trình tuyến tính,bđược xem là vector có chiều dài bằng số dòng của A Nếu thay vectorbbằng ma trận B kích thước ×𝑛 × 𝑝 𝑝, ta sẽ phải tìm ma trận X, với:

𝐴 →𝑋=𝐿𝑈𝑋=𝐵

Có thể sử dụng phương pháp giải hệ phương trình tuyến tính để giải cho mỗi cột

của ma trậnX Với giả sử rằngBlà ma trận đơn vị với kích thướcnthìXkhi đó là nghịch đảo củaA.

2.1 Phương pháp:

- B1: Phân hủyA=LU

- B2: Giải hệ phương trình tuyếntính:

Ax=B ↔ Ax=LUx=B

{Ly = B(1)Ux = y(2)

Giải hệ (1) tìm y Giải hệ (2) tìm x

- B3: Suy ra ma trận nghịch đảo

2.2 Ví dụ:

1 2 −1 TìmmatrậnnghịchđảocủamatrậnA= (2 5 −3)

3 7 −5

1 2 −1 ℎ2−2ℎ1; ℎ3−3ℎ1 1 2 −1 ℎ3−ℎ2 1 2 −1

1 2 −1

Vậy:U=(0 1 −1)

0 0 −1

TìmLsao choA=LU

L=(l21 1 0) =(2 1 0)

l31 l32 1 3 1 1

1 2 −1 1 0 0

→ 𝐴 →=𝐿𝑈=(0 1 −1)(2 1 0)

0 0 −1 3 1 1

Giải hệ phương trình (1)

(2 1 0|0 1 0)→ 𝑦=( −2 1 0)

Giải hệ phương trình (2)

(0 1 −1|−2 1 0)→x=( −1 2 −1)

0 0 −1 −1 −1

4 −3 1 Vậymatrậnnghịchđảo𝐴 →−1=(−1 2 −1)

3 Tính địnhthức

3.1 Phươngpháp

Các ma trận L và U có thể được dùng để tínhđịnh thứccủa ma trận A rất hiệu quả vì det(A) = det(L).det(U) và định thức của các ma trận tam giác đơn giản là tích các phần tử trên đường chéo của nó

Đặc biệt, nếu L là ma trận tam giác đơn vị thì:

𝑛 × 𝑝

det(𝐴 →)= det(𝐿)det(𝑈)= 1 det(𝑈)=∏𝑢𝑖𝑖

𝑖=1 Tương tự với phân tích LUP Định thức của ma trận hoán vị P là(−1)𝑆, với S là phép hoán đổi trong phép phân tích

3.2 Vídụ:

ChomatrậnA=[6 13 5 19] Tínhdet(A)

2 19 10 23

4 10 11 31

Sử dụng phân tích A=LU, ta được :

L =[3 1 0 0] và U =[0 4 2 4]

det(L)= 1 × 1 × 1 × 1 = 1 det(U)= 2 × 4 × 1 × 3 = 24 Vậydet(A)= det(L)det(U)= 1 × 24 = 24

Qua đây ta có thể thấy rằng việc sử dụng phân tích A=LU đặc biệt hiệu quả và nhanh chóng trong tính định thức của một ma trận khi nó là ma trận vuông từ cấp 4 trở lên

Danh mục tài liệu tham khảo

1 Đặng Văn Vinh, Giáo trình Đại số tuyến tính, NXB Đại học Quốc gia Thành phố

Hồ ChíMinh

2 Phạm Thị Ngọc Yên, Cơ sở Matlab và ứng dụng, NXB Khoa học và KĩThuật

3 Wikipedia – Bách khoa toàn thư mở, Phân tích LU

(https://vi.wikipedia.org/wiki/Ph%C3%A2n_t%C3%ADch_LU)

4 Course Hero, Hệ PTTT - Phân tích LU và Ma trận nghịch đảo

(https://www.coursehero.com/profile/diennguyenduy1311999/)

(https://rootonchair.blogspot.com/2019/06/phep-phan-tich-ma-tran-alu.html)

Lời kết

Trong suốt quá trình thực hiện báo cáo trên, nhóm chúng em đã nhận được rất

nhiều sự quan tâm và ủng hộ, giúp đỡ tận tình của thầy/cô

Qua bài báo cáo chúng em đã biết như thế nào là phân tích A = LU và phân tích

PA = PLU Không những thế, nhóm còn hiểu rõ bản chất của chương trình dùng để phân tích A = LU cũng như biết các ứng dụng đặc biệt của phép phân tíchnày

Cuối lời, chúng em xin một lần nữa gửi lời biết ơn sâu sắc các thầy cô đã dành thời gian chỉ dẫn cho nhóm Đây chính là niềm tin, nguồn động lực to lớn để nhóm có được bài báo cáo ngày hôm nay

Xin chân thành cảm ơn !