数値計算

四捨五入・切り上げの演算

0.0から0.9までの値を小数第1位で四捨五入する場合を考えます.小数点以下を切り捨てるINT関数があったとき,0.0から0.4は0.0,0.5から0.9は1.0としたいので,元の数値に0.5を足してINT関数を使います.切り上げするときは,元の数値に0.9を足してINT関数を使います.

一般的に,数値Nを小数点第n位で四捨五入する場合は, $\lfloor(N+0.5\cdot 10-n)\rfloor$ とします.切り上げる場合, $\lfloor(N+0.9\cdot 10-n)\rfloor$ とします.ただし, $\lfloor x\rfloor$ はxを超えない整数とします.

数値解析

方程式の近似解法

ここでは,方程式f(x)=0の近似解を求める方法を説明します.

二分法

xy平面上のy=f(x)のグラフが連続で,区間[a,b]でf(a)f(b)<0のとき,f(α)=0を満たす実数α(a<α<b)が少なくとも1つ存在するという中間値の定理を利用します.

中点を $c=\frac{a+b}{2}$ とします.f(c)=0であれば,cがf(x)=0の解です.f(a)f(c)<0であれば,区間[a,c]に,f(c)f(b)<0であれば,区間[c,b]に解があります.新しくとった区間の中点を再び求め,同様の操作を繰り返せば繰り返すほど中点の値はαに近づきます.

ただし,この方法では,定めた区間内に複数の解がある場合でも,解は1つしか計算できません.また,f(x)=0が重解をもつ場合,その前後の値a,bはf(a)f(b)>0となるため,解が求められません.よって,実際に計算する前にグラフの概形を調べ,区間を適切に定める必要があります.

二分法のグラフ

ニュートン法

任意の実数aに対して,関数f(x)のx=aにおける微分係数 $f^{\prime}(a)$ が存在する場合において,方程式f(x)=0の解αの近似値を考えます.まず,αに近い値 $x_{1}$ をとり,xy平面上の関数y=f(x)の,グラフ上の点 $\left(x_{1},f(x_{1})\right)$ における接線がx軸と交わる点のx座標を $x_{2}$ とします.接線の方程式は $y=f^{\prime}(x_{1})(x-x_{1})+f(x_{1})$ より, $x_{2}=x_{1}-\frac{f(x_{1})}{f^{\prime}(x_{1})}$ です.

次に,点 $\left(x_{1},f(x_{2})\right)$ における接線がx軸と交わる点のx座標を $x_{3}$ とし,同様の計算を繰り返します.すると,数列 $\{x_{n}\}$ の漸化式は $x_{n+1}=x_{n}-\frac{f(x_{n})}{f^{\prime}(x_{n})}$ となります.

ニュートン法のグラフ

数列 $\{x_{n}\}$ は, $x_{1}$ (初期値)がαに十分に近いとき,多くの場合は急速にαの値に近づきます.

誤差の限界をεとします.適当な初期値aを与え, $b=a-\frac{f(a)}{f^{\prime}(a)}$ を求め,|b-a|≦εならbを近似解とします.そうでなければ,aにbを代入して再びbを計算します.これを繰り返すとαの近似値が得られます.

ただし,初期値があまりにもαと違う場合や,微分係数が存在しないときはこの方法が使えません.

数値積分法

コンピュータは高い計算能力をもちますが,無限に計算を続けることはできません.よって,微積分の理論のように「無限に」計算を続けた結果の値は求められません.そのため,計算結果は近似値となります.

関数f(x)について, $\int_{a}^{b}f(x)\,dx$ を近似的に求める方法を数値積分法と言います.

区分求積法

区間[a,b]をn等分し,分点を小さい方から順に $x_{0},x_{1},\cdots,x_{n-1}$ とし, $h=\frac{b-a}{n}$ とします.このとき,左からi番目(0≦i≦n-1)の小区間 $[x_{i-1},x_{i}$ における面積は長方形として近似できます.近似する長方形の形は,図のように薄い長方形と濃い長方形が考えられます.

前者は $\sum_{i=0}^{n-1}f\left(x_{i-1}\right)h$ となり,後者は $\sum_{i=0}^{n-1}f\left(x_{i}\right)h$ です.nの値が大きくなるほど求める積分の値に近づきますが,n→∞という極限を考えないと, $\sum_{i=0}^{n-1}f\left(x_{i-1}\right)h<\int_{a}^{b}f(x)\,dx<\sum_{i=0}^{n-1}f\left(x_{i}\right)h$ です.

区分求積法の近似図

台形公式

考え方は区分求積法と同じですが,台形を用いて近似します.区間 $[x_{i-1},x_{i}]$ の台形の面積を,全区分で足したものが求める値です.

つまり, $\int_{a}^{b}f(x)\,dx\approx\frac{b-a}{2n}f\left(x_{0}\right)+2\left(f\left(x_{1}\right)+f\left(x_{2}\right)+\cdots+f\left(x_{n-2}\right)\right)+f\left(x_{n-1}\right)$ です.

台形公式の近似図

シンプソンの公式

放物線を用いて近似します.区間[a,b]を2n等分し,分点を小さい方から順に $x_{0},x_{1},\cdots,x_{2n-1}$ とします.区間 $[x_{2i-2},x_{2i}]$ において, 3点 $\left(x_{2i-2},y_{2i-2}\right)$ , $\left(x_{2i-1},y_{2i-1}\right)$ , $\left(x_{2i},y_{2i}\right)$ を通る放物線とx軸に狭まれる部分の面積は, $h=\frac{b-a}{2n}$ とすると, $\frac{h}{3}\left(f\left(x_{2i-2}\right)+4f\left(x_{2i-1}\right)+f\left(x_{2i}\right)\right)$ です.

つまり, $\int_{a}^{b}f(x)\,dx\approx\frac{b-a}{6n}f\left(x_{0}\right)+4\left(f\left(x_{1}\right)+f\left(x_{3}\right)+\cdots+f\left(x_{2n-3}\right)\right)$ $+2\left(f\left(x_{2}\right)+f\left(x_{4}\right)+\cdots+f\left(x_{2n-2}\right)\right)+f\left(x_{2n-1}\right)$ です.

シンプソンの近似図

グラフ理論

グラフとは

グラフ(G)は,有限個の点(V)辺(E)から構成されます.点はグラフを構成する各頂点で,辺は頂点同士を結びます.一般に,グラフはG=(V,E)と定義します.

無向グラフと有向グラフ

辺に向きがないものを無向グラフ(上図左),向きがあるものを有向グラフ(上図右)と言います.

この図の場合,e1=(v1,v2),e2=(v2,v3),e3=(v1,v3)と表記します.一般に,e=(vi,vj)のvi,vjをそれぞれ端点と言います.

連続した点と辺を結んだものを歩道と言い,次の種類があります.

上図は両方とも閉路になっており,いずれか1つの辺を除くと経路になります.

グラフを構成する全ての辺を1度だけ通るような小道をもつグラフをオイラーグラフと言います.いわゆる「一筆書き」ができるグラフです.さらに,グラフを構成する全ての点を通る閉路をもつグラフをハミルトングラフと言います.上図はハミルトングラフでもあります.

根付き木とは,をもつ木です.木を構成する点の内,最頂点の位置にあるもので,上図右の例ではv1が根です.

また,根からでるそれぞれの経路をと言います.上図では,e1,e2,e3が枝にあたります.

グラフの種類と考え方

グラフG=(V,E)において,節点の集合を2つの部分集合V1,V2に分割し,Gのどの枝も一方の端点がV1に,他方の端点がV2に属するようにできるとき,Gを2部グラフと言います.

また,グラフの各枝に長さが与えられているとき,全ての節点を張る木の中で,枝の長さの和が最小である木を最短木と言います.最短木に閉路があってはいけません.

グラフのある点(出発点)から別の点(目的地)までの最短距離を計算する方法にダイクストラ法があります.

Column

グラフ理論の応用例として階層型・ネットワーク型データベースがあります.

待ち行列理論

待ち行列とは

銀行の窓口やコンビニのレジでは,客がランダムに到着して,窓口で精算や事務処理を行ってもらい,その人へのサービスが終わったら,並んでいた次の客がサービスを受けます.実際の待ち行列とは,このようなもの以外に,情報がコンピュータ上で処理を待っている場合にも適用できるため,情報処理にも応用できます.なお,これ以降,考える待ち行列は,先に並んだ人からサービスを受ける(FCFS)ものとします.

待ち行列にはランダムに人がきますが,具体的には以下の条件を満たします.

また,並んでいる人が突然列を抜けることも考えません.

待ち行列には色々な性質があり,ケンドールの記号を用いてA/B/c/dと表します.

A
到着の分布を表します.Mはポアソン分布(指数分布),Erはr次のアーラン分布,Dは一点分布,GIは独立な一般分布です.
B
サービスの分布を表します.使われる記号はAと同じです.
c
窓口の数を表します.数値を表す記号か数字を書きます.
d
許される待ち人数(待ち行列の長さ)です.無限である場合は省略可能です.

指数分布に従うサービスは,最悪の場合の(理論上「現実にあるサービスとしては最もいい加減な」)サービスと考えるため,解析が容易であり,よく利用されます.

なお,待ち行列理論によって計算される諸量は,時間を長くとったときの結果を示しているため,実際の利用にあたっては注意が必要です.待ち行列が空(誰も並んでいない)の状態から始まるときは過大評価,客の到着に相関がある(無記憶性が保証されない)場合は過小評価になります.また,到着率やサービス率が変化するときは,時間帯を区切って使う必要があります.

次に,待ち行列の尺度を説明します.

平均到着率λは,単位時間あたりにどの程度の人(もの)が到着するかを表します.トランザクションの平均到着間隔をtaとおくと, $\lambda=\frac{1}{t_{a}}$ です.

平均処理率(平均サービス率)μは,単位時間あたりに処理可能な人(もの)を表します.窓口の平均サービス時間(平均処理時間)をtsとくおと, $\mu=\frac{1}{t_{s}}$ です.

利用率ρは,窓口がどれだけ利用されているかを表します. $\rho=\frac{\lambda}{\mu}$ で,ρ>1だと待ち行列はいつまでたっても解消されません.

M/M/1/∞型の待ち行列

M/M/1型では,待ち行列の待ち人数と期待値Qと待ち時間の期待値Wについて,Q=λW(リトルの公式)が成立します.

サービスを受けるまでの待ち時間は $W=\frac{\rho}{\mu-\lambda}=\frac{\rho}{\mu(1-\rho)}$ と計算され,サービスを受け終わるまでの滞留時間 $U=W+\frac{1}{\mu}$ となります.

また,待っている人(もの)の期待値は $Q=\frac{\rho^{2}}{1-\rho}$ であり,サービスを受けている人も含めた待ち行列の人数(滞留人数または系内人数)は $L=\frac{\rho}{1-\rho}$ です.