数値計算と基本アルゴリズム

数値計算とは、方程式の解や関数の値を有限回の四則演算の繰り返しで近似的に求める分野である。二分法やニュートン法は、近似値を反復して改善し、誤差の基準を満たした時点で終了する代表的な手法である。整数の基本アルゴリズムであるユークリッドの互除法も、同じく反復と終了条件によって理解できる。

二分法の原理と反復回数

二分法は、連続関数の符号が変わる区間を中点で半分ずつ縮めて解を求める方法である。区間の両端で関数値の符号が異なるとき、中点の符号を調べて解を含む側の区間を残す。

区間幅は 1 回の反復ごとに半分になるため、k 回後の幅は初期幅の 1/2^k となる。初期幅が 1 で誤差の基準を 0.001 とすると、1/2^k < 0.001 すなわち 2^k > 1000 を満たす最小の k は 10 である。2^10 = 1024 だからである。

同じ条件のアルゴリズムでは、10 回目の反復で終了条件を満たし、その時点で処理が止まる。反復回数を問われた場合は、条件を満たした最初の回数を答える必要がある。

ニュートン法と接線による反復

ニュートン法は、曲線 y=f(x) 上の点 (x₀, f(x₀)) における接線を求め、その接線と x 軸の交点を次の近似値とする反復法である。接線の交点を新たな x₀ として手順を繰り返し、連続する近似値の差が一定値以下になった時点で終了する。方程式 f(x)=0 の近似解を求める手法として典型的である。

二分法は解を含む区間を保ちながら縮めるのに対し、ニュートン法は近似点そのものを接線に沿って移動させる。このため、解の近くでは収束が速い一方、初期値の選び方によっては近似が解から遠ざかることがある。両者の違いは、区間を縮めるか、接線で移動させるかという更新手順の違いとして押さえる。

また、常微分方程式の数値解法であるオイラー法、連立一次方程式を解くガウスの消去法、定積分を近似するシンプソン法は、いずれも方程式の根を接線で求める手法ではない。目的が異なるため、名称と対象を結び付けて区別しておく必要がある。