アルゴリズムと数値計算

アルゴリズムは問題を解く手順であり、数値計算では有限の桁で扱うことによる誤差も理解する必要がある。試験では、反復の回数、探索の平均比較回数、整列法の分類、誤差の種類、近似解法の名称などが問われる。手順の動きを一段ずつ追い、式の意味を言葉で説明できるようにすることが基本になる。

反復法による近似解の求め方

区間を半分ずつに分けて解を絞り込む方法は二分法と呼ばれる。0≦x≦1 で単調増加する f(x) について f(0)＜0≦f(1) のとき、区間の中点 x を計算し、その符号によって区間の端を入れ替えて狭める。 第k回の計算後の区間幅は 1/2の k 乗になるため、終了条件 x₁−x＜0.001 を満たすまでの回数は、この大きさから求められる。第9回では約0.00195で条件を満たさず、第10回では約0.00098となり、そこで終了する。 ニュートン法は、現在の近似値における接線と x 軸の交点を次の近似値とする方法である。 接線の式から x_{n+1}＝x_n−f(x_n)/f′(x_n) と求まり、この更新を繰り返す。収束が速い反面、導関数の値が0に近い場所では扱いに注意が必要である。 反復を終える条件は、二つの近似値の差がある値以下になったときと定めるのが一般的である。手順のどの量を比べて終了するかを読み取ることが、回数の問題を解く鍵になる。

探索の平均比較回数

n 個のデータを m 個ずつのブロックに分け、各ブロックの最後尾だけを線形探索してブロックを見つけ、そのブロックの中を線形探索する方法を考える。ブロックの数は n/m 個であり、最後尾の探索は平均で約 n/(2m) 回の比較になる。 該当ブロック内の探索は平均で約 m/2 回である。したがって、m が十分に大きいときの平均比較回数の主要項は m/2＋n/(2m) となる。 選択肢にありがちな m＋n/m や n/m だけでは、この主要項を表せない点が試験の要点になる。ブロック数そのものや、片方の探索だけを表す式と取り違えないよう、二つの探索の回数を分けて書き出すとよい。