科数网
学习
高中数学
高中物理
微积分
线性代数
概率论
人工智能
赞助本站
在线教程
初等数论
初等数论(高中版)
拉格朗日插值法和孙子定理
日期:
2023-11-09 18:50
查看:
147
次
编辑
拉格朗日插值法和孙子定理
**拉格朗日插值法和孙子定理** 约在 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
)
赞助我们
0
篇笔记
写笔记
更多笔记
提交笔记