プログラムな日常
>
理数学習このままでイイン会?
>
二変数多項式の因数分解(実係数)について
(arguments on factorizing two-variant polynomials within real factors)
【多変数多項式と因数分解】
このブログは昨年、「
一変数多項式の因数分解(実係数)
」にスタートし、先日「
二変数多項式の因数分解(実係数)
」をリリースするに至った。 この続きとして「三変数...」というのも可能なはずであり、簡単な例題に対処するアルゴリズムの基本はできている。 然しながら多項式の因数分解は、一変数の場合のみが重要であり、二変数以上では重要度は落ちるように思う。 これには2つの理由がある。
まず、一変数の多項式において因数分解は、「式の値」 = 0 とした方程式の解を得るのとほぼ同じだが、二変数以上では関係式の簡略化に留まり、変数の値が確定するわけではない。
もう一つの理由はより大きいかも知れないが、二変数以上で因数分解は身近ではない。一変数の多項式は、個々の因子がせいぜい二次式から成る次の形に分解できる
x
6
+Ax
5
+Bx
4
+Cx
3
+Dx
2
+Ex +F = (x
2
+Px +Q) (x
2
+Rx +S) (x
2
+Tx +U)
が、因数分解前後における係数の個数は(この場合、どちらも6個と)同じなので、無理なく決まることが推察される。 実際、ここでは、二次式3個の積としたが、このそれぞれはさらに一次式2個に分解できる場合があり、 それができるかは放物線が x 軸に交差して解を持つかどうかで決まるので、雑なことを言えば、半分の確率でこれも可能になる。 以上は代数学の基本定理などで保証されることだ。
これに対し、多項式の変数が2個になると、例えば、
Ax
2
+Bxy +Cx +Dy
2
+Ey +1 = (Px +Qy +1) (Rx +Sy +1)
のように分解できる可能性があるが、用いられる係数の数が(5から4に)減っている。 これでは、運が良くなければ全ての変数(5個)は合わせられない。
実例を挙げるなら、次の2つの多項式は、指数の組み合わせは一緒であるものの、係数が違うので、違うパターンに因数分解される。
4x
2
y
2
+2x
2
y +6xy
2
+7xy +x +3y +1 = (2xy +x +1) (2xy +3y +1)
4x
2
y
2
+6x
2
y +4xy
2
+4xy +3x +2y +1 = (2xy +1) (2xy +3x +2y +1)
そして、やはり係数が違うだけの次の場合は、因数分解自体、不能である
4x
2
y
2
+x
2
y +2xy
2
+xy +3x +2y +1
が、このように分解できないのが二変数以上の多項式では寧ろ一般的であって、分解できる方が稀である。
【二変数多項式因数分解のアルゴリズム:ステップ1】
まず、簡単な例として、次の積を考える。
=
これは、
10x
2
y +5x
2
+4xy
2
+31xy +7x +6y
2
+21y = (5x +2y +7) (2xy +x +3y)
という因数分解に対応するのだけれど、まず、因子にはゼロの要素があって、非ゼロ要素はそれぞれの因子で三角形の範囲に収まっていることがわかる。
また、積となった(3×3の)マトリクスにもゼロの要素があって、非ゼロ要素は六角形の範囲に収まる。
ここで、六角形の各辺は、因数である三角形の辺のどれかと平行である。例えば、六角形の左側に縦に連なる(4,6)という列は、 第一の因数の左端に連なる(2,3)という列と平行であるが、それだけでなく、その内容は比例関係を保っている。 このように、積で非ゼロ要素の作る多角形の各辺は、それと平行な辺を何れかの因子のどこかに必ず持ち、対応する辺と、内容の比例関係を保っている。
この場合であれば、全体の配分比を別とすれば、辺に着目するだけで全ての係数は決まる。 六角形の中心の数値は未使用だが、因子を検算して与えられた31以外になったら、少なくともこの辺の分け方に即しては、この課題の解が得られなかったと言える。
六角形の辺を振り分ける今の配分で解が得られなかったとしても、別の配分を考慮する必要がある。例えば、次のような配置である。
実際にはこの配分による解はなく、正しい解は上に挙げた一つだけである。
これは特に簡単な場合だった。もう少し複雑な場合に行く。
【二変数多項式因数分解のアルゴリズム:ステップ2】
次の積のマトリクスで左端に上下に連なる(2,3,1)は、(2,1)と(1,1)との積としてできたものである。 この結果は一変数多項式として因数分解できるが、こういう場合には因数として分け、辺ではなく、因数単位で振り分ける。
=
なお、振り分けるマトリクスの数は取り合えずは2つで構わない。左のマトリクスは最小のものから順に探し、残った右のマトリクスについては後から再分解を試す。
【二変数多項式因数分解のアルゴリズム:ステップ3】
このようにして、各因子の外周の要素は決まるが、その内側の要素は不定のまま残る。 例えば次のような場合、
=
第2のマトリクスの中心の2はまだ不定である。これをxと置くと、積の中の係数15に着目して次のことが言える。
2*1+3*x+1*7=15
これを解くと2が得られる。
これはソフトで表示する log の窓において、「single reduction」と定義している。 ただし、この議論はまだ十分に一般的ではなく、次のステップで、連立一次方程式を考察する必要がある。
【二変数多項式因数分解のアルゴリズム:ステップ4】
=
上の例では、積の左から2番目、上から2番目の-14と、それより2つ右の-43に着目すると、次の関係性がある。
1*y+5*1+1*1+x*1=-14
1*3+3*y+x*3+14*1=-43
この連立式を解くと、
x=-21
y=1
となる。このように、連立一次方程式を見つけられる場合は多い。 連立数はより多くなる場合もあり、逆行列を利用して解決している。
これは log では、「linear reduction」と定義している。 この手続きは、先のステップ3の場合を含む(連立数が1の場合)ので、こちらをしていればそちらを省略することもできる。
【二変数多項式因数分解のアルゴリズム:ステップ5】
ステップ4まででも解決しない特殊な場合もある。例えば次の形である。
=
xとyに対する条件が完全に対称で、x+y についてのみ連立一次方程式として解くことができるが、個々については解けない。これは、二次方程式として解決する。 同じような特殊ケースで、より大規模なものはないとは言えないが、今回のコードで対処しているのはこのように最も単純な場合までであり、 log では、「square reduction」と定義している。
以上、3から5までのステップは繰り返し適用して不明点を減らし、これで解が得られない時は、1に戻って別の分割方法を検討する。
2分割ができたら、左の因子は最小のものから探しているのでこれ以上分割する必要はなく、右の因子のさらなる分割を探索する。
【応用例】 三角形の辺の長さ a, b, c から面積を求めるヘロンの公式というのがあるが、面積の2乗 S
2
は式の値として、次のような2通りに書ける。
【一変数多項式因数分解のこと】
上のステップ2で一変数多項式因数分解を利用しているが、このやり方はまだご説明していなかった。(可読な)ソースコードの公開も今回が初めてだ。 はっきり申して、二変数よりもこの方が重要だが、これについては後日。