精华内容
下载资源
问答
  • 矩阵计算中第一次实验题,计算下三角矩阵的逆矩阵的详细算法,可以正常运行,有所有的测试数据与运行结果
  • 先说一下原理: 对于一个可逆矩阵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秒,优化成果显著;




        



    展开全文
  • 方法一:单位矩阵消元 \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; .....

    方法一:单位矩阵消元

    \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;
     7     end
     8 end
     9 C = A;
    10 B = eye(n);
    11 
    12 for i = 1:(n-1)
    13     B(i,:) = B(i,:)/A(i,i);
    14     A(i,:) = A(i,:)/A(i,i);
    15     for j = (i+1):n
    16         B(j,:) = B(j,:) - B(i,:)*A(j,i);
    17         A(j,:) = A(j,:) - A(i,:)*A(j,i);
    18     end
    19 end
    20 B(n,:) = B(n,:)/A(n,n);
    21 A(n,:) = A(n,:)/A(n,n);

    方法二:分块矩阵迭代

    \begin{equation}\left(\begin{matrix}A&C\\0&B\end{matrix}\right)^{-1}=\left(\begin{matrix}A^{-1}&-A^{-1}CB^{-1}\\0&B^{-1}\end{matrix}\right)\end{equation}

    \begin{equation}\left(\begin{matrix}A&0\\C&B\end{matrix}\right)^{-1}=\left(\begin{matrix}A^{-1}&0\\-B^{-1}CA^{-1}&B^{-1}\end{matrix}\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;
     7     end
     8 end
     9 
    10 inv_p = 1/A(1,1);
    11 for k = 2:n
    12     c = A(k,1:(k-1));
    13     zero = zeros((k-1),1);
    14     inv_q = [inv_p, zero; -(1/A(k,k))*c*inv_p, 1/A(k,k)];
    15     inv_p = inv_q;
    16 end

    第二种方法速度更快

    转载于:https://www.cnblogs.com/toorist/p/4818046.html

    展开全文
  • Matlab求矩阵的主对角元素、上(三角矩阵的逆、行列式的值、矩阵的秩、矩阵的范数、矩阵的条件数和矩阵的迹

    今天做作业,发现了问了一堆关于矩阵操作的,查了查资料,整理放在这里。
    觉得有用的朋友点个赞呗~b( ̄▽ ̄)d

    A = [1,-1,2,3;5,1,-4,2;3,0,5,2;11,15,0,9];
    B = [0.43,43,2;-8.9,4,21];
    %(1)方阵
    diag(A) %主对角元素
    triu(A) %上三角
    tril(A) %下三角
    inv(A)  %矩阵的逆
    det(A)  %行列式的值
    rank(A) %矩阵的秩
    norm(A) %矩阵的范数
    cond(A) %矩阵的条件数
    trace(A)%矩阵的迹
    %(2)非方阵
    diag(B) %主对角元素
    triu(B) %上三角
    tril(B) %下三角
    pinv(B)  %矩阵的逆
    %B不是方阵,不存在行列式的值
    rank(B) %矩阵的秩
    norm(B) %矩阵的范数
    cond(B) %矩阵的条件数
    sum(diag(B))%矩阵的迹
    

    最后


    在学习Python一年中,收集了很多Python学习资料,在这里整理一下,分享给各位!

    Python入门、数据分析、爬虫、运维、机器学习方面的学习资料

    干货 | Python学习资源整理分享

    展开全文
  • 主对角线以上都是零方阵称为下三角矩阵。 性质 行列式为对角线元素相乘 上(下)三角矩阵乘以系数后也是上(下)三角矩阵 上(下)三角矩阵间加减法和乘法运算结果仍是上(下)三角矩阵。 求 三阶 上三角、...

    定义

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

    性质

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

    求逆

    展开全文
  • 求矩阵 X 的逆矩阵,给定它的(下三角)Cholesky 分解; 即 X = LL',根据论文“使用 Cholesky 分解的矩阵求逆”,Aravindh Krishnamoorthy,Deepak Menon,arXiv:1111.4144。
  • 上下三角矩阵的性质们

    千次阅读 2019-08-12 16:48:20
    文章目录定义性质性质1性质2:与幂零矩阵的关系性质3:逆矩阵性质4:与所有方阵的关系性质5证明:性质6:LU分解 定义 上三角:主对角线下方元素全为0的方阵 A=(aij)A=(a_{ij})A=(aij​)是上三角⇔\Leftrightarrow⇔ ...
  • 矩阵 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做如下...
  • 快速求解(单位)上下三角矩阵的逆的C++程序
  • 求解三角形伴随矩阵的参考文献,根据这篇文献设计求逆矩阵...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
  • 上(三角矩阵

    2016-12-14 15:38:00
    上三角阵: 下三角阵: 严格三角矩阵:主对角线元素全为0。...另外高斯矩阵的逆矩阵也是高斯矩阵: 注意就是将列元素变号。 转载于:https://www.cnblogs.com/ly123456/p/6179555.html...
  • LU 分解法求矩阵的逆

    2010-01-05 17:09:49
    LU分解是矩阵分解的一种,可以将一个矩阵分解为一个下三角矩阵和一个上三角矩阵的乘积(有时是它们和一个置换矩阵的乘积)。LU分解主要应用在数值分析中,用来解线性方程、求矩阵的逆或计算行列式。
  • //将采用邻接矩阵存储有向无环图邻接矩阵转换为下三角矩阵,并输出新旧编号对照表 int topologic_order[G.vexnum];//拓扑序列,反过来就是拓扑序列 //topologic_order[G.vexnum - 1 - 新序号] = 旧序号
  • c++矩阵逆的lu分解实现

    千次阅读 2019-12-29 15:21:31
    c++方阵求的lu分解实现 初学c++,尝试利用基础知识编写矩阵求。但发现求解伴随阵的过程非常复杂且难以实现,而...1.求矩阵的crout(LU)分解,其中L为下三角矩阵,U为上三角矩阵 2.求L,U矩阵的伴随阵,见参考...
  • 因此在计算中大型矩阵的逆时常将原矩阵AAA分解为一个下三角矩阵LLL和一个上三角矩阵UUU相乘的形式,再分别求下三角矩阵的逆L−1L^{-1}L−1和上三角矩阵的逆U−1U^{-1}U−1,再将它们相乘获得最终的逆矩阵结果。...
  • 矩阵的运算与逆矩阵

    千次阅读 2019-07-06 12:23:35
      同型矩阵、零矩阵、对角矩阵、单位矩阵、上()三角矩阵、系数矩阵、增广矩阵、线性变换、矩阵加法、数乘矩阵、矩阵相乘、方阵幂、转置矩阵、(反)对称矩阵、方阵行列式、伴随矩阵、行列式余子式、代数...
  • - 使用部分旋转将 LU 分解为下三角矩阵 L 和上三角矩阵的示例代码 - 示例代码向前和向后替换,用于求解三角矩阵的线性系统。 - 基于 LU 的示例代码逆矩阵
  • 从上到将A变为上三角矩阵的复杂度为O(n3n^3n3),再从往上将上三角矩阵变化为单位矩阵复杂度为O(n3n^3n3),因此总共的复杂度为O(n3n^3n3) 。 还有一种做法是按照高斯消元接线性方程组的方式求解n次线性方程组,...
  • 这篇总结是《矩阵运算代码...将原矩阵A分解成两个三角矩阵,上三角矩阵L和下三角矩阵U。通过求解U和L对应的逆矩阵,即可求得相应A的逆矩阵。算法分成以下几个步骤: 1)矩阵的LU分解 对于LU上每个位置的值,可以用以
  • 矩阵运算 Python实现

    千次阅读 2018-09-11 23:40:24
    原理:应用列主元消去法运算矩阵A的逆矩阵,利用初等矩阵行变换A转化单位矩阵时,同样的行变化可将单位矩阵转化为A的逆矩阵。 步骤: 编制下三角部分消元和上三角部分消元的代码 a. 从对角线元素往下比较取得这...
  • 常见几种矩阵分解方式

    万次阅读 多人点赞 2016-09-25 15:54:23
    1.三角分解(LU分解)矩阵的LU分解是将一个矩阵分解为一个下三角矩阵与上三角矩阵的乘积。本质上,LU分解是高斯消元的一种表达方式。首先,对矩阵A通过初等行变换将其变为一个上三角矩阵。对于学习过线性代数的同学来...
  • 矩阵LU分解求(学习笔记)

    万次阅读 2014-09-25 16:51:10
    矩阵的一种有效而广泛应用的分解...所以首先对矩阵进行三角分解,这里采用Doolittle分解,即分解为一个下三角矩阵(对角元素为1),和一个上三角矩阵的乘积。再进行相应的处理。 所以,矩阵求的算法流程可表述如下:
  • 下三角或上三角用高斯消元求,相当比较快,一般还要先化为下三角或者上三角。 用这个分块方法计算量最复杂地方就是要算3次2*2矩阵,好处是分块计算,总有对地方。 但一般考试中不提倡这个方法,算错...
  • PLU-分解以及求逆矩阵

    2021-02-03 11:17:40
    PLU-分解 PLU-分解是对LU分解一种改进,其增加了选主元操作...P为置换矩阵,L为下三角矩阵,U为上三角矩阵。选主元操作在计算过程中以一个一维数组保存代替n×nn\times nn×n矩阵,以下为此算法Fortran代码,
  • 矩阵的逆矩阵双曲正弦值。 acoshm :矩阵的主双曲余弦值。 test :测试脚本。 运行此命令以检查功能是否正常运行。 其他M文件: normam :由其他函数用来估计矩阵幂的范数。 要求 这些代码已在MATLAB 2015a--...
  • 矩阵的逆7. 提取矩阵的上、下三角部分8. 矩阵转化为向量9. 矩阵常用的函数 1. 矩阵的基本运算 当两个矩阵的维度相同时(即两个矩阵的行数和列数相同),矩阵的四则运算,就是对应元素的加减乘除。 先生成两个...
  • inv 矩阵的逆 norm 矩阵的范数值 normest 矩阵的2-范数值 rank 矩阵的秩 orth 矩阵的正交化运算 rcond 矩阵的逆条件数值 trace 矩阵的迹 triu 上三角变换 tril 下三角变换 diag 对角变换 exmp 矩阵的指数...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 206
精华内容 82
关键字:

下三角矩阵的逆矩阵