Hcc における近似アルゴリズムの性能評価

(1)

2004 年度卒業論文

Hcc における近似アルゴリズムの性能評価

提出日 :2005 年 2 月 2 日指導 : 上田和紀教授

早稲田大学

理工学部コンピュータネットワーク工学科学籍番号 :G00P007-5

飯盛幸太郎

(2)

図目次

2.1 オイラー法 . . . . 2

2.2 ルンゲ・クッタ法 . . . . 3

3.1 5次式Δx=5 ＆ 10次式Δx=5. . . . 4

3.2 20次式Δx=5 ＆ sinΔx=5 . . . . 5

3.3 log Δx=5 . . . . 5

3.4 誤差5次式Δx=5 . . . . 5

3.5 誤差10次式Δx=5 . . . . 6

3.6 誤差20次式Δx=5 . . . . 6

3.7 誤差sinΔx=5 . . . . 6

3.8 誤差log Δx=5 . . . . 7

3.9 10次式Δx=1 ＆ 10次式Δx=2 . . . . 8

3.10 10次式Δx=3 ＆ 10次式Δx=4 . . . . 8

3.11 10次式Δx=5 . . . . 8

3.12 sin Δx=1＆ sinΔx=2 . . . . 9

3.13 sinΔx=3＆ sin Δx=4 . . . . 9

3.14 sin Δx=5 . . . . 9

3.15 誤差10次式Δx=1 . . . . 10

3.16 誤差10次式Δx=2 . . . . 10

3.17 誤差10次式Δx=3 . . . . 11

3.18 誤差10次式Δx=4 . . . . 11

3.19 誤差10次式Δx=5 . . . . 11

3.20 5次式Δx=4 ＆ 10次式Δx=2. . . . 12

3.21 20次式Δx=1 . . . . 13

3.22 誤差5次式Δx=4 . . . . 13

3.23 誤差10次式Δx=2 . . . . 13

3.24 誤差20次式Δx=1 . . . . 14

3.25 おもりの数3個オイラー法/ ルンゲ・クッタ法 . . . . 15

3.26 おもりの数5個オイラー法/ ルンゲ・クッタ法 . . . . 15

2

(4)

表目次

(5)

概要

hybrid ccは常微分方程式を与えることにより、その解を示してくれる言語であ

る。その解を求めるためにいくつかの近似アルゴリズムが用意されている。それらは、オイラー法、ルンゲ・クッタ法、ベアストウ法などである。それぞれ全く異なった近似方法を行うため、それぞれがどのような条件でどの程度の性能であるか、ということは実際に実験を行って結果をみることで初めて明らかになる。

今回は、数学的にも有名でよく用いられるオイラー法、ルンゲ・クッタ法について様々な条件下で実験を行い、多項式においてその結果で性能を比較してみた。

様々な条件とは関数の次元を5次元から20次元まで変化させてみること、近似におけるxの変化量を0.1から0.5まで変化させることである。また、簡単な非線形関数の例としてsin関数とlog関数のデータも収集した。こうした基本的な関数のデータを踏まえた上で実際のアニメーションで用いる関数もいくつか実験を行い、その性能を比較した。

今回は主に関数をグラフィックにしたときに問題になる程度の誤差を見るので、

上3桁以下の誤差は無視する。しかし、厳密な数値の誤差についても多少後半で観察を行う。この条件を元に、c言語を用いた理論値（丸め誤差はあるが）との誤差と、実行時間の様子を観察、考察した。

その結果、複雑な関数、刻みを大きくするほど理論値との誤差はルンゲ・クッタ法の方がオイラー法よりも精度の高い近似ができることがわかった。また、実行時間も含めた総合的な性能の向上を図るために、オイラー法の誤差の軽減、ルンゲ・クッタ法の実行時間に対していくつか提案をした。

(6)

第 1 _{章序論}

1.1 研究の目的と意義

今回の研究は、hybrid cc を使う上で用いる常微分方程式の近似方法がどのような条件下でどの程度の誤差、実行時間が現れるのかをあらかじめ把握しておく

ことがhybrid cc を用いる上で必要不可欠なものであるから、その指標を作るこ

とが目的である。もしいずれかのアルゴリズムがある特徴に対して有効ならば、

今後そのようなことを考慮して最適な近似法を用いることができる。

1.2 本論文の構成

(7)

第 2 _{章実験に先立つ準備}

2.1 オイラー法

オイラー法とは、図2.1のような近似の方法である。あるx =x_nから微小幅 Δx先の値を、その点の接線から求めて近似を行う。テイラー展開の第二項以降を省略しているので、(Δx)² 程度の誤差が累積する。したがって誤差を小さくするには Δx を小さくすればよいが、計算時間が増加し、また累積誤差が増加する。

図 2.1: オイラー法

2.2 _{ルンゲ・クッタ法}

ルンゲ・クッタ法の数学的な意味を以下に示す。

dy/dx=f(x, y)

2

(8)

この微分方程式の初期値が(x₀, y₀)で、xを Δx進ませた座標を(x₀+Δx, y₁)とし、両辺積分すると

y₁ =y₀ +

Z _x₀_+Δ_x

x0

f(x)dx

となる。この式はxが Δxだけ進むと、yはその区間の元関数の積分値だけ増加することを意味している。図2.2にあるように、x0, x1,Δx, fa, fb, fcとすると、シンプソンの公式（ここでの説明は省く）を用いてこの面積を計算すると、

ΔS=h/6(f₁+ 4f₂+f₃) となる。以上のことから、

y₁ =y₀+ h

6｛f(x₀) + 4f(x₀+h

2) +f(x₀+h)｝

となり、この式がルンゲ・クッタ法の近似式である。

図 2.2: ルンゲ・クッタ法

(9)

第 3 _{章実験}

3.1 実験方法

今回実験を行った関数は、5次関数、10次関数、20次関数、sin関数、log関数である。具体的には

y=x−x²+x³−x⁴+x⁵/10

y=x−x²+x³−x⁴+x⁵−x⁶+x⁷−x⁸+x⁹−x¹⁰/10

y=x−x²+x³−x⁴+x⁵−x⁶+x⁷−x⁸+x⁹−x¹⁰+x¹¹−x¹²+x¹³−x¹⁴+ x¹⁵−x¹⁶+x¹⁷−x¹⁸+x¹⁹−x²⁰/10

y=sinx y=log(x+ 1)

のデータを収集した。なおそれぞれ区間は0 ≤ x ≤ 10で測定した。また、

hybrid cc に与える微分方程式は一回微分の方程式を渡した。（例：５次式なら

y⁰ = 1−2x+ 3x²−4x³ + 5x⁴）しかし、sinxだけは例外として、y⁰⁰ =−yという形で渡してある。

3.2 _{次数の影響}

まず、刻み幅固定で次数をあげ、その近似の様子を観察してみた。

図 3.1: 5次式Δx=5＆ 10次式Δx=5

4

(10)

図 3.2: 20次式Δx=5 ＆ sinΔx=5

図 3.3: logΔx=5

上の図のように、ルンゲ・クッタ法はほぼ理論値と誤差はないことが分かった。

少なくとも上3桁の誤差は0であった。それに対し、オイラー法は目で見て明らかなほどの誤差がある。以下にその誤差の様子をグラフにしてみた。

図 3.4: 誤差5次式Δx=5

(11)

図 3.7: 誤差sin Δx=5

6

(12)

図 3.8: 誤差log Δx=5

上のグラフのように、オイラー法は、f⁰(x)が正から負、または負から正に変わるときに大きな誤差を生じる。またそれは、f⁰⁰(x)の値が大きいときほど誤差も大きくなることがわかった。それは3.1で述べたオイラー法の近似の仕組みを考えると納得できる結果であった。つまり、ある点での接線で近似をするので、

その接線の傾きの変化の激しさによっては、とても大きな誤差を生み出すことになる。実験でもそのことが明らかになった。場合によっては理論値にたいして、

100％以上の誤差を生じることもあった。一方、logのように比較的接線の傾きの変化が激しくないものについてはそこまで大きな誤差は生じない。

また、実行時間についても以下の表にまとめてみた。実行時間については、近似方法、関数の違いによらずほぼ同じであった。

近似方法 5次式 10次式 20次式 sin log オイラー法 0.06 0.06 0.07 0.07 0.05 ルンゲ・クッタ法 0.06 0.07 0.07 0.07 0.05

実行時間（CPU時間）

3.3 刻み幅の影響

次に、同じ関数について刻み幅を変え、誤差の様子を観察してみた。関数は10 次式とsinのグラフで比較を行った。

(13)

図 3.9: 10次式Δx=1 ＆ 10次式Δx=2

図 3.10: 10次式Δx=3 ＆ 10次式Δx=4

図 3.11: 10次式Δx=5

8

(14)

図 3.12: sin Δx=1 ＆ sin Δx=2

図 3.13: sinΔx=3 ＆ sinΔx=4

図 3.14: sin Δx=5

以上の結果から、10次式については刻み幅を細かくすることにより誤差を軽減できることがわかった。しかし、sin関数についてはオイラー法は刻み幅を細か

(15)

くしてもうまく近似できない。これはずれというよりも近似方法に根本的な問題があると考えられる。刻み幅の変化がどの程度誤差に影響しているか、以下に誤差のグラフも示す。

図 3.15: 誤差10次式Δx=1

図 3.16: 誤差10次式Δx=2

10

(16)

図 3.17: 誤差10次式Δx=3

図 3.18: 誤差10次式Δx=4

図 3.19: 誤差10次式Δx=5

オイラー法の誤差を見比べてみると、最終的に大きくなった誤差は今回の実験

(17)

結果においてはほぼ比例関係にある。もちろん、これは関数の形によりまちまちであるとは思われるが、おおよその目安として、誤差は刻み幅に比例して大きくなると言うことができる。

ルンゲ・クッタ法に関しては Δx = 0.1〜Δx = 0.3は誤差は全くの0であっ

た。Δx= 0.4以降も誤差は1％未満であることが確認できた。ルンゲ・クッタ法

に関してはグラフィックでの目立つ誤差はないと言える。オイラー法も含め、細かい誤差については後の考察で述べたいと思う。

また、実行時間も以下に表として掲載しておく。

近似方法 Δx= 0.1 Δx= 0.2 Δx= 0.3 Δx= 0.4 Δx= 0.5 オイラー法 0.09 0.08 0.07 0.07 0.06 ルンゲ・クッタ法 0.09 0.07 0.07 0.07 0.07

10次式の実行時間（CPU時間）

3.4 次数と刻み幅の複合影響

次に、次数と刻み幅を同時に変化させたときの様子を観察する。選んだサンプルは、5次式Δx=0.4、10次式Δx=0.2、20次式Δx=0.1の3つである。以下にその関数のグラフを示す。

図 3.20: 5次式Δx=4 ＆ 10次式Δx=2

12

(18)

図 3.21: 20次式Δx=1

今回の比較は、次数と刻み幅を逆向きに変化させたときに誤差がどうなるかを比較するために行った。上のグラフでは見た目にはさほどの誤差はないように見える。以下に、誤差の様子をグラフにしてみた。

図 3.23: 誤差10次式Δx=2

(19)

図 3.24: 誤差20次式Δx=1

オイラー法について、上の誤差のグラフを見ると、10次式Δx=0.2のグラフの最後のサンプルだけ飛び出ているが、誤差は最大150％程度に収まっている。この3つの近似はほぼ同程度の精度といってよいだろう。つまり、次数を2倍にすることと刻み幅を2倍にすることは同程度に誤差の影響を及ぼすと推測できる。

また、飛びぬけてしまったサンプルのようなものに対し、後の考察でどの程度の値のf⁰(x)で何％程度の誤差になってしまうのかを検証する。

3.5 実際のアニメーションでの誤差

アニメーションの例として、いくつかのおもりがバネで連結された状況を考え、

それぞれのおもりの動きを表現してみた。オイラー法においては、おもりが3個の時点で物理的におかしな動きをし、近似ができているとは言えないほどであった。一方、ルンゲ・クッタ法ではおもりが3個、5個の状況でも上手く表現できていた。しかし、ルンゲ・クッタ法でもおもりが10個になると近似はできなくなった。

おもりが3個、5個のときは実行時間にほぼ差はなかったが、おもりが10個になると2倍ほどルンゲ・クッタの方が処理が遅くなった。しかし、おもり10個ではどちらのアルゴリズムも近似ができているとはいい難く、処理の速さはもはや問題ではない。

このような実験から、実行時間についてはオイラー法の方が性能がよいが、実行時間に差が出るのはかなり関数が複雑になってからだと思われる。一方、近似の誤差に関しては関数がそこまで複雑でなくても生じてくる。このことを考えると、よほどオイラー法にとって都合のいい関数でなければ実行時間、計算誤差を合わせて考えた総合的な性能もルンゲ・クッタ法の方が優れていると思われる。

14

(20)

図 3.25: おもりの数3個オイラー法 /ルンゲ・クッタ法

図 3.26: おもりの数5個オイラー法 /ルンゲ・クッタ法

以上の実験はすべてΔx=0.1で行った。また、以下に実行時間についての表を掲載する。

近似方法 /おもりの数 3個 5個 10個オイラー法 0.15 0.19 0.14 ルンゲ・クッタ法 0.15 0.21 0.26

実行時間 (CPU時間)

(21)

第 4 _{章考察}

4.1 オイラー法の誤差と関数の次数、刻み幅の関係

4.4の「次数と刻み幅の複合影響」で、グラフを観察し、刻み幅、次数それぞれについて誤差と比例関係にあるのではないかと推測したが、逆に数式でこのことを検証してみる。

n次の関数を刻み幅Δxでオイラー法で近似することを考える。簡単のために n次の関数は

y=f(x) =xⁿ

として考える。オイラー法の原理からx=xから Δx進ませたときに出る誤差は f(x+Δx)−f(x)−f⁰(x)Δx

である。これをy=xⁿに当てはめると

(x+Δx)ⁿ−xⁿ−nxⁿ⁻¹Δx よって、この区間において生じる誤差は、関数の値に対して

(x+Δx)ⁿ−xⁿ−nxⁿ⁻¹Δx (x+Δx)ⁿ

の割合である。ここで分母は(Δx)² 以下、分子は(Δx)³ 以下の項を切り捨てると、

n(n−1)(Δx)² 2x²+ 2nxΔx と近似することができる。

ここで、この式のnと Δxに注目すると、どちらも分母、分子で同じ次数になっている。このことからnを2倍にすることとΔxを2倍にすることはほぼ等価であるとみなすことができる。もちろん、Δxがそこまで微小でないことや、

粗い近似を行っているので厳密ではないが、これを指標にすることができる。

結果、推測したように刻み幅、次数と誤差がそれぞれ比例しているとは言えないが、刻み幅を2倍することと、次数を2倍にすることはおよそ等価であることが分かった。

16

(22)

4.2

(23)

Hcc における近似アルゴリズムの性能評価

2004 年度 卒業論文