院試過去問 2008年度専門科目数理のバックアップ(No.12)

http://www.i.u-tokyo.ac.jp/edu/course/mi/admission.shtml
http://www.i.u-tokyo.ac.jp/edu/course/mi/pdf/2008suuri-j.pdf

第一問 †

Krylov subspace
$A\in\mathbb{C}^{n\times n},b\in\mathbb{C}^n$ について、
$\{b,Ab,\cdots,A^{k-1}b\}$ の張る部分空間を $W_k(A,b)$ とし、 $d_k=\dim W_k$ とする。

(1)を示せ。
- 自明…
  $\forall v=\sum_{i=0}^{k-1}a_{i}A^{i}b \in W_k$ について、
  $a_k=0$ ととれば、 $v=\sum_{i=0}^{k}a_{i}A^{i}b \in W_{k+1}$
(2)を示せ。
- $A^{k}b\in W_k \Rightarrow A^{k+1}b\in W_{k+1}$ を示せばよい。
  $A^{k}b\in W_k$ ならば、ある $\{a_i\}_{i=0}^{k-1}$ について、
  $A^{k}b=\sum_{i=0}^{k-1}a_{i}A^{i}b$ が成立。
  よって $A^{k+1}b=\sum_{i=1}^{k}a_{i-1}A^{i}b \in W_{k+1}$
(3)を示せ。
- 自明…？
  $A^{k}b\in W_k$ のとき、 $W_k=W_{k+1}=W_{k+2}$ なので両辺ともに0となり、成立。
  そうでないとき、 $W_{k+1}$ は $W_k$ の基底に $A^{k}b$ を追加したものを基底とする線形空間なので、
  $d_{k+1}-d_{k}=1$ 、右辺も同様に高々1なので、不等式成立。
(4)任意のに対して、となることを示せ。
- 帰納法を使う。
  まず、 $W_1(A-\lambda I,b)=W_1(A,b)$ は成立している。
  $W_k(A-\lambda I,b)=W_k(A,b)$ が成立しているなら、
  $A^{k-1}b\in W_{k}(A-\lambda I,b)$
  $(A-\lambda I)A^{k-1}b\in W_{k+1}(A-\lambda I,b)$ なので
  $A^{k}b = (A-\lambda I)A^{k-1}b+\lambda A^{k-1}b \in W_{k+1}(A-\lambda I,b)$ であり、
  ついでに $(A-\lambda I)^{k}b$ は $A^{i}b,\ (i=0,\cdots,k)$ の線形結合で書けるので
  $(A-\lambda I)^{k}b\in W_{k+1}(A-\lambda I,b)$
  よって $W_{k+1}(A-\lambda I,b)=W_{k+1}(A,b)$ が成立。
  以上から、帰納的に任意の $k$ について、 $W_{k+1}(A-\lambda I,b)=W_{k+1}(A,b)$ が成立。
(5)について、
となるためのの必要十分条件を求めよ。
- (4)を使うと、対角に定数を足す分だけ調整できるので、 $\alpha$ には制限は付かない。
  さらに、一般性を失なうことなく $\alpha=0$ としてよい。
  $\{b,Ab,A^2b\}$ が線型独立ならば $d_3=3$ なので，
  $\begin{align*}|b\ Ab\ A^2b|=\left|\begin{matrix}b_1&b_2&b_3\\b_2&b_3&0\\b_3&0&0\end{matrix}\right|=-b_3^3\end{align*}$ が非ゼロであればよい．よって， $b_3\ne 0$ がとなる必要十分条件．
(6)について，
となるためのの必要十分条件を求めよ．
- (4)より， $A=\begin{pmatrix}0&1&0&0&0\\0&0&1&0&0\\0&0&0&0&0\\0&0&0&\beta-\alpha&1\\0&0&0&0&\beta-\alpha\end{pmatrix}$ と変形できる。
  $\det\left(b,Ab,A^{2}b,A^{3}b,A^{4}b\right)\neq 0$ であればよい。
  $\tilde{A}=\begin{pmatrix}\beta-\alpha&1\\0&\beta-\alpha\end{pmatrix},\ \tilde{b}=\tilde{A}^{3}\begin{pmatrix}b_4\\b_5\end{pmatrix}$ と置くと、
  $\det\begin{pmatrix}b_1&b_2&b_3&&\\b_2&b_3&0&&\\b_3&0&0&&\\ *&*&*&\tilde{b}&\tilde{A}\tilde{b}\end{pmatrix}=(\beta-\alpha)^{6}b_{3}^{3}b_{5}^{2}$
  よって、 $b_{3}b_{5}(\alpha-\beta)\neq 0$ が必要十分条件．

↑

第二問 †

力学系l
$\frac{d}{dt}\begin{pmatrix}p(t)\\q(t)\\r(t)\end{pmatrix}=\begin{pmatrix}p(t)\left(q(t)-r(t)\right)\\q(t)\left(r(t)-p(t)\right)\\r(t)\left(p(t)-q(t)\right)\end{pmatrix}$
について、 $p(0),q(0),r(0)>0$ かつ $p(0)+q(0)+r(0)=1$ を満たしている。

、を示せ。
を示せ。
- $\frac{d}{dt}\left(p(t)+q(t)+r(t)\right)=0$ と
  $\frac{d}{dt}\left(p(t)q(t)r(t)\right)=0$ となるので、両方共定数。
  なので、
  $p(t)q(t)r(t)\neq 0$ だから $p,q,r$ はどれも0にはなれない。
  は連続で、初期値は正だから任意の時刻で正。
  また、も成立。
(2)となるためのの条件を示せ。
となるためのの条件を示せ。
- $\dot{p}=p(q-r)=p(2q+p-1)>0 \iff q > \frac{1-p}{2}$
  $\dot{q}=p(q-r)=q(2p+q-1)>0 \iff q < 1-2p$
- 実際にはの領域でもなければならない．
(3) 不動点を求めよ．また，浮動点でないときの運動の概形を図示せよ．
- 不動点は $\dot{p}=\dot{q}=\dot{r}=0$ のときなので， $p(t)q(t)r(t)\ne 0$ より．
- 図は不動点の周りをを満たしつつ，の直線に対称に，原点に近い方のの点ではが増える方向に矢印を書けばよい．
Euler法で $\frac{1}{h}\begin{pmatrix}p_{n+1}-p_n\\ q_{n+1}-q_n\\r_{n+1}-r_n\end{pmatrix}=\begin{pmatrix}p_n(q_n-r_n)\\ q_n(r_n-p_n)\\ r_n(p_n-q_n)\end{pmatrix}$ と離散化し，近似的に解くことを考える．．
(4) を十分小さくとれば，いかなる初期値に対しても，となることを示せ．
- $\begin{align*}p_{n+1}+q_{n+1}+r_{n+1}=p_n+q_n+r_n=\dots =p_0+q_0+r_0=1\tag{**}\end{align*}$ であることに注意する．
  帰納法で証明する．
  での成立は(1)で述べた通りである．
  のとき，(**)より $|q_n-r_n|\le 1-p_n$ なので，
  $\begin{align*}p_{n+1}&=p_n+hp_n(q_n-r_n)\\&\ge p_n-hp_n(1-p_n)\\&\ge (1-h)p_n+hp_n^2\end{align*}$
  である．これより， $h\le 1$ であれば， $p_{n+1}\ge 0$ ．同様にして， $q_{n+1},r_{n+1}>0$ である．ここで， $p_{n+1}+q_{n+1}+r_{n+1}=1$ なので， $0<p_{n+1},q_{n+1},r_{n+1}<1$ ．
  よって，数学的帰納法により題意は示せれた．
(6) 初期値が定常解でないとき，刻み幅を十分小さくとれば，はに関して狭義単調減少となることを示せ．また，このときのの略図を図示せよ．
- とし，とする．このとき，であることに注意すると，
  $\begin{align*}I_{n+1}&=I_n(1+a)(1+b)(1-a-b)\\&=I_n(1+(a+b)+ab)(1-(a+b))\\&=I_n(1-(a+b)^2+ab(1-(a+b)))\\&<I_n*\max((1-(a+b)^2),(1-(a+b)^2+2ab))\\&=I_n*\max((1-(a+b)^2),(1-a^2-b^2))<I_n\end{align*}$
  よって，は狭義単調減少．
- は狭義単調減少であるから，(3)の閉曲線を不動点に向かう螺旋に変形すればよい.（図略）

↑

第3問 †

Markov Chain
$Q^{(n)}(j,k)=P(X(n)=k| X(0)=j)$
$f^{(n)}(j,k)=P(X(n)=k|X(0)=j)*\prod_{1\le l< n}P(X(l)\ne k|X(0)=j)$
$\bar{Q}_{jk}(z)=\sum_{n=1}^{\infty} Q^{(n)}(j,k)z^n$
$\bar{f}_{jk}(z)=\sum_{n=0}^{\infty}f^{(n)}(j,k)z^n$
と定義する．

(1) を示せ．
- のとき， $Q^{(0)}(j,k)=\delta_{jk}$ ,
  のとき， $Q^{(n)}(j,k)=\sum_{s=0}^n f^{(s)}(j,k)Q^{n-s}(k,k)$ であるから，
  $\begin{align*}\bar{Q}_{jk}(z)&=\sum_{n=0}^{\infty}Q^{(n)}(j,k)z^n\\&=\delta_{jk}+\sum_{n=0}^{\infty}\sum_{s=0}^{n} f^{(s)}(j,k)Q^{(n-s)}(k,k)z^n\\&=\delta_{jk}+\sum_{s=0}^{\infty}\sum_{t=0}^{\infty} f^{(s)}(j,k)z^sQ^{(t)}(k,k)z^t\\&=\delta_{jk}+\bar{f}_{jk}(z)\bar{Q}_{kk}(z)\end{align*}$
(2) 状態が再帰的であるとき，の値を求めよ．
- $\bar{f}_{jj}(1)=\sum_{n=0}^{\infty}f^{(n)}(j,j)$ であるので，有限ステップで状態に戻ってくる確率を表している．よって， $\bar{f}_{jj}(1)=1$ であることが，状態が再帰的であるための必要十分条件．
(3) 条件

は状態が再帰的であるための必要十分条件であることを示せ．
- $\sum_{n=0}^{\infty}Q^{(n)}(j,j)=\bar{Q}_{jj}(1)$ であることに注意する．また(1)より， $(1-\bar{f}_{jj}(1))\bar{Q}_{jj}(1)=1$ である．これより， $\bar{Q}_{jj}(1)=\infty$ であることが $\bar{f}_{jj}(1)=1$ であるための必要十分条件，すなわちが再帰的であるための必要十分条件である．
(4)
で定義される1次元ランダムウォークを考える．このとき，を求めよ．
- $\begin{align*}Q^{(2n)}(0,0)&= {2n \choose n}p^n(1-p)^n=\frac{(2n)!}{(n!)^2}p^n(1-p)^n\\Q^{(2n+1)}(0,0)&=0\end{align*}$
  であるから，
  $\begin{align*}\bar{Q}_{00}(z)&=\sum_{n=0}^{\infty}\frac{(2n)!}{(n!)^2}p^n(1-p)^nz^{2n}\\&=\frac{1}{\sqrt{1-4p(1-p)z^2}}\end{align*}$
- $\begin{align*}Q^{(2n+1)}(1,0)&= {2n+1 \choose n}p^n(1-p)^{n+1}=\frac{(2n+2)!}{((n+1)!)^2}p^{n+1}(1-p)^{n+1}\frac{1}{2p}\\Q^{(2n)}(1,0)&=0\end{align*}$
  よって，
  $\begin{align*}\bar{Q}_{10}(z)&=\sum_{n=0}^{\infty}\frac{(2n)!}{(n!)^2}p^n(1-p)^nz^{2n}\frac{1}{2pz}-\frac{1}{2pz}\\&=\frac{1}{2pz}\left(\frac{1}{\sqrt{1-4p(1-p)z^2}}-1\right)\end{align*}$
- $\bar{Q}_{10}(z)=\bar{f}_{10}\bar{Q}_{00}(z)$ なので，
  $\begin{align*}\bar{f}_{10}(z)=\frac{\bar{Q}_{10}(z)}{\bar{Q}_{00}(z)}=\frac{1}{2pz}\left(1-\sqrt{1-4p(1-p)z^2}\right)\end{align*}$
  (カタラン数を使えば直接求めることができるはず...)
各頂点が次数の木グラフにおけるランダムウォークを考える．各頂点から隣合う頂点に等確率で移動するとするとき，枝数で測った距離はを状態集合とするマルコフ連鎖となる．以降初めて出発点に到達するまでは(4)のランダムウォークとみなせるがこのときのをを用いて表せ．
- 確率で1離れ，で1近づくので，．
(5)のについてを求め，状態が再帰的でないことを示せ．
- $\bar{f}_{00}(z)$ は(4)の意味での $\bar{f}_{10}(z)$ となるので， $\bar{f}_{00}(z)=\frac{1}{2pz}\left(1-\sqrt{1-4p(1-p)z^2}\right)$ ．
  よって， $\bar{f}_{00}(1)=\frac{1}{2p}\left(1-\sqrt{1-4p(1-p)}\right)\ne 1$ より状態0は再帰的ではない．

↑

第四問 †

空間図形
時刻 t_1 に日本のある場所から空を見上げたら，遠くの山の頂の点Pと同じ位置に1つの明るい星Aと人工衛星Bとが重なって見えた．その視点における北極星とPの臨み角は $\alpha$ であった．同じ夜の t_1+t_2 に同じ場所からもう一度空を見上げたら，星Aと頂Pの臨み角は $\beta$ で，一方，人工衛星Bは地球をほぼ一周したあと山の頂Pと同じ位置に見えた. さらに時刻 t_1+2t_2 でも，人工衛星BはPと同じ位置に見えた．人工衛星Bは地球の自転軸と $\theta$ をなす平面を角速度 $\omega$ で回転運動しているものとする．

(1)経過時間を求めよ．
- $\alpha=0$ であったり，明るい星Aが月や太陽や惑星ではないものとする．
  天動説を採用し，北極星を中心にAが $\phi$ 回転したものとする．これより，地球と北極星の距離をとすると， $2r\tan\alpha\sin(\phi/2)=2r\sec\alpha\sin(\beta/2)$ ．すなわち， $\phi=2\arcsin\left(\frac{\sin(\beta/2)}{\sin\alpha}\right)$ ．よって， $t_2=\arcsin\left(\frac{\sin(\beta/2)}{\sin\alpha}\right)/\pi$ 日．
(2)人工衛星Bの大円軌道に関して考え得るを求めよ．
- 山の頂を眺める視線は地球の自転と共に地軸に対して回転対称な図形を描く．人工衛星は地球の中心から等距離を飛ぶので，この図形と地球の中心を中心とする球の交差部，すなわち地軸に垂直な円C上の等間隔な3点でを通ることが分かる．このような3点を通る円はC以外には存在しないので，人工衛星はC上を飛んでいることが分かる．ここで，Cの中心が地球の中心に一致するためには $\theta=0$ でなければならない．また，人工衛星の回転方向が地球の自転と同方向である場合と逆方向である場合について考えて，
  $\omega=2\pi\left(\frac{1}{t_2}\pm t_2\right) (\text{rad}/\text{day}),\theta=0$
  ただし例外として
  $\beta=0, \omega=\infty, \theta=\frac{\pi}{2}-\alpha$
  $\alpha=0, \beta=0, \omega=\text{any}, \theta=\frac{\pi}{2}$
  がある．

↑

第五問 †

無向2部グラフ $G=(V^+\cup V^-,E)$ について、
最大マッチングを考える。

(1)以下のアルゴリズムが必ずしも最大マッチングを与えないことを
例を挙げて示せ。
- $V^+=\{0,1\},\ V^-=\{2,3\},\ E=\{\{1,2\},\{0,2\},\{1,3\}\}$ として、
  $\{1,2\},\{0,2\},\{1,3\}$ の順に枝が選ばれたら、
  得られるマッチングは $\{\{1,2\}\}$ であり、最大マッチング $\{\{0,2\},\{1,3\}\}$ ではない。
(2) をの2つのマッチングとする．との対称差を枝集合とするはどのような性質を持つか．
- どの頂点からも高々2本の枝がでているので，いくつかの互いに素なパスができる．
(3) をのマッチング，をの最大マッチングとする．このとき，(2)で定義されたを用いて，が最大であるための必要十分条件を書け．
- に現れる全てのパスが偶数長であることである．なぜならば，もし奇数長のパスが存在すればそれを用いてマッチングの数を増やすことができ，全て偶数長のパスならばである．
(4)のマッチングに属する枝を側から側へ，に属さない枝を側から側に向き付けしてできた有効グラフをとする．このを用い，が最大マッチングであるための必要十分条件を示せ．
- $M_1\bigtriangleup(M_1\bigtriangleup M_2)=M_2$ であり， $M_1\bigtriangleup M_2$ は互いに素なパスの集合であるから，が最大マッチングであるなら始点と終点がでカバーされていないような有向パスが存在せず，逆に最大マッチングでないならあるパスが存在して始点と終点がでカバーされていない．よって，始点と終点がでカバーされていないような有向パスが存在しないことが最大マッチングであるための必要十分条件．
(5) (4)の結果を利用して，最大マッチングを求めるアルゴリズム，ならびに，その時間計算量を与えよ．
- $M=\emptyset$ とする．
  (4)のグラフを作り始点と終点がでカバーされてないようなパスを探索する．これは幅優先探索で実現できるので時間計算量はである．このようなパスが見つかったら $M=M\bigtriangleup E(P)$ とマッチングを更新する．見つからなかったら終了．
  マッチングの数はで抑えられるので，全体の時間計算量は，．