• C语言求矩阵的逆（初等行变换法）

    初等变换法是常用的矩阵求逆方法之一

    相对于伴随法，初等行变换法有着较低的时间复杂度，可以进行相对高维的矩阵运算，但同时也会损失一点点精度。

    伴随法可参考之前的博客：C语言求矩阵的逆（伴随法）

    LU矩阵分解法求逆可参考：LU分解法求矩阵逆

    更新：

    • 原代码在进行增广矩阵进行内存拷贝的时，使用的是n（2*col），应改为col(原矩阵的列)，此处已做更改，并在原代码中指出。
    • 最后释放内存时需要循环释放，已做修改。
    • _msize函数在Mac/Linux中无法使用，这里给出了另一种解决思路，见方法二。
    • 更改选主元时的bug。

    目录

    数学原理

    矩阵的初等行变换

    利用增广矩阵求逆

    选择主元

    程序设计

    法一

    整体代码

    测试

    法二

    整体代码

    测试 

    数学原理

    矩阵的初等行变换

    矩阵的初等变换又分为矩阵的初等行变换和矩阵的初等列变换。矩阵的初等行变换和初等列变换统称为初等变换。另外：分块矩阵也可以定义初等变换。

    定义：如果B可以由A经过一系列初等变换得到，则称矩阵A与B称为等价。

    数域V上的矩阵具有以下三种行变换：

    1）以V中一个非零的数，乘以矩阵的某一行

    2）把矩阵的某一行的a倍加到另一行(a∈V)

    3）互换矩阵中两行的位置

    矩阵A通过以上三种行变换变成矩阵B，称为A→B

    （注意：不要与行列式的行变换性质混淆）

    利用增广矩阵求逆

    如果想求矩阵A的逆，可以通过拼上一个单位E矩阵，形成A|E的增广矩阵，通过初等行变换使其成为E|B，B就是A的逆矩阵。

    例如：

    gif.latex?A" role="presentation">gif.latex?A

    (1)形成A|E

    gif.latex?C" role="presentation">gif.latex?C

    (2)进行初等行变换，A|E→E|B

    gif.latex?C" role="presentation">gif.latex?C

    gif.latex?" role="presentation">gif.latex?

    逆矩阵B则是

     gif.latex?B" role="presentation">gif.latex?B

    选择主元

    主元就是在矩阵消去过程中，每列的要保留的非零元素，用它可以把该列其他消去。在阶梯型矩阵中，主元就是每个非零行第一个非零元素就是主元。

    高斯消去法在消元过程中可能出现零主元，即a_{kk}^{n}=0，这时消元过程将无法进行；也可能主元绝对值非常小，用它做除法将会导致舍入误差的扩散，使数值解不可靠。解决该问题的办法是避免使用绝对值过小的元素作主元。

    选择主元的方法：

    1）找到主对角线以下每列最大的数Max所在的行数k

    2）利用初等行变换——换行变换，将k行与当前主元行互换（记录总共换行次数n）

    3）以当前主元行为基，利用初等行变换——消法变换，将主对角线下方消0

    4）行列式每次换行需变号，行列式最后的符号为-1^{n}

    5）每次进行高斯消去前都必须选择主元，计算n维的行列式，则需要进行n-1次主元选择

    程序设计

    法一

    整体流程：

    1）判断传入指针是否为空，判断矩阵是否为方针

    2）为增广矩阵、输出的逆矩阵开辟空间，并初始化为0

    3）将原矩阵中的数据拷贝到增广矩阵中，并将增广矩阵右侧化为单位阵

    4）逐列开始，选择主元，将其他位置化为0，每列阶梯位置化为1

    6）将增广矩阵右侧的逆矩阵拷贝到输入矩阵中，并释放增广矩阵内存

    整体代码

    1. #include
    2. #include
    3. #include
    4. #include
    5.  
    6. double** Matrix_inver(double** src)
    7. {
    8. 	//step 1
    9. 	//判断指针是否为空
    10. 	if (src == NULL)exit(-1);
    11. 	int i, j, k, row, col, n，principal;
    12. 	double** res, ** res2,tmp;//res为增广矩阵，res为输出的逆矩阵
    13.     double Max;
    14. 	//判断矩阵维数
    15. 	row = (double)_msize(src) / (double)sizeof(double*);
    16. 	col = (double)_msize(*src) / (double)sizeof(double);
    17. 	if (row != col)exit(-1);
    18. 	//step 2
    19. 	res = (double**)malloc(sizeof(double*) * row);
    20. 	res2 = (double**)malloc(sizeof(double*) * row);
    21. 	n = 2 * row;
    22. 	for (i = 0; i < row; i++)
    23. 	{
    24. 		res[i] = (double*)malloc(sizeof(double) * n);
    25. 		res2[i] = (double*)malloc(sizeof(double) * col);
    26. 		memset(res[i], 0, sizeof(res[0][0]) * n);//初始化
    27. 		memset(res2[i], 0, sizeof(res2[0][0]) * col);
    28. 	}
    29. 	//step 3
    30. 	//进行数据拷贝
    31. 	for (i = 0; i < row; i++)
    32. 	{
    33.     //此处源代码中的n已改为col，当然方阵的row和col相等，这里用col为了整体逻辑更加清晰
    34. 		memcpy(res[i], src[i], sizeof(res[0][0]) * col);
    35. 	}
    36. 	//将增广矩阵右侧变为单位阵
    37. 	for (i = 0; i < row; i++)
    38. 	{
    39. 		for (j = col; j < n; j++)
    40. 		{
    41. 			if (i == (j - row))
    42. 				res[i][j] = 1.0;
    43. 		}
    44. 	}
    45. 	
    46. 	for (j = 0; j < col; j++)
    47. 	{
    48.        //step 4
    49. 	   //整理增广矩阵，选主元
    50. 		principal = j;
    51.         Max = fabs(res.[principal][j]); // 用绝对值比较
    52.         // 默认第一行的数最大
    53.         // 主元只选主对角线下方
    54.         for (i = j; i < row; i++)
    55.         {
    56.             if (fabs(res.[i][j]) > Max)
    57.             {
    58.                 principal = i;
    59.                 Max = fabs(res.[i][j]);
    60.             }
    61.         }
    62.         if (j != principal)
    63.         {
    64.             for (k = 0; k < n; k++)
    65.             {
    66.                 tmp = res.[principal][k];
    67.                 res.[principal][k] = res.[j][k];
    68.                 res.[j][k] = tmp;
    69.             }
    70.         }
    71.         //step 5
    72. 		//将每列其他元素化0
    73. 		for (i = 0; i < row; i++)
    74. 		{
    75. 			if (i == j || res[i][j] == 0)continue;
    76. 			double b = res[i][j] / res[j][j];
    77. 			for (k = 0; k < n; k++)
    78. 			{
    79. 				res[i][k] += b * res[j][k] * (-1);
    80. 			}
    81. 		}
    82. 		//阶梯处化成1
    83. 		double a = 1.0 / res[j][j];
    84. 		for (i = 0; i < n; i++)
    85. 		{
    86. 			res[j][i] *= a;
    87. 		}
    88. 	}
    89. 	//step 6
    90. 	//将逆矩阵部分拷贝到res2中
    91. 	for (i = 0; i < row; i++)
    92. 	{
    93. 		memcpy(res2[i], res[i] + row, sizeof(res[0][0]) * row);
    94. 	}
    95. 	//必须释放res内存！
    96.     for(i = 0; i < row; i++)
    97.     {
    98.         free(res[i]);
    99.     }
    100.     free(res);
    101. 	return res2;
    102. }

    上述代码中：

    函数传入的参数需是以malloc开辟的动态矩阵，如固定为二维数组，需自行更改 

    step 1：

    • row = (double)_msize(src) / (double)sizeof(double*); 
    • col = (double)_msize(*src) / (double)sizeof(double); 
    • 为判断矩阵的维数；
    • 其中_msize为库函数，需要包含头文件                                           
    • 返回指针指向内存的小心，单位为字节。

    step 2： 

    • 增广矩阵的行数不变，列数是原来的2倍；
    • 对照该方法开辟矩阵空间，便可以理解step1中如何计算矩阵维数。

    step 3：

    • memset和memcpy都需要包含头文件
    • 需要注意memset是以字节对内存进行赋值的，对非字符（char类型）的类型进行赋值时，只使用赋0或-1。

    step 4：

    • 选择主元：该步骤具有两层意义：
    • 1）相对程度上提高计算精度
    • 2）保证阶梯处的数都非0

    step 5：

    • j代表从每列开始进行消0，i和k代表行和列；
    • 不要混淆j和k：j代表消零的大循环，k代表赋值的小循环。

    step 6：

    • res[i] + row代表只拷贝增广矩阵中逆矩阵部分，函数结束前必须释放增广矩阵的内存，否则将造成内存泄漏。

    关于上述函数不太理解的地方可以参考之前发的判断矩阵维数和伴随法求逆矩阵

    C语言动态内存部分可参考C语言动态内存管理

    测试

    相关测试函数（创建矩阵，初始化矩阵，打印矩阵）

    1. double** MakeMat(int n)
    2. {
    3. 	int i = 0;
    4. 	if (n <= 0)exit(-1);
    5. 	double** res = (double**)malloc(sizeof(double*) * n);
    6. 	if (res == NULL)exit(-1);
    7. 	for (i = 0; i < n; i++)
    8. 	{
    9. 		res[i] = (double*)malloc(sizeof(double) * n);
    10. 	}
    11. 	return res;
    12. }
    13.  
    14. void InitMat(double** src)
    15. {
    16. 	if (src == NULL)exit(-1);
    17. 	int i, j, n;
    18. 	n = (double)_msize(src) / (double)sizeof(double*);
    19. 	for (i = 0; i < n; i++)
    20. 	{
    21. 		for (j = 0; j < n; j++)
    22. 		{
    23. 			src[i][j] = pow(i,j);
    24. 		}
    25. 	}
    26. }
    27.  
    28. void print(double** src)
    29. {
    30. 	if (src == NULL)exit(-1);
    31. 	putchar('\n');
    32. 	int i, j, row,col;
    33. 	row = (double)_msize(src) / (double)sizeof(double*);
    34. 	col = (double)_msize(*src) / (double)sizeof(double);
    35. 	for (i = 0; i < row; i++)
    36. 	{
    37. 		for (j = 0; j < col; j++)
    38. 		{
    39. 			printf("%9.4lf", src[i][j]);
    40. 		}
    41. 		putchar('\n');
    42. 	}
    43. }

    主函数测试：

    1. int main()
    2. {
    3. 	int n = 5;
    4. 	double** arr = MakeMat(n);
    5. 	InitMat(arr);
    6. 	double** res = Matrix_inver(arr);
    7. 	printf("原矩阵:>");
    8. 	print(arr);
    9. 	printf("逆矩阵:>");
    10. 	print(res);
    11. 	return 0;
    12. }

    打印结果：

    6281a4338e53442c8dfb5ebc5b033e59.png

     如果矩阵接近奇异值，计算结果会不准确；如果矩阵秩亏，会输出无效值（nan）。

    法二

    整体代码

    由于无法利用_msize函数直接调取内存，又不想在计算时手动输入矩阵的维数，不妨转换一下思路：在创建矩阵时就把矩阵的行和列的信息保存下来，调用矩阵时直接读取矩阵信息即可。

    于是需要创建一个矩阵的结构体：

    1. typedef struct Matrix
    2. {
    3.     int row;
    4.     int col;
    5.     double **data;
    6. } Matrix, *pMatrix;

    其中row、col保存矩阵的行、列，data指针与原来的方法一样，通过row和col为矩阵开辟内存，因此开辟矩阵的函数如下：

    1. Matrix MakeMatrix(int row, int col)
    2. {
    3. 	int i = 0;
    4. 	Matrix arr = {0};
    5. 	arr.row = row;
    6. 	arr.col = col;
    7. 	arr.data = (double **)malloc(sizeof(double *) * arr.row);
    8. 	if (arr.data == NULL)
    9. 		exit(-1);
    10. 	for (i = 0; i < arr.row; i++)
    11. 	{
    12. 		arr.data[i] = (double *)malloc(sizeof(double) * arr.col);
    13. 		memset(arr.data[i], 0, sizeof(double) * arr.col);
    14. 	}
    15. 	return arr;
    16. }

    此外，由于生成矩阵时是循环开辟内存的，因此在销毁矩阵时依然需要循环销毁，销毁矩阵内存的函数如下：

    1. void free_Matrix(Matrix arr)
    2. {
    3. 	int i;
    4. 	for (i = 0; i < arr.row; i++)
    5. 	{
    6. 		free(arr.data[i]);
    7. 	}
    8.     free(arr.data);
    9. }

    接下来只需要对求逆函数略作更改，将参数与返回值改为结构体形式即可：

    1. Matrix Matrix_Guass_inver(Matrix src)
    2. {
    3.     // step 1
    4.     // 判断指针是否为空,判断矩阵维数
    5.     assert(src.data);
    6.     assert(src.row == src.col);
    7.     // step 2
    8.     int i, j, k, n, principal;
    9.     double Max, tmp;
    10.     n = 2 * src.row;
    11.     // res为增广矩阵，res为输出的逆矩阵
    12.     Matrix res = MakeMatrix(src.row, n);
    13.     Matrix res2 = MakeMatrix(src.row, src.col);
    14.     // step 3
    15.     // 进行数据拷贝
    16.     for (i = 0; i < src.row; i++)
    17.     {
    18.         memcpy(res.data[i], src.data[i], sizeof(res.data[0][0]) * src.col);
    19.     }
    20.     // 将增广矩阵右侧变为单位阵
    21.     for (i = 0; i < src.row; i++)
    22.     {
    23.         for (j = src.col; j < n; j++)
    24.         {
    25.             if (i == (j - src.row))
    26.                 res.data[i][j] = 1.0;
    27.         }
    28.     }
    29.     for (j = 0; j < src.col; j++)
    30.     {
    31.         // step 4
    32.         // 整理增广矩阵，选主元
    33.         principal = j;
    34.         Max = fabs(res.data[principal][j]); // 用绝对值比较
    35.         // 默认第一行的数最大
    36.         // 主元只选主对角线下方
    37.         for (i = j; i < src.row; i++)
    38.         {
    39.             if (fabs(res.data[i][j]) > Max)
    40.             {
    41.                 principal = i;
    42.                 Max = fabs(res.data[i][j]);
    43.             }
    44.         }
    45.         if (j != principal)
    46.         {
    47.             for (k = 0; k < n; k++)
    48.             {
    49.                 tmp = res.data[principal][k];
    50.                 res.data[principal][k] = res.data[j][k];
    51.                 res.data[j][k] = tmp;
    52.             }
    53.         }
    54.         // step 5
    55.         // 将每列其他元素化0
    56.         for (i = 0; i < src.row; i++)
    57.         {
    58.             if (i == j || res.data[i][j] == 0)
    59.                 continue;
    60.             double b = res.data[i][j] / res.data[j][j];
    61.             for (k = 0; k < n; k++)
    62.             {
    63.                 res.data[i][k] += b * res.data[j][k] * (-1);
    64.             }
    65.         }
    66.         // 阶梯处化成1
    67.         double a = 1.0 / res.data[j][j];
    68.         for (i = 0; i < n; i++)
    69.         {
    70.             res.data[j][i] *= a;
    71.         }
    72.     }
    73.     // step 6
    74.     // 将逆矩阵部分拷贝到res2中
    75.     for (i = 0; i < src.row; i++)
    76.     {
    77.         memcpy(res2.data[i], res.data[i] + src.row, sizeof(res.data[0][0]) * src.row);
    78.     }
    79.     // 释放增广矩阵内存
    80.     free_Matrix(res);
    81.     return res2;
    82. }

    测试 

    1. void test()
    2. {
    3.     Matrix a = MakeMatrix(3, 3);
    4.     a.data[0][0] = 1;
    5.     a.data[1][1] = 2;
    6.     a.data[0][1] = 1;
    7.     a.data[2][0] = 1;
    8.     a.data[2][2] = 2;
    9.     Matrix res = Matrix_Guass_inver(a);
    10. }

  • 相关阅读:
    小恐龙快跑，不要被逮到拉~ python制作小恐龙游戏
    2021年数维杯数学建模C题运动会优化比赛模式探索求解全过程文档及程序
    计算机网络基本知识
    HJ17 坐标移动----牛客刷题
    beanstalkd 启动跟停止【经常使用 nohup 和 & 配合来启动程序，如： nohup ./test &同时免疫SIGINT和SIGHUP信号】
    浅谈Solidity智能合约DAPP项目系统开发技术逻辑（Solidity语言框架）
    【win10和win11打印机局域网共享】
    【装包拆包----泛型】
    数据对比与处理利器——Pandas 实战
    每日一学—JavaScript数字
  • 原文地址：https://blog.csdn.net/why1472587/article/details/128121958