三角領域上の二次元完全対称積分則
2010SE098 木村 綾乃
指導教員：杉浦洋と書き，アトムと呼ぶ．D の部分集合 A ⊂ D がこの 6 つのアフィン変換で不変なとき，A は FS(Fully Symmetric:
2 次元領域上の関数の定積分を求めることは，数学にお完全対称) 集合であると言う．A が FS 集合なら，p ∈ A ⇒ける基本的な問題である．平面上の任意の多角形領域は⟨p⟩ ⊂ A である．FS 集合はアトムを単位とするので，同三角領域に分割できる．したがって，三角領域上の数値一標本点数の一般の公式と比べ，パラメーター数は少な積分法を作れば多角形領域上の積分ができる．任意の単く，設計も実装も容易となる．式 (2) の積分公式 Qn (D)連結有界領域上の積分は，領域を多角形領域で近似する．
は，一般に基本三角領域 ∆ から三角領域 D へ，アフィまたは，変数変換で多角形に変換することにより，三角ン変換 φ に依存せず一意に定まる．アトムが FS 公式の領域上の積分に帰着する．
標本点からなるとき，そのアトムを公式の標本アトムと本論文では，適応型積分法 [1] を考える．適応型積分法
いう．のアルゴリズムは「精度が低いと判定された小三角形を２分する」という操作を繰り返して，必要な精度を達成 4 再利用性する．このような数値積分法を用いる効率の良い積分公
三角領域 D = D(a, b, c) 上での近似積分 Qn (D)f の精式を設計することが，本論文の目標である．
度が悪いときは，D の頂点と重心 g を通る直線で小三角
形 D0 と D1 に 2 分し，より，精度の高い近似積分
2 三角形領域上の積分則

1

はじめに2.1

数値積分則の設計

Qn (D0 )f + Qn (D1 )f ∼= Q(D)fxy− 平面上の 3 点 α = (0, 0), β = (1, 0), γ = (0, 1) を頂点とする三角形領域 ∆ を基本三角領域と呼ぶ．n 個の標本点
π i = (ξi , ηi ) ∈ ∆ (1 ≤ i ≤ n)と重み ρi (1 ≤ i ≤ n) による積分公式を特別に

In f =n∑

ρl f (π l )l=1と書き，基本公式と言う．これを変数変換により任意の三角領域の近似積分に用いる．点 a, b, c を頂点とする三角領域 D = D(a, b, c) の面積を S とする．∆ から D へのアフィン変換 φ : q = sα + tβ + uγ → p = sa + tb + uc
により，∫∫∫ ∫Q(D)f = f (p)dxdy = 2Sf (φ(q))dtdu.
D∆n∑ρi f (φ(ξi , ηi )) ∼= Q(D)fn

2

点 p の重心座標を (x, y, z) とすると

p = xa + yb + zc
b+c2
= xa + (y − z)b + 2zd.

= xa + (y − z)b + 2z

この右辺に積分則 In を用いて積分公式

Qn (D)f = 2Sを得る。この領域分割を D0 , D1 以下にも再帰的に繰り返し，十分精度の高い近似積分値が得られる．このような領域分割を再帰的に繰り返す近似積分法を適用型積分則という．アトム ⟨p⟩ が Qn (D) の標本アトムであるとする．
⟨p⟩ の全ての点が Qn (D0 ) か Qn (D1 ) の標本点になっていれば，⟨p⟩ は再利用可能であるという．Qn (D) の全ての標
本点が Qn (D0 )，Qn (D1 ) で再利用可能であるとき Qn (D)を R 公式という．また，その標本点集合を R 集合という．
R 公式は標本点上で一度計算した関数値が，領域分割の過程で再利用できるため効率的である．D = D(a, b, c)の頂点 a を選び，a と g を通る直線で D を分割すると小三角形 D1 = D(a, b, d) と D2 = D(a, d, c) ができる．ここで，d = b+ｃ は点 b,c の中点である．Q (D) の標本(1)ゆえに p の D1 における重心座標は (x, y − z, 2z) である．
y −z ≥ 0 のとき p ∈ D1 である．さらに，(x, y −z, 2z)を得る．アフィン変換で，x, y の k 次の多項式は t, u のk 次多項式に変換されるから，In が s 次公式なら Qn (D) が Qn (D1 ) の標本点の重心座標なら，p は Qn (D1 ) で再利用される．同様に (x, 2y, z − y) は p の D2 における重も s 次公式である．
心座標である．z − y ≥ 0 のとき，p ∈ D２ である．さら3 FS(Fully Symmetric：完全対称) 集合に，(x, 2y, z −y) が Qn (D2 ) の標本点の重心座標なら p は
三角領域 D をそれ自身に移すアフィン変換は重心座標 Qn (D2 ) で再利用される．以上により，Qn (D) の標本点の置換であり，その数は頂点を順列の数と等しく 6 であ ⟨p⟩ = ⟨x, y, z⟩ (x ≤ y ≤ z) が再利用可能であるための必る．点 p ∈ D の重心座標を (x, y, z) とし，その成分を 要十分条件は，三つのアトム ⟨p0 ⟩ = ⟨2x, y − x, z⟩, ⟨p1 ⟩ =⟨2x, y, z − x⟩, ⟨p2 ⟩ = ⟨x, 2y, z − y⟩ が Qn (D) の標本アト置換した座標全体をムであることである。Qn (D) が R 公式であるための必要⟨p⟩ = ⟨x, y, z⟩
十分条件は，Qn (D) の標本アトム ⟨p⟩ から出る三本の矢= {(x, y, z), (x, z, y), (y, z, x), (y, z, x), (z, x, y), (z, y, x)} 印の終点が再び Qn (D) の標本アトムであることである．
i=1

5

アトムの親子グラフとギルドグラフ

アトム集合 X にあらわれるすべての関係 p → q(p, q ∈X) を矢印で結んだものを X の親子グラフと呼び G(X)と書く．p は q の子であり，q は p の親である．R 集合を系統的に作り出す方法として，それ自身 R 集合である
原子集合 X の親子グラフ G(X) を作り，その部分グラフG(P )，P ⊂ X の再利用性を判定することである．X としては自然数 n に対して

Xn = {<i j k, , >: i + j + k = n, 0 ≤ i ≤ j ≤ k}
n n n

6.1

優良公式の選抜作成した FSR 則について分割コストＣと誤差係数Ｅを計算した．領域分割 1 回あたりＣ点の標本点が追加されるとき，Ｅを公式の分割コストという．
三角領域 D 上での積分に用いる標本点集合を P ，D を二等分した領域 D1 ，D2 上での積分に用いる標本点集合をそれぞれ P1 ，P2 とすると，R 公式では P1 ∪ P2 ⊃ P であり，P の点はすべて P1 ，P2 で再利用される．そして，再利用された点以外の点の数
Ｃ = |(P1 ∪ P2 ) − P |が考えられる．< ni , nj , nk > に対し再利用関係をもつ <2i j k−i
i 2j k−j
2i j−i kn , n , n >, < n , n , n >, < n , n , n > はすべて Xnが分割コストである．s 次則は正確に積分できない s + 1次多項式をもつ．基本領域Δにおける単項式の積分誤差をの元であるから Xn は R 集合である．この節では，分母∫∫が n = 30 以下の全てのアトムからなる集合を A30 とし，
k l
xk y l dxdy(k, l ≥ 0)
Ek,l = Qn (x y ) −その親子グラフ G(A30 ) について考察する．野田 [3] は，D手作業の限界から，n = 20 であった．総アトム数は 788とするとき，s + 1 次単項式に対する積分誤差の絶対値のである．n が既約共通分母となっているアトムからなる総和
部分集合
k+l=s+1∑
Ｅ=|Ek,l |i j kYn = {< , , >: GCD(i, j, k, n) = 1} ⊂ Xn
k≥0,l≥0n n n
を s 次則 Qn の誤差係数と呼ぶ．我々は，構成した 1013 個を「n 系」と呼ぶ．GCD は最大公約数である．明らかにの FSR 則から上記の s, Ｃ, E を基準にして優良公式を選p ∈ Yn , p → q なら抜する．s は大きいほど良く，Ｃと E は小さいほど良い．
{
ここでは，全リストから劣悪公式を取り除くことで，そYn，n は奇数p∈れを達成する．劣悪公式とは，s, Ｃ, E のいずれにおいてYn ∪ Y n2 ，n は偶数もその公式より優れた公式が存在する公式のことである．
である．ゆえに，G(A30 ) は 30 以下のすべての奇数 K に関する部分グラフ

7

おわりにこれまで，野田 [3] の FMR 集合に関するグラフ理論を学んできた．野田は，その理論に基づき，手で親子グラフを描き，重心座標の分母が 20 以下の標本点をもつすべに分割される．このアトム集合 ZK を「K 系統」と呼ぶ．ての FMR 集合を列挙した．
G(ZK ) において，2 つのアトム p, q が双方向の有向路で今回は，親子グラフをコンピュータ上に実現し，ギル結ばれるとき，兄弟という．特別に p 自身は p と兄弟でドを極大強連結集合として抽出し，FMR 集合の列挙を自あるとする．p と兄弟アトム全体 K(p) を p のギルドと言動化することを目標とした．その結果 26 個の優良 FMRう．p が R 集合 A に含まれるなら K(p) ⊂ A であるので，公式を得た．積分次数は最低 1 次最高 8 次で，様々な精R 集合はギルドを単位に構成される．ギルド間にもアト度要求に応じることができる．
ムの親子関係を継承した親子関係がある．これによりギルドをノードとするギルドグラフが得られる．{0, 0, 1} の 8 参考文献
みからなるギルドはそれ自身 R 集合である．このような [1] A.Genz and R.Cools:An Adaptive Numerical Cuギルドを根ギルドという．
bature Algorithm for Simplices，ACM Transactions

G(ZK )，ZK = YK ∪ Y2K ∪ … ∪ YLK ，LK ≤ 30 < 2LK

6R 集合構成アルゴリズム

on Mathemtical Software，vol.29，no.3，pp.297308(2003)．

まず，各系統でギルドグラフに基づき，点数 40 以下の[2] 古田純也, 長方形領域の再利用可能積分公式 南山
R 集合の表を作る．ギルドグラフは Mathematica のグラ
大学情報理工学部 情報システム数理学科 2012 年度
フ処理機能を用いて作成，描画した [2]．各系統から R 集
卒業論文, 数値計算の基礎と応用合を 1 つずつ選んで和集合をとると，A30 の R 集合が得られる．ただし，各系統は空集合を R 集合として含むも [3] 野田恭代，二次元完全対称積分則の設計, 南山大学数理情報学部数理科学科 2011 年度卒業論文, 数値計算のとする．の基礎と応用
本論文では，その中から 40 点以下の R 集合をすべて構成した．その数は 1013 個であった．これらすべてに対し，積分則の重みを計算し，FSR 則を作った．そして，次数s は達成可能な最大次数を選んだ．