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

院試勉強会

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
について、
の張る部分空間をとし、とする。
- (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}\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

と定義する．
- (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は再帰的ではない．

第四問
時刻に日本のある場所から空を見上げたら，遠くの山の頂の点Pと同じ位置に1つの明るい星Aと人工衛星Bとが重なって見えた．その視点における北極星とPの臨み角はであった．同じ夜のに同じ場所からもう一度空を見上げたら，星Aと頂Pの臨み角はで，一方，人工衛星Bは地球をほぼ一周したあと山の頂Pと同じ位置に見えた. さらに時刻でも，人工衛星BはPと同じ位置に見えた．人工衛星Bは地球の自転軸とをなす平面を角速度で回転運動しているものとする．
- (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の大円軌道に関して考え得るを求めよ．
  - $\beta=0, \omega=\infty, \theta=\frac{\pi}{2}-\alpha$
  - $\alpha=0, \beta=0, \omega=\text{any}, \theta=\frac{\pi}{2}$

第五問
無向2部グラフについて、
最大マッチングを考える。
- (1)以下のアルゴリズムが必ずしも最大マッチングを与えないことを
  例を挙げて示せ。
  - $V^+=\{0,1\},\ V^-=\{2,3\},\ E=\{\{0,2\},\{1,3\},\{1,2\}\}$ として、
    $\{1,2\},\{0,2\},\{1,3\}$ の順に枝が選ばれたら、
    得られるマッチングは $\{\{1,2\}\}$ であり、最大マッチング $\{\{0,2\},\{1,3\}\}$ ではない。

無料コンテンツはここまでです．
全ての解答を見るためには，残りを書き上げる必要があります．

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

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