矩阵求逆操作的复杂度分析
逆矩阵的复杂度分析
1 背景
之前写过一篇关于矩阵复杂度分析的文章，没有想到阅读人数那么多。对于IT相关人士来说，从代码层次再结合基本数学知识，就能够很好地理解矩阵的复杂度如何计算得到和分析。其中一位读者提出“矩阵求逆的复杂度如何分析”。今天就来一起共同探讨一下，笔者知道，矩阵求逆有多种方法，这里就来探讨最基本的方式，其他优化方式，读者可以看完本篇博客后，自行分析，因为原理基本上差不是很多。本篇博客仅仅是抛砖引玉。
2 求逆操作分析
2.1 求逆矩阵基本原理
这里很多读者可以容易忽视掉，先复习一下。
(
A
∣
E
)
=
(
E
∣
A
−
1
)
(A|E) = (E| A^{-1})
(A∣E)=(E∣A−1)
相信大家对这个公式都比较熟悉，即把原矩阵和一个单位矩阵对齐后，进行行列变化，就得到了单位矩阵，右边部分就算逆矩阵。
证明如下：
A
−
1
(
A
∣
E
)
=
(
A
−
1
A
∣
A
−
1
E
)
A^{-1}(A|E) = (A^{-1}A| A^{-1}E)
A−1(A∣E)=(A−1A∣A−1E)
=
(
E
∣
A
−
1
)
= (E| A^{-1})
=(E∣A−1)
思考为什么呢？
因为：
A
−
1
A
=
E
A^{-1}A=E
A−1A=E，右乘
A
−
1
A^{-1}
A−1后：
A
−
1
E
=
A
−
1
A^{-1}E=A^{-1}
A−1E=A−1
故变化的桥梁就是存在 A − 1 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] : 原始矩阵，dxd
ans[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
∗
/
d
e
t
(
A
)
A^{-1} = A^{*}/det(A)
A−1=A∗/det(A)
即先计算A的伴随矩阵，再计算A的行列式值。
前者的复杂度为：
N
∗
O
(
N
!
)
N*O ( N ! )
N∗O(N!)
后者的复杂度为：
N
2
∗
O
(
(
N
−
1
)
!
)
N^2 ∗O((N−1)!)
N2∗O((N−1)!)
故使用伴随矩阵求解方式的复杂度为：
N
∗
O
(
N
!
)
+
N
2
∗
O
(
(
N
−
1
)
!
)
N*O ( N ! ) + N^2 ∗O((N−1)!)
N∗O(N!)+N2∗O((N−1)!)文章来源：https://www.toymoban.com/news/detail-799442.html
ps：本博客只考虑基本的操作，不考虑优化处理
文章来源地址https://www.toymoban.com/news/detail-799442.html
到了这里，关于矩阵求逆操作的复杂度分析（逆矩阵的复杂度分析）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
