Skip to content

Latest commit

 

History

History
429 lines (416 loc) · 12.5 KB

README.md

File metadata and controls

429 lines (416 loc) · 12.5 KB
Raw

作业要求

要求完成课堂上讲的关于矩阵分解的LU、QR（Gram-Schmidt）、Orthogonal Reduction (Householder reduction 和Givens reduction)和 URV程序实现，要求如下：

1、一个综合程序，根据选择参数的不同，实现不同的矩阵分解；在此基础上，实现Ax=b方程组的求解，以及计算A的行列式；

2、可以用matlab、Python等编写程序，需附上简单的程序说明，比如参数代表什么意思，输入什么，输出什么等等，附上相应的例子；

3、一定是可执行文件，例如 .m文件等,不能是word或者txt文档。附上源代码，不能为直接调用matlab等函数库;

实验环境

  • python 3.8.9
  • numpy 1.23.4 已在macos 12.6.1 pycharm上运行通过

程序说明

  • LUFactorization.py 实现了矩阵LU分解
  • QRFactorization.py 使用 Gram-Schmidt 实现了矩阵的QR分解
  • OrthogonalReduction.py 使用 Householder reduction 和 Givens reduction 实现了矩阵的QR分解
  • URVFactorization.py 使用 Householder reduction 实现了矩阵的URV分解（也可以选择Givens，测试一致）
  • test.py 是测试上面四个程序的文件
  • main.py 是一个综合程序，可以任意选择一个线性系统，选择任意方法进行矩阵分解，并最后求解该线性系统。包括附加功能求行列式

操作手册

  1. 首先初始化矩阵A和b
  2. 选择LU分解、QR分解或URV分解
  3. 使用分解后的矩阵求解线性系统
  4. 求行列式

main.py 操作示例

shijunhan@sjh code % cd MatrixApplication
shijunhan@sjh MatrixApplication % source venv/bin/activate
(venv) shijunhan@sjh MatrixApplication % python main.py
请选择一个线性系统(1->输入data.txt文件 2->随机生成一个mxn矩阵 0->退出)
1
请选择分解方法(1->LU 2->QR 3->URV 4->求行列式 5->使用LU求解线性系统 6->使用QR求解线性系统 0->退出)
1
L矩阵:
 [[1. 0. 0.]
 [2. 1. 0.]
 [3. 4. 1.]]
U矩阵:
 [[2. 2. 2.]
 [0. 3. 3.]
 [0. 0. 4.]]
LU矩阵:(LU分解过程中会有行交换的行为，所以还原的矩阵可能会与原矩阵不对应
 [[ 2.  2.  2.]
 [ 4.  7.  7.]
 [ 6. 18. 22.]]
请选择分解方法(1->LU 2->QR 3->URV 4->求行列式 5->使用LU求解线性系统 6->使用QR求解线性系统 0->退出)
2
请选择QR分解算法(gm->gram-schmidt householder->Householder reduction givens->Givens reduction)
gm
Q矩阵:
 [[ 0.26726124 -0.57735027  0.77151675]
 [ 0.53452248 -0.57735027 -0.6172134 ]
 [ 0.80178373  0.57735027  0.15430335]]
R矩阵:
 [[ 7.48331477 18.70828693 21.91542184]
 [ 0.          5.19615242  7.5055535 ]
 [ 0.          0.          0.6172134 ]]
请选择分解方法(1->LU 2->QR 3->URV 4->求行列式 5->使用LU求解线性系统 6->使用QR求解线性系统 0->退出)
2
请选择QR分解算法(gm->gram-schmidt householder->Householder reduction givens->Givens reduction)
householder
Q矩阵:
 [[ 0.26726124 -0.57735027  0.77151675]
 [ 0.53452248 -0.57735027 -0.6172134 ]
 [ 0.80178373  0.57735027  0.15430335]]
R矩阵:
 [[ 7.48331477 18.70828693 21.91542184]
 [ 0.          5.19615242  7.5055535 ]
 [ 0.         -0.          0.6172134 ]]
请选择分解方法(1->LU 2->QR 3->URV 4->求行列式 5->使用LU求解线性系统 6->使用QR求解线性系统 0->退出)
2
请选择QR分解算法(gm->gram-schmidt householder->Householder reduction givens->Givens reduction)
givens
Q矩阵:
 [[ 0.26726124 -0.57735027  0.77151675]
 [ 0.53452248 -0.57735027 -0.6172134 ]
 [ 0.80178373  0.57735027  0.15430335]]
R矩阵:
 [[ 7.48331477 18.70828693 21.91542184]
 [ 0.          5.19615242  7.5055535 ]
 [-0.         -0.          0.6172134 ]]
请选择分解方法(1->LU 2->QR 3->URV 4->求行列式 5->使用LU求解线性系统 6->使用QR求解线性系统 0->退出)
3
U矩阵
 [[ 0.26726124 -0.57735027  0.77151675]
 [ 0.53452248 -0.57735027 -0.6172134 ]
 [ 0.80178373  0.57735027  0.15430335]]
R矩阵
 [[29.77055112 -0.          0.        ]
 [ 8.79051518  2.46174252 -0.        ]
 [ 0.45435813  0.25936349  0.32747771]]
V矩阵
 [[ 0.25136635  0.62841587  0.73614431]
 [-0.89759173 -0.13321737  0.42021688]
 [ 0.36213817 -0.76638543  0.53057453]]
URV矩阵
 [[ 2.  2.  2.]
 [ 4.  7.  7.]
 [ 6. 18. 22.]]
请选择分解方法(1->LU 2->QR 3->URV 4->求行列式 5->使用LU求解线性系统 6->使用QR求解线性系统 0->退出)
4
该方阵行列式 = 24.0
请选择分解方法(1->LU 2->QR 3->URV 4->求行列式 5->使用LU求解线性系统 6->使用QR求解线性系统 0->退出)
5
求解x=
x0 = [6.]
x1 = [6.]
x2 = [-6.]
请选择分解方法(1->LU 2->QR 3->URV 4->求行列式 5->使用LU求解线性系统 6->使用QR求解线性系统 0->退出)
6
[array([6.]), array([6.]), array([-6.])]
请选择分解方法(1->LU 2->QR 3->URV 4->求行列式 5->使用LU求解线性系统 6->使用QR求解线性系统 0->退出)
0
请选择一个线性系统(1->输入data.txt文件 2->随机生成一个mxn矩阵 0->退出)
2
请输入矩阵长宽 e.g. 3,3
4,3
请选择分解方法(1->LU 2->QR 3->URV 4->求行列式 5->使用LU求解线性系统 6->使用QR求解线性系统 0->退出)
1
L矩阵:
 [[ 1.          0.          0.          0.        ]
 [ 0.10352949  1.          0.          0.        ]
 [ 0.31619531  1.05492921  1.          0.        ]
 [ 1.20885259 -0.23810013 -0.54131211  1.        ]]
U矩阵:
 [[0.59469373 0.54918399 0.42531948]
 [0.         0.68855697 0.35536365]
 [0.         0.         0.30067725]
 [0.         0.         0.        ]]
LU矩阵:(LU分解过程中会有行交换的行为，所以还原的矩阵可能会与原矩阵不对应
 [[0.59469373 0.54918399 0.42531948]
 [0.06156834 0.74541371 0.39939675]
 [0.18803937 0.90002826 0.81004476]
 [0.71889706 0.49993699 0.26677619]]
请选择分解方法(1->LU 2->QR 3->URV 4->求行列式 5->使用LU求解线性系统 6->使用QR求解线性系统 0->退出)
0
请选择一个线性系统(1->输入data.txt文件 2->随机生成一个mxn矩阵 0->退出)
0
程序运行结束！
(venv) shijunhan@sjh MatrixApplication %

测试文件test.py输出结果

shijunhan@sjh code % cd MatrixApplication
shijunhan@sjh MatrixApplication % source venv/bin/activate
(venv) shijunhan@sjh MatrixApplication % python test.py
-----------------开始LU分解测试-------------------
Test A mxm, r=m
L =
 [[1. 0. 0.]
 [2. 1. 0.]
 [3. 4. 1.]]
U =
 [[2. 2. 2.]
 [0. 3. 3.]
 [0. 0. 4.]]
A = LU =
 [[ 2.  2.  2.]
 [ 4.  7.  7.]
 [ 6. 18. 22.]]
Test B mxn, m>n
L =
 [[ 1.    0.    0.    0.    0.    0.  ]
 [ 3.5   1.    0.    0.    0.    0.  ]
 [ 2.    0.    1.    0.    0.    0.  ]
 [ 0.5  -3.    5.    1.    0.    0.  ]
 [ 0.5  -3.    5.    1.25  1.    0.  ]
 [ 4.    0.    3.    0.    0.    1.  ]]
U =
 [[ 2.   1.   1.   4. ]
 [ 0.  -0.5 -2.5 -6. ]
 [ 0.   0.  -1.  -2. ]
 [ 0.   0.   0.  -4. ]
 [ 0.   0.   0.   0. ]
 [ 0.   0.   0.   0. ]]
A = LU =
 [[ 2.  1.  1.  4.]
 [ 7.  3.  1.  8.]
 [ 4.  2.  1.  6.]
 [ 1.  2.  3.  6.]
 [ 1.  2.  3.  5.]
 [ 8.  4.  1. 10.]]
Test C mxn, n>m>r
L =
 [[1. 0. 0.]
 [3. 1. 0.]
 [2. 0. 1.]]
U =
 [[ 2.  2.  2.  2.]
 [ 0. 12. 16.  6.]
 [ 0.  0.  0.  0.]]
A = LU =
 [[ 2.  2.  2.  2.]
 [ 6. 18. 22. 12.]
 [ 4.  4.  4.  4.]]
0
-----------------结束LU分解测试-------------------
-----------------开始QR分解测试-------------------
Test A mxm
Q矩阵
 [[ 0.   -0.8  -0.6 ]
 [ 0.6   0.48 -0.64]
 [ 0.8  -0.36  0.48]]
R矩阵
 [[ 5. 25. -4.]
 [ 0. 25. 10.]
 [ 0.  0. 10.]]
QR矩阵
 [[  0. -20. -14.]
 [  3.  27.  -4.]
 [  4.  11.  -2.]]
Test A mxn
Test B, mxn and m>n
Q矩阵4x3
 [[ 0.         -0.78655366 -0.54750772]
 [ 0.55708601  0.51261601 -0.56796405]
 [ 0.74278135 -0.29970407  0.12514462]
 [ 0.37139068 -0.16951588  0.60165684]]
R矩阵3x3
 [[ 5.38516481 25.06887065 -1.48556271]
 [ 0.         25.42738139  8.54360015]
 [ 0.          0.         13.29661611]]
QR矩阵
 [[  0. -20. -14.]
 [  3.  27.  -4.]
 [  4.  11.  -2.]
 [  2.   5.   6.]]
0
-----------------结束QR分解测试-------------------
-----------------开始正交约减测试-------------------
Test A, mxm
Q矩阵
 [[ 0.   -0.8  -0.6 ]
 [ 0.6   0.48 -0.64]
 [ 0.8  -0.36  0.48]]
R矩阵
 [[ 5. 25. -4.]
 [ 0. 25. 10.]
 [ 0. -0. 10.]]
QR矩阵
 [[  0. -20. -14.]
 [  3.  27.  -4.]
 [  4.  11.  -2.]]
Givens Reduction
Q矩阵
 [[ 0.   -0.8  -0.6 ]
 [ 0.6   0.48 -0.64]
 [ 0.8  -0.36  0.48]]
R矩阵
 [[ 5. 25. -4.]
 [ 0. 25. 10.]
 [-0. -0. 10.]]
QR矩阵
 [[  0. -20. -14.]
 [  3.  27.  -4.]
 [  4.  11.  -2.]]
Test B, mxn and m>n
Q矩阵4x4
 [[ 0.         -0.78655366 -0.54750772 -0.28560222]
 [ 0.55708601  0.51261601 -0.56796405 -0.3229502 ]
 [ 0.74278135 -0.29970407  0.12514462  0.58548455]
 [ 0.37139068 -0.16951588  0.60165684 -0.6865438 ]]
R矩阵4x3
 [[ 5.38516481 25.06887065 -1.48556271]
 [ 0.         25.42738139  8.54360015]
 [ 0.         -0.         13.29661611]
 [-0.         -0.          0.        ]]
QR矩阵
 [[  0. -20. -14.]
 [  3.  27.  -4.]
 [  4.  11.  -2.]
 [  2.   5.   6.]]
Givens Reduction
Q矩阵
 [[ 0.         -0.78655366 -0.54750772  0.28560222]
 [ 0.55708601  0.51261601 -0.56796405  0.3229502 ]
 [ 0.74278135 -0.29970407  0.12514462 -0.58548455]
 [ 0.37139068 -0.16951588  0.60165684  0.6865438 ]]
R矩阵
 [[ 5.38516481 25.06887065 -1.48556271]
 [ 0.         25.42738139  8.54360015]
 [-0.         -0.         13.29661611]
 [ 0.          0.         -0.        ]]
QR矩阵
 [[  0. -20. -14.]
 [  3.  27.  -4.]
 [  4.  11.  -2.]
 [  2.   5.   6.]]
Test C, mxn and m<n
Q矩阵3x3
 [[ 0.   -0.8  -0.6 ]
 [ 0.6   0.48 -0.64]
 [ 0.8  -0.36  0.48]]
R矩阵3x4
 [[ 5.   25.   -4.    3.4 ]
 [ 0.   25.   10.   -2.48]
 [ 0.   -0.   10.   -3.36]]
QR矩阵
 [[  0. -20. -14.   4.]
 [  3.  27.  -4.   3.]
 [  4.  11.  -2.   2.]]
Givens Reduction
Q矩阵
 [[ 0.   -0.8  -0.6 ]
 [ 0.6   0.48 -0.64]
 [ 0.8  -0.36  0.48]]
R矩阵
 [[ 5.   25.   -4.    3.4 ]
 [ 0.   25.   10.   -2.48]
 [-0.   -0.   10.   -3.36]]
QR矩阵
 [[  0. -20. -14.   4.]
 [  3.  27.  -4.   3.]
 [  4.  11.  -2.   2.]]
Test D, mxm and r=1
Q矩阵3x3
 [[ 0.57735027  0.81649658 -0.        ]
 [ 0.57735027 -0.40824829  0.70710678]
 [ 0.57735027 -0.40824829 -0.70710678]]
R矩阵3x3
 [[  1.73205081 -34.64101615 -24.24871131]
 [ -0.           0.           0.        ]
 [  0.          -0.          -0.        ]]
QR矩阵
 [[  1. -20. -14.]
 [  1. -20. -14.]
 [  1. -20. -14.]]
Givens Reduction
Q矩阵
 [[ 0.57735027 -0.40824829  0.70710678]
 [ 0.57735027 -0.40824829 -0.70710678]
 [ 0.57735027  0.81649658  0.        ]]
R矩阵
 [[  1.73205081 -34.64101615 -24.24871131]
 [  0.           0.          -0.        ]
 [  0.           0.           0.        ]]
QR矩阵
 [[  1. -20. -14.]
 [  1. -20. -14.]
 [  1. -20. -14.]]
0
-----------------结束正交约减测试-------------------
-----------------开始URV分解测试-------------------
Test A mxm, r=m
U矩阵
 [[ 0.   -0.8  -0.6 ]
 [ 0.6   0.48 -0.64]
 [ 0.8  -0.36  0.48]]
R矩阵
 [[25.8069758  -0.         -0.        ]
 [22.66828956 14.53095484 -0.        ]
 [-1.54996852  9.2998111   3.33333333]]
V矩阵
 [[ 0.19374606  0.96873032 -0.15499685]
 [-0.30224386  0.20924575  0.92998111]
 [ 0.93333333 -0.13333333  0.33333333]]
URV矩阵
 [[  0. -20. -14.]
 [  3.  27.  -4.]
 [  4.  11.  -2.]]
Test B mxm, r=n<m
U矩阵
 [[ 0.40824829  0.18257419 -0.89442719]
 [ 0.81649658  0.36514837  0.4472136 ]
 [ 0.40824829 -0.91287093  0.        ]]
R矩阵
 [[ 5.13160144 -0.          0.        ]
 [ 2.03347513 15.41206169 -0.        ]
 [ 0.          0.          0.        ]]
V矩阵
 [[ 0.47733437  0.87511301  0.07955573]
 [-0.06297974 -0.05623191  0.99642939]
 [ 0.87646189 -0.48064039  0.02827296]]
URV矩阵
 [[  1.   2.   3.]
 [  2.   4.   6.]
 [  1.   1. -14.]]
Test C mxn, m<n r=2
U矩阵
 [[-0.66666667 -0.66666667 -0.33333333]
 [ 0.33333333 -0.66666667  0.66666667]
 [-0.66666667  0.33333333  0.66666667]]
R矩阵
 [[ 9. -0. -0. -0.]
 [-0.  3.  0.  0.]
 [ 0.  0.  0.  0.]]
V矩阵
 [[ 0.66666667  0.          0.66666667  0.33333333]
 [ 0.          1.         -0.         -0.        ]
 [-0.66666667  0.          0.73333333 -0.13333333]
 [-0.33333333  0.         -0.13333333  0.93333333]]
URV矩阵
 [[-4. -2. -4. -2.]
 [ 2. -2.  2.  1.]
 [-4.  1. -4. -2.]]
Test D mxn, m>n r=2
U矩阵
 [[-0.59628479 -0.2981424   0.48256454  0.56805548]
 [ 0.2981424   0.1490712  -0.48864076  0.80629963]
 [-0.59628479 -0.2981424  -0.72688491 -0.16490566]
 [-0.4472136   0.89442719  0.         -0.        ]]
R矩阵
 [[ 9.05538514  0.         -0.        ]
 [ 1.76690442  3.14293633  0.        ]
 [ 0.          0.          0.        ]
 [ 0.          0.          0.        ]]
V矩阵
 [[ 0.7407972   0.19754592  0.64202424]
 [-0.41646337  0.88498465  0.20823168]
 [-0.52704628 -0.42163702  0.73786479]]
URV矩阵
 [[-4. -2. -4.]
 [ 2.  1.  2.]
 [-4. -2. -4.]
 [-3.  2. -1.]]
0
-----------------结束URV分解测试-------------------
(venv) shijunhan@sjh MatrixApplication %