线性方程组 解的判别 与 解的结构

Github地址
https://github.com/tianzhenyun/formula

一.线性方程组求解定理

1.线性方程组有解判别定理 线性方程组

a11 x1 + a12 x2 + … + a1n x n = b1 ,

a21 x1 + a22 x2 + … + a2n x n = b2 ,

......................................................

as1 x1 + as2 x2 + … + asn x n = bs

有解的充分必要条件是 : 它的系数矩阵与增广矩阵有相同的秩.

2.齐次线性方程组
a11 x1 + a12 x2 + … + a1n x n = 0 ,

a21 x1 + a22 x2 + … + a2n x n = 0 ,

......................................................

as1 x1 + as2 x2 + … + asn x n = 0

有非零解的充分必要条件是: 它的系数矩阵的秩 r 小于未知量个数 n.

齐次线性方程组求解一般步骤：

• 把系数矩阵通过初等变换，变换成阶梯形矩阵.
• 判断阶梯形矩阵中非零行的个数秩(r)，以及计算自由元个数m=n-r.
• 确定自由元位置，然后以次为它们赋值1,0...
• 求解出方程组的基础解系.
• 用基础解系表示出方程全解.

非齐次线性方程组求解，与齐次线性方程组求解过程基本一致，只需要再求出一个特解。

二.如何用C语言计算线性方程组的解

那么如何用算法求出线性方程组的解呢？

就是根据上面方程组求解一般步骤来的:

• 矩阵的初等变换(在上次行列式计算的基础上，这个很好实现)
• 求出矩阵的秩/自由元个数，然后确定自由元的位置(我认为这是一个难点)
• 初始化自由元(1,0,..)，计算变量，最终求出基础解系
• 非齐次线性方程
  • 先求出齐次线性方程组的基础解系
  • 再利用上面步骤求一个特解即可

1.矩阵的初等变换

//初等行变换
void primaryRowChange(int s, int n, double **array)
{
    int i,j,k,ii,kk,flag;
    double temp;
    for(i=0,j=0;i<s-1;i++,j++)//s行，最外围只需要变换s-1
    {

        ii=i;
        //如果行的首元为0，向下查找一个不为0的，然后换行
        if(*(*(array+i)+j) == 0)
        {
            flag=0;
            for(k=i+1;k<s;k++)
            {
                if(*(*(array+k)+j)!=0)//第k行与第i行交换
                {
                    for(kk=j;kk<n;kk++)
                    {    
                        temp=*(*(array+k)+kk);
                        *(*(array+k)+kk) = *(*(array+i)+kk);
                        *(*(array+i)+kk) = temp;
                    }            
                    flag =1;
                    break;
                }
            }        
            //判断是交换成功，如果没有成功，则i--
            if(!flag)
            {                
                i--;
                continue;
            }
            i--;
            j--;
            continue;
        }
        for(;ii<s-1;ii++)
        {
            if(*(*(array+ii+1)+j)==0)
                continue;
            temp =-*(*(array+ii+1)+j) / *(*(array+i)+j);
            for(k=j;k<n;k++)
                *(*(array+ii+1)+k) += *(*(array+i)+k) * temp;

        }
    }
}

2.计算矩阵的秩

//计算矩阵的秩
int getRank(int s, int n, double **array)
{
    int flag;
    int i,j,r=s;
    //判断非零行个数
    for(i=0;i<s;i++)
    {
        flag=0;
        for(j=0;j<n;j++)
        {
            if(*(*(array+i)+j)!=0 && (*(*(array+i)+j)>0.01 || *(*(array+i)+j) <-0.01))//排除很小数，
            {
                flag=1;
                break;        
            }
        }
        if(!flag)//当前行全为零,则r为i;
        {
            r=i;
            break;
        }
    }
    return r;
}

3.确定自由元位置

自由元确定需要考虑两种情况：

• 系数梯形矩阵最后一行只有一个非零元素.
• 系数梯形矩阵中某行的个数等于自由元的个数.

//获取自由元信息
int* getFreeElement(int r, int n, double **array, int **matrixPrimary, double **matrixCalc)
{
    int i,j,k,o,p,q;
    int m=n-1-r;//n-1:
    int *freeElement =(int*)malloc(m*sizeof(int));
    j=-1;//判断是否有为0的变量
    q=0;//如果当前行非零个数与自由元个数相等，则标记为1,自由元选择起始位置左移一位
    for(i=r-1;i>=0;i--)//查找自由元，及位置为0的
    {
        if(*(*(matrixPrimary+i)+1)==1)//说明第i行只有一个变量，如果是齐次方程它的解一定为0
        {
            j=*(*(matrixPrimary+i)+0);
            for(k=0;k<r;k++)
                *(*(matrixCalc+k)+j)=*(*(array+k)+n-1) / *(*(array+k)+j);
        }
        else if(n-1-matrixPrimary[i][0]==m)
        {
            q=1;
        }
        else if(n-1-matrixPrimary[i][0]>m)
        {
            o=matrixPrimary[i][0];//当前行的首元位置
            p=0;//次数
            for(k=n-2-q;k>=o;k--)//从后向前查找自由元位置 
            {
                if(k==j)
                    continue;
                freeElement[p++]=k;
                if(p==m)//说明已经找到 m个自由元
                    return freeElement;
            }
        }
    }
    return freeElement;
}

求解示例图:

1> p148-例4

2> 2.7(1)-1

3> 2.7(2)-1.1

4> 2.7(2)-1.2

5> 2.7(2)-1.3

6> 2.7(3)-1.1

7> 2.7(3)-1.2

8> 2.7(3)-1.3

9> 2.7(3)-1.4

10> p155-例6

评论

Reply