矩阵求逆的快速算法.doc

《矩阵求逆的快速算法.doc》由会员分享，可在线阅读，更多相关《矩阵求逆的快速算法.doc（2页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、矩阵求逆的快速算法算法介绍 矩阵求逆在3D程序中很常见，主要应用于求Billboard矩阵。按照定义的计算方法乘法运算，严重影响了性能。在需要大量Billboard矩阵运算时，矩阵求逆的优化能极大提高性能。这里要介绍的矩阵求逆算法称为全选主元高斯-约旦法。 高斯-约旦法（全选主元）求逆的步骤如下： 首先，对于 k 从 0 到 n - 1 作如下几步： 从第 k 行、第 k 列开始的右下角子阵中选取绝对值最大的元素，并记住次元素所在的行号和列号，在通过行交换和列交换将它交换到主元素位置上。这一步称为全选主元。 m(k, k) = 1 / m(k, k) m(k, j) = m(k, j) * m

2、(k, k)，j = 0, 1, ., n-1；j != k m(i, j) = m(i, j) - m(i, k) * m(k, j)，i, j = 0, 1, ., n-1；i, j != k m(i, k) = -m(i, k) * m(k, k)，i = 0, 1, ., n-1；i != k 最后，根据在全选主元过程中所记录的行、列交换的信息进行恢复，恢复的原则如下：在全选主元过程中，先交换的行（列）后进行恢复；原来的行（列）交换用列（行）交换来恢复。 实现(4阶矩阵) float Inverse(CLAYMATRIX& mOut, const CLAYMATRIX& rhs) CL

3、AYMATRIX m(rhs); DWORD is4; DWORD js4; float fDet = 1.0f; int f = 1; for (int k = 0; k 4; k +) / 第一步，全选主元 float fMax = 0.0f; for (DWORD i = k; i 4; i +) for (DWORD j = k; j fMax) fMax = f; isk = i; jsk = j; if (Abs(fMax) 0.0001f) return 0; if (isk != k) f = -f; swap(m(k, 0), m(isk, 0); swap(m(k, 1),

4、 m(isk, 1); swap(m(k, 2), m(isk, 2); swap(m(k, 3), m(isk, 3); if (jsk != k) f = -f; swap(m(0, k), m(0, jsk); swap(m(1, k), m(1, jsk); swap(m(2, k), m(2, jsk); swap(m(3, k), m(3, jsk); / 计算行列值 fDet *= m(k, k); / 计算逆矩阵 / 第二步 m(k, k) = 1.0f / m(k, k); / 第三步 for (DWORD j = 0; j 4; j +) if (j != k) m(k,

5、j) *= m(k, k); / 第四步 for (DWORD i = 0; i 4; i +) if (i != k) for (j = 0; j 4; j +) if (j != k) m(i, j) = m(i, j) - m(i, k) * m(k, j); / 第五步 for (i = 0; i = 0; k -) if (jsk != k) swap(m(k, 0), m(jsk, 0); swap(m(k, 1), m(jsk, 1); swap(m(k, 2), m(jsk, 2); swap(m(k, 3), m(jsk, 3); if (isk != k) swap(m(0, k), m(0, isk); swap(m(1, k), m(1, isk); swap(m(2, k), m(2, isk); swap(m(3, k), m(3, isk); mOut = m; return fDet * f; 比较 原算法 原算法(经过高度优化) 新算法 加法次数 103 61 39 乘法次数 170 116 69 需要额外空间 16 * sizeof(float) 34 * sizeof(float) 25 * sizeof(float) 结果不言而喻吧。