精华内容
下载资源
问答
  • 先说一下原理: 对于一个可逆矩阵A,必然会得到它的唯一LU分解,即分解为一个下三角矩阵L和一个上三角矩阵U使得 A=L*U; 我们需要求得的问题是A的矩阵A`,已知 A=LU,A*A`=E,所以 A` = U`*L`; ...

    基于实际需要,需要对五百万阶的方阵进行求逆运算,但查看Spark(v. 2.2.0)的官方api并没有此方面的信息,就自己尝试着实现了一个;

    先说一下原理:

            对于一个可逆矩阵A,必然会得到它的唯一LU分解,即分解为一个下三角矩阵L和一个上三角矩阵U使得 A=L*U;

            我们需要求得的问题是A的逆矩阵A`,已知 A=LU,A*A`=E,所以 A` = U`*L`;

            由线性代数知识可知,一个下三角矩阵的逆必然也是下三角矩阵;

            又因为,逆的转置等于转置的逆,即,(U`)T = (UT),而UT和L一样是下三角矩阵,可以实现代码复用;

    所以问题便转化成了,

        (一)大型可逆矩阵的LU分解

        (二)大型下三角矩阵的求逆

    第一部分由我的同学实现,之后会放出链接;这里主要讲一下大型下三角矩阵求逆的方法和实现;


    大型矩阵运算,因为数据量过大,无法在单台计算机上进行,故需要进行并行化处理,这里采用分块矩阵乘法的思想。

    首先设定一个步长 s,使得阶数为s的方阵可以在单台节点上进行求逆运算。


    根据分块矩阵乘法,

        L1*L1`=E

        L2*L1`+L3*L2`=0

        L3*L3`=E

    化简可知,

        L1`=(L1)`

        L2`=-(L3)`*L2*(L1)`

        L3`=(L3)`

    如此一来。只要知道(L3)`,便可以知道整个矩阵的逆,而(L3)`同样是下三角矩阵,如此一来便可以进行迭代,当迭代到L3的步长不大于s时,便可以在单台节点上进行计算,如此一来,便可以反推回整个矩阵的逆;


    下面进入实际实现部分:

        1.基于Spark的api,将HDFS上的矩阵加载到内存中,类型为 BlockMatrix

     2.调用BlockMatrix.blocks方法得到底层RDD,过滤出行标不大于列标的分块(下三角矩阵上半部分全是0,减少运算量)

     3.首先得到原矩阵右下角的分块,求逆得到(L3)`,行标-1,得到L1和L2,得到(L1)`和L2,如此一来便可以拼凑出原矩阵右下角分块为2的矩阵的逆,迭代运算便可得到最终结果;

        

    期间遇到的难点:

        1.矩阵加载,Spark提供的原生api无法加载CSV文件直接转成BlockMatrix,所以此处进行了封装:

    new IndexedRowMatrix(spark.sparkContext.textFile(path,Main.excutors).map(UDF.line2IndexedRow))
      .toCoordinateMatrix().toBlockMatrix(steps, steps)
    
    
    /*
     *输入一行以逗号(英文 , )分割的浮点数,最开始的数字作为索引
     *返回一个IndexRow
     */
    def line2IndexedRow(line:String): IndexedRow ={
      val arrayBuffer = line.split(",").map(_.toDouble).toBuffer
      val index = arrayBuffer.head.toLong
      arrayBuffer.trimStart(1)
      val vector = Vectors.dense(arrayBuffer.toArray)
      new IndexedRow(index,vector)
    }
    
    

    2.在计算  L2`=-(L3)`*L2*(L1)`时,由于直接调用矩阵分块乘法api会导致分块最终位置与算法设想不同,需要自行解决;

    3.在本地运行时结果与集群运行结果不一致:由于算法全程使用尾递归进行迭代,有部分全局变量需要广播到各个节点;

    4.性能优化,在矩阵运算过程中,由于是懒执行,部分变量会重复计算造成计算资源浪费,需要在SparkUI上查看,逐项调校;

    5.Spark的persist机制:在调用RDD的persist方法后,RDD并不会马上被缓存,而是要等到第一个action调用时才会执行,但实际上

    本算法中action的调用距离RDD首次生成相隔甚远,所以,需要在persist方法后接一个action来进行显示缓存;由于缓存项目过多

    可能造成大量IO操作,需要及时进行unpersist操作;

    优化后的RDD DAG截图如下:


    可以看到,大部分的RDD操作由于缓存,节省了大量计算资源;

    测试结果表明,在计算20阶,步长为5的矩阵运算时,优化前的计算时间为36.39秒;

    优化后,将时间缩减到10.809秒,优化成果显著;




        



    展开全文
  • C语言之单位下三角矩阵求逆

    千次阅读 2015-10-26 17:51:46
    //矩阵第一列求逆  for(i = 1; i ; i++ )  {  l[i][0]=-l[i][0];    }  //bs表示矩阵的维数  for(n=1;n;n++)  {      for(i = n+1; i ; i++)  {  for(j = 0; j ...
    #include<stdio.h>
    

    int main()

    {

    //矩阵保存在二位数组也可以随机生成

       double l[4][4]={1,0,0,0,2,1,0,0,3,2,1,0,5,4,2,1};
       long bs=4,i,j,n;
    //矩阵第一列求逆
     for(i = 1; i < bs; i++ )
       {

           l[i][0]=-l[i][0];
       
       } 
    //bs表示矩阵的维数

       for(n=1;n<bs-1;n++)
       {
       
       
           for(i = n+1; i < bs; i++)
           {


               for(j = 0; j < n; j++)
               {
             
                  l[i][j]-=l[n][j]*l[i][n];
               }
                   l[i][n]=-l[i][n];


           }
       
       }


    //求逆后保存在原矩阵

    //打印矩阵


       for(i=0;i<bs;i++)
      {
        for(j=0;j<bs;j++)
        {
           printf("%.2f ",l[i][j]);
        }
       printf("\n");
      }
       
        return 0;
    }
    展开全文
  • 矩阵计算中第一次实验题,计算下三角矩阵矩阵的详细算法,可以正常运行,有所有的测试数据与运行结果
  • DSP算法架构及设计,内容为基于systolic的上三角矩阵求逆电路的实现,里面有详尽的MATLAB/SIMULINK 仿真模型,及HDL代码和在modelsim中的仿真程序,非常不错的。
  • 定义 性质 求逆 ...主对角线以下都是零的方阵称为上三角矩阵。...主对角线以上都是零的方阵称为下三角矩阵。...上()三角矩阵乘以系数后也是上()三角矩阵 上()三角矩阵间的加减法和...一般化的上下三角矩阵求逆 ...

    定义

    • 主对角线以下都是零的方阵称为上三角矩阵。
    • 主对角线以上都是零的方阵称为下三角矩阵。

    性质

    • 行列式为对角线元素相乘
    • 上(下)三角矩阵乘以系数后也是上(下)三角矩阵
    • 上(下)三角矩阵间的加减法和乘法运算的结果仍是上(下)三角矩阵。

    求逆

    展开全文
  • 求矩阵 X 的逆矩阵,给定它的(下三角)Cholesky 分解; 即 X = LL',根据论文“使用 Cholesky 分解的矩阵求逆”,Aravindh Krishnamoorthy,Deepak Menon,arXiv:1111.4144。
  • 在讨论今天的主题之前...可逆矩阵:存在n阶矩阵A和n阶矩阵B,使得矩阵A、B的乘积为单位矩阵,则称A为可逆矩阵,B为A的逆矩阵。对角矩阵:一个主对角线之外的元素都为0的矩阵。根据我的主题,大家也能够想到今天要谈...

    在讨论今天的主题之前,我们先给出三类矩阵的定义,分别是相似矩阵、可逆矩阵、对角矩阵。

    相似矩阵:在线性代数中,相似矩阵指的是存在相似关系的矩阵,设A、B为n阶矩阵,如果有n阶可逆矩阵P存在,使得P^(-1)AP=B。

    可逆矩阵:存在n阶矩阵A和n阶矩阵B,使得矩阵A、B的乘积为单位矩阵,则称A为可逆矩阵,B为A的逆矩阵。

    对角矩阵:一个主对角线之外的元素都为0的矩阵。

    根据我的主题,大家也能够想到今天要谈的,便是关于相似矩阵中的可逆矩阵P能否对角化。

    相似矩阵不用多说,大家也清楚,证明两个矩阵相似,便是存在n阶可逆矩阵P,满足上面的定义。

    那么对于判断矩阵A与对角矩阵相似呢,我直接给出定理,这也是书本上提到的。

    n阶矩阵A与对角矩阵相似的充分必要条件是矩阵A有n个线性无关的特征向量。

    话不多说,接下来就给出一道实际的例题,来让大家详细了解一下:

    3f5c99b8c8cc29f83fbc33517acfa0e3.png

    如图所示,这道例题便是告诉我们两个矩阵相似,其中各个矩阵之中都有未知数,让我们通过相似矩阵的性质来求出未知数的值。

    这里笔者当时在做的时候,有个点没有注意到,那便是相似矩阵两者的迹数相等,也就是主对角线上所有元素之和相等,导致我没有列出第一个式子,至于第二个式子,大家也都知道,就是行列式的值相等。

    011821b2b1f59d812b9d40d3b904fc10.png

    这是第二小题的做法,它的目的是让我们求出可逆矩阵P,满足P^(-1)AP是对角矩阵,对于这类题型而言,正如图中所说,是有如下步骤的:

    1、求出全部的特征值,这里因为矩阵A和矩阵B相似,所以求矩阵B的特征值更好求,得到1,1,5。

    2、然后对每一个特征值求特征向量,写出基础解系。

    3、然后代入到可逆矩阵P中,算出答案。

    最后总结一下,对于求相似矩阵包含的未知数而言,最基本最重要的就是记住相似矩阵的性质,而对于求可逆矩阵P而言,最重要的就是知道解题步骤,清楚特征值特征向量该如何使用。

    展开全文
  • 矩阵求逆 LU三角分解

    千次阅读 2018-09-02 19:18:42
    L是下三角矩阵,U是上三角矩阵,P是一个置换矩阵(P将在下一篇博客中写出) LUP分解:PA=LU②  由①②可得1.正向替换(设y=Ux):Ly=Pb 2.反向替换:Ux=y 所以 忽略P,下面说明LU的法: 1.参数矩阵A做如下...
  • Math01: 两种方法求下三角矩阵

    千次阅读 2015-09-18 00:13:00
    方法一:单位矩阵消元 \begin{equation}\left(A|I\right)\rightarrow\left(I|B\right)\end{equation} 1 clear; 2 n = 500; 3 A = zeros(n,n); 4 for j = 1:n 5 for i = j:n 6 A(i,j) = (i + j)^2; .....
  • 1.矩阵的crout(LU)分解,其中L为下三角矩阵,U为上三角矩阵 2.L,U矩阵的伴随阵,参考文献:三角形矩阵伴随矩阵的一种方法(曾月新) 3.L,U矩阵的(伴随阵A* /det(A)) 4.inv_A = inv_U * inv_L
  • 求解三角形伴随矩阵的参考文献,根据这篇文献设计求逆矩阵...1.矩阵的crout(LU)分解,其中L为下三角矩阵,U为上三角矩阵 2.L,U矩阵的伴随阵 3.L,U矩阵的(伴随阵A* /det(A)) 4.inv_A = inv_U * inv_L
  • 矩阵求逆c++实现

    万次阅读 多人点赞 2014-05-02 08:53:44
    矩阵求逆c++实现
  • 因此在计算中大型矩阵的时常将原矩阵AAA分解为一个下三角矩阵LLL和一个上三角矩阵UUU相乘的形式,再分别求下三角矩阵L−1L^{-1}L−1和上三角矩阵U−1U^{-1}U−1,再将它们相乘获得最终的矩阵结果。...
  • C语言实现矩阵求逆

    2018-06-08 13:14:18
    本人使用C语言编写使用初等行变换的方法,矩阵逆矩阵
  • 满意答案MAKALANZU2013.09.08采纳率:54%等级:...希望下面的东西能帮到你(你试试看):对A进行QR分解(A=QR),其中Q是nxk正交矩阵(Orthonormal Matrix),R是kxk上三角矩阵(Upper Triangular Matrix),然后min ||Ax-b||...
  • 这篇总结是《矩阵运算代码...将原矩阵A分解成两个三角矩阵,上三角矩阵L和下三角矩阵U。通过求解U和L对应的矩阵,即可求得相应A的矩阵。算法分成以下几个步骤: 1)矩阵的LU分解 对于LU上每个位置的值,可以用以
  • 上下三角矩阵

    千次阅读 2018-09-23 15:45:43
    三角矩阵具有行列式为对角线元素相乘、上三角矩阵乘以系数后也是上三角矩阵、上三角矩阵间的加减法和乘法运算的结果仍是上三角矩阵等性质。 若矩阵U具有下列形式: 则称为上三角矩阵三角矩阵的性质: 1)上...
  • c++矩阵求逆的lu分解实现

    千次阅读 2019-12-29 15:21:31
    c++方阵求逆的lu分解实现 初学c++,尝试利用基础知识编写矩阵求逆。但发现求解伴随阵的过程非常复杂且难以实现,而...1.矩阵的crout(LU)分解,其中L为下三角矩阵,U为上三角矩阵 2.L,U矩阵的伴随阵,见参考...
  • 1. 矩阵求逆 import numpy as np a = np.array([[1, 2], [3, 4]]) # 初始化一个非奇异矩阵(数组) print(np.linalg.inv(a)) # 对应于MATLAB中 inv() 函数 # 矩阵对象可以通过 .I 更方便的求逆 A = np.matrix(a) ...
  • C语言矩阵求逆(源代码)

    热门讨论 2009-05-22 09:50:14
    C语言中这样逆矩阵矩阵求逆的源代码。非常实用。
  • 矩阵求逆(c++)

    千次阅读 2017-09-21 17:55:10
    矩阵求逆(c++)标签(空格分隔): 技术博客简要过程介绍方法的名称是“Gauss-Jordan (or reduced row) elimination method”。设单位对角矩阵为I,则MM−1=IMM^{-1}=I主要过程为,摆一个相同大小的对角矩阵在旁边...
  • 因为矩阵AA-1=E,于是可以利用AX=E来A-1。... 程序先初始化两个n维矩阵p[],q[],,p[]用来存放要求的矩阵,通过高斯列主元消元法变成上三角矩阵,q[]与p[]同时变换。通过追赶法解出每一行的解存放在q[]中
  • Matlab求矩阵的主对角元素、上(三角矩阵、行列式的值、矩阵的秩、矩阵的范数、矩阵的条件数和矩阵的迹
  • 矩阵求逆的c#代码实现

    千次阅读 2019-04-27 23:56:01
    矩阵可逆=矩阵非奇异=矩阵对应的行列式不为0=满秩=行列...求逆矩阵的方法: 1.逆矩阵等于伴随矩阵乘以行列式值的负一次方,程序实现的计算量较大 2.高斯消元法 对(A E)作初等变换,将A化为单位阵 ,单位矩阵E就化为A...
  • C++三阶矩阵求逆矩阵

    千次阅读 2020-07-26 22:05:02
    //三阶矩阵求逆矩阵 //=================== #include <stdio.h> #include <math.h> #include <stdlib.h> #include <iostream> #include <fstream> #include<string> #include&...
  • http://blog.csdn.net/pipisorry/article/details/52241141本blog主要内容有:矩阵的奇异性、条件数与病态矩阵矩阵求逆。奇异矩阵和非奇异矩阵singular matrix&nonsingular matrix概念和定义若n阶矩阵A的行列式不...
  • 给定任意一个矩阵A,它的逆矩阵。 方案一:直接求逆 【例1】:简单的二维矩阵 设A=[abcd]A=\begin{bmatrix} a &amp; b \\ c &amp; d\end{bmatrix}A=[ac​bd​],则A−1=1det(A)[d−b−ca]A^{-1}=\frac{1}{...
  • 题目 这是一道矩阵求逆的模板题。 先了解一下什么叫矩阵求逆: 两个矩阵A,B,BA=I(I为...现将矩阵消成上三角矩阵,再将上三角矩阵消成对角矩阵,最后消成单位矩阵。 在消的途中,对一个单位矩阵进行相同的操作,便...
  • 如何用MATLAB求逆矩阵如果英文好呢,自己看目录不好还是先看中文的教材,对matlab的框架和功能有了一定的了解后,自己也就看的懂帮助里面的内容了,以后不懂再自己查帮助求逆矩阵一般有2种方法:1、伴随矩阵法。...
  • 基于Cholesky分解的正定矩阵求逆矩阵

    万次阅读 2014-06-12 21:49:58
    在前面的博客中我提到了如何实现正定矩阵的Cholesky分解,并提供了源代码,通过该代码可以将一个正定矩阵分解为一个上三角矩阵和其转置的乘积,在此基础上,对上三角矩阵进行求逆是十分简单的运算,在得到其矩阵...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,230
精华内容 5,692
关键字:

下三角矩阵求逆