合成部門

合成除算を使用してをで割った商を求めるアニメーション。には項がないので、右から 4 番目の列にはゼロが含まれていることに注意してください。 $2x^{4}+3x^{2}+5x+1$ $x-2$ $x^{3}$

代数学において、合成除法は、長除法よりも記述量と計算量が少なく、多項式のユークリッド除法を手動で実行する方法です。

この方法は主に線形単項多項式による除算（ルフィニの定理として知られている）について教えられていますが、この方法は任意の多項式による除算に一般化できます。

合成除算の利点は、変数を書かずに計算できること、計算回数が少ないこと、長除算よりも紙のスペースを大幅に節約できることです。また、長除算の減算は最初に符号を切り替えることで加算に変換されるため、符号エラーを防ぐのに役立ちます。

通常の合成分割

最初の例は、単項線形分母のみを使用した合成除算です。 $xa$

{\frac {x^{3}-12x^{2}-42}{x-3}}

分子はと書くことができます。 $p(x)=x^{3}-12x^{2}+0x-42$

分母のゼロはです。 $g(x)$ $3$

の係数は、のゼロを左側にして次のように配置されます。 $p(x)$ $g(x)$

{\begin{array}{cc}{\begin{array}{r}\\3\\\end{array}}&{\begin{array}{|rrrr}\ 1&-12&0&-42\\&&&\\\hline \end{array}}\end{array}}

バーの後の最初の係数は最後の行に「ドロップ」されます。

{\begin{array}{cc}{\begin{array}{r}\\3\\\\\end{array}}&{\begin{array}{|rrrr}\color {blue}1&-12&0&-42\\&&&\\\hline \color {blue}1&&&\\\end{array}}\end{array}}

削除された数字はバーの前の数字と掛け合わされ、次の列に配置されます。

{\begin{array}{cc}{\begin{array}{r}\\\color {grey}3\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&\color {brown}3&&\\\hline \color {blue}1&&&\\\end{array}}\end{array}}

次の列で加算が実行されます。

{\begin{array}{cc}{\begin{array}{c}\\3\\\\\end{array}}&{\begin{array}{|rrrr}1&\color {green}-12&0&-42\\&\color {green}3&&\\\hline 1&\color {green}-9&&\\\end{array}}\end{array}}

前の 2 つの手順を繰り返すと、次の結果が得られます。

{\begin{array}{cc}{\begin{array}{c}\\3\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&3&-27&-81\\\hline 1&-9&-27&-123\end{array}}\end{array}}

ここで、最後の項 (-123) は剰余であり、残りは商の係数に対応します。

項は、剰余と結果の次数 0 から始まり、右から左へ次数が増加する形で記述されます。

{\begin{array}{rrr|r}1x^{2}&-9x&-27&-123\end{array}}

したがって、商と余りは次のようになります。

q(x)=x^{2}-9x-27

r(x)=-123

剰余定理による多項式の評価

上記の合成除算の形式は、一変数多項式を評価するための多項式剰余定理の文脈で有用である。要約すると、におけるの値は、を $p(x)$ $a$ $p(x)$ $xa.$

この方法で値を計算する利点は、単純な評価に比べて必要な乗算ステップが半分強で済むことです。別の評価戦略として、ホーナー法があります。

合成部門の拡大

この方法は、太字の変更によるわずかな修正のみで、任意の単項多項式による除算に一般化されます。次の例では表示されていない場合がありますが、除数も冗長係数で記述する必要があることに注意してください。( の場合のように) 前と同じ手順を使用して、次の除算を実行します。 $2x^{3}+0x^{2}-4x+8$

{\frac {x^{3}-12x^{2}-42}{x^{2}+x-3}}

ここでは係数のみに着目します。割られる多項式の係数を一番上に書きます。

{\begin{array}{|rrrr}\ 1&-12&0&-42\end{array}}

除数の係数を反転します。

{\begin{array}{rrr}-1x^{2}&-1x&+3\end{array}}

左端の最初の係数を除くすべての係数を右上がりの対角線で書き入れます(次の図を参照)。

{\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\end{array}}&{\begin{array}{|rrrr}\ 1&-12&0&-42\\&&&\\&&&\\\hline \end{array}}\end{array}}

符号が1 から -1 へ、および -3 から 3 へ変化していることに注意してください。バーの後の最初の係数を最後の行に「ドロップ」します。

{\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&&\\&&&\\\hline 1&&&\\\end{array}}\end{array}}

ドロップされた数字にバーの前の対角線を掛けて、結果のエントリをドロップされたエントリの 右斜めに配置します。

{\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&3&\\&-1&&\\\hline 1&&&\\\end{array}}\end{array}}

次の列で加算を実行します。

{\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&3&\\&-1&&\\\hline 1&-13&&\\\end{array}}\end{array}}

次の対角線で上部のエントリを通過するまで、前の 2 つの手順を繰り返します。

{\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&3&-39\\&-1&13&\\\hline 1&-13&16&\\\end{array}}\end{array}}

次に、残りの列を合計します。

{\begin{array}{cc}{\begin{array}{rr}\\&3\\-1&\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&-42\\&&3&-39\\&-1&13&\\\hline 1&-13&16&-81\\\end{array}}\end{array}}

棒の左側の項を数えます。2 つあるので、残りの項の次数は 1 となり、これが棒の下の右端の 2 つの項になります。区切りを縦棒でマークします。

{\begin{array}{rr|rr}1&-13&16&-81\end{array}}

項は、剰余と結果の両方について、次数 0 から始まり、右から左へ次数が増加する形で記述されます。

{\begin{array}{rr|rr}1x&-13&16x&-81\end{array}}

分割の結果は次のようになります。

{\frac {x^{3}-12x^{2}-42}{x^{2}+x-3}}=x-13+{\frac {16x-81}{x^{2}+x-3}}

非モニック因子の場合

少し努力すれば、拡張された手法は、単項式だけでなく任意の多項式にも適用できるようにさらに一般化できます。これを行う通常の方法は、除数をその先頭の係数 ( と呼びます) で割ることです。 $g(x)$

h(x)={\frac {g(x)}{a}}

次に、を除数として合成除算を使用し、その商をaで割って元の除算の商を取得します (余りは変わりません)。しかし、この方法では見苦しい小数点が生成されることが多く、後で削除されるため、エラーが発生しやすくなります。の係数を最初に減らさなくてもこれを行うことは可能です。 $h(x)$ $g(x)$

このような非単数除数で最初に長除算を実行するとわかるように、の係数は、「削除」された後、乗算される前にの先頭の係数で除算されます。 $f(x)$ $g(x)$

次の除算を実行して説明してみましょう。

{\frac {6x^{3}+5x^{2}-7}{3x^{2}-2x-1}}

わずかに変更された表が使用されます:

{\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&&\\&&&\\\hline &&&\\&&&\\\end{array}}\end{array}}

一番下の余分な行に注意してください。これは、「削除された」値をの先頭の係数(この場合は/3で示されます。の残りの係数とは異なり、この数値の符号は変更されないことに注意してください) で割って求めた値を書き込むために使用されます。 $g(x)$ $g(x)$

次に、の最初の係数は通常どおり削除されます。 $f(x)$

{\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&&\\&&&\\\hline 6&&&\\&&&\\\end{array}}\end{array}}

そして、削除された値は 3 で割られ、下の行に配置されます。

{\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&&\\&&&\\\hline 6&&&\\2&&&\\\end{array}}\end{array}}

次に、新しい（分割された）値を使用して、拡張された手法と同様に、上部の行を 2 と 1 の倍数で埋めます。

{\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&\\&4&&\\\hline 6&&&\\2&&&\\\end{array}}\end{array}}

次に 5 を削除し、その下の 4 を必須で追加して、答えを再度割ります。

{\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&\\&4&&\\\hline 6&9&&\\2&3&&\\\end{array}}\end{array}}

次に、3 を使用して上の行を埋めます。

{\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&3\\&4&6&\\\hline 6&9&&\\2&3&&\\\end{array}}\end{array}}

この時点で、3 番目の合計を取得した後、それを使用して上の行を埋めようとすると、右側から「落ちてしまう」ため、通常の合成除算と同様に、3 番目の合計が剰余の最初の係数になります。ただし、剰余の値は除数の先頭の係数で除算され ません。

{\begin{array}{cc}{\begin{array}{rrr}\\&1&\\2&&\\\\&&/3\\\end{array}}{\begin{array}{|rrrr}6&5&0&-7\\&&2&3\\&4&6&\\\hline 6&9&8&-4\\2&3&&\\\end{array}}\end{array}}

これで答えの係数を読み取ることができます。拡張合成除算と同様に、最後の 2 つの値 (2 は除数の次数) は剰余の係数であり、残りの値は商の係数です。

{\begin{array}{rr|rr}2x&+3&8x&-4\end{array}}

そして結果は

{\frac {6x^{3}+5x^{2}-7}{3x^{2}-2x-1}}=2x+3+{\frac {8x-4}{3x^{2}-2x-1}}

コンパクト拡張合成部門

ただし、上記の対角形式は、除数の次数が被除数の次数の半分を超えると、スペース効率が低下します。次の除算を考えてみましょう。

{\dfrac {a_{7}x^{7}+a_{6}x^{6}+a_{5}x^{5}+a_{4}x^{4}+a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}}{b_{4}x^{4}-b_{3}x^{3}-b_{2}x^{2}-b_{1}x-b_{0}}}

各積を正しい列に記述する限り、どの行に記述してもまったく問題ないことが容易にわかります。そのため、以下の除算に示すように、アルゴリズムは貪欲な戦略によってコンパクト化できます。

{\begin{array}{cc}{\begin{array}{rrrr}\\\\\\\\b_{3}&b_{2}&b_{1}&b_{0}\\\\&&&&/b_{4}\\\end{array}}{\begin{array}{|rrrr|rrrr}&&&&q_{0}b_{3}&&&\\&&&q_{1}b_{3}&q_{1}b_{2}&q_{0}b_{2}&&\\&&q_{2}b_{3}&q_{2}b_{2}&q_{2}b_{1}&q_{1}b_{1}&q_{0}b_{1}&\\&q_{3}b_{3}&q_{3}b_{2}&q_{3}b_{1}&q_{3}b_{0}&q_{2}b_{0}&q_{1}b_{0}&q_{0}b_{0}\\a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline a_{7}&q_{2}'&q_{1}'&q_{0}'&r_{3}&r_{2}&r_{1}&r_{0}\\q_{3}&q_{2}&q_{1}&q_{0}&&&&\\\end{array}}\end{array}}

以下にアルゴリズムの実行方法を説明します。このアルゴリズムには、非モニックな除数を除算する手順が含まれています。

被除数の係数をバーに書きます。
${\begin{array}{cc}{\begin{array}{|rrrrrrrr}\ a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline \end{array}}\end{array}}$
除数の最初の（先頭の）係数を無視し、各係数を反転してバーの左側に配置します。
${\begin{array}{cc}{\begin{array}{rrrr}b_{3}&b_{2}&b_{1}&b_{0}\\\end{array}}&{\begin{array}{|rrrrrrrr}\ a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline \end{array}}\end{array}}$
バーの左側に置かれた係数の数から、右端の列から始めて、バーの上にある被除数係数の数を数えます。次に、その列の左側と下の行に垂直バーを配置します。この垂直バーは、商と余りの区切りを示します。
${\begin{array}{cc}{\begin{array}{rrrr}b_{3}&b_{2}&b_{1}&b_{0}\\\\\end{array}}&{\begin{array}{|rrrr|rrrr}a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline &&&&&&&\\\end{array}}\end{array}}$
被除数の最初の係数をバーの下にドロップします。
${\begin{array}{cc}{\begin{array}{rrrr}b_{3}&b_{2}&b_{1}&b_{0}\\\\\end{array}}&{\begin{array}{|rrrr|rrrr}a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline a_{7}&&&&&&&\\\end{array}}\end{array}}$
- 前に除数/合計数を除数の先頭係数で割り、下の行に配置します (先頭係数が 1 の場合はこれを行う必要はありません)。
  この場合、インデックスは除数のインデックスを被除数から減算することによって選択されています。 $q_{3}={\dfrac {a_{7}}{b_{4}}}$ $3=7-4$
- 前に削除/合計された数 (または分割された削除/合計された数) を左側の各負の除数係数 (左端から開始) に掛けます。削除/合計された数が 0 の場合はスキップします。各積を後続の列の上に配置します。
  ${\begin{array}{cc}{\begin{array}{rrrr}\\b_{3}&b_{2}&b_{1}&b_{0}\\\\&&&&/b_{4}\\\end{array}}{\begin{array}{|rrrr|rrrr}&q_{3}b_{3}&q_{3}b_{2}&q_{3}b_{1}&q_{3}b_{0}&&&\\a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline a_{7}&&&&&&&\\q_{3}&&&&&&&\\\end{array}}\end{array}}$
次の列に対して列ごとの加算を実行します。この場合、。 $q_{2}'=q_{3}b_{3}+a_{6}$
${\begin{array}{cc}{\begin{array}{rrrr}\\b_{3}&b_{2}&b_{1}&b_{0}\\\\&&&&/b_{4}\\\end{array}}{\begin{array}{|rrrr|rrrr}&q_{3}b_{3}&q_{3}b_{2}&q_{3}b_{1}&q_{3}b_{0}&&&\\a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline a_{7}&q_{2}'&&&&&&\\q_{3}&&&&&&&\\\end{array}}\end{array}}$
前の 2 つの手順を繰り返します。縦棒の直前の数字で前の 2 つの手順を実行したら停止します。
1. させて。 $q_{2}={\dfrac {q_{2}'}{b_{4}}}$
  ${\begin{array}{cc}{\begin{array}{rrrr}\\\\b_{3}&b_{2}&b_{1}&b_{0}\\\\&&&&/b_{4}\\\end{array}}{\begin{array}{|rrrr|rrrr}&&q_{2}b_{3}&q_{2}b_{2}&q_{2}b_{1}&&&\\&q_{3}b_{3}&q_{3}b_{2}&q_{3}b_{1}&q_{3}b_{0}&q_{2}b_{0}&&\\a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline a_{7}&q_{2}'&q_{1}'&&&&&\\q_{3}&q_{2}&&&&&&\\\end{array}}\end{array}}$
2. させて。 $q_{1}={\dfrac {q_{1}'}{b_{4}}}$
  ${\begin{array}{cc}{\begin{array}{rrrr}\\\\\\b_{3}&b_{2}&b_{1}&b_{0}\\\\&&&&/b_{4}\\\end{array}}{\begin{array}{|rrrr|rrrr}&&&q_{1}b_{3}&q_{1}b_{2}&&&\\&&q_{2}b_{3}&q_{2}b_{2}&q_{2}b_{1}&q_{1}b_{1}&&\\&q_{3}b_{3}&q_{3}b_{2}&q_{3}b_{1}&q_{3}b_{0}&q_{2}b_{0}&q_{1}b_{0}&\\a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline a_{7}&q_{2}'&q_{1}'&q_{0}'&&&&\\q_{3}&q_{2}&q_{1}&&&&&\\\end{array}}\end{array}}$
3. させて。 $q_{0}={\dfrac {q_{0}'}{b_{4}}}$
  ${\begin{array}{cc}{\begin{array}{rrrr}\\\\\\\\b_{3}&b_{2}&b_{1}&b_{0}\\\\&&&&/b_{4}\\\end{array}}{\begin{array}{|rrrr|rrrr}&&&&q_{0}b_{3}&&&\\&&&q_{1}b_{3}&q_{1}b_{2}&q_{0}b_{2}&&\\&&q_{2}b_{3}&q_{2}b_{2}&q_{2}b_{1}&q_{1}b_{1}&q_{0}b_{1}&\\&q_{3}b_{3}&q_{3}b_{2}&q_{3}b_{1}&q_{3}b_{0}&q_{2}b_{0}&q_{1}b_{0}&q_{0}b_{0}\\a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline a_{7}&q_{2}'&q_{1}'&q_{0}'&r_{3}&&&\\q_{3}&q_{2}&q_{1}&q_{0}&&&&\\\end{array}}\end{array}}$
残りの列ごとの加算を後続の列に対して実行します (剰余を計算します)。
${\begin{array}{cc}{\begin{array}{rrrr}\\\\\\\\b_{3}&b_{2}&b_{1}&b_{0}\\\\&&&&/b_{4}\\\end{array}}{\begin{array}{|rrrr|rrrr}&&&&q_{0}b_{3}&&&\\&&&q_{1}b_{3}&q_{1}b_{2}&q_{0}b_{2}&&\\&&q_{2}b_{3}&q_{2}b_{2}&q_{2}b_{1}&q_{1}b_{1}&q_{0}b_{1}&\\&q_{3}b_{3}&q_{3}b_{2}&q_{3}b_{1}&q_{3}b_{0}&q_{2}b_{0}&q_{1}b_{0}&q_{0}b_{0}\\a_{7}&a_{6}&a_{5}&a_{4}&a_{3}&a_{2}&a_{1}&a_{0}\\\hline a_{7}&q_{2}'&q_{1}'&q_{0}'&r_{3}&r_{2}&r_{1}&r_{0}\\q_{3}&q_{2}&q_{1}&q_{0}&&&&\\\end{array}}\end{array}}$
水平バーの下の一番下の結果は多項式の係数 (商と剰余) です。商の係数は垂直バーの区切りの左側にあり、剰余の係数は右側にあります。これらの係数は、商と剰余の両方で次数 0 から始まり、右から左に向かって次数が増加するものとして解釈されます。

結果を解釈すると次のようになります。

${\dfrac {a_{7}x^{7}+a_{6}x^{6}+a_{5}x^{5}+a_{4}x^{4}+a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}}{b_{4}x^{4}-b_{3}x^{3}-b_{2}x^{2}-b_{1}x-b_{0}}}=q_{3}x^{3}+q_{2}x^{2}+q_{1}x+q_{0}+{\dfrac {r_{3}x^{3}+r_{2}x^{2}+r_{1}x+r_{0}}{b_{4}x^{4}-b_{3}x^{3}-b_{2}x^{2}-b_{1}x-b_{0}}}$

Python実装

次のスニペットは、任意の一変数多項式に対して Pythonで拡張合成除算を実装します。

def  expand_synthetic_division ( dividend ,  divisor ): 
"""拡張合成除算を使用した高速多項式除算。    非単項多項式でも機能します。    


    被除数と除数はどちらも多項式で、ここでは単に係数のリストです。
    例: x**2 + 3*x + 5 は [1, 3, 5] と表されます。
    """ 
    out  =  list (被除数)   # 被除数をコピーします。normalizer 
    =  divisor  [ 0 ] for 
    i  in  range  ( len (被除数) -  len  (除数) +  1  ) : 
        # 一般的な多項式の除算 (多項式が非単項式の場合) では、
        係数を
        除数の最初の係数で割って正規化する必要があります。out [ i ]  /=  normalizer

        coef  =  out [ i ] 
        if  coef  !=  0 :   # coef が 0 の場合は乗算しても無駄です
            # 合成除算では、除数の最初の係数は常にスキップされます。
            # これは、被除数係数を正規化するためにのみ使用されるためです
            for  j  in  range ( 1 ,  len ( divisor )): 
                out [ i  +  j ]  +=  - divisor [ j ]  *  coef

    # 結果の出力には商と余りの両方が含まれ、
    # 余りは除数のサイズです (余りは
    被除数で割ることができなかったため、必然的に除数と同じ次数になります)。そのため、
    この分離があるインデックスを計算し、商と余りを返します。separator = 1 - len ( divisor ) return out [ : Separator ], out [ Separator :] # 商と余りを返します。

参照

参考文献

Fan, Lianghuo (2003 年 6 月). 「合成除算の一般化と多項式の除算の一般定理」(PDF) . Mathematical Medley . 30 (1): 30–37. 2015 年 9 月 7 日時点のオリジナルからアーカイブ(PDF) 。
Li, Zhou (2009年1月). 「Short Division of Polynomials」(PDF) . College Mathematics Journal . 40 (1): 44–46. JSTOR 27646720. 2020年7月9日時点のオリジナルよりアーカイブ(PDF) 。

外部リンク

Goodman, Len ; Stover, Christopher & Weisstein, Eric W.「合成除算」。MathWorld。
ストーバー、クリストファー。「ルフィニの法則」。MathWorld。