线性方程组

主要用高斯消元 (Gaussian Elimination) 来求解线性方程组(System of linear equations).

一个 $n$ 未知数的线性方程组有唯一解, 需要存在 $n$ 个线性无关的方程.

对于有 $n$ 个未知数, $n$ 个方程的线性方程组, 我们使得矩阵的第 $i$ 行第 $n + 1$ 列为第 $i$ 个方程等号右边的常数. 前 $n$ 列中, 第 $i$ 行第 $j$ 列表示第 $i$ 个方程中第 $j$ 个未知数的系数.

对于线性方程组的增广矩阵, 我们可以进行如下变换并且解不变:

• 交换两行

• 某行乘以某数

• 两行相加减

我们把除第一行以外的行都减去第一行的特定倍数, 使得除第一行以外的每一行的第一项都为 $0$. 用同样的方法把 $[3, n]$ 的第 $2$ 项变成 $0$. 最后得到了第 $i$ 行的前 $i - 1$ 项为 $0$ 的矩阵.

然后反过来, 把前 $n - 1$ 行减去对应倍数的第 $n$ 行, 就可以消掉前 $n - 1$ 行的第 $n$ 项. 以此类推可以让第 $i$ 行只剩下第 $i$ 列和第 $n + 1$ 列. 最后只需要把所有行乘以对应倍数使得第 $i$ 列为 $1$, 这时第 $i$ 行的第 $n + 1$ 列就是解中第 $i$ 个未知数的值了.

复杂度 $O(n^3)$. 下面是模板题代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

double a[105][105];
unsigned m, n;
unsigned A, B, C, D, t;
unsigned Cnt(0), Ans(0), Tmp(0);
inline char Zer(double& x) { return (x <= 0.00000001) && (x >= -0.00000001); }
signed main() {
  n = RD();
  for (unsigned i(1); i <= n; ++i) for (unsigned j(1); j <= n + 1; ++j) a[i][j] = RDsg();
  for (unsigned i(1); i <= n; ++i) {
    unsigned Do(i);
    while ((Zer(a[Do][i])) && (Do <= n)) ++Do;
    if (Do > n) { printf("No Solution\n");return 0; }
    if (Do ^ i) for (unsigned j(i); j <= n + 1; ++j) swap(a[i][j], a[Do][j]);
    for (unsigned j(i + 1); j <= n; ++j) {
      double Tms(-a[j][i] / a[i][i]);
      for (unsigned k(i); k <= n + 1; ++k) a[j][k] += a[i][k] * Tms;
    }
  }
  for (unsigned i(n); i; --i) {
    if (Zer(a[i][i])) { printf("No Solution\n");return 0; }
    for (unsigned j(i - 1); j; --j)
      a[j][n + 1] -= (a[j][i] / a[i][i]) * a[i][n + 1], a[j][i] = 0;
  }
  for (unsigned i(1); i <= n; ++i) printf("%.2lf\n", a[i][n + 1] / a[i][i]);
  return Wild_Donkey;
}

对于三维向量 $(x_0, y_0, z_0)$, $(x_1, y_1, z_1)$, 其叉乘定义为两个向量所在平面的法向量, 模长是两个向量决定的平行四边形的面积. 即为 $(y_0z_1 - z_0y_1, z_0x_1 - x_0z_1, x_0y_1 - y_0x_1)$. 在右手系内, 对于法向量的方向, 可以用右手定则判断. 如果是左手系则用左手定则判断. 如果是二维向量, 可以将其作为第三维为 $0$ 的向量做叉乘, 得到的向量关于两个向量所在平面垂直, 也就是关于 $x$ 轴, $y$ 轴所在平面垂直, 所以它的前两维一定是 $0$, 我们取它的第三维坐标作为二维向量叉乘的结果.

叉乘的反交换律可以表示为:

$\vec a \times \vec b = -\vec a \times \vec b$