数理解析研究所講究録986 巻 1997 年 16-21

16$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$の関数描画機能の拡張について 1)

詫間電波高専 近藤祐史 (Yuji Kondoh)埼玉女子短大 三好善彦 (Yoshihiko Miyoshi)
上智大学理工学部 齋藤友克 (Tomokatsu Saito)
Abstract.
Visualization helps us to understand phenomenona, to see into the background,to discover a new question and so on. Usually, we use a numerical method to draw
graphs, but little of them is faithful.
In this paper, we extended the plotting functions on. Our system
can faithfully plot algebraic functions without loss of minute structures of algebraic
functions. We can use Gr\"obner basis to detect the minute structures.
$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$1. はじめに
数式処理の分野において関数の形状を表示することは、現象の理解、 背景の洞察もしくは新しい課題の発見等のために欠くべからざるプロセスである。特に数式で与えられた問題の幾何的イメージを把握できれば、解の存在範囲や交点の個数配置などが容易に見る事ができ、最終的な答えを導き出すことに役立つことが多い。
関数のグラフを表示することは–見容易な問題に見えるが、与えられた精度で関数のグラフを確実に描くことは非常に困難である。
我々はこの問題を ifplot 問題と呼び、 2 変数代数関数の場合に限って–般的なアルゴリ
ズム [3] を報告した。 また、 これらのアルゴリズムをインプリメントした陰関数描画システ
ム [2] を試作した。本稿では、 本システムの現状と追加した機能について報告する。

2. Cell plotting
関数の描画とは、与えられた表示領域 $D$ での関数 $f(x_{1,2}x)=0$ の零点を必要とされる精度で、 出力装置 (ディスプレイ、 プリンタ等) に出力することである。領域 $D$ を必要とされる精度でメッシュに切り、 セル亀に分割することにより、$D= \bigcup_{i=1}S_{i}$,$s_{i}\mathrm{n}S_{j}=\phi$,$i\neq j$,と表せる。描画とは各セルにおいて零点が存在するか否かの判定を行うことである。のような描画法を cell plotting と呼ぶことにする。
$S_{i}$1)

An extension of the plotting functions on$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{S}\mathrm{i}\mathrm{r}$こ17Cell plotting において、領域に関する定義として基本単位系とセル$S$に零点が存在するか否かの判定に対する定義として描画関数を次のように定める。
21. 描画基本単位系
上定義された$D$$\chi$の基本単位系 $S$ とは、$S_{i}l$$S$a$D\mathit{0}$) compact subset,

は S, の有限集合,$D=\cup S_{i}$,$S_{i}^{i}\cap Si\emptyset i=1j=i\neq j$と定義する。 ここで$S^{i}$

は $S$ の内点の集合であり、 $n$ はセルの総数である。

22. 描画関数
描画関数 $\chi(D, S)(f)$ とは、
$\{$

1.
2.

$\chi$: $Sarrow\{0,1\}$)$.\overline{\pi}X$$\chi(s_{i}).=0S_{i}\emptyset\{\pm^{\mathrm{B}},\mathrm{f}\mathrm{f}\mathrm{i}\mathit{0}$に対し $f(X)\neq 0$と定義する。 この $\chi(D, S)$ を $D$ における $S$ による character とよぶ。

2.2.1. Faithful characterによる faithful character
における$S$

$D$

$\{$

1.
2.

$\chi$$\chi$とは、は $S$ による character$\chi(s_{i})=1$$\exists x\in S_{i}\mathrm{s}.\mathrm{t}$. $f(x)=0$と定義する。

3. 2 変数多項式の faithful character
上の矩形領域とし、 $f(x_{1,2}x)$ を 2 変数有理係数多項式とする。
を今、 セルにおいて解を持つ必要+分条件は、 次の定理により与えらき、 $f(x_{1,2}x)=0$ がセル$S$

このと$\mathbb{R}$$S$れる。

において無平方とする。 が領域
2 変数代数方程式 $f(x_{1,2}x)=0$ はおいて零点を持つ場合は次の 3 つの場合しかない。 .

定理 1

1. が の境界上に零点を持つ。
2. Gr\"obner 基底
3. Gr\"obner 基底
$f$

$f$

$\mathbb{Q}$$\mathcal{G}(f=0, \partial f/\partial x_{1}=0)$$S$

か $S$ 内に零点を持つ。

が $S$ 内に零点を持つ。

この定理で場合 3 は場合 2 を含むため、セル$f$に$S$$\mathcal{G}(\partial f/\partial X_{1}=0, \partial f/\partial X2=^{0,f}=^{0})$

1.
2.
3.

$S$

$S$に零点がある否かを次のように判定する。

を無平方にする。の境界線上で Sturm の定理による方法により零点があるか判定する。

$\mathcal{G}(f=0, \partial f/\partial_{X_{1}}=0)$が $S$ 内に零点を持つか否か判定する。

18
4. インプリメントと実行例
本システムは、数式処理ライブラリ Risa および Asir の Gr\"obner 基底計算部を利用する。 また、 Asir とのプロセス間通信のインタフェイスを備えることにより、 asir-plot と同様な使用ができるように実現した。 また、新たに、

1. Postscript 出力
2. 点、線分、 円、 円弧などのオブジェクトの上書き機能などの機能を付加した。そのため、線分などのオブジェクトの上書き機能を利用する方法として、 Asir に plotobj $()$ 関数を加えた。

本システムの実行例に、 以下の代数関数を用いる。
$f_{1}(x, y)=x^{5}-2y_{X}+y^{5}2$249088
125$f_{2}(x, y)= \frac{93392896}{15625}x^{6}+(^{9}y+\frac{91521024}{625}2y\underline{4359552}--)x^{4}+\frac{1032192}{25}y4$

625

625

$-36864y^{3}- \frac{7732224}{25}y^{2}-20736\mathrm{o}y+\frac{770048}{25})_{X^{2}}+65536y+49152y^{5}6$-$135168y^{4}-72704y^{3}+101376y^{2}+27648y-27648$$f_{3}(x, y)=f_{2}(x, y)- \frac{1}{5}$を 600( $2400\mathrm{x}2400$ セル) で計算した PostScript 出力結果を Fig. 1 に示す。 また、タイミングデータを Table 1,2 に示す。計算は FreeBSD 2.2-SNAP Pentium
上で行った。 Fig. 1 中の円は中心のセル内に孤立特異点またはセルの内部で閉じた微細構造が$f_{2}$$\mathrm{d}\mathrm{p}\mathrm{i}$$166\mathrm{M}\mathrm{H}\mathrm{z}$あることを示す。

..

し rODner$\urcorner \mathrm{D}^{)}$.

し ro Dner Ak/氏とて (/) 月年 (!)\sim t 鼻

19$.\cdot.\cdot.\cdot.\cdot.\cdot.\cdot.[\ovalbox{\tt\smallREJECT}.’.\cdot..\cdot.\cdot.\cdot.\cdot..\backslash$$\cdot.\cdot.\cdot.-||\mathrm{L}-\overline{2}.\overline{0}^{-:}-\iota.0\overline{0.0}1.02.0^{-}i.\cdot.0^{\cdot}.02.0\iota_{2.0}1.00$.

Fig. 1.

$f_{2}\text{の}$Postscript 出力$(600 \mathrm{d}\mathrm{p}\mathrm{i})$5. Cell Trace
セルの境界部の計算効率を上げるため、 Cell Trace を試みた。 この方法は、 表示領域の境界上の零点を含むセルと $\{f=0, \partial f/\partial x=0\}$ の解と表示領域の境界上の $f=0$ の解を含むセルから出発して、セル毎の追跡を行うものであり、以下の手順で境界部の Sturm を計算する。

1. $\{f=0, \partial f/\partial x=0\}$ の解と表示領域の境界上の $f=0$ の解を含むセルを黒く塗り、 その周りのセルを候補に入れる。
2. 候補のセルを– つ取り出し、 その境界線上で Sturm により零点があるかどうか調べる。 このとき、一度計算した境界線を再度計算しないように工夫する。零点があるのセルを黒く塗り、その周りのセルを候補に加える。 (ただし、既に黒く塗られているセルは除く。)
3. 候補が無くなるまで 2. を繰り返す。

Cell Trace と素朴な方法との計算時間を Table 3 に示す。 この結果より、 Cell Trace は曲Table 3

素朴な方法と Cell Trace の境界部計算の時間 (秒)線が表示領域の–部分しかないような場合には有効である。

20
6. 簡易 3 次元表示
本システムに付加したオブジェクトの上書き機能を利用することにより、 $z=f(x, y)$ の簡易 3 次元表示プログラムを開発した。 このプログラムは、新たに付加した plotobj $()$関数を用いることにより、 Asir 言語で記述してある。 Fig. 2 に、 $z=x^{2}+y^{2}$ での実行例を示す。

Fig. 2.

$z=x^{2}+y^{2}$の簡易 3 次元表示

7. まとめの描画機能を拡張し、有理数係数 2 変数代数関数の零点を表示装置の分解能の精度で正確に描画するシステムを開発した。 また、本システ
我々は、 数式処理システム$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$ムには、

1. Postscript 出力の faithful character への対応
2. 点、線分、 円、 円弧などのオブジェクトの上書き機能などの機能を付加している。 この機能を利用して簡易 3 次元表示を行うアプリケ $-$ ションも開発した。 今後は、 Sturm を用いている境界部分計算の高速化を行う必要がある。

参考文献[1] 近藤, 三好, 齋藤, 陰関数描画に関する一つの試み, 数理解析研究所講究録, vo1.920, pp.168-174,.
1995.
[2] 近藤, 三好, 齋藤, Cell Plotting, 数式処理学会大会報告, 数式処理, vo1.5, No 1, pp.52-53, 1996.

[3] 齋藤, 三好, 近藤, ifplot アルゴリズム, 数理解析研究所講究録, vo1.941, Pp.223-228, 1996.

21[4] Saito, T., An extension of Sturm’s theorem to two dimensions, Proceedings of the Japan
Academy to appear.