数値解法と再帰・分割統治

数値解法は、解析的に解けない方程式や定積分などを反復計算や区間の絞り込みによって近似的に求める手法の総称である。再帰は、問題を同じ形のより小さな問題に帰着させて自分自身を呼び出す手法であり、分割統治法は問題を独立した部分問題に分けて解いた結果を統合する設計法である。いずれも「小さく分けて順に解く」という考え方に基づいており、試験では手順の正しさと終了条件の判断が問われやすい。

二分法による近似の仕組み

二分法は、解が含まれる区間の中点を求め、中点の符号に応じて区間の端を入れ替えることで、区間を半分ずつ縮めていく。関数が単調に増加し両端の符号が異なるならば、解は区間内に存在するため、この絞り込みが成り立つ。k回の反復後に区間幅は元の幅の1/2のk乗になるので、区間幅が0.001未満となる最小の反復回数は、2のk乗が1000を超える条件から10回と求まる。同じ終了条件を用いる問題でも、10回目で条件を満たして終了するため、100回や1,000回といった多くの反復は必要にならない。一回の反復で使う情報が中点の符号だけであるため、区間幅の縮小に頼る分、確実性は高いものの反復回数は多くなりやすい。

ニュートン法と終了判定

ニュートン法は、現在の近似値における曲線の接線を求め、その接線とx軸の交点を次の近似値とする反復法である。接線の傾きは関数の微分係数で与えられ、接線の式からx軸との交点を求めれば次の近似値が得られる。反復は、連続する二つの近似値の差の絶対値が指定した値以下になった時点で打ち切る。この差は近似の精度の目安として用いられる。ニュートン法は接線の情報を使うため、区間の符号条件を必要としない一方、初期値の選び方によっては解に収束しないことがある。二分法と比べて、確実に解を囲い込む性質がない点が区別の要となる。