2014/6/16 解答 1. 1 次元の場合、すなわち f : R → R について f (x) = 0 の解を求める場合のニュートン法の √ 公式を自分で導き、a > 0 を与えて a の近似解を求める公式を導け。(なお、この公式は必ず収束することが証明できる) (解答：) 前半はテキスト通りなので、省略。次に f (x) = x2 − a とし、f (x) = 0, について xn+1 = xn − f (xn ) f ′ (xn ) , を計算すると、xn+1 = 12 (xn + a xn ) 2. 縦 1, 横 a (a > 1) の長方形の上部に１辺 a の正方形をくっつけてできる長方形が、もとの長 √ 方形と相似になったとする。この長方形は黄金比 a : 1 = 1 : 5−1 2 （1 次元探索に現れた値）をもつことを示せ。 (解答：) a + 1 : a = a : 1 から a2 − a − 1 = 0. a = (1 + √ √ 5)/2 を得る. a : 1 = 1 : ( 5 − 1)/2 は明らか. 3. ナップザック問題について、次のグリーディアルゴリズムを考える • ci /di の大きいものから順にならべたものを j1 , j2 , . . . (cj1 /dj1 ≥ cj2 /dj2 ≥ cj3 /dj3 ≥ · · · ) とし、b を超えない限り j1 , j2 , . . . の順に詰めていく。この方法が失敗し、最適解が得られない例を挙げよ。 (解答：) n = 3、b = 1, c1 = 0.6, c2 = c3 = 0.4 d1 = 0.6, d2 = d3 = 0.5 とおく。グリーディでは、1 だけが詰められるが、2 と 3 を詰めるほうが最適になるので、グリーティ法は失敗している。 4. 巡回セールスマン問題で、都市 1 から出発するとし、次のグリーディ法によって進むとする。 • d(1, j) が最小の j を訪問する。 • d(j, i) が最小の i を訪問する。これを繰り返し、最後に 1 に戻る。このグリーディ法で最適解が得られない例を作れ。このような例が作れる最小の都市の数はいくつか。 (解答：) n = 4, d(1, 2) = 1, d(2, 3) = 1, d(3, 4) = 1, d(4, 1) = 10, d(1, 3) = d(2, 4) = 2 とおくと、グリーディ法によれば、1–2–3–4–1 とまわるので、目的関数は 13 となる。1–3–4–2–1 の目的関数は 6 になるので、グリーディ法は失敗している。 5. 第１回の演習で実施した回帰直線を求める問題における 1∑ (yi − axi − b)2 2 i=1 n F (a, b) = は凸関数であることを示せ。 (解答：) gi (a) = (yi − xi a − b)2 , a = [a, b] とすると、 gi (λa1 + (1 − λ)a2 ) = (λ(yi − xi a1 − b1 ) + (1 − λ)(yi − xi a2 − b2 ))2 ≤ λ(yi − xi a1 − b1 )2 + (1 − λ)(yi − xi a2 − b2 )2 = λgi (a1 ) + (1 − λ)gi (a2 ) よって gi (a) は凸関数。よってそれらの和である F (a, b) = 1 ∑ i gi (a) も凸関数となる。