高斯约旦消元法求逆矩阵的思想(分块矩阵的逆矩阵)

P4783【模板】矩阵求逆题目描述求一个N×NN×NN×N的矩阵的逆矩阵。答案对109+710^9+7109+7取模。1.逆矩阵的定义假设AAA是一个方阵,如果存在一个矩阵A−1A^{-1}A−1,使得A−1A=IA^{-1}A=IA−1A=I并且AA−1=IAA^{-1}=IAA−1=I那么,矩阵A就是可逆的,A−1A^{-1}A−1称为A的逆矩阵2.逆矩阵求…

大家好,又见面了,我是你们的朋友全栈君。

luogu P4783 【模板】矩阵求逆

题目描述

求一个 N × N N×N N×N的矩阵的逆矩阵。答案对 1 0 9 + 7 10^9+7 109+7取模。

1.逆矩阵的定义

假设 A A A 是一个方阵,如果存在一个矩阵 A − 1 A^{-1} A1,使得
A − 1 A = I A^{-1}A=I A1A=I
并且
A A − 1 = I AA^{-1}=I AA1=I

那么,矩阵 A 就是可逆的, A − 1 A^{-1} A1 称为 A 的逆矩阵

2.逆矩阵求法 —— 初等变换法(高斯-约旦消元)

0.高斯-约旦消元

详见P3389 【模板】高斯消元法题解部分

高斯约旦消元与高斯消元区别:

高斯消元 -> 消成上三角矩阵 

高斯-约旦消元 -> 消成对角矩阵 

约旦消元法的精度更好,代码更简单,没有回带的过程

void Gauss_jordan(){ 
   
	/***** 行的交换&加减消元 *****/ 
	for(re int i=1,r;i<=n;++i){ 
   	//正在处理第i行 
		r=i;
		for(re int j=i+1;j<=n;++j) 
			if(fabs(a[j][i])>fabs(a[r][i])) r=j;
		if(fabs(a[r][i])<eps){ 
   
			puts("No Solution");return;
		}
		if(i!=r) swap(a[i],a[r]);
		
		for(re int k=1;k<=n;++k){ 
   
		//每一行都处理 
			if(k==i) continue;
			double p=a[k][i]/a[i][i];
			for(re int j=i;j<=n+1;++j) a[k][j]-=p*a[i][j];
		} 
	}	
	
	//上述操作后会剩下对角矩阵,答案要除以系数 
	for(re int i=1;i<=n;++i) printf("%.2lf\n",a[i][n+1]/a[i][i]);
}

1.矩阵求逆

思路

  • A A A的逆矩阵,把 A A A和单位矩阵 I I I放在一个矩阵里
  • A A A进行加减消元使 A A A化成单位矩阵
  • 此时原来单位矩阵转化成逆矩阵

原理
A − 1 ∗ [ A I ] = [ I A − 1 ] A^{-1} * [AI] = [I A^{-1}] A1[AI]=[IA1]

举个栗子

[ 2 − 1 0 − 1 2 − 1 0 − 1 2 ] \left[ \begin{matrix} 2 &amp; -1 &amp; 0 \\ -1 &amp; 2 &amp; -1 \\ 0 &amp; -1 &amp; 2 \end{matrix} \right] 210121012

首先
[ 2 − 1 0 1 0 0 − 1 2 − 1 0 1 0 0 − 1 2 0 0 1 ] \begin{bmatrix} 2 &amp; -1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 \\ -1 &amp; 2 &amp; -1 &amp; 0 &amp; 1 &amp; 0 \\ 0 &amp; -1 &amp; 2 &amp; 0 &amp; 0 &amp; 1 \end{bmatrix} 210121012100010001
对左边进行消元可得
[ 2 − 1 0 1 0 0 0 3 2 − 1 1 2 1 0 0 0 4 3 1 3 2 3 1 ] \left[ \begin{matrix} 2 &amp; -1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 \\ 0 &amp; \frac{3}{2} &amp; -1 &amp; \frac{1}{2} &amp; 1 &amp; 0 \\ 0 &amp; 0 &amp; \frac{4}{3} &amp; \frac{1}{3} &amp; \frac{2}{3} &amp; 1 \end{matrix} \right] 20012300134121310132001
此时已消成上三角矩阵,高斯消元开始回代,但约旦会消成对角矩阵
[ 2 0 0 3 2 1 1 2 0 3 2 0 3 4 3 2 3 4 0 0 4 3 1 3 2 3 1 ] \left[ \begin{matrix} 2 &amp; 0 &amp; 0 &amp; \frac{3}{2} &amp; 1 &amp; \frac{1}{2} \\ 0 &amp; \frac{3}{2} &amp; 0 &amp; \frac{3}{4} &amp; \frac{3}{2} &amp; \frac{3}{4} \\ 0 &amp; 0 &amp; \frac{4}{3} &amp; \frac{1}{3} &amp; \frac{2}{3} &amp; 1 \end{matrix} \right] 200023000342343311233221431
最后每行除以系数
[ 1 0 0 3 4 1 2 1 4 0 1 0 1 2 1 1 2 0 0 1 1 4 1 2 3 4 ] \left[ \begin{matrix} 1 &amp; 0 &amp; 0 &amp; \frac{3}{4} &amp; \frac{1}{2} &amp; \frac{1}{4} \\ 0 &amp; 1 &amp; 0 &amp; \frac{1}{2} &amp; 1 &amp; \frac{1}{2} \\ 0 &amp; 0 &amp; 1 &amp; \frac{1}{4} &amp; \frac{1}{2} &amp; \frac{3}{4} \end{matrix} \right] 10001000143214121121412143
此时右半边即为所求

2.细节

  1. 开long long(不要冒风险,乘法很容易溢出)
  2. 模意义下除以一个数等于乘上逆元,可用快速幂求逆元(费马小定理)

C o d e Code Code

#include<iostream>
#include<cstdio>
#include<cmath>
#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;
}

网上浏览一圈头都要炸掉,线性代数太可怕了,定义好多
最后只看懂了这种方法

有什么问题欢迎评论区指出 :)

参考文章

线性代数之——矩阵乘法和逆矩阵

逆矩阵的几种求法与解析(很全很经典)

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/129183.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • jupyter跟python的关系_jupyter python

    jupyter跟python的关系_jupyter python大家好,我是时间财富网智能客服时间君,上述问题将由我为大家进行解答。jupyter和pycharm区别如下:1、Python是一种广泛使用的高级的、通用的、解释的、动态编程语言。”Python是一种相当古老且流行的语言,它是开源的,常被应用于网站开发(利用Django、Flask等框架)、科学统计计算(NumPy、SciPy等库可以帮助计算)、软件开发等甚至更多。Jupyter项目开…

  • 计算机蓝屏代码0x000000ED,电脑蓝屏代码0x000000ed解决步骤[通俗易懂]

    计算机蓝屏代码0x000000ED,电脑蓝屏代码0x000000ed解决步骤[通俗易懂]电脑蓝屏代码现象是我们在使用电脑中最常见的一种启动问题,令小白用户很头痛。比如,我们在启动电脑的时候,它并没有正常地启动,屏幕反而一片蓝色,出现了一串奇怪的代码:0x000000ed,怎么办?下面,小编给大伙演示电脑蓝屏代码0x000000ed的修复流程。电脑蓝屏代码0x000000ed怎么解决蓝屏代码0x000000ed原因分析:一般是由于磁盘存在错误导致的。有可能是电脑非常关机导致系统错误,…

  • WiFi网络WPA2 KRACK漏洞分析报告「建议收藏」

    WiFi网络WPA2 KRACK漏洞分析报告「建议收藏」作者:阿里安全技术平台团队————————0x00漏洞概述安全研究员MathyVanhoef发现的WPA2协议的KRA(KeyReinstallationAttacks)漏洞,利用WPA2协议标准加密密钥生成机制上的设计缺陷,四次握手协商加密密钥过程中第三个消息报文可被篡改重放,导致在用密钥被重新安装。WiFi网络通过WPA…

  • 智能避障小车_基于单片机的智能玩具车系统设计

    智能避障小车_基于单片机的智能玩具车系统设计【1】背景意义近些年随着国民生活水平的提升,以小车为载体的轮式机器人进入了我们的生活,尤其是在一些布线复杂困难的安全生活区和需要监控的施工作业场合都必须依赖轮式机器人的视频监控技术。因此,基于嵌入式技术的无线通信视频监控轮式机器人应运而生。由于它们与人类工作相比具有成本低廉、安全稳定的优点,目前已经在许多危险作业以及工业场合得到了广泛应用而且轮式机器人不需要像人那样采取过多的保护措施,因此轮式机…

    2022年10月18日
  • SIFT特征点提取「建议收藏」

    SIFT特征点提取「建议收藏」计算机视觉中的特征点提取算法比较多,但SIFT除了计算比较耗时以外,其他方面的优点让其成为特征点提取算法中的一颗璀璨的明珠。SIFT算法的介绍网上有很多比较好的博客和文章,我在学习这个算法的过程中也参看网上好些资料,即使评价比较高的文章,作者在文章中对有些比较重要的细节、公式来历没有提及,可能写博客的人自己明白,也觉得简单,因此就忽略了这些问题,但是对刚入门的人来说,看这些东西,想搞清楚这些是怎么

  • 185 MySQL中TIMESTAMPDIFF和TIMESTAMPADD函数的用法

    185 MySQL中TIMESTAMPDIFF和TIMESTAMPADD函数的用法https://blog.csdn.net/zmxiangde_88/article/details/8011661SQL里面怎么用呢TIMESTAMPDIFF(DAY,'”.date(‘Y-m-d’,$nowtime).”‘,from_unixtime(birthday_time,’%Y-%m-%d’))=1生日的前一天发短信,送祝福…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号