written on 2022-08-13
高斯消元主要用于解决 \(n\) 元一次方程组相关的问题。一般时间复杂度 \(O(n^3)\)，此过程需要用到矩阵的初等行变换。
接下来我们来看一下高斯消元的过程。
\[\begin{cases} k_{1,1}x_1+k_{1,2}x_2+\cdots+k_{1,n}x_n=p_1\\k_{2,1}x_1+k_{2,2}x_2+\cdots+k_{2,n}x_n=p_2\\\cdots\\k_{n,1}x_1+k_{n,2}x_2+\cdots+k_{n,n}x_n=p_n\end{cases} \]这是一个 \(n\) 元一次方程组，如果直接用代码来实现这个解方程的模拟过程是很繁琐的。高斯消元，实质上就是用加减消元（高斯消元的通俗别名）来将解方程的过程程式化。
执行高斯消元，为了简便操作，我们将其原方程组转化为矩阵的形式。
\[\left[ \begin{array} {lcrr|r} k_{1,1} & k_{1,2} & \cdots & k_{1,n} & p_1 \\ k_{2,1} & k_{2,2} & \cdots & k_{2,n} & p_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ k_{n,1} & k_{n,2} & \cdots & k_{n,n} & p_n \end{array} \right]\]这里我们将原方程组的系数 \(k\) 写成一个系数矩阵，加上原等式右侧的常数，构成一个增广矩阵。
对于这样一个增广矩阵，考虑一下，为了达到消元获解的目标，显然我们应该达到的目的是：
\[k_{i,i}=1,k_{i,j}=0(i\neq j) \]为了达成这个目标，我们考虑矩阵的初等行变换，其包含三种操作：
-
交换矩阵中某两行的位置。
-
把矩阵的某一行的 \(x\) 倍加到另一行。
-
将某一行内的所有数乘以 \(x\)。
初等行变换好像是代数中的初等变换的一个分支，详见百度百科吧
下面给出程式化的代码：
for(int i=1;i<=n;i++)
{
bool flag=0;
for(int j=i;j<=n;j++) if(Mat[j][i]!=0){swap(Mat[i],Mat[j]),flag=1;break;}//找出不为0的行交换
if(!flag) puts("No Solution"),exit(0);//特判无解
for(int j=i+1;j<=n+1;j++) Mat[i][j]/=Mat[i][i];
Mat[i][i]=1;//操作3
for(int j=1;j<=n;j++)
{
if(j==i) continue;
for(int k=i+1;k<=n+1;k++) Mat[j][k]-=Mat[j][i]*Mat[i][k];
Mat[j][i]=0;
}//操作2
}
那么最后的答案就是 \(Mat_{i,n+1}\)
高斯消元这个算法相对来说难度不是很大，关键在于找出题目中没有直接给出的方程。
标签：方程组,矩阵,cdots,初等,高斯消,vdots From： https://www.cnblogs.com/Freshair-qprt/p/16585615.html