随着互联网的普及和电子商务的发展，推荐系统逐渐成为电子商务IT 技术的一个重要研究内容，得到越来越多研究者的关注[1]
。例如，Amazon 、CDNOW 、e －
Bay 、京东等电子商务网站，都开始逐渐引入了各种形式的推荐系统。
协同过滤推荐是当今被广泛使用的推荐技术[4]，其中，潜在因素模型（latent factor models ）是协同过滤推
荐使用的技术之一。潜在因素模型是通过分析消费历史记录来推测潜在的发展趋势。矩阵分解算法（matrix
factorization ）[2]
是潜在因素模型中被广泛使用的技术之
一。但是，随着网站消费记录的增多，传统的矩阵分解算法不能高效地为大规模消费记录构建潜在因素模型，无法实现推荐系统的实时性。本文针对大规模历史消费记录，提出了高效地特征矩阵分解算法，该算法是
收稿日期：2012-12-21
作者简介：张海建（1978-），男，北京人，硕士，讲师，主要研究方向：计算机软件，数据库系统。
分布式矩阵分解算法在推荐系统中的研究与应用
张海建
（北京信息职业技术学院，北京100018）
摘要：随着互联网信息技术的高速发展，越来越多的人开始接触网络。网上购物成为当今社会的购物的主要方式之一，各大电子商务网站每天都有大量的消费者购买及浏览记录。电子商业往往希望通过分析大量的网站购买记录以及消费者浏览记录，对消费者提供有价值地商品推荐，以便于提高销售量。矩阵分解广泛地应用在推荐系统中的协同过滤算法中，但是，随着网站数据量的增大，传统的矩阵分解算法不能有效地处理这些大规模海量数据。本文针对推荐系统中大规模的网站数据，提出了基于云平台的分布式矩阵分解算法，该算法能够分布式完成推荐系统中的协同过滤过程。实验结果表明，本文提出的算法能够高效地完成推荐系统中的协同过滤，并且，该算法具有很好的可扩展性。关键词：推荐系统；分布式；云平台；mapReduce ；矩阵分解；协同过滤中文分类号：ＴＰ３
文献标识码：Ａ
文章编号：1001-7119（2013）12-0151-03
The Research and Application of Distributed Matrix
Factorization Algorithm in Recommend System
Zhang Haijian
(Beijing Information Technology College,Beijing 100018,China)
Abstract:With the high-speed development of internet information technology,more and more people begin to get in touch with internet.On-line shopping is becoming one of the main shopping methods,several big e-commerce sites pro －duce big amount of consumer purchasing and browsing records.E-commerce sites usually hope to analyze these records and provide to the consumers with valuable commodity recommendation,in order to promote sales.Matrix factorization is popularly used in collaborative filtering algorithm in recommendation system.However,with the incensement of web data,traditional matrix factorization could not deal with this huge amount of data.In this paper,focusing on big scale website data,we propose distributed matrix factorization based on Cloud computing platform.Through the experimental results,the algorithm in this paper could complete collaborative filtering in recommendation system effectively,and it has good scalability.
Key words ：recommender systems;distributed;cloud platforms;mapReduce;matrix decomposition,and collaborative filtering
第29卷第12期
2013年12月
科技通报
BULLETIN OF SCIENCE AND TECHNOLOGY
Vol.29No.12Dec.2013
技通报科第29卷
基于MapReduce [5]分布式云计算平台[7]，能够高效、快速地完成潜在因素模型的构建。实验结果进一步表明，本文提出的算法具有很高的加速比，并且有很好的可扩展性。
1矩阵分解算法
矩阵分解模型中，引入一组二进制值pui,pui 代表
用户u 对项目i 的偏好：
p ui =
1ulikei
0udislike i
如果用户u 已经购买了项目，那么令p ui =1，否则，令p ui =0。在购买历史记录中，不存在p ui =0的样本值，因此该矩阵分解算法只能用于对正训练数据进行推荐。
在矩阵分解模型中，偏好度被假定为内积形式：
p ui =x T u y i 。矩阵分解模型的目标是求解向量x u 和y i 满足最
小化训练数据的预测错误平方值。用户因素和项目因素是通过最小化如下方程求解的：
min
x *,y *∑（u,i ）∈R
（p ui -x T u y i ）2+λ（∑u
||x u ||2+∑i
||y i ||2
）
其中，λ是正则化参数，用于防止过拟合问题。通
过固定用户参数或者项目参数，成本函数变为二次方程，因此该问题转化为最小平方优化问题，步骤如下：
首先，通过重新计算用户因素x u 最小化如下成本方程：
x u =（Y T Y+λI ）-1Y T
p （u ）
其中，p (u )包含所有用户u 的购买项目记录。然后，通过相同的方法重复计算项目因素：
y i =（X T X+λI ）-1X T p （i ）
通过迭代重复计算项目因素和用户因素x u 和y i ，矩阵分解模型将p
赞ui 中top-N 项目推荐给用户u ，其中p 赞ui 代表用于u 对项目i 的预测偏好度。
2分布式矩阵分解算法
通过前面的介绍，可以看出算法的执行时间与矩
阵相乘有关，并且与因式分解的个数相关，如果矩阵X 的维度非常大，那么大矩阵相乘问题将严重影响算法的执行时间。本节部分针对大规模数据计算矩阵相乘求解慢问题，基于MapReduce 分布式计算平台，设计分布式矩阵分解算法。下面，详细介绍算法的执行流程。
（1）将数据集平均分配到各个不同节点中，即将初始化矩阵X ，Y 平均分配到K 的个计算节点中，每个计算节点的子矩阵表示为：
Y 1，Y 2,..,Y k ;X 1，X 2,..,X k 。并且，将p (u )和p (i )的信息传递到各个计算节点。
（2）每个计算节点中，分别求解子矩阵转置与该
子矩阵的乘积，即：Y T k Y,X T k X 以及Y T
k p （u ）和X T k p
（i ）。（3）当所有计算节点计算完毕后，将所有的计算
结果Y T k Y,X T k X 做和作为Y T Y 和X T
X 最终的结果；
同时，将Y T k p （u ）和X T k p
（i ）结果按照列号合并，最为最终的矩阵结果。
（4）对Y T Y 和X T X 分别求逆运算，与矩阵和X T p
（i ）分别相乘，求解出相应的x u 和y i 。迭代步骤(2)、(3)、(4)，直至收敛为止，完成最小化成本函数求解。
（5）将最终的x u 转置和y i 相乘，得出预测p 赞u i ，并将top-N 项目推荐给用户u 。
下面是基于MapReduce 的分布式矩阵分解算法的伪代码：
Input ：User-Factor Matrix X,Item-Factor Matrix Y,p(u),p(i)
Output:p 赞ui
Mapper
Program:
图1可扩展性测试结果Fig.1Scalability Testing Results 表1实验数据描述
Table 1Experimental Data Description 数据集名称
D1D2D3D4D5D6
记录条数1,000,0002,000,0004,000,0008,000,00010,000,00012,000,000
表2算法执行时间比较
Table2Algorithm Running Time Comparison
实验数据D1D2D3D4D5D6
分布式矩阵分解
（D-MF ）执行时间/s 3867781523312336704632
传统算法（T-MF ）执行时间/s 48251058019296409114660959289
加速比12.513.612.6713.112.712.8
152
第12期
1:for each node k
2:compute(Y T k Y,X T k X);
3:compute(Y T k p（u）和X T k p（i）);
4:end for
5:ItermediateResult=store(k,Y T k Y,X T k X,Y T k p（u）,
X T k p（i）);
Reducer Program:
1:for each key k
2:Y T Y=Matrix_Add(Y T k Y)
3:X T X=Matrix_Add(X T k X)
4:Y T p（u）=Matrix_Combine(Y T k p（u）)
5:X T p（i）=Matrix_Combine(X T k p（i）))
6:x u=Compute(Y T Y,Y T p（u）)
7:y i=Compute(X T X,X T p（i）)
Controller Program:
1:Initialize X,Y,p(u),p(i)
2:Distribute X,Y,p(u),p(i)to K nodes
3:Transmit data to mappers
4:Start Mapper
5:Start Reducer
6:while(|C current-C before|>β){
7:repeat4),5)
8:}
9:Store(x u,y i)=Output(Reducer)
10:p赞ui=MatrixMulti(x u,y i)
3实验结果
实验部分的数据集是使用公开的互联网消费记录中获取的，其中数据集的记录格式如下所示：用户ID项目ID数量时间戳
每条记录描述了用户购买某一项目的数目以及时间。表1详细地描述了使用的大规模数据的信息。
由于本文是基于分布式计算框架，本文的所有计算都是基于最新版本的Hadoop[6]-0.20.2做为MapRe－duce分布式编程环境。本文的实验环境是分布式云计算平台，该平台含有20个运算节点，每个节点的配置为：4.0Hz的Intel处理器，32G内存，CentOs Linux操作系统。
本文的实验分为两个部分，第一部分测试分布式矩阵分解加速比，主要测试分布式矩阵分解算法（D-MF）与传统算法（T-MF）在执行时间上的比较。表2描述了分布式算法在20个计算节点上对6组实验数据的执行时间和传统矩阵分解算法的执行时间，以及加速比结果。
通过表2的结果可以看出，分布式矩阵分解算法与传统算法有明显的加速比，能够明显地提高推荐系统的执行效率，高效地做出推荐。
本文的第二部分实验主要测试算法的可扩展性。本组实验通过测试不同数据集在不同计算节点下的计算时间，测试算法的可扩展性。图1所示为6组实验数据在节点个数为5,10,15和20下的运算时间。通过图1的结果可以看出，随着计算节点个数的增多，运行时间逐渐减少，有效地提高算法的执行效率。结果表明，当处理大规模数据时，可以通过增加计算节点的个数减小运算时间。同时，通过图1可以看出，随着数据规模的增多，算法的执行时间呈现等比增长，可以看出算法具有很好的扩展性。
4总结
随着电子商务规模的增大，用户数目和项目数据急剧增加，推荐系统的系统实时性要求越来越难以满足。针对海量大规模网站数据问题，本文针对协同过滤技术中的矩阵分解算法，提出了基于云计算平台的分布式矩阵分解算法，该算法通过实验结果进一步表明具有很高的加速比以及很高的可扩展性。
参考文献：
[1]Schafer J Ben,Joseph Konstan,and John Riedi.Recom－
mender systems in e-commerce[C]//.Proceedings of the
1st ACM conference on Electronic commerce.ACM,
1999.
[2]Koren,Yehuda,Robert Bell,and Chris Volinsky.Matrix
factorization techniques for recommender systems[J].Com－
puter2009,42(8):30-37.
[3]Seung D and L Lee.Algorithms for non-negative matrix
factorization[J].Advances in neural information processing
systems2001(13):556-562.
[4]邓爱林,左子叶,朱扬勇.基于项目聚类的协同过滤推
荐算法[J].小型微型计算机系统2004，25(9):1665-
1670.
[5]Dean Jeffrey and Sanjay Ghemawat.MapReduce:simpli－
fied data processing on large clusters[J].Communications
of the ACM2008,51(1):107-113.
[6]Borthakur Dhruba.The hadoop distributed file system:
Architecture and design[J].Hadoop Project Website2007
(11):21.
[7]刘捡平,黄勇,周西柳.云计算科技服务系统平台设计
研究[J].科技通报,2012,28(10):19-21.
张海建.分布式矩阵分解算法在推荐系统中的研究与应用153
万方数据
万方数据
万方数据
万方数据
基于矩阵分解的协同过滤算法 作者：李改， 李磊， LI Gai， LI Lei 作者单位：李改,LI Gai(顺德职业技术学院,广东顺德528333;中山大学信息科学与技术学院,广州510006;中山大学软件研究所,广州510275)， 李磊,LI Lei(中山大学信息科学与技术学院,广州510006;中山大学软件研究 所,广州510275) 刊名： 计算机工程与应用 英文刊名：Computer Engineering and Applications 年，卷(期)：2011,47(30) 被引用次数：1次 参考文献(18条) 1.Wu J L Collaborative filtering on the Nefifix prize dataset 2.Ricci F.Rokach L.Shapira B Recommender system handbook 2011 3.Adomavicius G.Tuzhilin A Toward the next generation of recommender systems:a survey of the state-of-the-art and possible extenstions 2005(06) 4.Bell R.Koren Y.Volinsky C The bellkor 2008 solution to the Netflix prize 2007 5.Paterek A Improving regularized singular value decomposition for collaborative filtering 2007 6.Lee D D.Seung H S Leaming the parts of objects by non-negative matrix factorization[外文期刊] 7.徐翔.王煦法基于SVD的协同过滤算法的欺诈攻击行为分析[期刊论文]-计算机工程与应用 2009(20) 8.Pan R.Zhou Y.Cao B One-class collaborative filtering 2008 9.Pan R.Martin S Mind the Gaps:weighting the unknown in largescale one-class collaborative filtering 2009 https://www.doczj.com/doc/f218168722.html,flix Netflix prize 11.罗辛.欧阳元新.熊璋通过相似度支持度优化基于K近邻的协同过滤算法[期刊论文]-计算机学报 2010(08) 12.汪静.印鉴.郑利荣基于共同评分和相似性权重的协同过滤推荐算法[期刊论文]-计算机科学 2010(02) 13.Hadoop[E B/OL] 14.Apache MapReduce Architecture 15.Wbite T.周敏.曾大聃.周傲英Hadoop权威指南 2010 16.Herlocker J.Konstan J.Borchers A An algorithmic framework for performing collaborative filtering 1999 17.Linden G.Smith B.York J https://www.doczj.com/doc/f218168722.html, recommendations:Itemto-item collaborative filtering[外文期刊] 2003 18.Sarwar B.Karypis G.Konstan J ltem-based collaborative filtering recommendation algorithms 2001 引证文献(1条) 1.沈韦华.陈洪涛.沈锦丰基于最佳匹配算法的精密零件检测研究[期刊论文]-科技通报 2013(5) 本文链接：https://www.doczj.com/doc/f218168722.html,/Periodical_jsjgcyyy201130002.aspx
矩阵分解以及矩阵范数在数值计算中的应用 张先垒 （自动化与电气工程学院 控制科学与工程 2012210186） 【摘要】矩阵的分解是将一个矩阵分解为较为简单的或具有某种特性的若干矩阵的和或 者乘积，这是矩阵理论及其应用中比较常见的方法。由于矩阵的这些特殊的分解形式，一方面反映了矩阵的某些数值特性，如矩阵的秩、特征值、奇异值等；另一方面矩阵的分解方法与过程往往为某些有效的数值计算方法和理论分析提供了重要的依据，它是应用于解最优化问题、特征值问题、最小二乘方问题的主要数学工具。 关键词 ： 矩阵分解 对角化 逆矩阵 范数 条件数 1. 引言 矩阵分解在工程中的应用主要是在解线性方程组中,而这主要就是关系到储存和计算时间的问题上面,如何实现最小的储存和最少的计算时间是在工程计算中的头等问题。在这方年就牵涉到很多对矩阵进行怎样的分解，这篇文章介绍了基本的关于三角分解相关的内容以及关于界的稳定性的考虑。 2. 矩阵的三角分解求解线性方程组 数值求解线性方程组的方法中有一个主要是直接法，假设计算中没有舍入误差，经过有限次算术运算能够给出问题的精确解的数值方法。其中高斯消去法就是利用矩阵的分解实现的。矩阵论一种有效而且应用广泛的分解法就是三角分解法，将一个矩阵分解为一个酉矩阵（或正交矩阵）与一个三角矩阵的乘积或者三角矩阵与三角矩阵的乘积。（见课本P93例4.3）考虑一般的线性方程组，设其中的系数矩阵A 是可逆的， 1111 n m mn a a A a a ?? ? = ? ??? （1-1） 设矩阵A 的第一列中至少有一个是非零元素（否则A 就是奇异矩阵）不妨设为1i a 若一 般的记初等矩阵 [1] 如1-2式及矩阵论课本上的Givens 矩阵。
对矩阵分解及其应用 矩阵分解是指将一个矩阵表示为结构简单或具有特殊性质若干矩阵之积或之和，大体分为三角分解、QR 分解、满秩分解和奇异值分解。矩阵的分解是很重要的一部分内容，在线性代数中时常用来解决各种复杂的问题，在各个不同的专业领域也有重要的作用。秩亏网平差是测量数据处理中的一个难点，不仅表现在原理方面，更表现在计算方面，而应用矩阵分解来得到未知数的估计数大大简化了求解过程和难度。 1. 矩阵的三角分解 如果方阵A可表示为一个下三角矩阵L和一个上三角矩阵U之积，即A=LU 则称A可作三角分解。矩阵三角分解是以Gauss消去法为根据导出的，因此矩阵可以进行三角分解的条件也与之相同，即矩阵A的前n-1个顺序主子式都不为0, 即?k工0.所以在对矩阵A进行三角分解的着手的第一步应该是判断是否满足这个前提条件，否则怎么分解都没有意义。矩阵的三角分解不是唯一的，但是在一定的前提下， A=LDU勺分解可以是唯一的，其中D是对角矩阵。矩阵还有其他不同的三角分解，比如Doolittle 分解和Crout 分解，它们用待定系数法来解求 A 的三角分解，当矩阵阶数较大的时候有其各自的优点，使算法更加简单方便。 矩阵的三角分解可以用来解线性方程组Ax=b。由于A=LU，所以Ax=b可以变换成LU x=b，即有如下方程组： Ly = b { {Ux = y 先由Ly = b依次递推求得y i, y2, ........ ，y n，再由方程Ux = y依次递推求得X n， x n-1 ， ... ，X1 . 必须指出的是，当可逆矩阵A不满足?k工0时，应该用置换矩阵P左乘A以便使PA 的n个顺序主子式全不为零，此时有： Ly = pb { { Ux = y 这样，应用矩阵的三角分解，线性方程组的解求就可以简单很多了。 2. 矩阵的QF分解 矩阵的QR分解是指，如果实非奇异矩阵A可以表示为A=QR其中Q为正交矩阵，R为实非奇异上三角矩阵。QR分解的实际算法各种各样，有Schmidt正交方
咨询QQ：3025393450 有问题百度搜索“”就可以了 欢迎登陆官网：https://www.doczj.com/doc/f218168722.html,/datablog python机器学习：推荐系统实现（以矩阵分解来协同过滤）数据分析报告 用户和产品的潜在特征编写推荐系统矩阵分解工作原理使用潜在表征来找到类似的产品 1. 用户和产品的潜在特征 我们可以通过为每个用户和每部电影分配属性，然后将它们相乘并合并结果来估计用户喜欢电影的程度。
咨询QQ：3025393450 有问题百度搜索“”就可以了 欢迎登陆官网：https://www.doczj.com/doc/f218168722.html,/datablog 相同的计算可以表示为矩阵乘法问题。首先，我们把用户属性放在一个名为U 的矩阵中，在这个例子中是5，-2，1，-5和5。然后，我们把电影属性放在一个名为M的矩阵中，我们使用矩阵乘法来找出用户的评分。 但要做到这一点，我们必须已经知道用户属性和电影属性。为每个用户和每部电影提供属性评级并不容易。我们需要找到一种自动的方法。我们来看看电影评分矩阵，
咨询QQ：3025393450 有问题百度搜索“”就可以了 欢迎登陆官网：https://www.doczj.com/doc/f218168722.html,/datablog 它显示了我们数据集中的所有用户如何评价电影。这个矩阵非常稀疏，但它给了我们很多信息。例如，我们知道用户ID2给电影1号五颗星。所以，基于此，我们可以猜测，这个用户的属性可能类似于电影的属性，因为它们匹配的很好。换句话说，我们有一些线索可以使用。 让我们看看我们如何利用这些线索来了解每部电影和每个用户。在我们刚刚看到的等式中，U乘M等于电影等级，我们已经知道一些用户的实际电影等级。我们已经拥有的电影评分矩阵是我们方程式的解决方案。虽然它是解决方案的一部分，但是这个阵列仍然有很多漏洞，但对于我们来说，这已经足够了。
(1)LU 分解法程序：function x=solvebyLU(A,b) % 该函数利用LU分解法求线性方程组Ax=b的解 flag=isexist(A,b); %调用第一小节中的isexist函数判断方程组解的情况if flag==0 disp('该方程组无解！'); x=[]; return; else r=rank(A); [m,n]=size(A); [L,U,P]=lu(A); y(1)=b(1); if m>1 for i=2:m y(i)=b(i)-L(i,1:i-1)*y(1:i-1)'; end end y=y'; % 解Ux=y得原方程组的一个特解 x0(r)=y(r)/U(r,r); if r>1 for i=r-1:-1:1 x0(i)=(y(i)-U(i,i+1:r)*x0(i+1:r)')/U(i,i); end end x0=x0'; if flag==1 %若方程组有唯一解 x=x0; return; else %若方程组有无穷多解 format rat; Z=null(A,'r'); %求出对应齐次方程组的基础解系 [mZ,nZ]=size(Z); x0(r+1:n)=0; for i=1:nZ t=sym(char([107 48+i])); k(i)=t; %取k=[k1,k2...,]; end x=x0; for i=1:nZ x=x+k(i)*Z(:,i); %将方程组的通解表示为特解加对应齐次通解形式 end end end (2)矩阵的QR分解法（c语言）：
void QR(double a[N][N],double q[N][N],double r1[N][N],int n) /*QR分解*/ { int i,j,k,r,m; double temp,sum,dr,cr,hr; double ur[N],pr[N],wr[N]; double q1[N][N],emp[N][N]; for(i=1;i 线性系统的求解是数值分析中的一个基本问题。线性系统的求解在电路分析中典型的应用就是用基尔霍夫电压定律和基尔霍夫电流定律求解电路。下面的五个方程组是对一个典型的电路系统的描述：5I1+5I2=V;I3-I4-I5=0;2I4-3I5=0;I1-I2-I3=0;5I2-7I3-2I4=0;当系统确定以后I1, I2，I3，I4，I5前面的系数就确定了。I1，I2，I3，I4，I5的具体数值将随输入电压值V5的变化而改变。求解线性系统解（也就是求解矩阵的解）常用的方法有Gaussian Elimination with Backward Substitution 法，LU Factorization法，LDL T Factorization 法和Choleski 法。其中Gaussian Elimination with Backward Substitution 法最为简单直接，它的思路就是将系数矩阵化简为一个上三角矩阵或者化简为一个下三角矩阵。但是它消耗的资源最多，以一个可描述为5*5矩阵的系统而言它需要5*5*5/3次乘法运算，即大约42次乘法运算。但系统大到100*100时这种方法的计算量非常可观。这种方法不适合处理很大的矩阵。作为Gaussian Elimination with Backward Substitution 法的改进LU Factorization（也叫LU分解法）法的思路是将系统矩阵分解成为一个上三角矩阵和一个下三角矩阵进行运算。这样的话极为方便求解迭代。假设系统为n*n的系统，那么LU分解的方法将计算量由n*n*n/3降低到2*n*n。对于一个100*100的系统LU分解法的计算量仅仅是Elimination with Backward Substitution 法的3%。尽管在决定L矩阵和U矩阵时依然需要n*n*n/3次运算但是系统一旦定下来后是不会有大的改动的，往往是外部条件改变也就是说5I1+5I2=V;I3-I4-I5=0;2I4-3I5=0;I1-I2-I3=0;5I2-7I3-2I4=0;这个系统的系数是不会经常变的，常变的只是外部条件V。LU分解法适应的范围极宽，他对系统没有特殊的要求。当描述系统的矩阵大于6*6时选用LU分解法会更为节省资源，当系统小于6*6时Elimination with Backward Substitution法效率会更高些。LDL T Factorization 法和Choleski 法和LU分解法很像似，基本思路也是将系统矩阵分解成上三角矩阵和下三角矩阵。但是这两种方法要求系统的矩阵必须是正定的，也就是说系统的任意阶行列式必需为正。这样对系统的要求就严格一些。LDL T Factorization 法需要n*n*n/6+n*n-7*n/6次乘法和n*n*n/6-n/6次加减法。Choleski 法则仅仅需要n*n*n/6+n*n/2-2*n/3次乘法和n*n*n/6-n/6次加减法。当系统较大时不失为两种很好的选择。 矩阵分解是指将一个矩阵表示为结构简单或具有特殊性质若干矩阵之积或之和，大体分为三角分解、分解、满秩分解和奇异值分解.矩阵地分解是很重要地一部分内容，在线性代数中时常用来解决各种复杂地问题，在各个不同地专业领域也有重要地作用.秩亏网平差是测量数据处理中地一个难点，不仅表现在原理方面，更表现在计算方面，而应用矩阵分解来得到未知数地估计数大大简化了求解过程和难度. 矩阵地三角分解 如果方阵可表示为一个下三角矩阵和一个上三角矩阵之积，即，则称可作三角分解.矩阵三角分解是以消去法为根据导出地，因此矩阵可以进行三角分解地条件也与之相同，即矩阵地前个顺序主子式都不为，即.所以在对矩阵进行三角分解地着手地第一步应该是判断是否满足这个前提条件，否则怎么分解都没有意义.矩阵地三角分解不是唯一地，但是在一定地前提下，地分解可以是唯一地，其中是对角矩阵.矩阵还有其他不同地三角分解，比如分解和分解，它们用待定系数法来解求地三角分解，当矩阵阶数较大地时候有其各自地优点，使算法更加简单方便.资料个人收集整理，勿做商业用途 矩阵地三角分解可以用来解线性方程组.由于，所以可以变换成，即有如下方程组：资料个人收集整理，勿做商业用途 先由依次递推求得,,……，，再由方程依次递推求得，，……，. 资料个人收集整理，勿做商业用途 必须指出地是，当可逆矩阵不满足时，应该用置换矩阵左乘以便使地个顺序主子式全不为零，此时有：资料个人收集整理，勿做商业用途 这样，应用矩阵地三角分解，线性方程组地解求就可以简单很多了. 矩阵地分解 矩阵地分解是指，如果实非奇异矩阵可以表示为，其中为正交矩阵，为实非奇异上三角矩阵.分解地实际算法各种各样，有正交方法、方法和方法，而且各有优点和不足.资料个人收集整理，勿做商业用途 ．正交方法地分解 正交方法解求分解原理很简单，容易理解.步骤主要有：）把写成个列向量（，，……，），并进行正交化得（，，……，）；) 单位化，并令（，，……，），（，，……，），其中；）. 这种方法来进行分解，过程相对较为复杂，尤其是计算量大，尤其是阶数逐渐变大时，就显得更加不方便.资料个人收集整理，勿做商业用途 ．方法地分解 方法求分解是利用旋转初等矩阵，即矩阵()来得到地，()是正交矩阵，并且(()).()地第行第列 和第行第列为，第行第列和第行第列分别为和，其他地都为.任何阶实非奇异矩阵可通过左连乘()矩阵（乘积为）化为上三角矩阵，另，就有.该方法最主要地是在把矩阵化为列向量地基础上找出和，然后由此把矩阵地一步步向上三角矩阵靠近.方法相对正交方法明显地原理要复杂得多，但是却计算量小得多，矩阵()固有地性质很特别可以使其在很多方面地应用更加灵活.资料个人收集整理，勿做商业用途 ．方法地分解 方法分解矩阵是利用反射矩阵，即矩阵，其中是单位列向量，是正交矩阵，.可以证明，两个矩阵地乘积就是矩阵，并且任何实非奇异矩阵可通过连乘矩阵（乘积为）化为上三角矩阵，则.这种方法首要地就是寻找合适地单位列向量去构成矩阵， 《线性代数与矩阵分析》课程小论文 矩阵分解及其应用 学生姓名：****** 专业：******* 学号：******* 指导教师：******** 2015年12月 Little Paper about the Course of "Linear Algebra and Matrix Analysis" Matrix Decomposition and its Application Candidate:****** Major:********* StudentID:****** Supervisor:****** 12,2015 中文摘要 将特定类型的矩阵拆解为几个矩阵的乘机称为矩阵的分解。本文主要介绍几种矩阵的分解方法，它们分别是矩阵的等价分解、三角分解、谱分解、奇异值分解和 Fitting 分解等。矩阵的分解理论和方法是矩阵分析中重要的部分，在求解矩阵的特征值、解线性方程组以及实际工程中有着广泛的运用。因此，本文将介绍矩阵等价分解、三角分解、奇异值分解的理论运用以及三角分解的工程运用。 关键词：等价分解,三角分解,奇异值分解,运用 Abstract Many particular types of matrix are split into the product of a matrix of several matrices, which is called decomposition of matrix. In this paper, we introduce some methods of matrix decomposition, which are equivalent decomposition, triangular decomposition, spectral decomposition, singular value decomposition, Fitting decomposition and so on. The decomposition theory and method of matrix is an important part of matrix analysis, which is widely used in solving the characteristic value, solving linear equations and the practical engineering. In this paper, we will introduce the theory of matrix equivalence decomposition, triangular decomposition, singular value decomposition and the engineering application of triangular decomposition. Key words：Equivalent Decomposition, Triangular Decomposition, Singular Value Decomposition, Application 矩阵分析 §9. 矩阵的分解 矩阵分解是将一个矩阵分解为比较简单的或具有某种特性的若干矩阵的和或乘积，这是矩阵理论及其应用中常见的方法。由于矩阵的这些特殊的分解形式，一方面反映了原矩阵的某些数值特性，如矩阵的秩、特征值、奇异值等；另一方面矩阵分解方法与过程往往为某些有效的数值计算方法和理论分析提供了重要的依据，因而使其对分解矩阵的讨论和计算带来极大的方便，这在矩阵理论研究及其应用中都有非常重要的理论意义和应用价值。 这里我们主要研究矩阵的三角分解、谱分解、奇异值分解、满秩分解及特殊矩阵的分解等。 一、矩阵的三角分解——是矩阵的一种有效而应用广泛的分解法。 将一个矩阵分解为酉矩阵（或正交矩阵）与一个三角矩阵的乘积或者三角矩阵与三角矩阵的乘积，这对讨论矩阵的特征、性质与应用必将带来极大的方便。首先我们从满秩方阵的三角分解入手，进而讨论任意矩阵的三角分解。 定义1 如果(1,2,,)ii a i n = 均为正实数，()(,1,2,1;∈<=- ij a C R i j i n 1,2,),=++ j i i n 则上三角矩阵 1112122200 ?? ? ?= ? ??? n n nn a a a a a R a 称为正线上三角复（实）矩阵，特别当1(1,2,,)ii a i n == 时，R 称为单位上三角复（实）矩阵。 定义2如果(1,2,,)ii a i n = 均为正实数，()(,1,2,1;∈>=- ij a C R i j i n 1,2,),=++ j i i n 则下三角矩阵 1121 221 2 000?? ? ?= ? ??? n n nn a a a L a a a 浅谈矩阵的LU 分解和QR 分解及其应用 基于理论研究和计算的需要，往往有必要把矩阵分解为具有某种特性的矩阵之积，这就是我们所说的矩阵分解. 本文将介绍两种常用的矩阵分解方法，以及其在解线性方程组及求矩阵特征值中的应用. 1.矩阵的LU 分解及其在解线性方程组中的应用 1.1 高斯消元法 通过学习，我们了解到利用Gauss 消去法及其一些变形是解决低阶稠密矩阵方程组的有效方法.并且近些年来利用此类方法求具有较大型稀疏矩阵也取得了较大进展.下面我们就通过介绍Gauss 消去法，从而引出矩阵的LU 分解及讨论其对解线性方程组的优越性. 首先通过一个例子引入： 例1,解方程组 (1.1) (1. 2)(1.3) 解.1Step (1.1)(2)(1.3)?-+ 消去(1.3)中未知数,得到 23411x x --=-(1.4) 2Shep . (1.2)(1.4)+ 消去(1.4)中的未知数2 x 有12323364526x x x x x x ++=-=-=-????? 显然方程组的解为* x =123?? ? ? ? ?? 上述过程相当于 111604152211?? ?- ? ?-??~111604150411?? ?- ? ?---??~111 604150026?? ? - ? ? --?? 2-（）+ ()i i r 表示矩阵的行 由此看出，消去法的基本思想是：用逐次消去未知数的方法把原方程化为与其等价的三角方程组. 下面介绍解一般n 阶线性方程组的Gauss 消去法. 设111n n1nn a a a a A ?? ?= ? ??? 1n x X x ?? ?= ? ??? 1n b b b ?? ? = ? ??? 则n 阶线性方程组 AX b =(1.5) 并且A 为非奇异矩阵. 通过归纳法可以将AX b =化为与其等价的三角形方程，事实上： 及方程(1.5)为()()1 1 A X b =,其中 ()1A A =()1 b b = (1) 设(1) 11 0a ≠，首先对行计算乘数() ()1 1i11 11i a m m =.用1i m -乘(1.5)的第一个方程加到第 ()2,3,,i i n =?个方程上.消去方程(1.5)的第2个方程直到第n 个方程的未知数1x . 得到与(1.5)等价的方程组()()()11n 12n 111nn 0a a x x a ????? ? ? ? ? ? ?????? =()()112n b b ?? ? ? ??? 简记作 ()()22A b =(1.6) 其中()()() ()()()211211111 ij ij i ij i i i a m b b m a a b =-=- (2) 一般第()11k k n ≤≤-次消去，设第1k -步计算完成.即等价于 ()()k k A X b = (1.7) 且消去未知数121,,,k x x x -?.其中() ()()() ()() ()()()()11 1 11 12 12222 2k k k k kk kn k nk nna n n a a a a a A a a a a ?? ? ? ? ? = ? ? ? ?? ? 基于矩阵分解的矩阵填充算法研究实现一．矩阵填充应用 矩阵填充理论主要有两个应用方向：一个是视频去噪主要应用于视频或图像的处理过程，其原理是通过填充像素实现图像的恢复；另一个是协同过滤，主要应用于推荐系统的一种模型，其原理是通过分析用户的历史行为数据，给用户预测推荐，本文主要介绍协同过滤算法及实现。 二．协同过滤问题描述 使用协同过滤进行推荐的一个著名的例子是Netflix电影推荐系统。在网站有很多用户和影片，但是不是所有的用户都看过所有的影片，并且也不是所有看过的影片用户都会打分。现在我们使用协同过滤预测用户未看过的影片的评分，进而给用户做出推荐。 假设用一个“用户-影片”的矩阵来描述用户的评分记录如下表： 使用矩阵填充算法填充上面表格中缺失的信息，预测用户未看过的影片的评分，根据预测评分给用户做出推荐。 三．协同过滤算法概述 协同过滤算法分类如下 协同过滤推荐算法分类图 3.1基于内存的协同过滤推荐 基于内存的协同过滤推荐算法分为基于用户的协同过滤推荐和基于用户的协同过滤推荐。基于用户的协同过滤推荐基于假设：相似的用户会有相似的喜好，其原理是通过寻找相似用户来预测用户对未知物品的评分，将评分较高的项目推荐给目标用户。基于项目的协同过滤基于的假设：用户喜欢的项目都是同类型相似的项目，也就是用户喜欢与自己喜好项目相似度高的项目。基于内存的协同过滤推荐系统实现主要三个步骤：收集用户偏好，创建用户-评分矩阵；最近邻搜索；计算预测评分并推荐。 3.2基于模型的协同过滤推荐 基于模型的协同过滤推荐是通过数据挖掘、机器学习、深度学习的方法利用用户的历史行为数据进行建模，根据模型训练的结果进行相应的推荐。基于内存的协同过滤算法虽然易于理解和实现，但当用户-评分矩阵的规模逐渐增大且稀疏度增高时，该类算法的效果并不理想，而基于模型的协同过滤推荐算法能够很好的缓解稀疏性问题。按照机器学习训练方法的不同可以将基于模型的协同过滤推荐算法划分为基于矩阵分解的推荐、基于贝叶斯分类器的推荐、基于聚类模型的推荐以及基于图模型的推荐等。 矩阵分解及其简单应用 x=b，即有如下方程组：Ly=bUx=y 先由Ly=b依次递推求得y1, y2,……，yn，再由方程Ux=y依次递推求得 xn，xn-1，……， x1、必须指出的是，当可逆矩阵A不满足?k≠0时，应该用置换矩阵P左乘A以便使PA的n个顺序主子式全不为零，此时有： Ly=pbUx=y 这样，应用矩阵的三角分解，线性方程组的解求就可 以简单很多了。2、矩阵的QR分解矩阵的QR分解是指，如果实 非奇异矩阵A可以表示为A=QR，其中Q为正交矩阵，R为实非奇 异上三角矩阵。QR分解的实际算法各种各样，有Schmidt正交方法、Givens方法和Householder方法，而且各有优点和不足。2、1．Schmidt正交方法的QR分解Schmidt正交方法解求QR分解原 理很简单，容易理解。步骤主要有：1）把A写成m个列向量a= （a1，a2，……，am），并进行Schmidt正交化得=（α1， α2，……，αm）；2) 单位化，并令Q=（β1，β2，……，βm），R=diag（α1， α2，……，αm）K，其中a=K；3）A=QR、这种方法来进行QR分解，过程相对较为复杂，尤其是计算量大，尤其是阶数逐渐变大时，就显得更加不方便。2、2．Givens方法的QR分解Givens方 法求QR分解是利用旋转初等矩阵，即Givens矩阵Tij(c,s)来得 到的，Tij(c,s)是正交矩阵，并且det(Tij(c,s))=1。Tij(c,s)的第i行第i列和第j行第j列为cos，第i行第j列和第j行第i 列分别为sin和-sin，其他的都为0、任何n阶实非奇异矩阵A可通过左连乘Tij(c,s)矩阵（乘积为T）化为上三角矩阵R，另 Q=T-，就有A=QR。该方法最主要的是在把矩阵化为列向量的基础上找出c和s，然后由此把矩阵的一步步向上三角矩阵靠近。Givens方法相对Schmidt正交方法明显的原理要复杂得多，但是却计算量小得多，矩阵Tij(c,s)固有的性质很特别可以使其在很多方面的应用更加灵活。2、3．Householder方法的QR分解Householder方法分解矩阵是利用反射矩阵，即Householder矩阵H=E-2uuT，其中u是单位列向量，H是正交矩阵，detH=-1。可以证明，两个H矩阵的乘积就是Givens矩阵，并且任何实非奇异矩阵A可通过连乘Householder矩阵（乘积为S）化为上三角矩阵R，则A= QR。这种方法首要的就是寻找合适的单位列向量去构成矩阵H，过程和Givens方法基本相似，但是计算量要小一些。矩阵的QR分解可以用来解决线性最小二乘法的问题，也可以用来降低矩阵求逆的代价。矩阵的求逆是件不小的工程，尤其是阶数慢慢变大的情况时，而用先把矩阵QR分解成正交矩阵和上三角矩阵，就容易多了，况且正交矩阵的转置就是逆，这一点是其他的矩阵分解无法比拟的。在解求线性方程组中，如果系数矩阵的阶数比较大，可以利用QR分解来使计算简单化。另外，QR分解考虑的是n阶矩阵，其他的矩阵是不能用这种方法进行分解，由于QR 分解的这一前提条件，使得下面提到的满秩矩阵分解和奇异值分解就有了其特殊的意义。3、满秩分解满秩分解也称最大秩分 矩阵分解是指根据一定的原理用某种算法将一个矩阵分解成若干个矩阵的乘积。常见的矩阵分解有可逆方阵的三角（LU）分解、任意满秩矩阵的正交三角（QR）分解、对称正定矩阵的Cholesky分解，以及任意方阵的Schur分解、Hessenberg分解、EVD分解、SVD分解、GMD分解等。 (1) 可逆方阵的LU分解 矩阵的LU分解就是将一个矩阵表示为一个交换下三角矩阵和一个上三角矩阵的乘积形式。线性代数中已经证明，只要方阵A是非奇异的（即可逆的），LU分解总是可以进行的。 当L为单位下三角矩阵而U为上三角矩阵时，此三角分解称为杜利特(Doolittle)分解。当L为下三角矩阵而U为单位上三角矩阵时，此三角分解称为克劳特(Crout)分解。显然，如果存在，矩阵的三角分解不是唯一的。 （PS：方阵A可唯一地分解为A=LDU(其中L，U分别为单位下，上三角矩阵，D为对角矩阵)的充分必要条件为A的前n-1个顺序主子式都不为0。特别：对n阶对称正定矩阵，存在一个非奇异下三角矩阵L，使得A=LL'成立。） MATLAB提供的lu函数用于对矩阵进行LU分解，其调用格式为：[L,U]=lu(X)：产生一个上三角阵U和一个变换形式的下三角阵L(行交换)，使之满足X=LU。注意，这里的矩阵X必须是方阵。 [L,U,P]=lu(X)：产生一个上三角阵U和一个下三角阵L以及一个置换矩阵P，使之满足PX=LU。当然矩阵X同样必须是方阵。 (2) 满秩矩阵的QR分解 对矩阵X进行QR分解，就是把X分解为一个正交矩阵Q和一个上三角矩阵R的乘积形式。QR分解只能对方阵进行。MATLAB的函数qr可用于对矩阵进行QR分解，其调用格式为： [Q,R]=qr(X)：产生一个一个正交矩阵Q和一个上三角矩阵R，使之满足X=QR。 [Q,R,E]=qr(X)：产生一个一个正交矩阵Q、一个上三角矩阵R以及一个置换矩阵E，使之满足XE=QR。 (3) 对称正定矩阵的Cholesky分解 如果矩阵X是对称正定的，则Cholesky分解将矩阵X分解成一个下三角矩阵和上三角矩阵的乘积。设上三角矩阵为R，则下三角矩阵为其转置，即X=R'R。MATLAB函数chol(X)用于对矩阵X进行Cholesky 分解，其调用格式为： R=chol(X)：产生一个上三角阵R，使R'R=X。若X为非对称正定，则输出一个出错信息。 [R,p]=chol(X)：这个命令格式将不输出出错信息。当X为对称正定的，则p=0，R与上述格式得到的结果相同；否则p为一个正整数。如果X为满秩矩阵，则R为一个阶数为q=p-1的上三角阵，且满足R'R=X(1:q,1:q)。 (4) 任意方阵的Schur分解 任意一个n阶方阵X可以分解为X=URU'，其中U为酉矩阵，R为上三角schur矩阵且其主对角线上的元素为X的特征值。 随着互联网的普及和电子商务的发展，推荐系统逐渐成为电子商务IT 技术的一个重要研究内容，得到越来越多研究者的关注[1] 。例如，Amazon 、CDNOW 、e － Bay 、京东等电子商务网站，都开始逐渐引入了各种形式的推荐系统。 协同过滤推荐是当今被广泛使用的推荐技术[4]，其中，潜在因素模型（latent factor models ）是协同过滤推 荐使用的技术之一。潜在因素模型是通过分析消费历史记录来推测潜在的发展趋势。矩阵分解算法（matrix factorization ）[2] 是潜在因素模型中被广泛使用的技术之 一。但是，随着网站消费记录的增多，传统的矩阵分解算法不能高效地为大规模消费记录构建潜在因素模型，无法实现推荐系统的实时性。本文针对大规模历史消费记录，提出了高效地特征矩阵分解算法，该算法是 收稿日期：2012-12-21 作者简介：张海建（1978-），男，北京人，硕士，讲师，主要研究方向：计算机软件，数据库系统。 分布式矩阵分解算法在推荐系统中的研究与应用 张海建 （北京信息职业技术学院，北京100018） 摘要：随着互联网信息技术的高速发展，越来越多的人开始接触网络。网上购物成为当今社会的购物的主要方式之一，各大电子商务网站每天都有大量的消费者购买及浏览记录。电子商业往往希望通过分析大量的网站购买记录以及消费者浏览记录，对消费者提供有价值地商品推荐，以便于提高销售量。矩阵分解广泛地应用在推荐系统中的协同过滤算法中，但是，随着网站数据量的增大，传统的矩阵分解算法不能有效地处理这些大规模海量数据。本文针对推荐系统中大规模的网站数据，提出了基于云平台的分布式矩阵分解算法，该算法能够分布式完成推荐系统中的协同过滤过程。实验结果表明，本文提出的算法能够高效地完成推荐系统中的协同过滤，并且，该算法具有很好的可扩展性。关键词：推荐系统；分布式；云平台；mapReduce ；矩阵分解；协同过滤中文分类号：ＴＰ３ 文献标识码：Ａ 文章编号：1001-7119（2013）12-0151-03 The Research and Application of Distributed Matrix Factorization Algorithm in Recommend System Zhang Haijian (Beijing Information Technology College,Beijing 100018,China) Abstract:With the high-speed development of internet information technology,more and more people begin to get in touch with internet.On-line shopping is becoming one of the main shopping methods,several big e-commerce sites pro －duce big amount of consumer purchasing and browsing records.E-commerce sites usually hope to analyze these records and provide to the consumers with valuable commodity recommendation,in order to promote sales.Matrix factorization is popularly used in collaborative filtering algorithm in recommendation system.However,with the incensement of web data,traditional matrix factorization could not deal with this huge amount of data.In this paper,focusing on big scale website data,we propose distributed matrix factorization based on Cloud computing platform.Through the experimental results,the algorithm in this paper could complete collaborative filtering in recommendation system effectively,and it has good scalability. Key words ：recommender systems;distributed;cloud platforms;mapReduce;matrix decomposition,and collaborative filtering 第29卷第12期 2013年12月 科技通报 BULLETIN OF SCIENCE AND TECHNOLOGY Vol.29No.12Dec.2013几种矩阵分解方法的对比
矩阵分解及其简单应用
矩阵分解及其应用
第四章 矩阵分解
第四章 矩阵分解
§4.1: 矩阵的满秩分解 §4.2: 矩阵的正交三角分解 §4.3: 矩阵的奇异值分解 §4.4: 矩阵的极分解 §4.5: 矩阵的谱分解
矩阵分解前言
矩阵分解定义: 将一个已知矩阵表示为另一些较为简单或 较为熟悉的矩阵的积(或和)的过程称为矩阵分解. 例:(1)对任意n阶正规矩阵A,存在酉阵U∈Un×n使 A=Udiag(λ1,…,λn)U*, 其中λ1,…,λn为A的所有特征值的任一排列. (2)对任意n阶正定矩阵A,存在可逆阵Q∈Cnn×n使A=Q*Q,或存 在唯一正定阵B使A=BB. 矩阵分解意义:有利于研究已知的矩阵. 例如,利用正定阵A的平方根B为正定阵可证: 对任意Hermite阵H,AH或HA都有实特征值.
1
( AH～(A1/2)-1AHA1/2=A1/2HA1/2∈Hn×n )
2
初等变换与初等矩阵(p73)
三类初等变换: (行(列)变换←→左(右)乘) (1)将矩阵A的两行互换等价于用第一类初等矩阵P(i,j)左 乘A; (2)将矩阵A的第i行乘以k≠0等价于用第二类初等矩阵 P(i(k))=diag(1,…,1,k,1,…,1)左乘A. (3)将矩阵A的第j行乘以k≠0后再加到第i行等价于左乘第 三类初等矩阵P(i,j(k)).
P (i , j ) =
?1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1 0 1 1 1 0 1 1
初等变换与初等矩阵举例
?1 ?? 1 4 7 ? ? 1 4 7 ? ? 0 1 ?? 2 5 8 ? = ? 3 6 9 ? ; ? ?? ? ? ? ? 1 0 ?? 3 6 9 ? ? 2 5 8 ? ? ?? ? ? ? ?1 4 7??1 ? ? 1 7 4? ? 2 5 8?? 0 1? = ? 2 8 5? ? ?? ? ? ? ? 3 6 9?? 1 0? ? 3 9 6? ? ?? ? ? ?
?1 ??1 4 7? ? 1 4 7 ? ? ?? ? ? ? 0.2 ? ? 2 5 8 ? = ? 0.4 1 1.6 ? ; ? ? 1?? 3 6 9 ? ? 3 6 9 ? ? ?? ? ? ?
?1 4 7??1 ? ? 1 4 7 / 9? ? ?? ? ? ? ? 2 5 8?? 1 ? = ? 2 5 8/9? ? 3 6 9?? 1/ 9 ? ? 3 6 1 ? ? ?? ? ? ?
---- i ---- j
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1?
P (i , j ( k )) =
?1 ? ? ? ? ? ? ? ? ? ?
1
k 1
? ? ? ? ---? ? ? ---? ? ? 1?
i j
3
?1 ?? 1 2 3? ? 1 2 3 ? ? ?? ? ? ? ? ?4 1 ? ? 4 5 6 ? = ? 0 ?3 ?6 ? ; ? 1?? 7 8 9? ? 7 8 9 ? ? ?? ? ? ?
?3 ? ? 1 2 0 ? ? 1 2 3??1 ? ?? ? ? ? ? 4 5 6?? 1 ? = ? 4 5 ?6 ? ?7 8 9?? 1 ? ? 7 8 ?12 ? ? ?? ? ? ?
4
初等变换与初等矩阵的性质
3类初等矩阵都是可逆的(行列式不为0). 将A依次作初等矩阵P1,…,Pr对应的行(列)初等变换等价 于左(右)乘A以可逆矩阵Pr…P1(P1…Pr). 可适当选第一类初等矩阵的乘积P使PA(AP)的行(列)是A 的行(列)的任意排列; 可适当选第三类初等矩阵 P(i,j(k))中的k使P(i,j(k))A的(i,j)元变为0; 可适当选第二类初等矩阵P(i(k))中的k使P(i(k))A的非 零(i,i)元变为1. 存在初等矩阵的乘积P和Q,使PAQ= ,其中r=rankA.
初等变换与初等矩阵的性质续
命题:设A∈Crm×n前r列线性无关,则用初等行变换可把A变为
? Er ? ? 0 ?1 ? ? D? ? = ? ? 0 ? ? ? ? ? ? 1 1 * * * * *? ? *? *? ? *? ? ? ? ?
一般地,?A∈Crm×n都存在m,n阶可逆阵P和Q使PAQ=
5
证:因前r列线性无关,故用第一类初等矩阵左乘可使A的 (1,1)元≠0. 再用第二类初等矩阵左乘可使a11=1; 最后用若干第三类初等矩阵左乘可使A的第一列=e1. 因前2列线性无关,故新的第2列与e1线性无关且≠0, 故用第一类行变换可使(2,2)元≠0,…可使A的第2列=e2. ….可使A的第r列=er.此时空白处必为0元.
安徽大学 章权兵
1矩阵的分解
浅谈矩阵的LU分解和QR分解及其应用
基于矩阵分解的矩阵填充算法研究实现
矩阵分解及其简单应用
矩阵分解
分布式矩阵分解算法在推荐系统中的研究与应用_张海建
相关主题
文本预览