文章目录
一、问题引出二、原理2.1 矩阵求逆原理2.2 矩阵消元原理
三、举例四、题目链接五、代码实现5.1 整数逆元逆矩阵5.2 浮点逆矩阵
六、拓展:逆矩阵求法6.1 LU分解法6.2 SVD分解法6.3 QR分解法
一、问题引出
给定一个
n
×
n
n \times n
n×n 的矩阵
A
A
A ,我们想求得一个矩阵
B
B
B 使得
∣
A
×
B
∣
|A \times B|
∣A×B∣ 即
A
A
A 矩阵和
B
B
B 矩阵的积矩阵的行列式为
1
1
1 ,那么这个
B
B
B 矩阵就是
A
A
A 矩阵的逆矩阵,或者说
A
×
B
A \times B
A×B 得到单位矩阵
E
E
E
二、原理
2.1 矩阵求逆原理
我们先构造出一个
n
×
2
n
n\times 2n
n×2n 的增广矩阵
(
A
,
I
n
)
(A,I_n)
(A,In)然后用高斯消元法将这个增广矩阵化为最简形式
(
I
n
,
A
−
1
)
(I_n,A^{-1})
(In,A−1) ,此时的增广部分就是
A
A
A 矩阵的逆矩阵,如果最后简化的左半部分矩阵不是单位矩阵那么说明矩阵
A
A
A 不可逆
2.2 矩阵消元原理
对于一个矩阵
A
A
A ,我们从第
1
1
1 行到第
n
n
n 行不断选取第
i
i
i 列不为
0
0
0 的行,然后做一个行变换(交换两行,使得当前的第
i
i
i 行的第
i
i
i 列不为0)然后将当前的第
i
i
i 行做一个初等变换,也就是都除以
A
[
i
]
[
i
]
A[i][i]
A[i][i] 这样的话就能让第
i
i
i 行第
i
i
i 列变为
1
1
1将第
i
i
i 行下面的所有行的第
i
i
i 列全部消掉,此时就构成了一个上三角矩阵此时已经构成了一个阶梯型矩阵,我们再从下往上不断将上半矩阵同理消掉即可
三、举例
我们要求的
A
A
A 矩阵如下:
[
2
1
1
3
2
1
2
1
2
]
\begin{bmatrix} 2 \ 1 \ 1 \\ 3 \ 2 \ 1 \\ 2 \ 1 \ 2 \\ \end{bmatrix}
⎣⎡2 1 13 2 12 1 2⎦⎤
我们构造出增广矩阵:
[
2
1
1
1
0
0
3
2
1
0
1
0
2
1
2
0
0
1
]
\begin{bmatrix} 2 \ 1 \ 1 \ 1 \ 0 \ 0 \\ 3 \ 2 \ 1 \ 0 \ 1 \ 0\\ 2 \ 1 \ 2 \ 0 \ 0 \ 1 \\ \end{bmatrix}
⎣⎡2 1 1 1 0 03 2 1 0 1 02 1 2 0 0 1⎦⎤
开始行变换,消除下三角
[
1
1
/
2
1
/
2
1
/
2
0
0
0
1
−
1
−
3
2
0
0
0
1
−
1
0
1
]
\begin{bmatrix} 1 \ \ 1/2 \ \ 1/2 \ 1/2 \ 0 \ 0 \\ 0 \ 1 \ \ \ -1 \ -3 \ \ \ 2 \ \ 0\\ 0 \ \ 0 \ \ \ \ 1 \ -1 \ \ \ \ 0 \ \ 1 \\ \end{bmatrix}
⎣⎡1 1/2 1/2 1/2 0 00 1 −1 −3 2 00 0 1 −1 0 1⎦⎤ 3. 从下往上消除上三角形
[
1
0
0
3
−
1
−
1
0
1
0
−
4
2
1
0
0
1
−
1
0
1
]
\begin{bmatrix} 1 \ 0 \ \ 0 \ 3 \ -1 \ -1 \\ 0 \ 1 \ 0 \ -4 \ 2 \ 1\\ 0 \ 0 \ 1 \ -1 \ 0 \ 1 \\ \end{bmatrix}
⎣⎡1 0 0 3 −1 −10 1 0 −4 2 10 0 1 −1 0 1⎦⎤
四、题目链接
https://www.luogu.com.cn/problem/P4783
五、代码实现
5.1 整数逆元逆矩阵
对于这个整数逆元逆矩阵,需要注意的一点是模数最好选择一个质数,否则很容易存在逆元不存在的情况,导致求解出来的逆矩阵不正确
#include
#define re register
#define il inline
#define ll long long
using namespace std;
il ll read(){
ll s=0,f=0;char c=getchar();
while(c<'0'||c>'9') f=(c=='-'),c=getchar();
while(c>='0'&&c<='9') s=(s<<3)+(s<<1)+(c^'0'),c=getchar();
return f?-s:s;
}
const int N=405,mod=1e9+7;
int n;
ll a[N][N<<1];
il ll qpow(ll x,ll k){
ll ans=1;
while(k){
if(k&1) ans=ans*x%mod;
x=x*x%mod;
k>>=1;
}
return ans%mod;
}
il void Gauss_j(){
for(re int i=1,r;i<=n;++i){
r=i;
for(re int j=i+1;j<=n;++j)
if(a[j][i]>a[r][i]) r=j;
if(r!=i) swap(a[i],a[r]);
if(!a[i][i]){puts("No Solution");return;}
int kk=qpow(a[i][i],mod-2); //求逆元
for(re int k=1;k<=n;++k){
if(k==i) continue;
int p=a[k][i]*kk%mod;
for(re int j=i;j<=(n<<1);++j)
a[k][j]=((a[k][j]-p*a[i][j])%mod+mod)%mod;
}
for(re int j=1;j<=(n<<1);++j) a[i][j]=(a[i][j]*kk%mod);
//更新当前行 如果放在最后要再求一次逆元,不如直接放在这里
}
for(re int i=1;i<=n;++i){
for(re int j=n+1;j<(n<<1);++j) printf("%lld ",a[i][j]);
printf("%lld\n",a[i][n<<1]);
}
}
int main(){
n=read();
for(re int i=1;i<=n;++i)
for(re int j=1;j<=n;++j)
a[i][j]=read(),a[i][i+n]=1;
Gauss_j();
return 0;
}
5.2 浮点逆矩阵
对于浮点逆矩阵那么直接用高斯消元的方式做就好了
#include
using namespace std;
#define ll long long
#define mod 26
#define endl "\n"
#define PII pair
#define INF 0x3f3f3f3f
#define EPS 0.00001
const int N = 1e2+10;
ll n;
double a[N][N],b[N][N];
void output(double a[N][N],double b[N][N]){
//调试输出
发表评论