多項式の内部表現

Maximaの多項式は通常のCやFORTRANで記述するx^2+3*x*z+4の様な書式で入力され,表

示される結果も同様です.但し,表示の方は入力式そのままではありません.多少の簡易化を行ない, 係数の内部的順序に沿って項の並替えを行います.

(%i28) a:x+y+z;

(%o28) z + y + x

(%i29) :lisp $a;

((MPLUS SIMP) $X $Y $Z) (%i29) b:z+x+y;

(%o29) z + y + x

(%i30) :lisp $b;

((MPLUS SIMP) $X $Y $Z)

(%i31) c:(1+2)*x+3*y+(2+1-2)*z-z;

(%o31) 3 y + 3 x

(%i32) :lisp $c;

((MPLUS SIMP) ((MTIMES SIMP) 3 $X) ((MTIMES SIMP) 3 $Y)) (%i33) a1*x+a2*x;

(%o33) a2 x + a1 x

この例では多項式x+y+zと(1+2)*x+3*y+(2+1-2)*z-zの処理を示したものです. 最初に変数aに x+y+zを割当てています. :lisp $a;で変数aの内部表現を参照すると,((MPLUS SIMP) $X $Y $Z) が返却されています. (MPLUS\ SIMP)でこの式がMaximaの和である事を示し,後には項が並んで います.この項の並びは,x+y+zと入力しても,z+x+yと入力しても同じです. これはMaximaに は変数に対して順序を入れており,その順序に沿って与えられた多項式の各項を並替えているから です.

多項式(1+2)*x+3*y+(2+1-2)*z-zを入力すると,Maximaは自動的に簡易化を行なっている事が

判ります.但し,この簡易化は項の係数が数値の場合に限定されます.

以下,x+y,x-y,x*y,x/y,xˆ yについても:lispで内部表現を調べてみましょう.

(%i33) t0:x+y;

(%o34) y + x

64 第9章 多項式について (%i34) :lisp $t0;

((MPLUS SIMP) $X $Y) (%i35) t1:x-y;

(%o35) x - y

(%i35) :lisp $t1;

((MPLUS SIMP) $X ((MTIMES SIMP) -1 $Y)) (%i36) t2:x*y;

(%o36) x y

(%i37) :lisp $t2;

((MTIMES SIMP) $X $Y) (%i38) t2:x/y;

x

(%o38)

-y (%i39) :lisp $t3;

((MTIMES SIMP) $X ((MEXPT SIMP) $Y -1)) (%i40) t4:x^y;

y

(%o40) x

(%i41) :lisp $t4;

((MEXPT SIMP) $X $Y)

この様にMaximaではx-yはx+(-y),x/yはxˆ (-y)で置換えている事が判ります. Maximaでは この様に演算子を被演算子の前に置いた前置表現を一般形式と呼んでいます.これに対し,更に内 部表現を簡潔にした正準有理式表現(Cannonical Rational Expressions,略してCRE表現)もあり ます.

CRE表現はfactorやratsimp等々の函数で内部的に利用されるもので,利用者はこの表現をあ

まり意識する必要はありません. このCRE表現は本質的に展開された多項式や有理式函数に適し たリストによる表現の一つです.

尚,多項式のリストによる表現には連想リスト(alist)による表現もありますが, CRE表現はより

簡潔な(小括弧の少い)表現となります.

先ず,多項式3x²−1で説明しましょう.この場合,3x²+ (−1)x⁰と同値です.これをλ式風に考えれ ば,λ x˙3x²+ (−1)x⁰となりますね.ここで,係数と次数の対をから構成されるリストは((2 3) (0 -1)) となります.これだけでは変数が判らないので,頭にxを入れてみましょう.すると,(x (2 3) (0 -1)) となります. ここで,中の小括弧を外して(x 2 3 0 -1)としても3x²+ (−1)x⁰の復元には問題ありま せん.この様に,単変数の多項式に対するCRE表現は(h変数i h次数₁i係数₁ h次数₂i係数₂ · · ·) で与えられるもので,この表現と単変数多項式は一対一に対応します.

多変数多項式の場合も同様に表現出来ます.但し,1変数の場合の様な平坦なリストでCRE表現 は表現されず,CRE表現のリストによる複合リストとなります. 多変数の場合,重要な事は変数の 間に順序を入れる事です.これは辞書で見られる様な順番です.Maximaの場合は逆辞書式と呼ばれ

る順序がデフォルトで入っています.この順序ではアルファベットのzが一番大きく,aが一番小さ いというアルファベットの逆の順序で順番が付けられています.ここで,変数が二文字以上の場合, 最初に先頭の文字を比較します.そこで,先頭の文字が等しければ次の文字で比較します.途中で大 小関係が付くと,その順序で変数に順番が入ります.例えば,xxzとxxyの場合は頭の二つはxです が,最後がzとyで比較する為,z>yであれば,xxz>xxyとなります.

さて,多変数多項式のCRE表現に戻りますが,この場合は,再帰的な考えで処理します.例として 2xy+x−3で考えてみましょう.先ず,この多項式をxの多項式とすると(2y+ 1)x−3となるの で,CRE表現の第一段目は(x 1 2y+1 0 -3)となりますね.但し,第二成分の2y+ 1はCRE表現で はないので,これをCRE表現に変換した(y 1 2 0 1)で置換える必要があります.結局, (x 1 (y 1 2 0 1) 0 -3)が求めるCRE表現となります. 今度は,yの多項式として考えると,2xy+x−3なので, 中間的には(y 1 2x 0 x-3),中のxの式をCRE表現に置換えて, (y 1 (x 1 2) 0 (x 1 1 0 -3))が得ら れます.

この様に多変数の場合,CRE表現は順序をあやふやにしていると一意に定まるとは限りません.

変数に順序を入れて,大きな変数順に式を括れば,一意に定まります.その為,二つのCRE表現が与 えられた時に,それらの変数順序が異なれば,処理は非常に厄介な事になるのが判るかと思います.

その為,CRE表現を用いる函数に関しては,後の事も考えて主変数の設定を行う必要があります.

又,CRE表現の変数には,通常の算術演算子(+,-,*,/)や整数羃(ˆ )を持たないものを与えます.

その為,yˆ 2の様な式は変数に使えませんが,log(x)やcos(x+1)の様な函数は使えます.

ここで,変数順序はratvars函数で指定出来ます.ratvarsで指定しなかった場合,Maximaは逆ア ルファベット順の順序を入れています.

有理式は多項式の分数ですが,有理式のCRE表現の表現は,多項式の分母と分子に共通因子が無 く,分母の筆頭項(leading term)の係数を正にしたものとなります.

66 第9章 多項式について 以下に実例を示しましょう.

(%i1) r1: rat((y-1)/((y-x)*z^2+1));

y - 1

(%o1)/R/

---2 (y - x) z + 1 (%i2) r2: rat((y-1)/((x-y)*z^2+1));

y - 1

(%o2)/R/ -

---2 (y - x) z - 1 (%i3) r3:rat((y-1)/(-(y-z)*x^2+1));

y - 1

(%o3)/R/

---2 2

x z - x y + 1 (%i4) :lisp $r3;

((MRAT SIMP ($X $Y $Z) (X13180 Y13181 Z13182)) (Y13181 1 1 0 -1) Z13182 1 (X13180 2 1) 0 (Y13181 1 (X13180 2 -1) 0 1))

(%i4) t3:(y-1)/(-(y-z)*x^2+1);

y - 1

(%o4)

---2

x (z - y) + 1 (%i5) :lisp $t3;

((MTIMES SIMP)((MPLUS SIMP) -1 $Y) ((MEXPT SIMP)

((MPLUS SIMP) 1

((MTIMES SIMP)((MEXPT SIMP) $X 2)((MPLUS SIMP) ((MTIMES SIMP) -1 $Y) $Z)))

-1)) (%i5)

この例では順序が逆アルファベット順の為,変数の順序はz > y > xとなります.その為,zが主 変数となって式はzの多項式として纏められます.最初の二つの例では,(x−y)z²は,y > xとなる ので−(y−x)z²に並び替えられてしまいます.この際に,最も順序の高い項となるyz²の係数を正 にする為に,必要に応じて-1がかけられています. この例で示す様に,式がCRE表現,或いはCRE

表現の部分式を含む場合,記号/R/が行ラベルに続きます.

:lisp $r3;でCRE表現の内部表現を表示しています.先頭のMRATでCRE表現である事を示

し,その後で変数がX,Y,Zであり,X,Y,Zの順序が,整数13180,13181と1382で与えられている事 を示しています.この式ではZの値が最大の為,Zが主変数となります.尚,showratvarsはこの変数リ ストを返却する函数です.次に,(MATcdots)の後に分子となる式が来ます.この式は先頭がY13181

の為,重み13181が付いた変数Yの多項式で,後の1 1 0 -1から次数が1でその係数が1の項と,

次数が0で係数が-1である事が判ります.最後の副リストが分母の式となり,先頭がZ13182となっ ているので,主変数Zの多項式である事が判ります.以降,分子の時と同じ様に読めば,良いのです.

但し,式は変数の順序に従って読む必要があります.この例ではZ > Y > Xの順なので,Zがあれ ば, Zの多項式として表現し,Zが無くてYがあればYの多項式,ZとYが無ければXの多項式とし て帰納的に解釈します.

これに対し,同じ多項式の一般表現を最後に示しますが,この様に,非常に長いものとなっている 事が判ります.

尚,CRE表現で分母が整数の場合(CRE表現では,浮動小数点は有理数で近似されます),CRE表 現の内部表現は少し変化します.

(%i4) r1:rat((x-1)/5);

x - 1

(%o4)/R/

---5 (%i5) :lisp $r1;

((MRAT SIMP ($X) (X13157)) (X13157 1 1 0 -1) . 5)

この例れ示す様に,分子はx-1ですが,分子と分母の間に.が入っています. CRE表現では分子と 分母の間に,分母が整数の時に限って.を入れています. これはCRE表現の生成でconsが用いられ ている事を示しています.

68 第9章 多項式について

拡張CRE表現はtaylor級数を表現する為に用いられています.有理式の表記は正の整数では無

く,正か負の有理数となる様に拡張されており,係数はそれ自身,多項式と云うよりは,上で記述し た様に有理式となっています. これらは内部的に再帰的な多項式形式によって表現され,多項式形 式はCRE表現に類似していますが,より一般化したものです.尚,切り捨てられる次数の様な情報 も追加されています.

式を表示する際に,拡張CRE表現の場合は記号/T/が式の行ラベルに続きます.

(%i1) t1:taylor(exp(x),x,0,5);

2 3 4 5

x x x x

(%o1)/T/ 1 + x + -- + -- + -- + --- + . . .

2 6 24 120

(%i2) :lisp $t1;

((MRAT SIMP (((MEXPT SIMP) $%E $X) $X) (%e^x13162 X13163) (($X ((5 . 1)) 0 NIL X13163 . 2)) TRUNC)

PS (X13163 . 2) ((5 . 1)) ((0 . 1) 1 . 1) ((1 . 1) 1 . 1) ((2 . 1) 1 . 2) ((3 . 1) 1 . 6) ((4 . 1) 1 . 24) ((5 . 1) 1 . 120))

雰囲気はCRE表現に近いものですが,係数と羃のリストの書式がconsで結合されたリストであ り,他に,リストの第一成分にTaylor展開の様々な情報が追加されている事が判ります.