12. 因数分解(4)
次の多項式について考えます。
f(x) = a0 + a1x + ... + anxn
g(x) = b0 + b1x + ... + blxl
h(x) = c0 + c1x + ... + cmxm
l + m = n
各々異なる x
i (i = 0, ... ,n) について、
f(xi) = g(xi)h(xi)
が成り立てば、
f(x) = g(x)h(x)
が成り立つことがわかります（証明は簡単なので省略）。
多変数の場合にもっと丁寧な説明を
次のページに載せました
（9/12/02)。
従って、各々の i について、
g(xi) = pji
h(xi) = qji
pjiqji = f(xi)
が成り立つような g(x)、h(x) がある j を見つければよいです。
j は有限個なので、連立方程式を有限回解けば因数分解することができます
（あるいは因数分解できないことがわかる）。
実際には連立方程式を満たす g(x) が見つかれば、
f(x)/g(x)を計算して、割り切れるかどうか調べます。
あと、
f(xi) = 0 => g(x) = x - xi
です。
p
i, q
i が定まったとして、連立方程式を解きましょう。
x
i を次のように定めます。
xi = i (i = 0, ... ,n)
とすると、
b0 = p0
b0 + b1 + ... + bl = p1
b0 + 2b1 + ... + 2lbl = p2
...
b0 + lb1 + ... + llbl = pl
...
b0 + nb1 + ... + nlbl = pn
上のl+1元連立方程式を解き、整数解であれば下のn-l個の式にあてはめ、
式が成り立てばOKです。
上のl+1元連立方程式は引き算を繰り返すことにより次のようになります。
詳しくは
こちら。
b0 = p0
1!b1 + d12b2 + ... + d1lbl = p1 - p0
+ 2!b2 + ... + d2lbl = p2 - 2p1 + p0
...
l!bl = pl - lCl-1pl-1 + lCl-2pl-2 - ... + (-1)lp0
dij = ij - iCi-1(i-1)j + iCi(i-2)j-2 - ... + iC1(-1)i-1
あとは、b
l, b
l-1, ... と次々に求められます。
求まった b
i に対し、下のn-l個の式が成り立つような
p
l+1, ... , p
n がそれぞれ
f(x
l+1), ... , f(x
n) を割り切れるかどうかで判定します。
テキストボックスに多項式を入れてボタンを押すと、因数分解されます。
ソースは次です。
polynomial.js (ファイルに保存にしてください)
p_numbers.js (ファイルに保存にしてください)
divisors.js (ファイルに保存にしてください)
予想はしていましたが、すごく遅いです。
8次くらいなら1秒くらいで答えが出ることが多いですが、
16次だと全然返ってきませんでした。
スピードアップの工夫は色々できますが、
p
iが4つ以上取れることが多いので、
基本的に4のn/2乗以上かかってしまいます。
これは本質的なのでしょうか？