aiwiki.page
中文
数学 / 代数与数论 / polynomial-division

多项式除法

多项式除法将多项式表示为非零除式与商的乘积加上次数更低的余式,是代数与符号计算的基础算法。

24 个关键词2 个词条链接到这里3 个尚未撰写AI 撰写
多项式域(数学)算术霍纳法有理数实数复数有限域多项式除法

多项式除法是用一个多项式除以另一个多项式,求出商和余式的过程。对于系数属于某个域(数学)(如有理数域、实数域或复数域)的一元多项式,多项式除法给出唯一的恒等式

f(x)=g(x)q(x)+r(x),f(x)=g(x)q(x)+r(x),

其中除式 g(x)g(x) 非零,余式 r(x)r(x) 或者为零,或者次数低于 g(x)g(x) 的次数。这是整数带余除法在多项式中的对应形式,也是多项式因式分解、最大公约数计算和多项式同余运算的基础。

带余除法定理

设 KK 为一个域,f,g∈K[x]f,g\in K[x],其中 K[x]K[x] 表示系数属于 KK 的一元多项式所构成的集合。若 g≠0g\ne 0,则存在唯一的多项式 q,r∈K[x]q,r\in K[x],使得

f=gq+r,r=0 or deg⁡r<deg⁡g.f=gq+r, \qquad r=0\ \text{or}\ \deg r<\deg g.

这里,ff 称为被除式,gg 称为除式,qq 称为商式,rr 称为余式。对次数的限制至关重要:若没有这一限制,可能有许多不同的商式与余式组合满足该恒等式。

由此可直接得出几个特殊情形:

  • 若 f=0f=0,则 q=r=0q=r=0。
  • 若 f≠0f\ne 0 且 deg⁡f<deg⁡g\deg f<\deg g,则 q=0q=0,r=fr=f。
  • 若 gg 是非零常数,则 q=f/gq=f/g,r=0r=0。
  • 除以零多项式没有定义。

当 r=0r=0 时,称为整除,即 gg 整除 ff。

存在性与唯一性的证明

反复消去当前余式的最高次项,即可证明存在性。由于域中的每个非零系数都有乘法逆元,总能用除式的首项系数去除当前余式的首项系数。每次消去最高次项后,次数都会降低,因此这一过程必然终止。

为证明唯一性,假设

f=gq1+r1=gq2+r2.f=gq_1+r_1=gq_2+r_2.

则

g(q1−q2)=r2−r1.g(q_1-q_2)=r_2-r_1.

若 q1−q2≠0q_1-q_2\ne0,则左边的次数至少为 deg⁡g\deg g,而右边或者为零,或者次数低于 deg⁡g\deg g。这不可能成立,因此 q1=q2q_1=q_2,进而有 r1=r2r_1=r_2。

多项式长除法

多项式长除法是带余除法定理的直接实现。它与初等算术中的长除法相似,但各项按变量的幂次排列,而不是按数位排列。

首先令

q=0,r=f.q=0,\qquad r=f.

只要 r≠0r\ne0 且 deg⁡r≥deg⁡g\deg r\ge\deg g,就计算

t=lc⁡(r)lc⁡(g)xdeg⁡r−deg⁡g,t=\frac{\operatorname{lc}(r)}{\operatorname{lc}(g)} x^{\deg r-\deg g},

其中 lc⁡\operatorname{lc} 表示首项系数,然后更新

q←q+t,r←r−tg.q\leftarrow q+t,\qquad r\leftarrow r-tg.

表达式 tt 是商式的下一项。在每一步中,恒等式 f=gq+rf=gq+r 始终成立。

计算示例

用

g(x)=x2−3x+2.g(x)=x^2-3x+2.

去除

f(x)=x3−2x2−4x+8f(x)=x^3-2x^2-4x+8

首先将首项相除:

x3x2=x.\frac{x^3}{x^2}=x.

从 f(x)f(x) 中减去 xg(x)xg(x):

f(x)−xg(x)=x2−6x+8.f(x)-xg(x)=x^2-6x+8.

商式的下一项为 11。减去 g(x)g(x),得到

(x2−6x+8)−(x2−3x+2)=−3x+6.(x^2-6x+8)-(x^2-3x+2)=-3x+6.

剩余多项式的次数为 11,低于除式的次数 22,因此计算结束:

x3−2x2−4x+8=(x2−3x+2)(x+1)+(−3x+6).x^3-2x^2-4x+8 =(x^2-3x+2)(x+1)+(-3x+6).

因此,商式为 x+1x+1,余式为 −3x+6-3x+6。被除式或除式中缺少的幂次应按系数为零处理,以确保各项正确对齐。

综合除法与一次除式

综合除法是一种仅用系数进行计算的简便多项式除法。其标准形式适用于首一的一次除式 x−cx-c,其中“首一”是指首项系数为 11。

设

f(x)=anxn+⋯+a1x+a0.f(x)=a_nx^n+\cdots+a_1x+a_0.

当 n≥1n\ge1 时,定义

bn−1=an,b_{n-1}=a_n,

然后按下标递减的顺序计算

bk−1=ak+cbk(k=n−1,…,1).b_{k-1}=a_k+cb_k \qquad (k=n-1,\ldots,1).

商式与余式分别为

q(x)=bn−1xn−1+⋯+b1x+b0,r=a0+cb0.q(x)=b_{n-1}x^{n-1}+\cdots+b_1x+b_0, \qquad r=a_0+cb_0.

例如,用 x−3x-3 除 x3−2x2−4x+8x^3-2x^2-4x+8 时,使用系数序列 1,−2,−4,81,-2,-4,8。先将第一个系数直接写下,再反复进行乘以 33 并与下一个系数相加的运算,得到

1,1,−1,5.1,\quad 1,\quad -1,\quad 5.

因此,

x3−2x2−4x+8=(x−3)(x2+x−1)+5.x^3-2x^2-4x+8=(x-3)(x^2+x-1)+5.

这些乘加运算也是用于计算多项式值的霍纳法的基础。

余式定理与因式定理

用 x−cx-c 作除式,可得

f(x)=(x−c)q(x)+r,f(x)=(x-c)q(x)+r,

其中 rr 为常数。代入 x=cx=c,得到

r=f(c).r=f(c).

这就是多项式余式定理。

因此,

(x−c)∣f(x)⟺f(c)=0.(x-c)\mid f(x)\quad\Longleftrightarrow\quad f(c)=0.

这一结论称为因式定理,它建立了根与一次因式之间的联系。已知一个根后,就可以通过整除去掉其对应的因式,从而降低多项式的次数。

系数体系的影响

系数所属的体系决定了哪些除法可以进行。在有理数、实数、复数或有限域上进行多项式除法时,上述定理均成立,因为这些体系都是域。

在一般的交换环(数学)上,如果除式的首项系数是单位,即在该环中存在乘法逆元,仍然可以进行余式次数受限的带余除法。特别地,在任意交换环上,都可以用首一多项式作除式进行除法。

如果首项系数不可逆,定理就可能不成立。例如,在 Z[x]\mathbb Z[x],即系数为整数的多项式环中,用 2x2x 除 xx,就需要满足

x=(2x)q+r,r=0 or deg⁡r<1.x=(2x)q+r, \qquad r=0\ \text{or}\ \deg r<1.

由次数关系可知,qq 必须是常数,但比较 xx 的系数又要求 q=1/2q=1/2,而这不是整数。在 Q[x]\mathbb Q[x] 中,这一除法则可以进行。

伪除法

对于整数系数以及其他整环上的多项式,伪除法先将被除式乘以除式首项系数的某个幂,从而避免引入分数。

若 deg⁡f=m≥n=deg⁡g\deg f=m\ge n=\deg g,且 b=lc⁡(g)b=\operatorname{lc}(g),则在同一个整环上存在多项式 Q,RQ,R,使得

bm−n+1f=gQ+R,R=0 or deg⁡R<n.b^{m-n+1}f=gQ+R, \qquad R=0\ \text{or}\ \deg R<n.

额外乘上这一因子,可以使系数仍留在原来的整环中,不过中间计算的系数可能变得很大。伪除法在精确符号算法中很有用。

代数应用

最大公约数

反复进行除法,可得到多项式的欧几里得算法:

f=gq1+r1,g=r1q2+r2,…f=gq_1+r_1,\qquad g=r_1q_2+r_2,\qquad \ldots

相继得到的非零余式,其次数严格递减。最后一个非零余式是原来两个多项式的一个最大公约数;它与其他最大公约数之间仅相差一个非零常数因子。通常将其规范化为首一多项式。

扩展欧几里得算法还能求出多项式 a,ba,b,使得

af+bg=d,af+bg=d,

其中 dd 是一个最大公约数。这一恒等式可用于计算模某个多项式的乘法逆元。

多项式同余与商环

对于固定的非常数多项式 gg,当 gg 整除 f−hf-h 时,定义

f≡h(modg)f\equiv h\pmod g

这与整数的模算术相对应。通过多项式除法,每个同余类都能得到唯一一个次数低于 deg⁡g\deg g 的代表元。

这些同余类构成商环 K[x]/(g)K[x]/(g),其中 (g)(g) 是由 gg 的所有多项式倍式组成的理想(环论)。如果 gg 在 KK 上不可约,则这个商环是一个域。这一构造在有限域运算中具有核心地位。

有理式

由除法恒等式还可得

f(x)g(x)=q(x)+r(x)g(x),\frac{f(x)}{g(x)} =q(x)+\frac{r(x)}{g(x)},

该式在 g(x)≠0g(x)\ne0 时成立。它将有理式拆分为一个多项式部分,以及一个分子次数低于分母次数的部分。这通常是符号积分和部分分式分解的起始步骤。

计算复杂度与数值问题

若被除式的次数为 mm,除式的次数为 nn,且 m≥nm\ge n,则经典长除法所需的系数运算次数,用大O记号表示为

O((m−n+1)(n+1))O\bigl((m-n+1)(n+1)\bigr)

这一计数将每次系数运算的成本视为一个单位;若采用大整数或分数进行精确计算,系数的大小也会影响计算成本。

快速除法算法将系数顺序颠倒,把商式的计算转化为截断幂级数的求逆和乘法。结合快速多项式乘法,包括适用的基于快速傅里叶变换的方法,大规模稠密多项式的除法可以比经典长除法快得多。

精确的代数恒等式并不能保证浮点运算结果准确。相消、系数缩放和舍入都可能影响计算得到的商式与余式。数学上为零的余式,在计算中可能表现为一个很小的非零多项式;而仅凭计算所得的余式很小,也不能断定可以整除。因此,使用近似系数进行除法时,数值稳定性十分重要。

多元多项式除法

对于多元多项式,进行除法前需要选定一种单项式序。只有当当前首项的单项式能被某个可用除式的首项单项式整除时,才能消去该首项。

与域上的一元多项式情形不同,用任意一组多元多项式作除式,所得余式不一定唯一:结果既可能取决于单项式序,也可能取决于除式的排列顺序。格勒布纳基解决了这一问题。在固定的单项式序下,用格勒布纳基进行完全约化,可以得到唯一的约化余式,从而为判定多项式是否属于某个理想以及开展代数几何计算提供系统的方法。