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

> source: 文章/lagrange-crt/index.md

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


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

<!-- more -->

## 物不知数

>
>
>今有物不知数，
>
>三三数之剩二，
>
>五五数之剩三，
>
>七七数之剩二，
>
>问物几何？
>
>——《孙子算经》

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

1. 每次只考虑一个除式有余数的情况
2. 对于有余数的情况，把余数都简化成最简单的$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$这两个变量来作为基底绘制坐标系

<center><img src="https://mdstore.oss-cn-beijing.aliyuncs.com/markdown/mod2_mod3.png" alt="mod2_mod3" style="zoom:72%;" /></center>

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

以线性代数的角度来看这个坐标系，我们可以发现可以以$\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}_{\mod 3} = 35\times 2 = 70
$$
同理我们可以得到剩下的两个向量：
$$
\boldsymbol{e}_2 = M_2 \times [M_2]^{-1}_{\mod 5} = 21\times 1 = 21 \\\\
\boldsymbol{e}_3 = M_3 \times [M_3]^{-1}_{\mod 7} = 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}_{\mod x-x_1}  = \frac{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}_i(x) = \prod_{j\neq i}\frac{x-x_j}{x_i - x_j}
$$
​	代入解向量我们可以得到
$$
f(x) =\sum_{i=1}^nf(x_i)\prod_{j\neq i}\frac{x-x_j}{x_i - x_j}(\mod M(x))
$$
上面的和拉格朗日插值算法长得已经非常像了，那么拉格朗日插值法是怎么来的呢？我们尝试从线性代数的角度分析一下

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

对于一个多项式：
$$
y = a_0 + a_1x +a_2x^2+a_3x^3 +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
这是什么？这不就是基向量吗？
$$

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

<center><img src="https://mdstore.oss-cn-beijing.aliyuncs.com/markdown/polymial_function.png" alt="polymial_function" style="zoom:72%;" /></center>

对于这个多项式，可以很直观地表现为：
$$
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$取单位量的构件. 然后用这些构件凑出所求的结构.

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

## Reference

1. [《数学文化》](https://book.douban.com/subject/3164999/)——顾沛， p151-174
2. [【拉格朗日插值法的本质】拉格朗日，孙子，与每个人都能推出来的插值法](https://www.bilibili.com/video/BV1TR4y1j745/)
3. [【拉格朗日插值】：思想、计算与误差](https://www.bilibili.com/video/BV1fL4y1T7fL/)
