[[院試勉強会]] 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 **第一問 [#df49e074] Krylov subspace~ &imgtex(\(A\in\mathbb{C}^{n\times n},b\in\mathbb{C}^n\));について、~ &imgtex(\(\{b,Ab,\cdots,A^{k-1}b\}\));の張る部分空間を&imgtex(\(W_k(A,b)\));とし、&imgtex(\(d_k=\dim W_k\));とする。 -- (1)&imgtex(\(W_k \subseteq W_{k+1}\));を示せ。 --- 自明…~ &imgtex(\[\forall v=\sum_{i=0}^{k-1}a_{i}A^{i}b \in W_k\]);について、~ &imgtex(\(a_k=0\));ととれば、&imgtex(\[v=\sum_{i=0}^{k}a_{i}A^{i}b \in W_{k+1}\]); -- (2)&imgtex(\(W_k=W_{k+1}\Rightarrow W_{k+1}=W_{k+2}\));を示せ。 --- &imgtex(\(A^{k}b\in W_k \Rightarrow A^{k+1}b\in W_{k+1}\));を示せばよい。~ &imgtex(\(A^{k}b\in W_k\));ならば、ある&imgtex(\[\{a_i\}_{i=0}^{k-1}\]);について、~ &imgtex(\[A^{k}b=\sum_{i=0}^{k-1}a_{i}A^{i}b\]);が成立。~ よって&imgtex(\[A^{k+1}b=\sum_{i=1}^{k}a_{i-1}A^{i}b \in W_{k+1}\]); -- (3)&imgtex(\(d_{k+1}-d_k \geq d_{k+2}-d_{k+1}\));を示せ。 --- 自明…?~ &imgtex(\(A^{k}b\in W_k\));のとき、&imgtex(\(W_k=W_{k+1}=W_{k+2}\));なので両辺ともに0となり、成立。~ そうでないとき、&imgtex(\(W_{k+1}\));は&imgtex(\(W_k\));の基底に&imgtex(\(A^{k}b\));を追加したものを基底とする線形空間なので、~ &imgtex(\(d_{k+1}-d_{k}=1\));、右辺も同様に高々1なので、不等式成立。 -- (4)任意の&imgtex(\(\lambda\));に対して、&imgtex(\(W_k(A-\lambda I,b)=W_k(A,b)\));となることを示せ。 --- 帰納法を使う。~ まず、&imgtex(\(W_1(A-\lambda I,b)=W_1(A,b)\));は成立している。~ &imgtex(\(W_k(A-\lambda I,b)=W_k(A,b)\));が成立しているなら、~ &imgtex(\(A^{k-1}b\in W_{k}(A-\lambda I,b)\));~ &imgtex(\((A-\lambda I)A^{k-1}b\in W_{k+1}(A-\lambda I,b)\));なので~ &imgtex(\(A^{k}b = (A-\lambda I)A^{k-1}b+\lambda A^{k-1}b \in W_{k+1}(A-\lambda I,b)\));であり、~ ついでに&imgtex(\((A-\lambda I)^{k}b\));は&imgtex(\(A^{i}b,\ (i=0,\cdots,k)\));の線形結合で書けるので~ &imgtex(\((A-\lambda I)^{k}b\in W_{k+1}(A-\lambda I,b)\));~ よって&imgtex(\(W_{k+1}(A-\lambda I,b)=W_{k+1}(A,b)\));が成立。~ 以上から、帰納的に任意の&imgtex(\(k\));について、&imgtex(\(W_{k+1}(A-\lambda I,b)=W_{k+1}(A,b)\));が成立 。 -- (5)&imgtex(\[A=\begin{pmatrix}\alpha&1&0\\0&\alpha&1\\0&0&\alpha\end{pmatrix},\ b=\begin{pmatrix}b_1\\b_2\\b_3\end{pmatrix}\]);について、~ &imgtex(\(d_3=3\));となるための&imgtex(\(\alpha,b\));の必要十分条件を求めよ。 --- (4)を使うと、対角に定数を足す分だけ調整できるので、&imgtex(\(\alpha\));には制限は付かない。~ さらに、一般性を失なうことなく&imgtex(\(\alpha=0\));としてよい。~ &imgtex(\(\{b,Ab,A^2b\}\));が線型独立ならば&imgtex(\(d_3=3\));なので,~ &imgtex(\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*}); が非ゼロであればよい. よって,&imgtex(\(b_3\ne 0\));が&imgtex($d_3=3$);となる必要十分条件. -- (6)&imgtex(\[A=\begin{pmatrix}\alpha&1&0&0&0\\0&\alpha&1&0&0\\0&0&\alpha&0&0\\0&0&0&\beta&1\\0&0&0&0&\beta\end{pmatrix},\ b=\begin{pmatrix}b_1\\b_2\\b_3\\b_4\\b_5\end{pmatrix}\]);について,~ &imgtex(\(d_5=5\));となるための&imgtex(\(\alpha,\beta,b\));の必要十分条件を求めよ. --- (4)より,&imgtex(\[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}\]); と変形できる。~ &imgtex(\(\det\left(b,Ab,A^{2}b,A^{3}b,A^{4}b\right)\neq 0\));であればよい。~ &imgtex(\(\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}\));と置くと、~ &imgtex(\(\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}\));~ よって、&imgtex(\(b_{3}b_{5}(\alpha-\beta)\neq 0\));が必要十分条件. **第二問 [#accc1ca0] 力学系l~ &imgtex(\[\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}\]);~ について、 &imgtex(\(p(0),q(0),r(0)>0\));かつ&imgtex(\(p(0)+q(0)+r(0)=1\));を満たしている。 -- &imgtex(\(p(t)+q(t)+r(t)=1\));、&imgtex(\(p(t)q(t)r(t)=\mathrm{const}\));を示せ。~ &imgtex(\(0<p(t),q(t),r(t)<1\));を示せ。 --- &imgtex(\[\frac{d}{dt}\left(p(t)+q(t)+r(t)\right)=0\]);と~ &imgtex(\[\frac{d}{dt}\left(p(t)q(t)r(t)\right)=0\]);となるので、両方共定数。~ &imgtex(\[p(0)+q(0)+r(0)=1\]);なので、&imgtex(\[p(t)+q(t)+r(t)=1\]);~ &imgtex(\[p(t)q(t)r(t)\neq 0\]);だから&imgtex(\(p,q,r\));はどれも0にはなれない。~ &imgtex(\[p(t),q(t),r(t)\]);は連続で、初期値は正だから任意の時刻で正。~ また、&imgtex(\[p(t)=1-q(t)-r(t)<1\]);も成立。 -- (2)&imgtex(\(\dot{p}(t)>0\));となるための&imgtex(\((p,q)\));の条件を示せ。~ &imgtex(\(\dot{q}(t)>0\));となるための&imgtex(\((p,q)\));の条件を示せ。 --- &imgtex(\(\dot{p}=p(q-r)=p(2q+p-1)>0 \iff q > \frac{1-p}{2}\));~ &imgtex(\(\dot{q}=q(r-p)=q(1-2p-q)>0 \iff q < 1-2p\)); --- 実際には&imgtex($p>0, q>0, p+q<1$);の領域でもなければならない. -- (3) 不動点を求めよ.また,浮動点でないときの運動の概形を図示せよ. --- 不動点は&imgtex($\dot{p}=\dot{q}=\dot{r}=0$);のときなので,&imgtex($p(t)q(t)r(t)\ne 0$);より&imgtex($p(t)=q(t)=r(t)=1/3$);. --- 図は不動点の周りを&imgtex($p>0, q>0, p+q<1$);を満たしつつ,&imgtex($p=q$);の直線に対称に,原点に近い方の&imgtex($p=q$);の点では&imgtex($q$);が増える方向に矢印を書けばよい.~ &ref(名称未設定.png); -- Euler法で&imgtex(\[\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) &imgtex($h$);を十分小さくとれば,いかなる初期値に対しても,&imgtex($0<p_n, q_n, r_n<1 (n=1,2,\dots)$);となることを示せ. --- &imgtex(\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*});であることに注意する.~ 帰納法で証明する.~ &imgtex($n=0$);での成立は(1)で述べた通りである.~ &imgtex($n+1$);のとき,(**)より&imgtex($|q_n-r_n|\le 1-p_n$);なので,~ &imgtex(\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*});~ である.これより,&imgtex($h\le 1$);であれば,&imgtex($p_{n+1}\ge 0$);. 同様にして,&imgtex($q_{n+1},r_{n+1}>0$);である. ここで,&imgtex($p_{n+1}+q_{n+1}+r_{n+1}=1$);なので, &imgtex($0<p_{n+1},q_{n+1},r_{n+1}<1$);.~ よって,数学的帰納法により題意は示せれた. --(5) 初期値が定常解でないとき,刻み幅&imgtex($h$);を十分小さくとれば, &imgtex($I_n=I(p_n,q_n,r_n)$);は&imgtex($n$);に関して狭義単調減少となることを示せ.また,このときの&imgtex($\{(p_n,q_n)|n=0,1,2,\dots\}$);の略図を図示せよ. ---&imgtex($a=h(q_n-r_n), b=h(r_n-p_n)$);とし,&imgtex($h<1/2$);とする. このとき,&imgtex($|a+b|<1$);であることに注意すると,~ &imgtex(\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*});~ よって,&imgtex($I_n$);は狭義単調減少. ---&imgtex($I_n$);は狭義単調減少であるから,(3)の閉曲線を不動点に向かう螺旋に変形すればよい.(図略) **第3問 [#nda8a6d8] Markov Chain~ &imgtex($Q^{(n)}(j,k)=P(X(n)=k| X(0)=j)$);~ &imgtex($f^{(n)}(j,k)=P(X(n)=k|X(0)=j)*\prod_{1\le l< n}P(X(l)\ne k|X(0)=j)$);~ &imgtex($\bar{Q}_{jk}(z)=\sum_{n=1}^{\infty} Q^{(n)}(j,k)z^n$);~ &imgtex($\bar{f}_{jk}(z)=\sum_{n=0}^{\infty}f^{(n)}(j,k)z^n$);~ と定義する. --(1) &imgtex($\bar{Q}_{jk}=\delta_{jk}+\bar{f}_{jk}(z) \bar{Q}_{kk}(z)$);を示せ. --- &imgtex($n=0$);のとき,&imgtex($Q^{(0)}(j,k)=\delta_{jk}$);,~ &imgtex($n>0$);のとき,&imgtex($Q^{(n)}(j,k)=\sum_{s=0}^n f^{(s)}(j,k)Q^{n-s}(k,k)$);であるから,~ &imgtex(\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) 状態&imgtex($j$);が再帰的であるとき,&imgtex($\bar{f}_{jj}(1)$);の値を求めよ.~ ---&imgtex($\bar{f}_{jj}(1)=\sum_{n=0}^{\infty}f^{(n)}(j,j)$);であるので, 有限ステップで状態&imgtex($j$);に戻ってくる確率を表している. よって,&imgtex($\bar{f}_{jj}(1)=1$);であることが,状態&imgtex($j$);が再帰的であるための必要十分条件. --(3) 条件~ &imgtex(\[\sum_{n=0}^{\infty}Q^{(n)}(j,j)=\infty\]);~ は状態&imgtex($j$);が再帰的であるための必要十分条件であることを示せ. --- &imgtex($\sum_{n=0}^{\infty}Q^{(n)}(j,j)=\bar{Q}_{jj}(1)$);であることに注意する. また(1)より,&imgtex($(1-\bar{f}_{jj}(1))\bar{Q}_{jj}(1)=1$);である. これより,&imgtex($\bar{Q}_{jj}(1)=\infty$);であることが&imgtex($\bar{f}_{jj}(1)=1$);であるための必要十分条件,すなわち&imgtex($j$);が再帰的であるための必要十分条件である. --(4)&imgtex(\begin{align*}Q^{(1)}(j,k)&=\begin{cases}p&(k=j+1)\\1-p&(k=j-1)\\0&(\text{otherwise})\end{cases}\end{align*});~ で定義される1次元ランダムウォークを考える.このとき,&imgtex($\bar{Q}_{00}(z),\bar{Q}_{10}(z), \bar{f}_{10}(z)$);を求めよ. --- &imgtex(\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*});~ であるから,~ &imgtex(\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*}); --- &imgtex(\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*});~ よって,~ &imgtex(\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*}); ---&imgtex($\bar{Q}_{10}(z)=\bar{f}_{10}\bar{Q}_{00}(z)$);なので,~ &imgtex(\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*});~ (カタラン数を使えば直接求めることができるはず...) -- 各頂点が次数&imgtex($d$);の木グラフにおけるランダムウォークを考える. 各頂点から隣合う頂点に等確率で移動するとするとき,枝数で測った距離&imgtex($X(n)$);は&imgtex($S=\{0,1,2,\dots\}$);を状態集合とするマルコフ連鎖となる.&imgtex($n=1$);以降初めて出発点に到達するまでは(4)のランダムウォークとみなせるがこのときの&imgtex($p$);を&imgtex($d$);を用いて表せ. ---確率&imgtex($1/d$);で1離れ,&imgtex($(1-d)/d$);で1近づくので,&imgtex($p=1/d$);. --(5)の&imgtex($X(n):n=0,1,2,\dots$);について&imgtex($\bar{f}_{00}(z)$);を求め, 状態&imgtex($0\in S$);が再帰的でないことを示せ. --- &imgtex($\bar{f}_{00}(z)$);は(4)の意味での&imgtex($\bar{f}_{10}(z)$);となるので,&imgtex($\bar{f}_{00}(z)=\frac{1}{2pz}\left(1-\sqrt{1-4p(1-p)z^2}\right)$);.~ よって,&imgtex($\bar{f}_{00}(1)=\frac{1}{2p}\left(1-\sqrt{1-4p(1-p)}\right)\ne 1$);より状態0は再帰的ではない. **第四問 [#o2f75002] 空間図形~ 時刻&imgtex($t_1$);に日本のある場所から空を見上げたら,遠くの山の頂の点Pと同じ位置に1つの明るい星Aと人工衛星Bとが重なって見えた. その視点における北極星とPの臨み角は&imgtex($\alpha$);であった. 同じ夜の&imgtex($t_1+t_2$);に同じ場所からもう一度空を見上げたら, 星Aと頂Pの臨み角は&imgtex($\beta$);で,一方,人工衛星Bは地球をほぼ一周したあと山の頂Pと同じ位置に見えた. さらに時刻&imgtex($t_1+2t_2$);でも,人工衛星BはPと同じ位置に見えた. 人工衛星Bは地球の自転軸と&imgtex($\theta$);をなす平面を角速度&imgtex($\omega$);で回転運動しているものとする. --(1)経過時間&imgtex($t_2$);を求めよ. ---&imgtex($\alpha=0$);であったり,明るい星Aが月や太陽や惑星ではないものとする.~ 天動説を採用し,北極星を中心にAが&imgtex($\phi$);回転したものとする. これより,地球と北極星の距離を&imgtex($r$);とすると, &imgtex($2r\tan\alpha\sin(\phi/2)=2r\sec\alpha\sin(\beta/2)$);. すなわち,&imgtex($\phi=2\arcsin\left(\frac{\sin(\beta/2)}{\sin\alpha}\right)$);. よって,&imgtex($t_2=\arcsin\left(\frac{\sin(\beta/2)}{\sin\alpha}\right)/\pi$);日. --(2)人工衛星Bの大円軌道に関して考え得る&imgtex($(\theta,\omega)$);を求めよ. ---山の頂を眺める視線は地球の自転と共に地軸に対して回転対称な図形を描く. 人工衛星は地球の中心から等距離を飛ぶので,この図形と地球の中心を中心とする球の交差部,すなわち地軸に垂直な円C上の等間隔な3点でを通ることが分かる. このような3点を通る円はC以外には存在しないので,人工衛星はC上を飛んでいることが分かる. ここで,Cの中心が地球の中心に一致するためには&imgtex($\theta=0$);でなければならない.また,人工衛星の回転方向が地球の自転と同方向である場合と逆方向である場合について考えて,~ &imgtex($\omega=2\pi\left(\frac{1}{t_2}\pm t_2\right) (\text{rad}/\text{day}),\theta=0$);~ ただし例外として~ &imgtex($\beta=0, \omega=\infty, \theta=\frac{\pi}{2}-\alpha$);~ &imgtex($\alpha=0, \beta=0, \omega=\text{any}, \theta=\frac{\pi}{2}$);~ がある. **第五問 [#j49a8fd1] 無向2部グラフ&imgtex(\(G=(V^+\cup V^-,E)\));について、~ 最大マッチングを考える。 -- (1)以下のアルゴリズムが必ずしも最大マッチングを与えないことを~ 例を挙げて示せ。~ &imgtex(\begin{align*}&M:=\emptyset\\&\mathrm{forall}\ e \in E\\&\ \ \mathrm{if}\ M\cup \{e\} \mathrm{\ is\ a\ matching}\\&\ \ \mathrm{then} M:= M\cup \{e\}\end{align*}); --- &imgtex(\(V^+=\{0,1\},\ V^-=\{2,3\},\ E=\{\{1,2\},\{0,2\},\{1,3\}\}\));として、~ &imgtex(\(\{1,2\},\{0,2\},\{1,3\}\));の順に枝が選ばれたら、~ 得られるマッチングは&imgtex(\(\{\{1,2\}\}\));であり、最大マッチング&imgtex(\(\{\{0,2\},\{1,3\}\}\));ではない。 --(2) &imgtex($M_1,M_2$);を&imgtex(G);の2つのマッチングとする. &imgtex($M_1$);と&imgtex($M_2$);の対称差&imgtex($M_1\bigtriangleup M_2$);を枝集合とする&imgtex($G'=(V^+\cup V^-, M_1\bigtriangleup M_2)$);はどのような性質を持つか. ---どの頂点からも高々2本の枝がでているので,いくつかの互いに素なパスができる. --(3) &imgtex($M_1$);を&imgtex($G$);のマッチング, &imgtex($M_2$);を&imgtex($G$);の最大マッチングとする. このとき,(2)で定義された&imgtex($G'$);を用いて, &imgtex($M_1$);が最大であるための必要十分条件を書け. ---&imgtex($G'$);に現れる全てのパスが偶数長であることである. なぜならば,もし奇数長のパスが存在すればそれを用いてマッチングの数を増やすことができ,全て偶数長のパスならば&imgtex($|M_1|=|M_2|$);である. --(4)&imgtex($G$);のマッチング&imgtex($M_1$);に属する枝を&imgtex($V^-$);側から&imgtex($V^+$);側へ, &imgtex($M_1$);に属さない枝を&imgtex($V^+$);側から&imgtex($V^-$);側に向き付けしてできた有効グラフを&imgtex($\vec{G}$);とする. この&imgtex($\vec{G}$);を用い,&imgtex($M_1$);が最大マッチングであるための必要十分条件を示せ. ---&imgtex($M_1\bigtriangleup(M_1\bigtriangleup M_2)=M_2$);であり, &imgtex($M_1\bigtriangleup M_2$);は互いに素なパスの集合であるから, &imgtex($M$);が最大マッチングであるなら始点と終点が&imgtex($M$);でカバーされていないような有向パスが存在せず, 逆に最大マッチングでないならあるパスが存在して始点と終点が&imgtex($M$);でカバーされていない. よって,始点と終点が&imgtex($M$);でカバーされていないような有向パスが存在しないことが最大マッチングであるための必要十分条件. --(5) (4)の結果を利用して,最大マッチングを求めるアルゴリズム,ならびに,その時間計算量を与えよ. ---&imgtex($M=\emptyset$);とする.~ (4)のグラフを作り始点と終点が&imgtex($M$);でカバーされてないようなパスを探索する.これは幅優先探索で実現できるので時間計算量は&imgtex($O(|E|)$);である.このようなパス&imgtex($P$);が見つかったら&imgtex($M=M\bigtriangleup E(P)$);とマッチングを更新する.見つからなかったら終了.~ マッチングの数は&imgtex($min(|V^+|,|V^-|)$);で抑えられるので,全体の時間計算量は,&imgtex($O(min(|V^+|,|V^-|)|E|)$);. ---- とりあえず完成しました.~ 誤植や計算間違い,誤植,誤植などがありましたら修正お願いします.~ ~ - 2-(2)微修正 -- [[tako]] &new{2008-08-22 (金) 18:47:01}; #comment //#comment