線形探索

最もシンプルなアイデアとして、$x$ を 0 から $\epsilon$ ずつ増やして上記の不等式を満たす $x$ を探索すると言う方法が考えられます。 この方法をリストの線形探索になぞらえて、線形探索 と呼ぶことにします。

$n = 2$、$\epsilon = 0.1$としたときの計算過程は以下のようになります。 （$\epsilon$を 0.1 ずつ増やしているにも関わらず端数の誤差が生じる理由は第 02 回の授業で取り扱います。）

$x = 1.4$ のとき、条件を満たしていることが確認できます。 またこのとき、$0.1 \geq 1.41421356\cdots - 1.4 \geq -0.1$ であることも確認できます。

なお、$x$をさらに$\epsilon$分増やした$x = 1.5$ でも $0.1 \geq 1.41421356\cdots - 1.5 \geq -0.1$ が満たされています。 これは一般的に成り立つ性質であり、$\epsilon \geq \left| T - A \right|$ かつ $\epsilon < \left| T - (A - \epsilon) \right|$ のとき、$\epsilon \geq \left| T - (A + \epsilon) \right|$ となります。

さらに、同じ条件のとき、$A + \epsilon \geq T > A$が満たされます。 すなわち、これは$\sqrt{2}$の真値は 1.4 から 1.5 の間に存在していることを表しています。

線形探索アルゴリズムでは、近似値にたどり着くまでに $\epsilon = 0.1$ のときで 14 回、$\epsilon = 0.01$ のとき 141 回、$\epsilon = 0.001$ の時で 1414 回…、と精度が一桁上がるごとに約 10 倍の繰り返しが必要となり、計算効率が良くありません。

次は上記の性質を用いて効率良く真値に近い近似値を求める方法を考えてみましょう。