LoginSignup
0
0

More than 1 year has passed since last update.

@aokikenichi(青木 健一)

『スタンフォード ベクトル・行列からはじめる最適化数学』6章章末問題の解答

Last updated at Posted at 2022-09-18

スタンフォード ベクトル・行列からはじめる最適化数学

の演習問題を解いているが解答が本書内にもネット上にもない模様。自分の解答を晒して間違いにツッコミをいただき理解を深めようという試み。

第6章

  • 問6.1
    • (a)正しい。$n\times m$
    • (b)正しくない。
    • (c)正しくない。
    • (d)正しい。$m\times n$
  • 問6.2
    • $p\times q$
  • 問6.3
    • (a)$Aをp\times qと置いた時、A^{\top}はq\times pでIはq\times q$ $よってKは(p+q)\times(q+p)なので正方行列。\therefore(a)は成り立つ。$
    • (b)Aは縦長でも矛盾しないから必ずしも成立しない。
    • (c)
K^{\top}=
\begin{bmatrix}
I^{\top} & A^{\top}\\
(A^{\top})^{\top} & 0^{\top}\\
\end{bmatrix}
=
\begin{bmatrix}
I & A\\
A^{\top} & 0\\
\end{bmatrix}
=K\\
よって(c)は成り立つ。
    • (d)$Aをp\times qと置いた時、Iはq\times q。0はp\times p。よって必ずしも成り立たない。$
    • (e)成り立つ。
    • 答え (a), (c), (e)
  • 問6.4
(6.2)の隣接行列で考えると、\\
\begin{align}
AI&=
\begin{bmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 \\
\end{bmatrix}
\begin{bmatrix}
1 \\
1 \\
1 \\
1 \\
\end{bmatrix}
=
\begin{bmatrix}
2 \\
2 \\
1 \\
1 \\
\end{bmatrix}
となり、各ノードに向かう有向辺の数。\\
A^{\top}I&=
\begin{bmatrix}
0 & 1 & 0 & 1 \\
1 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 \\
\end{bmatrix}
\begin{bmatrix}
1 \\
1 \\
1 \\
1 \\
\end{bmatrix}
=
\begin{bmatrix}
2 \\
1 \\
1 \\
2 \\
\end{bmatrix}
となり、各ノードから出る有向辺の数。
\end{align}
  • 問6.5
    • 元のグラフのすべての辺の向きを反転ということは元の隣接行列を転置することだから $A^{\top}$
  • 問6.6
    • (a)
\begin{align}
\begin{bmatrix}
y_1 \\
\vdots \\
y_n \\
\end{bmatrix}
&=
\begin{bmatrix}
0 & 0 & I_k \\
0 & I_k & 0 \\
I_k & 0 & 0 \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
\vdots \\
x_n \\
\end{bmatrix}\\
k&=2の時\\
\begin{bmatrix}
y_1 \\
\vdots \\
\vdots \\
\vdots \\
\vdots \\
y_n \\
\end{bmatrix}
&=
\begin{bmatrix}
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
\vdots \\
\vdots \\
\vdots \\
\vdots \\
x_n \\
\end{bmatrix}\\
&=
\begin{bmatrix}
x_{n-1} \\
x_n \\
x_3 \\
x_4 \\
x_1 \\
x_2 \\
\end{bmatrix}\\
\\
&\begin{bmatrix}
x_{n-k} \\
x_{n-(k-1)} \\
\vdots \\
x_n \\
\vdots \\
x_1 \\
\vdots \\
x_k \\
\end{bmatrix}\\
&xをkずつ順序を入れ替えたものが並ぶベクトル。
\end{align}
    • (b)
\begin{align}
k&=2の時\\
\begin{bmatrix}
y_1 \\
\vdots \\
\vdots \\
\vdots \\
\vdots \\
y_n \\
\end{bmatrix}
&=
\begin{bmatrix}
\frac{1}{k} & \frac{1}{k} & 0 & 0 & 0 & 0 \\
\frac{1}{k} & \frac{1}{k} & 0 & 0 & 0 & 0 \\
0 & 0 & \frac{1}{k} & \frac{1}{k} & 0 & 0 \\
0 & 0 & \frac{1}{k} & \frac{1}{k} & 0 & 0 \\
0 & 0 & 0 & 0 & \frac{1}{k} & \frac{1}{k} \\
0 & 0 & 0 & 0 & \frac{1}{k} & \frac{1}{k} \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
\vdots \\
\vdots \\
\vdots \\
\vdots \\
x_n \\
\end{bmatrix}\\
&=
\begin{bmatrix}
\frac{x_1+x_2}{2} \\
\frac{x_1+x_2}{2} \\
\frac{x_3+x_4}{2} \\
\frac{x_3+x_4}{2} \\
\frac{x_5+x_6}{2} \\
\frac{x_5+x_6}{2} \\
\end{bmatrix}\\
\\
&\begin{bmatrix}
\left.
  \begin{array}{l}
  　　\frac{x_1+\cdots+x_k}{k} \\
  　　\quad\vdots \\
  　　\frac{x_1+\cdots+x_k}{k}
  \end{array}
\right \}k個 \\
\vdots \\
\left.
  \begin{array}{l}
  　　\frac{x_{n-k}+\cdots+x_n}{k} \\
  　　\quad\vdots \\
  　　\frac{x_{n-k}+\cdots+x_n}{k}
  \end{array}
\right \}k個 \\
\end{bmatrix}\\
&xをkずつ平均をとったものが並ぶベクトル。
\end{align}
  • 問6.7
\begin{align}
R&=
\begin{bmatrix}
1      & R_{12} & \cdots & \cdots & R_{1n} \\
R_{21} & 1      & R_{23} & \cdots & R_{2n} \\ 
\\
\vdots &        & \ddots &        & \vdots \\
\\
R_{n1} & \cdots & \cdots & \cdots & 1 \\
\end{bmatrix}
\\
y&=R
\begin{bmatrix}
x_1 \\
\\
\\
\vdots \\
\\
x_n \\
\end{bmatrix}\\
&=\begin{bmatrix}
1      & R_{12} & \cdots & \cdots & R_{1n} \\
R_{21} & 1      & R_{23} & \cdots & R_{2n} \\ 
\\
\vdots &        & \ddots &        & \vdots \\
\\
R_{n1} & \cdots & \cdots & \cdots & 1 \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
\\
\\
\vdots \\
\\
x_n \\
\end{bmatrix}\\
&=
\begin{bmatrix}
x_1 + R_{12}x_2+\cdots+R_{1n}xn \\
\vdots \\
R_{n1}x_1+\cdots+\cdots++x_n \\
\end{bmatrix}
\end{align}
\\
y_iは通貨i換算での保有額。
  • 問6.8
\begin{align}
c&=
\begin{bmatrix}
c_1 \\
c_2 \\
\vdots \\
c_T \\
\end{bmatrix}\\
b_1&=1\\
b_t&=(1+r)b_{t-1}+c_t\quad t=2,\cdots, T\\
b&=Ac\\
b&=
\begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1T} \\
a_{21} &        &        &  \\
\vdots &        & \ddots &  \vdots \\
a_{T1} &        & \cdots & a_{TT} \\
\end{bmatrix}
\begin{bmatrix}
c_1 \\
c_2 \\
\vdots \\
c_T \\
\end{bmatrix}\\
b_1&=a_{11}c_1+a_{12}c_2+\cdots+a_Tc_T\\
&=c_1より、\\
a_{11}&=1, \quad a_{12}, \cdots, a_T=0\\
b_2&=a_{21}c_1+a_{22}c_2+\cdots+a_{2T}c_T\\
&=a_{21}b_1+\cdots+a_{2T}c_T\\
&=(1+r)b_1+c_2より、\\
a_{21}&=(1+r), \quad a_{22}=1, \quad a_{23}, \cdots, a_{2T}=0\\
b_3&=a_{31}c_1+a_{32}c_2+a_{33}c_3+\cdots+a_{3t}c_T\\
&=(1+r)b2+c3\\
&=(1+r)\{(1+r)b_1+c_2\}+c_3\\
&=(1+r)^2b_1+(1+r)c_2+c_3\\
&=(1+r)^2c_1+(1+r)c_2+c_3より、\\
a_{31}&=(1+r)^2, a_{32}=1+r, a_{33}=1, \quad a_{34}, \cdots, a_{3T}=0\\
\vdots\\
\therefore 
A&=\begin{bmatrix}
1       & 0 & \cdots & & & 0 \\
1+r     & 1 & \cdots & & & 0 \\
(1+r)^2 & 1+r & 1 & \cdots & & 0 \\
\vdots & & \ddots & & & \vdots \\
(1+r)^{T-1} & (1+r)^{T-2} & \cdots & & & 1 \\
\end{bmatrix}\\
\end{align}\\
Aのt行目は過去の一期間につき、(1+r)の利子を掛けたものとなっている。
  • 問6.9
    • (a) $|c|$
    • (b) $\mathbf{1}$
    • (c) $R\cdot a$
    • (d) $max(R_{3,j}) \quad j=1,\cdots,n\quadの時のjメディア$
    • (e)　市場区分３に対するメディア５のインプレッションが非常に弱い。
  • 問6.10
    • (a) $Y=Rx$
    • (b) $c=pR$ で良いか？
  • 問6.11
    • (a)
\begin{align}
Ax&=
\begin{bmatrix}
a_{11}x1+a_{12}x_2+\cdots+a_mx_n \\
\vdots \\
a_{m1}x_1+a_{m2}x_2+\cdots+a_mx_n \\
\end{bmatrix}\\
Bx&=
\begin{bmatrix}
b_{11}x1+b_{12}x_2+\cdots+b_mx_n \\
\vdots \\
b_{m1}x_1+b_{m2}x_2+\cdots+b_mx_n \\
\end{bmatrix}\\
これが全てのxについて成り立つのだから\\
A=B。
\end{align}
    • (b) ０でないA=Bが成り立つ場合もある。
  • 問6.12
    • (a)
\begin{align}
A&=\begin{bmatrix}
a_{11} & a_{12} \\
a_{21} & a_{22} \\
\end{bmatrix}とおくと、 \\

\begin{bmatrix}
a_{11} & a_{12} \\
a_{21} & a_{22} \\
\end{bmatrix}&=
\begin{bmatrix}
-a_{11} & -a_{21} \\
-a_{12} & -a_{22} \\
\end{bmatrix}から\\
a_{11}&=0, a_{22}=0, a_{21}=-a_{12} つまり、\\
A&=
\begin{bmatrix}
0 & a \\
-a & 0 \\
\end{bmatrix} \quad aは任意の実数
\end{align}
    • (b) 対角要素は転置しても変わらず、歪対称行列正負が逆転する必要があり、0しかあり得ないため。
    • (c)
\begin{align}
x^{\top}(Ax)&=\sum_{i,j=1}^n{A_{ij}x_ix_j} \\
i&=jの時A_{ij}=0\\
i&\ne jの時A_{ij}=A_{ji} \\
よって、\\
x^{\top}(Ax)&=0\\
つまり、\\
Ax&\perp x
\end{align}
    • (d)
\begin{align}
A&=
\begin{bmatrix}
a_{11} & a_{21} & \cdots & a_{n1} \\
a_{21} &        &        & \\
\vdots &        & \ddots & \vdots \\
a_{n1} &        & \cdots & a_{nn} \\
\end{bmatrix}とおく。\\
ここで、(e_i+e_j)^{\top}(A(e_i+e_j))&=A_{ii}+A_{jj}+A_{ij}+A_{ji}\\
任意のxについて(Ax)&\perp xだから\\
A_{ii}+A_{jj}+A_{ij}+A_{ji}&=0\\
i=jの時 A_{ii}&=0\\
i\ne jの時 A_{ij}&=-A_{ji}\\
よってAは歪対称行列である。
\end{align}
  • 問6.13
\begin{align}
p(t)&=c_1+c_2t+\cdots+c_nt^{n-1}\\
p'(t)&=c_2+2c_3t+\cdots+(n-1)c_nt^{n-2}\\
&=d_1+d_2t+\cdots+d_{n-1}t^{n-2}\\
d_1&=c_2\\
d_2&=2c_3\\
d_3&=3c_4\\
\vdots\\
d_{n-1}&=(n-1)c_n\\
\begin{bmatrix}
d_1 \\
d_2 \\
\\
\vdots \\
d_{n-1} \\
\end{bmatrix}
&=\begin{bmatrix}
0 & 1 & 0 &   &   & \cdots & 0 \\
0 & 0 & 2 & 0 &   & \cdots & 0 \\
0 & 0 & 0 & 3 & 0 & \cdots & 0 \\
\vdots & & & \ddots & & & \vdots \\
0 & & & \cdots & & 0 & n-1 \\
\end{bmatrix}
\begin{bmatrix}
c_1 \\
c_2 \\
\\
\vdots \\
c_n \\
\end{bmatrix}\\
\therefore D&=
\begin{bmatrix}
0 & 1 & 0 &   &   & \cdots & 0 \\
0 & 0 & 2 & 0 &   & \cdots & 0 \\
0 & 0 & 0 & 3 & 0 & \cdots & 0 \\
\vdots & & & \ddots & & & \vdots \\
0 & & & \cdots & & 0 & n-1 \\
\end{bmatrix}\\
&(n-1)\times n次元\\
\end{align}\\
  • 問6.14
\begin{align}
Aの&i行目をa_i^Tとするコーシー・シュワルツの不等式より、\\
|a_i^Tx|&\le\|a_i\|\|x\| \\
iを&1行目からm行目まで足すと\\
\|Ax\|&\le\|A\|\|x\|
\end{align}
  • 問6.15
\begin{align}
\|A-B\|^2&=\sum_{i=1}^n{\sum_{j=1}^n{|a_{ij}-b_{ij}|^2}} \\
a_{ij}, b_{ij}&とも１つまりjから、iから有向辺が存在すれば\\
|a_{ij}-b_{ij}|^2&=0\\
|a_{ij}-b_{ij}|^2&=1となるのは、\\
a_{ij}&=0でb_{ij}=1または\\
a_{ij}&=1でb_{ij}=0つまり\\
一方のグラフ&には有向辺があるが一方には含まれない時である。\\
\therefore \|A-B\|^2&は一方のグラフには含まれているが\\
一方のグラフ&には含まれていない有向辺の数を表す。
\end{align}
  • 問6.16
D=
\begin{bmatrix}
-1 &  1 &  0 &    & \cdots &  0 &  0 &  0 \\
0  & -1 &  1 &  0 & \cdots &  0 &  0 &  0 \\
\vdots & & & & \ddots & & & \vdots \\
0  &  0 &  0 &    & \cdots & -1 &  1 &  0 \\
0  &  0 &  0 &    & \cdots &  0 & -1 &  1 \\ 
\end{bmatrix}\\
各列を他の列の線型結合では表せられないからDの列は線型独立である。
  • 問6.17
\begin{align}
S&=
\begin{bmatrix}
a_{11} &        & \cdots &   & a_{1n} \\
\vdots &        & \ddots &   & \vdots \\
a_{m1} &        & \cdots &   & a_{mn} \\
1      & 0      & \cdots & 0 & 1 \\
0      & 1      & \cdots & 0 & 0 \\
\vdots &        & \ddots &   & \vdots \\
0      & 0      & \cdots & 0 & 1 \\
\end{bmatrix}\\
&Sの列は後半n個が線型独立なので常に線型独立。\\
&Sの行はAが線型独立かつAの行が単位行列と同じものがない時に限り線型独立となる。
\end{align}
  • 問6.18
    • 分からず。
  • 問6.19
    • $m\times n$ 行列とn次元ベクトルxとの行列ベクトル積の計算にはm(2n-1)flopsかかるから、$T\times n$ 行列とn次元ベクトル積の計算にはT(2n-1)flopsかかる。
\begin{align}
2500(2\cdot 500-1)flops&=2500\cdot 9999 \\
&\simeq 2.5\times 10^7flops \\
\frac{2.5\times 10^7}{1\times 10^9}&=0.025 \\
\therefore 0.025秒
\end{align}
  • 問6.20
\begin{align}
6.5節の方法ではm(2n-1)flops\\
ここでの方法では\\
a_{11}x_1+\cdots+a_{1n}x_m \\
\vdots \\
a_{m1}x_1+\cdots+a_{mn}x_m \\
m\cdot n \quad flops\\
よって\\
m(2n-1)-mn&=2mn-m-mn\\
&=m(n-1)\\
6.5節の方法と比べてm(n-1)\quad flopsだけ短縮される。
\end{align}
  • 問6.２１
    • $ m(2\cdot nnz(x)) $ ?
  • 問6.22
    • (a)$ mn+n+m(2n-1)=3mn+n-m $
      • 答え 3mn+n-m flops
    • (b)
\begin{align}
4mn \quad flops \\
4mn&\gt 3mn+n-m \\
m(n+1)&\gt n \\
m&\gt \frac{n}{n+1}の時(a)の方が小さい\\
&だがm, nは正の整数でありこれは常に成り立って\\
&しまうので、どこかで間違っていそう。
\end{align}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0