多項式の長除算

代数学において、多項式長除法は、多項式を同じ次数またはより低い次数の別の多項式で割るアルゴリズムであり、長除法と呼ばれるよく知られた算術技法の一般化版です。複雑な除算問題をより小さな問題に分割するため、手作業で簡単に実行できます。多項式長除法は、多項式のユークリッド除法を実装するアルゴリズムです。2つの多項式A（被除数）とB（除数）から、 Bが0でない場合、商Qと剰余Rが生成されます。

A = BQ + R、

そして、R = 0 であるか、 Rの次数がBの次数より低いかのいずれかである。これらの条件は QとR を一意に定義する。R = 0 の結果は、多項式 A が B を因数として持つ場合のみ発生する。したがって、長除法は、ある多項式が別の多項式を因数として持つかどうかを判定し、持つ場合はそれを因数分解する手段となる。

場合によっては、合成除算と呼ばれる省略形を使用すると、特に除数が線形多項式である場合に、記述量と計算量が少なくなり、処理が速くなることがあります。

多項式の長除算は、多項式の係数が同じ体に属している限り可能です。つまり、非ゼロ要素による除算は常に可能です。体の例としては、有理数、実数、複素数などがあります。

例

被除数を除数で割ったときの商と余りを求めます。 $(x^{3}-2x^{2}-4)$ $(x-3)$

まず、被除数は次のように書き直されます。

x^{3}-2x^{2}+0x-4.

商と余りは次のようにして決定できます。

被除数の最初の項を、除数の最大の項（つまりxの最大のべき乗を持つ項、この場合はx）で割ります。結果をバーの上に置きます（x ³ ÷ x = x ²）。
${\begin{array}{l}{\color {White}x-3\ )\ x^{3}-2}x^{2}\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\end{array}}$
除数に先ほど得た結果（最終的な商の最初の項）を掛けます。結果を被除数の最初の2項（ $x 2 \cdot (x - 3) = x 3 - 3 x 2$ ）の下に書きます。
${\begin{array}{l}{\color {White}x-3\ )\ x^{3}-2}x^{2}\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\\{\color {White}x-3\ )\ }x^{3}-3x^{2}\end{array}}$
得られた積を元の被除数の適切な項から減算し (マイナス記号の付いたものを減算することは、プラス記号の付いたものを加算することと同じであることに注意してください)、その結果を下に書きます $(x 3 - 2 x 2) - (x 3 - 3 x 2) = -2 x 2 + 3 x 2 = x 2$ 次に、次の項を被除数から「下げます」。
${\begin{array}{l}{\color {White}x-3\ )\ x^{3}-2}x^{2}\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\\{\color {White}x-3\ )\ }{\underline {x^{3}-3x^{2}}}\\{\color {White}x-3\ )\ 0x^{3}}+{\color {White}}x^{2}+0x\end{array}}$
前の 3 つの手順を繰り返しますが、今回は被除数として先ほど書き込んだ 2 つの項を使用します。
${\begin{array}{r}x^{2}+{\color {White}1}x{\color {White}{}+3}\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\\{\underline {x^{3}-3x^{2}{\color {White}{}+0x-4}}}\\+x^{2}+0x{\color {White}{}-4}\\{\underline {+x^{2}-3x{\color {White}{}-4}}}\\+3x-4\\\end{array}}$
手順 4 を繰り返します。今回は、「ダウンさせる」ものは何もありません。
${\begin{array}{r}x^{2}+{\color {White}1}x+3\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\\{\underline {x^{3}-3x^{2}{\color {White}{}+0x-4}}}\\+x^{2}+0x{\color {White}{}-4}\\{\underline {+x^{2}-3x{\color {White}{}-4}}}\\+3x-4\\{\underline {+3x-9}}\\+5\end{array}}$

棒グラフの上の多項式は商q ( x )であり、余りの数値(5)は余りr ( x )である。

{x^{3}-2x^{2}-4}=(x-3)\,\underbrace {(x^{2}+x+3)} _{q(x)}+\underbrace {5} _{r(x)}

算術の長除算アルゴリズムは上記のアルゴリズムと非常に似ており、変数x が(10 を基数として) 特定の数値 10 に置き換えられます。

擬似コード

このアルゴリズムは、次のように擬似コードで表すことができます。ここで、+、-、× は多項式演算を表し、lead は関数の入力引数として指定された多項式の主要な項 (最高次数の項) を返す関数です。lead(remainder) / lead(denominator) は、2 つの主要な項を除算して得られる多項式を返します。

関数の分子/分母は
    分母≠0が必要
    商 ← 0
    余り ← 分子 // 各ステップで分子 = 分母 × 商 + 余り

    剰余≠0かつ次数(剰余)≥次数(分母)のとき
        tmp ← lead(剰余) / lead(分母) // 先頭の項を割り算する
        商 ← 商 + tmp
        余り ← 余り − tmp × 分母

    （商、余り）
を返す

これは、次数(分子) < 次数(分母)の場合でも同様に機能します。その場合、結果は単なる (0,分子) となり、while ループには入りません。

このアルゴリズムは、まさに上記の紙と鉛筆による方法を記述しています。分母は「)」の左側に書き込まれ、商は水平線の上に項ごとに書き込まれ、tmp には各ループの繰り返しにおける商の最後の項が格納されます。水平線の下の領域は、剰余の連続値を計算して書き留めるために使用されます。

ユークリッド除算

B ≠ 0となるような多項式（ A、B）のあらゆるペアに対して、多項式除算は商Qと余りRを与え、

A=BQ+R,

R = 0 または次数( R ) < 次数( B ) のいずれかである。さらに、( Q , R ) はこの性質を持つ唯一の多項式のペアである。

AとBから一意に定義される多項式QとRを得る過程はユークリッド除算（あるいは除算変換）と呼ばれます。したがって、多項式長除算はユークリッド除算のアルゴリズムです。^[1]

アプリケーション

多項式の因数分解

多項式の根が1つ以上分かっている場合があり、これは有理根定理を用いて求められているものなどがある。n次多項式P ( x )の根rが1つ分かっている場合、多項式の長除法を用いてP ( x )を( x − r ) Q ( x )の形に因数分解することができる。ここでQ ( x )はn −1 次多項式である。Q ( x )は単に除算から得られる商である。rはP(x)の根であることが分かっているので、余りは0になるはずである。

同様に、 P ( x )の複数の根r、s、…がわかっている場合は、線形因子( x − r )を割り出してQ ( x )を取得し、さらにQ ( x )から( x − s )を割り出すなどすることができます。 ^{[a]あるいは、}P ( x )から二次因子を割り出してn −2次の商を取得することもできます。 $(x-r)(x-s)=x^{2}-(r{+}s)x+rs$

この方法は特に3次多項式に有効で、高次多項式のすべての根を求めることができる場合もあります。例えば、有理根定理によって5次多項式（5次）の1つの（有理）根が得られる場合、それを因数分解して4次（4次）の商を求めることができます。そして、4次多項式の根を求める明示的な公式を用いて、5次多項式の残りの4つの根を求めることができます。しかし、5次多項式を純粋に代数的な方法で解く一般的な方法は存在しません。アーベル・ルフィニの定理を参照してください。

多項式関数の接線を求める

多項式の長除法は、多項式P ( x ) で定義される関数のグラフの特定の点x = rにおける接線の方程式を求めるために使用できます。^[2]R ( x ) がP ( x ) を( x − r ) ²で割った余りである場合、 r が多項式の根であるかどうかに関係なく、関数y = P ( x )のグラフに対するx = rにおける接線の方程式はy = R ( x )です。

例

次の曲線に接する直線の方程式を求めよ $y=(x^{3}-12x^{2}-42)$

で：

x=1

まず多項式を次のように割ります。 $(x-1)^{2}=(x^{2}-2x+1)$

{\begin{array}{r}x-10\\x^{2}-2x+1\ {\overline {)\ x^{3}-12x^{2}+0x-42}}\\{\underline {x^{3}-{\color {White}0}2x^{2}+{\color {White}1}x}}{\color {White}{}-42}\\-10x^{2}-{\color {White}01}x-42\\{\underline {-10x^{2}+20x-10}}\\-21x-32\end{array}}

接線は $y=(-21x-32)$

巡回冗長検査

巡回冗長検査では、多項式除算の剰余を使用して、送信されたメッセージのエラーを検出します。

参照

参考文献

^ S. Barnard (2008). Higher Algebra . READ BOOKS. p. 24. ISBN 978-1-4437-3086-0。
^ ストリックランド・コンスタブル、チャールズ、「多項式グラフの接線を見つけるための簡単な方法」、Mathematical Gazette 89、2005年11月、466-467ページ。

注記

^ s は P(x) の根であるため、P(s) = (s - r)Q(s) = 0 となり、s は Q(x) の根となります（r と s は等しくないと仮定）。したがって、Q(x) は Q(x) = (x - s)Q'(x) と因数分解できます。ここで、Q'(x) は Q(x) を (x - s) で割った商です。