首页 > 其他分享 >高斯消元

高斯消元

时间:2024-08-11 19:56:27浏览次数:14  
标签:map int double 矩阵 include 高斯消

1.高斯消元的基础信息

本质

通过初等行变化,将线性方程组的增广矩阵转化为行阶梯矩阵,讲人话就是用加减消元来转化,代入消元来回带。

应用

用来求解线性方程组(m个一次方程,n个变量),矩阵的秩(校园后的主元数)以及求可逆方阵的逆矩阵。

难度

思维难度低,代码实现难度低

复杂度

时间:O(n^3)空间:O(nm)

2.高斯消元的算法流程(以下图为例)

1.构造增广矩阵(系数与常数项):

1  -2   1   0
0   2  -8   8
-4  5   9  -9

2.通过以交换行、某行乘以非负常数和两行相加这三种初等变化将原系统转化为更简单的三角形式

1  -2   1   0     1 -2  1  0     1 -2  1  0     
0   2  -8   8     0  1 -4  4     0  1 -4  4
0  -3  13  -9     0 -3 13 -9     0  0  1  3

3.回带求解(用方程理解)

x1-2*x2+x3=0
x2-4*x3=4
x3=3

从最后一行开始推,x3=3,x2=16,x1=29就是结果

3.代码详解

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
double map[111][111];
double ans[111];
double eps=1e-7;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)
            scanf("%lf",&map[i][j]);
    for(int i=1;i<=n;i++){
        int r=i;
        for(int j=i+1;j<=n;j++)
            if(fabs(map[r][i])<fabs(map[j][i]))
                r=j;//找本列最大的主元
        if(fabs(map[r][i])<eps)//最大的主元为0,则无解或无数解
     { printf("No Solution"); return 0; } if(i!=r)swap(map[i],map[r]);//对换一行或一列,属于找最大当前系数的其中一步。(这样就可以只处理当前行的系数啦!) double div=map[i][i]; for(int j=i;j<=n+1;j++) map[i][j]/=div;//系数化为1 for(int j=i+1;j<=n;j++){//i行后面的行的第i个清为0 div=map[j][i]; for(int k=i;k<=n+1;k++) map[j][k]-=map[i][k]*div; } } ans[n]=map[n][n+1]; for(int i=n-1;i>=1;i--){ ans[i]=map[i][n+1]; for(int j=i+1;j<=n;j++) ans[i]-=(map[i][j]*ans[j]); }//回带操作 for(int i=1;i<=n;i++) printf("%.2lf\n",ans[i]); }

4.高斯约旦算法

大体相似,将增广矩阵消为只有对角线有值的矩阵

#include <bits/stdc++.h>
using namespace std;
const double eps=1E-20;
int n;
double a[110][110];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n+1;j++)
        {
            scanf("%lf",&a[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        int max=i;
        for(int j=i+1;j<=n;j++)
        {
            if(fabs(a[j][i])>fabs(a[max][i]))max=j;
        }
        for(int j=1;j<=n+1;j++)swap(a[i][j],a[max][j]);
        if(fabs(a[i][i])<=eps)
        {
            printf("No Solution\n");
            return 0;
        }
        for(int j=1;j<=n;j++)//最主要的不同,从一开始循环
        {
            if(i==j)continue;
            double tmp=a[j][i]/a[i][i] ;
            for(int k=i+1;k<=n+1;k++)
            {
                a[j][k]-=a[i][k]*tmp;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%.2lf\n",a[i][n+1]/a[i][i]);
    }
    return 0;
 } 

5.对比

高斯约旦无需回带,代码更简单,但只能判断是否有唯一解,无法判断究竟是无解还是无数解。

高斯可以需回带,可以判断无解,无数解,唯一解

6.判解

对于无解的判断:某一行前n个数均为 0,最后的结果却不为0。

对于无数解的判断:某一行n+1个数均为0.

无解无数解的共同特点某一行前n个数都为0(有一个主元为0则)。

否则有唯一解。

标签:map,int,double,矩阵,include,高斯消
From: https://www.cnblogs.com/storms11/p/18275483

相关文章

  • 可变阶数高斯消元算法-passcal-c shap-c语言
    高斯消元法在各种工程领域都有广泛的应用,尤其是在需要求解线性方程组的情况下。尽管高斯消元法在某些情况下可能不是最高效的算法,但它仍然是一个强大且通用的工具,对于许多工程问题来说是非常实用的。随着计算机性能的提高,高斯消元法在处理大规模问题时也变得更加可行。高斯消......
  • 高斯消元
    高斯消元高斯消元法通常用于求解如下的\(n\)元线性方程组\[\begin{cases}a_{1,1}x_1+a_{2,2}x_2+\cdots+a_{1,n}x_n=b_1\\a_{2,1}x_1+a_{2,2}x_2+\cdots+a_{2,n}x_n=b_2\\\cdots\\a_{n,1}x_1+a_{n,2}x_2+\cdots+a_{n,n}......
  • 高斯消元
    #include<iostream>#include<cassert>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<cmath>#include<queue>#include<set>#include<cli......
  • 【数学】高斯消元
    1.算法简介高斯消元法(Gauss–Jordanelimination)是求解线性方程组的经典算法。例如求解下列方程组:\(\begin{cases}2x+9y-5z=10\\4x+20y+z=24\\x-2y+3z=8\end{cases}\)形式化的,高斯消元可用于求解类似于\(\begin{cases}a_{1,1}x_1+a_{1,2}x_2+\dots+a_{1,n}x_n=b......
  • G68 实数线性基+高斯消元法 P3265 [JLOI2015] 装备购买
    视频链接:G68实数线性基+高斯消元法P3265[JLOI2015]装备购买_哔哩哔哩_bilibili  P3265[JLOI2015]装备购买-洛谷|计算机科学教育新生态(luogu.com.cn)//线性基+高斯消元法O(n*m*m)#include<iostream>#include<cstring>#include<algorithm>usingnames......
  • 高斯消元
    高斯-约旦消元解线性方程组例题:线性方程组步骤:选出未被更新的行中第\(k\)列绝对值最大的值,令为主元把主元所在行移到当前行,加减消元消去主元重复12结束后若存在找不到主元(找到是0)的情况,那就遍历没处理的行,如果有常数项非\(0\)则无解,否则无数解点击查看代......
  • 高斯消元
    前言:由于作者未系统过学习线性代数,故下文肯定有不严谨的成分,不过应付算法竞赛是绰绰有余了QAQ。\[\begin{cases}a_{1,1}x_1+a_{1,2}x_2+\cdots+a_{1,n}x_n=b_1\\a_{2,1}x_1+a_{2,2}x_2+\cdots+a_{2,n}x_n=b_2\\\cdots\\a_{n,1}x_1+a_{n,2......
  • 高斯消元和矩阵快速幂
    高斯消元高斯消元是一种能在\(O(N^3)\)的时间内求解\(N\)元一次方程组的算法。其思路大致如下:使第一个未知数只有第一个式子中系数非\(0\)。使第二个未知数只有第二个式子中系数非\(0\)。\(\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\vdots\)使第......
  • AcWing算法基础课笔记——高斯消元
    高斯消元用来求解方程组a11x1+......
  • 高斯消元学习笔记
    引入高斯-约当消元法(Gauss–Jordanelimination)是求解线性方程组的经典算法,它在当代数学中有着重要的地位和价值,是线性代数课程教学的重要组成部分。高斯消元法除了用于线性方程组求解外,还可以用于行列式计算、求矩阵的逆,以及其他计算机和工程方面。过程一个经典的问题,给定一......