高斯消元

高斯消元用于 求解线性方程组:　通过初等行变换 把增广矩阵变为简化阶梯型矩阵的线性方程组　的求解算法

\(核心思想\) 对每个未知量 \(x_i\), 找到一个 \(x_i\) 的系数非零, 但 \(x_1\)~\(x_i-1\)? 的系数均非零的方程, (若没有, 则该元为自由元) 然后用初等行变换把其他方程的\(x_i\)的系数全部消成 0

题目

• AcWing: 球形空间产生器

代码

const long double eps=1e-8;		// 实战中 常常会使用 long double 而非 double(卡精度)

/*  交换第i行 和 第j行  */
void Swap(int i, int j){
	if(i==j) return ;
	REP(k, 1, m) swap(A[i][k], A[j][k]);
	swap(B[i], B[j]);
}

/*  用行j 消去 行i的第o个元素  */
void Eliminate(int i, int j, int o){
	long double rate=A[i][o]/A[j][o];
	REP(k, o, m) A[i][k]-=A[j][k]*rate;
    B[i]-=B[j]*rate;
}

void Gaosi_Elimination(){
	int d=0;
	REP(o, 1, m){			// 考虑 第o个元素
		int j=o, k=0;
		REP(i, d+1, n) if(fabs(A[i][j])>eps) k=i;	// 注意 这里的 i 从 d+1 开始; A[i][j]要取绝对值
		if(k==0) continue;  // Xo 是自由元

		Swap(++d, k);
		REP(i, 1, n) if(i!=d) Eliminate(i, d, o);	// i != d
	}
    REP(i, 1, d) printf("%lf ", B[i]/A[i][i]);
}