精度保証付き数値計算にまつわるできたてほやほやの話

大石進一(早稲田大学理工学部情報学科)


本文の構成は次のようである.
1. はじめに
2. 難しいことが分かった
3. 戦略とのめぐり合い

1.はじめに

(目次に戻る)

数値計算の誤差をすべて評価し,数学的に正しい結論を数値計算によって 導くというのが精度保証付き数値計算であり,これが実用的であることは 近年の計算機の発展と理論的なブレークスルーのおかげでようやく最近になって わかってきた.筆者はこの5年間,その研究に夢中になっている.このような 中で筆者の研究室のドクターの学生であった柏木雅英君が 有限次元非線形方程式の有界領域内のすべての解を精度保証付き 数値計算を利用して必ず求められることを証明し,それをプログラムとして 実装した.筆者と 同じ堀内和夫研究室の出身の群馬大学 山村清隆先生が群馬大学で宣伝して下さった.``方程式さえ書けば, 後は計算機で自動的にすべての解が求まるプログラムを早稲田大学が作った そうですよ''.さすがに,兄弟弟子の山村先生,宣伝をして下さる なんてありがたい.と思う間もなく,山村先生からe-mailが届いた. ``生物化学工科の土橋敏明先生が多相平衡問題に現れる大変解きにくい 連立非線形方程式が あります. もし,それが解けたら化学の分野では重要な仕事に なります,とおっしゃられています'',という前文に続いて,A4一枚程度に, 方程式と簡にして要を得た説明 があった.電話でも, ``要するに,試験管に油と水と中性洗剤を入れたときに,これらが 層になって,分離したとしますよね.この各層は完全に水だけとか 油だけということはなくて,少しずつ3つの物質が混ざりあって平衡している そうです.その平衡の条件を書いたのが平衡条件でこれが対数関数を含む 非線形連立方程式になり,その混ざり具合の比率が解になるそうです'' と補足してくれた.その説明に続いて,``水と油といいましたが, それがポリスチレンとメチルヘキサンで,自由エネルギーがなんとかかんとか で対数関数が出て来るそうです'',などというくだりになると,頭は完全に 飽和状態.

 ``ちょっ,ちょっと待って下さい,全ての解を求められ ることを証明したといっても,有界``閉’’領域での,すべての解が正則な とき...などの前提条件があります'',とは今更いえなくて, ``方程式を書いて下さったのですから意味はわからずとも 解いてみます''というお返事をしてしまった. 柏木君は,そこは大物,そんな問題が届いた ことを気にもかけずに,悠然と自分の研究を進めている.そのうち,九州大学に 就職して,さっさと博多へ行ってしまった.電話をしてみても,``えっと, こちらではトランジスタ回路の解の個数を研究してまして...''という 感じでとりあってくれない.``これはあかん,こんなことでは大石研の信用 まるつぶれや''と大阪弁で思ったかどうかは別として,新学期(去年の5月) だったのでM1の中谷君の研究テーマにして解いてもらうことにした. そして昨日(今年の2月),卒論生の遠藤咲織さんの卒論でようやくすべての解が 求まって決着.今日は,この長い苦闘の顛末をお話しさせて頂きます.

2.難しいことが分かった

(目次に戻る)

ことは去年の5月から始まる.中谷君には, ``log xという項があるから変数xの範囲が0

3.戦略とのめぐり合い

(目次に戻る)

こうして夏休みが明け,中谷君と遠藤さんがMathematicaで出した図 をもってきた. 図を少しみただけでは,どこに2つのグラフの 交点があるかわからない.それ程の悪条件問題であるが,この図を拡大して 子細に眺めてみると3つの異なった解があるようである.そこでクラフチック 作用素を利用して精度保証付き数値計算によってその3つの解の存在検証を してもらったところ成功した.この辺の議論の基礎となるクラフチック作用素 については講座``非線形現象の解析手法''(2,3月号)に書いたので興味をもたれた 読者は参照されたい.では,それ以外に解がないことをどうやっていうか. Mathematicaで書かせたグラフは誤差があり,少しうねれば新しい解が存在しても おかしくないので, このグラフで証明することはできない.従来の方法で解がない領域を 示そうとしても,領域が開であることと,これに目をつぶっても メモリ不足となってしまうので,新しいアイディアが必要である.

このようなとき九州大学で非線形問題研究会が開催された.そこで,山村先生の 講演を伺った.山村先生は精度保証付きではないが,非線形方程式の全ての解を 効率的に求めることに執念を燃やしておられて,Yamamura's sign testと世界で呼ばれる大変効率的な手法をあみ出しておられる.このときの講演では, 本論以外に,付録として原稿1枚分,講演時間で3分,線形計画法を利用して解の ない領域を見出す手法の提案があった.これを伺って電撃のような衝撃を 受けた.これはすごい.これこそ求めていた手法だ.この山村の手法 を使えばy=log xというスラック変数yを導入し,xの定義域を 分割し,例えば[a,b]という領域を考えるとlog a <= y <= log b という制約条件となる.こうして元の問題の非線形項をすべてスラック変数に 置き換えて得られる線形不等式の解の存在,非存在は線形計画問題のフェーズI で判定できる.もし,この線形計画問題に解がないときには,元の非線形方程式 にも解はないことがいえる.また,更に,a=0のときにはlog a <= y <= log bという条件はlog 0= -∞となることからy <= log b という条件になるだけである.すなわち,領域が開であることもこの手法で 克服できる.

早速,出張から帰って,中谷君と遠藤さんに山村の方法を伝授して, 解がないことの検出に山村の方法を加えた,新しい全ての解を求めるプログラム を作ってもらうことにした.中谷君は非線形関数のグラフを凸領域で囲むという 新しいアイディアを加えて山村の方法を効率化し,全解探索に とりかかった.山村の方法を利用すると,従来は無理であった開領域が取り扱 える.それだけではなく,かなり大きな領域に解がないこともわかる.こうして メモリオーバーをようやく回避できるようになった.それでも,解の 近くでは分割がかなり進む.これは,解の近くでクラフチック作用素が 縮小写像となる領域が10の-17乗以下の狭い領域になることや,解の条件数が 10の20乗程度になることが後で判明したことからも必然的であった.

中谷君と遠藤さんは 晩秋からの4ヶ月この問題に打ち込み,今年の2月 になってようやく,3つの解の存在とそれ以外には解がないことの証明に成功した. このことを書いた遠藤さんの卒論の最後は次のような言葉で結ばれている.``困難は多々あったが, 正しい全解を得ることができて非常に満足している.''

遠藤さんに卒論作成で何が一番苦しかったか聞いたところ,山村の 方法のアイディアはもらったが,これで果たして全解探索が成功するか どうか保証がないまま,何ヵ月も作業しなくてはいけなかったところ,ということであった. できるか,できないか分からないことを最初にやることは, 非常に大変なことであることがまたまた実感された.

本稿では人名を出させて頂きました.それらの人々から筆者は多くの 勉強をさせて頂きました.深く感謝いたします. (目次に戻る)


理工ジャーナル目次へ

御意見、御質問は、oishi@mn.waseda.ac.jpまで。

本文は(社)電子情報通信学会より発行された学会誌1996年11月号 pp.693-695に掲載された記事をHTMLに変換したものです.