高斯消去法

高斯消去法解方程组

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含 n+1n+1 个实数，表示一个方程的 nn 个系数以及等号右侧的常数。

输出格式

如果给定线性方程组存在唯一解，则输出共 nn 行，其中第 ii 行输出第 ii 个未知数的解，结果保留两位小数。

如果给定线性方程组存在无数解，则输出 Infinite group solutions。

如果给定线性方程组无解，则输出 No solution。

高斯消去法的步骤：

• 找到当前列绝对值最大的一行
• 把它换到最上面一行
• 将该行的第一个数变为1
• 把下面所有行的该列消为0

解的形式：

• 完美阶梯型：唯一解
• 零=非零：无解
• 零=零：无穷解

代码为：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        double arr[][] = new double[n][n+1];
        for (int i = 0;i<n;i++){
            for (int j = 0;j<=n;j++){
                arr[i][j] = scanner.nextDouble();
            }
        }
        int index = guass(arr);
        if (index==0){
            for (int i = 0;i<n;i++){
                if(arr[i][n]==-0.0) arr[i][n]=0.0;
                System.out.println(String.format("%.2f",arr[i][n]));
            }
        }else if (index==1){
            System.out.println("Infinite group solutions");  //无穷多个解
        }else {
            System.out.println("No solution");//无解
        }

    }
    public static int guass(double arr[][]){

        int n = arr.length;
        int r = 0,c = 0;
        for (r = 0,c = 0;c<n;c++){
            //第一步，找到该列的最大值
            int t = r;
            for (int i = r;i<n;i++){
                if (Math.abs(arr[t][c])<Math.abs(arr[i][c])){
                    t = i;
                }
            }
            if(Math.abs(arr[t][c])<0.000001) continue;
            //最大值的行数为t，与当前行交换
            for (int i = c;i<=n;i++){
                double temp = arr[t][i];
                arr[t][i] = arr[r][i];
                arr[r][i] = temp;
            }
            //将当前行的第一个数设为1
            for (int i = n;i>=c;i--){
                arr[r][i]/= arr[r][c];
            }
            //将下面所有行的该列消为0
            for (int i = r+1;i<n;i++){
                if(Math.abs(arr[i][c])>0.000001) {
                    for (int j = n; j >= c; j--) {
                        arr[i][j]-= arr[r][j] * arr[i][c];
                    }
                }
            }
            //进行下一行处理
            r++;
        }
        //0解或者无穷解
        if (r<n){
            for (int i = r;i<n;i++){
                if (Math.abs(arr[i][n])>0.000001) return 2;//0解
            }
            return 1;//无穷解
        }
        //唯一解
        /*此时这里得到的矩阵是
          1.0 0.5 -1.5 -4.5
          0.0 1.0 0.33  -1.0
          0.0 0.0 1.0  3.0
        */
        for (int i = n-1;i>=0;i--){
            for (int j = i+1;j<n;j++){
                // 其中a[i][j]是主元的位置
                //行从后面向前面消除主元后面的元素
                //例如倒数第二行的[0.0 1.0 0.3  -1.0]
                //[0.0 1.0 0 -2.0] -1.0-0.33*3=-2.0
                arr[i][n]-=arr[i][j]*arr[j][n];
            }
        }
        return 0;
    }
}

高斯消元代码中最难理解的就是往回推的最后一步

for (int i = n - 1; i >= 0; i -- )
       for (int j = i + 1; j < n; j ++ )
           a[i][n] -= a[j][n] * a[i][j];

这里的 i，j 其实代表的是 xi和xj ，对于 i 行中的 xj 对应的系数是 a[i][j],而a[i][j]则代表了此时 i 行的多项式的结果，为了得到xi的解（xi的系数是1）就需要此时的结果减去后面的多项式的和即

for(int j = i + 1; j < n; j ++ )
    a[i][n] -= a[j][n] * a[i][j];//x_j * x_j的系数