プログラミング雑感  新JavaScript入門  JavaScript,Neo-Generation  掲示板  表紙
12. 因数分解(4)  14. 多項式クラス(7) 
プログラミング雑感
Written 9/12/02
13. 多項式クラス(6)
前に多項式クラスを作ったときから1年が経ってしまいました。
今回から多項式の因数分解ができるようにしたいと思います。
■基本的な考え方
因数分解(4)の考え方を多変数の多項式に拡張します （ホントはナントカ基底がどーとかするらしいですが、 よく分からないのでこのまま行きます）。
n次のp変数多項式だとして、次の多項式について考えます。
このとき、全ての ki の組み合わせについて、
が成り立てば、
が成り立つことがわかります。 ここで、xij は j が異なれば異なる値であるとします。
■2変数2次での例
以上の考え方を簡単な例でみてみましょう。 例えば、次の多項式を因数分解することを考えます。 
    f(x,y) = x2 - 2xy + y2 + 3x - 3y + 1
これは2次式なので因数分解できるとすれば1次式同士の因数分解になります。 
    g(x,y) = p1x + p2y + p3
    h(x,y) = q1x + q2y + q3
    f(x,y) = g(x,y)h(x,y)
f と同じ形の多項式 f1 を考えます。すなわち、 
    f(x,y)  = a0 + a1x + a2x2 + a3y + a4xy + a5y2
    f1(x,y) = b0 + b1x + b2x2 + b3y + b4xy + b5y2
それぞれ異なる x0, x1, x2 と y0, y1, y2 に対して、 
    f(x0,y0) = f1(x0,y0)
    f(x1,y0) = f1(x1,y0)
    f(x2,y0) = f1(x2,y0)
    f(x0,y1) = f1(x0,y1)
    f(x1,y1) = f1(x1,y1)
    f(x0,y2) = f1(x0,y2)
が成り立つとします。このとき f と f1 は同一です。なぜなら、 
    Aa = Ab
    
    a = t(a0, a1, a2, a3, a4, a5)
    b = t(b0, b1, b2, b3, b4, b5)
A の行列式は、 
    detA = (x1 - x0)2(x2 - x0)(x2 - x1)(y1 - y0)2(y2 - y0)(y2 - y1) ≠ 0
よって、 
    a = b
よって、それぞれ異なる x0, x1, x2 と y0, y1, y2 に対して、 
    f(x0,y0) = g(x0,y0)h(x0,y0)
    f(x1,y0) = g(x1,y0)h(x1,y0)
    f(x2,y0) = g(x2,y0)h(x2,y0)
    f(x0,y1) = g(x0,y1)h(x0,y1)
    f(x1,y1) = g(x1,y1)h(x1,y1)
    f(x0,y2) = g(x0,y2)h(x0,y2)
が成り立てば、 
    f(x,y) = g(x,y)h(x,y)
すなわち f が因数分解できることになります。
次に上の6つの式を解くこと（あるいは解けないことを示すこと）を考えます。
■続・基本的な考え方
x0, x1, x2, y0, y1, y2 を整数値とすると、 
     f(xi,yj), g(xi,yj), h(xi,yj)
もそれぞれ整数になります。 そのため g と h が取り得る値は f の約数（負数を含む）になります。 
     xi = yi = i (i = 0, 1, 2)
とすると、 
    f(0,0) = g(0,0)h(0,0) = 1
    f(1,0) = g(1,0)h(1,0) = 5
    f(2,0) = g(2,0)h(2,0) = 11
    f(0,1) = g(0,1)h(0,1) = -1
    f(1,1) = g(1,1)h(1,1) = 1
    f(0,2) = g(0,2)h(0,2) = -1
すなわち、 
    (g(0,0), h(0,0)) = (1, 1), (-1, -1)
    (g(1,0), h(1,0)) = (5, 1), (-5, -1), (1, 5), (-1, -5)
    (g(2,0), h(2,0)) = (11, 1), (-11, -1), (1, 11), (-1, -11)
    (g(0,1), h(0,1)) = (-1, 1), (1, -1)
    (g(1,1), h(1,1)) = (1, 1), (-1, -1)
    (g(0,2), h(0,2)) = (-1, 1), (1, -1)
が成り立つことになります。 これをしらみつぶしに調べれば、因数分解が得られる、 または因数分解できないことが分かります。
もし、 
    f(xi,yj) = g(xi,yj)h(xi,yj) = 0
となった場合は、 
    g(xi,yj) = 0 or h(xi,yj) = 0
です。
この考え方を最初のような一般的な場合に拡張することは容易でしょう。
first, prev, next, exit