京都大学 情報学研究科 システム科学専攻 2022年8月実施 数学【I】 Author 机智的若叶 , 祭音Myyura
Description ベクトル x x x m m m A x = b A x = b A x = b m m m A A A P − Q P - Q P − Q P x = Q x + b P x = Q x + b P x = Q x + b x 0 x_0 x 0 x n + 1 = Q x n + b x_{n+1} = Q x_n + b x n + 1 = Q x n + b x n + 1 = P − 1 ( Q x n + b ) x_{n+1} = P^{-1} (Q x_n + b) x n + 1 = P − 1 ( Q x n + b ) A A A P P P
ただし、 m m m Z Z Z Z − 1 Z^{-1} Z − 1 Z T Z^T Z T ρ ( Z ) \rho (Z) ρ ( Z ) ρ ( Z ) \rho (Z) ρ ( Z ) Z Z Z λ i \lambda_i λ i ( i = 1 , … , m ) (i = 1, \ldots, m) ( i = 1 , … , m ) max i ∣ λ i ∣ \max_i |\lambda_i| max i ∣ λ i ∣
(i) P − 1 P^{-1} P − 1 P x = Q x + b P x = Q x + b P x = Q x + b x n + 1 = Q x n + b x_{n+1} = Q x_n + b x n + 1 = Q x n + b
x − x n + 1 = P − 1 Q ( x − x n ) x - x_{n+1} = P^{-1} Q (x - x_n) x − x n + 1 = P − 1 Q ( x − x n ) となる。
P − 1 Q P^{-1} Q P − 1 Q n → ∞ n \to \infty n → ∞ x 0 x_0 x 0 x n x_n x n ρ ( P − 1 Q ) \rho (P^{-1} Q) ρ ( P − 1 Q )
以下の設問では、次の方程式をヤコビ法を用いて解く場合について考える。
A x = b , A = [ 12 − 4 3 − 3 4 0 3 − 2 4 ] , b = [ 5 1 − 3 ] (1) A x = b, \quad A = \begin{bmatrix} 12 & -4 & 3 \\ -3 & 4 & 0 \\ 3 & -2 & 4 \end{bmatrix}, \quad b = \begin{bmatrix} 5 \\ 1 \\ -3 \end{bmatrix} \tag{1} A x = b , A = 12 − 3 3 − 4 4 − 2 3 0 4 , b = 5 1 − 3 ( 1 ) (ii) P P P Q Q Q P − 1 P^{-1} P − 1
(iii) P − 1 Q P^{-1} Q P − 1 Q P − 1 Q P^{-1} Q P − 1 Q
(iv) x 0 = [ 0 0 0 ] x_0 = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} x 0 = 0 0 0 x 1 x_1 x 1
(v) A − 1 A^{-1} A − 1
行列 A A A n × n n \times n n × n a i j ( i , j = 1 , … , n ) a_{ij} (i, j = 1, \ldots, n) a ij ( i , j = 1 , … , n )
∑ j = 1 n a i j = 1 , i = 1 , … , n \sum_{j=1}^n a_{ij} = 1, \quad i = 1, \ldots, n j = 1 ∑ n a ij = 1 , i = 1 , … , n を満たすと仮定する。以下の設問に答えよ。ただし、 u u u n n n
(i) A u = u A u = u A u = u
(ii) 任意の零ベクトルでない n n n x x x x x x x m x_m x m i ∈ { 1 , … , n } i \in \{1, \ldots, n\} i ∈ { 1 , … , n }
∣ ∑ j = 1 n a i j x j ∣ ≤ ∣ x m ∣ \left| \sum_{j=1}^n a_{ij} x_j \right| \leq |x_m| j = 1 ∑ n a ij x j ≤ ∣ x m ∣ が成り立つことを示せ。
(iii) A A A λ \lambda λ ∣ λ ∣ ≤ 1 |\lambda| \leq 1 ∣ λ ∣ ≤ 1
(iv) n = 2 n = 2 n = 2 A A A
A = [ 1 − α α α 1 − α ] , 0 < α ≤ 1 A = \begin{bmatrix}
1 - \alpha & \alpha \\
\alpha & 1 - \alpha
\end{bmatrix}, \quad 0 < \alpha \leq 1 A = [ 1 − α α α 1 − α ] , 0 < α ≤ 1 を取るとする。
設問 (i) から、 A A A λ 1 = 1 \lambda_1 = 1 λ 1 = 1 u = u / 2 u = u / \sqrt{2} u = u / 2 λ 2 \lambda_2 λ 2 w w w w w w
(v) 設問 (iv) の A A A A k A^k A k
B = lim k → ∞ A k B = \lim_{k \to \infty} A^k B = k → ∞ lim A k が存在する α \alpha α B B B
题目描述
回答以下两题。
考虑用迭代法求解关于 m m m x \boldsymbol{x} x
A x = b . A\boldsymbol{x}=\boldsymbol{b}. A x = b . 把 m m m A = P − Q A=P-Q A = P − Q
P x = Q x + b . P\boldsymbol{x}=Q\boldsymbol{x}+\boldsymbol{b}. P x = Q x + b . 给定初值 x 0 \boldsymbol{x}_0 x 0 x k + 1 = Q x k + b \boldsymbol{x}_{k+1}=Q\boldsymbol{x}_k+\boldsymbol{b} x k + 1 = Q x k + b
x k + 1 = P − 1 ( Q x k + b ) . \boldsymbol{x}_{k+1}
=P^{-1}(Q\boldsymbol{x}_k+\boldsymbol{b}). x k + 1 = P − 1 ( Q x k + b ) . 当 P P P A A A Z − 1 Z^{-1} Z − 1 Z T Z^{\mathrm T} Z T ρ ( Z ) \rho(Z) ρ ( Z ) m m m Z Z Z λ i \lambda_i λ i i = 1 , … , m i=1,\ldots,m i = 1 , … , m Z Z Z
ρ ( Z ) = max i ∣ λ i ∣ . \rho(Z)=\max_i|\lambda_i|. ρ ( Z ) = i max ∣ λ i ∣.
假设 P − 1 P^{-1} P − 1
x − x k + 1 = P − 1 Q ( x − x k ) . \boldsymbol{x}-\boldsymbol{x}_{k+1}
=P^{-1}Q(\boldsymbol{x}-\boldsymbol{x}_k). x − x k + 1 = P − 1 Q ( x − x k ) . 再假设 P − 1 Q P^{-1}Q P − 1 Q ρ ( P − 1 Q ) \rho(P^{-1}Q) ρ ( P − 1 Q ) k → ∞ k\to\infty k → ∞ x 0 \boldsymbol{x}_0 x 0 x k \boldsymbol{x}_k x k
以下各问针对用 Jacobi 法求解
A x = b , A = [ 12 − 4 3 − 3 4 0 3 − 2 4 ] , b = [ 5 1 − 3 ] . (1) A\boldsymbol{x}=\boldsymbol{b},\qquad
A=
\begin{bmatrix}
12&-4&3\\
-3&4&0\\
3&-2&4
\end{bmatrix},
\qquad
\boldsymbol{b}=
\begin{bmatrix}
5\\
1\\
-3
\end{bmatrix}.
\tag{1} A x = b , A = 12 − 3 3 − 4 4 − 2 3 0 4 , b = 5 1 − 3 . ( 1 )
求 P P P Q Q Q P − 1 P^{-1} P − 1
求 P − 1 Q P^{-1}Q P − 1 Q
取
x 0 = [ 0 0 0 ] , \boldsymbol{x}_0=
\begin{bmatrix}
0\\0\\0
\end{bmatrix}, x 0 = 0 0 0 , 求 x 1 \boldsymbol{x}_1 x 1 A − 1 A^{-1} A − 1
设 A = ( a i j ) A=(a_{ij}) A = ( a ij ) n × n n\times n n × n 1 1 1
∑ j = 1 n a i j = 1 , i = 1 , … , n . \sum_{j=1}^n a_{ij}=1,
\qquad i=1,\ldots,n. j = 1 ∑ n a ij = 1 , i = 1 , … , n . 令 u \boldsymbol{u} u 1 1 1 n n n
证明 A u = u A\boldsymbol{u}=\boldsymbol{u} A u = u
对任意非零实向量
x = ( x 1 , … , x n ) T \boldsymbol{x}=(x_1,\ldots,x_n)^{\mathrm T} x = ( x 1 , … , x n ) T x m x_m x m i ∈ { 1 , … , n } i\in\{1,\ldots,n\} i ∈ { 1 , … , n }
∣ ∑ j = 1 n a i j x j ∣ ≤ ∣ x m ∣ . \left|\sum_{j=1}^n a_{ij}x_j\right|
\leq|x_m|. j = 1 ∑ n a ij x j ≤ ∣ x m ∣.
证明 A A A λ \lambda λ ∣ λ ∣ ≤ 1 |\lambda|\leq1 ∣ λ ∣ ≤ 1
令 n = 2 n=2 n = 2
A = [ 1 − α α α 1 − α ] , 0 < α ≤ 1. A=
\begin{bmatrix}
1-\alpha&\alpha\\
\alpha&1-\alpha
\end{bmatrix},
\qquad
0<\alpha\leq1. A = [ 1 − α α α 1 − α ] , 0 < α ≤ 1. 由第 1 小问可知，λ 1 = 1 \lambda_1=1 λ 1 = 1 A A A u / 2 \boldsymbol{u}/\sqrt2 u / 2 λ 2 \lambda_2 λ 2 w \boldsymbol{w} w A A A A k A^k A k
B = lim k → ∞ A k B=\lim_{k\to\infty}A^k B = k → ∞ lim A k 存在的 α \alpha α B B B
Kai (i)
誤差 e n = x − x n e_n=x-x_n e n = x − x n e n = ( P − 1 Q ) n e 0 e_n=(P^{-1}Q)^ne_0 e n = ( P − 1 Q ) n e 0 P − 1 Q P^{-1}Q P − 1 Q e 0 e_0 e 0 e n → 0 e_n\to0 e n → 0
ρ ( P − 1 Q ) < 1 \boxed{\rho(P^{-1}Q)<1} ρ ( P − 1 Q ) < 1 である。
(ii)
P = [ 12 0 0 0 4 0 0 0 4 ] Q = P − A = [ 0 4 − 3 3 0 0 − 3 2 0 ] P − 1 = [ 1 12 0 0 0 1 4 0 0 0 1 4 ] \begin{aligned}
P &= \begin{bmatrix} 12 & 0 & 0 \\ 0 & 4 & 0 \\ 0 & 0 & 4 \end{bmatrix} \\
Q &= P - A = \begin{bmatrix} 0 & 4 & -3 \\ 3 & 0 & 0 \\ -3 & 2 & 0 \end{bmatrix} \\
P^{-1} &= \begin{bmatrix} \frac{1}{12} & 0 & 0 \\ 0 & \frac{1}{4} & 0 \\ 0 & 0 & \frac{1}{4} \end{bmatrix} \\
\end{aligned} P Q P − 1 = 12 0 0 0 4 0 0 0 4 = P − A = 0 3 − 3 4 0 2 − 3 0 0 = 12 1 0 0 0 4 1 0 0 0 4 1 (iii)
P − 1 Q P^{-1}Q P − 1 Q λ \lambda λ
0 = det ( t I − P − 1 Q ) = λ 3 − 7 16 λ + 3 32 = 1 32 ( 2 λ − 1 ) ( 4 λ − 1 ) ( 4 λ + 3 ) ∴ λ = 1 2 , 1 4 , − 3 4 \begin{aligned}
0 &= \text{det}(tI - P^{-1}Q) \\
&= \lambda^{3} - \frac{7}{16} \lambda + \frac{3}{32} \\
&= \frac{1}{32} (2 \lambda - 1) (4 \lambda - 1) (4 \lambda + 3) \\
\therefore \ \
\lambda &= \frac{1}{2}, \frac{1}{4}, -\frac{3}{4}
\end{aligned} 0 ∴ λ = det ( t I − P − 1 Q ) = λ 3 − 16 7 λ + 32 3 = 32 1 ( 2 λ − 1 ) ( 4 λ − 1 ) ( 4 λ + 3 ) = 2 1 , 4 1 , − 4 3 である。よって、
ρ ( P − 1 Q ) = 3 4 \rho(P^{-1}Q) = \frac{3}{4} ρ ( P − 1 Q ) = 4 3 (iv)
x 1 = P − 1 b = [ 5 12 1 4 − 3 4 ] \begin{aligned}
x_1 = P^{-1}b = \begin{bmatrix} \frac{5}{12} \\ \frac{1}{4} \\ -\frac{3}{4} \end{bmatrix}
\end{aligned} x 1 = P − 1 b = 12 5 4 1 − 4 3 (v)
A − 1 = [ 8 63 5 63 − 2 21 2 21 13 42 − 1 14 − 1 21 2 21 2 7 ] , x = A − 1 b = [ 1 1 − 1 ] . \begin{aligned}
A^{-1}
&=
\begin{bmatrix}
\frac{8}{63}&\frac{5}{63}&-\frac{2}{21}\\
\frac{2}{21}&\frac{13}{42}&-\frac{1}{14}\\
-\frac{1}{21}&\frac{2}{21}&\frac{2}{7}
\end{bmatrix},\\
x=A^{-1}b&=\begin{bmatrix} 1 \\ 1 \\ -1 \end{bmatrix}.
\end{aligned} A − 1 x = A − 1 b = 63 8 21 2 − 21 1 63 5 42 13 21 2 − 21 2 − 14 1 7 2 , = 1 1 − 1 . (i)
a i j a_{ij} a ij A A A i i i j j j
A u = [ ∑ j = 1 n a 1 j , ∑ j = 1 n a 2 j , … ∑ j = 1 n a n j ] T = u \begin{aligned}
Au = \big[\sum_{j=1}^n a_{1j}, \sum_{j=1}^n a_{2j}, \ldots \sum_{j=1}^n a_{nj} \big]^T = u
\end{aligned} A u = [ j = 1 ∑ n a 1 j , j = 1 ∑ n a 2 j , … j = 1 ∑ n a nj ] T = u である。
(ii)
すべての要素が非負であり、
∣ ∑ j = 1 n a i j x j ∣ ≤ ∑ j = 1 n a i j ∣ x j ∣ ≤ ∑ j = 1 n a i j ∣ x m ∣ = ∣ x m ∣ \begin{aligned}
|\sum_{j=1}^n a_{ij} x_j| \le \sum_{j=1}^n a_{ij}|x_j| \le \sum_{j=1}^n a_{ij} |x_m| = |x_m|
\end{aligned} ∣ j = 1 ∑ n a ij x j ∣ ≤ j = 1 ∑ n a ij ∣ x j ∣ ≤ j = 1 ∑ n a ij ∣ x m ∣ = ∣ x m ∣ (iii)
固有ベクトルを [ x 1 , x 2 , … , x n ] T [x_1,x_2,\ldots,x_n]^T [ x 1 , x 2 , … , x n ] T ∣ x m ∣ = max j ∣ x j ∣ |x_m|=\max_j|x_j| ∣ x m ∣ = max j ∣ x j ∣ m m m
∣ ∑ j = 1 n a m j x j ∣ = ∣ λ x m ∣ . \left|\sum_{j=1}^na_{mj}x_j\right|=|\lambda x_m|. j = 1 ∑ n a mj x j = ∣ λ x m ∣. (ii) より、
∣ λ x m ∣ ≤ ∣ x m ∣ ∴ ∣ λ ∣ ≤ 1 \begin{aligned}
&|\lambda x_m| \le |x_m| \\
&\therefore |\lambda| \le 1
\end{aligned} ∣ λ x m ∣ ≤ ∣ x m ∣ ∴ ∣ λ ∣ ≤ 1 (iv)
tr ( A ) = λ 1 + λ 2 = 2 − 2 α ∵ λ 1 = 1 ∴ λ 2 = 1 − 2 α \begin{aligned}
&\text{tr} (A) = \lambda_1 + \lambda_2 = 2 - 2\alpha \\
&\because \lambda_1 = 1\ \ \ \therefore \lambda_2 = 1-2\alpha
\end{aligned} tr ( A ) = λ 1 + λ 2 = 2 − 2 α ∵ λ 1 = 1 ∴ λ 2 = 1 − 2 α ( A − ( 1 − 2 α ) I ) w = 0 ⇒ w = [ 1 2 , − 1 2 ] T \begin{aligned}
(A - (1 - 2\alpha)I) w = 0 \Rightarrow w = [\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}}]^T
\end{aligned} ( A − ( 1 − 2 α ) I ) w = 0 ⇒ w = [ 2 1 , − 2 1 ] T (v)
0 < α ≤ 1 0<\alpha\le1 0 < α ≤ 1 1 − 2 α 1-2\alpha 1 − 2 α
0 < α < 1 . \boxed{0<\alpha<1}. 0 < α < 1 . このとき、v = ( 1 , 1 ) T / 2 v=(1,1)^T/\sqrt2 v = ( 1 , 1 ) T / 2 w = ( 1 , − 1 ) T / 2 w=(1,-1)^T/\sqrt2 w = ( 1 , − 1 ) T / 2
A = [ v , w ] [ 1 0 0 1 − 2 α ] [ v , w ] T , A=[v,w]
\begin{bmatrix}1&0\\0&1-2\alpha\end{bmatrix}
[v,w]^T, A = [ v , w ] [ 1 0 0 1 − 2 α ] [ v , w ] T , なので
B = v v T = 1 2 [ 1 1 1 1 ] . B=vv^T
=\boxed{\frac12
\begin{bmatrix}1&1\\1&1\end{bmatrix}}. B = v v T = 2 1 [ 1 1 1 1 ] .