高斯消元法和拉格朗日插值

· · 个人记录

本来这俩没什么关系，但是在 OI 中可以解决相似的问题（如求多项式），就在一起写了。

\color{brown} 高斯消元

高斯消元法适合求解多元线性方程组。

简化文章内容 （其实是太菜不会讲），本文不强调线性代数理论，强调做法。

高斯消元有传统方法，也有高斯-约旦法。二者区别很小，这里讲约旦法。

P2455 [SDOI2006] 线性方程组

此题除去区分「无穷解」与「无解」情况外，与 P3389 模板无异。而区分「无穷解」与「无解」的方式也是本文内容之一。

消元步骤

我们用样例举例

3
2 -1 1 1
4 1 -1 5
1 1 1 0
\begin{bmatrix} 2 & -1 & 1 & 1 \\ 4 & 1 & -1 & 5 \\ 1 & 1 & 1 & 0 \end{bmatrix}

矩阵前三列分别表示三个元的系数，第四列表示方程等式右边的值。

利用解方程“加减消元”的思想，我们用一行的值去消其余行，使得其余行本列为 0，即该列表示的元仅该行的对应位置有系数。

那么最终理想状态下消的结果应当还满足每行仅一个元有系数。我们将每次操作保留下来的系数叫做“消除者”，被消成 0 的系数叫做“被消除者”。

如果按顺序枚举 i ，将 (i,i) 作为本列的“消除者”，结果应该长这样：

\begin{bmatrix} a & 0 & 0 & x \\ 0 & b & 0 & y \\ 0 & 0 & c & z \end{bmatrix}

此时，三个元的值分别为 \frac x a，\frac y b，\frac z c。

而前述消除方法也很简单，“被消除者”所在的行减去指定“消除者”所在的行乘以“消除者”和“被消除者”之间的倍数关系即可。

就像这样：\color{red}^{[*]}

\begin{bmatrix} 2 & -1 & 1 & 1 \end{bmatrix} \times 2= \begin{bmatrix} 4 & -2 & 2 & 2 \end{bmatrix} \begin{bmatrix} 4 & 1 & -1 & 5 \end{bmatrix} - \begin{bmatrix} 4 & -2 & 2 & 2 \end{bmatrix}= \begin{bmatrix} 0 & 3 & -3 & 3 \end{bmatrix}

有一个需要注意的细节是，如果程序使用浮点数计算，可能会产生精度问题。减小精度误差的方式：每列在行数 \ge i 的行中，选值最大的作为“消除者”。\color{red}^{[**]}程序中一般顺序枚举 i ，将 (i,i) 作为“消除者”，那么我们将 i 列绝对值最大的数所在的行交换到当前行即可。

证明：

我还没见过严谨证明，但是抽象理解起来，可以想到当值越大的作为了“消除者”，其与“被消除者”的倍数越大，“消除者”所在行内其余数给对应列的数提供减益时乘的系数越小，精度越高。（此证明参考皎月半撒花 dalao 在模板题的题解）

现在我们模拟程序做一遍样例：

(1,1) 是指定消除者

\begin{bmatrix} \color{red}2 & -1 & 1 & 1 \\ 4 & 1 & -1 & 5 \\ 1 & 1 & 1 & 0 \end{bmatrix}

减小精度，交换

\begin{bmatrix} \color{red}4 & 1 & -1 & 5 \\ 2 & -1 & 1 & 1 \\ 1 & 1 & 1 & 0 \end{bmatrix}

消除第 1 列（更具体的过程参考上文\color{red}^{[*]}，只是这里用 4 消 2 而上文是 2 消 4 罢了）

\begin{bmatrix} \color{red} 4 & 1 & -1 & 5 \\ 0 & -\frac 3 2 & \frac 3 2 & -\frac 3 2 \\ 0 & \frac 3 4 & \frac 5 4 & -\frac 5 4 \end{bmatrix}

(2,2) 是指定消除者，且无需交换

\begin{bmatrix} 4 & 1 & -1 & 5 \\ 0 & \color{red}-\frac 3 2 & \frac 3 2 & -\frac 3 2 \\ 0 & \frac 3 4 & \frac 5 4 & -\frac 5 4 \end{bmatrix}

消除第 2 列

\begin{bmatrix} 4 & 0 & 0 & 4 \\ 0 & \color{red}-\frac 3 2 & \frac 3 2 & -\frac 3 2 \\ 0 & 0 & 2 & -2 \end{bmatrix}

(3,3) 是指定消除者，且无需交换

\begin{bmatrix} 4 & 0 & 0 & 4 \\ 0 & -\frac 3 2 & \frac 3 2 & -\frac 3 2 \\ 0 & 0 & \color{red}2 & -2 \end{bmatrix}

消除第 3 列

\begin{bmatrix} 4 & 0 & 0 & 4 \\ 0 & -\frac 3 2 & 0 & 0 \\ 0 & 0 & \color{red}2 & -2 \end{bmatrix}

已经得到了希望得到的形式

解的存在性

上述做法仍不完善，我们默认保证了方程组是有解的。如果方程组存在无解或者无穷组解，我们的做法没有相应的判断方法。

怎么办呢？可以想到如果存在无解或者无穷组解，那么至少存在一项的系数是 0。在此前提下，如果存在等式右边（矩阵最后一列）相应位置不为 0，那么无解，否则无穷组解。

修改原做法的一些位置即可。

  1. 如果枚举到一列全是 0，那么跳过。

分析：「无穷解」与「无解」的情况下，一定会出现这种情况，在消元过程中跳过，在最后统一判断。

分析：由于上一条遇到全 0 就跳过的规定，可能存在一些式子可以消后面的元，但是被跳过了，导致后续误判。

CODE

\color{brown} 拉格朗日插值

拉格朗日插值，利用 n 个点插出确定的 k(k<n) 次多项式的方法。

这种插值方法虽然无法确定多项式的系数，但可以每次对一个确定 x 求出多项式的值，每次操作 O(n^2)，部分情况可以优化至 O(n)。

P4781 【模板】拉格朗日插值

假设题目要求 f(k)，已知 n 组取值 (x_i,y_i)。

f(k)=\sum_{i=1}^n y_i \prod_{j\not =i}\frac{k-x_j}{x_i-x_j}

这个多项式，如果带入原取值进去（比如问 f(x_t)），会发现和式除了 i=t 的每一项都为 0，而 i=t 项为 y_t。

而已经满足 n 个点了，只要该多项式次数 <n，那么它就是唯一确定的。

如果 x_i 的取值是连续的，显然可以用前缀积优化至 O(n)。

参见 The Sum of the k-th Powers。