《机器学习数学基础》补充资料：韩信点兵与拉格朗日插值法

本文作者：卓永鸿

19世纪的伟大数学家高斯，他对自己做的数学有非常高的要求，未臻完美不轻易发表。于是经常有这样的情况：其他也很厉害的数学家提出自己的工作，高斯便拿出自己的文章说他一二十年前就做出来了，而且做得更好。导致经常有杰出数学家吐血三升，甚至对高斯怀恨在心。

高斯在 1801年发表《算术研究》(Disquisitiones Arithmeticae)，当中提出一个关于同余的定理。后来 1874年，德国科学史家马蒂生，指出早在南北朝时《孙子算经》里面就提出了等价的算法，比高斯早了一千多年。此后，这个定理就被称为中国剩余定理（Chinese remainder theorem）。这下，高斯若天上有知，总算自己也尝了一次这种滋味。

《孙子算经》中所提出的，是“物不知数”问题，俗称“韩信点兵”，这是中国古代数学研究成果中极少数为世界所知晓的。这问题大概是说：有一正数除以三余二、除以五余三、除以七余二，则此正数最小为多少？

这个问题在《孙子算经•卷下》第二十六题，原文抄附如下：“今有物，不知其数。三、三数之，剩二；五、五数之，剩三；七、七数之，剩二。问物几何？答曰：二十三。术曰：‘三、三数之，剩二’，置一百四十；‘五、五数之，剩三’，置六十三；‘七、七数之，剩二’，置三十。并之，得二百三十三。以二百一十减之，即得。凡三、三数之，剩一，则置七十；五，五数之，剩一，则置二十一；七、七数之，剩一，则置十五。一百零五以上，以一百零五减之，即得。”其中“一百零五”乃是一百零五，并非今日口语所指的一百五十。

这类问题在高中数学课程中经常出现，许多老师所授解题方式千奇百怪，常令学生无所适从。然而观察《孙子算经》的算法，它其实是带有比较朴素的一般性思想，先考虑几个简单的特殊情况，将这些特殊情况线性组造出特解，再写出通解。以今日的数学符号表述如下：

首先解齐次方程
$$\{\begin{array}{l}{x}_h=3q_1+0\\ x_h=5q_2+0\\ x_h=7q_3+0\end{array}$$
得到齐次方程的通解公式
$$x_h=3\times 5\times 7\times n=105n,n\in \mathbb{Z}\text{\hspace{1em}(1)}$$

接着分别找

$$\{\begin{array}{l}{x}_1=3q_{11}+1\\ x_1=5q_{12}+0\\ x_1=7q_{13}+0\end{array}\{\begin{array}{l}{x}_2=3q_{21}+0\\ x_2=5q_{22}+1\\ x_2=7q_{23}+0\end{array}\{\begin{array}{l}{x}_3=3q_{31}+0\\ x_3=5q_{32}+0\\ x_3=7q_{33}+1\end{array}$$

之特解，得到
$$x_1=70,x_2=21,x_3=15$$
然后线性组合
$$x_p=70\times 2+21\times 3+15\times 2=233\text{\hspace{1em}(2)}$$

此便为原问题的一个特解。结合（1）与（2），便得到通解
$$x=x_p+x_h=233+105n,n\in \mathbb{Z}\text{\hspace{1em}(3)}$$
其中当 $n=-2$ 有最小正整数解 $x=23$。写到此处，笔者想起孔子说的：“吾道一以贯之。”

拉格朗日插值法，亦是韩信点兵思想之发扬。以下举一实例，用同样的想法写出拉格朗日插值多项式。

给定 $A(3,2),B(2,-1),C(-1,3)$ 三点，求过此三点的最低次多项式函数 $f(x)$。我们先求出三个较特别的二次函数：
$$\begin{array}{r}f1(x)：过(3,1),(2,0),(-1,0)\\ f2(x)：过(3,0),(2,1),(-1,0)\\ f3(x)：过(3,0),(2,0),(-1,1)\end{array}$$
然后设定
$$f(x)=2\cdot f_1(x)+(-1)\cdot f_2(x)+3\cdot f_3(x)$$
这样便有
$$\{\begin{array}{l}f(3)=2\cdot 1+0+0=2\\ f(2)=0+(-1)\cdot 1+0=-1\\ f(-1)=0+0+3\cdot 1=3\end{array}$$
即为所欲求之二次多项式函数。而每个 $f_i(x)$ 皆容易，因 $f_1(x)$ 过 $(2,0),(-1,0)$，设
$$f_1(x)=a(x-2)(x+1)\text{\hspace{1em}(4)}$$
代 $(3,1)$​ 得
$$1=a\cdot (3-2)(3+1)\Rightarrow a=\frac{1}{(3-2)(3+1)}$$
再把这个 $a$ 代回式子 (4) 得
$$f_1(x)=\frac{(x-2)(x+1)}{(3-2)(3+1)}$$
同样的流程，可解出
$$\begin{array}{rl}{f}_2(x)& =\frac{(x-3)(x+1)}{(2-3)(2+1)}\\ f_3(x)& =\frac{(x-2)(x-3)}{(-1-2)(-1-3)}\end{array}$$
便得到
$$f(x)=2\cdot \frac{(x-2)(x+1)}{(3-2)(3+1)}+(-1)\cdot \frac{(x-3)(x+1)}{(2-3)(2+1)}+3\cdot \frac{(x-2)(x-3)}{(-1-2)(-1-3)}$$
这就是拉格朗日插值法。