【模板】高斯消元法

题目

洛谷P3389高斯消元法

题解

通过初等行变换把增广矩阵变为简化阶梯形矩阵的线性方程组求解算法就是高斯消元算法。

算法流程:先将方程组写成一个增广矩阵。

然后是加减消元操作,一共进行n次。在第i次操作中,要将第i+1~n行的方程的xi的系数消为0。具体消系数的方法:假设第i行为a*x+c*y=e,要消的某一行为b*x+d*y=f,则b-=(b/a)*a,d-=(b/a)*c,f-=(b/a)*e。在第i次操作进行前,先要将i+1~n行中系数绝对值最大的方程与第i个方程交换位置,这样可以减小误差(原因玄学)而且可以避免当前行的xi系数为0。如果此时第i~n行的式子中xi系数全为0,那么方程组就有无穷多组解。

加减消元操作结束后,会得到一个上三角阶梯型矩阵。

接着是代入消元,可以发现,下面的方程比上面的方程更容易解,于是从n~1依次解元,并利用下面方程已经解得的值,消去当前方程中一些元的系数。

代码

Subscribe
提醒
guest
4 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月26日 下午3:48

【小白解析】
此题思路依旧简单粗暴,为基本的解线性方程组思路。具体体现为:若要解n元一次方程组(x1,x2,…xn),可以保留第一个方程,用其消去其他n-1个方程的x1,生成n-1元一次方程组;在用第二个方程消去n-2个方程的x2…以此类推。求得最后一个一元一次方程组答案后,即可依次回代。
在此重点解释几个消元/回代的语句:
第17行:

a[j][k]-=a[j][i]/a[i][i]*a[i][k];

即保持矩阵第i行不变,要消去第j行的第一个非0系数a[j][i],可以将第i行每个系数乘a[j][i]/a[i][i],再让j行减去i行,j行的首非0系数即被消除。
第21行:

a[i][n+1]-=a[i][j]*a[j][n+1];

代表回代。进行该操作时,任何第j行已化为:
0 0…(j-1个0) 1 0 0…(n-j个0) a[j][n+1],
其中1的列坐标为j;因而a[i][n+1]-a[i][j]*a[j][n+1]的操作即表示将i行j列的系数化为0。
第22行:

a[i][n+1]/=a[i][i];

即将第i行首个(也是除n+1列外的唯一一个)非0系数化为1,代表xi==a[i][n+1]。

*

如果此时第i~n行的式子中xi系数全为0,那么方程组就有无穷多组解。

其实这个判断在12行中,顺便排除了除最后一列系数外都为0的无解情况。矩阵的秩,你好强大!

cyx
cyx
Reply to  cyx
2020年8月26日 下午3:50

好吧,似乎没排除,看错每行列数了。

cyx
cyx
Reply to  cyx
2020年8月26日 下午3:52

不对,到底有没有排除依旧存疑

cyx
cyx
Reply to  cyx
2020年8月26日 下午8:53

破案了,排除了——但无法分辨是无限解还是无解