3 二分法による方程式の解(上級者向選択課題)

これは上級者向の選択課題で,無理にプログラムを作成しなくても良い.もし,このプロ グラムができたならば,他の課題は実施しなくても良い.これだけできれば十分である.

ここでは,コンピューターを用いた方程式の解をもとめるプログラムを作成する.二分法 と言う方法を示す.このプログラムが作れるようになると,コンピューターは便利なもの であると分かるだろう.

3.1 二分法の原理

3.1.1 方程式の解

まずは,単純な方程式を考えよう.次の3次方程式

$\displaystyle x^3-3x^2+9x-8=0$ (1)

の解を求めることを考える.

一般に,方程式は次の形に書き表すことができる.

$\displaystyle f(x)=0$ (2)

この方程式の解$ x$をコンピューターで求める.もし,方程式の右辺がゼロでない場合は, 左辺へ移項して式(2)の形にできる.方程式 (2)を解くことは,関数$ f(x)$ の値がゼロになる$ x$の値を捜す-- と言い換えることができる.実際コンピューターを使った数値計算では,$ f(x)$の値がゼ ロとなる$ x$を捜すことになる.コンピューターでは,関数$ y= f(x)$がx軸と交わる点, 即ち$ f(x)=0$を反復(ループ)計算を用いて捜す.この点$ x$を捜す方法には,いくつかあ るが,ここでは最も単純な二分法を示す.

解くべき方程式(1)をグラフにすると,図 2のようになる.もちろん,グラフにした関数は,

$\displaystyle f(x)=x^3-3x^2+9x-8$ (3)

である.$ x$軸との交点の値は, $ x=1.1659055841222127171\cdots$である.これが,元の 方程式(1)の解になっている.
図 2: $ f(x)=x^3-3x^2+9x-8$の関数.x軸との交点が解である.
\includegraphics[keepaspectratio, scale=0.8]{figure/ShapeOfFunction.eps}

3.1.2 二分法

二分法の原理は非常に単純であるが,場合によっては非常に強力な方法である.これ は,区間 $ a\leq x\leq b$で連続な関数$ f(x)$の値が,

$\displaystyle f(a)f(b)\leq 0$ (4)

ならば,$ f(x)=0$となる$ x$があるということを使う.

実際の数値計算は, $ f(a)f(b)\leq 0$であるような2点 $ a,\,b(a\leq b)$から出発する. そして,区間$ [a,\,b]$を2分する点$ c=(a+b)/2$に対して,$ f(c)$を計算を行う. $ f(c)f(a)\leq 0$ならば$ b$$ c$と置き換え, $ f(c)f(a)\geq 0$ならば$ a$$ c$と置き換 える.絶えず,区間$ [a,b]$の間に解があるようにするのである.この操作を繰り返して, 区間の幅$ \vert b-a\vert$が与えられた値 $ \varepsilon$2よりも小さくなったならば,計算を終了する.例えば, $ \varepsilon$$ 10^{-10}$ とすると,その精度で計算できる.

実際にこの方法で式(1)を計算した結果を図 3に示す.この図より,$ f(a)$$ f(b)$の関係の式 (4)を満たす区間$ [a,b]$が1/2ずつ縮小していく様子がわかる.

計算の終了は,

$\displaystyle b-a\leq\varepsilon$ (5)

の条件を満たした場合とするのが一般的である.ここで, $ \varepsilon$は解の精度 である.これを変えることにより,任意の精度で近似解を求めることができる.
図 3: $ f(x)=x^3-3x^2+9x-8$の実数解を二分法で解散し,その解の収束の 様子を示している.初期値は $ a=-1,\,b=11$として,最初の解$ c=x_0=5$が求 まり,順次より精度の良い $ x_1,\,x_2,\,x_3,\cdots$が求まる.それが,解析解 $ x=1.1659\cdots $(x軸との交点)に収束していく様子が分かる.
\includegraphics[keepaspectratio, scale=0.7]{figure/NibunMethod.eps}

3.2 プログラム方法

4のような二分法のフローチャートの通りにすれば,目的の 動作をするプログラムができる.
図 4: 二分法のフローチャート
\includegraphics[keepaspectratio, scale=1.0]{figure/flow_nibun.eps}

ホームページ: Yamamoto's laboratory
著者: 山本昌志
Yamamoto Masashi
平成18年7月19日


no counter