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

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

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

3.1 二分法の原理

3.1.1 方程式の解

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

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

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

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

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

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

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

$$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軸との交点が解である．

3.1.2 二分法

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

$$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$²よりも小さくなったならば，計算を終了する．例えば， $\varepsilon$を$10^{-10}$ とすると，その精度で計算できる．

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

計算の終了は，

$$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軸との交点)に収束していく様子が分かる．

3.2 プログラム方法

図4のような二分法のフローチャートの通りにすれば，目的の 動作をするプログラムができる．

図 4: 二分法のフローチャート

ホームページ: Yamamoto's laboratory
著者: 山本昌志