矩阵三角分解法完整版实用资料Word格式文档下载.docx
《矩阵三角分解法完整版实用资料Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《矩阵三角分解法完整版实用资料Word格式文档下载.docx（86页珍藏版）》请在冰点文库上搜索。
u[i][j]=1;
if（j-i>
=2）
if（i-j==1）
l[i][j]=a[i][j];
if（i-j>
}
for（j=1;
if（j-i==1&
&
l[i][j-1]!
=0）
u[i][j]=a[i][j]/l[i][j-1];
l[i][j]=a[i][j]-a[i][j-1]*u[i-1][j];
printf（"
l矩阵：
\n"
）;
}{for（j=0;
j++）{printf（"
%.2f"
l[i][j]）;
}printf（"
printf（"
u矩阵：
for（i=0;
i++）{for（j=0;
u[i][j]）;
i++）{if（i==0）y[0]=f[0]/l[0][0];
elsey[i]=（f[i]-l[i][i-1]*y[i-1]）/l[i][i];
y[%d]=%.2f"
i+1,y[i]）;
\n\n"
for（i=N-1;
i>
=0;
i--）{if（i==N-1）x[N-1]=y[N-1];
elsex[i]=y[i]-u[i][i+1]*x[i+1];
x[%d]=%.4f"
i+1,x[i]）;
第21卷第2期 淮 北 煤 师 院 学 报 Vol.21 No.2 2000年6月 JournalofHuaibeiCoalIndustryTeachersCollege Jun.2000
求矩阵秩分解的初等变换法及其应用江旭光
（安徽省直职工大学,
摘 要:
本文给出了秩为rA.
关键词:
分类号:
C 文章编号:
1000-2227（200002-0071-73
众所周知,设A是m×
n矩阵,秩A=r,则存在可逆的
m×
m矩阵P,n×
n矩阵Q,使Ir 0PAQ=,此式称为矩阵A的秩分解[1].对上式一般的教科书中从未给出P、Q的具0 体求法,P、Q的初等变换求法如下:
下面利用上述P、Q讨论线性方程组解的问题.
设有齐次线性方程组
（2 AX=0
式中,A同（1式.
设Q=（a1,a2,…,an,则由（1得,Aar+
1=0,…,Aan=0,ar+1,…,an是（2的解向量,又秩A=r,Q可逆,得ar+1,ar+2,…,an是齐线性方程组（2的一个基础解系.
现考虑一般线性方程组
AX=b
收稿日期:
2000—03—27
男,浙江宁波人,学士,讲师作者简介:
江旭光（1956- （3
72淮 北 煤 师 院 学 报 2000
年其中b=（b1,b2,…,bmT,X=（x1,x2,…,xnT,A如上
.
第2期 江旭光
求矩阵秩分解的初等变换法及其应用73故该方程组通解为
η=η 0+k1a3+k2a4（k3,k4为任意实数
参考文献:
[1]张禾瑞,郝钅丙新.高等代数（第三版[M].北京:
高等教育出版社,1983.
TheElementaryOperationsMethodofRankDecompsionandItsApplication
JIANGXu2guang
（StaffandWorkersUniversitySubordinatetoAuhuiProvince,Hefei230001
Abstract:
Inthispaper,aelementraryoperationsmethodisgivenforfindingfactormatrixinrankdecompositionofmatrixAwithrankrandappliedtosolvelinearequations.
Keywrods:
rankdecomposition;
elementaryoperations;
solvelinearequations
矩阵分解在电网节点阻抗矩阵形成中的应用
张静亮
控制科学与工程学院模式识别与智能系统2021010216
摘要：
在电力系统计算中，节点阻抗矩阵元素的计算相当复杂，不可能从网络的接线图和支路参数直接求出，但是通过对节点导纳矩阵求其逆矩阵可以得到。
在此利用矩阵分解中的LR分解、LDR分解对线性方程组求解，可以得到节点导纳矩阵的逆矩阵即节点阻抗矩阵。
一．节点阻抗矩阵：
用导纳表示的节点电压方程的基本形式为I=YU，Y为nxn阶节点导纳矩阵，将前式两边左乘Y的逆矩阵Y—1，可得Y—1I=U，令Y—1=Z，则ZI=U，Z为nxn阶的节点阻抗矩阵，是节点导纳矩阵的逆矩阵。
将ZI=U改写成：
i=1，2，……，n
如果在节点i注入单位电流，其余节点（j≠i）注入电流都为零，则上式第i个方程简化为Ui=ZiiIii，即自阻抗Zii的物理意义是除去节点i外其余节点都没有注入电流，仅在节点i注入单位电流时，节点i上的电压。
如果在节点i注入单位电流，其余节点（j≠i）注入电流都为零，则上式第j个方程简化为Uj=ZjiIii，即互阻抗Zji的物理意义是除去节点i外其余节点都没有注入电流，仅在节点i注入单位电流时，节点j上的电压。
并且Zji=Zij。
当在节点i注入电流时，网络中除参考节点的电压外其余节点的电压都不为零，因此互阻抗一般不为零。
由互阻抗的性质决定了节点阻抗矩阵是一个对称矩阵，但不是稀疏矩阵而是满矩阵。
二．节点阻抗矩阵的求解：
节点阻抗矩阵是节点导纳矩阵的逆矩阵，但在较复杂的网络中不能像节点导纳矩阵那样按照定义直接求取自阻抗和互阻抗。
节点阻抗矩阵可以利用节点导纳矩阵求逆的方法形成。
线性代数中任意一种矩阵求逆的数学方法都可以应用，如解线性方程组求逆法、消元求逆法等，但在电力系统计算中比较常用的方法是解线性代数方程组的方法。
因为Y—1=Z，所以YZ=I，式中：
I为单位矩阵，Y中的各元素已知。
将上式展开得：
由矩阵运算可得n组n元联立方程：
…….;
每解一组上式中的线性代数方程，可得节点阻抗矩阵中的一列元素，求解n组后即形成了完整的节点阻抗矩阵。
线性代数方程组求解的数学方法很多，电力系统计算中常用的有高斯消去法及由此派生的因子表法、三角分解法、分块矩阵法等。
由节点导纳矩阵求逆形成节点阻抗矩阵的方法，就是求解上式所列的n组线性代数方程组，这些方程组中有一个共同点:
节点导纳矩阵Y是不变的系数矩阵，只有常数项矩阵在变化，为了能够方便地多次求解这类方程组，就可以利用三角分解法。
设方程组AX=B需要多次求解，每次仅改变其常数项B，而系数矩阵A是不变的，三角分解的具体方法是将系数矩阵A分解为上三角矩阵和下三角矩阵的乘积。
在电力系统中常用的方法有：
LR分解、LDR分解法，下面简介分解的原理。
三角分解是指任何一个方阵A都可分解为单位下三角矩阵L和上三角矩阵R的乘积Ａ＝ＬＲ，设矩阵L的所有对角元素都为1，Ｌ，Ｒ的展开式为：
;
则此二矩阵的乘积即对应系数矩阵Ａ中的各元素。
如ａ１１＝ｒ１１，ａ１２＝ｒ１２，ａ２１＝l２１ｒ１１，ａ２２＝l２１ｒ１２＋ｒ２２，如果l２１＝ａ２１／ｒ１１，ｒ１２＝ａ１２，ｒ２２＝ａ２２－l２１ｒ１２至此已分解出二阶的Ｌ，Ｒ矩阵，可依次类推。
一般Ｌ和Ｒ的元素可用递推公式计算，可求得Ａ三角分解后的递推公式为：
k=1,2,……,n;
j=1,2,……,k-1
j=k,k+1,…n
矩阵分解为Ｌ和R后，上三角矩阵R的元素都不等于零，因此又可把R分解为对角矩阵D和对角元素为1的上三角矩阵U的乘积R=DU，则
A=LDU
如果A是对称矩阵，在Ａ＝LDU中有U=LT的关系，则矩阵Ａ可进一步分解为
A=LDLT
式中矩阵元素表达式为：
k=1,2,…..,n
j=1,2,…..,k-1
下面介绍利用矩阵三角分解后求解方程组ＡＸ＝Ｂ的基本方法。
设Ａ已经分解为Ｌ，Ｄ，则ＡＸ＝Ｂ变为ＬＤLTＸ＝Ｂ，对上式可采用依次求解的方法：
令Ｚ＝ＤLTＸ，则LZ=B，解出矩阵Z；
再令W=LTＸ，则DW=Z，解出矩阵W；
最后由LTＸ=W解出矩阵X。
虽然这种先进行三角分解，然后依次求解的方法看起来较复杂，但都是用三角矩阵在求解。
在这类问题时，仅需要对节点导纳矩阵Y作一次三角分解即可。
三．应用总结：
在上述节点阻抗矩阵的求解中主要用到了矩阵论中的矩阵分解的部分知识，主要是LR分解以及ＬＤＲ分解。
此外还涉及了矩阵求逆，稀疏矩阵等部分矩阵知识。
矩阵ＬＲ分解的定义为，设Ａ∈Ｃｎｘｎ，如果Ａ可分解成Ａ＝ＬＲ，其中L是对角元素为1的下三角矩阵（称为单位下三角矩阵），R是上三角矩阵，则称之为A的Doolittle分解。
如果A可分解为A=ＬＤＲ，其中Ｌ是单位下三角矩阵，Ｄ是对角矩阵，Ｒ是单位上三角矩阵，则称之为Ａ的ＬＤＲ分解。
由A的Doolittle分解A=LR，得
于是
（j=1,2,….n）,
（i=1,2,…..n）,
（j=k,k+1,….,n;
k=2,3,….,n）,
（i=k+1,k+2,….,n;
k=2,….,n）
由上式可导出求A的Doolittle分解的紧凑计算格式为
（j=1，2，…..,n）,
（i=2,3,……,n）,
（j=k,k+1,……,n;
k=2,3,….,n）,
（i=k+1,…,n;
k=2,3,…..,n）.
综上所述，在线性代数方程求解过程中应用矩阵分解，把矩阵转化为形式比较简单或具有某种特性的一些矩阵的乘积，是比较方便和直观的。
因为这些分解式的特殊形式一方面能明显地反映出原矩阵的某些数值特征，另一方面，分解的方法与过程往往提供了某些有效的计算方法和理论分析根据，特别是应用在电力系统的n节点情况下更显现出了矩阵分解应用的便利。
矩阵的奇异值分解（SVD）及其应用
版权声明：
本文由LeftNotEasy发布于,本文可以被全部的转载或者部分使用，但请注明出处，如果有问题，请联系
前言：
上一次写了关于PCA与LDA的文章，PCA的实现一般有两种，一种是用特征值分解去实现的，一种是用奇异值分解去实现的。
在上篇文章中便是基于特征值分解的一种解释。
特征值和奇异值在大部分人的印象中，往往是停留在纯粹的数学计算中。
而且线性代数或者矩阵论里面，也很少讲任何跟特征值与奇异值有关的应用背景。
奇异值分解是一个有着很明显的物理意义的一种方法，它可以将一个比较复杂的矩阵用更小更简单的几个子矩阵的相乘来表示，这些小矩阵描述的是矩阵的重要的特性。
就像是描述一个人一样，给别人描述说这个人长得浓眉大眼，方脸，络腮胡，而且带个黑框的眼镜，这样寥寥的几个特征，就让别人脑海里面就有一个较为清楚的认识，实际上，人脸上的特征是有着无数种的，之所以能这么描述，是因为人天生就有着非常好的抽取重要特征的能力，让机器学会抽取重要的特征，SVD是一个重要的方法。
在机器学习领域，有相当多的应用与奇异值都可以扯上关系，比如做featurereduction的PCA，做数据压缩（以图像压缩为代表）的算法，还有做搜索引擎语义层次检索的LSI（LatentSemanticIndexing）
另外在这里抱怨一下，之前在XX里面搜索过SVD，出来的结果都是俄罗斯的一种狙击枪（AK47同时代的），是因为穿越火线这个游戏里面有一把狙击枪叫做SVD，而在Google上面搜索的时候，出来的都是奇异值分解（英文资料为主）。
想玩玩战争游戏，玩玩COD不是非常好吗，玩山寨的CS有神马意思啊。
国内的网页中的话语权也被这些没有太多营养的帖子所占据。
真心希望国内的气氛能够更浓一点，搞游戏的人真正是喜欢制作游戏，搞DataMining的人是真正喜欢挖数据的，都不是仅仅为了混口饭吃，这样谈超越别人才有意义，中文文章中，能踏踏实实谈谈技术的太少了，改变这个状况，从我自己做起吧。
前面说了这么多，本文主要关注奇异值的一些特性，另外还会稍稍提及奇异值的计算，不过本文不准备在如何计算奇异值上展开太多。
另外，本文里面有部分不算太深的线性代数的知识，如果完全忘记了线性代数，看本文可能会有些困难。
一、奇异值与特征值基础知识：
特征值分解和奇异值分解在机器学习领域都是属于满地可见的方法。
两者有着很紧密的关系，我在接下来会谈到，特征值分解和奇异值分解的目的都是一样，就是提取出一个矩阵最重要的特征。
先谈谈特征值分解吧：
1）特征值：
如果说一个向量v是方阵A的特征向量，将一定可以表示成下面的形式：
这时候λ就被称为特征向量v对应的特征值，一个矩阵的一组特征向量是一组正交向量。
特征值分解是将一个矩阵分解成下面的形式：
其中Q是这个矩阵A的特征向量组成的矩阵，Σ是一个对角阵，每一个对角线上的元素就是一个特征值。
我这里引用了一些参考文献中的内容来说明一下。
首先，要明确的是，一个矩阵其实就是一个线性变换，因为一个矩阵乘以一个向量后得到的向量，其实就相当于将这个向量进行了线性变换。
比如说下面的一个矩阵：
它其实对应的线性变换是下面的形式：
因为这个矩阵M乘以一个向量（x,y）的结果是：
上面的矩阵是对称的，所以这个变换是一个对x，y轴的方向一个拉伸变换（每一个对角线上的元素将会对一个维度进行拉伸变换，当值>
1时，是拉长，当值<
1时时缩短），当矩阵不是对称的时候，假如说矩阵是下面的样子：
它所描述的变换是下面的样子：
这其实是在平面上对一个轴进行的拉伸变换（如蓝色的箭头所示），在图中，蓝色的箭头是一个最主要的变化方向（变化方向可能有不止一个），如果我们想要描述好一个变换，那我们就描述好这个变换主要的变化方向就好了。
反过头来看看之前特征值分解的式子，分解得到的Σ矩阵是一个对角阵，里面的特征值是由大到小排列的，这些特征值所对应的特征向量就是描述这个矩阵变化方向（从主要的变化到次要的变化排列）
当矩阵是高维的情况下，那么这个矩阵就是高维空间下的一个线性变换，这个线性变化可能没法通过图片来表示，但是可以想象，这个变换也同样有很多的变换方向，我们通过特征值分解得到的前N个特征向量，那么就对应了这个矩阵最主要的N个变化方向。
我们利用这前N个变化方向，就可以近似这个矩阵（变换）。
也就是之前说的：
提取这个矩阵最重要的特征。
总结一下，特征值分解可以得到特征值与特征向量，特征值表示的是这个特征到底有多重要，而特征向量表示这个特征是什么，可以将每一个特征向量理解为一个线性的子空间，我们可以利用这些线性的子空间干很多的事情。
不过，特征值分解也有很多的局限，比如说变换的矩阵必须是方阵。
（说了这么多特征值变换，不知道有没有说清楚，请各位多提提意见。
）
2）奇异值：
下面谈谈奇异值分解。
特征值分解是一个提取矩阵特征很不错的方法，但是它只是对方阵而言的，在现实的世界中，我们看到的大部分矩阵都不是方阵，比如说有N个学生，每个学生有M科成绩，这样形成的一个N*M的矩阵就不可能是方阵，我们怎样才能描述这样普通的矩阵呢的重要特征呢？
奇异值分解可以用来干这个事情，奇异值分解是一个能适用于任意的矩阵的一种分解的方法：
假设A是一个M*N的矩阵，那么得到的U是一个M*M的方阵（里面的向量是正交的，U里面的向量称为左奇异向量），Σ是一个M*N的矩阵（除了对角线的元素都是0，对角线上的元素称为奇异值），V’（V的转置）是一个N*N的矩阵，里面的向量也是正交的，V里面的向量称为右奇异向量），从图片来反映几个相乘的矩阵的大小可得下面的图片
那么奇异值和特征值是怎么对应起来的呢？
首先，我们将一个矩阵A的转置*A，将会得到一个方阵，我们用这个方阵求特征值可以得到：
这里得到的v，就是我们上面的右奇异向量。
此外我们还可以得到：
这里的σ就是上面说的奇异值，u就是上面说的左奇异向量。
奇异值σ跟特征值类似，在矩阵Σ中也是从大到小排列，而且σ的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。
也就是说，我们也可以用前r大的奇异值来近似描述矩阵，这里定义一下部分奇异值分解：
r是一个远小于m、n的数，这样矩阵的乘法看起来像是下面的样子：
右边的三个矩阵相乘的结果将会是一个接近于A的矩阵，在这儿，r越接近于n，则相乘的结果越接近于A。
而这三个矩阵的面积之和（在存储观点来说，矩阵面积越小，存储量就越小）要远远小于原始的矩阵A，我们如果想要压缩空间来表示原矩阵A，我们存下这里的三个矩阵：
U、Σ、V就好了。
二、奇异值的计算：
奇异值的计算是一个难题，是一个O（N^3）的算法。
在单机的情况下当然是没问题的，matlab在一秒钟内就可以算出1000*1000的矩阵的所有奇异值，但是当矩阵的规模增长的时候，计算的复杂度呈3次方增长，就需要并行计算参与了。
Google的吴军老师在数学之美系列谈到SVD的时候，说起Google实现了SVD的并行化算法，说这是对人类的一个贡献，但是也没有给出具体的计算规模，也没有给出太多有价值的信息。
其实SVD还是可以用并行的方式去实现的，在解大规模的矩阵的时候，一般使用迭代的方法，当矩阵的规模很大（比如说上亿）的时候，迭代的次数也可能会上亿次，如果使用Map-Reduce框架去解，则每次Map-Reduce完成的时候，都会涉及到写文件、读文件的操作。
个人猜测Google云计算体系中除了Map-Reduce以外应该还有类似于MPI的计算模型，也就是节点之间是保持通信，数据是常驻在内存中的，这种计算模型比Map-Reduce在解决迭代次数非常多的时候，要快了很多倍。
Lanczos迭代就是一种解对称方阵部分特征值的方法（之前谈到了，解A’*A得到的对称方阵的特征值就是解A的右奇异向量），是将一个对称的方程化为一个三对角矩阵再进行求解。
按网上的一些文献来看，Google应该是用这种方法去做的奇异值分解的。
请见Wikipedia上面的一些引用的论文，如果理解了那些论文，也“几乎”可以做出一个SVD了。
由于奇异值的计算是一个很枯燥，纯数学的过程，而且前人的研究成果（论文中）几乎已经把整个程序的流程图给出来了。
更多的关于奇异值计算的部分，将在后面的参考文献中给出，这里不再深入，我还是focus在奇异值的应用中去。
三、奇异值与主成分分析（PCA）：
主成分分析在上一节里面也讲了一些，这里主要谈谈如何用SVD去解PCA的问题。
PCA的问题其实是一个基的变换，使得变换后的数据有着最大的方差。
方差的大小描述的是一个变量的信息量，我们在讲一个东西的稳定性的时候，往往说要减小方差，如果一个模型的方差很大，那就说明模型不稳定了。
但是对于我们用于机器学习的数据（主要是训练数据），方差大才有意义，不然输入的数据都是同一个点，那方差就为0了，这样输入的多个数据就等同于一个数据了。
以下面这张图为例子：
这个假设是一个摄像机采集一个物体运动得到的图片，上面的点表示物体运动的位置，假如我们想要用一条直线去拟合这些点，那我们会选择什么方向的线呢？
当然是图上标有signal的那条线。
如果我们把这些点单纯的投影到x轴或者y轴上，最后在x轴与y轴上得到的方差是相似的（因为这些点的趋势是在45度左右的方向，所以投影到x轴或者y轴上都是类似的），如果我们使用原来的xy坐标系去看这些点，容易看不出来这些点真正的方向是什么。
但是如果我们进行坐标系的变化，横轴变成了signal的方向，纵轴变成了noise的方向，则就很容易发现什么方向的方差大，什么方向的方差小了。
一般来说，方差大的方向是信号的方向，方差小的方向是噪声的方向，我们在数据挖掘中或者数字信号处理中，往往要提高信号与噪声的比例，也就是信噪比。
对上图来说，如果我们只保留signal方向的数据，也可以对原数据进行不错的近似了。
PCA的全部工作简单点说，就是对原始的空间中顺序地找一组相互正交的坐标轴，第一个轴是使得方差最大的，第二个轴是在与第一个轴正交的平面中使得方差最大的，第三个轴是在与第1、2个轴正交的平面中方差最大的，这样假设在N维空间中，我们可以找到N个这样的坐标轴，我们取前r个去近似这个空间，这样就从一个N维的空间压缩到r维的空间了，但是我们选择的r个坐标轴能够使得空间的压缩使得数据的损失最小。
还是假设我们矩阵每一行表示一个样本，每一列表示一个feature，用矩阵的语言来表示，将一个m*n的矩阵A的进行坐标轴的变化，P就是一个变换的矩阵从一个N维的空间变换到另一个N维的空间，在空间中就会进行一些类似于旋转、拉伸的变化。
而将一个m*n的矩阵A变换成一个m*r的矩阵，这样就会使得本来有n个feature的，变成了有r个feature了（r<
n），这r个其实就是对n个feature的一种提炼，我们就把这个称为feature的压缩。
用数学语言表示就是：
但是这个怎么和SVD扯上关系呢？
之前谈到，SVD得出的奇异向量也是从奇异值由大到小排列的，按PCA的观点来看，就是方差最大的坐标轴就是第一个奇异向量，方差次大的坐标轴就是第二个奇异向量…我们回忆一下之前得到的SVD式子：
在矩阵的两边同时乘上一个矩阵V，由于V是一个正交的矩阵，所以V转置乘以V得到单位阵I，所以可以化成后面的式子
将后面的式子与A*P那个m*n的矩阵变换为m*r的矩阵的式子对照看看，在这里，其实V就是P，也就是一个变化的向量。
这里是将一个m*n的矩阵压缩到一
升级会员 