高斯消元法是线性代数中的一个算法可用来求解线性方

《高斯消元法是线性代数中的一个算法可用来求解线性方》由会员分享，可在线阅读，更多相关《高斯消元法是线性代数中的一个算法可用来求解线性方（9页珍藏版）》请在装配图网上搜索。

1、高斯消元法，是线性代数中的一个算法，可用来求解线性方程组，并可以求出矩阵的秩，以及求 出可逆方阵的逆矩阵。 高斯消元法的原理是： 若用初等行变换将增广矩阵 化为，则AX = B与CX = D是同解方程组。 所以我们可以用初等行变换把增广矩阵转换为行阶梯阵，然后回代求出方程的解。 以上是线性代数课的回顾，下面来说说高斯消元法在编程中的应用。 首先，先介绍程序中高斯消元法的步骤： （我们设方程组中方程的个数为equ，变元的个数为var，注意：一般情况下是n个方程，n个变 元，但是有些题目就故意让方程数与变元数不同） 1. 把方程组转换成增广矩阵。 2. 利用初等行变换来把增广矩阵转

2、换成行阶梯阵。 枚举k从0到equ - 1，当前处理的列为col（初始为0），每次找第k行以下（包括第k行），col列中 元素绝对值最大的列与第k行交换。如果col列中的元素全为0，那么则处理col + 1列，k不变。 3. 转换为行阶梯阵，判断解的情况。 ① 无解 当方程中出现（0, 0,…，0, a）的形式，且a != 0时，说明是无解的。 ② 唯一解 条件是k = equ，即行阶梯阵形成了严格的上三角阵。利用回代逐一求出解集。 ③ 无穷解。 条件是k < equ，即不能形成严格的上三角形，自由变元的个数即为equ - k，但有些题目要求判 断哪些变元是不缺定的。 这里单

3、独介绍下这种解法： 首先，自由变元有var - k个，即不确定的变元至少有var- k个。我们先把所有的变元视为不确 定的。在每个方程中判断不确定变元的个数，如果大于1个，则该方程无法求解。如果只有1个变 元，那么该变元即可求出，即为确定变元。 以上介绍的是求解整数线性方程组的求法，复杂度是O（n3）。浮点数线性方程组的求法类似，但 是要在判断是否为0时，加入EPS，以消除精度问题。 高斯消元法简介 在信息学竞赛中，很多问题都可以转化成线性方程组或者与之相关的问题。因此，我们需要 了解线性方程组的各种解法。在本文中，我将主要对线性方程组最常见的解法---高斯消元法 进行初步的介绍。希望

4、能借此让大家对线性方程组及其解法有进一步的了解。 高斯消元法 ^11 x1 + 々12 x2 + … + 々"xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 an1 x1 + an2 x2 + … + ann xn = bn 对于形如(1)的线性方程组，我们通常可以按照以下步骤求出解集［x1; x2,•…; xn} 1.建立增广矩阵 我们把方程组中的系数与常数直接取出，得到这样一个矩阵 a11 a12 …a1n b1 a21 a22 …a2n b2 … an1 an2 …ann bn 2. 消元 对于刚才构建的矩阵，我们反复实施初等

5、变换，即将某一行乘上一个数加到另一行上，得到 一个这样的一个三角矩阵 c11 c12 …dn d1 0 c22 …c2n d2 … 0 …0 cnn dn ，即得到了一个与原方程组同解的方程组 c11 x1 + c12 x2 + … + c1n xn = d1 c22 x2 + … + c2n xn = d2 … cnn xn = dn 3. 回代 由方程组(2)的最后一个方程，我们可以很容易得到lFn = dn/cnn，将功带入倒数第 二个方程可以得到oxn-1,#xn和欢』带入倒数第三个方程可以得到户小2,…，依次类 推，我们即可求出解集,x1, x2, …,xn}。

6、 像上面这样通过初等变换构造同解方程组来解线性方程组的方法，我们称之为高斯消元法， 一般来说，高斯消元法的时间复杂度是O（n3）o 选取主元 在消元过程进行到第k步时，即正要用第k行去消后面的行时。我们需要把第^行除以akk然 后乘上印*加到第i行上（i>k）。显然如果akk特别小的话，不仅有可能损失精度，还有可能 造成出。为了避免这种情况，我们需要选取主元： 在系数矩阵右下角选取n-k+1阶子矩阵中绝对值最大的元素a”，交换第^行与第i行，交换第 k列与殉列。注意到列的交换会使得解的顺序混乱，因此我们需要记录列的交换过程，以便 最后还原。当然由于交换后akk的绝对值是最大的，所以如果

7、akk=°我们就可以直接终止 计算了，因为这时无法找到唯一的一组解。（选取主元的过程并不影响时间复杂度，整个过 程的时间复杂度仍然是O（n3）） 高斯约当消元法 高斯约当消元法是一种不需要回代的消元法，可以算是高斯消元法的一种改进，它与高斯消 元法唯一的不同是：高斯约当消元法每次不仅要把主对角线以下的元素消为0,还要把主对角 线以上的元素消为0。自然消完后系数矩阵只有主对角线上有非0元素，所以就不需要回代了。 其他解法 除了高斯消元法与高斯约当消元法外，我们还可以使用迭代法或者共轭梯度法来解线性方程 组。 练习题 1. zoj2296 Spread Sheet 2. hdu244

8、9 Gauss Elimination 3. NOIP2004 虫食算 参考资料 [1] 徐士良数值分析与算法机械工业出版社 [2] 何江舟用高斯消元法解线性方程组 下面讲解几道OJ上的高斯消元法求解线性方程组的题目： POJ 1222 EXTENDED LIGHTS OUT POJ 1681 Painter's Problem POJ 1753 Flip Game POJ 1830开关问题 POJ 3185 The Water Bowls 开关窗户，开关灯问题，很典型的求解线性方程组的问题。方程数和变量数均为行数*列数，直 接套模板求解即可。但是，当

9、出现无穷解时，需要枚举解的情况，因为无法判断哪种解是题目要 求最优的。 POJ 2947 Widget Factory 求解同余方程组问题。与一般求解线性方程组的问题类似，只要在求解过程中加入取余即可。 注意：当方程组唯一解时，求解过程中要保证解在［3, 9］之间。 POJ 1166 The Clocks 经典的BFS问题，有各种解法，也可以用逆矩阵进行矩阵相乘。 但是这道题用高斯消元法解决好像有些问题（困扰了我N天…持续困扰中…），由于周期4不是素 数，故在求解过程中不能进行取余（因为取余可能导致解集变大），但最后求解集时，还是需要进 行取余操作，那么就不能保证最后求出的解

10、是正确的…在discuss里提问了好几天也没人回答... 希望哪位路过的大牛指点下〜〜 POJ 2065 SETI 同样是求解同余方程组问题，由于题目中的p是素数，可以直接在求解时取余，套用模板求解即 可。（虽然AC的人很少，但它还是比较水的一道题，） POJ 1487 Single-Player Games 很麻烦的一道题目…题目中的叙述貌似用到了编译原理中的词法定义（看了就给人不想做的感 觉..•） 解方程组的思想还是很好看出来了 （前提是通读题目不下5遍...），但如果把树的字符串表达式转换 成方程组是个难点，我是用栈+递归的做法分解的。首先用栈的思想求出该结点的孩子数

11、，然 后递归分别求解各个孩子。 这题解方程组也与众不同…首先是求解浮点数方程组，要注意精度问题，然后又询问不确定的变 元，按前面说的方法求解。 一顿折腾后，这题居然写了6000+B...而且冏的是巨人C++ WA，G++ AC，可能还是精度的问题 吧…看这题目，看这代码，就没有改的欲望… hdu OJ 2449 哈尔滨现场赛的一道纯高斯题，当时鹤牛敲了 1个多小时…主要就是写一个分数类，套个高精模 板（偷懒点就Java...）搞定〜〜 注意下0和负数时的输出即可。 fze OJ 1704 福大月赛的一道题目，还是经典的开关问题，但是方程数和变元数不同 (考验模板的时候到

12、 了〜〜)，最后要求增广阵的阶，要用到高精度〜〜 这里提供下自己写的还算满意的求解整数线性方程组的模板(浮点数类似，就不提供了)〜〜 /*用于求整数解得方程组.*/ #include #include #include using namespace std; const int maxn = 105; int equ, var; //有equ个方程，var个变元。增广阵行数为equ,分别为0到equ - 1，列数为var + 1， 分别为0到var. int a[maxn][maxn]; int x[maxn]; /

13、/ 解集. bool free_x[maxn]; //判断是否是不确定的变元. int free_num; void Debug(void) ( int i, j; for (i = 0; i < equ; i++) ( for (j = 0; j < var + 1; j++) ( cout << a[i][j] << ""; } cout << endl; } cout << endl; } inline int gcd(int a, int b) ( int t; while (b != 0) ( t = b; b = a % b; a =

14、t; } return a; } inline int lcm(int a, int b) ( return a * b / gcd(a, b); } //高斯消元法解方程组(Gauss-Jordan elimination).(-2表示有浮点数解，但无整数解，-1表示无解， 0表示唯一解，大于0表示无穷解，并返回自由变元的个数) int Gauss(void) ( int i, j, k; int max_r; //当前这列绝对值最大的行. int col; //当前处理的列. int ta, tb; int LCM; int temp; int free

15、_x_num; int free_index; //转换为阶梯阵. col = 0; //当前处理的列. for (k = 0; k < equ && col < var; k++, col++) ( //枚举当前处理的行. //找到该col列元素绝对值最大的那行与第k行交换.(为了在除法时减小误差) max_r = k; for (i = k + 1; i < equ; i++) ( if (abs(a[i][col]) > abs(a[max_r][col])) max_r = i; } if (max_r != k) ( //与第k行交换. for (j = k

16、; j < var + 1; j++) swap(a[k][j], a[max_r][j]); } if (a[k][col] == 0) ( //说明该col列第k行以下全是0了，则处理当前行的下一列. k--; continue; } for (i = k + 1; i < equ; i++) ( //枚举要删去的行. if (a[i][col] != 0) LCM = lcm(abs(a[i][col]), abs(a[k][col])); ta = LCM / abs(a[i][col]), tb = LCM / abs(a[k][col]); if (a[i][

17、col] * a[k][col] < 0) tb = -tb; // 异号的情况是两个数相加. for (j = col; j < var + 1; j++) ( a[i][j] = a[i][j] * ta - a[k][j] * tb; } } } } Debug(); // 1.无解的情况：化简的增广阵中存在(0,0, ..., a)这样的行(a != 0). for (i = k; i < equ; i++) ( //对于无穷解来说，如果要判断哪些是自由变元，那么初等行变换中的交换就会影响，则 要记录交换. if (a[i][col] != 0) return

18、-1; } // 2.无穷解的情况：在var * (var + 1)的增广阵中出现(0,0, ..., 0)这样的行，即说明没有形成 严格的上三角阵. //且出现的行数即为自由变元的个数. if (k < var) ( //首先，自由变元有var - k个，即不确定的变元至少有var- k个. for (i = k - 1; i >= 0; i--) ( //第i行一定不会是(0, 0, ..., 0)的情况，因为这样的行是在第k行到第equ行. //同样，第i行一定不会是(0, 0, ..., a), a != 0的情况，这样的无解的. free_x_num = 0;

19、//用于判断该行中的不确定的变元的个数，如果超过1个，则无法 求解，它们仍然为不确定的变元. for (j = 0; j < var; j++) ( if (a[i][j] != 0 && free_x[j]) free_x_num++, free_index = j; } if (free_x_num > 1) continue; //无法求解出确定的变元. //说明就只有一个不确定的变元free_index，那么可以求解出该变元，且该变元是 确定的. temp = a[i][var]; for (j = 0; j < var; j++) ( if (a[i][j] !=

20、 0 && j != free_index) temp -= a[i][j] * x[j]; } x[free_index] = temp / a[i][free_index]; // 求出该变元. free_x[free_index] = 0; // 该变元是确定的. } return var - k; // 自由变元有 var - k 个. } // 3.唯一解的情况：在var * (var + 1)的增广阵中形成严格的上三角阵. // 计算出 Xn-1, Xn-2 ... X0. for (i = var - 1; i >= 0; i--) ( temp = a[i

21、][var]; for (j = i + 1; j < var; j++) ( if (a[i][j] != 0) temp -= a[i][j] * x[j]; } if (temp % a[i][i] != 0) return -2; //说明有浮点数解，但无整数解. x[i] = temp / a[i][i]; } return 0; } int main(void) ( freopen("Input.txt”, "r", stdin); int i, j; while (scanf("%d %d", &equ, &var) != EOF) ( memset

22、(a, 0, sizeof(a)); memset(x, 0, sizeof(x)); memset(free_x, 1, sizeof(free_x)); // 一开始全是不确定的变元. for (i = 0; i < equ; i++) ( for (j = 0; j < var + 1; j++) ( scanf("%d", &a[i][j]); } } // Debug(); free_num = Gauss(); if (free_num == -1) printf("无解!\n"); else if (free_num == -2) printf(“有浮点

23、数解，无整数解!\n"); else if (free_num > 0) ( printf("无穷多解！自由变元个数为%d\n", free_num); for (i = 0; i < var; i++) ( if (free_x[i]) printf("x%d 是不确定的\n", i + 1); else printf("x%d: %d\n", i + 1, x[i]); } else ( for (i = 0; i < var; i++) ( printf("x%d: %d\n", i + 1, x[i]); } } printf("\n"); } return 0; }