0≤x≤1 の範囲で単調に増加する連続関数 f(x)f(x)f(x) が f(0)<0≤f(1)f(0) < 0 \leq f(1)f(0)<0≤f(1) を満たすときに、区間内で f(x)=0f(x) = 0f(x)=0 である xxx の値を近似的に求めるアルゴリズムにおいて、(2) は何回実行されるか。
【アルゴリズム】
- x0=0,×1=1x_0 = 0, \quad x_1 = 1×0=0,×1=1 とする。
- x=x0+x12x = \frac{x_0 + x_1}{2}x=2×0+x1 とする。
- ∣x1−x0∣<0.001|x_1 – x_0| < 0.001∣x1−x0∣<0.001 ならば xxx の値を近似値として終了する。
- f(x)f(x)f(x) の値により、x0=xx_0 = xx0=x として、そうでなければ x1=xx_1 = xx1=x とする。
- (2) に戻る。
選択肢：
ア 10
イ 20
ウ 100
エ 1,000
解説
設問の手順で連続関数のゼロ点を近似的に求めるアルゴリズムは「分法」と呼ばれます。
簡単に手順を示します。
- 関数 ƒ(x) に対して、ƒ(a)＜0、ƒ(b)＞0 となるaとbを選ぶ
- c ←
a＋b
2
で区間の真ん中を求める - ƒ(c) を求め、誤差が条件内であればcを近似解とする
- ƒ(c)＜0であればa ← c、ƒ(c)＞0であればb ← cとして順2に戻る
仮に ƒ(0.3)＝0 としてアルゴリズムを途中までトレースしていくと次のようになります。
1: x ← 0，x ← 1
2: x ← (0＋1)／2 = 0.5
3: (1－0.5)＜0.001 は偽なので処理続行する
4: ƒ(0.5)≧0 は真なので、x ← 0.5
//(2)に戻る
5: x ← (0 + 0.5)／2 = 0.25
6: (0.5 – 0.25)＜0.001 は偽なので処理続行する
7: ƒ(0.25)≧0 は偽なので、x ← 0.25
8: x ← (0.25 + 0.5)／2 = 0.375
9: (0.5 – 0.375)＜0.001 は偽なので処理続行する
10: ƒ(0.375)≧0 は真なので、x ← 0.375
//(2)に戻る
11: x ← (0.25 + 0.375)／2 = 0.3125
12: (0.375 – 0.3125)＜0.001 は偽なので処理続行する