🟢 拉格朗日插值法与中国剩余定理\#

我在一年前就感觉到拉格朗日插值法和中国剩余定理有些联系，当时是在顾沛的《数学文化》这本书上看到的，然后又看到了bilibili上乐正垂星佬的视频，感觉这些算术确实是通过线性代数，将函数给联系起来了，线性代数在高视角看问题上用途真是广泛啊

物不知数\#

今有物不知数，

三三数之剩二，

五五数之剩三，

七七数之剩二，

问物几何？

——《孙子算经》

这不就是带余除法吗，我们现在按条件写下来，设现在要求的数为$s$ $$ \left{ \begin{align} s &= 3n_1 +2\ s &= 5n_2 +3\ s &= 7n_3 +2 \end{align} \right. $$ 现在，我们要考虑将这个方程简化：

每次只考虑一个除式有余数的情况
对于有余数的情况，把余数都简化成最简单的$1$

这样我们就得到三个方程组： $$ \begin{bmatrix} x =& 3n_1 +1\ x =& 5n_2 \ x =& 7n_3 \end{bmatrix} (1);\quad \begin{bmatrix} y =& 3n_1 \ y =& 5n_2 +1\ y =& 7n_3 \end{bmatrix} (2);\quad \begin{bmatrix} z =& 3n_1 \ z =& 5n_2 \ z =& 7n_3 +1\end{bmatrix}(3) $$

(1)式表示，在5和7的公倍数中找被3除余1的数
(2)式表示，在3和7的公倍数中找被5除余1的数
(3)式表示，在3和5的公倍数中找被7除余1的数

于是对于(1)我们可以得到： $$ \left{ \begin{align} x-70 &= 3(n_1 -23)\ x-70 &= 5(n_2 -14)\ x-70 &= 7(n_3 -10) \end{align} \right. $$ 因此我们得到$x-70$能同时被3,5,7整除 $$ x = 105k_1 +70, \quad k_1 = 0,1,2,\cdots $$ 同理计算(2)和(3)式，可以得到： $$ y = 105k_2 +21, \quad k_1 = 0,1,2,\cdots \\ z = 105k_3 +15, \quad k_1 = 0,1,2,\cdots $$ 现在我们有： $$ \left{ \begin{align} x = 105k_1 +70 \ y = 105k_2 +21 \ z = 105k_3 +15 \end{align} \right. $$ 我们知道$x,y,z$分别被3,5,7除会余1，因此要让一个数被3除余2，我们只需要使用$2x$即可，同理，要让一个数被5除余3，只需要使用$3y$，要让一个数被7除余2，只需要使用$2z$

然后我们把这三个数加起来，因为这三个数被3，5，7中的其中一个数除的时候只有一个会生效即有余数，因此加起来可以保持性质不变，因此我们得到 $$ \begin{matrix} s &=& 2x+3y+2z \ &=& 70\times 2 + 21\times 3 +15\times 2 + 105k, k\in \mathbb{Z} \end{matrix} $$ 关于这个问题，明朝数学家程大位在《算法统宗》中还编成了一首歌诀：

三人通行七十稀，五树梅花廿一枝，

七子团圆正月半，除百零五便得知

至此，我们就在简单的算术方法下解决了这个问题，接下来我们将会以高视角来审视这个问题，体会体会一览众山小的感觉

中国剩余定理\#

秦九韶在物不知数问题中将此解法称为“大衍求一术”，这一叫法非常形象，这个结论直到18世纪才由高斯和欧拉(两幻神)发现(Chinese remainder theorem)

设$m_1,m_2,\cdots,m_n$两两互素，我们有同余方程组： $$ x \equiv a_1 (\mod m_1)\\ x \equiv a_2 (\mod m_2)\\ x \equiv a_3 (\mod m_3)\\ \vdots\\ x \equiv a_n (\mod m_n)\\ $$ 那么这个同余方程组的解为： $$ x \equiv \sum_{i=1}^n a_i\boldsymbol{e}(\mod{M}) \quad M = \prod_{i=1}^n m_i $$ 其中 $$ \boldsymbol{e} = M_i[M_i]_{\mod m_i}^{-1}, \quad M_i = \frac{M}{m_i},\quad i = 1,2,\cdots,n $$ 上面的这个式子如果我们不带任何知识储备去看，肯定看得一头雾水，完全不知道是怎么来的，接下来，我将从线性代数的角度来推导中国剩余定理

线性代数的视角\#

同余性质\#

首先我们要引入同余性质，这对于我们后面的推导有着简化的作用

如果$a\equiv b(\mod m)$，且$c \equiv d(\mod m)$，那么$a+b \equiv b+d (\mod m)$
如果$a\equiv b(\mod m)$，且$c \equiv d(\mod m)$，那么$a-b \equiv b-d (\mod m)$
如果$a\equiv b(\mod m)$，且$c \equiv d(\mod m)$，那么$ab \equiv bd (\mod m)$
如果$ab\equiv 1 (\mod m)$，定义$a^{-1} \equiv b(\mod m)$

线性空间中的物不知数\#

接下来我们来看物不知数问题，现在我么做一个简化，就假设有两个变量$2$和$3$，那么一个数除以$2$和$3$能有多少种情况呢？这个很简单，除以$2$有两种，除以$3$有三种，因此一共只有六种情况，我们甚至可以像这样列出来，而且对于每种具体的情况我们都能很轻松地找到结果： $$ \left{ \begin{align} x &\equiv 0(\mod 2) \ x &\equiv 0(\mod 3) \end{align} \right. \Longrightarrow x = 0 $$

\[ \left\{ \begin{align} x &\equiv 0(\mod 2) \\ x &\equiv 0(\mod 3) \end{align} \right. \Longrightarrow x = 0 \]

\[ \left\{ \begin{align} x &\equiv 1(\mod 2) \\ x &\equiv 0(\mod 3) \end{align} \right. \Longrightarrow x = 3 \]

\[ \left\{ \begin{align} x &\equiv 0(\mod 2) \\ x &\equiv 1(\mod 3) \end{align} \right. \Longrightarrow x = 4 \]

\[ \left\{ \begin{align} x &\equiv 1(\mod 2) \\ x &\equiv 1(\mod 3) \end{align} \right. \Longrightarrow x = 1 \]

\[ \left\{ \begin{align} x &\equiv 0(\mod 2) \\ x &\equiv 2(\mod 3) \end{align} \right. \Longrightarrow x = 2 \]

\[ \left\{ \begin{align} x &\equiv 1(\mod 2) \\ x &\equiv 2(\mod 3) \end{align} \right. \Longrightarrow x = 5 \]

现在，我们用坐标系来看看，我们以$\mod 2$和$\mod 3$这两个变量来作为基底绘制坐标系

我们发现这里还是有一些规律的，箭头碰到右边就会穿过去，从左边穿出来

以线性代数的角度来看这个坐标系，我们可以发现可以以$\mod 2 = 1$和 $\mod 3 = 1$为一组基向量，为什么呢？在两条轴上，一个变量是不会对另一个变量造成干扰的，即它们是线性无关的，因此我们在这个例子中有： $$ \boldsymbol{e}_1 = [1\mod 2] = \begin{pmatrix} 3 \ 0 \end{pmatrix} \\ \boldsymbol{e}_2 = [1\mod 3] = \begin{pmatrix} 0 \ 4 \end{pmatrix} $$ 那么

\[ \begin{pmatrix}a \\ b \end{pmatrix} = a\times \begin{pmatrix} 1 \\ 0 \end{pmatrix} +b\times \begin{pmatrix} 0 \\ 1 \end{pmatrix} = 3a + 4b \]

这样我们就成功得到了一组解了

现在我们再来看物不知数的问题，我们翻译一下条件：$m_1 = 3, m_2 = 5, m_3 = 7$，要求最小公倍数，我们可以先将它们都乘起来，即 $$ M = \prod_{i=1}^3 m_i \\ M_1 = \frac{M}{m_1} $$ 因此这里 $$ M_1 = m_2 \times m_3 = 35 \\ M_1 \equiv 2(\mod 3) $$ 那么我们该如何让余数为$1$呢？简单，式子两边$\times 2$就能解决： $$ 2\times M_1 \equiv 2\times 2 (\mod 3)\\ 2M_1 \equiv 1(\mod 3) $$ 这里用到了我们前面提到的同余的性质，再根据我们前面对数论倒数的定义： $$ M_1^{-1} \equiv 2(\mod 3) $$ 我们就能得到： $$ \boldsymbol{e}1 = M_1 \times [M_1]^{-1} = 35\times 2 = 70 $$ 同理我们可以得到剩下的两个向量： $$ \boldsymbol{e}2 = M_2 \times [M_2]^{-1} = 21\times 1 = 21 \\ \boldsymbol{e}3 = M_3 \times [M_3]^{-1} = 15\times 1 = 15 $$ 这样我们就求出了这个三维线性空间的三个正交(线性无关)向量 $$ \begin{pmatrix} 70 &0&0 \ 0 &21&0 \ 0 &0&15 \end{pmatrix} $$ 这样的话，，无论我们怎么除，都只有一个向量在生效

接下来我们看看中国剩余定理是如何与拉格朗日插值法相联系的

拉格朗日插值法\#

整式的同余\#

高中阶段我们有时会用到整式除法，但是基本上是在能够进行因式分解的时候使用，对于不能进行因式分解的情况，我们基本上是没有办法处理的。对于数，我们可以加上余数，不过这个我们在小学二年级就学了，但是对于整式，我们一样可以这样操作： $$ x^3 / (x-2) = x^2 + 2x + 4 \cdots 2^3 \\ x^3 \equiv 2^3 (\mod x-2) \\ x^2 \equiv 2^2 (\mod x-2) $$ 事实上，$\forall n \in \mathbb{N}, x^n\equiv a^n(\mod x-a)$

我们之前的同余性质：

如果$a(x)b(x)\equiv 1(\mod m(x))$，定义$a^{-1}(x)\equiv b(x)(\mod m(x))$，将$a^{-1}(x)$称为逆元

在多项式中，一次项同余有这样的性质： $$ f(x) = f(a)(\mod x-a) \\ f^{-1}(a) = \frac{1}{f(a)}(\mod x-a) $$

整式的中国剩余定理\#

学过线性代数我们就知道，函数也可以在线性代数中被表示，因此如果有：

\[ \begin{matrix} f(x)&\equiv&a_1(x)(\mod x-x_1) \\ f(x)&\equiv&a_2(x)(\mod x-x_2) \\ f(x)&\equiv&a_3(x)(\mod x-x_3) \\ &\vdots& \\ f(x)&\equiv&a_n(x)(\mod x-x_4) \\ \end{matrix} \]

对这些同余式利用上面的性质：

\[ \begin{matrix} f(x)&\equiv&f(x_1)(\mod x-x_1) \\ f(x)&\equiv&f(x_2)(\mod x-x_2) \\ f(x)&\equiv&f(x_3)(\mod x-x_3) \\ &\vdots& \\ f(x)&\equiv&f(x_n)(\mod x-x_4) \\ \end{matrix} $$ 那么 $$ f(x)\equiv \sum_{i=1}^nf(x_i)\boldsymbol{e}_i(x)(\mod M(x)) $$ 其中 $$ M_i(x) = \frac{M(x)}{m_i(x)}, \quad i =1,2,\cdots, n $$ 我们先来看$M_1(x)$ $$ M_1(x) = (x-x_2)(x-x_3)\cdots(x-x_n) \]

\[ [M_1(x)]^{-1}_{\mod x-x_1} \equiv M^{-1}_1(x_1)(\mod x-x_1) = \frac{1}{M_1(x_1)}(\mod x-x_1) \]

因此 $$ \boldsymbol{e}1(x) = M_1(x)[M_1(x)]^{-1} \\ = \frac{(x-x_2)(x-x_3)\cdots(x-x_n)}{(x_1-x_2)(x_1-x_3)\cdots(x_1-x_n)} = \prod_{j\neq 1}\frac{x-x_j}{x_1 - x_j} $$ 一般地 $$ \boldsymbol{e}} = \frac{M_1(x)}{M_1(x_1)i(x) = \prod $$ 代入解向量我们可以得到 $$ f(x) =\sum_{i=1}^nf(x_i)\prod_{j\neq i}\frac{x-x_j}{x_i - x_j}(\mod M(x)) $$ 上面的和拉格朗日插值算法长得已经非常像了，那么拉格朗日插值法是怎么来的呢？我们尝试从线性代数的角度分析一下}\frac{x-x_j}{x_i - x_j

线性空间下的拉格朗日插值法\#

对于一个多项式： $$ y = a_0 + a_1x +a_2x^2+a_3x3 +a_4x^4 $$ 我们需要五个点，对应$x_1,x_2,x_3,x_4,x_5$才能确定这个多项式：

\[ \left\{ \begin{array}{c} y_1 = a_0+a_1x_1+a_2x_1^2+a_3x_1^3+a_4x_1^4 \\ y_1 = a_0+a_1x_2+a_2x_2^2+a_3x_2^3+a_4x_2^4 \\ y_1 = a_0+a_1x_3+a_2x_3^2+a_3x_3^3+a_4x_3^4 \\ y_1 = a_0+a_1x_4+a_2x_4^2+a_3x_4^3+a_4x_4^4 \\ y_1 = a_0+a_1x_5+a_2x_5^2+a_3x_5^3+a_4x_5^4 \end{array} \right. \]

很容易可以写成矩阵：

\[ \begin{bmatrix} y_1\\y_2\\y_3\\y_4\\y_5 \end{bmatrix}= \underbrace{ \begin{bmatrix} 1 & x_1 & x_1^2 & x_1^3 & x_1^4 \\ 1 & x_2 & x_2^2 & x_2^3 & x_2^4 \\ 1 & x_3 & x_3^2 & x_3^3 & x_3^4 \\ 1 & x_4 & x_4^2 & x_4^3 & x_4^4 \\ 1 & x_5 & x_5^2 & x_5^3 & x_5^4 \end{bmatrix}}_{Vandermonde\ matrix}· \begin{bmatrix} a_0\\a_1\\a_2\\a_3\\a_4 \end{bmatrix} \]

当数据很多的时候，解这个方程组的运算量是很大的，在线性代数中，我们需要充分利用基的性质，现在我们有$n+1$个节点 $$ P_n(x_0) = y_0,P_n(x_1) = y_1,\cdots,P_n(x_n) = y_n $$ 我们可以得到这样的形式 $$ P_n(x) = y_0l_0(x) + y_1l_1(x) + \cdots + y_nl_n(x) $$ 其中 $$ l_i(x) = \prod_{j\neq i}\frac{x-x_j}{x_i - x_j} $$

\[ P_n(x) = \sum_{i=0}^n y_il_i(x) = \sum_{i=0}^n y_i\prod_{j\neq i}\frac{x-x_j}{x_i - x_j} \]

这里的$l_i(x)$称为拉格朗日基函数，我们希望拉格朗日基函数是这样的： $$ \begin{matrix} l_0(x_0) = 1 & l_1(x_1) = 1 &\cdots& l_n(x_n) = 1 \ l_0(x_i) = 0 & l_0(x_i) = 0 &\cdots& l_0(x_i) = 0 \ \end{matrix}\Longrightarrow 这是什么？这不就是基向量吗？ $$

我们希望在使用拉格朗日插值法的时候，通过对其中一个节点的调整，只会影响到它自己的值，而对其他节点的值没有影响。我们接着看上面这个四次多项式，由于拉格朗日基函数的特性，我们可以写成零点式

对于这个多项式，可以很直观地表现为： $$ l_1(x) = c(x-x_0)(x-x_2)(x-x_3)(x-x_4) $$

因为$l_1(x_1) = 1$,则 $$ c= \frac{1}{(x_1-x_0)(x_1-x_2)(x_1-x_3)(x_1-x_4)} $$

事实上，上面的这幅图也是用同样的方法画出来的，因此 $$ l_1(x) = \frac{(x-x_0)(x-x_2)(x-x_3)(x-x_4)}{(x_1-x_0)(x_1-x_2)(x_1-x_3)(x_1-x_4)} = \prod_{k\neq0, k\neq j}^n\frac{x-x_k}{x_j-x_k} $$

将求这个点的方法推广到所有的点，就得到了我们刚才的插值公式，其实这个形式的拉格朗日插值法还有一些弊端，在算法领域不够实用： 1. 算法复杂度 big O notation: $O(n^2)$，复杂度较高，需要计算乘法 2. 加入新点的时候需要重新计算

因此我们希望对这个算法进行改进，具体参考末尾的链接

总结\#

两个看起来毫不相关的事情：拉格朗日插值法和中国剩余定理，竟然有着非常相似的内核！究其本质，还是在利用线性空间的性质。而分别看待这两个问题，一个是数论同余，另一个是函数插值，竟然可以通过线性代数相联系起来，我不禁赞叹线性空间这个概念真是让人有无穷的想象啊

此外，对于这个问题，华罗庚先生将解决问题的基本思想称为“单因子构件凑成法”，并概括成了如下的“合成原则”，我认为非常通俗易懂：

要做出具有平行的、类似的几个性质$A,B,C$的一个数学结构，而$A,B,C$分别以某种量$\alpha,\beta,\gamma$刻画，这时可用“单因子构件凑成法”: 先作$B,C$不发生作用，而$A$取单位量的构件；再作$C,A$不发生作用，$B$取单位量的构件；再作$A,B$不发生作用，$C$取单位量的构件. 然后用这些构件凑出所求的结构.

这个原则在有的书里称为“孙子——华原则”，体现了“化繁为简”的思想.