院試過去問 2003年度数学のバックアップ(No.3) - PukiWiki

[ トップ ] [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ] [ リンク元 ]

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
院試過去問 2003年度数学へ行く。
- 1 (2008-08-19 (火) 14:04:37)
- 2 (2008-08-19 (火) 16:03:09)
- 3 (2008-08-20 (水) 13:38:47)
- 4 (2008-08-22 (金) 17:29:20)
- 5 (2009-06-04 (木) 11:13:08)
- 6 (2009-06-04 (木) 11:13:08)
- 7 (2009-08-04 (火) 20:33:26)

院試過去問の解答

院試過去問 2003年度数学 †

第1問 †

tex表記は面倒なので、分かる範囲でタイプ数を減らしています(太字でない等)

(1)
- 1.
  $\| Ax \| \ge 0 \Rightarrow \sigma (A) \ge 0$
  ${}^\forall \| x \|=1, \| Ax\|=0 \Leftrightarrow A=O$
- 2.
  $\| \sigma Ax\|=|\sigma|\| Ax \|$
- 3.
  $\sigma(A+B) = \| (A+B)x\|=\| Ax +Bx \| \le \| Ax\| +\| Bx\|=\sigma(A)+\sigma(B)$
(2)
...を計算に関係ない部分として、
$A_1 =\begin{pmatrix} \alpha & w^T \\ z & A_2 \end{pmatrix}=U^T AV_1 = U_1^TA(x_1,x_2,...) = U_1^T (\sigma_1 y_1,...) =\begin{pmatrix} \sigma_1y_1^Ty_1 & \dots \\ \sigma_1y_2^Ty_1 & \dots \\ \vdots & \dots \end{pmatrix} = \begin{pmatrix}\sigma_1 & w^T \\ O & A_2 \end{pmatrix}$
なので、 $\alpha=\sigma_1,z=0$ である。
(3)
$\| A_1 \begin{pmatrix}\sigma_1 \\ w \end{pmatrix}\| = \| \begin{pmatrix} \sigma_1^2 + w^Tw \\ A_2 w \end{pmatrix} \| \ge \sigma_1^2 + w^Tw$
(4) $\| x\|=1 \Leftrightarrow \| V_1^T x\|=\| x' \|=1$ を用いる。 $\| Ax\|=\| U_1A_1V_1^T x \|=\| U_1\| \| A_1 x'\| = \| A_1 x'\|$
であり、 $\| Ax\|$ を最大にするxをとりx'に変換すれば、 $\| A_1x'\|$ は最大になる。よって $\sigma(A)=\sigma(A_1) = \sigma_1$
(5)
$\sigma_1 \ge \left\| A_1 \frac{1}{\| \begin{pmatrix} \sigma_1 \\ w \end{pmatrix} \|} \begin{pmatrix} \sigma_1 \\ w \end{pmatrix} \right\| \ge \frac{1}{\| \begin{pmatrix} \sigma_1 \\ w \end{pmatrix} \|} (\sigma_1^2 + w^Tw)= \sqrt{\sigma_1^2 + w^Tw }$
なので、w=0
(6)
$\sigma(A_2)=\sigma_2$ とおく。あるx2が存在し、x2,y2を単位ベクトルとして。 $\sigma_2y_2=A_2x_2$ とできる。
$\| A_1 \begin{pmatrix} 0 \\ x_2 \end{pmatrix} \| = \left\| \begin{pmatrix} \sigma_1 & 0 \\ 0 & A_2 \end{pmatrix} \begin{pmatrix} 0 \\ x_2 \end{pmatrix} \right\| =\left\| \sigma_2 \begin{pmatrix} 0 \\ y_2 \end{pmatrix} \right\| = \sigma_2$
$\sigma(A_2) = \sigma_2 \le \sigma(A_1)$
なぜならば、 $\sigma$ の定義にはmaxを用いているから。
(7)
略、補完希望

第2問 †

(1)
$F' = \sqrt{f'} -\frac{1}{2} f f'^{-\frac{3}{2}} f''$
(2)
$F'' = \frac{3}{4} f f'^{-\frac{5}{2}} f'' -\frac{1}{2} f f'^{-\frac{3}{2}} f''$
(3)
を用いる。
$\lim_{x \rightarrow r} \frac{G(x) -r }{(x-r)^2}=\lim_{x \rightarrow r} \frac{x -r -\frac{F}{F'} }{(x-r)^2} = \lim_{x \rightarrow r} \frac{1 -\frac{F - F(r)}{(x-r)F'} }{(x-r)} = \lim_{x \rightarrow r} \frac{1 -\frac{F'}{F'} }{(x-r)} =0$
となる。

第3問 †

(1)
全てのi,jに対し、
$\sigma(G_i^{l-1}) -\sigma(G_j^{l-1}) \le \max\{ a_1,\cdots,a_n \}$
が成り立っているとき。 $\sigma(G_i^{l-1}) \ge \sigma(G_j^{l-1})$ ならば
$\sigma(G_i^{l}) -\sigma(G_j^{l}) \le \sigma(G_i^{l-1}) - \sigma(G_j^{l-1}) -a_l \le \max\{ a_1,\cdots,a_n \}$
不等号が逆の場合もほぼ同様。
$\max\{ a_1,\cdots,a_n \}$ を満たすものをahとする。ahを含むグループの値はah以上なので、右側の不等号の成立が言える。
(2)
ahを特別視して、残りのn-1個をできるだけ均等に分割すると、 $\frac{1}{m}\sum_{k\ne h} a_k$ となり、どの時点でもこの値と同じか小さいグループがあるので、これより大きいグループにahが足されることはあり得ない。よって
$P(\Delta ) \le \frac{1}{m}\sum_{k\ne h} a_k + a_h = \frac{1}{m}\sum_{k=1}^n a_k + (1-\frac{1}{m}) \max\{ a_1,\cdots,a_n \}$
(3)
$\frac{1}{m} \sum_{k=1}^{n}a_k \le P( \Delta_opt) \because \sum a_i =\sum \sigma(G_i) \le m \max \sigma(G_i)$
(1)の右側の不等式、(2)を用いれば(3)が示せる。
(4)
添え字1からm(m-1)までai=1で、最後がmの数列を考える。合計m^2であり、最適な分割では全ての大きさをmにできるが、このアルゴリズムを用いると、m(m-1)個を分割した時点で全ての分割の大きさがm-1になり、最後、大きさmの数字を分割した時点で、最大のグループの大きさは2m-1となる。

第4問 †

行列を実対称行列とし，関数をと定義する．ただし，制約の元での極値を求める問題について議論する．ラグランジュ関数をと定義する．
- (1)を求めよ．
  - $\frac{\partial L}{\partial x}=2Ax-2\lambda x-2\mu b.$
    $\frac{\partial L}{\partial \lambda}=1-\|x\|^2$
    $\frac{\partial L}{\partial \mu}=-2b^{\top}x$
- (2)ベクトルのとき，は行列Aの固有ベクトルになることを示せ．
  - のとき， $2A\bar{x}-2\bar{\lambda} \bar{x}=0$ となるので， $A\bar{x}=\bar{\lambda} \bar{x}$ より $\bar{x}$ は $\bar{\lambda}$ に対応する固有ベクトルとなる．
- (3)Aを $a_{11}<a_{22}<\dots <a_{nn}$ を満たす対角行列とし，の要素は全て非ゼロとする．
- (3-1)を求めよ．
  - $\partial L/\partial x_i=2(Ax-\lambda x-\mu b)_i=2(a_{ii}x-\lambda x_i-\mu b_i)$
- (3-2)「かつ」が成り立たないことを示せ．
  - 成立を仮定すると， $\bar{\lambda}=a_{jj}$ なるが存在する．これより， $\mu=0$ , $i\ne j$ ならばとなり， $x_j=\pm 1$ ．これより， $b^{\top}x=\pm b_j\ne 0$ となり矛盾．
- (3-3)「かつ」が成り立たないことを示せ．
  - 成立を仮定すると，任意のについてとなり $\|x\|=1$ に矛盾．
- (3-4)「かつ」が成り立たないことを示せ．
  - 成立を仮定すると， $\mu=0$ となり矛盾．
- (4)行列はを満たすの対角行列とし，とする．の中の点を全て求めよ．
  - 束縛条件は，
    $\begin{align*}x_1(2-\lambda)&=\sqrt{3}\mu\\x_2(4-\lambda)&=\sqrt{2}\mu\\x_3(6-\lambda)&=\sqrt{3}\mu\\x_1^2+x_2^2+x_3^2&=1\\\sqrt{3}x_1+\sqrt{2}x_2+\sqrt{3}x_3=0\end{align*}$
    なので， $\mu\left(\frac{3}{2-\lambda}+\frac{2}{4-\lambda}+\frac{3}{6-\lambda}=0\right).$
    ここで， $\mu\ne 0$ ならば， $\lambda=3,5$ ． $\mu=\pm\frac{\sqrt{3}}{4}$ ．これより， $\mu=0$ のときは(3-2)と(3-3)が矛盾するので解なし．
- (5)が極値を与えないことを示せ．
  - $A=\begin{pmatrix}0&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&-1\end{pmatrix}$ とすれば良い．極値を与えないことは自明に明らか．

第5問 †

第6問 †

(1)
4個のボールを2個の箱に分配するとき、(4,0),(3,1),(2,2),(1,3),(0,4)の5通りが考えられるが、(4,0)を○○○○｜や、(1,3)を○｜○○○のように、ボールと(S-1)個の仕切りを並べる並べ方の問題と同一視できる。よって
$\frac{(N+S-1)!}{N!(S-1)!}$
通りの分配が存在する。
(2)
N<Sの時は考えないことにする。はじめに1個のボールを全ての箱に入れてしまう。そうすれば、残りのN-S個のボールをS個の箱に入れる問題に読み替えることができる。(1)の結果を用いて、
$\frac{(N-1)!}{(N-S)!(S-1)!}$
(3)
n>Nといった特殊な状況は考えないことにする。ある箱にn個のボールが入っていれば、残りはN-n個である。また、残りの箱はS-1個である。この分配の仕方は、(1)を用いて、
$\frac{(N-n+S-2)!}{(N-n)!(S-2)!}$
通りである。だから、全ての分配の数で割ることにより
$\begin{eqnarray*} P(n,N,S)&=&\frac{(N-n+S-2)! N!(S-1)!}{(N+S-1)!(N-n)!(S-2)!}=\frac{N(N-1)\cdots(N-n+1) \cdot (S-1)}{(N+S-1)(N+S-2)\cdots (N+S-n-1)} \\ &=& \frac{N^n \quad 1(1-\frac{1}{N})(1-\frac{2}{N})\cdots(1-\frac{n-1}{N}) S (1-\frac{1}{S})}{S^{n+1} (\frac{N}{S}+1-\frac{1}{S})(\frac{N}{S}+1-\frac{2}{S})\cdots (\frac{N}{S}+1-\frac{n+1}{S})} \\ &=& r^n \frac{1(1-\frac{1}{N})(1-\frac{2}{N})\cdots(1-\frac{n-1}{N})(1-\frac{1}{S})}{(r+1-\frac{1}{S})(r+1-\frac{2}{S})\cdots (r+1-\frac{n+1}{S})} \end{eqnarray*}$
なので、
$\lim_{N,S \to \infty , N/S =r} P(n,N,S)= \lim_{N,S \to \infty , N/S =r} r^n \frac{1(1-\frac{1}{N})(1-\frac{2}{N})\cdots(1-\frac{n-1}{N})(1-\frac{1}{S})}{(r+1-\frac{1}{S})(r+1-\frac{2}{S})\cdots (r+1-\frac{n+1}{S})} = \frac{r^n}{(r+1)^{n+1}}$

コメント †