筑波大学／2003年度

筑波大学 2003年数学第7問解答・解説

このページには広告が含まれます。

1問題

筑波大学2003年度第7問

関数 $f(x)$ は区間 $a \leq x \leq b$ で連続であるとする (ただし, $a < b$ )。さらに, $f(x)$ は $a < d < b$ を満たす点 $x = d$ で最小値をとり,

$\begin{array}{l} a < x _ {1} < x _ {2} < d \quad \text {ならば } \quad f (x _ {1}) > f (x _ {2}), \\ d < x _ {1} < x _ {2} < b \quad \text {ならば} \quad f \left(x _ {1}\right) < f \left(x _ {2}\right) \\ \end{array}$

とする。区間の幅を縮小させながら d の値を近似的に計算する。a < s < t < b を満たす s と t に対し,

$\begin{array}{l} f (s) > f (t) \quad \text {ならば} \quad s < d < b, \\ f (s) \leq f (t) \quad \text {ならば} \quad a < d \leq t \\ \end{array}$

であることを用い，次のアルゴリズムを作成した。ここで，pは $\displaystyle \frac{1}{2}<p<1$ を満たす定数，hはh<b-aを満たす十分小さい正の定数とする。

流れ図は「始め」→a,b,p,hを入力→i←0,a₀←a,b₀←b,s₀←a₀+(1−p)(b₀−a₀),t₀←a₀+p(b₀−a₀)→bᵢ−aᵢ<hの順に進む。YESはsᵢを出力→「終わり」、NOはf(sᵢ)>f(tᵢ)の判定に進む。そのYESはaᵢ₊₁←sᵢ,bᵢ₊₁←bᵢ,sᵢ₊₁←tᵢ,tᵢ₊₁←aᵢ₊₁+p(bᵢ₊₁−aᵢ₊₁)、NOはaᵢ₊₁←aᵢ,bᵢ₊₁←tᵢ,tᵢ₊₁←sᵢ,sᵢ₊₁←aᵢ₊₁+(1−p)(bᵢ₊₁−aᵢ₊₁)を実行する。両枝はi←i+1に合流し、左側を回る矢印でbᵢ−aᵢ<hの判定へ戻る。

(1) $\displaystyle p = \frac{b_{1} - s_{1}}{b_{1} - a_{1}} = \frac{t_{1} - a_{1}}{b_{1} - a_{1}}$ を満たす p を求めよ。

(2) (1)で求めた p に対して,

$\displaystyle p = \frac {b _ {i} - s _ {i}}{b _ {i} - a _ {i}} = \frac {t _ {i} - a _ {i}}{b _ {i} - a _ {i}}$

が i = k のとき成り立てば, $i = k + 1$ のときも成り立つことを示せ。

(3) (1)で求めた p に対しアルゴリズムを実行する。 $p^{i}$ がはじめて $\displaystyle \frac{h}{b-a}$ より小さくなったとき, $s_{i}$ が出力されることを示せ。

まずは自分で解いてみましょう。詰まったら「考え方」、解けたら「答え」で確かめられます。

2考え方

考え方を見る解き方の方針だけを確かめる

初回更新の両分岐から黄金比条件を導き、その恒等式を使って区間内の二点の相対位置を帰納的に保つ。区間幅の等比的縮小を停止条件に結び付ける。

3答え

答えを見る自分の答えと照らし合わせる

(1) $\displaystyle \quad p=\frac{\sqrt5-1}{2}.\qquad$ (2) $\displaystyle \quad p=\frac{b_i-s_i}{b_i-a_i}=\frac{t_i-a_i}{b_i-a_i}\space{}(i=k)\Longrightarrow$ 同式が $i=k+1$ でも成立 $.\qquad$ (3) $\displaystyle \quad p^i<\frac{h}{b-a}$ が初めて成り立つとき $s_i$ を出力する.

4解答

解答を見る途中式つきの解答

$\displaystyle \text{(1) }L=b-a\text{ とおく。初期値は }s_0=a+(1-p)L,\ t_0=a+pL\text{ である。}\\\text{YES枝なら }a_1=s_0,\ b_1=b,\ s_1=t_0\text{ なので }b_1-a_1=pL,\quad\frac{b_1-s_1}{b_1-a_1}=\frac{1-p}{p},\quad\frac{t_1-a_1}{b_1-a_1}=p.\\\text{NO枝なら }a_1=a,\ b_1=t_0,\ t_1=s_0\text{ なので }b_1-a_1=pL,\quad\frac{b_1-s_1}{b_1-a_1}=p,\quad\frac{t_1-a_1}{b_1-a_1}=\frac{1-p}{p}.\\\text{したがって枝によらず、二つの比が等しいための条件は }p=\frac{1-p}{p}\text{、すなわち }p^2+p-1=0\text{ である。}\frac12<p<1\text{ より }p=\frac{\sqrt5-1}{2}\text{ を得る。このとき }1-p=p^2\text{ かつ }\frac{1-p}{p}=p\text{ である。}\\\text{(2) }w_i=b_i-a_i\text{ とする。仮定から }s_i-a_i=(1-p)w_i,\ t_i-a_i=pw_i\text{ である。YES枝では }w_{i+1}=b_i-s_i=pw_i,\ s_{i+1}=t_i\text{ なので }\frac{b_{i+1}-s_{i+1}}{w_{i+1}}=\frac{b_i-t_i}{pw_i}=\frac{1-p}{p}=p.\text{ また更新式より }t_{i+1}-a_{i+1}=pw_{i+1}\text{ である。NO枝では }w_{i+1}=t_i-a_i=pw_i,\ t_{i+1}=s_i\text{ なので }\frac{t_{i+1}-a_{i+1}}{w_{i+1}}=\frac{s_i-a_i}{pw_i}=\frac{1-p}{p}=p.\text{ また更新式より }b_{i+1}-s_{i+1}=pw_{i+1}\text{ である。したがってどちらの枝でも二つの比はともに }p\text{ となり、主張が成り立つ。}\\\text{(3) どちらの枝でも }w_{i+1}=pw_i\text{ であり、}w_0=b-a\text{ だから }w_i=p^i(b-a)\text{ である。}p^i\text{ が初めて }\frac{h}{b-a}\text{ より小さくなる時点では }w_i<h\text{ となるので、幅の判定がYESとなり }s_i\text{ が出力される。それ以前の }j\text{ では }p^j\geq\frac{h}{b-a}\text{ なので }w_j\geq h\text{ であり、出力判定はYESにならない。}$

この問題で使う考え方

二次方程式とグラフ
等比数列の一般項と和
数学的帰納法

数学を1対1で教わるオンライン塾「数強塾」

数強塾は、中学生・高校生のための数学専門のオンライン個別指導塾です。プロ講師がマンツーマンで教え、大学受験の数学にも対応しています。入塾の前に、今の学習状況と目標を確かめる診断授業（体験・3,000円、税込）を受けられます。

「数強塾」オンライン数学克服塾〈プロ講師〉

東大生と1対1で学べるオンライン個別指導「トウコベ」

トウコベは、東大生を中心に難関大学の学生が講師を務める、完全マンツーマンのオンライン個別指導です。はじめに、オンラインの説明会・勉強相談（無料）をWebで予約でき、その後にお試し授業を受けられます。

トウコベ公式サイト

似た問題を、ほかの大学で

答えや解説の誤りに気づいたら、お問い合わせから教えてください。