多項式のGCDの魅力
この記事は日曜数学 Advent Calendar 2024
(
https://adventar.org/calendars/9972
) の9日目の記事です．
はじめに
数式処理(計算機代数)とは，因数分解やグレブナー基底といった，数学における計算をコンピュータに厳密に(記号的に)行わせることを目的とした応用数学の一分野です．
応用数学とはいっても，工学等への応用のみでなく，純粋数学におけるややこしい計算もある程度は記号的に処理できるため，純粋数学畑の人にとっても有用なものです．
数式処理のトピックの一つとして，多項式のGCDは非常に応用範囲が広いため，研究されています．本記事では様々な応用を通じて，GCD，そして数式処理の魅力を解説したいと思います．
多項式のGCD
今回，係数体は$\mathbb{R}$とします．
一変数多項式$f,g\in \mathbb{R}[x]$に対し，以下の条件を満たす多項式$h\in \mathbb{R}[x]$のことを$f,g$の最大公約元(GCD)といい，$\gcd(f,g)$で表す．
- $h$は$f,g$を割り切る
- $d\in \mathbb{R}[x]$が$f,g$を割り切るなら，$h$も割り切る
$f=x^2-1=(x-1)(x+1),\ g=x^2-2x+1=(x-1)^2$とすると，$\gcd(f,g)=x-1.$
上の例では因数分解した形を書いておきましたが，実際のGCD計算で因数分解を使うわけではありません．整数のGCD同様Euclidの互除法で計算ができますが，注意として，$\mathbb{Z}$や$\mathbb{Q}$上で実行すると係数膨張という現象によって，係数体上の演算がかなり重たくなり，効率が悪くなります(気になる人は，互除法の途中経過を計算機で確認してみてください)．係数膨張を抑えるGCDの計算法としてはsubresultantによるものやmoduler法などが使われますが，ここでは触れません．
無平方分解
GCDの計算ができると嬉しいことの一つとして，無平方分解の計算があります．まずは無平方の定義をしておきます．
$f\in \mathbb{R}[x]$が無平方であるとは，$g\in \mathbb{R}[x]$で，$\deg g\geq 1$かつ$g^2$が$f$を割り切るようなものが存在しないことをいう．
$f=x^2-2x+1=(x-1)^2$は無平方でない．
$g=x^2+1$は無平方．
無平方分解は以下のように定義されます．
$f\in \mathbb{R}[x]$の無平方分解とは，以下の分解のこと．
\begin{align*}
f=f_1f_2^2\cdots f_k^k.
\end{align*}
ただし，$f_k$は定数でなく，$f_1,\cdots,f_k$は無平方で，$\gcd(f_i,f_j)=1\quad (i\neq j)$．
$f=x^6-14 x^5+80 x^4-238 x^3+387 x^2-324 x+108$とすると，$f$の無平方分解は$f=(x-1)(x-2)^2(x-3)^3.$
例えば因数分解アルゴリズムのように，アルゴリズムの入力に無平方であることを要求されることがよくあります．このような場合，無平方分解を行った後，無平方因子ごとにアルゴリズムを実行すればよいのです．
無平方分解の計算アルゴリズムはGCDを基に作ることができます．よく知られたアルゴリズムは，以下の性質を利用して設計されています．
$f\in \mathbb{R}[x]$が無平方 $\Longleftrightarrow$ $\gcd(f,f^\prime)=1.$
$f=f_1\cdots f_k^k\in \mathbb{R}[x]$を$f$の無平方分解とすると，$\gcd(f,f^\prime)=\prod_{2\leq i\leq k}f_i^{i-1}.$
アルゴリズムの詳細は書きませんが，どうやって計算するか最初の方だけお見せしましょう．命題２から，$u=f/\gcd(f,f^\prime)=f_1\cdots f_k$です．$\gcd(f,f^\prime)$は$f_1$を因子に持たないので，$ v=\gcd(u,\gcd(f,f^\prime))=f_2\cdots f_k$となります．すると$\dots$ $u/v=f_1$となって，$f_1$が計算できます．
残りも同様にひたすらGCDを計算することで，$f_2,\cdots,f_k$が求められます．GCDは強力なわけです．
Newton法(重根の場合)
Newton法への応用を考えてみます．Newton法の解説は山ほどあるので，ここでは説明しませんが，代数方程式$f(x)=0$の近似解が計算できるよ〜ということが分かっていればOKです．
Newton法は強力なツールですが，求めたい根が重根の場合に精度が悪くなることが知られています．
$f=x^{22}-28 x^{20}+355 x^{18}-2690 x^{16}+13535 x^{14}-47480 x^{12}+118485 x^{10}-210330 x^8+260280 x^6-213840 x^4+104976 x^2-23328$とする($f$の根は全て重根)．初期値を$x_0=0.5 $としてNewton法を実行すると，近似解は1.41297となる．
これ，実は$x=\sqrt{2}$の近似解を求めているのですが，$ \sqrt{2}=1.41421\dots$なので，小数第三位の時点で合っていません．ガバガバ近似です．
今回はこの問題を前節の無平方分解を使って解決してみましょう．$f$を無平方分解して，各無平方因子に対しNewton法を適用すれば良いのです．無平方因子は単根しか持たないため，重複度による精度の悪化を回避できます．
$f$を無平方分解すると，$f=(x^2-2)^5(x^2-3)^6$が得られる．$f_5=x^2-2,f_6=x^2-3$に対して適切な初期値でNewton法を適用すればOK.
実際，先ほどの初期値で$f_5$にNewton法を実行すると，$\sqrt{2}$の近似解は1.41421$\cdots$と，先ほどよりずっと良く近似できている．
ちなみに，無平方分解から根の重複度も分かるわけですが($x=\pm \sqrt{2}$は5重根，$x=\pm\sqrt{3}$は6重根)，重複度とかどうでもいいから根が計算してぇ〜というときは
無平方部分$f/\gcd(f,f^\prime)=f_5f_6$に対してNewton法を適用してもよいです．
GCDでは，まだ足りない...
さて，これまでGCDとその応用について解説してきました．この他にも山ほど応用があります．ただ，これまで見た例はあくまでも解きやすい，人工的なものです．
実践的には，厳密計算のGCDではどうにもならないことがあるのです．
代数的アルゴリズムへの誤差の影響
これまで，係数体は$\mathbb{R}$で話を進めてきました．理論的には何も問題ないのですが，数式処理のアルゴリズムは最終的には計算機で実行します．ということは，係数として浮動小数点数を使う場面があります．すると，何らかの影響で誤差が入ることがあり，この時重大な問題が起こります．
本来は$f=x^2-2x+1,g=x^2-1$となるはずが，何らかの影響で係数に誤差が入り， $\hat{f}=x^2-2.00001x+1.00001,\hat{g}=x^2-1.00001$となってしまった！
$\gcd(f,g)=x-1$のはずが，$\gcd(\hat{f},\hat{g})=1$と互いに素になってしまった$\dots$
数式処理の多くのアルゴリズムは，厳密計算を前提とする故に，誤差が入ると全く無意味な答えを返すことがあります．GCDの計算もその一例です(例えば互除法で計算すると，剰余の0判定でうまくいかない)．また，サブルーチンにGCDを使う無平方分解も同様です(Newton法の例では整数係数だったので，厳密に計算ができた)．
しかし，実用上浮動小数演算を避けられない場面はどうしても出てきます．では，多項式に誤差が入るのはもう仕方ないとして，そこからGCDっぽいものを計算できないでしょうか？
近似GCD
GCDの定義において，誤差項を許容すると，例えば以下のようにGCDっぽいものを定義できます．
$f,g\in \mathbb{R}[x], \varepsilon\geq 0$に対し，以下を満たす次数最大の$h$を$f,g$の許容度$\varepsilon$の近似GCDという．
\begin{align*}
&\exists \Delta_f,\Delta_g,f_1,g_1\in \mathbb{R}[x], f+\Delta_f=f_1h, g+\Delta_g=g_1h,\\
&\deg\Delta_f\leq \deg f, \deg \Delta_g \leq \deg g, \quad \|\Delta_f\|_2\leq \varepsilon \|f\|_2,\|\Delta_g\|_2\leq \varepsilon \|g\|_2.
\end{align*}
ただし，$\|p\|_2$は$p$の係数ベクトルの$2$ノルムとする．
近似GCDは一意的には定まりません．また，他にも色々な定義の近似GCDがあります(例えば，次数をこちらが指定するもの等)．
試しに，先ほどの例の近似GCDを求めてみましょう．
$\hat{f}=x^2-2.00001x+1.00001,\hat{g}=x^2-1.00001$とする．適当な許容度の下近似GCDを求めると，$1-0.999995x$が得られる．元々は$\gcd(f,g)=x-1$だった．確かに，それらしきものが計算できている！
代数的なものに近似なんて入れて大丈夫なの？それ意味あるの？と思われるかもしれませんが，近似GCDを使えば，さらにできることが増えます．いくつかの応用を見てみましょう．
Newton法(近接根の場合)
Newton法の節で，重根に対して精度が悪くなるという話をしました．実は重根以外にも，近接根というものでも精度が悪くなります．
$f=x^6-2.73932 x^5+3.12662 x^4-1.90329 x^3+0.651715 x^2-0.119017x+0.00905628$とする．
$f$の根は$x=0.45655351,0.45655341,0.45655331,0.45655321.0.45655311,0.45655301$であり，近接している．
初期値$x_0=0.4$からNewton法を適用すると，近似解は0.455624となる．
$x=0.45655301$の近似解になるはずですが，小数第三位から合っていません．あまり良い近似ではないようです．
重根の時と同じように近接根も無平方分解で何とか対処できないか？と考えたい所ですが，今回の場合近接根は単根になっているので，無平方分解をしたところで近接根を分離することはできませんね．どうしたものやら$\dots$
この場合，近似GCDと同様に近似無平方分解を考えることができ，近似無平方分解は近似GCDを用いて計算できます．近接根は近似重根として近似無平方分解に現れるので，それを利用してより精度の良い根を得ることができます(近似無平方分解の実装を持ってないので例は挙げていませんが，例えばapproGCDを見てください)．
有理関数の約分
有理数を扱う時と同様に，有理関数を扱う際，分子分母のGCDをとって約分する操作はよく使われます．ここでも，誤差の影響で本来約分されるはずの因子が分子分母に残ってしまうことがあります．これによって無駄に次数の大きい有理関数を扱うことになる，約分で消えるはずの因子から本来現れない極が現れるなど，用途によっては都合の悪いことが起きます．近似GCDを考えれば，うまく約分をすることができます．
$p/q=\frac{x^2-1.23329 x+0.354303}{x^2-1.34441 x+0.404929}$とする(本来は一次分数になるはずが，誤差が入って約分されなかったとしよう)．$p,q$の近似GCDは$x-0.455625$であり，$p/q\simeq \frac{x-0.777665}{x-0.888785}$と近似的に約分できる．
おわりに
GCDについてのいくつかの応用と，近似GCDについて紹介しました．数式処理では厳密計算を主に扱うので，近似を考える数値計算とは対極にあり，一見相容れないものと思われるかもしれません．しかしここで紹介した近似GCDのような，ある種数式処理と数値計算の融合した領域(数値数式融合計算，近似代数)もあり，これによって厳密計算を考えるだけでは難しかった問題にも立ち向かうことが可能となります．
今回は応用メインで紹介しましたが，数式処理のアルゴリズムの構築自体も大変面白いものです．ああでもないこうでもないと頭を捻り，作り上げたアルゴリズムで今まで計算できなかったものが計算できるようになったとき，嬉しくてたまらないのです．まだまだ魅力を解説しきれていないようにも思いますが，数式処理の面白さが伝われば幸いです．
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
