43311 多項式除法的商式和餘式
多項式除法的商式和餘式

中陳建燁先生給出了如下的「多項式除法基本定理」:

引理1 (見): 設 $p_1, p_2, \ldots, p_m$ 兩兩不等, 且 $n\ge m\ge 2$, 則 $$x^n=\left[\prod_{1\le i\le m}(x-p_i)\right]\cdot \left[\sum_{j=0}^{n-m}h_{n-m-j}(p)x^j\right] +\sum_{j=1}^m p_j^n\frac{\prod\limits_{1\le i\le m,i\not=j}(x-p_i)}{\prod\limits_{1\le i\le m,i\not=j}(p_j-p_i)}.$$ 其中 $h_k(p)=\sum\limits_{\lambda_1+\lambda_2+\cdots+\lambda_m=k,\atop \lambda_1,\lambda_2,\ldots,\lambda_m\ge 0}(p_1^{\lambda_1}p_2^{\lambda_2}\cdots p_m^{\lambda_m})$, 即 $h_k(p)$是 $p_1,p_2,\ldots, p_m$ 的 $k$ 次完全齊次對稱多項式。

注: 為表述方便, 本文將文 中的 $h_k(p_1,p_2,\ldots, p_m)$ 簡寫為 $h_k(p)$, 並將商式改為按 $x$ 的升冪排列。

本文探求一般的 $n$ 次多項式 $f(x)=\sum\limits_{i=0}^n a_ix^i$ 除以 $\prod\limits_{1\le i\le m}(x-p_i)$ 所得的商式 $q(x)$ 和餘式 $r(x)$, 即: $$f(x)=q(x) \prod\limits_{1\le i\le m}(x-p_i)+r(x).$$ 其中 $q(x)$ 是 $n-m$ 次多項式 $(n\ge m)$, $r(x)$ 是次數不超過 $m-1$ 的多項式。

本文還要用到文 中的 $h-L$ 轉換公式:

引理2 (見): $m\ge 2$, $k\ge 0$ 且 $k\in N$, $L_k(p)=\sum\limits_{i=1}^m \dfrac{p_i^k}{\prod\limits_{1\le s\le m,s\not=i}(p_i-p_s)} $, 則: $$h_k(p)=L_{k+m-1}(p).$$

一、求商式 $q(x)$

按文 的思路, 要求 $q(x)$, $r(x)$, 只需把 $f(x)$ 的各項都除以 $\prod\limits_{1\le i\le m}(x-p_i)$ 找到商式和餘式, 再分別求和。

對於商式 $q(x)$, 只需考慮 $f(x)$ 中次數不低於 $m$ 的項「$a_mx^m$, $a_{m+1}x^{m+1} $, $\ldots$, $a_nx^n$」 所產生的商式即可。 因此我們有必要將 $f(x)$ 拆成兩部分, 即: \begin{equation} f(x)=\sum_{i=0}^n a_ix^i=u(x)+v(x),\ \hbox{其中}\ u(x)=\sum_{i=m}^n a_ix^i,\quad v(x)=\sum_{i=0}^{m-1}a_ix^i.\label{1} \end{equation}

另外, 本文的推導中需要截取 $f(x)$ 中的某些連續的項, 因此我們設: \begin{equation} u_k(x)=\sum_{i=k}^n a_ix^i\qquad (k=m,m+1,\ldots,n).\label{2} \end{equation}

注: \eqref{2} 式中的 $u_m(x)$ 即是 \eqref{1} 式中的 $u(x)$.

由 $u(x)=u_m(x)=\sum\limits_{i=m}^n a_ix^i$, 結合引理 1 可知商式: \begin{eqnarray} q(x)&=&\sum\limits_{i=m}^n \left[a_i \sum_{j=0}^{i-m} h_{i-m-j}(p)x^j\right] =\sum\limits_{i=m}^n \sum_{j=0}^{i-m} [a_ih_{i-m-j}(p)x^j]\nonumber\\ &=&\sum_{j=0}^{n-m}\sum_{i=m+j}^{n}a_ih_{i-m-j}(p)x^j. %=\sum_{j=0}^{n-m}x^j\sum_{i=m+j}^{n}a_ih_{i-m-j}(p). \label{3} \end{eqnarray}

\eqref{3} 式給出的 $q(x)$ 的運算式中含有係數 $a_i$ 和完全齊次對稱多項式 $h_{i-m-j}(p)$, 顯得不夠簡潔。 下面我們給出 $q(x)$ 的另一種表達形式。

由 \eqref{3} 式和引理 2, 在 \eqref{3} 式中令 $j=0$, 可得商式 $q(x)$ 中的常數項為: \begin{eqnarray*} \sum_{i=m}^n a_ih_{i-m}(p)&=&\sum_{i=m}^n a_iL_{i-1}(p)=\sum_{i=m}^n\left[a_i\sum_{s=1}^m\frac{p_s^{i-1}}{\prod\limits_{1\le k\le m,k\not=s}(p_s-p_k)}\right]\\ &=&\sum_{i=m}^{n}\sum_{s=1}^{m}\frac{a_ip_s^{i-1}}{\prod\limits_{1\le k\le m,k\not=s}(p_s-p_k)} =\sum_{i=m}^{n}\sum_{s=1}^{m}\frac{a_ip_s^{i}}{p_s\cdot\prod\limits_{1\le k\le m,k\not=s}(p_s-p_k)}\\ &=&\sum_{s=1}^{m}\sum_{i=m}^{n}\frac{a_ip_s^{i}}{p_s\cdot\prod\limits_{1\le k\le m,k\not=s}(p_s-p_k)} =\sum_{s=1}^{m}\frac{\sum\limits_{i=m}^{n}a_ip_s^{i}}{p_s\cdot\prod\limits_{1\le k\le m,k\not=s}(p_s-p_k)}. \end{eqnarray*} 結合 \eqref{2} 式可知: 上式$=\sum\limits_{s=1}^{m}\dfrac{u_m(p_s)}{p_s\cdot\prod\limits_{1\le k\le m,k\not=s}(p_s-p_k)}$.

同理, 在 \eqref{3} 式中令 $j=1$, 可得商式 $q(x)$ 中 $x$ 的係數為: \begin{eqnarray*} \sum_{i=m+1}^n a_ih_{i-m-1}(p)&=&\sum_{i=m+1}^n a_iL_{i-2}(p)=\sum_{i=m+1}^n\left[a_i\sum_{s=1}^m \frac{p_s^{i-2}}{\prod\limits_{1\le k\le m,k\not=s}(p_s-p_k)}\right]\\ &=&\sum_{i=m+1}^{n}\sum_{s=1}^{m}\frac{a_ip_s^{i-2}}{\prod\limits_{1\le k\le m,k\not=s}(p_s-p_k)} =\sum_{i=m+1}^{n}\sum_{s=1}^{m}\frac{a_ip_s^{i}}{p_s^2\cdot\prod\limits_{1\le k\le m,k\not=s}(p_s-p_k)}\\ &=&\sum_{s=1}^{m}\sum_{i=m+1}^{n}\frac{a_ip_s^{i}}{p_s^2\cdot \prod\limits_{1\le k\le m,k\not=s}(p_s-p_k)} =\sum_{s=1}^{m}\frac{\sum\limits_{i=m+1}^{n}a_ip_s^{i}}{p_s^2\cdot \prod\limits_{1\le k\le m,k\not=s}(p_s-p_k)}\\ &=&\sum_{s=1}^{m}\frac{u_{m+1}(p_s)}{p_s^2\cdot \prod\limits_{1\le k\le m,k\not=s}(p_s-p_k)}. \end{eqnarray*} 一般地, 可推得商式 $q(x)$ 中 $x^j$ 的係數為: $$\sum_{s=1}^{m}\frac{u_{m+j}(p_s)}{p_s^{j+1}\cdot \prod\limits_{1\le k\le m,k\not=s}(p_s-p_k)}\quad (j=0,1,\ldots,n-m).$$ 因此, 我們得到了 \eqref{3} 式的如下等價形式: \begin{equation} q(x)=\sum_{j=0}^{n-m}\sum_{i=1}^m \frac{u_{m+j}(p_i)}{p_i^{j+1}\cdot \prod\limits_{1\le k\le m,k\not=i}(p_i-p_k)}x^j.\label{4} \end{equation}

二、求餘式 $r(x)$

由引理 1 知: $f(x)$ 的第一部分 $u(x)$ 除以 $\prod\limits_{1\le i\le m} (x-p_i)$ 的餘式為: $$\sum_{j=1}^m u(p_j)\dfrac{\prod\limits_{1\le i\le m,i\not=j} (x-p_i)}{\prod\limits_{1\le i\le m,i\not=j} (p_j-p_i)}.$$ 因此由 \eqref{1} 式知餘式 $$r(x)=\sum_{j=1}^m u(p_j)\dfrac{\prod\limits_{1\le i\le m,i\not=j} (x-p_i)}{\prod\limits_{1\le i\le m,i\not=j} (p_j-p_i)}+v(x).$$

注意到 $v(x)$ 和 $\sum\limits_{j=1}^m v(p_j)\dfrac{\prod\limits_{1\le i\le m,i\not=j} (x-p_i)}{\prod\limits_{1\le i\le m,i\not=j} (p_j-p_i)}$ 次數都不超過 $m-1$, 而它們在 $x=p_1, p_2, \ldots, p_m$ 處的值都分別相等, 因此 $$v(x)\equiv \sum\limits_{j=1}^m v(p_j)\dfrac{\prod\limits_{1\le i\le m,i\not=j} (x-p_i)}{\prod\limits_{1\le i\le m,i\not=j} (p_j-p_i)}.$$ 所以 \begin{equation} r(x)=\sum\limits_{j=1}^m [u(p_j)+v(p_j)]\dfrac{\prod\limits_{1\le i\le m,i\not=j} (x-p_i)}{\prod\limits_{1\le i\le m,i\not=j} (p_j-p_i)} =\sum\limits_{j=1}^m f(p_j)\dfrac{\prod\limits_{1\le i\le m,i\not=j} (x-p_i)}{\prod\limits_{1\le i\le m,i\not=j} (p_j-p_i)} .\label{5} \end{equation}

由多項式插值理論知, \eqref{5} 式有如下等價形式: \begin{equation} r(x)=f(p_1)+c_1(x-p_1)+c_2(x-p_1)(x-p_2)+\cdots+c_{m-1}\prod_{j=1}^{m-1}(x-p_j).\label{6} \end{equation} 其中 $c_j$ 是多項式 $f(x)$ 關於插值點 $p_1,p_2,\ldots,p_j$ 的 $j$ 階差商, $c_j$ 有如下計算公式: $$c_j=\sum_{i=1}^{j+1}\frac{f(p_i)}{\prod\limits_{1\le k\le j+1,k\not=i} (p_i-p_k)}\qquad (j=1,2,3,\ldots,m-1).$$

注: 由文 知 \eqref{5} 式是多項式 $f(x)$ 關於插值點 $p_1,p_2,\ldots,p_m$ 的次數不超過 $m-1$ 的 Lagrange 插值多項式, 而 \eqref{6} 式是 $f(x)$ 在相同插值點處的次數不超過 $m-1$ 的 Newton 插值多項式。 而兩者在插值點 $p_1, p_2, \ldots, p_m$ 處的值都分別相等, 因此這兩個多項式是恒等的。

三、結果與實例

綜合第一、 二部分中的結果, 我們得到:

定理: 設 $p_1, p_2, \ldots, p_m$ 兩兩不等, $n\ge m\ge 2$, $h_k(p)$ 是 $p_1,p_2,\ldots,p_m$ 的 $k$ 次完全齊次對稱多項式。 多項式 $f(x)=\sum\limits_{i=0}^n a_ix^i$, ($a_n\not=0$), 而 $u_k(x)=\sum\limits_{i=k}^na_ix^i$, ($k=m, m+1,\ldots,n$), 則 $f(x)$ 除以多項式 $\prod\limits_{1\le i\le m} (x-p_i)$ 的商式 $q(x)$ 由 \eqref{3} 式或 \eqref{4} 式確定, 而餘式 $r(x)$ 由 \eqref{5} 式或 \eqref{6} 式確定。

下面我們舉一個例子來驗證這個定理中的 \eqref{4}、 \eqref{5} 兩式。

設 $f(x)=x^6+2x^5+3x^4+4x^3+5x^2+6x+7$, $\prod\limits_{1\le i\le m}(x-p_i)=x(x+1)(x+2)$, 這裡 $n=6$, $m=3$. 因 $\dfrac{u_3(x)}{x}=x^5+2x^4+3x^3+4x^2=x^2(x^3+2x^2+3x+4)$, 所以 $$\frac{u_3(0)}{0}=0 ,\quad \frac{u_3(-1)}{-1}=2 ,\quad \frac{u_3(-2)}{-2}=-8.$$

注: $\dfrac{u_3(0)}{0}$ 是將 $x=0$ 代入多項式 $x^5+2x^4+3x^3+4x^2$ 進行計算, 是有意義的(參看 \eqref{4} 式的推導過程)。 $$\hbox{而}\quad \prod_{1\le k\le 3,k\not=1}(p_1-p_k)=2 , \quad \prod_{1\le k\le 3,k\not=2}(p_2-p_k)=-1, \quad \prod_{1\le k\le 3,k\not=3}(p_3-p_k)=2 .$$ 所以商式中常數項為: $$\sum_{i=1}^{3}\frac{u_3(p_i)}{p_i\prod\limits_{1\le k\le 3,k\not=i} (p_i-p_k)}=\frac 02+\frac 2{-1}+\frac{-8}2=-6.$$ 因 $\dfrac{u_4(x)}{x^2}=x^4+2x^3+3x^2=x^2(x^2+2x+3)$, 所以 $$\dfrac{u_4(0)}{0}=0,\quad \dfrac{u_4(-1)}{(-1)^2}=2,\quad \dfrac{u_4(-2)}{(-2)^2}=12.$$ 所以商式中 $x$ 的係數為: $$\sum_{i=1}^{3}\frac{u_4(p_i)}{p_i^2\prod\limits_{1\le k\le 3,k\not=i} (p_i-p_k)}=\frac 02+\frac 2{-1}+\frac{12}2=4.$$

同理, 商式中 $x^2$ 的係數為 $\sum\limits_{i=1}^{3}\dfrac{u_5(p_i)}{p_i^3\prod\limits_{1\le k\le 3,k\not=i} (p_i-p_k)}=-1$.
$x^3$ 的係數為 $\sum\limits_{i=1}^{3}\dfrac{u_6(p_i)}{p_i^4\prod\limits_{1\le k\le 3,k\not=i} (p_i-p_k)}=1$.

結合 \eqref{4} 式即知商式 $$q(x)=x^3-x^2+4x-6 .$$ 而由 \eqref{5} 式知餘式 \begin{eqnarray*} r(x)&=&7\times\frac{(x+1)(x+2)}{2}+4\times \frac{x(x+2)}{-1}+31\times\frac{x(x+1)}{2}\\ &=&15x^2+18x+7. \end{eqnarray*} 容易驗證: 上述結果與多項式做長除法時的結果是一致的。

參考資料

陳建燁。 商式定理。 數學傳播季刊, 41(4), 78-88, 2017。 喻文健。 數值分析與算法。 北京市:清華大學出版社, 214-217, 2012。

---本文作者任教中國重慶市長壽龍溪中學---