最后更新: 2025-06-21 09:49 查看: 371 次纠错评论(0) 课件开VIP

拉格朗日插值与孙子定理

## 拉格朗日插值法和孙子定理

约在 2000 多年以前, 我国古代数学著作 《孙子算经》中提出了著名的 “物不知其数” 问题: “今有物不知其数, 三三数之余二,五五数之余三, 七七数之余二, 问物几何.” 答曰: “二十三.”

我国历史上还有很多人研究过这类问题, 其名称也多种多样.后来, 人们将这类问题的解法进一步发展和推广, 并称之为孙子定理, 在国外文献和教科书中称为 “中国剩余定理”.

设物数为 $x$, 那么 “物不知其数” 问题相当于解如下形式的方程组:

$$
\left\{\begin{array}{l}
x \equiv 2(\bmod 3), \\
x \equiv 3(\bmod 5), \\
x \equiv 2(\bmod 7) .
\end{array}\right. ...(※)
$$

这种方程组, 我们称为**同余方程组**.

如果存在正整数 $k$, 使得 ( $※$ ) 中每个同余式成立, 那么 $k$ 就是 “物不知其数” 问题的一个解.

容易检验, 当 $k$ 使得 (※)中每个同余式都成立时, 所有模 $3 \times 5 \times 7=105$ 同余于 $k$ 的整数,也使得 (※)中每个同余式成立. 反过来, 如果还有整数 $l$ 使得 (※)中每个同余式成立, 那么

$$
l \equiv k(\bmod 3), l \equiv k(\bmod 5), l \equiv k(\bmod 7),
$$

于是 $3|l-k, 5| l-k, 7 \mid l-k$. 这表明 $l-k$ 含有素因数 $3,5,7$, 从而 $3 \times 5 \times 7 \mid l-k$,即 $l \equiv k(\bmod 105)$.

通常, 我们把 $x \equiv k(\bmod 105)$ 叫做同余方程组 ( $※)$ 的解. 在这个意义下, 同余方程组 (※)仅有一个解.
为了解同余方程组 (※), 我们首先建立拉格朗日插值公式.

## 拉格朗日插值
问：能否求一个多项式$f(x)$ 使得$f(1)=1,f(-1)=3,f(2)=3$?

由二次函数的知识知, 在平面上一定存在一条抛物线通过 $(1,1),(-1,3),(2,3)$这三个点. 因此, 我们先假定 $f(x)=a x^2+b x+c$, 由题意, 得

$$
\left\{\begin{array}{l}
1=a+b+c, \\
3=a-b+c, \\
3=4 a+2 b+c .
\end{array}\right.
$$

解得, $a=1, b=-1, c=1$.
因此多项式 $f(x)=x^2-x+1$ 满足上述条件. 利用这个多项式, 我们可以写出所有满足条件的多项式

$$
f(x)=x^2-x+1+(x-1)(x+1)(x-2) h(x),
$$

其中 $h(x)$ 为任意多项式.
下面介绍一种更为一般的方法 一拉格朗日插值法. 我们按如下步骤进行:
(1) 求多项式 $p(x)$, 使 $p(1)=1, p(-1)=0, p(2)=0$;
(2) 求多项式 $q(x)$, 使 $q(1)=0, q(-1)=1, q(2)=0$;
(3) 求多项式 $r(x)$, 使 $r(1)=0, r(-1)=0, r(2)=1$;
(4) 作多项式 $f(x)=1 \times p(x)+3 \times q(x)+3 \times r(x)$, 它就是问题的一个解.
这里的多项式 $p(x), q(x)$ 与 $r(x)$ 好求吗?
如选取 $p(x)=c(x+1)(x-2)$, 其中 $c$ 为常数. 显然 $p(-1)=0, p(2)=0$. 再代人条件 $p(1)=1$, 可求得 $c$ 为 $(1+1)(1-2)$ 的倒数. 于是

$$
p(x)=\frac{(x+1)(x-2)}{(1+1)(1-2)}=-\frac{1}{2}\left(x^2-x-2\right) .
$$

同理可得

$$
\begin{aligned}
& q(x)=\frac{(x-1)(x-2)}{(-1-1)(-1-2)}=\frac{1}{6}\left(x^2-3 x+2\right), \\
& r(x)=\frac{(x-1)(x+1)}{(2-1)(2+1)}=\frac{1}{3}\left(x^2-1\right) .
\end{aligned}
$$

一般地, 设 $a, b, c$ 两两不同, 那么满足 $f(a)=e, f(b)=f, f(c)=g$ 的一个多项式 $f(x)$ 可由下面的公式给出:

$$
f(x)=e \cdot p(x)+f \cdot q(x)+g \cdot r(x), ...(I)
$$

其中

$$
p(x)=\frac{(x-b)(x-c)}{(a-b)(a-c)}, q(x)=\frac{(x-a)(x-c)}{(b-a)(b-c)}, r(x)=\frac{(x-a)(x-b)}{(c-a)(c-b)}  ...(II)
$$

通常, 我们把公式 (I) 和 (II) 叫做**拉格朗日插值公式**. 运用类似的方法, 同学们可将它推广到一般情形.

为了解同余方程组 (※) . 我们依照建立拉格朗日插值公式的想法, 按如下两个步骤进行:
$1^{\circ}$ 求整数 $p$, 使 $p \equiv 1(\bmod 3), p \equiv 0(\bmod 5), p \equiv 0(\bmod 7)$.
求整数 $q$, 使 $q \equiv 0(\bmod 3), q \equiv 1(\bmod 5), q \equiv 0(\bmod 7)$.
求整数 $r$, 使 $r \equiv 0(\bmod 3), r \equiv 0(\bmod 5), r \equiv 1(\bmod 7)$.
$2^{\circ}$ 作整数 $k=2 \times p+3 \times q+2 \times r$, 这个 $k$ 使得 $(※)$ 中每个同余式都成立.此时, $x \equiv k(\bmod 3 \times 5 \times 7)$ 就是同余方程组  (※) 的解.

如何求出整数 $p, q$ 和 $r$ 呢? 不妨以求整数 $p$ 为例.
由于 $p \equiv 0(\bmod 5), p \equiv 0(\bmod 7)$, 故 $5|p, 7| p$, 于是 $p=5 \times 7 \times c$, 其中 $c$ 为某个整数. 再由 $p \equiv 1(\bmod 3)$ 知, 整数 $c$ 满足: $5 \times 7 \times c \equiv 1(\bmod 3)$. 而 $5 \times 7 \equiv-1(\bmod 3)$,于是 $-c \equiv 1(\bmod 3)$, 进而 $c \equiv-1(\bmod 3)$. 若选取 $c=2$, 则 $p=70$.

用类似的方法, 我们计算得 $q=21, r=15$. 作整数 $k=2 \times 70+3 \times 21+2 \times 15=233$,于是同余方程组 $(※)$ 的解为 $x \equiv 233 \equiv 23(\bmod 105)$.

从前面 $p$ 的计算过程可以看出，步骤（1）中整数 $p, q$ 和 $r$ 的选取是不惟一的，那么 $p, q$ 和 $r$ 的不同选取方式会导致解的不同吗？为什么？你能根据上面的解答来解释程大位的算法口诀吗？

## 孙子定理
一般地, 我们有下面的结论.
孙子定理 设 $a, b, c$ 为两两互素的正整数, $e, f, g$ 为任意整数, 则同余方程组

$$
\left\{\begin{array}{l}
x \equiv e(\bmod a), \\
x \equiv f(\bmod b), \\
x \equiv g(\bmod c)
\end{array}\right.
$$

仅有一解: $x \equiv e b c c_1+f a c c_2+g a b c_3(\bmod a b c)$, 其中 $c_1, c_2, c_3$ 分别为满足同余式: $b c c_1 \equiv 1(\bmod a), a c c_2 \equiv 1(\bmod b), a b c_3 \equiv 1(\bmod c)$ 的整数.
运用类似的方法, 同学们可将孙子定理推广到更一般的情形.

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：一次同余方程

下一篇：弃九验算法

本文对您是否有用？有用 (0) 无用 (0)