前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >矩阵求逆的快速算法[通俗易懂]

矩阵求逆的快速算法[通俗易懂]

作者头像
全栈程序员站长
发布于 2022-11-16 17:48:18
1.4K0
发布于 2022-11-16 17:48:18
举报
文章被收录于专栏：全栈程序员必看

作者：龚敏敏

算法介绍

矩阵求逆在3D程序中很常见，主要应用于求Billboard矩阵。按照定义的计算方法乘法运算，严重影响了性能。在需要大量Billboard矩阵运算时，矩阵求逆的优化能极大提高性能。这里要介绍的矩阵求逆算法称为全选主元高斯-约旦法。

高斯-约旦法（全选主元）求逆的步骤如下：

首先，对于 k 从 0 到 n – 1 作如下几步：

  1. 从第 k 行、第 k 列开始的右下角子阵中选取绝对值最大的元素，并记住次元素所在的行号和列号，在通过行交换和列交换将它交换到主元素位置上。这一步称为全选主元。
  2. m(k, k) = 1 / m(k, k)
  3. m(k, j) = m(k, j) * m(k, k)，j = 0, 1, …, n-1；j != k
  4. m(i, j) = m(i, j) – m(i, k) * m(k, j)，i, j = 0, 1, …, n-1；i, j != k
  5. m(i, k) = -m(i, k) * m(k, k)，i = 0, 1, …, n-1；i != k

最后，根据在全选主元过程中所记录的行、列交换的信息进行恢复，恢复的原则如下：在全选主元过程中，先交换的行（列）后进行恢复；原来的行（列）交换用列（行）交换来恢复。

实现(4阶矩阵)

代码语言：javascript
复制
float Inverse(CLAYMATRIX& mOut, const CLAYMATRIX& rhs)

Jetbrains全家桶1年46，售后保障稳定

代码语言：javascript
复制
{
代码语言：javascript
复制
	CLAYMATRIX m(rhs);
代码语言：javascript
复制
	DWORD is[4];
代码语言：javascript
复制
	DWORD js[4];
代码语言：javascript
复制
	float fDet = 1.0f;
代码语言：javascript
复制
	int f = 1;
代码语言：javascript
复制
	for (int k = 0; k < 4; k ++)
代码语言：javascript
复制
	{
代码语言：javascript
复制
		// 第一步，全选主元
代码语言：javascript
复制
		float fMax = 0.0f;
代码语言：javascript
复制
		for (DWORD i = k; i < 4; i ++)
代码语言：javascript
复制
	{
代码语言：javascript
复制
			for (DWORD j = k; j < 4; j ++)
代码语言：javascript
复制
			{
代码语言：javascript
复制
				const float f = Abs(m(i, j));
代码语言：javascript
复制
				if (f > fMax)
代码语言：javascript
复制
				{
					fMax	= f;
代码语言：javascript
复制
					is[k]	= i;
代码语言：javascript
复制
					js[k]	= j;
代码语言：javascript
复制
				}
代码语言：javascript
复制
代码语言：javascript
复制
				}
代码语言：javascript
复制
				}
代码语言：javascript
复制
		if (Abs(fMax) < 0.0001f)
代码语言：javascript
复制
			return 0;
代码语言：javascript
复制
		if (is[k] != k)
代码语言：javascript
复制
			{
代码语言：javascript
复制
			f = -f;
代码语言：javascript
复制
			swap(m(k, 0), m(is[k], 0));
代码语言：javascript
复制
			swap(m(k, 1), m(is[k], 1));
代码语言：javascript
复制
			swap(m(k, 2), m(is[k], 2));
代码语言：javascript
复制
			swap(m(k, 3), m(is[k], 3));
代码语言：javascript
复制
				}
代码语言：javascript
复制
		if (js[k] != k)
代码语言：javascript
复制
			{
代码语言：javascript
复制
			f = -f;
代码语言：javascript
复制
			swap(m(0, k), m(0, js[k]));
代码语言：javascript
复制
			swap(m(1, k), m(1, js[k]));
代码语言：javascript
复制
			swap(m(2, k), m(2, js[k]));
代码语言：javascript
复制
			swap(m(3, k), m(3, js[k]));
代码语言：javascript
复制
				}
代码语言：javascript
复制
		// 计算行列值
代码语言：javascript
复制
		fDet *= m(k, k);
代码语言：javascript
复制
		// 计算逆矩阵
代码语言：javascript
复制
		// 第二步
代码语言：javascript
复制
		m(k, k) = 1.0f / m(k, k);
代码语言：javascript
复制
		// 第三步
代码语言：javascript
复制
		for (DWORD j = 0; j < 4; j ++)
代码语言：javascript
复制
			{
代码语言：javascript
复制
			if (j != k)
代码语言：javascript
复制
				m(k, j) *= m(k, k);
代码语言：javascript
复制
				}
代码语言：javascript
复制
		// 第四步
代码语言：javascript
复制
		for (DWORD i = 0; i < 4; i ++)
代码语言：javascript
复制
			{
代码语言：javascript
复制
			if (i != k)
代码语言：javascript
复制
			{
代码语言：javascript
复制
				for	(j = 0; j < 4; j ++)
代码语言：javascript
复制
			{
代码语言：javascript
复制
			if (j != k)
代码语言：javascript
复制
						m(i, j) = m(i, j) - m(i, k) * m(k, j);
				}
代码语言：javascript
复制
				}
代码语言：javascript
复制
				}
代码语言：javascript
复制
		// 第五步
代码语言：javascript
复制
		for (i = 0; i < 4; i ++)
代码语言：javascript
复制
			{
代码语言：javascript
复制
			if (i != k)
代码语言：javascript
复制
				m(i, k) *= -m(k, k);
代码语言：javascript
复制
				}
代码语言：javascript
复制
				}
代码语言：javascript
复制
	for	(k = 3; k >= 0; k --)
代码语言：javascript
复制
			{
代码语言：javascript
复制
		if (js[k] != k)
代码语言：javascript
复制
			{
代码语言：javascript
复制
			swap(m(k, 0), m(js[k], 0));
代码语言：javascript
复制
			swap(m(k, 1), m(js[k], 1));
代码语言：javascript
复制
			swap(m(k, 2), m(js[k], 2));
代码语言：javascript
复制
			swap(m(k, 3), m(js[k], 3));
代码语言：javascript
复制
				}
代码语言：javascript
复制
		if (is[k] != k)
代码语言：javascript
复制
		{
			swap(m(0, k), m(0, is[k]));
代码语言：javascript
复制
			swap(m(1, k), m(1, is[k]));
代码语言：javascript
复制
			swap(m(2, k), m(2, is[k]));
代码语言：javascript
复制
			swap(m(3, k), m(3, is[k]));
代码语言：javascript
复制
				}
代码语言：javascript
复制
				}
代码语言：javascript
复制
	mOut = m;
代码语言：javascript
复制
	return fDet * f;
代码语言：javascript
复制
				}
代码语言：javascript
复制

比较

原算法

原算法(经过高度优化)

新算法

加法次数

103

61

39

乘法次数

170

116

69

需要额外空间

16 * sizeof(float)

34 * sizeof(float)

25 * sizeof(float)

结果不言而喻吧。

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

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

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022年11月2日 ，如有侵权请联系 cloudcommunity@tencent.com 删除
编程算法
https
网络安全

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

编程算法
https
网络安全
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 实现(4阶矩阵)
  • 比较
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2024 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论