线性方程组Ax=b求解

线性方程组

有多个未知数，并且每个未知数的次数均为一次，这样多个未知数组成的方程组为线性方程组。

高斯消元法

高斯消元主要用来求解线性方程组，也可以求解矩阵的秩，矩阵的逆。在ACM中是一个有力的数学武器。时间复杂度是n^3，主要与方程组的个数，未知数的个数有关。高斯消元的过程就是手算解方程组的过程。加减消元，消去未知数，如果有多个未知数，就一直消去，直到得到类似kx=b（k和b为常数，x为未知数）的式子，就可以求解出未知数x，然后我们回代，依次求解出各个未知数的值，就解完了方程组。

总共分两步：

1. 加减消元
2. 回代求未知数值

C++实现1

首先，我们对于每一行找到第一个不为零的元素，并且将这一行置为1 的形式，用这一行乘上倍数加到之后的每一行。

然后，我们从最后一行开始，选择主元，加到之前的每一行上，使得该列的元素都为零。

#include<iostream>
#include<cstdio>
#include<iomanip>
using namespace std;
#define e     0.00000001
#define maxn 50

int    n;//规模nXn
double a[maxn][maxn];//系数矩阵
double b[maxn];//b矩阵
double m[maxn][maxn];//中间变量矩阵
double x[maxn];//最终解
int    H=1;//扩大H被结算（优化）
/*
读取数据
*/
void read(){
    cout<<"请输入系数矩阵规模n:= ";
    cin>>n;
    cout<<"|-----------------------------\n";
    cout<<"|请输入系数矩阵,如：\n";
    cout<<"|1.1348 3.8326 1.1651 3.4017\n"; 
    cout<<"|0.5301 1.7875 2.5330 1.5435\n";
    cout<<"|3.4129 4.9317 8.7643 1.3142\n";
    cout<<"|1.2371 4.9998 10.6721 0.0147\n";
    cout<<"|-----------------------------\n";
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            a[i][j]*=H;
        }
    cout<<"|-----------------------------\n";
    cout<<"|请输入b矩阵，如：\n";
    cout<<"|9.5342 6.3941 18.4231 16.9237\n";
    cout<<"|-----------------------------\n";
    for(int i=1;i<=n;i++){
        cin>>b[i];
        b[i]*=H;
    }
}

/*
中间矩阵输出
参数：消元次数
*/
void PrintProc(int cases){
    printf("--------第%d次消元结果如下：\n",cases);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<setw(10)<<a[i][j]<<' ';
        }
        cout<<setw(10)<<b[i]<<'\n';
    }
    cout<<"END THIS SHOW-------------\n";
}

/*
显示结果
*/
void Print(){
    cout<<"|-----------------------------\n";
    cout<<"|结果为：\n";
    for(int i=1;i<=n;i++){
        printf("x[%d]=  %lf\n",i,x[i]);
    }
    cout<<"|-----------------------------\n\n";
}

/*
顺序消元法
*/
void ShunXuXiaoYuan(){
    //消元计算
    for(int k=1;k<n;k++){
        for(int i=k+1;i<=n;i++){
            m[i][k]=a[i][k]/a[k][k];
            for(int j=k+1;j<=n;j++){
                a[i][j]-=m[i][k]*a[k][j];
            }
        }
        for(int i=k+1;i<=n;i++){
            b[i]-=m[i][k]*b[k];
        }
        PrintProc(k);//输出中间计算过程
    }
    //回代求解
    x[n]=b[n]/a[n][n];
    for(int i=n-1;i>0;i--){
        x[i]=b[i];
        for(int j=i+1;j<=n;j++)
            x[i]-=a[i][j]*x[j];
        x[i]/=a[i][i];
    }
    //输出结果
    Print();
}

/*
列主消元
*/
void LieZhuXiaoYuan(){
    for(int k=1;k<n;k++){
        //选主元[这一列的绝对值最大值]
        double ab_max=-1;
        int       max_ik;
        for(int i=k;i<=n;i++){
            if(abs(a[i][k])>ab_max){
                ab_max=abs(a[i][k]);
                max_ik=i;
            }
        }
        //交换行处理[先判断是否为0矩阵]
        if(ab_max<e){//0矩阵情况
            cout<<"det A=0\n";
            break;
        }else if(max_ik!=k){//是否是当前行，不是交换
            double temp;
            for(int j=1;j<=n;j++){
                temp=a[max_ik][j];
                a[max_ik][j]=a[k][j];
                a[k][j]=temp;
            }
            temp=b[max_ik];
            b[max_ik]=b[k];
            b[k]=temp;
        }
        //消元计算
        for(int i=k+1;i<=n;i++){
            a[i][k]/=a[k][k];
            for(int j=k+1;j<=n;j++){
                a[i][j]-=a[i][k]*a[k][j];
            }
            b[i]-=a[i][k]*b[k];
        }
        PrintProc(k);//输出中间计算过程
        if(k<n-1)continue;
        else{
            if(abs(a[n][n])<e){
                cout<<"det A=0\n";
                break;
            }else{//回代求解
                x[n]=b[n]/a[n][n];
                for(int i=n-1;i>0;i--){
                    x[i]=b[i];
                    for(int j=i+1;j<=n;j++)
                        x[i]-=a[i][j]*x[j];
                    x[i]/=a[i][i];
                }
                //输出结果
                Print();
            }
        }
    }
}

/*
主函数
*/
int main(){
    while(1){
        read();
        LieZhuXiaoYuan();
        //ShunXuXiaoYuan();
    }return 0;
}
/*
书上高斯消元的例子：
1 1 1 
1 3 -2
2 -2 1

6 1 1
*/
/*
书上列主消元的例子：
-0.002 2 2
1 0.78125 0
3.996 5.5625 4

0.4 1.3816 7.4178
*/

C++实现2

#include<stdio.h>
    #include<algorithm>
    #include<iostream>
    #include<string.h>
    #include<math.h>
    using namespace std;
    const int MAXN=50;
    int a[MAXN][MAXN];//增广矩阵
    int x[MAXN];//解集
    bool free_x[MAXN];//标记是否是不确定的变元
    int gcd(int a,int b){
        if(b == 0) return a; else return gcd(b,a%b);
    }
    inline int lcm(int a,int b){
        return a/gcd(a,b)*b;//先除后乘防溢出
    }
    // 高斯消元法解方程组(Gauss-Jordan elimination).(-2表示有浮点数解，但无整数解，
    //-1表示无解，0表示唯一解，大于0表示无穷解，并返回自由变元的个数)
    //有equ个方程，var个变元。增广矩阵行数为equ,分别为0到equ-1,列数为var+1,分别为0到var.
    int Gauss(int equ,int var){
        int i,j,k;
        int max_r;// 当前这列绝对值最大的行.
        int col;//当前处理的列
        int ta,tb;
        int LCM;
        int temp;
        int free_x_num;
        int free_index;

        for(int i=0;i<=var;i++){
            x[i]=0;
            free_x[i]=true;
        }

        //转换为阶梯阵.
        col=0; // 当前处理的列
        for(k = 0;k < equ && col < var;k++,col++){// 枚举当前处理的行.
        // 找到该col列元素绝对值最大的那行与第k行交换.(为了在除法时减小误差)
            max_r=k;
            for(i=k+1;i<equ;i++){
                if(abs(a[i][col])>abs(a[max_r][col])) max_r=i;
            }
            if(max_r!=k){// 与第k行交换.
                for(j=k;j<var+1;j++) swap(a[k][j],a[max_r][j]);
            }
            if(a[k][col]==0){// 说明该col列第k行以下全是0了，则处理当前行的下一列.
                k--;
                continue;
            }
            for(i=k+1;i<equ;i++){// 枚举要删去的行.
                if(a[i][col]!=0){
                    LCM = lcm(abs(a[i][col]),abs(a[k][col]));
                    ta = LCM/abs(a[i][col]);
                    tb = LCM/abs(a[k][col]);
                    if(a[i][col]*a[k][col]<0)tb=-tb;//异号的情况是相加
                    for(j=col;j<var+1;j++){
                        a[i][j] = a[i][j]*ta-a[k][j]*tb;
                    }
                }
            }
        }
        // 1. 无解的情况: 化简的增广阵中存在(0, 0, ..., a)这样的行(a != 0).
        for (i = k; i < equ; i++){ // 对于无穷解来说，如果要判断哪些是自由变元，那么初等行变换中的交换就会影响，则要记录交换.
            if (a[i][col] != 0) return -1;
        }
        // 2. 无穷解的情况: 在var * (var + 1)的增广阵中出现(0, 0, ..., 0)这样的行，即说明没有形成严格的上三角阵.
        // 且出现的行数即为自由变元的个数.
        if (k < var){
            return var - k; // 自由变元有var - k个.
        }
        // 3. 唯一解的情况: 在var * (var + 1)的增广阵中形成严格的上三角阵.
        // 计算出Xn-1, Xn-2 ... X0.
        for (i = var - 1; i >= 0; i--){
            temp = a[i][var];
            for (j = i + 1; j < var; j++){
                if (a[i][j] != 0) temp -= a[i][j] * x[j];
            }
            if (temp % a[i][i] != 0) return -2; // 说明有浮点数解，但无整数解.
            x[i] = temp / a[i][i];
        }
        return 0;
    }
    int main(void){
    //    freopen("in.txt", "r", stdin);
    //    freopen("out.txt","w",stdout);
        int i, j;
        int equ,var;
        while (scanf("%d %d", &equ, &var) != EOF){
            memset(a, 0, sizeof(a));
            for (i = 0; i < equ; i++){
                for (j = 0; j < var + 1; j++){
                    scanf("%d", &a[i][j]);
                }
            }
            int free_num = Gauss(equ,var);
            if (free_num == -1) printf("无解!\n");
            else if (free_num == -2) printf("有浮点数解，无整数解!\n");
            else if (free_num > 0){
                printf("无穷多解! 自由变元个数为%d\n", free_num);
                for (i = 0; i < var; i++){
                    if (free_x[i]) printf("x%d 是不确定的\n", i + 1);
                    else printf("x%d: %d\n", i + 1, x[i]);
                }
            }else{
                for (i = 0; i < var; i++){
                    printf("x%d: %d\n", i + 1, x[i]);
                }
            }
            printf("\n");
        }
        return 0;
    }

QR 分解

QR 分解的形式

QR 分解是把矩阵分解成一个正交矩阵与一个上三角矩阵的积。QR 分解经常用来解线性最小二乘法问题。QR 分解也是特定特征值算法即QR算法的基础。

QR 分解的求解

QR 分解的实际计算有很多方法，例如 Givens 旋转、Householder 变换，以及 Gram-Schmidt 正交化等等。每一种方法都有其优点和不足

参考

• 高斯消元快速入门