高斯消元求待定系数

发表于 更新于 分类于 阅读次数：

手撸了一份，推公式用。

如果\(f(x)\)为多项式，即满足 \[f(x) = \sum_{i=0}^{n} a_i x^i\] 我们可以通过打表找出\(n+1\)个点值，然后用待定系数法求解。我们可以得到这样一个方程 \[\begin{bmatrix} x_0^0 & x_0^1 & \cdots & x_0^n  \\x_1^0 & x_1^1 & \cdots & x_1^n\\ \vdots & \vdots & \ddots & \vdots \\ x_n^0 & x_n^1 & \cdots & x_n^n \end{bmatrix} \cdot \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_n \end{bmatrix} =\begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_n \end{bmatrix}\] 那么我们可以通过系数矩阵\(\boldsymbol X\)和\(\vec y\)向量来构造增广矩阵\([{\boldsymbol X} | \vec y ]\)，进而通过高斯消元法求解待定系数。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class AugMatrix:
    def __init__(self, row, col):
        self.row, self.col = row, col
        self.mtr = [[0] * (col + 1) for i in range(row)]
    def fillAt(self, row, col, val):
        self.mtr[row][col] = val
    def fillAugAt(self, row, val):
        self.mtr[row][self.col] = val
    def fill(self, mtr, augMtr):
        for i in range(self.row):
            for j in range(self.col):
                self.mtr[i][j] = mtr[i][j]
            self.mtr[i][self.col] = augMtr[i]
    def printMtr(self):
        for i in range(self.row):
            print(self.mtr[i])
    @staticmethod
    def gcd(a, b):
        while b != 0:
            a, b = b, a % b
        return a
    def rowMul(self, row, val):
        for i in range(self.col + 1):
            self.mtr[row][i] = self.mtr[row][i] * val
    def rowSub(self, rowA, rowB):
        for i in range(self.col + 1):
            self.mtr[rowA][i] = self.mtr[rowA][i] - self.mtr[rowB][i]
    def eliminate(self):
        for i in range(self.col - 1):
            for j in range(self.row - 1, i, -1):
                now, pre = self.mtr[j][i], self.mtr[j - 1][i]
                if now == 0:
                    continue
                elif pre == 0:
                    self.mtr[j], self.mtr[j - 1] = self.mtr[j - 1], self.mtr[j]
                    continue
                gcd = self.gcd(now, pre)
                lcm = now * pre // gcd
                self.rowMul(j, lcm // now)
                self.rowMul(j - 1, lcm // pre)
                self.rowSub(j, j - 1)
        for i in range(self.col - 1, 0, -1):
            for j in range(0, i):
                now, pre = self.mtr[j][i], self.mtr[j + 1][i]
                if now == 0 or pre == 0:
                    continue
                gcd = self.gcd(now, pre)
                lcm = now * pre // gcd
                self.rowMul(j, lcm // now)
                self.rowMul(j + 1, lcm // pre)
                self.rowSub(j, j + 1)
    def approximate(self):
        for i in range(self.row):
            g = self.gcd(self.mtr[i][self.col], self.mtr[i][i])
            self.mtr[i][self.col] = self.mtr[i][self.col] // g
            self.mtr[i][i] = self.mtr[i][i] // g
    def simplify(self):
        for i in range(self.row):
            self.mtr[i][self.col] = self.mtr[i][self.col] / self.mtr[i][i]
            self.mtr[i][i] = 1
    def generate(self):
        ret = list()
        for i in range(self.row):
            ret.append(self.mtr[i][self.col])
        return ret