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

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

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

• 問11.1

\begin{align}
XZ&=YZ=I \\
(\alpha X+\beta Y)Z&=\alpha XZ+\beta YZ\\
&=\alpha XZ+(1-\alpha)YZ\\
&=\alpha I + I - \alpha I \\
&=I\\
\therefore&\alpha X+\beta YもZの左逆行列
\end{align}

• 問11.2
  • (a)

\begin{align}
xはn行１列の縦長行列とみなせるから&左逆行列を持つ。\\
(\alpha_1+\alpha_2+\cdots+\alpha_n)
\begin{bmatrix}
x_1 \\
x_2 \\
\vdots \\
x_n\\
\end{bmatrix}&=I\\
\alpha_1x_1+\alpha_2x_x+\cdots+\alpha_n x_n&=I \\
\therefore \begin{bmatrix}
\frac{1}{\sqrt{n}} \\
\frac{1}{\sqrt{n}} \\
\vdots \\
\frac{1}{\sqrt{n}}
\end{bmatrix}\\
とノートに書いたが違うな？
\end{align}

• • (b)

\begin{align}
\begin{bmatrix}
x_1 \\
x_2 \\
\vdots \\
x_n \\
\end{bmatrix}
(\alpha_1 \alpha_2 \cdots \alpha_n) &=
\begin{bmatrix}
x_1\alpha_1 & x_1\alpha_2 & \cdots & x_1\alpha_n \\
x_2\alpha_1 & x_2\alpha_2 & \cdots & x_2\alpha_n \\
\vdots \\
x_n\alpha_1 & x_n\alpha_2 & \cdots & x_n\alpha_n \\
\end{bmatrix}=I \\
x_1\alpha_1&=x_2\alpha_2=\cdots=x_n\alpha_n=1で \\
x_2\alpha_1&=0となるものはないから逆行列は存在しない。\\
例えば&\begin{bmatrix}
1 \\
1 \\
\vdots \\
1
\end{bmatrix}である。
\end{align}

• 問11.3
  • (a)

\begin{align}
&2\times2行列で考える。例えば\\
A&=\begin{bmatrix}
1 & 0 \\
2 & 1 \\
\end{bmatrix}のとき\\
Ax&=\begin{bmatrix}
1 & 0 \\
2 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x_{11} & x_{12} \\
x_{21} & x_{22} \\
\end{bmatrix} \\
&=\begin{bmatrix}
x_{11} & x_{12} \\
2x_{11}+x_{21} & 2x_{12}+x_{22} \\
\end{bmatrix}\\
&同様に \\
Ay&=\begin{bmatrix}
y_{11} & y_{12} \\
2y_{11}+y_{21} & 2y_{12}+y_{22} \\
\end{bmatrix}\\
x_{11}&=y_{11}, x_{12}=y_{12} \\
\\
\\
&\left\{
\begin{array}{l}
2x_{11}+x_{21}=2y_{11}+y_{21} \\
2x_{12}+x_{22}=2y_{12}+y_{22} \\
\end{array}
\right. \tag{1}\\

なので例えば\\
x_{11}&=1, y_{11}=2\\
x_{21}&=2, y_{21}=0 \\
x_{12}&=0, y_{12}=-1\\
x_{22}&=1, y_{22}=3\\
でも(1)式&は成り立ってしまい\\
x&\ne yである
\end{align}

• • (b)

\begin{align}
AX&=AYの両辺に左からA^{-1}を掛けると\\
A^{-1}AX&=A^{-1}AY\\
X&=Y
\end{align}

• • (c)

\begin{align}
AX&=AY\\
A(X-YY)&=0\\
ここで&2\times2行列の場合のみを示す\\
\begin{bmatrix}
a & b \\
c & d \\
\end{bmatrix}
\begin{bmatrix}
e & f \\
g & h \\
\end{bmatrix}
&=
\begin{bmatrix}
ae+bg & af+bh \\
ce+dg & cf+dh \\
\end{bmatrix}=0\\
a&=b, e=g, f=-h, c=dとおくと０になる\\
つまり&ad-bd=0でAは正則ではない\\
またX-Y&=\begin{bmatrix}
e & f \\
-e & -f\\
\end{bmatrix}
とすれば\\
X&\ne YかつAX=AYを満たす
\end{align}

• 問11.4

\begin{align}
Uが&直行行列であるとは、\\
U^{\top}U&=UU^{\top}=I\\
である&ことである\\
Uの&転置を考えると\\
(U^{\top})^{\top}U^{\top}&=UU^{\top}\\
U^{\top}(U^{\top})^{\top}&=U^{\top}U\\
つまり(U^{\top})^{\top}U^{\top}&=U^{\top}(U^{\top})^{\top}\\
よって&U^{\top}も直行行列である
\end{align}

• 問11.5
  • (a)

\begin{align}
A&=\begin{bmatrix}
I & a \\
a^{\top} & 0 \\
\end{bmatrix}\\
detA&=detIdet(0-a^{\top}1^{\top}a)\\
&=-det(a^{\top}1a)\\
&=\|a\|\\
detA&\ne0であればAが正則だから\\
a&\ne0であれば良い
\end{align}

• • (b)

A^{-1}=\begin{bmatrix}
0 & \frac{1}{a}\\
\frac{1}{a} & -\frac{1}{a^2}\\
\end{bmatrix}

• 問11.6

\begin{align}
求める逆行列を&
\begin{bmatrix}
W & X\\
Y & Z\\
\end{bmatrix}とおくと\\
A\begin{bmatrix}
W & X\\
Y & Z\\
\end{bmatrix}&=
\begin{bmatrix}
B & C \\
0 & D \\
\end{bmatrix}
\begin{bmatrix}
W & X \\
Y & Z \\
\end{bmatrix}\\
&=\begin{bmatrix}
BW+CY & BX+CZ \\
DY & DZ \\
\end{bmatrix}
&=
\begin{bmatrix}
I & 0 \\
0 & I \\
\end{bmatrix}\\
&\left\{
\begin{array}{r l}
BW+CY&=I \\
DZ&=I \\
BX+CZ&=0\\
DY&=0\\
\end{array}
\right.\\
Y&=0, BW=Iより\\
W&=B^{-1}\\
DZ&=Iより\\
Z&=D^{-1}\\
BX+CD^{-1}&=0\\
BX&=-CD^{-1}\\
X&=-B^{-1}CD^{-1}\\
よって求める逆行列は&
\begin{bmatrix}
B^{-1} & -B^{-1}CD^{-1} \\
0 & D^{-1} \\
\end{bmatrix} 
\end{align}

• 問11.7

  • わからず

• 問11.8

\begin{align}
AA^{-1}&=I\\
また\|AB\|&\le\|A\|\|B\|より\\
\|I\|&=\|AA^{-1}\|\le\|A\|\|A^{-1}\|\\
\|A^{-1}\|&\ge\frac{\|I\|}{\|A\|}=\frac{\sqrt{n}}{\|A\|}\\
\therefore &与式は成り立つ
\end{align}

• 問11.9
  • (a)

\begin{align}
y&=Axとおく\\
(I+BA)x&=0のとき\\
(I+AB)y&=(I+AB)Ax\\
&=IAx+ABAx\\
&=A(I+BA)x\\
(I+BA)x&=0より\\
A(I+BA)x&=0\\
\end{align}

• • (b)

\begin{align}
B(I+AB)&=(I+BA)B\\
B(I+AB)(I+AB)^{-1}&=(I+BA)B(I+AB)^{-1}\\
B&=(I+BA)B(I+AB)^{-1}\\
(I+BA)^{-1}B&=(I+BA)^{-1}(I+BA)B(I+AB)^{-1}\\
(I+BA)^{-1}B&=B(I+AB)^{-1}\\
よって&与式は満たされた
\end{align}

• 問11.10
  • (a)

\begin{align}
x_{t+1}&=Ax_t\\
x_t&=Ax_{t-1}\\
両辺の&左からA^{-1}を掛けると\\
A^{-1}x_t&=A^{-1}Ax_{t-1}\\
x_{t-1}&=A^{-1}x_t\\
よってA^{rev}&=A^{-1}とおけば与式は成り立つ
\end{align}

• • (b)

\begin{align}
A^{rev}&=A^{-1}=\frac{1}{12+2}\begin{bmatrix}
4 & -1 \\
1 & 3 \\
\end{bmatrix}\\
&=\frac{1}{14}
\begin{bmatrix}
4 & -1 \\
1 & 3 \\
\end{bmatrix}
\end{align}

• 問11.11
  • 問8.8の続きだが8.8が解けておらずここもわからず
• 問11.12
  • (a)

\begin{align}
(A+B)&が正則であれば\\
(A+B)C&=AC+BC=I\\
C(A+B)&=CA+CB=I\\
C&=\frac{1}{2}A^{-1}=\frac{1}{2}B^{-1}であれば成立するが\\
これ以外&であれば成立しないので一般には成り立たず\\
\therefore &必ずしも正則ではない
\end{align}

• • (b)

\begin{align}
\begin{bmatrix}
A & 0 \\
0 & B \\
\end{bmatrix}
\begin{bmatrix}
A^{-1} & 0 \\
0 & B^{-1} \\
\end{bmatrix}=
\begin{bmatrix}
I & 0 \\
0 & I \\
\end{bmatrix}\\
よって正則
\end{align}

• • (c) (a)(b)より必ずしも正則ではない
• • (d)

\begin{align}
ABA(A^{-1}B^{-1}A^{-1})&=ABI(B^{-1}A^{-1}\\
&=AIA^{-1}\\
&=I\\
よって正則
\end{align}

• 問11.13

\begin{align}
\tilde{A}A&=\begin{bmatrix}
A_1^{-1} & 0_{n\times (m-n)}
\end{bmatrix}
\begin{bmatrix}
A_1 \\
A_2 \\
\end{bmatrix}\\
&=\begin{bmatrix}
A_1^{-1}A \\
0\cdot A_2 \\
\end{bmatrix}\\
&=\begin{bmatrix}
\mathbf{I} \\
\mathbf{0} \\
\end{bmatrix}\\
&???わからず
\end{align}

• 問11.14
  • (a)
    • Aに右、Bに左逆行列が存在することなので、Aに左正則性があり、Bに右正則性があることつまり、
      • Aに列の線型独立性
      • Bに行の線型独立性
    • があることである。
• • (b)

\begin{align}
AXB&=I\\
A^{-1}AXB&=A^{-1}I\\
XBB^{-1}&=A^{-1}B^{-1}\\
X&=A^{-1}B^{-1}
\end{align}

• 問11.15

\begin{align}
&detAを基本変形で求める\\
&1行\times (1-d_1)-2行\times b_1より\\
&\begin{vmatrix}
0 & b_2 & \cdots & b_{99} & b_{100} \\
1-d_1 & 0 & \cdots & 0 & 0 \\
0 & 1-d_2 & \cdots & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & 1-d_{99} & 0 \\
\end{vmatrix}\\
&同様に繰り返すと\\
&\begin{vmatrix}
0 & 0 & \cdots & 0 & b_{100} \\
1-d_1 & 0 & \cdots & 0 & 0 \\
0 & 1-d_2 & \cdots & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & 1-d_{99} & 0 \\
\end{vmatrix}\\
&よってd_j\ne1かつb_{100}\ne0であれば正則
\end{align}

• 問11.16

\begin{align}
&\begin{vmatrix}
\begin{array}{c c c c c | c c c c c}
1 & 0 & \cdots & 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\
1 & 1 & \cdots & 0 & 0 & 0 & 1 & \cdots & 0 & 0 \\
\vdots &  & \ddots &  & \vdots & \vdots &  & \ddots &  & \vdots \\
1 & 1 & \cdots & 1 & 1 & 0 & 0 & \cdots & 0 & 1 \\
\end{array}
\end{vmatrix}\\
\\
n行-(n-1)行&\begin{vmatrix}
\begin{array}{c c c c c | c c c c c}
1 & 0 & \cdots & 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\
1 & 1 & \cdots & 0 & 0 & 0 & 1 & \cdots & 0 & 0 \\
\vdots &  & \ddots &  & \vdots & \vdots &  & \ddots &  & \vdots \\
0 & 0 & \cdots & 0 & 1 & 0 & 0 & \cdots & 1 & 1 \\
\end{array}
\end{vmatrix}\\
\\
(n-1)行-(n-2)行&\begin{vmatrix}
\begin{array}{c c c c c | c c c c c}
1 & 0 & \cdots & 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\
1 & 1 & \cdots & 0 & 0 & 0 & 1 & \cdots & 0 & 0 \\
\vdots &  & \ddots &  & \vdots & \vdots &  & \ddots &  & \vdots \\
0 & 0 & \cdots & 1 & 0 & 0 & 0 & \cdots & 1 & 0 \\
0 & 0 & \cdots & 0 & 1 & 0 & 0 & \cdots & 1 & 1 \\
\end{array}
\end{vmatrix}\\
\\
これを繰り返すと&\\
&\begin{vmatrix}
\begin{array}{c c c c c | c c c c c}
1 & 0 & \cdots & 0 & 0 & 1 & 0 & \cdots & 0 & 0 \\
0 & 1 & \cdots & 0 & 0 & -1 & 0 & \cdots & 0 & 0 \\
\vdots &  & \ddots &  & \vdots & \vdots &  & \ddots &  & \vdots \\
0 & 0 & \cdots & 1 & 0 & 0 & 0 & \cdots & 1 & 0 \\
0 & 0 & \cdots & 0 & 1 & 0 & 0 & \cdots & -1 & 1 \\
\end{array}
\end{vmatrix}\\
\\
よって逆行列は&\\
&\begin{bmatrix}
1 & 0 & \cdots & 0 & 0 \\
-1 & 1 & & \cdots & 0 & 0 \\
\vdots & & \ddots & & \vdots \\
0 & 0 & \cdots & 1 & 0 \\
0 & 0 & \cdots & -1 & 0 \\
\end{bmatrix}\\
累積行列の階差をとる行列
\end{align}

• 問11.17

\begin{align}
(I-A)(I-A)^{-1}&=(I-A)(I+A+\cdots+A^{k-1})\\
&=I+A+\cdots+A^{k-1}-(A+A^2+\cdots+A^k)\\
&=I-A^k\\
&=I\\
&よって与式は成り立つ
\end{align}

• 問11.18
  • わからず
• 問11.19

\begin{align}
x_{t+1}&=Ax_t+u_t\\
x_k&=Ax_{k-1}\\
x_{k+1}&=Ax_k+u_k\\
&=A(Ax_{k-1})+u_k\\
&=A^2x_{k-1}+u_k\\
x_N&=A^{N-k}x_{N-1}+A^{N-k-2}u_k\\
&=A^{N-k}A^{N-1}x_1+A^{N-k-2}u_k\\
x^{des}&=A^{2N-k-2}x_1+A^{N-k-2}u_k\\
A^{N-k-2}u_k&=x^{des}-A^{2N-k-2}x_1\\
u_k&=(A^{N-k-2})^{-1}x^{des}-(A^{N-k-2})^{-1}A^{2N-k-2}x_1\\
&=(A^{N-k-2})^{-1}x^{des}-A^Nx_1

\end{align}

• 問11.20

\begin{align}
x_{t+1}&=Ax_t+u\\
x_T&=Ax_{T-1}+u\\
&=A(Ax_{T-2}+u)\\
&=A^2x_{T-2}+Au\\
&=\cdots\\
x^{des}&=A^{T-1}x_1+A^{T-2}u\\
(A^{T-2})^{-1}x^{des}&=(A^{T-2})^{-1}A^{T-1}x_1+u\\
u&=(A^{T-2})^{-1}x^{des}-Ax_1\\
Aが正則&であることを条件とする
\end{align}

• 問11.21
  • 問8.１２がわかっておらず解けず
• 問11.22

\begin{align}
A^{\dagger}&=(A^{\top}A)^{-1}A^{\top}より\\
AA^{\dagger}A&=A(A^{\top}A)^{-1}A^{\top}A\\
&=AA^{-1}(A^{\top})^{-1}A^{\top}A\\
&=IIA\\
&=A
\\
A^{\dagger}AA^{\dagger}&=(A^{\top}A)^{-1}A^{\top}A(A^{\top}A)^{-1}A^{\top}\\
&=A^{\dagger}A(A^{\top}A)^{-1}A^{\top}\\
&=A^{\dagger}AA^{-1}(A^{\top})^{-1}A^{\top}\\
&=A^{\dagger}II\\
&=A^{\dagger}
\end{align}

• 問11.23

\begin{align}
ADEB&=AIB\\
&=AB\\
&=I\\
よって&EBはADの擬似逆行列\cdotsで良いか？
\end{align}

• 問11.24

\begin{align}
\begin{bmatrix}
c_{11} & c_{12} & c_{13} & c_{14} \\
c_{21} & c_{22} & c_{23} & c_{24} \\
\end{bmatrix}
\begin{bmatrix}
2 & 2 \\
3 & 1 \\
2 & 1 \\
2 & 2 \\
\end{bmatrix}
&=\begin{bmatrix}
2c_{11} + 3c_{12} + 2c_{13} + 2c_{14} & 2c_{11} + c_{12} + c_{13} + 2c_{14}\\
2c_{21} + 3c_{22} + 2c_{23} + 2c_{24} & 2c_{21} + c_{22} + c_{23} + 2c_{24}\\
\end{bmatrix}\\
&=\begin{bmatrix}
1 & 0 \\
0 & 1 \\
\end{bmatrix}\\
同様に\\
\begin{bmatrix}
3 & 2 \\
1 & 0 \\
2 & 1 \\
1 & 3 \\
\end{bmatrix}
&=\begin{bmatrix}
3c_{11} + c_{12} + 2c_{13} + c_{14} & 2c_{11} + c_{13} + 3c_{14}\\
3c_{21} + c_{22} + 2c_{23} + c_{24} & 2c_{21} + c_{23} + 3c_{24}\\
\end{bmatrix}\\
&=\begin{bmatrix}
1 & 0 \\
0 & 1 \\
\end{bmatrix}\\
&\left\{
\begin{array}{r l}
2c_{11}+3c_{12}+2c_{13}+2c_{14}&=1 \\
2c_{11}+c_{12}+c_{13}+2c_{14}&=1 \\
3c_{11}+3c_{12}+2c_{13}+2c_{14}&=1\\
2c_{11}+3c_{12}+2c_{13}+2c_{14}&=1\\
\end{array}
\right.\\
c_{14}&=0\\
c_{13}&=1\\
c_{11}&=-\frac{1}{2}\\
c_{12}&=0\\
&\left\{
\begin{array}{r l}
2c_{21}+3c_{22}+2c_{23}+2c_{24}&=0 \\
2c_{21}+c_{22}+c_{23}+2c_{24}&=1 \\
3c_{21}+c_{22}+2c_{23}+c_{24}&=0\\
2c_{21}\qquad\:+c_{23}+3c_{24}&=1\\
\end{array}
\right.\\
c_{24}&=0\\
c_{21}&=2\\
c_{23}&=-3\\
c_{22}&=0\\
\therefore c&=\begin{bmatrix}
-\frac{1}{2} & 0 & 1 & 0 \\
2 & 0 & -3 & 0 \\
\end{bmatrix}
\end{align}

• 問11.２５
  • 連立方程式を解くときの後退代入の計算量は$$n^2$$。Axの計算量は$$2n^2$$。
  • nの大きさと計算の正確性をどこまで求めるかによる。
• 問11.26
  • (a)

\begin{align}
x&=A^{-1}b\\
\tilde{A}&=A^{-1}\tilde{b}\\
&=A^{-1}(b+\epsilon e_j)\\
\|x-\tilde{x}\|&=\|A^{-1}b-A^{-1}(b+\epsilon e_j)\|\\
&=\|A^{-1}\epsilon e_j\|\\
よって&\|x-\tilde{x}\|はA, \epsilon, e_jにのみ依存しbに依存しない
\end{align}

• • (b)

\begin{align}
A^{-1}&=\begin{bmatrix}
\alpha_{11} & \alpha_{12} & \cdots & \alpha_{1n} \\
\alpha_{21} & & \cdots & \\
\vdots & & \ddots & \\
\alpha_{n1} & & & \alpha_{nn} \\
\end{bmatrix}
\begin{bmatrix}
e_1 \\
\vdots \\
e_j \\
\vdots \\
e_n\\
\end{bmatrix}\\
A^{-1}の&列の絶対が最大の列
\end{align}

• 問11.27
  • Axーbは常に小さい
  • 計算速度（Google Colaboratory)は下記の通り

import numpy as np
import random
import time
random.seed(123456)

def random_matrix(n):
  matrix = [[0 for _ in range(n)] for _ in range(n)]
  for i in range(n):
      for j in range(n):
          matrix[i][j] = random.randint(0, 9)

  return(np.array(matrix))

def random_vector(n):
  vector = [0 for _ in range(n)]
  for i in range(n):
    vector[i] = random.randint(0, 9)

  return(np.array(vector))

for n in [500, 1000, 2000]:
  sum_calc_time = 0
  for i in range(3):
    A = random_matrix(n)
    A_inv = np.linalg.inv(A)
    b = random_vector(n)
 
    start = time.time()
    x = np.dot(A_inv, b)
    calc_time = time.time() - start
    sum_calc_time += calc_time

    ans = sum(abs(np.dot(A, x) - b))
  
    print('n={}, result: {:.3e},  time={:.3f}'.format(n, ans, calc_time))

  print('average time: {:.3f}s'.format(sum_calc_time / 3))
  print('{:.3f} Gflops'.format(2*n**3 / (sum_calc_time / 3) / 10 ** 9))

n=500, result: 2.444e-09,  time=0.000
n=500, result: 3.072e-10,  time=0.000
n=500, result: 5.718e-09,  time=0.000
average time: 0.000s
1129.525 Gflops
n=1000, result: 3.327e-09,  time=0.001
n=1000, result: 6.884e-09,  time=0.001
n=1000, result: 2.145e-09,  time=0.003
average time: 0.001s
1442.168 Gflops
n=2000, result: 2.899e-08,  time=0.003
n=2000, result: 3.338e-08,  time=0.003
n=2000, result: 2.315e-08,  time=0.003
average time: 0.003s
5444.791 Gflops

• 問11.28

\begin{align}
Ax&=b\\
Ay&=c\\
Az&=dを解く\\
d&=\alpha b+\beta c\\
Az&=d\\
&=\alpha b+\beta c\\
&=\alpha Ax+\beta Ay\\
z&=A^{-1}\alpha Ax+A^{-1}\beta Ay\\
&=\alpha x+\beta y\\
ベクトル&の掛け算の計算量はO(n)だからこの計算量もnに比例する\\
QR分解&の計算量はO(n^2)\\
Ax&=b, Ay=cを解くには\\
3000^2&=9\times10^6回の計算が必要\\
1Gflops&だから\\
9\times\frac{10^6}{10^9}&=9\times10^{-3}s\\
Az&=dは2nだから6\times10^3回\\
6\times\frac{10^3}{10^9}&=6\times10^{-6}s
\end{align}

---

• 『スタンフォード ベクトル・行列からはじめる最適化数学』10章章末問題の解答(1/2)
• 『スタンフォード ベクトル・行列からはじめる最適化数学』10章章末問題の解答(2/2)
• 『スタンフォード ベクトル・行列からはじめる最適化数学』12章章末問題の解答