最后更新: 2023-11-09 18:50 查看: 223 次反馈刷题

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

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

约在 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)$ 叫做同余方程组 ( $※)$ 的解. 在这个意义下, 同余方程组 (※)仅有一个解.
为了解同余方程组 ( $\%$, 我们首先建立拉格朗日插值公式.

由二次函数的知识知, 在平面上一定存在一条抛物线通过 $(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)$ 为任意多项式.
下面介绍一种更为一般的方法 一拉格朗日 0 插值法. 我们按如下步骤进行:
(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),
$$

其中

$$
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)} .
$$

通常, 我们把公式 (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)$.

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：一次同余方程

下一篇：孙子定理

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