C语言 高斯-若尔当消元法

图片 10

高斯若尔当方便解N元方程:

这段日子不搞oi了,搞点数学的东西

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

float a[3][4]={{2,1,-1,8},{-3,-1,2,-11},{-2,1,2,-3}};
int rows=3,cols=4;


void print_matrix()
{//打印矩阵
    int i,j;
    int m=rows,n=cols;
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++){
            printf("%10.3f\t",a[i][j]);
        }
        printf("\n");
    }
}
void swap_row(row1,row2)
{//交换行列
    int j=0,n=cols;
    float temp;
    for(;j<n;j++){
        temp=a[row1][j];
        a[row1][j]=a[row2][j];
        a[row2][j]=temp;
    }
}
void xiao_zhuyuan(int row,int curj,float val)
{//消主元,使之为1
    printf("行%d 除以 %f\n",row,val);
    int j=0,n=cols;
    for(;j<n;j++)
    {
        a[row][j]=a[row][j]/val;
    }
}

void gauss(){
    int i=0,j=0; //行和列
    int m=rows,n=cols;
    while(i<m&&j<n)
    {
            int k,maxi;
            float zhuyuan;
            k=i+1;

            if(fabs(a[k][j])>fabs(a[i][j]) ){

                swap_row(k,i); //按绝对值大小排序
                printf("行%d与行%d交换位置\n",k,i);
                print_matrix();
            }


            //消除非1的主元;
            zhuyuan=a[i][j];
            if(zhuyuan!=1){

               xiao_zhuyuan(i,j,zhuyuan);
                print_matrix();
            }//if



           if(a[k][j]!=0){
                int temp=0;
                int u,v;

                for(v=i;v<m-1;v++){
                float per=a[v+1][j]/a[i][j];//系数

                    printf("行%d减 (%f倍)行%d\n",v+1,per,i);
                    for(u=0;u<n;u++){
                    a[v+1][u]=a[v+1][u]-per*a[i][u];

                     }
                      print_matrix();

                }
                 j++;
            }
             i++;


    }//while
}//gauss

int main()
{
    //高斯消元法的算法复杂度是O(n3);这就是说,如果系数矩阵的是n × n,那么高斯消元法所需要的计算量大约与n3成比例

    /*  2x+y-z=8
     *  -3x-y+2z=-11
     *  -2x+y+2z=-3
     * 因此,增广举证为:
     *  2   1   -1      8
     * -3   -1  2       -11
     * -2   1   2       -3
     */

     int i,j;
     printf("原始增广矩阵\n");
     print_matrix();
     gauss();

     //printf("消元后的矩阵\n");
    // print_matrix();

}

多年来被一学奥数的同班水了一把,于是补了一下高斯消元的知识

图片 1

如下:

唯独当下只达成 矩阵梯队的花样。

 

继续。。。。。

历史

——————————————————————————————————————————————————————————————————

该方法以数学家高斯命名,但最早出现于中国古籍《九歌算术》,成书于约公元前150年。

上个例子中留存有的标题:

 例子

1.在调换行的时候,未有全行比较,只比较了附近2行。

高斯消元法可用来寻找下列方程组的解或其解的限制:

2.在显示第几行的时候,用的是数组的下标,故少了1.

图片 2

3.平素不对浮点数的展现优化,现在用的是”%.3g”,那样能压降低数部分的长度.

图片 3

4.从未有过选择 jordan的议程直接求解。

图片 4

上边是完好例子,可是亦非一级的,因为内部的变量看起来有一些乱。

以此算法的原理是:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

float a[3][4]={{2,1,-1,8},{-3,-1,2,-11},{-2,1,2,-3}};
//float a[4][5]={{2,1,-1,8,1},{-3,-1,2,-11,1},{-2,1,2,-3,1},{5,7,8,0,1}};
int rows=3,cols=4;


void print_matrix()
{//打印矩阵
    int i,j;
    int m=rows,n=cols;
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++){
            printf("%10.3g",a[i][j]);
        }
        printf("\n");
    }
     printf("\n");
}
void swap_row(row1,row2)
{//交换行列
    int j=0,n=cols;
    float temp;
    for(;j<n;j++){
        temp=a[row1][j];
        a[row1][j]=a[row2][j];
        a[row2][j]=temp;
    }
}
void xiao_zhuyuan(int row,int curj,float val)
{//消主元,使之为1
    printf("行%2d 消除 %.3g\n",row+1,val);
    int j=0,n=cols;
    for(;j<n;j++)
    {
        a[row][j]=a[row][j]/val;
    }
}

void gauss(){
    printf("\n高斯消元开始:\n");
    int i=0,j=0; //行和列
    int m=rows,n=cols;
    while(i<m&&j<n)
    {
            int k,d,maxi=i,maxval;
            float zhuyuan;
            k=i+1;
            maxval=fabs(a[i][j]);
            for(d=k;d<n;d++){
                 if(fabs(a[d][j])>maxval ){
                     maxval=fabs(a[d][j]);
                     maxi=d;
                }
            }
            if(maxi!=i){
               swap_row(maxi,i); //按绝对值大小排序
                printf("行%2d与行%2d交换位置\n",maxi+1,i+1);
                print_matrix();
            }


            //消除非1的主元;
            zhuyuan=a[i][j];
            if(zhuyuan!=1){
               xiao_zhuyuan(i,j,zhuyuan);
                print_matrix();
            }//if



           if(a[k][j]!=0){
                int temp=0;
                int u,v;

                for(v=i;v<m-1;v++){
                float per=a[v+1][j]/a[i][j];//系数

                    printf("行%2d = 行%2d 减去(%.3g )倍的行%2d\n",v+2,v+2,per,i+1);
                    //printf("Subtract (%.3f × row %d) from row %d\n",per,i+1,v+2);
                    for(u=0;u<n;u++){
                    a[v+1][u]=a[v+1][u]-per*a[i][u];
                     }
                    print_matrix();
                }//for
                 j++;
            }//if
             i++;
    }//while
}//gauss

void jordan()
{
printf("\n若尔当消元开始:\n");
 int i=0,j=0,k; //行和列
    int m=rows,n=cols;
    float xs;
    for(i=m-1;i>=0;i--){
        for(k=0;k<i;k++){
            xs=a[k][i];
            if(i!=k){
            printf("行%2d = 行%2d 减去(%.3g )倍的行%2d\n",k+1,k+1,xs,i+1);
            //printf("Subtract (%.3f × row %d) from row %d\n",xs,i+1,k+1);
              for(j=0;j<n;j++){
                a[k][j]=a[k][j]-xs*a[i][j];
                }
               print_matrix();
             }//if
       }
    }//for i

}//jordan
int main()
{

     int i,j;
     printf("原始增广矩阵\n");
     print_matrix();
     gauss(); //使用高斯消元
     jordan(); //使用若尔当消元
}

首先,要将L1
以下的等式中的x 消除,然后再将L2 以下的等式中的y
化解。那样可使整毎方程组产生一个三角形形似的格式。之后再将已搜查捕获的答案四个个地代入已被简化的等式中的未鲜明的数中,就可求出任何的答案了。

 

在刚刚的例证中,大家将图片 5
L2相加,就足以将L2 中的x 消除了。然后再将L1L3相加,就可以将L3 中的x 消除。

图片 6

我们能够那样写:

在测量试验那些顺序的时候发掘:即使是方阵话,若尔当消元后,产生类似一下的矩阵:

图片 7

1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1

图片 8

附:

结果便是:

高斯消元法百科:
高斯若尔当消元法百科:
在线高斯-若尔当消元总结(瑞典语): 

图片 9


图片 10

图片 11

现在将 − 4L2L3 相加,就可将L3 中的y 消除:

图片 12

其结果是:

图片 13

发表评论

电子邮件地址不会被公开。 必填项已用*标注