代数幾何ゼミ
石井大海
早稲田大学基幹理工学部
数学科四年2013 年 10 月 16 日

Using Algebraic Geometry
Chapter 2 Solving Polynomial Equations• Ideals, Varieties and Algorithms が一段落したので，今日からUsing Algebraic Geometry を読みます．
• 第二章：代数方程式の解法• lex 順序に関する Gröbner 基底により一文字ずつ文字を消去出来る• 一変数の根の数値解法と組合せた単純なアルゴリズム−→ 有限精度で多項式を連立するのには本質的な困難が• 代数的構造に着目してその困難を乗り越えよう！
• 解のよりよい近似と実数解の数え上げ，解の分離（？）などを行えるように• 他章でも解法を検討する

Ch 3: 終結式を用いた解法．
Ch 4: 重複度の解への割り当て方
Ch 7: ホモトピー連続法に基いた重複度の数え方

2.1 消去理論による解法• 消去順序，特に lex 順序による Gröbner 基底 G で変数を順次消去出来る．
• 次のような戦略が考えられる：
123Gröbner 基底 G を計算
G の変数数最小のものから根を求めていく
拡張定理を用いて順次代入・拡張していく⋆ この方法は特に V (I ) が有限なら上手くいく！

実際に解く例 I 222
x + y + z = 4x 2 + 2y 2 = 5xz = 1(1.1)

この方程式系の lex に関する Gröbner 基底を計算すると，

G = { g1 = 1 + 2z 4 − 3z 2 , g2 = y 2 − z 2 − 1, g3 = x + 3z 3 − 3z }g1 の根は高々有限個．g2 に z を代入しても高々 2 つの根しかでてこず，g3 によれば x は z に対し一意に決まる．よって|V (I )| < ℵ0 ．
I2 = I ∩ k[z] の基底は g1 で，更に Q[z] で因数分解できる：
g1 = (z − 1)(z + 1)(2z 2 − 1)

実際に解く例 II
よって，次の根が得られる：√z = ±1, ±1/ 2
LCy (g2 ) = 1 より拡張定理からこれらは複素数の範囲で V (I1 ) 完全解に伸びる．更に LCx (g3 ) = 1 なので，V (I ) 全体にも伸びることがわかる．特に， z = 1 として G に代入すれば，Ḡ = { −1 + x, y 2 − 2, 0 }√となるので x = 1, y = ± 2 となることがわかる．他も同様に解いて（演習問題 1），次を得る：√√(x, y , z) = (1, ± 2, 1), (−1, ± 2, −1),
√ √√√
√
√
31
31( 2, ±,), (− 2, ±,−) (複号任意)2222

考察 I⋆ (1.1) は解の座標が全て有理数の根号で表せるので比較的簡単−→ 一般の場合はそんなに簡単ではない！
• [Galois et al.] 五次以上の代数方程式は根号と体演算による解の公式を持たない．
−→ 結果が五次以上になると根号を使って記号的に解けない！

• 例：(1.1) において最初の x 2 を x 5 に変えると，{G=g1 = 2z 7 − 3z 5 − z 3 + 2, g2 = 4y 2 − 2z 5 + 3z 3 + z − 10
g3 = 2x + 2z 6 − 3z 4 − z 2

ここで， g1 = (z − 1)(2z 6 + 2z 5 − z 4 − z 3 − z 2 − z − 1) であり，二番目の因子は Q[z] で既約．

⇝ これを「解く」とはどういう意味か？欲しい「解」の種類を決める必要}考察 II• 純粋に「代数的」・「構造的」な解が欲しいなら， Maple とかを使えば解けない方程式の根を文字で置いた構造的な答えを教えてくれる．

↔ 実用上は近似値がわかったほうが便利だし，その精度が高ければ文句はない．
⊚ 一つのありうる方法：
2z 6 + 2z 5 − z 4 − z 3 − z 2 − z − 1 = 0(1.2)の近似解を求めて，今まで通り拡張定理を適用する．
• 今までと違って，全ての計算を浮動小数を用いてやる必要がある• 複数の変数に対し近似解を求める必要があるかも• R, C で多項式の根を求める有名な方法：Newton-Raphson 法Newton 法 I

多項式 p(z) の根の近似値を求めたいとする．
1初期近似値 z0 を選ぶ

2数列 {zk }k<ω を次により定める（p ′ は p の導関数）：

zk+1 = zk −p(zk ).
p ′ (zk )3

大抵の場合， zk は p(z) = 0 の解 z̄ に急速に収束する

4

上の漸化式を適当な誤差の範囲に入るか，予め決めておいた反復上限に達するまで有限回繰り返す．

Newton 法 II
• 効率については後程論じる! Newton 法でやっかいな事：全ての解を求められるように z0を適切に選ぶこと· · · 異なる z0 を選んでも，同じ根に収束してしまうかも• 解の範囲がわからなければ見落としがあるかもしれない．
⇒ 根の絶対値のかんたんな上界が知られている．

Exercise 2-3p(z) = z n + an−1 z n−1 + · · · + a0 ∈ C[z] の根 z̄ は次を満たす：|z̄| ≤ max{1, |an−1 | + · · · + |a0 |}Newton 法 III
Proof.
p(z̄) = z̄ n + an−1 z̄ n−1 + · · · + a0 = 0 とすると，z̄ n = −(an−1 z̄ n−1 + · · · + a0 )∴ |z̄|n = |an−1 z̄ n−1 + · · · + a0 |≤ |an−1 ||z̄|n−1 + · · · + |a1 ||z̄| + |a0 ||z̄| ≤ 1 ならば OK．|z̄| > 1 として辺々を |z̄|n−1 で割れば，
an−2a0+ · · · + n−1z̄z̄
≤ |an−1 | + · · · + |a0 ||z̄| ≤ |an−1 | +よって示された．

Newton 法 IV
Exercise 2-10 (もっと良い上界)
上において z̄ ≤ 1 + max{|an−1 |, . . . , |a0 |} となる
証明．n に関する帰納法で示す．n = 1 の時，p(z) = z + a0 より|z̄| = |a0 | だから OK．
n = k で成立とする．n = k + 1 の時，p(z) = (z k + ak z k−2 + · · · + a1 )z + a0|{z}:=q0 (z)とおく．p(z̄) = 0 とすると，q0 (z̄)z̄ = −a0 ．ここで q0 (z̄) = 0 な
ら帰納法の仮定より |z̄| ≤ 1 + max{|a1 |, . . . , |ak |} となるので OK．
同様に z̄ = 0 の時も OK．よって a0 , z̄, q0 (z̄) ̸= 0 としてよい．
今，|q0 (z̄)| ≥ 1 とすると，三角不等式より
0 = |q0 (z̄)z̄ + a0 | ≥ |q0 (z̄)||z̄| − |a0 | ≥ |z̄| − |a0 | であるので|a0 | ≥ |z̄| となる．

Newton 法 V
そこで，|q0 (z̄)| < 1 とすると，|qi (z̄)| < 1 となる最大の i0 が取れる．もし i0 = n − 1 ならば，1 > |qn−1 (z̄)| ≥ |z̄| − |an−1 | より
1 + |an−1 | ≥ |z̄| となり OK．そこで i0 ̸= n − 1 とする．この時，i0 の最大生より |qi0 +1 (z̄)| ≥ 1 であることに気をつければ，
1 > |qi0 (z̄)| ≥ |qi0 +1 (z̄)||z̄| − |ai0 | ≥ |z̄| − |ai0 | であるので，1 + |ai0 | > |z̄| となるので成立．よって示された．
• これらの上界を使うことで，根を探す領域を限定することができる．
• このような数値解法と組合せれば，先程の問題も解ける．
• 落とし穴：一変数の解は近似式なので，代入して得られる解も近似式に過ぎない！

⇝ そもそも微妙に「違う方程式」を解いていることになる• 近似解を逐次求めても，厳密解に近い値が得られるとは限らない．
• 各反復・拡張の際に高次になればなるほど誤差が蓄積

Newton 法の本質的困難 I
Example.
p(x) = (x + 1)(x + 2) . . . (x + 20)，q(x) = p(x) + 10−9 x 19 とおいて数値解を求めると，次のような答えが出る：−20.03899282− 10.95660245− 10.00771277−8.99916237− 8.00005971− 6.99999746−6.00000006−5−4−3−2√−18.66983264 ± 0.35064021 −1√−16.57173899 ± 0.88331561 −1√−14.37367156 ± 0.77316072 −1√−12.383493 ± 0.10866741 −1−1複素数解が八つも現れ，しかも虚部もそこまで大きくない．

Newton 法の本質的困難 II• これは病的な例だが，近似解を探すときは気をつけなければならない．
• こうした事がおこらなくても，更に困ったような例が作れる．

Example.
G = { g1 = x 2 + 2x + 3 + y 2 − y , g2 = y 6 − y 2 + 2y } は lex に関する Gröbner 基底である．g2 = 0 は実数解を二つ持つ．なぜなら，g2 = y (y 5 − y + 2) であり，まず y = 0 が解．更に，
g2 (−1) < 0, g2 (−2) > 0 より中間値の定義から [−2, −1] 上にもう一つ解を持つことがわかる．ここで解かせると，
y = −1.267168305 となる．これを代入して g1 を解くと，
x = −1.0000737894, −0.9999262106 を得る．これらは −1 に限りなく近いが −1 ではない二つの解である．更に精度を弄って√
y = −1.2671683 を代入すれば x = −1 ± 2.207460939751 −1 となる．

Newton 法の本質的困難 III• 何が起きているのだろうか？
• g1 の非零根は y 5 − y + 2 = 0 を満たす．もし正確な根を代入出来たとすると，Ḡ = x 2 + 2x + 1, 0 となり，重根 x = −1を得る．

• 結論：重根を持つ方程式は誤差に弱い！
• とても近い二つの実解，複素共役解，実重解を見分けるのはとても難しい⇝ 解の個数を調べたい時に，今までの方法では困難！
• 数値計算の利便性は無視できないが，それだけでは簡単に間違える．
• 多項式方程式系の構造に関する情報を使って精度を上げられないか？
⇒ 次節以降では k[X]/I の性質を調べて新たな手段を作る数値解法についての幾つかの補足

1z̄ が p(z) の重根の時，Newton 法の収束は遅くなる．
⇝ 反復や計算精度には注意が必要（ここで演習問題 8 をやる）

z0 を選び間違えると zk は収束しないことがある（exc 9）
3 z0 と最終的な z̄ の位置関係は予測出来ない．
2• 近くを無視してちょっと遠いところに収束するかも最後の二つは C 上の Newton 法に関するフラクタル図形に関連．
• 消去に依存しない多変数 Newton 法なども考えらえてはいる• 他にも後程やるホモトピー連続法などもある