到底是求逆快，还是用克拉默快？

登录 · 发表于 2021-2-11 08:35

本帖最后由 xukun977 于 2021-2-11 11:15 编辑

问题的描述：

关于求解方程ax=b，有网友说求逆x=a^-1b，比用克拉默法则来的慢！

下面来比较一下，到底哪个计算量少一些。

对于求逆，公平起见，不使用技巧，使用最呆的方法：

为了公平起见，也为了让结果更具有一般性，假设所有元素都不为零。

对于3阶矩阵，要计算9次二阶行列式，是两个交叉乘积的差，每一个元素基本上可以口算的。

而克拉默法则中分子的计算，要计算3次行列式，每一次要降秩两次，然后计算对角线之积，所以计算量是3×3=9次。

发表于 2021-2-15 13:33

本帖最后由 andy520520 于 2021-2-15 14:04 编辑

克莱姆法则适合计算机软件这样死的计算方法，你上面说的三阶的A*X = B，X=A^-1 *B , 实际也不可能求出A的逆矩阵矩阵然后相乘计算，线性方程的求解用增广矩阵通过变换直接求出X，跟多元方程的消元法差不多。对于矩阵里面的变换，如果没有赋予计算灵活的算法，计算机根本完成不了，而克莱姆法则是死东西，非常适合计算机
这个让我想起了一个用8个电阻组成100R的测试电路，8个电阻分别是 1， 2， 2 ，5， 10, 20 ，20 ，40 这个8个电阻，怎样用你计算机快速控制这个8个电阻使其成为1---100R的任意值，用试揍的方法很慢，用位图查表的方法简直瞬间完成

发表于 2021-2-15 18:23

andy520520 发表于 2021-2-15 13:33
克莱姆法则适合计算机软件这样死的计算方法，你上面说的三阶的A*X = B，X=A^-1 *B , 实际也不可能求出A的逆 ...

8个电阻好像是贪婪算法，位图查表的方式，愿闻其详

登录 · 发表于 2021-2-15 18:48

本帖最后由 xukun977 于 2021-2-15 18:50 编辑

andy520520 发表于 2021-2-15 13:33
克莱姆法则适合计算机软件这样死的计算方法，你上面说的三阶的A*X = B，X=A^-1 *B , 实际也不可能求出A的逆 ...

实际情况，与你说的，恰好相反。

本科学的东西基本上是用不上的！！
对于Ax=b，如果A为4阶矩阵，那么采用高斯算法，每一个乘法和除法算计算一次，那么需要计算36次。
即便矩阵A中一半（8个元素）为零，仍旧要计算36次，效率太低了。

在计算机算法中，求逆矩阵是常见的必然算法：

而克拉莫法则基本上没有用武之地，效率太低了。

发表于 2021-2-15 19:02

本帖最后由叶春勇于 2021-2-15 19:20 编辑

andy520520 发表于 2021-2-15 13:33
克莱姆法则适合计算机软件这样死的计算方法，你上面说的三阶的A*X = B，X=A^-1 *B , 实际也不可能求出A的逆 ...

复制

T=[40,20,20,10,5,2,2,1]



def get_r(v,t):

    tab=[x for x in t if x<=v ]

    #print(v,tab)

    if(v==0):

        return 0

    else:

        

        r=tab[0]

        print(r)

        tab.pop(0)

        return get_r(v-r,tab)





get_r(67,T)

输出结果：

复制

>>> 

============================== RESTART: D:/getr.py =============================

40

20

5

2

>>>

这是我的代码，用MIT 算法导论里面的贪婪加递归。

发表于 2021-2-15 19:07

xukun977 发表于 2021-2-15 18:48
实际情况，与你说的，恰好相反。

A*X = B, X = A^-1 *B , 把A的逆矩阵求出来，再和B相乘，你觉得会简化多少？
实际手工计算也是用A的扩展矩阵求得阶梯型矩阵，这些是很容易的手工算了。
A的扩展矩阵 [A B] ，把B加进来
[A B] ----> [ E A^-1 *B] = [E X] ，左边是单位矩阵E,右边是X直接出来

发表于 2021-2-15 19:25

本帖最后由 andy520520 于 2021-2-15 19:27 编辑

叶春勇发表于 2021-2-15 19:02
输出结果：
这是我的代码，用MIT 算法导论里面的贪婪加递归。

把电阻编号，查表可以瞬间完成， uint8_t tab[101]

发表于 2021-2-15 19:29

andy520520 发表于 2021-2-15 19:25
查表可以瞬间完成， uint8_t tab[100]

我想复杂了。原来是先计算好一个表格呀

发表于 2021-2-15 19:48

andy520520 发表于 2021-2-15 19:07
A*X = B, X = A^-1 *B , 把A的逆矩阵求出来，再和B相乘，你觉得会简化多少？
实际手工计算也是用A的 ...

你说的这些，都是本科课程知识。

到了研究生课程-----矩阵论和数值分析，这些理论才开始有实用价值。

例如电路算法中的稀疏矩阵，本科的线性代数就没有说，矩阵论中才重点研究。

所以不要抬杠了，自己看看关于计算机辅助的电路分析，尤其是侧重于算法的书籍吧。

登录 · 发表于 2021-2-15 20:00

本帖最后由 xukun977 于 2021-2-15 21:10 编辑

下面用一个具体的例子，给你们展示一下，到底是求逆来的快，还是用克拉默法则来的快。
这样对比一下，就有说服力了。

随意假设一个矩阵A为：

下面来求A的逆。

电路中分析高阶电路，方法是把整体分解成一阶和二阶的组合，同样道理，我也可以对矩阵分割：

分割成4个子矩阵，分别标号为A11，A12等。

第一步，求主对角两个矩阵的逆。

由于是二阶矩阵，本科线性代数书上有现成的公式套，基本上无需费什么时间，可直接写出结果：

用类似的方法，可计算出A22的逆为1/7 【1 3；3 2】

第二步，求两个矩阵的乘积：

同样的方法计算出A21 *A11^-1=1/7[8 5 ; -3 -8]

第三步，在第二步计算结果基础之上，再计算一次乘积：

第4步，在第三步计算结果之上，做个减法，然后求逆：

然后对结果矩阵求逆：

与上面步骤完全相同，先做一次减法，然后求逆：

其逆为1/57[ 28 7; -25 8]

发表于 2021-2-15 20:29

xukun977 发表于 2021-2-15 20:00
下面用一个具体的例子，给你们展示一下，到底是求逆来的快，还是用克拉默法则来的快。
这样对比一下，就有 ...

实际上解方程不需要这样求出逆矩阵，你这样把一个4阶的矩阵求出来看下，头都大了吧，你还没有求出来是不是？

发表于 2021-2-15 20:31

xukun977 发表于 2021-2-15 20:00
下面用一个具体的例子，给你们展示一下，到底是求逆来的快，还是用克拉默法则来的快。
这样对比一下，就有 ...

即使是真的去求这个逆矩阵，你也可以把把A扩展宽矩阵， [A E] ---> 通过行变换， [E A^-1] ，不你你这个搞法强百倍的效率？

发表于 2021-2-15 20:33

本帖最后由 xukun977 于 2021-2-15 20:38 编辑

andy520520 发表于 2021-2-15 20:29
实际上解方程不需要这样求出逆矩阵，你这样把一个4阶的矩阵求出来看下，头都大了吧，你还没有求出来是不 ...

上面的计算例子，我已经完成80%了，可见计算过程只有二阶矩阵的乘法、减法和求逆组成。

也就是说，只需12次计算（包括减法），就能计算出这个矩阵的逆。

用克拉默方法，只算乘和除，需要36次。

哪个快，哪个慢，一目了然。

登录 · 发表于 2021-2-15 20:37

本帖最后由 andy520520 于 2021-2-15 20:44 编辑

xukun977 发表于 2021-2-15 20:00
下面用一个具体的例子，给你们展示一下，到底是求逆来的快，还是用克拉默法则来的快。
这样对比一下，就有 ...

搞个简单的2*2矩阵，求出逆矩阵的方法，单位矩阵后面的2*2部分就是逆矩阵，照下面的方法不你那快？

发表于 2021-2-15 20:42

andy520520 发表于 2021-2-15 20:31
即使是真的去求这个逆矩阵，你也可以把把A扩展宽矩阵， [A E] ---> 通过行变换， [E A^-1] ，不你你这 ...

你始终沉迷于大二的《线性代数》上，这样聊天就没意思了。

登录 · 发表于 2021-2-15 20:47

xukun977 发表于 2021-2-15 20:42
你始终沉迷于大二的《线性代数》上，这样聊天就没意思了。

对比下你错哪里？

登录 · 发表于 2021-2-15 21:14

本帖最后由 xukun977 于 2021-2-15 21:21 编辑

我们学校的培养方式，是先有一定手算能力，然后再用软件仿真验证
而不允许只会玩软件，不懂得手算。

现在把上面剩下的部分计算完，然后和楼上的对照。

第5步，把第二步计算结果，和第4步计算结果，做个简单的乘法运算：

类似地，有：

把上面计算出来的4个子矩阵，合并到一起，就求得了A的逆为：

发表于 2021-2-15 21:23

本帖最后由 xukun977 于 2021-2-15 21:49 编辑

andy520520 发表于 2021-2-15 20:47
对比下你错哪里？

请看17楼计算结果。我哪儿错辣？？？

发表于 2021-2-16 11:11

xukun977 发表于 2021-2-15 21:23
请看17楼计算结果。我哪儿错辣？？？

手工计算也不会这种方法，用我上面的拓宽矩阵的方法更简单。

发表于 2021-2-16 11:22

本帖最后由 andy520520 于 2021-2-16 11:29 编辑

xukun977 发表于 2021-2-15 21:23
请看17楼计算结果。我哪儿错辣？？？

拿百度里面的编辑的词条来佐证的的所谓克莱姆法则没有效率，你看下各种线性方程是不是用X1= D1/D

X2 = D2/D , X3 = D3/D ... D !=0 时, 直接给出解的，也不需要直接算出来|A|的行列式的值，方便后续计算

纯手工计算是利用矩阵或者行列式的特点有很多技巧的，比喻行列式的值，在5阶以上是有5！的个排列式子

a1j1 a2j2 a3j3 a4j4 a5j5 * (-1)^N(j1,j2,j3,j4,j5)的和，这个值算起来确实有难度，但实际上如果你采用行列

特性也是很快求出行列式值的，对于任意一个行列式D = 任意一行或列的所有元素与相应的代数余子式的乘积的和。

到底是求逆快，还是用克拉默快？

本帖子中包含更多资源

相关帖子

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

浏览过的版块

坚毅之洋流

核心会员奖章

十世金身

技术导师奖章

奔腾之江水

技术奇才奖章

精英会员奖章