矩阵求逆操作的复杂度分析
逆矩阵的复杂度分析

1 背景

之前写过一篇关于矩阵复杂度分析的文章，没有想到阅读人数那么多。对于IT相关人士来说，从代码层次再结合基本数学知识，就能够很好地理解矩阵的复杂度如何计算得到和分析。其中一位读者提出“矩阵求逆的复杂度如何分析”。今天就来一起共同探讨一下，笔者知道，矩阵求逆有多种方法，这里就来探讨最基本的方式，其他优化方式，读者可以看完本篇博客后，自行分析，因为原理基本上差不是很多。本篇博客仅仅是抛砖引玉。

2 求逆操作分析

2.1 求逆矩阵基本原理

这里很多读者可以容易忽视掉，先复习一下。
$$(A|E)=(E|A^{-1})$$
相信大家对这个公式都比较熟悉，即把原矩阵和一个单位矩阵对齐后，进行行列变化，就得到了单位矩阵，右边部分就算逆矩阵。

证明如下：
$$A^{-1}(A|E)=(A^{-1}A|A^{-1}E)$$
$$=(E|A^{-1})$$
思考为什么呢？

因为：
$$A^{-1}A=E$$，右乘$$A^{-1}$$后：
$$A^{-1}E=A^{-1}$$

故变化的桥梁就是存在$$A^{-1}$$

3 逆矩阵复杂度分析-高斯消元法

3.1 代码层次

/* 函数说明：将原矩阵a和一个单位矩阵E作成一个大矩阵(A,E)， 用初等变换将大矩阵中的a变成E，则会得到(E,A^{-1})的形式 * */ void inverseMatrix(double arc[d][d], int n, double ans[d][d])//计算矩阵的逆 {/*d = n : 表示维度arc[d][d] : 原始矩阵，dxdans[d][d] : 变化后的结果矩阵，dxd ，一开始初始化为单位矩阵*/int i, j, k;//列double max, tempA, tempB, P;int max_num;double arcCopy[d][d];memcpy(arcCopy, arc, 288);for (i = 0; i < n; i++){ans[i][i] = 1;}for (i = 0; i < n; i++)//第i列{max = fabs(arcCopy[i][i]);max_num = i;for (j = i + 1; j < n; j++)//选出主元{if (fabs(arcCopy[j][i]) > max){max = fabs(arcCopy[j][i]);max_num = j;}}for (k = 0; k < n; k++)//交换行{tempA = arcCopy[i][k];arcCopy[i][k] = arcCopy[max_num][k];arcCopy[max_num][k] = tempA;tempB = ans[i][k];ans[i][k] = ans[max_num][k];ans[max_num][k] = tempB;}for (k = i + 1; k < n; k++){P = arcCopy[k][i] / arcCopy[i][i];for (j = 0; j < n; j++){arcCopy[k][j] = arcCopy[k][j] - arcCopy[i][j] * P;ans[k][j] = ans[k][j] - ans[i][j] * P;}}}for (i = 0; i < n; i++)//行{P = arcCopy[i][i];for (j = i; j < n; j++){arcCopy[i][j] = arcCopy[i][j] / P;}for (j = 0; j < n; j++){ans[i][j] = ans[i][j] / P;}}for (i = n - 1; i > 0; i--){for (j = i - 1; j >= 0; j--){for (k = 0; k < n; k++){ans[j][k] = ans[j][k] - ans[i][k] * arcCopy[j][i];}}} }

3.2 结果

逆矩阵时间复杂为：O(n^3)

开销代价最大是这里，

for (i = n - 1; i > 0; i--){for (j = i - 1; j >= 0; j--){for (k = 0; k < n; k++){ans[j][k] = ans[j][k] - ans[i][k] * arcCopy[j][i];}}}

4 逆矩阵复杂度分析-伴随矩阵

这个比较直接：
$$A^{-1}=A^{\ast }/det(A)$$
即先计算A的伴随矩阵，再计算A的行列式值。
前者的复杂度为：$$N\ast O(N!)$$
后者的复杂度为：$$N^2\ast O((N-1)!)$$

故使用伴随矩阵求解方式的复杂度为：
$$N\ast O(N!)+N^2\ast O((N-1)!)$$

ps：本博客只考虑基本的操作，不考虑优化处理

总结

以上是生活随笔为你收集整理的矩阵求逆操作的复杂度分析（逆矩阵的复杂度分析）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。