专栏文章

详解高斯消元

___mt19937__
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq7lzew
此快照首次捕获于
2025/12/04 00:16
3 个月前
此快照最后确认于
2025/12/04 00:16
3 个月前
查看原文

详解高斯消元

好东西，可以求所有一次方程组的解。\color {red} 好东西，可以求所有一次方程组的解。

前置知识

一般消元法的公理：

  • 两方程互换，解不变；
  • 一方程乘以非零数kk，解不变；
  • 一方程乘以数kk加上另一方程，解不变。

增广矩阵：

由一个矩阵AA和一个常数列BB组成的矩阵称为增广矩阵。
通常为一下格式：
(A11…AN1A21…AN2⋮    ⋱      AN1…ANN|sum1sum2⋮sumN)\left ( \begin{matrix} A_{11}\dots A_{N1} \\ A_{21}\dots A_{N2} \\ \vdots\space\space\space\space\ddots\space\space\space\space\space\space \\ A_{N1}\dots A_{NN} \end{matrix} \middle| \begin{matrix} sum_1 \\ sum_2 \\ \vdots \\ sum_N \end{matrix} \right )

高斯消元的目标矩阵

即上三角矩阵：
(…            0…          0 0…       ⋱          0 0 0…w|sum1sum2⋮sumN)\left ( \begin{matrix} \dots\space\space\space\space\space\space\space\space\space\space\space\space\\ 0\dots\space\space\space\space\space\space\space\space\space\space\\ 0\space 0\dots\space\space\space\space\space\space\space\\ \ddots\space\space\space\space\space\space\space\space\space\space\\ 0\space 0 \space 0\dots w \end{matrix} \middle| \begin{matrix} sum_1 \\ sum_2 \\ \vdots \\ sum_N \end{matrix} \right )

基本步骤

1.转化

把方程组转化为一下格式：
{A11×x1+A12×x2+⋯+A1N×xN=sum1A12×x1+A22×x2+⋯+A2N×xN=sum2              ⋮AN1×x1+AN2×x2+⋯+A1N×xN=sumN\begin{cases} A_{11}\times x_1 + A_{12}\times x_2 + \dots + A_{1N}\times x_N= sum_1 \\ A_{12}\times x_1 + A_{22}\times x_2 + \dots + A_{2N}\times x_N= sum_2 \\ \space\space\space\space\space\space\space\space\space\space\space\space\space\space\vdots \\ A_{N1}\times x_1 + A_{N2}\times x_2 + \dots + A_{1N}\times x_N= sum_N \\ \end{cases}

2.把系数写成增广矩阵

依据：
  • 在消元法中，参与计算和发生改变的是方程中各变量的系数；
  • 各变量并未参与计算，且没有发生改变；
  • 可以利用系数的位置表示变量，从而省略变量；
  • 在计算中将变量简化省略，方程的解不变。

3.行变换消元

第ii次消元选定第ii行ii列的元素为主元。
如果主元为00，那么就交换下一行，直到他遇到一个不为00的元素为止，如果全是00的话，就直接跳过。
然后，将第i∽ni\backsim n行的元素乘上lcm(ai,ai+1…an)lcm(a_i,a_{i+1}\dots a_n)。
再将第i+1∽ni+1\backsim n行都减去第ii行，就完成了第ii列的消元。

4.回带

傻子都会。

CODE

CPP
#include <cmath>
#include <cstdio>
#include <utility>

using namespace std;

const long double eps = 0.0000000000001L;

long double mat[101][102];

bool isZero(long double x)
{
	return fabs(x) < eps;
}

bool solve(int n)
{
	for (int i = 1; i <= n; i++)
	{
		int notZero = i;
		for (int j = i; j <= n; j++)
		{
			if (!isZero(mat[j][i]))
			{
				notZero = j;
				break;
			}
		}
		if (notZero != i)
		{
			swap(mat[i], mat[notZero]);
		}
		if (isZero(mat[i][i]))
		{
			return false;
		}
		for (int j = i + 1; j <= n + 1; j++)
		{
			mat[i][j] /= mat[i][i];
		}
		for (int j = i + 1; j <= n; j++)
		{
			for (int k = i + 1; k <= n + 1; k++)
			{
				mat[j][k] -= mat[j][i] * mat[i][k];
			}
		}
	}
	for (int i = n - 1; i >= 1; i--)
	{
		for (int j = i + 1; j <= n; j++)
		{
			mat[i][n + 1] -= mat[i][j] * mat[j][n + 1];
		}
	}
	return true;
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n + 1; j++)
		{
			scanf("%Lf", &mat[i][j]);
		}
	}
	if (solve(n))
	{
		for (int i = 1; i <= n; i++)
		{
			printf("%.2Lf\n", mat[i][n + 1]);
		}
	}
	else
	{
		puts("No Solution");
	}
	return 0;
}

完结撒花！！🎉🎉🎉

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...