高斯消元

理论

求解线性方程组，例如

\[\begin{cases} a_{1,1}x_1+a_{1,2}x_2+a_{1,3}x_3=b_1\\ a_{2,1}x_1+a_{2,2}x_2+a_{2,3}x_3=b_2\\ a_{3,1}x_1+a_{3,2}x_2+a_{3,3}x_3=b_3 \end{cases} \]

将它转化为矩阵乘法

\[\left[ \begin{matrix} a_{1,1}&a_{1,2}&a_{1,3}\\ a_{1,1}&a_{1,2}&a_{1,3}\\ a_{1,1}&a_{1,2}&a_{1,3} \end{matrix} \right] \times \left[ \begin{matrix} x_1\\ x_2\\ x_3 \end{matrix} \right] = \left[ \begin{matrix} b_1\\ b_2\\ b_3 \end{matrix} \right] \]

上面的三个矩阵还是太麻烦了，我们将他变为增广矩阵

\[\left[ \begin{matrix} a_{1,1}&a_{1,2}&a_{1,3}&b_1\\ a_{1,1}&a_{1,2}&a_{1,3}&b_2\\ a_{1,1}&a_{1,2}&a_{1,3}&b_3 \end{matrix} \right] \]

然后我们定义初等行变换
1.交换两行
2.将同一行的元素同时乘 \(val\)
3.将第 \(i\) 行的元素加到第 \(j\) 行上面
不难发现初等行变换不会改变方程的解。然后就像我们常规解方程一样进行消元就可以了。

具体操作为，对于每一个未知数，我们取一个最大的 \(a\) ，然后用初等行变换将其他行对应的地方变成 \(0\) ，最后我们可以得到一个这样的矩阵

\[\left[ \begin{matrix} a'_1&0&0&b'_1\\ 0&a'_2&0&b'_2\\ 0&0&a'_3&b'_3 \end{matrix} \right] \]

我们就可以很方便的进行求解了。

例题:洛谷P3389

#include 
#define db double
using namespace std;
db a[105][105];
int n;
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n+1;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++){
		int maxhang=i;
		for(int j=i+1;j<=n;j++)
			if(abs(a[j][i])>=abs(a[maxhang][i]))
				maxhang=j;
		for(int j=1;j<=n+1;j++)
			swap(a[maxhang][j],a[i][j]);
		if(a[i][i]==0) {
			cout<<"No Solution\n";
			return 0;
		}
		for(int j=1;j<=n;j++){
			if(j==i) continue;
			db sb=a[j][i]*1.0/a[i][i];
			for(int k=i;k<=n+1;k++)
				a[j][k]-=a[i][k]*sb;
		}
	}
	for(int i=1;i<=n;i++) {
		cout<