一、前言
讲一下高斯-约旦消元法。
它适用于处理 \(n\) 元 1 次 方程组。
误差较小并且好写。
二、步骤
主要用消元的方式求解，就是一列列处理，每一次处理消掉这一列所有其它的未知数。
处理第 \(i\) 列：
- 找到当前这一列的所有系数的绝对值的最大值，确定在第 \(x\) 行。
- 如果这一列全是 0，那么无解或者无穷解。
- 交换第 \(i\) 行和 \(x\) 行。
- 消掉这一列所有其它未知数。
那我们最后可以得到一个矩阵，只有值的那一列和一条斜对角线有系数，除一下就好了。
int main(){
n=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n+1;j++)a[i][j]=read();
for(int i=1,x=1;i<=n;i++,x=i){
for(int j=i+1;j<=n;j++)
if(fabs(a[j][i])>fabs(a[x][i]))x=j;
if(a[x][i]==0){puts("No Solution");return 0;}
for(int j=1;j<=n+1;j++)swap(a[i][j],a[x][j]);
for(int j=1;j<=n;j++)
if(j!=i){
double y=a[j][i]/a[i][i];//将第 i 行的系数乘 y 后恰好消掉 a[j][i]
for(int k=i+1;k<=n+1;k++)a[j][k]-=y*a[i][k];
}
}
for(int i=1;i<=n;i++)printf("%.2f\n",a[i][n+1]/a[i][i]);
return 0;
}
三、例题
1. 【模板】高斯消元法
模板题。代码如上。
2. [JSOI2008]球形空间产生器
推一下式子就可以了。
假设球心的坐标是 \((x_1,...,x_n)\)，那么由题目给出的公式可以知道，\(\sum\limits^n\limits_{i=1}(a_{1,i}-x_i)^2=\sum\limits^n\limits_{i=1}(a_{2,i}-x_i)^2=...=\sum\limits^n\limits_{i=1}(a_{n+1,i}-x_i)^2\)。取出前两个，化简后得到 \(\sum\limits^n\limits_{i=1}a_{1,i}^2-2\sum\limits^n\limits_{i=1}a_{1,i}·x_i=\sum\limits^n\limits_{i=1}a_{2,i}^2-2\sum\limits^n\limits_{i=1}a_{2,i}·x_i\)，即 \(\sum\limits^n\limits_{i=1}(a_{2,i}-a_{1,i})·x_i=\frac{\sum\limits^n\limits_{i=1}(a_{2,i}^2-a_{1,i}^2)}{2}\)。
其余同理。直接用高斯消元即可。
点击查看代码
int main(){
scanf("%d",&n);
for(int i=1;i<=n+1;i++)
for(int j=1;j<=n;j++)scanf("%lf",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
b[i][j]=a[i+1][j]-a[i][j];
b[i][n+1]+=(a[i+1][j]*a[i+1][j]-a[i][j]*a[i][j])/2.0;
}
for(int i=1,x=1;i<=n;i++,x=i){
for(int j=i+1;j<=n;j++)
if(fabs(b[j][i])>fabs(b[x][i]))x=j;
for(int j=1;j<=n+1;j++)swap(b[i][j],b[x][j]);
for(int j=1;j<=n;j++)
if(j!=i){
double y=b[j][i]/b[i][i];
for(int k=i+1;k<=n+1;k++)b[j][k]-=y*b[i][k];
}
}
for(int i=1;i<=n;i++)printf("%.3f ",b[i][n+1]/b[i][i]);
return 0;
}