字节跳动 automation stl vue绑定点击事件 react脚手架搭建 jquery事件绑定方法 windows查看进程命令 less的比较级 python练习 python手册 python的re模块 python调用自定义函数 python传参 javamysql javapackage java方法重载 java如何配置环境变量 javac java字符串相等 shell脚本参数 怎么安装linux python开发实例 免费的视频剪辑 程序员面试宝典 银头鲑鱼 dnf95b套 视频添加水印 黑域怎么用 opengl版本过低 摸摸头不哭表情包 画图橡皮擦怎么放大 迅捷屏幕录像工具 getdata软件 excel箱线图 dns地址 局域网监控系统 smartupload 错误1004 匹瑞诺德王冠 baidupan
当前位置: 首页 > 学习教程  > 编程语言

【算法讲13:高斯约旦消元法】

2021/2/13 20:04:45 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

前置 在线性代数的课程中,我们就学过基本的矩阵及其行初等变化。 根据这些初等变化,我们的老师就高速我们怎么样去进行消元,然后求解线性方程组。 模板题 【模板】高斯消元法 | 洛谷 P3389 挺基础的蓝题,虽然是个模板但是思路很…

前置

  • 在线性代数的课程中,我们就学过基本的矩阵及其行初等变化
    根据这些初等变化,我们的老师就高速我们怎么样去进行消元,然后求解线性方程组

模板题

  • 【模板】高斯消元法 | 洛谷 P3389
    挺基础的蓝题,虽然是个模板但是思路很简单可以手敲。

⌈ \lceil 高斯约旦消元法 ⌋ \rfloor

  • 首先,我们获得一个系数矩阵 A n × n A_{n\times n} An×n 和一个列向量 B n × 1 B_{n\times 1} Bn×1
    我们把它合并成一个增广矩阵 A n × ( n + 1 ) A_{n\times (n+1)} An×(n+1)
    那么这个矩阵代表什么意思呢?比如我们有一下方程组:
    { 1 x + 8 y + 2 z = 5 2 x + 4 y + 12 z = 10 1 x + 0 y + 4 z = 20 \begin{cases} 1x+8y+2z=5\\ 2x+4y+12z=10\\ 1x+0y+4z=20\\ \end{cases} 1x+8y+2z=52x+4y+12z=101x+0y+4z=20
    我们的增广矩阵就如下所示
    A = [ 1 8 2 ∣ 5 2 4 12 ∣ 10 1 0 4 ∣ 20 ] A= \begin{bmatrix} 1&8&2&|&5\\ 2&4&12&|&10\\ 1&0&4&|&20\\ \end{bmatrix} A=121840212451020
    【做法】:
    (1)我们按进行处理。假设现在处理到第 i i i
    为了使得答案精度更高,我们选择 该列中行号 ≥ i \ge i i 的行中最大的值的那行 ,然后把该行和第 i i i 进行交换
    (2)如果某一列的所有值都为 0 0 0 ,那么说明该行变量是个无关变量,任意取值都满足。
    (3)根据行初等变化,我们把除了第 i i i 行的每一行都减去一定的比值,使得 该行第 i i i 列为 0 0 0
    (4)这样操作完,系数矩阵只有主对角线位置的元素非零。容易算出每一个变量的取值了。
    【举例】:
    A = [ 1 8 2 ∣ 5 2 4 12 ∣ 10 1 0 4 ∣ 20 ] A= \begin{bmatrix} 1&8&2&|&5\\ 2&4&12&|&10\\ 1&0&4&|&20\\ \end{bmatrix} A=121840212451020
    (1)我们找第一列最大的元素,为 2 2 2 ,该行和第一行交换
    A = [ 2 4 12 ∣ 10 1 8 2 ∣ 5 1 0 4 ∣ 20 ] A= \begin{bmatrix} 2&4&12&|&10\\ 1&8&2&|&5\\ 1&0&4&|&20\\ \end{bmatrix} A=211480122410520
    (2)第二行减去第一行的 1 2 \frac{1}{2} 21 倍,第三行减去第一行的 1 2 \frac{1}{2} 21 倍,得到新的矩阵:
    A = [ 2 4 12 ∣ 10 0 6 − 4 ∣ 0 0 − 2 − 2 ∣ 15 ] A= \begin{bmatrix} 2&4&12&|&10\\ 0&6&-4&|&0\\ 0&-2&-2&|&15\\ \end{bmatrix} A=200462124210015
    (3)找第二列的行号为 2 ∼ 3 2\sim 3 23 的最大值。由于 6 6 6 最大且本身就是第二列,因此无需交换。
    (4)第一行减去第二行的 4 6 \frac{4}{6} 64 倍,第三行减去第二行的 − 2 6 -\frac{2}{6} 62 倍,得到:
    A = [ 2 0 44 3 ∣ 10 0 6 − 4 ∣ 0 0 0 − 10 3 ∣ 15 ] A= \begin{bmatrix} 2&0&\frac{44}{3}&|&10\\ 0&6&-4&|&0\\ 0&0&-\frac{10}{3}&|&15\\ \end{bmatrix} A=200060344431010015
    (5)找第三列的行号为 3 ∼ 3 3\sim 3 33 的最大值。最大值为 − 10 3 -\frac{10}{3} 310,无需交换。
    (6)第一行减去第三行的 − 44 3 ⋅ 3 10 -\frac{44}{3}\cdot\frac{3}{10} 344103 倍,第二行减去第三行的 4 ⋅ 3 10 4\cdot\frac{3}{10} 4103 倍。得到:
    A = [ 2 0 0 ∣ 76 0 6 0 ∣ − 18 0 0 − 10 3 ∣ 15 ] A= \begin{bmatrix} 2&0&0&|&76\\ 0&6&0&|&-18\\ 0&0&-\frac{10}{3}&|&15\\ \end{bmatrix} A=20006000310761815
    我们容易得到,变量的值为:
    { x = 38 y = − 3 z = − 4.5 \begin{cases} x=38\\ y=-3\\ z=-4.5\\ \end{cases} x=38y=3z=4.5
    完美!(手算错两遍咳咳咳)

补充

  • 它和普通的高斯消元法有什么区别吗?
    高斯消元法每次消元,最后会得到系数矩阵的上三角矩阵
    然后通过回带来得到所有解,稍微麻烦些。
    举个例子,比如得到下面的样子:
    A = [ 2 4 12 ∣ 10 0 8 2 ∣ 5 0 0 4 ∣ 20 ] A= \begin{bmatrix} 2&4&12&|&10\\ 0&8&2&|&5\\ 0&0&4&|&20\\ \end{bmatrix} A=200480122410520
    然后易得 z z z 的值,然后带回第二行得到 y y y 的值,再带回第一行得到 x x x 的值。
    我个人感觉高斯约旦消元法更加方便。

代码

  • 时间复杂度: O ( N 3 ) O(N^3) O(N3)
/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 1e2+50;
const ll  MOD = 1e9+7;

double aa[MAX][MAX];

bool GJ(int n){
    for(int i = 1;i <= n;++i){
        int now = i;
        int mx  = aa[i][i];
        for(int j = i + 1;j <= n;++j){
            if(aa[j][i] > mx){
                now = j;
                mx = aa[i][j];
            }
        }
        if(fabs(mx) < EPS)return false;
        if(now != i)
            for(int j = 1;j <= n + 1;++j)
                swap(aa[now][j],aa[i][j]);
        for(int j = 1;j <= n;++j){
            if(j == i)continue;
            for(int k = n + 1;k >= i;--k){
                aa[j][k] -= aa[j][i] / aa[i][i] * aa[i][k];
            }
        }
    }
    return true;
}
int main()
{
    int n;cin >> n;
    for(int i = 1;i <= n;++i)
    for(int j = 1;j <= n + 1;++j)
        scanf("%lf",&aa[i][j]);
    bool can = GJ(n);
    if(!can)puts("No Solution");
    else{
        for(int i = 1;i <= n;++i)
            printf("%.2f\n",aa[i][n+1] / aa[i][i]);
    }
    return 0;
}

本文链接: http://www.dtmao.cc/news_show_700389.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?