矩阵求逆的快速算法

《矩阵求逆的快速算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、!=km(i,j)=m(i,j)-m(i,k)*m(k,j)，i,j=0,1,...,n-1；i,j!=km(i,k)=-m(i,k)*m(k,k)，i=0,1,...,n-1；i!=k最后，根据在全选主元过程中所记录的行、列交换的信息进行恢复，恢复的原则如下：在全选主元过程中，先交换的行（列）后进行恢复；原来的行（列）交换用列（行）交换来恢复。实现(4阶矩阵)floatInverse(CLAYMATRIX&mOut,constCLAYMATRIX&rhs){CLAYMATRIXm(rhs);DWORDis[4];DWORDjs[4];floatfDet=1.0f;intf=

3、1;for(intk=0;k<4;k++){//第一步，全选主元floatfMax=0.0f;for(DWORDi=k;i<4;i++){for(DWORDj=k;j<4;j++){constfloatf=Abs(m(i,j));if(f>fMax){fMax=f;is[k]=i;js[k]=j;}}}if(Abs(fMax)<0.0001f)return0;if(is[k]!=k){f=-f;swap(m(k,0),m(is[k],0));swap(m(k,1),m(is[k],1));swap(m(k,2),m(is[k],2));swap(m(k,3),m(is[k],

4、3));}if(js[k]!=k){f=-f;swap(m(0,k),m(0,js[k]));swap(m(1,k),m(1,js[k]));swap(m(2,k),m(2,js[k]));swap(m(3,k),m(3,js[k]));}//计算行列值fDet*=m(k,k);//计算逆矩阵//第二步m(k,k)=1.0f/m(k,k);//第三步for(DWORDj=0;j<4;j++){if(j!=k)m(k,j)*=m(k,k);}//第四步for(DWORDi=0;i<4;i++){if(i!=k){for(j=0;j<4;j++){if(j!=k)m(i,j)=m

5、(i,j)-m(i,k)*m(k,j);}}}//第五步for(i=0;i<4;i++){if(i!=k)m(i,k)*=-m(k,k);}}for(k=3;k>=0;k--){if(js[k]!=k){swap(m(k,0),m(js[k],0));swap(m(k,1),m(js[k],1));swap(m(k,2),m(js[k],2));swap(m(k,3),m(js[k],3));}if(is[k]!=k){swap(m(0,k),m(0,is[k]));swap(m(1,k),m(1,is[k]));swap(m(2,k),m(2,is[k]));swap(m(

6、3,k),m(3,is[k]));}}mOut=m;returnfDet*f;}比较　原算法原算法(经过高度优化)新算法加法次数1036139乘法次数17011669需要额外空间16*sizeof(float)34*sizeof(float)25*sizeof(float)结果不言而喻吧。