Loading...

高斯消元&矩阵树定理 学习笔记

check评论:0 条 remove_red_eye浏览量:59 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-11-17

没啥前言可说,为了学矩阵树定理学的

我们将一个方程组的系数看成一个矩阵,若$\left\{ \begin{matrix} a_{11}x_1+a_{12}x_2+a_{13}x_3 =A_1\\a_{21}x_1+a_{22}x_2+a_{23}x_3 =A_2\\a_{31}x_1+a_{32}x_2+a_{33}x_3 =A_3\end{matrix}\right .$,就可以写作$\left[ \begin{matrix}a_{11} \ a_{12} \ a_{13} \ A_1\\ a_{21} \ a_{22} \ a_{23} \ A_2\\a_{31} \ a_{32} \ a_{33} \ A_3 \end{matrix} \right]​$

如果我们能将这个矩阵化作$\left[ \begin{matrix}1\ 0\ 0 \ A_1'\\0\ 1\ 0\ A_2'\\0\ 0\ 1\ A_3'\end{matrix}\right]$,那么显然,$\left\{ \begin{matrix}x_1=A_1'\\x_2=A_2'\\x_3=A_3'\end{matrix}\right.$

然后要求值的话,我们的思路就是,依次消去第$i$个数,使得对于$\forall i,i\in[1,n]$,$x_i$所在列只有一项为$1$,如果有一行为全$0$,那显然是无解,否则,我们先将该行所有数字除以$a_{ki}$,将其交换至第$i$行后,依次与其他行相减即可,最后就是答案,为了减少精度误差,我们每次找到最大的$a_{ki}$来消去,时间复杂度$O(n^3)$

关于矩阵求逆之类的,回头补锅==

贴个代码

/*  Never Island  */
/*deco loves Chino*/
/* Summer Pockets */
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-8;
int n;
double a[120][120];
int gauss()
{
    for(int i=1;i<=n;i++)
    {
        int mx=i;
        for(int j=i+1;j<=n;j++)
        {
            if(fabs(a[j][i])>fabs(a[mx][i]))
            {
                mx=j;
            }    
        } 
        if(fabs(a[mx][i])<eps)
        {
            return 0;
        }
        if(i!=mx)
        {
            swap(a[i],a[mx]);
        }
        for(int j=i+1;j<=n+1;j++)
        {
            a[i][j]/=a[i][i];
        }
        for(int j=1;j<=n;j++)
        {
            if(i==j)
            {
                continue;
            }
            for(int k=i+1;k<=n+1;k++)
            {
                a[j][k]-=a[j][i]*a[i][k];
            }
        }
    }
    return 1;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n+1;j++)
        {
            scanf("%lf",&a[i][j]);
        }
    }
    int qwq=gauss();
    if(!qwq)
    {
        cout<<"No Solution";
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        printf("%.2lf\n",a[i][n+1]);
    }
}

关于行列式求法,根据定义

$det(A)=\sum\limits_{\sigma\in S_n}sgn(\sigma)\prod\limits_{i=1}^n a_{i,\sigma(i)}$

其中$\sigma$代表$1-n$的某种排列,$S_n$就是全排列的集合,当$\sigma$的逆序对数为偶数时,$sgn(\sigma)=1$,否则为$0$,这个玩意直接求值是$O(n!)$的

然后行列式满足一些性质

一.行列式与其转置行列式相等

若$b_{ji}=a_{ij}$,则$det(B)$为$det(A)$的转置行列式

二.交换行列式两行,行列式取相反数

不会证.jpg

三.行列式某一行都乘$k$,行列式值乘$k$

每一个排列都会包含一个当前行的数,那么显然答案会乘$k$

四.行列式如果两行元素成比例,则行列式为$0$

可以用性质三和一来证明

五.若行列式$A=B+C$,则$A$的值为$B$的值加$C$的值

不会证

六. 把行列式的某一行(列)的各元素同乘同一个数然后加到另一行(列)对应的元素上去,行列式不变

然后利用性质六,可以将该行列式化成三角形行列式,然后对角线相乘求值即可

代码回头补

矩阵树定理

对于一个无向图$G$,我们令$D_{i,j}$为度数矩阵,其中$D_{i,i}$代表第$i$个点的度数,$A_{i,j}$为邻接矩阵,代表$i,j$间有多少条边

$K_{i,j}$称为基尔霍夫矩阵,其定义为$K=D-A$

然后对于基尔霍夫矩阵,我们任意选择一个他的$n-1$阶主子式,求值即可

不会证明QwQ

变元矩阵树定理回头补锅

chevron_left SP104 HIGH - Highways
bzoj 1001 狼抓兔子 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名