- Trang Chủ
- Toán học
- Phân rã ma trận LU và phương pháp lập trình giải mô hình tuyến tính trong phân tích kinh tế
Xem mẫu
- TẠP CHÍ KHOA HỌC ĐẠI HỌC VĂN LANG Nguyễn Văn Lộc
PHÂN RÃ MA TRẬN LU VÀ PHƯƠNG PHÁP LẬP TRÌNH
GIẢI MÔ HÌNH TUYẾN TÍNH TRONG PHÂN TÍCH KINH TẾ
DISCUSSION AND PROGRAMMING METHODS IN ECONOMIC ANALYSIS
NGUYỄN VĂN LỘC
TÓM TẮT: Bài viết trình bày cách ứng dụng phương pháp sử dụng phân rã ma trận LU và phương
pháp lập trình để giải hệ phương trình có hàng trăm phương trình tuyến tính trong phân tích kinh
tế mà các phương pháp thông thường trong chương trình toán cao cấp khó giải được.
Từ khóa: lập trình; phân rã ma trận; hệ phương trình tuyến tính.
ABSTRACT: The paper presents the method of using LU matrix decomposition and programming
method to solve the system of linear equations in economic analysis.
Key words: matrix decomposition; system of linear equations.
1. ĐẶT VẤN ĐỀ Phân rã ma trận là cách giảm ma trận thành
Trong một nền kinh tế có hàng trăm sản các thành phần cấu thành của nó. Phân rã ma
phẩm, mỗi sản phẩm có hai phương trình cung và trận là một cách tiếp cận có thể đơn giản hóa các
phương cầu nhằm xác định sản lượng cân bằng. tính toán ma trận phức tạp vì được thực hiện trên
Để xác định tất cả các sản lượng cân bằng của ma trận phân tách thay vì trên chính ma trận gốc.
nền kinh tế, phục vụ cho việc nghiên cứu sản Phân rã ma trận tương tự như phân tách (factor)
phẩm tiềm năng Yp, ta phải giải một hệ có đến các số: ví dụ như factor 10 thành 2 5. Giống
hằng trăm phương trình tuyến tính. Các phương như phân tích các giá trị thực, có nhiều cách để
pháp toán học như: Phương pháp ma trận nghịch phân tách một ma trận và một loạt các kỹ thuật
đảo; Phương pháp Cramer; Phương pháp Gauss... phân rã ma trận khác nhau. Trong bài viết này,
các phương pháp lập trình như: Hàm solve( ); chúng tôi trình bày phương pháp phân rã ma trận
hàm inv( ); hàm pinv( )… là không thể giải. Dùng đơn giản, được sử dụng rộng rãi là phân rã ma
phân rã ma trận kết hợp với phương pháp lập trận LU. Phép phân rã LU - Decomposition
trình để chuyển việc giải các hệ tuyến tính “phức dùng cho ma trận vuông, nó phân tách ma trận
tạp” về giải các hệ tuyến tính đơn giản hơn là việc thành các thành phần L và U.
làm rất cần thiết trong nghiên cứu kinh tế. Trong Công thức: A = L.U hoặc A = LU
bài viết này, chúng tôi minh họa phương pháp Với A là ma trận vuông muốn phân rã; L
trên thông qua cách sử dụng phân rã ma trận LU là ma trận tam giác dưới; U là ma trận tam giác
và phương pháp lập trình để giải các hệ phương trên. Điều kiện áp dụng phân rã LU: A khả
trình tuyến tính trong phân tích kinh tế. nghịch, A 0, k n
2. NỘI DUNG
2.1.2. Phương pháp phân rã ma trận
2.1. Phân rã ma trận A=LU (LU - Decomposition) Biểu diễn A dưới dạng tích hai ma trận
trong Toán học đồng cấp với A: L là ma trận tam giác trên với
2.1.1. Phân rã ma trận (Matrix Decomposition) các phần tử trên đường chéo chính bằng 1, các
PGS.TS. Trường Đại học Văn Lang, loc.nv@vlu.edu.vn, Mã số: TCKH27-07-2021
88
- TẠP CHÍ KHOA HỌC ĐẠI HỌC VĂN LANG Số 27, Tháng 5 - 2021
phần tử đối diện “phần 0” cần xác định và U là P là ma trận hoán vị (permutation matrix).
ma trận tam giác dưới với các phần tử trên Mỗi dòng, mỗi cột có một hệ số bằng 1, tất cả
đường chéo chính và các phần tử đối diện các hệ số khác bằng 0. Hoán vị các dòng của I
“phần 0” cần xác định; hay các cột chuẩn.
Thực hiện phép nhân LU; + Đồng nhất Tính chất của ma trận P:
hóa các phần tử hai ma trận cùng cấp LU và ma T T 1 T
a ). P 1; b).P.P P .P I ; c ).P P
trận A, ta được hệ đẳng thức về sự bằng nhau
3 2 5 9
của các phần tử tương ứng của hai ma trận.
Từ hệ đẳng thức được xác định, ta tìm Ví dụ: Cho ma trận A 1 7 5 7
5 10 5 3
được các phần tử của L và U. 6 9 7 2
Ví dụ: Phân rã LU - Decomposition ma trận: a) Phân tích ma trận A thành các thành
1 2 4 1 0 0 phần P, L, U. In ra kết quả.
A 3 8 14 LU ; L L21 1 0 b) Tái tạo (phục hồi) ma trận B từ các
2 6 13
L31 L32 1 thành phần P, L, U.
U11 U12 U13 Giải:
&U 0 U 22 U 23 import numpy
0 0 U 33 Entrée[1]: import scipy
from scipy.linalg import lu
Giải: Ta có:
A = numpy.array([[3., 2. , 5., 9.], [1.,
U11 U12 U13
Entrée[2]: 7., 5., 7.], [5., 10., 5., 3.], [6., 9., 7.,
LU L21U11 L21U12 U 22 L21U13 U 23
2.]])
L31U11 L31U12 L32U 22 L31U13 L32U 23 U 33
Entrée[3]: P, L, U = lu(A)
1 2 4 Entrée[4]: P
3 8 14 (1) array([[0., 0., 1., 0.], [0., 1., 0., 0.],
2 6 13 Out [4]:
[0., 0., 0., 1.], [1., 0., 0., 0.]]
Đồng nhất hóa các phần tử tương ứng của Entrée[5]: L
hai ma trận từ (1), ta có: array([[ 1., 0., 0., 0.], [0.16666667, 1., 0.,
U11 1; U12 2; U13 4. Out [5]: 0.], [0.5, -0.45454545, 1., 0.], [0.83333333,
0.45454545, -0.79439252, 1.]])
L21 3; U 22 2; U 23 2; L31 2; L32 1; U 33 3.
Entrée[6]: U
1 2 4 1 0 0 1 2 4 array([[ 6., 9., 7., 2.], [ 0., 5.5 , 3.83333333,
A 3 8 14 3 1 0 0 2 2
2 6 13 2 1 1 0 0 3 Out [6]: 6.66666667], [0., 0., 3.24242424,
11.03030303], [0., 0., 0., 7.06542056]])
2.2. Phân rã ma trận PA = LU bằng phương B = P.dot(L).dot(U)
Entrée[7]:
pháp lập trình B
Việc phân rã LU được thực hiện bằng cách array([[ 3., 2., 5., 9.],
sử dụng một quá trình số lặp và có thể thất bại Out [7]:
[ 1., 7., 5., 7.],
đối với các ma trận không thể phân tích. Do [ 5., 10., 5., 3.],
vậy, để phân tích ma trận ổn định về mặt số, ta [ 6., 9., 7., 2.]])
dùng phân tích LU xoay vòng một phần (Partial 2.3. Ứng dụng phân rã ma trận PA = LU và
Pivoting) [1, tr.6]. phương pháp lập trình giải hệ phương trình
Công thức: PA = LU tuyến tính
Với mọi ma trận vuông A: PA = LU. Với L là
AX 1 PAX LUX PB B '
ma trận tam giác dưới; U là ma trận tam giác trên.
89
- TẠP CHÍ KHOA HỌC ĐẠI HỌC VĂN LANG Nguyễn Văn Lộc
LY B ' 2 Y L1.B ' Entrée[6]: print(U)
UX Y 3 X U .Y
1 [[ 3. 2. -1. 2.] [ 0. -4.33333333
2.66666667-0.33333333] [0. 0.
Thay vì giải hệ phương trình (1), ta lần lượt: 4.15384615-2.76923077] [0. 0. 0. -6.]]
Bước 1: Giải hệ phương trình (2), tìm Y, import numpy as np
1
với Y L .B ' Entrée[7]: B = np.array([[6], [8], [4], [-8]])
Bước 2: Giải hệ phương trình (3), tìm X, B
1 Out [7]: array([[ 6], [ 8], [ 4], [-8]])
với X U .Y
D=P@B
Ví dụ: Giải hệ phương trình: Entrée[8]:
D
x1 2 x2 3 x3 2 x4 6 Out [8]: array([[ 4.], [-8.], [ 6.], [ 8.]])
2 x1 x2 2 x3 3 x4 8 . Theo [2, tr.86] from numpy.linalg import inv
3x 2 x x 2 x 4
1 2 3 4 Entrée[9]: K = inv(L)
2 x1 3 x2 2 x3 x4 8 K
Chuyển hệ phương trình về dạng phương array([[ 1., 0., 0., 0.], [-0.66666667,
1., 0., 0.], [-0.53846154, 0.30769231, 1.,
trình ma trận: AX =B, với: Out [9]:
0.], [-0.66666667, -0.33333333,
1 2 3 2 x1 6
x2 0.66666667, 1.]])
2 1 2 3 8
A ;B
2
;X Y=K@D
3 2 1 x3 4
2 8
Entrée[10]:
Y
3 2 1 4
x
array([[4.], [-10.66666667], [1.38461538],
Giải: (Sử dụng phân rã PA =LU). Out [10]:
[12.]])
from numpy import array E = inv(U)
Entrée[1]: Entrée[11]:
from scipy.linalg import lu E
A = array([[1, 2, 3, -2], [2, -1, -2, - array([[ 0.33333333, 0.15384615, -
Entrée[2]: 3], [3, 2, -1, 2], [2, -3, 2, 1]]) 0.01851852, 0.11111111], [-0., -
print(A) Out [11]: 0.23076923, 0.14814815, -0.05555556],
[[ 1 2 3 -2] [ 0., 0., 0.24074074, -0.11111111], [-0., -
[ 2 -1 -2 -3] 0., -0., -0.16666667]])
[ 3 2 -1 2] X = E.dot(Y)
[ 2 -3 2 1]] Entrée[12]:
X
P, L, U =lu(A) Out [12]: array([[ 1.], [ 2.], [-1.], [-2.]])
Entrée[3]: C=P.dot(L).dot(U)
print(C) Vậy nghiệm của hệ phương trình là :
[[ 1. 2. 3. -2.] x1 1
[ 2. -1. -2. -3.] x 2
[ 3. 2. -1. 2.] x 2 1
3
[ 2. -3. 2. 1.]] x4 2
Entrée[4]: print(P)
[[ 1. 2. 3. -2.] 2.4. Ứng dụng phân rã ma trận PA = LU và
[ 2. -1. -2. -3.] phương pháp lập trình giải mô hình tuyến
[ 3. 2. -1. 2.] tính kinh tế
[ 2. -3. 2. 1.]] Mô hình tuyến tính trong phân tích kinh tế
Entrée[5]: print(L) giải bằng phân rã LU và phương pháp lập trình
[[ 1. 0. 0. 0.] [0.66666667 1. 0. 0.] theo quy trình 3 bước như mô tả trong ví dụ sau:
[0.33333333-0.30769231 1. 0.] Ví dụ: Xét thị trường chè, café, ca cao có
[0.66666667 0.53846154-0.66666667 1.]] hàm cung và hàm cầu tương ứng như sau:
90
- TẠP CHÍ KHOA HỌC ĐẠI HỌC VĂN LANG Số 27, Tháng 5 - 2021
QS 10 P1 ; ...QD 20 P1 P3 ...( che ) [[1. 0. 0.]
1 1
[0. 1. 0.]
QS 2 P2 ; ...QD 40 2 P2 P3 ...( cafe) [0. 0. 1.]]
2 2
QS 5 3 P3 ; ...QD 10 P2 P3 P1...( caocao ) Entrée[6]: print(L)
3 3 [[ 1. 0. 0. ]
Hãy thiết lập mô hình cân bằng thị trường [ 0. 1. 0. ]
của ba loại hàng hóa trên. Xác định giá và [ 0.5 -0.25 1. ]]
lượng hàng hóa của mỗi loại ở trạng thái cân Entrée[7]: print(U)
bằng thị trường [3, tr.84]. [[2. 0. 1. ]
Giải:Bước 1: Thiết lập mô hình cân bằng [0. 4. 1. ]
thị trường: [0. 0. 3.75]]
import numpy as np
Q Q
S1 D1 10 P1 20 P1 P3 Entrée[8]: B = np. array([[30], [40], [15]])
S
Q Q D 2
2 P 40 2 P2 P3 B
Q 2 Q 2 5 3P3 10 P2 P3 P1 Out [8]: array([[30], [40], [15]])
S3 D3
D=P@B
Entrée[9]:
2 P1 P3 30 D
4 P2 P3 40 Out [9]: array([[30.], [40.], [15.]])
P1 P2 4 P3 15 from numpy.linalg import inv
Entrée[10]: K = inv(L)
Dạng ma trận AX = B với:
K
2 0 1 P1 30 array([[ 1., 0. , 0.], [0., 1., 0.], [-
A 0 4 1 ; X P 2 ; B 40 Out [10]:
0.5, 0.25, 1.]])
1 1 4 P3 15
Y=K@D
Entrée[11]:
Bước 2: Giải mô hình bằng phương pháp Y
lập trình, sử dụng phân rã ma trận PA= LU Out [11]: array([[30.], [40.], [10.]])
Entrée [1]: # Giải mô hình tuyến tính bậc Entrée[12]:
E = inv(U)
3_trong kinh tế : E
array([[ 0.5, 0., -0.13333333], [0., 0.25, -
2 P1 P3 30 Out [12]:
# 4 P2 P3 40
0.06666667], [0., 0., 0.26666667]])
X = E.dot(Y)
P1 P2 4 P3 15 Entrée[13]:
X
from numpy import array array([[13.66666667],
Entrée[2]: Out [13]:
from scipy.linalg import lu [9.33333333], [2.66666667]]
A = array([[2, 0, 1], [0, 4, 1], [1, -
Bước 3: Phát biểu kết quả “kinh tế” của
Entrée[3]: 1, 4]])
bài toán: Giá và lượng cân bằng tương ứng của
print(A)
[[ 2 0 1]
mỗi loại hàng hóa là:
[ 0 4 1] P1 13, 66, QD QS 10 13, 66 3, 66;
1 1
[ 1 -1 4]]
P, L, U =lu(A) P2 9, 33, QD QS 2.9, 33 18, 66;
2 2
Entrée[4]: C=P.dot(L).dot(U)
P3 2, 66, QD QS 5 3.2, 66 2, 98
print(C) 3 3
[[ 2. 0. 1.] 3. KẾT LUẬN
[ 0. 4. 1.] Hệ phương trình tuyến tính có ứng dụng
[ 1. -1. 4.]] rộng rãi trong các bài toán tìm vec-tơ riêng, giá
Entrée[5]: print(P)
trị riêng của ánh xạ tuyến tính, trong các hệ mô
91
- TẠP CHÍ KHOA HỌC ĐẠI HỌC VĂN LANG Nguyễn Văn Lộc
hình hóa tuyến tính trong kinh tế... Do vậy, việc trên. Từ những kết quả đã trình bày còn cho
tìm các phương pháp hữu hiệu giải các hệ tuyến thấy sự cần thiết của việc kết hợp nghiên cứu
tính có số ẩn và số phương trình “rất lớn” luôn phát triển các phương pháp Toán học và
là nhu cầu cần thiết. Phân rã ma trận LU kết phương pháp lập trình trong giải các mô hình
hợp với phương pháp lập trình cho ta một tuyến tính trong kinh tế và mở rộng cho các mô
phương pháp giải hiệu quả các phương trình hình kinh tế khác.
TÀI LIỆU THAM KHẢO
[1] Trung tâm tin học, Đại học Khoa học Tự nhiên (2019), Mathematics and Statistics for Data
Science, Tài liệu lưu hành nội bộ.
[2] Nguyễn Đình Trí (2014), Bài tập Toán cao cấp tập 1, Nxb Giáo dục Việt Nam.
[3] Nguyễn Tiến Quang (2014), Cơ sở Đại số tuyến tính, Nxb Giáo dục Việt Nam.
Ngày nhận bài: 22-02-2021. Ngày biên tập xong: 05-5-2021. Duyệt đăng: 20-5-2021
92
nguon tai.lieu . vn