2025年全网最最最最最详细的c++算法讲解（三）矩阵乘法进阶与高斯消元法

大家好，我是讯享网，很高兴认识大家。

建议各位在看本篇博客之前，先看一下我的博客的算法讲解（二），了解一些关于矩阵乘法和矩阵的相关知识

这里先来一道矩阵乘法好题，前几天看到的

n的范围是n<=

但其实不然，如果我们直接进行矩阵快速幂，复杂度是n^2*logk的

显然跑不过。

那么我们这时候就可以，动动脑筋了。好像在前一篇文章里，我提到过这么一个结论

只要当A矩阵为x*y，B矩阵的乘法y*z时，乘出的C矩阵是一个x*z的矩阵！！！

那么，我们要是可以将x和yT相乘就好了哎

展开式子，根据矩阵乘法的结合律，我们就会惊奇的发现：

Ak=(yTx)(yTx)…(yTx)
=yT(xyT)(xyT)…(xyT)x

=<x,y>^k-1A

woc 骚操作呀！时间复杂度直接O(n^2 log k)-->O(log k+n^2)

社会社会

一道华丽的分割线------------------------------------

好啦，进入正题。

原谅我的懒.....

讯享网

对于一个Ax=b的线性方程组

若b≠0，则称Ax=b为非齐次线性方程组

在解方程之前，我们先介绍一下矩阵的初等行变换

矩阵的三种初等行变换
(1)将A的第i行与第j行对换
(2)将A的第i行乘以非零常数k
(3)将A第i行的k倍加到第j行

并且并且并且------矩阵的初等行变换不改变线性方程组的解！

对矩阵A做一次初等行变换，等价于，在A的左边乘一个初等矩阵

这是矩阵行变换中常用的三个初等矩阵

Eij 对换第i行与第j行
Ei(k) 第i行乘以k
Eij(k) 第i行的k倍加到第j行

在高斯消元中，我们普遍是将矩阵化为最简阶梯型矩阵：

若矩阵的每个非零行的上方没有零行，且各个非零行自左向右的第一个非零元素a1j1,a2j2,…,arjr所在列的编号满足j1<j2<…<jr，则称该矩阵为阶梯形矩阵。其中第j1列，第j2列，…，第jr列被称为矩阵的主元列。

若阶梯形矩阵中个非零行自左向右第一个非零元素均为1，他们所在列的其余元素均为0，则称该阶梯形矩阵为最简阶梯形矩阵。

任意非零矩阵A只经初等行变换可化为阶梯形矩阵。
该阶梯形矩阵中主元列的个数称为矩阵A的秩，记作rank(A)

那么我们该如何求矩阵的秩？化为阶梯形矩阵！

如何求方程组的解？化为最简洁阶梯型矩阵！

如何只通过行变换将任意矩阵化为阶梯形矩阵？ Gauss消元法！！！

大概步骤就是

i：1~n k：当前已经选中的行数（矩阵的秩）
①挑选未被选中的某一行，满足这一行的第i列不为0
(若所有未被选择的行中，第i列都为0，则第i列不为主元列)
②将这一行换到第k+1行

③将这一行的若干倍加到其它未被选中的行上，使得它们的第i列变成0

最后求解即可。

这里注意

若rank(A)=n，则只有零解
若rank(A)=r<n，则有非零解
且非零解有n-r个自由变量

基础解系有n-r个解

若rank(A)≠rank([A,b])，则非齐次方程组无解
若rank(A)=rank([A,b])=n，则非齐次方程组有唯一解解

若rank(A)=rank([A,b])<n，则非齐次方程组有无数组解

我们需要在求解之前判断解的情况！！！！

上代码

bool gsxy() { int k=1; for (int i=1;i<=n;i++) { int now = k; while (now<=n && !a[now][i]) now++; if (now == n+1) continue; for (int j=1;j<=n+1;j++) swap(a[now][j],a[k][j]); for (int j=1;j<=n;j++) { if (j!=k){ double t = a[j][i]/a[k][i]; for (int p=1;p<=n+1;p++) a[j][p]=a[j][p]-a[k][p]*t; } } k++; } if (a[k][n+1]) return false; if (k-1<n) return false; for (int i=1;i<=k-1;i++) a[i][n+1]=a[i][n+1]/a[i][i]; }

讯享网

那么对于一些对解取余的题

我就在除法上，就需要逆元了

讯享网void gaosixiaoyuan() { int k=1; for (int i=1;i<=n;i++) { int now=k; while (now<=n && !a[now][i]) now++; if (now==n+1) continue; for (int j=1;j<=n+1;j++) swap(a[now][j],a[k][j]); int inv=power(a[k][i],mod-2); for (int j=1;j<=n;j++) if (j!=k) { int t=(long long)*a[j][i]*inv%mod; for (int p=1;p<=n+1;p++) a[j][p]=(a[j][p]-(long long)*t*a[k][p]%mod+mod)%mod; } k++; } if (a[k][n+1]) return false; if (k-1<n) return false; for (int i=1;i<=k;i++) a[i][n+1]=1ll*a[i][n+1]*power(a[i][i],mod-2)%mod; }

差别不大主要是逆元

啦啦啦高斯消元的讲解就到这了~

希望大家能懂嗯不懂可以加我有事情随意交流

如果您们能从我的博客中得到任何一点收获，都是我莫大的荣幸

共勉！

from y_immortal

2025年全网最最最最最详细的c++算法讲解（三）矩阵乘法进阶与高斯消元法

相关推荐